автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Автоматическая идентификация и распознавание структурированных документов

1 ВВЕДЕНИЕ.

1.1 Предварительные замечания.

1.2 Обзор существующих методов.

1.2.1 Методы описания формы документа и его идентификации.

1.2.2 Методы обработки изображения и выделения графических примитивов.

1.2.3 Замечания.

1.3 Задача идентификации и распознавания структурированных документов.

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

2 МОДЕЛЬ ДОКУМЕНТА.

2.1 Моделирование содержания и структуры документа.

2.1.1 Структурированное множество.

2.1.2 Структурированный информационный объект.

2.1.3 Логическая структура и физическая структура информационного объекта.

2.1.4 Однотипные структурированные документы.

2.1.5 Конверсия физической структуры: поле страницы - поле документа - поле информационного объекта.

2.1.6 Жесткое и нежесткое разбиение на страницы.

2.1.7 Пакет типовых документов.

2.2 Моделирование визуального представления документа.

2.2.1 Требования к моделированию визуального представления.

2.2.2 Координаты и обозначения.

2.2.3 Формы с жестко и нежестко фиксированным расположением элементов.

2.2.4 Примеры инвариантов расположения элементов.

2.2.5 Модель блочной декомпозиции.

2.2.6 Модель табличной декомпозиции.

2.2.7 Декомпозиция таблично-неделимых блоков.

2.2.8 Декомпозиция угловых блоков.

2.2.10 Повторяющиеся блоки элементов.

2.2.11 Декомпозиция блоков, построенных по принципу "укладка и перетекание ".

2.2.12 Декомпозиция документа, разделенного на страницы и колонки.

2.3 Шаблон структурированного документа.

2.3.1 Требования к полноте перечисления элементов.

2.3.2 Шаблоны логически однотипных форм.

2.3.3 Шаблон документа как основа для комбинирования методов идентификации и распознавания.

3 МЕТОДЫ ИДЕНТИФИКАЦИИ СТРУКТУРИРОВАННЫХ ДОКУМЕНТОВ.

3.1 Идентификация формы и сопоставление фрагментов графического образа элементам шаблона.

3.1.1 Пример установленного соответствия.

3.1.2 Варианты деформаций, допустимых при построении отображения.

3.1.3 Неоднозначность отображения.

3.1.4 Алгоритмы отображения при условии жесткого расположения элементов.

3.1.5 Расчет параметров деформации по подмножеству отображенных элементов.

3.1.6 Расчет параметров деформации в схеме «голосование за назначение».

3.1.7 Поиск отображения в итеративной схеме «оптимальное назначение» - «выбор непротиворечивого подмножества».

3.1.8 Алгоритм отображения при условии нежесткого упорядоченного расположения элементов.

3.2 Предобработка и анализ графического образа страницы.

3.2.1 Бинаризация графического образа.

3.2.2 Фрагментация графического образа страницы.

3.2.3 Выделение и снятие линий разграфки.

3.3 Контекстный анализ результатов распознавания.

3.3.1 Основные задачи контекстной постобработки.

3.3.2 Структура результатов распознавания.

3.3.3 Поиск фрагментов текста в распознанной строке с нефиксированными краями.

Алгоритм МСНБЯ.

4 СИСТЕМА МАССОВОГО ВВОДА СТАНДАРТНЫХ ФОРМ ДОКУМЕНТОВ.

4.1 Обзор системы.

4.1.1 Этапы технологической цепочки ввода стандартных форм.

4.1.2 Основные компоненты системы.

4.2 Реализованные проекты и особенности технической реализации.

4.2.1 Ввод налоговых документов.

4.2.2 Ввод документов пенсионного страхования.

4.2.3 Ввод анкет школьников и студентов, анкет-заявок на изготовление «Социальной карты москвича».

4.2.4 Ввод платежных поручений и мемориальных ордеров.

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

Как альтернатива ручному вводу, существуют технологии автоматизированного ввода форм, которые обладают рядом явных преимуществ: современные модели сканеров могут вводить до 200 страниц в минуту, программы оптического распознавания текста "читают" несколько сотен символов в секунду и могут делать это без перерыва на обед.

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

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

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

• идентификации отсканированного документа среди прочих, выделении в обрабатываемом потоке однотипных документов

• идентификации составных частей документа и выделении полей ввода данных

• распознавания и обработки автоматически выделенных полей ввода данных

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

• моделирования структурированного документа с точки зрения задач идентификации и распознавания

• автоматизации разработки шаблона документа (экземпляра модели структурированного документа определенного типа)

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

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

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

Основные результаты данной работы докладывались и обсуждались на международном симпозиуме "Человек, среда, техника - 95" (конференция "Цифровая фотограмметрия и дистанционное зондирование"), Санкт-Петербург, 1995, а также на международной конференции 5th German-Russian Workshop on Pattern Recognition and Image Understanding (GRWS98), Мюнхен, 1998.

Основные результаты, изложенные в работе опубликованы в статьях [МП99], [МПОО], [Пос98], [Пос98а], [Пос99], [Пос99а].

Результаты проведенных исследований апробированы и использованы в рамках системы массового ввода стандартных форм документов Cognitive Forms. Широкий спектр документов, обрабатываемый в ряде промышленных проектов, реализованных на базе системы, позволяет делать вывод о состоятельности основных положений работы.

5 Заключение

В диссертации получены следующие основные результаты.

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

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

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

Формализована система связей между объектами, выделяемыми на странице. Эта формализация служит основой построения функции оценки близости наложения реального документа на заранее подготовленный шаблон.

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

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

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

1. АС96.1. АКС99.1. БС98.1. Еме87. Еме88]1. ЕССОО.1. МП99. МПОО]1. Пос98.1. Пос98а.1. Пос99.1. Пос99а.1. СКБ99. Сла99]

2. Постников В.В., Разработка методов наложения формы на графическое изображение документа. В сб. «Интеллектуальные технологии ввода и обработки информации», Москва, 1998

3. СП98. Славин О.А., Подрабинович А.А. Древовидное распознавание нормализованных символов. В сб. "Интеллектуальные технологии ввода и обработки информации", 1998, с. 137-157 СТ84] М.Свами, К.Тхуласираман. "Графы, сети и алгоритмы",

4. Eighth Int'l Conf. Pattern Recognition, pp 1251-1255, Paris, 1986 BSY97. Bohnacker, U.; Schacht, J.; Yucel, Т.," Matching form lines basedon a heuristic search", ICDAR'97, IEEE, 1997 DA95. D. Drivas and A. Amin, "Page Segmentation and Classification

5. Flexible Invoice-Like Form-Reader System," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 7, pp. 730-745, July 1998

6. Gor93. L. O'Gorman, "The Document Spectrum for Page Layout

7. Analysis," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, pp. 1,162-1,173, 1993

8. D. Ittner and H. Baird, "Language-Free Layout Analysis," Proc.

9. Second Int'l Conf. Document Analysis and Recognition, pp. 336340,

10. Tsukuba, Japan, 1993 Ish95. Ishitani, "Model matching Based on association graph for formimage understanding," Proc. 3rd Int'l Conf. on Document Analysis and Recognition, pp. 287-292, 1995 KNS+93. M. Krishnamoorthy, G. Nagy, S. Seth, and M. Viswanathan,

11. Syntactic Segmentation and Labeling of Digitized Pages From Technical Journals," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, pp. 743-747, 1993 KYT96. K. Kise, O. Yanagida and S. Takamatsu, "Page Segmentation

12. IEEE International Conference on Image Processing, volume III, pages 328-331, Washington D.C., October 1995 Her92. M. van Herk, "A Fast Algorithm for Local Minimum and

13. Ots79. N.Otsu, "A threshold selection from gray-level histograms", IEEE Trans. Systems, Man, and Cybernetics, Vol SMC-9, No. 1, Jan. 1979, pp. 62-66

14. Pav82. T. Pavlidis, Algorithms for Graphics and Image Processing.

15. Rockville, Md.: Computer Science Press, 1982 (Т. Павлидис, "Алгоритмы машинной графики и обработки изображений", Москва, Радио и связь, 1986)

16. Pav86. Т. Pavlidis, "A vectorizer and feature extractor for documentrecognition " Computer Graphics and Image Processing, Vol 35, pp.111-127, 1986

17. Pun81. T.Pun, "Entropic thresholding: A new approach", Computer

18. Vision, Graphics, and Image Processing, Vol. 16,1981, pp. 210239.

19. TFP92. L. Taylor, R. Fritzson, and 3. A. Pastor, "Extraction of data form preprinted forms:" Machine Vision and Applications, vol. 5, no. 3, pp.211-222, 1992

20. SA96. S. Shimotsuji and M. Asano "Form Identification based on Cell Structure," Proc. of the 1996 Int. Conf. on Pattern Recognition (ICPR96), pp. 793-797,1996

21. TYS94. Y.Y. Tang, C. Yan, and C.Y. Suen, "Document Processing for

22. Automatic Knowledge Acquisition," IEEE Trans. Knowledge and Data Engineering, vol. 6, no. 1, pp. 3-20, 1994.

23. XDO+99. L. Xingyuan, D. Doermann, W. Oh, and W. Gao. "A Robust

24. Method for Unknown Forms Analysis". ICDAR '99, pages 531-534, IEEE, 1999

25. YJ96. B. Yu and A.K. Jain, "A Generic System for Form Dropout," IEEE

26. Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 11, pp. 1,127-1,134, Nov. 1996

27. SBJ96. P. Soille, E. J. Breen, and R. Jones, "Recursive Implementation of Erosions and Dilations Along Discrete Lines at Arbitrary Angles", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, No. 5, May 1996

28. SS95. D. Sylwester and S. Seth, "A Trainable, Single-Pass Algorithm for

29. Column Segmentation," Proc. Third Int'l Conf. Document Analysis and Recognition, pp. 615-618, Montreal, 1995

30. WLS95. Watanabe, Q.Luo, and N. Sugie, "Layout recognition of multikinds of table-form documents," IEEE Trans. PAMI, vol. 17, no. 4, pp.432-443, 1995

31. WR83. J.M.White and G.D. Rohrer, "Image thresholding for opticalcharacter recognition and other applications, requiring character image extraction," IBM J. Research and Development, Vol. 27. No. 4, pp. 400-411, July 1983

32. WWC82. F. Wahl, K. Wong, and R. Casey, «Block segmentation and text extraction in mixed text/image documents,» Computer Graphics and Image processing, Vol. 20, pp. 375 {390, 1982.