Адаптивные алгоритмы распознавания текстов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Титов, Юрий Васильевич

• Титов, Юрий Васильевич
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Титов, Юрий Васильевич

ВВЕДЕНИЕ.

ГЛАВА 1 «ОБЗОР ПРИЗНАКОВЫХ И АДАПТИВНЫХ АЛГОРИТМОВ РАСПОЗНАВАНИЯ ТЕКСТОВ».

1.1 вступление.

1.2 Метод характерных фрагментов.

1.2.1 Описание двухградационных изображений.

1.2.2 Алгоритмы выделения характерных фрагментов.

1.2.3 Векторы, задающих форму характерных фрагментов.

1.2.4 Векторы, задающие местоположение характерных фрагментов.

1.3 Адаптивное распознавание.

1.3.1 Общая схема адаптивного распознавания.

1.3.2 Создание эталонов.

1.3.3 Дораспознавание.

1.4 Штрафные функции.

1.5 Выводы.

ГЛАВА 2 «МЕТОДЫ И ПРОБЛЕМЫ АДАПТИВНОГО РАСПОЗНАВАНИЯ ОТСКАНИРОВАННОГО ТЕКСТА».

2.1 Основные задачи адаптивного распознавания.

2.1.1 Построение идеального образа.

2.1.2 Сравнение символа с эталоном.

2.2 Искажение символов при сканировании.

2.2.1 Определения.

2.2.2 Представление символа.

2.2.3 Влияние аппаратной функции.

2.2.4 Размеры прообраза.

2.2.5 Тонкие линии.

2.2.6 Наклонные линии на сетке.

2.2.7 Распределение полутонов. Количественные характеристики.

2.3 выводы.

ГЛАВА 3 «ФУНКЦИИ СРАВНЕНИЯ С ИДЕАЛЬНЫМ ОБРАЗОМ В АДАПТИВНОМ РАСПОЗНАВАНИИ»

3.1 Построение идеальных образов.

3.2 Уплотненные взвешенные растры.

3.2.1 Простейший случай укладки взвешенного растра.

3.2.2 Мера плотности укладки взвеш енных растров.

3.2.3 Укладка сложных растров.

3.3 Отличие символов от идеальных образов.

3.4 Стандартные функции сравнения - основные недостатки.

3.5 Алгоритм построения специальной функции сравнения.

3.6 Выводы.

ГЛАВА 4 «РЕАЛИЗАЦИЯ АДАПТИВНОГО АЛГОРИТМА».

4.1 Подбор параметров при обучении.

4.2 Инструментарий исследователя.

4.2.1 Компонента кластеризации.

4.2.2 Компонента просмотра и редактирования кластеров.

4.3 Полная схема алгоритма распознавания.

4.4 Выводы.

Введение диссертации (часть автореферата) на тему «Адаптивные алгоритмы распознавания текстов»

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

Во всех системах электронного документооборота и системах ввода печатных текстов одним из ключевых этапов является этап распознавания текстовых символов - перевод информации из графической формы - результата сканирования - в текстовую форму. Несмотря на многолетнюю историю развития алгоритмов распознавания [7, 11, 15, 21, 33, 37, 40] и существование большого количества алгоритмов хорошо распознающих четко напечатанные тексты, задача распознавания в более сложных случаях далека от решения. Деловой мир и все отрасли экономики ставят задачу дальнейшего увеличения точности распознавания, включая, в том числе, распознавание документов низкого качества. В частности, существующие алгоритмы обеспечивают относительно невысокую по сравнению с человеком-оператором точность распознавания текстов с графических изображений, полученных сканированием с малыми разрешениями. Среди прочего стоит отметить класс задач, в которых имеющееся графическое изображение невозможно улучшить путем увеличения разрешения сканирования или изменением параметров сканирования. К таким задачам относятся уже созданные ранее электронные архивы документов в виде растровых изображений, электронные библиотеки, факсимильные сообщения и пр.

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

Одной из распространенных схем распознавания текстов показавшей высокую точность является адаптивное распознавание - шрифтонезависи-мый алгоритм, использующий особенности распознаваемых символов. Данный алгоритм является представителем класса алгоритмов основанных на сравнении с эталоном. Одним из ключевых моментов любого алгоритма распознавания этого класса является используемая функция сравнения (мера близости [25], функция правдоподобия [14], функция расстояния [30]) - с помощью которой и происходит определение принадлежности распознаваемого символа к одному из классов.

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

Целями диссертации являются:

1) исследование преобразования символов при сканировании с целью получения точной картины возникающих искажений;

2) разработка улучшенных алгоритмов построения идеального образа распознаваемого символа - эталона;

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

Научная новизна работы состоит в следующем:

• проведен анализ алгоритмов адаптивного распознавания, и предложены уточненные методы решения на основе идеальных образов;

• проведено исследование искажений образов при сканировании и предложена модель для расчета вероятности возникновения ошибки заданной величины при сканировании бинарного образа с последующей бинаризацией;

• введено понятие уплотненных взвешенных растров и обоснована необходимость их применения;

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

Содержание диссертации организовано в соответствии с указанными выше целями.

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

Рассмотрены алгоритмы, разработанные в 70-80-х годах использующих выделение характерных фрагментов, основанные на геометрии символов.

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

Так же анализируются достоинства и недостатки применения штрафных функций для увеличения точности адаптивного распознавания.

Во второй главе поставлены две задачи распознавания с помощью идеальных образов символов: получение идеальных образов и сравнение с идеальным образом.

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

Описана модель искажения образа при сканировании.

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

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

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

В четвертой главе описаны особенности реализации алгоритма сравнения символов с идеальными образами и его внедрение в программу распознавания текста OCR Cognitive Cuneiform®. Описаны использованные программные компоненты, созданные специально для исследования алгоритмов распознавания. Протестировано обучение при подборе параметров в функции близости, предложенной в третьей главе.

По теме диссертации опубликовано 4 работы, одна из них в соавторстве; зарегистрирован патент на полезную модель.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Титов, Юрий Васильевич

Выводы и заключение

Основные теоретические и практические результаты работы заключаются в следующем:

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

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

3. Предложено использовать уплотненные взвешенные растры в качестве идеальных образов.

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

5. С помощью разработанного алгоритма поиска характерных фрагментов была существенно улучшена схема адаптивного распознавания с дообучением. Приведенный в работе алгоритм реализован в качестве составной части программы распознавания текстов OCR Cognitive Cuneiform®.

Список литературы диссертационного исследования кандидат технических наук Титов, Юрий Васильевич, 2007 год

1. Ануфриев И. MATLAB 7.0 Наиболее полное руководство - БХВ-Петербург, 2005 г. 1104 стр.

2. Арлазаров В.В. Структурирование визуальных представлений информационной среды и методы определения надежности распознавания: дис. канд. тех. наук М., 2004. 120 с.

3. Арлазаров B.J7., Котович Н.В., Славин O.A. Адаптивное распознавание // Информационные технологии и вычислительные системы № 4, 2002. С. 11-22

4. Арлазаров B.JL, Котович Н.В., Троянкер В.В. Адаптивное распознавание символов // Сб. трудов ИСА РАН "Интеллектуальные технологии ввода и обработки информации", 1998

5. Арлазаров В.Л., Логинов A.C., Славин O.A. Характеристики программ оптического распознавания текста// Программирование № 3, 2002. С. 45-63

6. Арлазаров В.Л., Славин O.A. Алгоритмы распознавания и технологии ввода текстов в ЭВМ. // Информационные технологии и вычислительные системы 1996. № 1. С. 48-54

7. Бонгард ММ Проблема узнавания. М.: Наука. 1967.

8. Браверман Э.М., Мучник И.Б. Структурные методы обработки эмпирических данных. М.: Наука. 1983.- 464 с.

9. Гинзбург А., Милчев М., Солоницын Ю. Периферийные устройства. Принтеры, сканеры, цифровые камеры Питер 2001.-448 стр.

10. Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB Техносфера, 2006 г. - 616 стр.11 .Дуда Р., Харт П. Распознавание образов и анализ сцен./ Пер. с анг. М.: Мир, 1976.-511 с.

11. Дьяконов В. Maple 8 в математике, физике и образовании Солон-Пресс, 2003 г. 656 стр.

12. Завалишин Н.В., Мучник И.Б. Модели зрительного восприятия и алгоритмы анализа изображений. М.: Наука, 1974.

13. Ковалевский В.А. Методы оптимальных решений в распознавании изображений. М.: Наука, 1976 г. - 328 стр.

14. Ковалевский В.А. Современное состояние проблемы распознавания образов. Кибернетика, №5, 1967

15. Мисюрёв A.B. Использование искусственных нейронных сетей для распознавания рукопечатных символов. // Сб. трудов ИСА РАН "Интеллектуальные технологии ввода и обработки информации", 1998, С.122-127

16. Мучник КБ. Формирование языка описания зрительных образов. // В сб. под ред. Э.М.Бравермана «Автоматический анализ сложных изображений»,— М.: Мир, 1969

17. Постное КА. Лекции по Общей Астрофизике для Физиков, курс лекций 2001 г., физический факультет МГУ // http://www.astronet.ru/db/msg/1170612/31ec/node5. html

18. Потемкин В. Г. Вычисления в среде MATLAB Диалог-МИФИ, 2004 г. 720 стр.

19. Роджерс Д. Алгоритмические основы машинной графики. — М.: Мир, 1989. —512 стр.

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

21. Славин O.A. Комбинированные методы распознавания печатных и рукопечатных символов. // Сб. трудов ИСА РАН "Документооборот. Концепции и инструментарий", 2004, С. 151-173

22. Славин O.A. Распознавание атрибутов текстовых символов. // Сб. трудов ИСА РАН "Документооборот. Концепции и инструментарий", 2004, С. 142-150

23. Славин O.A. Средства управления базами графических образов символов и их место в системе распознавания // Сборник трудов ИСА РАН «Развитие безбумажных технологий в организациях», 1999, с. 317-330

24. Славин О.А., Подрабинович А.А. Древовидное распознавание нормализованных символов // Сборник трудов ИСА РАН «Интеллектуальные технологии ввода и обработки информации», 1998, с. 137-156.

25. Славин О.А. Титов Ю.В. Динамическое построение функций сравнения с идеальным образом в задаче адаптивного распознавания текстовых символов. // Информационные технологии и вычислительные системы 2007. № 1.С. 3-12

26. Степаненко О.С. Сканеры и сканирование. Краткое руководство, Диалектика, 2004 г. 288 стр.

27. Титов Ю.В. Об искажении символов при сканировании // Сб. тр. ИСА РАН «Системный подход к управлению информацией», 2006. С. 260288.

28. Титов Ю. В. О восстановлении идеального прообраза по коллекции образов // Сб. тр. ИСА РАН «Системный подход к управлению информацией», Москва: URSS, 2006. С. 252-259.

29. Дж.Ту, Р.Гонсалес Принципы распознавания образов Мир, 1978, -414 стр.

30. Шарыгин М. Е. Сканеры и цифровые камеры, BHV Санкт - Петербург, Арлит 2000, - 384 стр.

31. Breuel Т. М. An Algorithm for Finding Maximal Whitespace Rectangles at Arbitrary Orientations for Document Layout Analysis. Proceedings of the Seventh International Conference on Document Analysis and Recognition (ICDAR'03), NJ, USA, 2003. P. 66-71

32. Cooper D.B., Cooper P.W., Non-supervised Adaptive Signal Detection and Pattern Recognition. Information and Control, vol. 7, Sept., 1969

33. Dias A.P. Minimum Spanning Trees for Text Segmentation // In Proc. of the Fifth Annual Symposium on Document Analysis and Information Retrieval, Las Vegas, Nevada, 1995. P. 61-65.

34. O'Gorman L. The Document Spectrum for Page Layout Analysis // IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993. V. 15. №11. P. 1162-1173

35. Green E., Krishnamoorthy M. Model-based analysis of printed tables // In Proceedings of International Conference on Document Analysis and Recognition (ICDAR), 1995. P. 214-217.

36. Haung T., Fu K.S., Stochastic Syntactic Analysis for Programmed Grammars and Syntactic Pattern Recognition, vol 1, №3, 1972

37. Ittner D. Automatic Inference of Textline Orientation // In Proc. of the Second Annual Symposium on Document Analysis and Information Retrieval, Las Vegas, Nevada, 1993. P. 123-133

38. Kise K., Yanagida O., Takamatsu S. Page Segmentation Base on Thinning of Background // In Proc. of the 13th International Conference on Pattern Recognition, page 788-792, Vienna, Austria, August 1996. P. 788-792

39. Kovalevsky V.A. Present and Future of Pattern Recognition Theory, Proceeding of IFIP Congress 65, Spartan Books, Washington D.C. 1965

40. Lebourgeois F., Henry J.L. An Evolutive OCR System Based on Continuous Learning // Proceedings of the 3rd IEEE Workshop on Applications of Computer Vision (WACV '96), December 1996. P. 272-277

41. Sawaki M., Hagita N., Ishii K. Robust Character Recognition of Gray-Scaled Images with Graphical Designs and Noise // Proceedings of Fourth International Conference Document Analysis and Recognition (ICDAR'97), 1997. P. 491-494.

42. Trier 0. D., Taxt T. Evaluation of Binarization Methods for Document Images // IEEE Transactions on pattern analysis and machine intelligence, vol. 17, No 3, March 1995. P. 312-315

43. Tubbs К. M, Embley D. W. Recognizing records from the extracted cells of microfilm tables // In Proceedings of the 2002 ACM Symposium on Document Engineering, ACM Press, New York, NY, 2002. P. 149-156.

44. Zlatopolsky A.A. Automated document segmentation // Pattern Recognition Letters, July 1994. V. 15. №7. P. 699-704.

45. CR CuneiForm система оптического распознавания текстов. // http://www.cuneiform.ru/

46. Система оптического распознавания текстов CuneiForm // http://www.cognitive.ru/products/cuneiform.htm

47. Пакет компьютерной алгебры Maple официальный сайт // http://www.maplesoft.com/

48. Пакет математического моделирования MATLAB официальный сайт // http ://www. mathworks. com/products/matlab/