Устройство распознавания изображений текстовых знаков по энтропийным характеристикам тема диссертации и автореферата по ВАК РФ 05.13.05, кандидат технических наук Бородин, Михаил Владимирович

• Бородин, Михаил Владимирович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Бородин, Михаил Владимирович

Введение

1 Методы и устройства распознавания символов

1.1 Ввод информации.

1.2 Кодирование.

1.3 Предварительная обработка.

1.4 Распознавание.

1.5 Обучение.

1.6 Устройства распознавания текстовых знаков.

1.7 Выводы.

2 Способ формирования шаблонов

2.1 Способ оценки информативности элементов двоичных эталонных изображений

2.2 Обобщение способа оценки информативности элементов на случай цветных изображений.

2.3 Способы формирования шаблонов на основе информативности элементов

2.4 Связь между вероятностью правильного распознавания и расстоянием между эталонами.

2.5 Выводы.

3 Моделирование распознавания

3.1 Моделирующая программа.

3.2 Результаты моделирования.

3.3 Выводы.

4 Описание устройства распознавания

4.1 Устройство распознавания.

4.2 Блок формирования шаблонов.

4.3 Блок распознавания.

4.4 Выводы.

Введение диссертации (часть автореферата) на тему «Устройство распознавания изображений текстовых знаков по энтропийным характеристикам»

Создание текстов в электронной форме, при помощи персонального компьютера, в последние десять-пятнадцать лет стало повседневной практикой. Сейсас абсолютное большинство создаваемой офисной, научной и конструкторской документации представлено именно в электронной форме. Возникли и получили широкое распространение электронные библиотеки и базы данных научной, технической и учебной направленности.

Вместе с тем, в настоящее время, огромный массив текстовой информации по-прежнему доступен лишь на бумажных носителях. Нет необходимости подробно останавливаться на всех недостатках указанной ситуации — они очевидны. Достаточно упомянуть лишь о том, что поиск информации в электронном издании обычно занимает несколько секунд, в то время как для поиска той же информации в том же издании на бумажном носителе может потребоваться до нескольких часов.

Процесс перевода текстовой информации в электронную форму обычно состоит из двух этапов — сканирования и распознавания. К настоящему моменту разработано множество способов распознавания текстовых символов и целый ряд систем, реализующих эти способы. Большинство из них являются программными реализациями, среди которых есть несколько популярных пакетов OCR (Optical Character Recognition — оптическое распознавание символов). Современные программные реализации алгоритмов распознаг вания, как правило, приспособлены ко вводу единичных документов и мало подходят для обработки больших массивов текстовой информации по причине недостаточного быстродействия. Причина этому — плохая приспособленность универсальных компьютеров к решению как задач распознавания изображений текстовых знаков в частности, так и задач обработки изображений вообще.

Путь к достижению высокой скорости распознавания состоит в создании высокопроизводительных специализированных устройств распознавания. Применение таких устройств должно помочь решению проблемы массового перевода бумажных текстовых документов в электронную форму. В настоянщее время известен ряд устройств распознавания, однако большинство из них характеризуется недостаточной вероятностью правильного распознавания или повышенной вычислительной сложностью.

В связи с вышеизложенным, научно-техническая задача повышения вероятности правильного распознавания, а также скорости распознавания изображений текстовых знаков является актуальной.

Работа выполнена в рамках гранта Министерства образования и науки Российской Федерации 1.10.98 «Разработка фундаментальных основ и алгоритмического обеспечения автоматизированных систем обработки изображения» и темы 1-37.02 «Разработка программных средств обработки измерительной информации».

Объект исследования

Объектом исследования является процесс распознавания текстовых знаков. Цель работы

Цель работы состоит в повышении вероятности правильного распознавания текстовых знаков при вводе текстов с бумажных носителей путем разработки способа распознавания, с использованием шаблонов, сформированных на основе энтропийных характеристик элементов эталонов, и быстродействующего устройства, реализующего этот способ.

Задачи, решаемые в работе

1. Исследование зависимости вероятности правильного распознавания от энтропийных характеристик элементов эталонов и разработка способа определения информативности элементов на ее основе.

2. Разработка способа формирования шаблонов, на основе информативности элементов эталонов.

3. Сравнительное исследование предлагаемого способа формирования шаблонов и известного способа, основанного на использовании спинового стекла.

4. Разработка устройства, реализующего предложенный способ распознавания.

Методы исследования

При решении поставленных задач использовались методы теории проектирования элементов и устройств вычислительной техники и устройств управления, теории цифровых автоматов, теории алгоритмов, теории вероятностей и математического моделирования.

Научная новизна

1. Установлена связь между энтропийными характеристиками элементов эталонных изображений и вероятностью правильного распознавания знаков,-позволяющая оценить информативность элементов через их энтропийные характеристики.

2. Разработан способ оценки информативности элементов эталонных изображений на основе энтропийных характеристик.

3. Разработан способ формирования шаблонов на основе оценки информативности элементов эталонных изображений, позволивший снизить выроятность ошибки распознавания.

Практическая ценность

Практическая ценность работы заключается в разработке алгоритмических, аппаратных и программынх средств для распознавания изображений текстовых знаков. Предложенные алгоритмы могут найти широкое применение в системах распознавания текстовых знаков. Использование разработанных аппаратных средств позволит повысить вероятность правильного распознавания текстовых знаков при сохранении скорости распознавания, присущей наиболее быстродействующим устройствам этого класса.

Положения, выносимые на защиту

1. Способ оценки информативности элементов эталонных изображений на основе энтропийных характеристик.

2. Способ формирования шаблонов на основе оценки информативности элементов эталонных изображений.

3. Структурно-функциональная организация устройства распознавания изображений текстовых знаков.

Реализация и внедрение результатов исследований

Результаты работы внедрены в ОКБ «Авиаавтоматика», а также в учебном процессе кафедры «Программное обеспечение вычислительной техники» Курского государственного технического университета в рамках дисциплин «Методы и алгоритмы обработки изображений», «Высокоскоростные системы обработки символьной информации» и «Моделирование»

Апробация работы

Основные результаты диссертационной работы докладывались на:

1. III и IV Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий» (Улан-Удэ, 2002 и 2003 гг.);

2. XXXI вузовской научно-технической конференции «Молодежь и XXI век» (Курск 2003 г.);

3. I Международной научно-технической конференции «Современные инструментальные системы, информационные технологии и инновации» (Курск, 2003 г.);

4. VI Международной конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (Курск 2003 г.).

Публикации

Результаты исследований отражены в шести печатных работах. В работе [62] лично автором проведено моделирование распознавания с использованием различных наборов эталонов и установлена количественная связь между расстоянием между эталонами в пространстве признаков и вероятностью правильного распознавания. В работе [10] автором предложен алгоритм распознавания с использованием нелинейных преобразований. В работах [60, 63, 64] лично автором разработан способ формирования шаблонов на основе энтропийных характеристик эталонов, а также проведено моделирование распознавания с использованием этих шаблонов. В работах [9, 60] лично автором разработана структурно-функциональная схема устройства распознавания текстовых символов с использованием шаблонов.

Структура работы

Материалы исследований излагаются в четырех главах диссертации, введении, заключении и приложениях.

В первой главе проведен аналитический обзор методов и устройств распознавания символьной информации.

Во второй главе проведено исследование энтропийных характеристик элементов эталонов и их связи с вероятностью верного распознавания предъявленных образов. Также в этой главе рассматривается способ формирования шаблонов на основе вышеназванных характеристик.

В третьей главе описываются программные средства для проведения моделирования распознавания образов по предлагаемому методу, а также представлены результаты моделирования распознавания цифр по их черно-белым изображениям.

В четвертой главе описывается устройство, реализующее предложенный способ формирования шаблонов и распознавания образов.

В приложениях представлены исходные тексты программ моделирования алгоритма и устройства распознавания.

Область возможного применения

Разработанное устройство может быть использовано в системах автоматического чтения текстов при вводе их с бумажных носителей.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Бородин, Михаил Владимирович

4.4 Выводы

1. Разработан алгоритм функционирования устройства распознавания образов с использованием шаблонов, основанных на энтропийных характеристиках.

2. На основе разработанного алгоритма синтезировано устройство распознавания.

Заключение

1. Разработан способ определения информативности элементов эталонов, основанный на вычислении изменения энтропии в процессе распознавания, взвешенного с учетом вы-роятности появления реализации каждого класса. Способ может использоваться как с двоичными эталонами, так и с эталонами, элементы которых принадлежат некоторому конечному множеству.

2. Разработан способ формирования шаблонов на основе анализа информативности элементов эталонов, позволяющий регулировать уровень вычислительной сложности процесса распознавания путем задания общего количества шаблонных элементов.

3. Разработана программа моделирования распознавания образом, заданых двоичными эталонами. Программа позволяет формировать шаблоны на основе предлагаемого способа или с использованием спинового стекла, а также формировать тестовые последовательности образов и распознавать как с использованием шаблонов, так и без такового. Проведенное, при помощи разработанной программы, моделирование показало, что при использовании одинакового количества шаблонных элементов предлагаемый способ формирования шаблонов позволяет сократить количество ошибок распознавания в 1,5-2 раза по сравнению с использованием спинового стекла при условии того, что зашумленность распознаваемого образа не превосходит 45-55%.

4. Разработанно устройство распознавания, реализующее предлагаемый способ формирования шаблонов и обеспечивающее тем самым меньшее количество ошибок распознавания по сравнению с устройством, использующим спиновое стекло, при одинаковых вычислительных затратах на этапе распознавания. Также предложенное устройство позволяет сократить вычислительные затраты на этапе распознавания по сравнению с устройством, не использующими шаблоны.

Список литературы диссертационного исследования кандидат технических наук Бородин, Михаил Владимирович, 2004 год

1. Предобработка ультразвуковых снимков с помощью нейронных сетей Хопфилда / Агапкин О. А., Орлов Ю. В., Персианцев И. Г., Доленко С. А. // Распознавание образов и анализ изображений: б-ая Междунар. конф. 21-26 октября 2002. — Новгород, 2002. - С. 1-6.

2. А. с. № 1508255. Устройство для распознавания графических изображений / Акимов В. М. и др. МКИ G 06 К 9/00.

3. А. с. № 1418775. Устройство для считываения стилизованных знаков / Алферьев Н. А. и др. МКИ G 06 К 9/18.

4. Аникин И. В., Шагиахметов М. В. Методы нечеткой обработки, распознавания и анализа изображений // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26 октября 2002. — Новгород, 2002. — С. 16-21.

5. Арлозоров В. В. Cognitive Form: Распределенная система потокового распознавания стандартных форм документов // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26 октября 2002 г. — Новгород, 2002. — С. 41-46.

6. Методы цифровой обработки изображений / А. Е. Архипов, С. В. Дегтярев, С. С. Садыков и др. Ч. 2 — Курск: Изд-во Курск гос. техн. ун-та. 2002. — 118 с.

7. Бородин М. В. Устройство распознавания символов по шаблонам. / Современные инструментальные системы, информационные технологии и инновации: Междунар. науч.техн. конф. Курск: КГТУ, 2003. - С. 59-62.

8. Бородин М. В. Об использовании нелинейного преобразования при распознавании образов. / Молодежь и XXI век: Вуз. науч.-техн. конф. — Курск: КГТУ, 2003. — С. 98-99.

9. А. с. JST* 760134. Устройство для распознавания образов / Боюн В. П. и др. — МКИ G 06 К 9/00.

10. Бутаков Е. А. и др. Обработка изображений на ЭВМ. — М.: Радио и связь, 1987. — 250 с.

11. Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974. 416 с.

12. Ветров Д. П. Об устойчивости алгоритмов распознавания образов // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26 октября 2002. — Новгород, 2002. С. 96-100.

13. А. с. JV« 1339601. Устройство для распознавания изображений / Гавришин А. И. и др. МКИ G 06 К 9/00.

14. А. с. № 1652984 Способ формирования признаков при распознавании изображений объектов / Гордиенко В. И. и др. — МКИ G 06 К 9/18.

15. А. с. № 746610. Способ распознавания изображений / Грицык В. В. и др. — МКИ G 06 К 9/00.

16. Гуревич И. В., Коребкина И. В. Метод классификации изображений на основе их информационных характеристик // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26 октября 2002. — Новгород, 2002. — С. 172-177.

17. А. с. JV® 2003174. Способ распознавания изображений / Деныциков И. К. и др. — МКИ G 06 К 9/00.

18. А. с. № 945875. Способ автоматической классификации знаков и устройство для его осуществления / Диетер Ш. — МКИ G 06 К 9/00.

19. Дорофенюк А. А. Алгоритмы автоматической классификации. // Автоматика и телемеханика, 1971, №12, с. 78-113.

20. А. с. JV® 1583946. Устройство для коррекции изображений / Државетский А. Л. — МКИ G 06 К 9/00.

21. А. с. N® 1631562. Устройство для селекции дефектов изображений / Државетский А. Л. МКИ G 06 К 9/16.

22. Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1976. — 512 с.

23. Еремин И. И., Мазуров В. Д. Кусочно-аффинная разделяющая функция в распознавании // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26октября 2002. — Новгород, 2002. — С. 224-226.

24. А. с. № 1575211. Устройство для распознавания образов / Ефимов Ю. Н. — МКИ G 06 К 9/00.

25. Жгун Т. В., Киросянов Б. Ф. Распознавания двоичной информации, перемешанной со случайными символами // Распознавание образов и анализ изображений: 6-ая Между-нар. конф. 21-26 октября 2002. — Новгород, 2002. — С. 231-233.

26. А. с. № 1543431. Устройство для идентификации текстовых изображений / Жук Ю. К. и др. МКИ G 06 К 9/00.

27. Забияка Ю. И. Инвариантный критерий близости контуров, основанный на представлении изображений неравномощными множествами признаков // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26 октября 2002. — Новгород, 2002. С. 233-237.

28. Загоруйко Н. Г. Методы распознавания и их применение. — М.: Книга, 1972.

29. А. с. № 1236518. Устройство для распознавания рукописных символов / Зубарев Ю. Б. МКИ G 06 К 9/00.

30. А. с. J№ 1164749. Устройство для считывания символов / Исмаилов Т. К. и др. — МКИ G 06 К 9/00.

31. Катыс Г. П. Восприятие и анализ оптической информации автоматической системой. — М.: Машиностроение, 1986. — 415 с.

32. Катыс Г. П. Обработка визуальной информации. — М.: Машиностроение, 1990. — 314 с.

33. А. с. № 1298782. Устройство для распознавания цифр / Корнейчук В. И. и др. — МКИ G 06 К 9/00.

34. А. с. № 1658181. Устройство для логической обработки изображений / Красиленко В. Г. и др. МКИ G 06 К 9/00.

35. А. с. № 1668984. Устройство для логической обработки изображений / Красиленко В. Г. и др. МКИ G 06 К 9/00.

36. А. с. № 1107139. Устройство для распознавания стилизованных цифр / Кудрявцев В. Б. и др. МКИ G 06 К 9/00.

37. А. с. № 1244683. Устройство для распознавания образов / Латышенок Н. Н. и др. — МКИ G 06 К 9/00.

38. Логинов А. И. Системы технического зрения. — М.: МИРЭА, 1991.

39. А. с. № 1705843. Устройство для корреляционной обработки изображений / Май-орчук М. А., Самохин Ю. С. МКИ G 06 К 9/00.

40. А. с. № 1101856. Устройство для считывания и распознавания нормализованных символов / Осипов JI. А. — МКИ G 06 К 9/00.

41. А. с. № 1229784. Устройство для считывания стилизованного шрифта / Осипов. JI. А. МКИ G 06 К 9/00.

42. Осовский С. Нейронные сети для обработки информации. — М.: Финансы и статистика, 2002. — 344 с.

43. А. с. № 1665395. Устройство для распознавания изображений объектов / Попов. М. А. МКИ G 06 К 9/00.

44. Постников В. В. Идентификация и распознавание документов заранее известной структуры // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26 октября 2002 г. — Новгород, 2002. — С. 459-464.

45. Пратт Т., Зелковиц М. Языки программирования. Разработка и реализация. — СПб.: Питер, 2002. 688 с.

46. Прет У. Цифровая обработка изображений: В 2-х кн.: Пер. с англ. — М.: Мир, 1972 г. Кн. 1. 312 е., Кн. 2. - 480 с.

47. Принс М. Д. Графические методы связи человек — вычислительная машина при машинном проектировании. // ТИИЭР. — 1966. №16. — с. 78.

48. Пытьев Ю. П., Чуличнов А. И. Морфологический анализ изображений: принципы и применение // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26 октября 2002. — Новгород, 2002. — С. 464-469.

49. Рахманкулов В. 3. и др. Алгоритм распознавания объемных образов на базе модифицированного метода максимальной клики. / Сб. тр. Института системного анализа РАН. М.: РАН, 2002 г.

50. Розенфельд А. Распознавание и обработка изображений. — М.: Мир, 1972. — 230 с.

51. Распознавание оптических изображений / Под. ред. Ю. С. Сагдулаева, В. С. Титова. — Ташкент: ТЭИС, 2000. 315 с.

52. Сайфер В. А. Компьютерная обработка изображений // Методы и алгоритмы: Соровский образовательный журнал. — 1996. 3. — с. 110-121.

53. Семерий О. С. Распознавание геометрических объектов с помощью функций расстояния // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26 октября 2002 г. — Новгород, 2002. — С. 484-491.

54. Старков Е. Ф. Устройство выделения ядра класса изображений. / Тр. Юбилейной науч. конф. Курск: КГТУ, 1995. — С. 62-64.

55. Старков Е. Ф. Нейронно-структурная модель распознавания изображений символов. / Тез. докл. Юбилейной конф. ученых Курского политехнического института. — Курск: КПИ, 1994. С. 98-100.

56. Старков Е. Ф., Титов В. С. Использование спинового стекла для получения шаблонов символов // Автоматика и телемеханика. — М., 1999, № 9. — С. 144-154.

57. Старков Е. Ф., Бородин М. В. Устройство распознавания биомедицинской информации. // Системный анализ и управление в биомедицинских системах. — М., 2003, Т. 2, № 4. С. 350-353.

58. А. с. № 2178916. Устройство для распознавания изображений символов / Старков Е. Ф., Старков Ф. А. МКИ G 06 К 9/00.

59. Старков Ф. А., Бородин М. В. О взаимосвязи качества распознавания и расстояния между эталонами. / Теоретические и прикладные вопросы современных информационных технологий: Всерос. научн.-техн. конф. — Улан-Удэ: ВСГТУ, 2002. — С. 113-116.

60. Старков Ф. А., Бородин М. В. О способе формирования шаблонов с использованием энтропии. / Теоретические и прикладные вопросы современных информационных технологий: Всерос. научн.-техн. конф. — Улан-Удэ: ВСГТУ, 2002. — С. 62-65.

61. Суворова Е. А., Шейнин Ю. Е. Проектирование цифровых систем на VHDL. — СПб.: БХВ-Петербург, 2003. 576 с.

62. Файн В. С. Описание изображений: основы непрерывно-групповой теории и ее приложения. — М.: Наука, 1970. — 296 с.

63. А. с. № 1387025. Устройство для распознавания образов / Федотов Н. Г. — МКИ G 06 К 9/00.

64. Федотов Н. Г., Шульга Л. А. Теория распознавания образов, основанная на статистической геометрии // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26 октября 2002 г. — Новгород, 2002. — С. 579-586.

65. Фомин Я. А., Тарловский Г. Р. Статистическая теория распознавания образов. — М.: Радио и связь, 1986. — 185 с.

66. Фор А. Восприятие и распознавание образов. — М.: Машиностроение, 1989. — 272 с.

67. Фу К. Структурные методы в распознавании образов. — М.: Мир, 1977. — 319 с.

68. Быстрые алгоритмы в цифровой обработке изображений. Пер. с англ. / Под ред. Т. Хуанга. — М.: Радио и связь, 1984. — 221 с.

69. Чикин В. А. Структура данных для представления изображений // Зарубежная радиоэлектроника. — 1983. №8. — С. 87-103.

70. А. с. N® 1583946. Устройство для фильтрации изображений / Широков В. А., Маркова А. Г. МКИ G 06 К 9/00.

71. А. с. № 945875. Способ автоматической классификации знаков и устройство для его осуществления / Шнейдер Д. — МКИ G 06 К 9/16.

72. Шоломов Д. Л. Идентификация нечетко распознанных текстовых конструкций // Распознавание образов и анализ изображений: 6-ая Междунар. конф. 21-26 октября 2002 г. — Новгород, 2002. — С. 623-627.

73. Яншин В. В. Анализ и обработка изображений: принципы и алгоритмы. — М.: Машиностроение, 1995. — 112 с.

74. Berikov V. В., Lbov G. S., Litvinenko A. G. Evaluation of Recognition Performance for Discrete Classifier // Pattern Recognition and Image Understanding: The 6th German-Russian workshop. August 25-30, 2003, Novosibirks, 2003, — pp. 34-38.

75. Fernandez G., Huntsberger T. Wavelet-based system for recognition and labeling of polyhedral junctions // Optical Engineering. — 2003. V. 37, N. 1. — pp. 158-166.

76. Freeman H. On the Encoding of Arbitrary Geometric Configurations. // IRE Trans. V. EC-10 (2). 1961. №6. - pp. 260-268.

77. Gusev V. D., Nemytikova L. A., Chuzhanova N. A. Adaptive Algorithm of Pattern Matching in Symbolic Sequences // Pattern Recognition and Image Understanding: The 6th German-Russian workshop. August 25-30, 2003, Novosibirks, 2003. — pp. 42-46.

78. Lossan N. Werden Computer denken wie wir? // VFI nachnchten magazin. — 1989.2. pp. 30-33.

79. Michalski R. S. et Dedoy E. A recent advance in data analysis. // North Holland Edit. — 1981. pp. 33-56.

80. Nedel'ko V. M. Voting by Several Decision Rules and Bayesian Strategy of Precision // Pattern Recognition and Image Understanding: The 6th German-Russian workshop. August 25-30, 2003, Novosibirks, 2003, — pp. 51-55.

81. Ogawa H. Image reconstruction from incomplete projection. IEEE. — 1982. — pp. 534539.

82. Pestunov I. Adaptation of the Nonparameterical Rosenblatt-Parzen classifiers to Non-stationary of Classes // Pattern Recognition and Image Understanding: The 6th German-Russian workshop. August 25-30, 2003, Novosibirks, 2003. — pp. 55-58.

83. Postnikov V. V., Shalomov D. L., Marchenko A. E. Flexidocs: The Template Driven Document Recognition Technology // Pattern Recognition and Image Understanding: The 6th German-Russian workshop. August 25-30, 2003, Novosibirks, 2003. — pp. 194-198.

84. Quintiliano P., Santa-Rosa A. Landsat Images Classification Based on KLI with Multiple Threshold // Pattern Recognition and Image Understanding: The 6th German-Russian workshop. August 25-30, 2003, Novosibirks, 2003. — pp. 198-202.

85. Taketsugu Yao, Takumi Minemoto Pattern recognition by quantization of modulated function to complexes of a quadrupole on matched filtering // Optical Engineering. — 2003, V. 42, N. 10. pp. 2994-3004.