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

АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ

УДК 681.3.01

ОКУНЬ ОЛЕГ ГРИГОРЬЕВИЧ

СЕГМЕНТАЦИЯ ИЗОБРАЖЕНИЙ ГРАФИЧЕСКИХ ДОКУМЕНТОВ НА ОСНОВЕ МЕТРИЧЕСКИХ ПРЕОБРАЗОВАНИЙ

05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

МИНСК 1996

Работа выполнена в Институте технической кибернетики Академии наук Беларуси

Научный руководитель: доктор технических наук, профессор

C.B. Абламейко

Официальные оппоненты: доктор технических наук, профессор

Р.Х. Садыхов

кандидат физико-математических наук, доцент

В.В. Краснопрашин

Оппонируишрд организация: Научно-исследовательский институт

электронных вычислительных машин, г. Минск

Зашрта диссертации состоится "1С?" ^ЭЯ 1996 г. в на заседании совета по защите диссертаций Д 01.04.01 при Институте технической кибернетики АН Беларуси (220012, Минск, ул. Сурганова, 6, конференц-зал).

С диссертацией можно ознакомиться в библиотеке Института технической кибернетики АН Беларуси.

Автореферат разослан "^Ь'ДПрСдЯ 1996 г.

Ученый секретарь

совета по защите диссертаций,

доктор технических наук

П.Н. Бибило

ОНДАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Корректность сегментации зависит от таких факторов, как расположение документа при его вводе в ЭВМ, форма текстовых/графических блоков, качество печати документа. Часто требуется выравнивать документ перед его вводом в ЭВМ. Это выравнивание выполняется оператором или механически, что не всегда приводит к желаемому результату. Если выравнивать не сам документ, а его изображение после ввода, то необходимо определить угол наклона, с которьм был введен документ. Точность автоматического определения наклона зависит от значения угла, т.к. многие алгоритмы предназначены только для вычисления неболышх углов (не более ±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).

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

Для достижения поставленной цели необходимо решить следующие основные задачи:

1. Разработать алгоритм разделения текста и графики для документов с блоками произвольной (необязательно прямоугольной) формы.

2. Разработать алгоритм определения угла наклона, с который вводится документ в ЭВМ, менее зависимый от величины угла по сравнению с ранее предложенный методами и применимый как для печатного, так и рукописного текста.

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

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

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

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

Научная новизна полученных результатов. К научной новизне полученных в данной работе результатов относятся:

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

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

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

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

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

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

Практическая значимость полученных результатов. Результаты научных исследований автора диссертации использовались: в системе обработки картографических изображений, созданной в ИТК АНБ по ОКР "Типаж-90" по заказу российской картографической службы; в системе цифрования и редактирования лесоустроительных планшетов для ПО "Белгослес" министерства лесного хозяйства РБ; в учебном процессе в Белорусском Государственном университете; при создании компонент для системы архивации документов в рамках проекта !МТАБ.

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

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

Основные положения диссертации, выносиьые на защиту:

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

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

- модель морфологической кластеризации в 1-мерном пространстве;

- алгоритм сегментации текста с меньшей вычислительной сложностью, чем у алгоритма проекционных профилей;

- быстрый алгоритм кусочно-линейной аппроксимации контуров текстовых символов с большей степенью сжатия информации (2,5-4 раз), чем при использовании кодов Фримена при ошибке аппроксимации не более 1 пикселя;

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

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

Апробация результатов диссертации. Основные положения диссертации докладывались на 1-й Всесоюзной конференции "Распознавание образов и анализ изображений", 14-18 окт., JA-ihck, 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 стр. приложений.

ОСНОВНОЕ СОДЕРЖАНИЕ

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

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

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

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

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

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

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

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

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

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

Графика выделяется, используя свойство площади, по гистограмме площадей связных компонент. Считается, что текст по смыслу относящийся к графике (например, текст графиков зависимостей , подрисуночных подписей и т.п.), следует рассматривать как графику. Это предположение облегчает дальнейшую обработку. Чтобы идентифицировать текст такого вида, всем текстовый компонентам, чьи описывакщие прямоугольники пересекают или расположены внутри прямоугольников графики, первоначально присваивается тип "графика". Для реализации данного шага достаточно проверки следукщего условия:

хгшпО) ^ хтах(д) Ой хтах(1).£ хтт(д) ОЛ (1)

утт(0 ^.утах(д) ОТ утах(0,£ ут!п(д)

Индекс в скобках указывает либо на текст (I) либо на графику (д). Если для параметров текстового прямоугольника данное условие не удовлетворяется, значит соответствующей связной компоненте присваивается тип "графика".

Когда текстовые/графические блоки имеют непрямоугольную форму, или текстовые строки располагаются под ненулевьм углом наклона относительно горизонтали, то после предьщущего шага часть компонент текстовых блоков может быть классифицирована как "графика". Для уточнения корректности классификации применяется свойство компактности текста. Вначале компоненты текстовых блоков, ближайшие к графике, находятся по формуле (1), формируя множество Б. Далее компоненты текстовых блоков, ошибочно помеченные как "графика", итеративно выделяются , используя формулу (1). На каждой итерации множество Б состоит из текстовых компонент, найденных на основании компонент, формировавил« Э на предыдущей итерации. Когда Б пусто, то итерации заканчиваются. Для классификации текстовых компонент, как принадлежащих основному тексту или заголовкам, каждая текстовая компонента представляется центром своего описываюцего прямоугольника. К полученному множеству пикселей применяется алгоритм кластеризации, основанный на метрическом преобразовании. Классификация производится на основании числа пикселей, содержащихся в ка>едом кластере.

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

Известные метода определения угла наклона (проекционные прсф^ли, преобразование Хафа, кросс-корреляция, регрессионный анализ, кластеризация по К-ближайшим соседям) либо позволяют оценить ограниченный диапазон углов (не более ± 15 градусов), либо они примениьы только для печатного текста. В диссертации предлагается алгоритм определения угла наклона как печатного, так и рукописного текста. Кроме того его применение позволяет вычислять углы 25-30 градусов. Как и в алгоритме, базируюцёмся на кластеризации по К-ближайшим соседям, искомой угол определяется по доминирующей ориентации ребер остовного дерева. Однако в качестве вершин дерева вместо центроид связных компонент используются специальные пиксели (метрические маркеры), выделяемые на изображении после выполнения метрического преобразования, что позволяет применять данный алгоритм как для печатного, так и рукописного текста.

Согласно введенному определению пиксель является метрическим маркером, если его значение р удовлетворяет условию (2).

|с|ггах-р|<\«1 (2)

где «/1 - расстояние в заданной метрике от рассматриваемого пикселя до его ближайшего горизонтального/вертикального соседа в пределах 3x3 окрестности, 1), ¡=1,...,8 - значения соседей в 3x3 окрестности, с}тах=Мах { с((!), ¡=1,... ,8 }.

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

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

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

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

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

N0 10 =Мр;

{N01. , если (М-1)/2< V. .

I-« <.-1

(3)

если (М-1 )/2 >,

VI -d/2+dпxld2, d=x2-x1-1, ¡=1,2,...

где Ир - число несовпадающих проекций, число кластеров,

выделяемых на ¡-м интервале метрических значений, nv£ - число появлений значения в гистограмме метрических значений, х1 и х2 (х2>х1) - координаты соседних проекций на ось X (или У).

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

При распознавании текстовые элементы часто представляются своими контурами. Для сжатия информации контуры аппроксимируются . Предлагается быстрый алгоритм кусочно-линейной аппроксимации, сохраняющий существенные особенности формы контура, что имеет одно из главных значений для распознавания текста. Данный алгоритм основан на анализе при отслеживании контура конфигураций из 3-х пикселей, встреча!ацихся при растровом представлении линий. Для каждой конфигурации, учитывая эксперименты с объектами различной формы, определен пиксель, который считается особьм, когда данная конфигурация будет найдена. По сравнению с алгоритмом аппроксимации, использующим коды Фримена, предлагаемый алгоритм имеет большую степень сжатия информации (2,5-4 раза против 1,5-2) при ошибке алпрок симации в 1 пиксель и линейной сложности вычислений по отношению к числу пикселей контура.

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

Метрическое преобразование - это один из распространенна методов восстановления форьы. Стандартный алгоритм, выполняющий данную операцию, состоит в 2-кратном применении метрического преобразования и операции порогового ограничения аначений пикселей. В традиционных, алгоритмах метрическое преобразование выполняется за два сканирования изображения, т.е. каждой анализируемый пиксель обрабатывается дважды ДО получения им финального значения согласно формулам (4) и (5).

Первое сканирование (сверху-вниз, слева-направо):

0(!,3)=М1П { 0(к,т)+а(к-1 ,т-3) \ (к,т)£ N1 (», 3) } (4)

Второе сканирование (снизу-вверх, справа-налево):

й(!,3)=Мт { 0(к,т)+с1(к-! ,т~3) \ (к,т) £ N2* \, 3) } (5)

где с!(к—I,т-]) - расстояние между пикселями (¡,.Л и (к,ш) в заданной метрике, N1<»,3 >= { (¡-1,3-1), (¡-1,3), (¡-1,3+1), (¡,3-1) }, N2(1,3)= { (¡,3+1),(¡+1,3+1>,(¡+1,3).(¡+1,3-1) >•

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

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

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

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

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

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

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

вьводы

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

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

2. Известные алгоритгл.1 определения наклона текстовых строк относительно оси X (например, основанные на преобразовании Хафа, анализе проекционных профилей, кросс-корреляции, кластеризации по К-ближайшим соседям) могут быть либо применены только к печатному тексту, либо с их помощью удается оценить только ограниченный диапазон углов (не более ±15 градусов). Разработан алгоритм, обладаюций меньшей зависимостью от величины угла (допустимые значения - ± 25-30 градусов) и применимый как для печатного, так и рукописного текста. Это достигается, используя специальные пиксели (маркеры), определяемые с помощью метрического преобразования.

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

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

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

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

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

СПИСОК ОПУБЛИКОВАНИЕ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Окунь О.Г., Берейшик В.И. Быстрая полигональная аппроксимация контуров и скелетов бинарных изображений в процессе сканирования // Тезисы докл. Методы и средства обработки сложной графической информации.- Н.Новгород, 1991С.62.

2. Берейшик В.И., Хоменко М.И., Окунь О.Г. Быделение, быстрая кусочно-линейная аппроксимация и сохранение информации о вложенности контуров связных компонент бинарных изображений в процессе их построчной обработки // Тезисы докл. Распознавание образов и анализ изображений.- Минск, 1991,- С.19-23.

3. Система автоматического ввода, обработки и преобразования в векторный формат изображений графических документов / С.В.Абламейко, В.И.Берейшик, А.И.Гренов.. О. Г. Окунь, Н. И .Парамонова, О.А.Пацко. О.В.Францкевич, М.И.Хоменко // Тезисы докл. Распознавание образов и анализ изображений. - Минск, 1391. - C.8-S.

4. Raster-to-vector transform of large-sized 2D line drawings /S.Ablarneyko, V.Bereishik, O.Frantskevich, M.Homenko, O.Okun, N.Paramonova // Разработка высокопроизводительных параллельных архитектур. - Минск: Ин-т техн. кибернетики АНБ, 1992.-С.71-85.

5. A system for automatic vectorization and interpretation of map-drawing / S.Abiameyko, V.Bereishik, O.Frantskevich. M.Ho-

menko, E.Melnik, N.Paramonova, O.Patsko, O.Okun // Proc. 4th Int. Conf. on Computer Vision.-Berlin, Germany, 1993.- P.456-460.

6. A system for automatic vectorization and interpretation of graphic images /' S.Ablameyko, V. Bereishik, O. Frantskevich, M.Homenko, E.Melnik, O.Okun, N.Paramonova // Pattern Recognition and Image Analysis.- 1993.- Vol.3, N1.- P.39-52.

7. Ablameyko S., Okun O. Text separation from graphics based on compactness and area properties // Machine Graphics and Vision Int. Journal.- 1994,- Vol.3, N3,- P.531-542.

8. Okun O., Ablameyko S. Text/graphics separation without constraints on document skew and block shape // Автоматизация обработки и распознавания изображений. - Шнек: Ин-т техн. кибернетики АНБ, 1995,- С.155-160.

S. Okun О., Ablameyko S. Text/graphics separation for technical papers // SPIE Proc. on Document Recognition II,-Vol. 2422.- San Jose, California, USA, 1995.- P.175-182.

10. Okun O. A conmon approach to handwritten and printed text segmentation // Автоматизация обработки и распознавания изображений.- Минск: Ин-т техн. кибернетики АНБ, 1995.-С.161-104.

11. Okun О., Ablameyko S. Towards the uniform approach for handwritten and printed text segmentation //Proc. 9th Scandinavian Conf. on Image Analysis.- Uppsala, Sweden, 1995.-P.1107-1113.

Р Э 3 Ю M Е дысертацыйнай працы Окуня Алега Рыгорав1ча "Сегментация адлюстравання? граф1чных дакументау на аснове метрычных пераутварэнняу

Ключавыя словы: апрацоука адлюстраванняу, метрычныя пераутва-рэннi, аддзяленне граф1к! ад тэксту, сегментацыя тексту, ад-науленне формы тэкставых Ымвапау.

Аб'ект даследаванняу у гэтай працы - бшарныя адлюст-раванн! , змяшчаючзю тэкст на еурапейскай мове i графику i ме~ тады ix сегментацьн. Мэта працы - распрацаваць эфектыуныя ал-гарьп-№1 сегментацьн так ix адлюстраванняу. Эфектыунасць азна-чае незалежнасць карэктнасф сегментацьн ад упльву так ix фак-тарау, як распалажэнне дакумента пры яго уводзе у ЭВМ, форма тэкставых/графшных блокау, якасць друку дакумента. У якасц! базавага метаду даследаванняу выбраны метрычныя пераутварэнн i. Атрьманы наступныя вын i к i : распрацаваны алгарытм сегментацьн на тэкст i граф!ку, як i адрозтваецца ад вядомых тьм, што ка-рзктнасць сегментацы! у гзтьм выпадку не залежыць ад формы тэкставых/граф1чных блокау (форма можа быть адвольнай, а не толью прамавугольнай); распрацаваны алгарытм вызначэння вуг-ла сх1лу тэкставых строк, hk¡ дазваляе вызначыць больш нырок¡ дыяпазон вуглоу (25-30 градусау) у параунант з ¡ниьм! алга-рытмам1 (10-15 градусау) i як! можа быць выкарыстованы як да друкаванага, так i да pyKanicHara тэксту; прапанаваны алгарытм сегментацьн тэксту, маючы мениыя патрабаванн! да памяц1 ЭВМ i вьш)чальную складанасць, чьи алгарытм праекцыенных про-фтяу; з мэтай атрьмання кампактнага прадстаулення тэкставых Ымвалау пры захоуванж галоуных зсабл!васцей формы с!мвалау распрацаваны xyTKi алгарытм кусочна-лшейнай апракЫмацьи кан-туроу, як i прыводзщь да большай ступет' змяншэння ¡нфарма-цьн (2,5-4 разы) у параунанш з алгарытмам, як i выкарыстуе коды Фрьмена (1,5-2 разы) пры па»/ылке апракс'шацьн у 1 niK-сель; прапанаваны алгарытм адна^лення формы тэкставых Ымва-лау, заснаваны на мадьф! цыраваньм метрычныи пераутварэннi, як i паскарае выкананне гэтай аперацьн у 1,3-1,4 разы у па-

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

РЕЗЮМЕ

диссертационной работы Окуня Олега Григорьевича

"Сегментация изображений графических документов на основе метрических преобразований"

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

Объект исследований в данной работе - бинарные изображения, содержащие текст на европейском языке и графику, методы их сегментации. Цель работы - разработать эффективные алгоритма сегментации таких изображений. Эффективность означает независимость корректности сегментации от влияния таких факторов, как расположение документа при его вводе в ЭВМ, форма текстовых/графических блоков, качество печати документа. В качестве базового метода исследований выбраны метрические преобразования. Получены следующие результаты: разработан алгоритм сегментации на текст и графику, отличающийся от известных тем, что корректность сегментации в данном случае не зависит от формы текстовых/графических блоков (форма может быть произвольной, а не только прямоугольной); разработан алгоритм определения ^гла наклона текстовых строк, позволяющий определить более широкий диапазон углов (25-30 градусов) по сравнению с другими алгоритмами (10-15 градусов) и применимый как к печатному, так и рукописному тексту; предложен алгоритм сегментации текста, имеюций на порядок меньшие требования к памяти ЭВМ и вычислительную сложность, чем алгоритм проекционных профилей; с целью получения компактного представления текстовых символов при сохранении существенных особенностей формы символов разработан быстрый алгоритм кусочно-линейной

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

SUMMARY of the thesis "Graphic document image segmentation by distance transforms'' by Oleg Grigorievich Okun

Key words: image processing, distance transforms, text/graphics separation, text segmentation, text symbol shape recon-st ruct ion.

Binary images containing the graphics and European text and methods of their segmentation are investigated in this work. Purpose of research is to develop the efficient segmentation algorithms of such images. Efficiency means thai segmeritation correctness does not depend on document location during its input to computer, text/graphic block shape, document print quality. Main method of research is distance transforms. The following results are obtained: text/graphics separation algorithm resulting in correct separation even if a text/graphic block shape is arbitrary (not only rectangular) is developed; text skew detection a Igorithm a Ilowi rig to determine a larger skew angle range (25-30 degrees) than other methods (10-15 degrees) do and is applicable for both printed and handwritten text is developed; text segmentation algorithm having the lesser computetionaI complexity and memory requirements than projection profile one is proposed; fast

contour polygonal approximation algorithm to obtain a compressed representation of text symbols by saving the important peculiarities of symbol shape.is developed. Compression rate is 2.5-4 as compared to the algorithm based on Freeman's codes (1.5-2), while approximation error is. 1 pixel; text symbol shape reconstruction aIgorithm based on modified distance transform speeding up a processing by a factor of 1.31.4 as compared to standard distance transform (while reconstruction quality is the same in both cases is proposed. The developed algorithms may be used to create the electronic document archives, digitize and edit the maps and the line-drawings.