Введение к работе
Актуальность темы диссертации. Информация является важный источником получения знаний, накопленных в прошлом и настоящем, а также в значительной мере может определять прогресс той или иной отрасли науки и техники в будущем. Однако, несмотря на быстрые темпы компьютеризации, бумага все еще остается основным носителем информации.
Для целей быстрого поиска и обновления информации необходимо преобразовывать информацию из бумажного в электронное представление. Такое преобразование выполняют системы автоматизированного анализа документов. Типичный документ содержит текстовые и графические данные. Поэтому составной частью любой системы анализа документов является сегментация изображения документа на логические части, такие как параграфы, текстовые строки, буквы, фотографии, рисунки и т.д. Однако многие системы имеют следующие недостатки, связанные с сегментацией.
Корректность сегментации зависит от таких факторов, как расположение документа при его вводе в ЭВМ, форма текстовых/графических блоков, качество печати документа. Часто требуется выравнивать документ перед его вводом в ЭВМ. Это выравнивание выполняется оператором или механически, что не всегда приводит к желаемому результату. Если выравнивать не сам документ, а его изображение после ввода, то необходимо определить угол наклона, с которым был введен документ. Точность автоматического определения наклона зависит от значения угла, т.к. многие алгоритмы предназначены только для вычисления небольших углов (не более ±15 градусов). Трудности при сегментации вызывает и нестандартная форма текстовых/графических блоков. Обычно блоки являются прямоугольным по форме, т. е. описьвакщие прямоугольники связных компонент, принадлежащих к разньм блокам, не пересекаются. В противном случае часть текстовьк компонент может быть классифицирована как графика. На степень корректности сегментации влияет и качество печати документа. Например, разрывы букв на несколько частей (это часто имеет место для факсов и копий документа п-го
порядка) значительно снижают точность сегментации.
Актуальность данной диссертационной работы заключается в устранении перечисленных выше недостатков с целью улучшения характеристик системы автоматизированного анализа документов, что в конечном итоге уменьшит материальные и временные затраты, связанные с процессом преобразования информации из бумажного в электронное представление.
Такая система может быть использована при архивации документов, создании электронных моделей чертежей, схем и карт, в издательском производстве.
Связь работы с крупными научными программами, темами. Диссертационная работа выполнена в рамках следующих научно-исследовательских работ и проектов:
"Разработка теоретических основ обработки и распознавания графических изображений САПР" (Тема "Машиностроение 2.27", гос. per. N 01.9.1001443), 1991-93 гг.;
"Разработка принципов построения, технологии, методов и программного обеспечения системы обработки и распознавания цифровых изображений" (задание 03.01.03.01, подпрограм-. ма "Интерфейс человек-машина", программа "Информатика", per. N 01.8.90042399), 1992-94 гг.;
"Разработка единого подхода к обработке цифровых изображений на основе математической морфологии и дистанционных преобразований" (проект ЫФ28-092 Фонда Фундаментальных исследований РБ), 1994-96 гг.;
"Разработка методов распознавания и представления изображений в интеллектуальных системах" (Тема "Информационные технологии-30", гос.per. N 19941856), 1994-95 гг.
Исследования, выполненные в диссертации, поддержаны грантами N36a/95 Международной Соросовской программы образования в области точных наук (ISSEP) и N 94-0459 Международной Ассоциации по сотрудничеству с учеными из СНГ (INTAS).
Цель и задачи исследования. Цель состоит в разработке эффективных (в плане независимости результатов сегментации от таких факторов, как форма блоков, ориентация и качество печати документа при его вводе в ЭВМ) алгоритмов и программных средств для сегментации изображений графических документов.
Для достижения поставленной цели необходимо решить следуюцие основные задачи:
-
Разработать алгоритм разделения текста и графики для документов с блоками произвольной (необязательно прямоугольной) формы.
-
Разработать алгоритм определения угла наклона, с который вводится документ в ЭВМ, менее зависимый от величины угла по сравнению с ранее предложенными методами и применимый как для печатного, так и рукописного текста.
-
Разработать алгоритм сегментации текста с меньшей вычислительной сложностью и более низкими требованиями к памяти ЭВМ, чем у алгоритма проекционных профилей.
-
Разработать быстрый алгоритм неэвклидова метрического преобразования для решения задачи реконструкции (восстановления) формы алфавитно-цифровых символов.
-
Разработать быстрый алгоритм кусочно-линейной аппроксимации контуров объектов бинарных изображений.
Методы исследований. Исследования, проводимые в работе, базируются на методах метрических преобразований, кластеризации образов, математической морфологии, теории графов.
Научная новизна полученных результатов. К научной новизне полученных в данной работе результатов относятся:
алгоритм отделения графики от текста, отличающийся от известных тем, что корректность результата отделения в данном случае не зависит от формы текстовых/графических блоков (форма может быть произвольной, а не только прямоугольной) .
алгоритм определения угла наклона текстовых строк, применимый как к печатному, так и рукописному тексту и позволяющий в 2 раза увеличить диапазон оцениваемых углов по сравнению с другими подобными методами.
модель морфологической кластеризации в 1-мерном пространстве, на основе которой предложена модификация алгоритма сегментации текста по проекционньм профилям, имекщая по сравнению со стандартньм алгоритмом на порядок меньшие требования к памяти ЭВМ и вычислительную сложность.
алгоритм реконструкции формы текстовых символов, базирукщийся на модифицированном метрическом преобразовании и
ускоряющий выполнение данной операции в 1,3-1,4 раза по сравнению с использованием стандартного преобразования при одном и том же качестве восстановления.
- быстрый алгоритм кусочно-линейной аппроксимации,
минимизирующий ошибку аппроксимации (не более 1 пикселя) и
приводящий к большему коэффициенту сжатия данных (2,5-4 раза)
по сравнению с аппроксимацией кодами Фримена (1,5-2 раза).
Практическая значимость полученных результатов. Результаты научных исследований автора диссертации использовались: в системе обработки картографических изображений, созданной в ИТК АНБ по ОКР "Типаж-90" по заказу российской картографической службы; в системе цифрования и редактирования лесоустроительных планшетов для ПО "Белгослес" министерства лесного хозяйства РБ; в учебном процессе в Белорусском Государственном университете; при создании компонент для системы архивации документов в рамках проекта і NTAS.
Разработанные алгоритмы могут быть использованы при создании систем автоматизированного анализа документов для решения таких задач, как автоматическое определение угла наклона текстовых строк, отделение текста от графики, сегментация печатного и рукописного текста, реконструкция формы букв и цифр при плохом качестве печати исходного документа, кусочно-линейная аппроксимация двумерных кривых.
Экономическая значимость полученных результатов. Разработанные алгоритмы при дополнительной доработке, зависящей от конкретного приложения, могут быть использованы в системах ввода и автоматической обработки текстовой и графической информации. Такие системы могут найти применение при создании электронных архивов документов, обработке бланков и анкет, генерации цифровых моделей карт и чертежей.
Основные положения диссертации, выносимые на защиту:
алгоритм сегментации на текст и графику для изображений документов с текстовьми/графическими блоками произвольной, а не только прямоугольной формы;
алгоритм определения угла наклона текстовых строк, более робастный к величине измеряемого угла, чем другие подобные методы и применимый как к печатному, так и к рукописному тексту;
модель морфологической кластеризации в 1-мерном пространстве;
алгоритм сегментации текста с меньшей вычислительной сложностью, чем у алгоритма проекционных профилей;
быстрый алгоритм кусочно-линейной аппроксимации контуров текстовых символов с большей степенью сжатия информации (2,5-4 раз), чем при использовании кодов Фримена при ошибке аппроксимации не более 1 пикселя;
модифицированный алгоритм метрического преобразования, ускоряюций выполнение данного преобразования и операции реконструкции формы текстовых символов и приводящий к такому же качеству восстановления, как при использовании алгоритма стандартного метрического преобразования.
Личный вклад соискателя. В работе лично автором предложены алгоритмы сегментации изображений документов, определения пространственньк соотношений между текстом и графикой и метрических маркеров, доказана теорема о метрических маркерах, и получены основные результаты.
Апробация результатов диссертации. Основные положения диссертации докладывались на 1-й Всесоюзной конференции "Распознавание образов и анализ изображений", 14-18 окт., Мінск, 1991; 4-й Всесоюзной конференции "Методы и средства обработки сложной графической информации", Н. Новгород, 1991; 4th Int. Conf. on Computer Vision, Berlin, Germany, 1993; Conf. on Document Recognition II, San Jose, USA, 1995; 9th Scandinavian Conf. on Image Analysis, Uppsala, Sweden, 1995.
Опубликованность результатов. По теме диссертации опубликовано 11 научных работ, в том числе:
2 статьи в международных журналах;
3 статьи в трудах международных конференций;
3 статьи в сборниках трудов ИТК АНБ;
- 3 тезиса докладов на Всесоюзных и СНГ конференциях;
Структура и объем диссертации. Диссертация состоит из
введения, общей характеристики работы, 4-х глав, выводов, списка литературы и приложений. Работа содержит 74 стр. печатного текста, 30 иллюстраций, 3 таблицы, список используемых источников на 11 стр. (130 наименований) и 38 стр. приложений.
