Министерство образования и науки украины международный научно-учебный центр информационных технологий и систем савчинский богдан дмитриевич удк 004.93'1:[519.76+519.814+519.168+519.857] контекстно-сво

Национальная академия наук Украины Министерство образования и науки Украины Международный научно-учебный центр информационных технологий и систем Савчинский Богдан Дмитриевич УДК 004.93'1:[519.76+519.814+519.168+519.857] КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИЧЕСКИЕ КОНСТРУКЦИИ ДЛЯ РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ ТЕКСТОВЫХ И ГРАФИЧЕСКИХ ДОКУМЕНТОВ 05.13.23 – системы и средства искусственного интеллекта Автореферат диссертации на соискание учёной степени кандидата технических наук Киев - 2007 Диссертацией является рукопись.

Работа выполнена в Международном научно-учебном центре информационных технологий и систем НАН Украины и МОН Украины в отделе обработки и распознавания изображений.

Научный Доктор физико-математических наук, профессор руководитель: Шлезингер Михаил Иванович, Международный научно-учебный центр информационных технологий и систем, главный научный сотрудник.

Официальные Доктор физико-математических наук, профессор оппоненты: Кириченко Николай Федорович, Институт кибернетики им. Глушкова НАН Украины, ведущий научный сотрудник.

Кандидат технических наук Калмыков Владимир Григорьевич, Институт проблем математических машин и систем НАН Украины, старший научный сотрудник.

Ведущая Национальный технический университет Украины организация: „Киевский политехнический институт” Защита состоится "7" июня 2007 года в 12 часов на заседании специализированного ученого совета Д 26.171.01 в Международном научно-учебном центре информационных технологий и систем НАН и МОН Украины по адресу:

03680, Киев, просп. акад. Глушкова, 40.

С диссертацией можно ознакомиться в библиотеке Международного научно-учебного центра информационных технологий и систем НАН Украины и МОН Украины: 03680, Киев, просп. акад. Глушкова, 40.

Автореферат разослан "4" мая 2007 г.

Ученый секретарь ТАРАСОВ В. А.

специализированного ученого совета ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Работа посвящена распознаванию семантически насыщенных изображений с иерархической структурой, которыми, как правило, являются изображения графических документов. Такие изображения состоят из большого количества взаимозависимых частей. Сложность их распознавания заключается в том, что имена отдельных частей не определяются однозначно изображениями этих частей.

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

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

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

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

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

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

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

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

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

Решение указанных актуальных вопросов заключается в:

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

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

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

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

Результаты работы являются составной частью:

• научно-исследовательской работы «Исследование контекстно-свободных формальных конструкций и иерархических моделей изображений» по заказу Национальной Академии наук Украины, 2004-2006 гг. ( № госрегистрации 0104U000952), которая выполнялась в соответствии с планами научных исследований отдела № 120 «Распознавание изображений» Международного научно-учебного центра информационных технологий и систем;

• работ по международному научно-исследовательскому проекту «Принципы распознавания образов в сигналах, последовательностях символов и изображениях на основе отличий (Principles of Dissimilarity-based Pattern Recognition in Signals, Symbolic Sequences and Images (acronym PRINCESS)) INTAS Ref. Nr 04-77-7347» по заказу европейской грантовой организации INTAS.

Лично автором были разработаны:

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

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

• архитектура программного комплекса для распознавания изображений по заданной грамматике (структурной конструкции);

• постановка и решение задачи настройки (обучения) для произвольной общей структурной конструкции;

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

• постановка и решение ряда нетрадиционных байесовских задач распознавания текстовых изображений.

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

Заданиями работы являются:

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

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

провести экспериментальную проверку полученных алгоритмов;

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

в пределах данной работы выполнить это задание на примере распознавания текстовых изображений;

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

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

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

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

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

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

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

Конструкции этого подкласа могут пониматься как двумерное обобщение регулярных грамматик.

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

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

Практическое значение полученных результатов. Результаты работы внедрены в Государственной научно-технической программе «Образный компьютер» при разработке систем распознавания чертежно-графических изображений и Центре машинного виденья Чешского технического университета (Прага) при распознавании изображений математических формул и использовались при выполнении таких контрактов:

• «Аппаратно-программный комплекс для автоматической обработки чертежно-графических и текстовых изображений» в рамках Государственной научно-технической программы «Образный компьютер», 2001 г.

(№ госрегистрации 01U007950);

• «Разработка интеллектуальных средств понимания изображений и создания на их основе опытных образцов подсистем ОК и приборов» в рамках Государственной научно-технической программы «Образный компьютер», 2002 г. (№ госрегистрации 0102U006897);

• «Разработать базовую интеллектуальную технологию восприятия, распознавания и понимания изображений и создать на этой основе прикладные технологии распознавания и образцы наукоемких изделий» в рамках Государственной научно-технической программы «Образный компьютер», 2003 г. (№ госрегистрации 0103U005769);

• «Разработать интеллектуальные технологии «Вижу и понимаю, что вижу» и изготовить экспериментальные образцы устройств, которые их реализуют» в рамках Государственной научно-технической программы «Образный компьютер», 2004 г. (№ госрегистрации 0104U008471).

Личный вклад диссертанта. Научные результаты, представленные в диссертации и статьях, получены автором самостоятельно. В статьях, написанных вместе с соавторами, вклад диссертанта является таким:

• в статье [1] диссертанту принадлежит формулировка модели линейных грамматик с фиксированными размерами нетерминалов, анализ эффективности соответствующего алгоритма распознавания и идея применения этой модели к распознаванию печатных нотных текстов;

• в статье [3] диссертанту принадлежит постановка и алгоритм решения задачи настройки эталонов букв текста;

• в статье [4] диссертанту принадлежит модель двумерной контекстно свободной грамматики с перекрытием сегментов и соответствующий алгоритм синтаксического анализа изображений.

Экспериментальные исследования выполнены с помощью программного обеспечения, реализованного автором вместе с соавторами статей Анохиной Г. А., Камоцким А. В. и Павлюк Е. В.

Апробация результатов диссертации. Результаты диссертации обнародованы на таких конференциях: Международная конференция «Document Image Analysis for Libraries (DIAL’06)», Лион, Франция;

Автоматика - 2004: 11-я международная конференция по автоматическому управлению;

Международная конференция «Электронные изображения и визуальные искусства» EVA Киев;

Результаты работы неоднократно докладывались на семинаре Государственной научно-технической программы «Образный компьютер», на семинарах в Институте искусственного интеллекта Дрезденского технического университета, Центре машинного видения Чешского технического университета, Институте космических исследований НАНУ и в отделе распознавания изображений Международного научно-учебного центра информационных технологий и систем.

Публикации. Материалы диссертации обнародованы в 8 научных публикациях. Среди них 4, одна из которых без соавторов, опубликованы в профильных журналах, утвержденных ВАК Украины, 2 доклада и 2 тезиса – в сборниках трудов конференций, в том числе международной конференции «Document Image Analysis for Libraries (DIAL’06)», Лион, Франция.

Структура диссертации. Диссертация состоит из вступления, 4 глав, выводов, списка использованных источников (9 страниц, 75 наименований) и дополнения. Работа содержит 28 рисунков. Общий объем диссертации 130 страниц.

Полный объем диссертации (включая список использованных источников, рисунки и дополнение) составляет 155 страниц.

СОДЕРЖАНИЕ РАБОТЫ Первая глава «Анализ современного состояния и выбор направлений исследований» состоит из трех подразделов, посвященных соответственно трем следующим главам диссертации.

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

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

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

Пусть T = {(i, j ) | 1 i H, 1 j W } – поле зрения, H и W его высота и ширина соответственно. Фрагментом поля зрения будем называть его прямоугольное подмножество вида g (ib, it, jl, jr ) = {(i, j ) | ib i it, jl j jr }.

Размером фрагмента g будем называть количество | g | элементов, которые входят в его состав. Пусть также t0 ( g ) = (ib ( g ), jl ( g )). Множесто всех возможных фрагментов будем обозначать = {g (it, ib, jl, jr ) | 1 ib it H, 1 jl jr W }. В частности T.

Пусть X – конечное множество сигналов. Функцию вида x : T X будем называть изображением. Множество X T всех возможных изображений будем обозначать X. Фрагментом x ( g ) изображения x будем называть сужение функции x на множество g T. Таким образом x ( g ) : g X.

Пусть V - конечное множество имен. Одно из имен V будем называть аксиомой. Определенное подмножество VZ V будем называть множеством терминальных имен. Поименованный фрагмент ( g, v ) V будем называть сегментом. Множество V всех сегментов будем обозначать S. Имя v и фрагмент g сегмента ( g, v ) обозначим соответственно v ( s ) и g ( s ). Множество Z VZ сегментов с терминальными именами будем называть множеством терминальных сегментов. Сегмент (T, ) назовем аксиомным и обозначим s.

Пусть P : S 3 {0, 1} – предикат, который определяет множество правил вывода.

Будем считать, что если P( s, s, s) = 1, то: (1) g ( s) g ( s ) и g ( s) g ( s ), (2) g ( s) g ( s). Количество элементов в множестве {( s, s, s) S 3 | P ( s, s, s) = 1} будем называть количеством правил вывода и обозначим | P |. Введем также предикат P : Z X {0, 1}, который определяет множество правил именования.

Контекстно-свободной конструкцией будем называть пятерку G = V, Z,, P, P.

Выводом сегмента s S в конструкции G при условии изображения x будем называть такое подмножество S = S G ( s, x ) S сегментов, для которого выполняются следующие четыре условия: (1) s S, (2) s = argmax sS | g ( s) |, (3) для всех s S Z существует единственная пара s, s S, что P( s, s, s) = 1, (4) для всех s S Z, P( s, x ( g ( s))) = 1. Множество всех выводов сегмента s при условии изображения x обозначим S ( s, x ), а множество S Z обозначим Z ( S ).

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

Алгоритм решения этой задачи заключается в последовательном построении списка L сегментов, упорядоченного по их размерам. Для s, s S обозначим S P ( s, s) = {s S | P ( s, s, s) = 1}.

Алгоритм 1. Распознавание в контекстно-свободных конструкциях.

1. Внести в список L все такие сегменты s Z, что P ( s, x ( g ( s ))) = 1.

2. Двигаться списком от меньших сегментов к большим. На каждом шаге для текущего сегмента s L выполнить действия шага 3. Если обработаны все сегменты из L, то конец.

3. Вставить в такое множество сегментов L {s | s S P ( s, s) {L}, s L,| g ( s) || g ( s) |}.

Изображение x выводится в данной грамматике т. и т. т., когда s L.

Временная и пространственная сложность алгоритма может варьироваться в зависимости от специфики правил грамматики и множества сегментов S. В общем случае его временная сложность составляет O (| P |), а пространственная O (| S |).

Пусть Ph0 : 3 {0, 1} и Pv0 : 3 {0, 1} – предикаты, определяющие горизонтальную и вертикальную конкатенацию фрагментов, то есть для произвольных g, g, g, g = (ib, it, jl, jr ), g = (i b, i t, j l, j r ), g = (i b, i t, j l, j r ), они равны соответственно Ph0 (g,g,g )= ((it = i t = i t ) &(ib = i b = i b ) &(jl = j l ) &( j r +1= jl ) &(jr = j''r )) и Pv0 ( g, g, g ) = ((it = i t ) & (i b = i t + 1) & ( jl = j l = j l ) & ( jr = j r = j r ) & (ib = i ''b )).

Известные двумерные контекстно-свободные грамматики являются таким частным случаем описанной конструкции, когда Ph : V 3 {0, 1}, Pv : V 3 {0, 1}, что 1.

P(( g, v ), ( g, v ), ( g, v )) = [ Ph0 ( g, g, g ) & Ph ( v, v, v )] [ Pv0 ( g, g, g ) & Pv ( v, v, v )] ;

Предикат P может принимать ненулевые значения лишь на фрагментах 2.

размером в один пиксел: если jr ( g ( s )) jl ( g ( s )) 1 или it ( g ( s )) ib ( g ( s )) 1, то P( s, x ( g ( s ))) = 0.

Можно показать, что временная сложность алгоритма 1 в случае двумерных контекстно-свободных грамматик равна O ( H 2W 2 ( H + W )), а пространственная – O ( H 2W 2 ).

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

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

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

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

В подразделе «Базовая структурная конструкция» описан разработанный формализм, лишенный указанных недостатков. Пусть q : X X R – функция, значение q( x, y ) которой определяет разницу между сигналами x и y. Анализ прикладных задач со статистической точки зрения указывает, что разница Q ( x, y ) x X y X между парой изображений определяется как и Q ( x, y ) = tT q( x (t ), y (t )). Задача распознавания изображения, которую также будем называть задачей на наилучшее соответствие, при этом заключается в отыскании y = arg min Q ( x, y ). (1) yL ( G ) Задача, эквивалентная (1), могла бы быть поставлена на основе аппарата двумерных контекстно-свободных конструкций таким образом: S S ( s, x ) 1. s, s S, s s выполняется единственная из трех альтернатив:

(1) g ( s ) g ( s) = ;

(2) g ( s ) g ( s) ;

(3) g ( s) g ( s ) ;

2. t T s Z ( S ) : t g ( s) ;

3. каждому терминальному имени v Vz поставлено в соответствие эталонное изображение ev : T X ;

4. P( s, x ( g ( s ))) = tg ( s ) q( x (t ), ev ( s ) (t t0 ( g ( s )))), s Z.

Задача распознавания, эквивалентная (1), заключается в вычислении S = arg min q( x (t ), ev ( s ) (t t0 ( g ( s )))).

S S ( s, x ) sZ ( S ) tg ( s ) Однако, как уже отмечалось, условия 1 и 2 сильно сужают область прикладного использования приведенной схемы. Для их ослабления воспользуемся тем, что на черно-белых изображениях документов как правило выделяется один из цветов x X – фон, которым заполняются промежутки между значимыми частями изображения. Для прикладного использования более удобным, чем условия 1 и 2, является условие:

s, s Z ( S )[t g ( s ) g ( s) ( ev ( s ) (t t0 ( g ( s ))) = x ) ( ev ( s) (t t0 ( g ( s))) = x )]. (2) S S ( s, x ) Выполнение для равенства q( x (t ), ev ( s ) (t t0 ( g ( s )))) = tT q( x (t ), y (t )) при этом требует, чтобы sZ ( S ) tg ( s ) q( x, x ) = 0x X. Потому вместо функции q будем использовать функцию q( x, y ) = q( x, y ) q( x, x ). Решение задачи (1) от этого не изменится, поскольку y = arg ymin) q( x (t ), y (t )) = arg ymin) [ q( x (t ), y (t )) q( x (t ), x )] = L ( G L ( G tT tT q( x(t ), y (t )) q( x(t ), x )] = arg min q( x(t ), y (t )).

= arg[ min yL ( G ) yL ( G ) tT tT tT В результате выполнения (2) ослабляются также условия на правила вывода P. Если в известных контекстно-свободных конструкциях допустимой является лишь горизонтальная и вертикальная конкатенация сегментов, то в введенной базовой структурной конструкции ограничение заключается лишь в том, что если P( s, s, s) = 1, то g ( s ) является наименьшим фрагментом, который содержит фрагменты g ( s) и g ( s) как свои подмножества.

Для решения задачи распознавания, заключающейся в вычислении S = arg min q( x (t ), ev ( s ) (t t0 ( g ( s )))), (3) S S ( s, x ) sZ ( S ) tg ( s ) может быть использован алгоритм 2.

Алгоритм 2. Решение задачи (3) в контекстно-свободных конструкциях.

Внести в список L все s Z. Для каждого из них вычислить и сохранить 1.

величину f ( s ) = P( s, x ( g ( s ))).

Двигаться списком от меньших сегментов к большим. На каждом шаге для 2.

текущего сегмента s L выполнить действия шага 3. Если обработаны все сегменты из L, то конец.

s S 0 ( s) = {s S P ( s, s) | s L,| g ( s) || g ( s) |} Для всех вычислить 3.

f 0 ( s ) = min s:sSP ( s,s) [ f ( s) + f ( s)] ;

вставить все s S 0 ( s) {L} в L и положить для них f ( s ) = f 0 ( s ) ;

для s S 0 ( s) {L} положить f ( s ) = min{ f 0 ( s ), f ( s )}.

Изображение x выводится в данной грамматике т. и т. т., когда s L.

Качество наилучшего вывода равно f ( s ).

Алгоритм 2, как и алгоритм 1, имеет временную сложность O (| P |) в наихудшем случае. Эта величина может быть как чрезвычайно большой ( O (| P |) = O ( S 3 ) = O ( H 6W 6 ) ), так и сравнительно малой в зависимости от конкретного предиката P.

В диссертации определен линейный по сложности ( O (| P |) = O (| T |) ) подклас конструкций, которые могут считаться двумерными обобщениями классических регулярных грамматик Хомского. Кроме этого, в диссертации приведена схема декомпозиции алгоритма синтаксического анализа, которая позволяет использовать для вывода отдельных сегментов алгоритмы, более эффективные, чем общий алгоритм 2. Эта же схема используется и для снижения расходов памяти алгоритма 2. Указанная схема будет рассмотрена сразу после еще одного замечания относительно сложности алгоритма 2.

А именно, его реальная сложность зависит от количества терминальных сегментов, внесенных в список L в начале работы алгоритма. Поэтому эффективным способом уменьшения сложности является уменьшение этого количества путем удаления тех сегментов, вхождение которых в оптимальный вывод является маловероятным. Для определения этой «вероятности» могут использоваться любые посторонние, не связанные с контекстно-свободными конструкциями процедуры распознавания, имеющие вид h : Z X {0, 1}. Тогда на первой стадии алгоритма 2 вместо внесения в список L всех сегментов s Z вносятся лишь те сегменты, для которых h( s ) = 1. Это обеспечивает уменьшение количества и других сегментов, которые образуются в ходе работы алгоритма на шагах 2 и 3.

В подразделе «Контексто-свободная конструкция с выделенными сегментами. Минимизация памяти, необходимой для синтаксического анализа» приведена схема декомпозиции алгоритма синтаксического анализа, позволяющая использовать для вывода отдельных сегментов алгоритмы, более эффективные, чем общий алгоритм 2. Пусть S S множество выделенных сегментов и s S. Будем строить алгоритм распознавания таким образом, что для каждого сегмента s S из этого множества обязательно будет подсчитываться качество f ( s ) его наилучшего вывода. Приведем этот алгоритм и укажем его преимущества перед алгоритмом 2. Для его формулировки определим ориентированный граф Gr = Vr, Ed с множеством вершин Vr и множеством Vr = S Z.

ребер Ed. Положим Множество ребер Ed определим так: ( s, s) Vr 2 ( s, s) Ed, если ( s1, s2,…, sn ) S n :

(s '1 S : P ( s, s1, s1) = 1) & (s2 S : P ( s1, s2, s2 ) = 1) &…& (sn S : P( sn, s, sn ) = 1).

Нетрудно видеть, что граф Gr задает частичный порядок на множестве Vr = S Z. Для выполнения алгоритма 3 этот порядок следует дополнить до полного, то есть ввести взаимнооднозначное отображение: ind : Vr {1, 2,…,| Vr |} такое, что из ( s, s) Ed следует ind ( s ) ind ( s). Обозначим при помощи Vr ( s ), s Vr множество {s Vr | ( s, s) Ed }, а при помощи P( A) – сужение P на множество A S.

Алгоритм 3. Распознавание в контекстно-свободных конструкциях с выделенными сегментами.

Положить i = 1 и вычислить s = ind 1 (i ).

1.

Если s Z, положить f ( s ) = P( s, x ( g ( s ))), иначе вычислить f ( s ) с помощью 2.

алгоритма 2 в грамматике V,Vr ( s ), s, P, P( Z (Vr ( s ))).

Если вычислено f ( s ), то конец. Иначе положить i = i + 1, s = ind 1 (i ) и 3.

перейти на шаг 2.

Комментарий: Качество наилучшего вывода равно f ( s ).

Алгоритм 3 имеет такие свойства:

• алгоритм разбивает синтаксический анализ всего изображения на анализ отдельных сегментов. При этом может быть использовано то, что определенные сегменты допускают анализ с помощью алгоритмов более эффективных, чем общий алгоритм 3, например, в случае, когда грамматика V,Vr ( s ), s, P, P( Z (Vr ( s ))), определенная на шаге 2, является двумерным обобщением регулярной грамматики. А именно, для использования этого факта следует на шаге 2 использовать именно такие, эффективные алгоритмы вместо алгоритма 2;

• объем памяти, необходимый алгоритму 3, зависит от упорядочения ind.

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

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

Третья глава «Настройка параметров контекстно-свободных конструкций» посвящена настройке параметров контекстно-свободных конструкций. Эта задача имеет такой формат: задано обучающее множество, состоящее из m обучающих изображений x1, x 2,…, x m из множества X изображений и соответствующих им выводов p1, p 2,…, p m из множества P выводов. Введем также некоторое множество R l векторов параметров. Пусть Q : X P R,, — параметризованная по вектору функция, определяющая штраф за вывод p P изображения x X.

Найти такой вектор параметров, чтобы для всех Задача 1.

изображений из обучающего множества D штраф за соответствующий им вывод оказался самым низким среди всех возможных выводов j j p = arg min Q ( x, p ), j = 1,…, m.

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

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

Естественно считать параметрами эталонные изображения букв текста, но, как было сказано, в этом случае Q зависит от параметров квадратично. Однако несложное преобразование, которое в распознавании получило название спрямления пространства параметров, обеспечивает линейную зависимость Q от. В этом случае задача 1 заключается в решении новых параметров относительно такой системы уравнений для определенной заданной вектор функции : X P R l :

p = arg min, ( x, p ), j = 1,…, m.

j j pP Эта система является эквивалентной системе линейных неравенств, ( x j, p ) ( x j, p j ) 0, j = 1,…, m, p P { p j}.

Сложность решения этой системы заключается в ее огромных размерах:

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

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

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

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

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

Каждому фрагменту g при этом ставится в соответствие определенная буква из алфавита A. Сегментом s будем называть пару s = ( g, ), состоящую из фрагмента g и имени, которое является буквой алфавита A. Фрагмент и имя сегмента s будем обозначать соответственно g ( s ) и ( s ). Традиционно задача распознавания изображения x текстовой строки формулируется как задача нахождения такой его сегментации, которая минимизирует суммарную разницу между эталонами букв и соответствующими им сегментами изображения x :

n( s) s = arg min f ( ( si ), x ( g ( si ))).

sS i = Здесь с помощью S обозначено множество всех возможных сегментаций, n( s ) равняется количеству сегментов в сегментации s, а x ( g ) обозначает сужение f ( ( si ), x ( g ( si ))) изображения x на поле зрения фрагмента g. Величина определяет разницу между изображением x ( g ( si )) и эталонным изображением буквы ( si ).

Известно, что такая постановка задачи в вероятностной интерпретации обозначает нахождение наиболее вероятной сегментации s при условии входного изображения x :

s = arg max P( s | x ). (4) s S При помощи P( s | x ) обозначена вероятность сегментации s при условии изображения x.

Такая постановка задачи может следовать из байесовской теории решений, поскольку является эквивалентной минимизации математического ожидания потерь, определенных некоторой функцией W : S S R, значение W ( s, s ') которой определяет потери от результата распознавания s при условии правильной сегментации s ' :

s = arg min P ( s ' | x )W ( s, s '). (5) sS s 'S 0, s = s ' Однако функция W ( s, s ') = потерь, при которой вычисление (5) 1, s s ' является эквивалентным вычислению (4), не учитывает того, на сколько отличается результат s распознавания от правильного s '. Так, например, она принимает одинаковые значения в случае одной неправильно распознанной буквы и в случае, когда правильно не было распознано ни одной буквы!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Статьи в научных профильных изданиях.

[1] Шлезінгер М. І., Савчинський Б. Д., Анохіна М. О. Синтаксичний аналіз та розпізнавання друкованих нотних текстів // Управляющие системы и машины. – 2003. – №4. – С. 30–38.

[2] Савчинський Б. Д. Нетрадиційні задачі розпізнавання тексту в межах байєсівської теорії прийняття рішень // Управляющие системы и машины. – 2005. – №1. – С. 8–17.

[3] Савчинський Б. Д., Камоцький О. В. Настройка алгоритму розпізнавання тексту // Управляющие системы и машины. – 2005. – №2. – С. 17–24.

[4] Павлюк О. В., Савчинський Б. Д. Ефективний синтаксичний аналіз та розпізнавання структурованих зображень // Управляющие системы и машины. – 2005. – №5. – С. 13–24.

Статьи в сборниках трудов конференций.

[5] Шлезінгер М. І., Савчинський Б. Д., Анохіна М. О. Комп’ютерна технологія для розпізнавання типографських нотних текстів // Міжнародна конференція «Електронні зображення та візуальні мистецтва» EVA-2002. Збірник праць. – Київ:

2002. – С. 82–86.

[6] Savchynskyy B., Kamotskyy O. Character templates learning for textual images recognition as an example of learning in structural recognition // Proc. of the 2-nd Intern.

Conf. on Document Image Analysis for Libraries DIAL 2006. — April 27-28 — Pp. 88– 95.

Тезисы конференций.

[7] Савчинський Б. Д. Синтаксичний аналіз та розпізнавання друкованих нотних текстів // Автоматика – 2004 Матеріали 11-ої міжнародної конференції з автоматичного управління. – Київ: 2004. – С. 93.

[8] Савчинський Б. Д., Камоцький О. В. Налаштування параметрів в задачах структурного розпізнавання // Автоматика – 2004 Матеріали 11-ої міжнародної конференції з автоматичного управління. – Київ: 2004. – С. 94.

АНОТАЦІЯ Савчинський Б. Д. Контекстно-вільні граматичні конструкції для розпізнавання зображень текстових та графічних документів. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 – системи та засоби штучного інтелекту. – Міжнародний науково-навчальний центр інформаційних технологій та систем, НАН України та МОН України, Київ, 2007.

Теоретично і експериментально доведено доцільність та придатність апарату двовимірних контекстно-вільних граматичних конструкцій для розв'язання певних класів практичних задач розпізнавання семантично насичених зображень зі складною ієрархічною структурою. Сформульовано основні принципи побудови швидкодіючих програмних комплексів для розпізнавання зображень, які задаються за допомогою двовимірних контекстно-вільних граматичних конструкцій. Вперше сформульовано задачу настройки (навчання) контекстно-вільних конструкцій, як задачу відшукання таких штрафів за використання правил, що забезпечують безпомилкове розпізнавання заданої навчальної множини. Суттєва відмінність сформульованої задачі від загальновідомих задач навчання у розпізнаванні полягає у форматі навчальної множини, кожний приклад з якої є складним зображенням з ієрархічним переліком його складових фрагментів. Показано, що сформульована задача настройки контекстно-вільних конструкцій зводиться до розв’язання системи лінійних нерівностей. Незважаючи на те, що кількість нерівностей у цій системі експоненційно залежить від розміру зображень, в роботі показано її поліноміальну розв’язність і визначено ефективний скінченнокроковий алгоритм її розв’язання.

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

АННОТАЦИЯ Савчинский Б. Д. Контекстно-свободные грамматические конструкции для распознавания изображений текстовых и графических документов. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 - системы и средства искусственного интеллекта. Международный научно-учебный центр информационных технологий и систем, НАН Украины и МОН Украины, Киев, 2007.

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

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

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

ABSTRACT Savchynskyy B. D. Context-free grammar constructions for recognition of textual and graphical document images. – Manuscript.

Thesis for scientific degree of candidate of technical sciences on speciality 05.13.23 systems and tools of artificial intelligence. - International Research and Training Center for Information Technologies and Systems, National Academy of Sciences and Ministry of Science and Education of Ukraine, Kyiv, 2007.

Advisability and applicability of two-dimensional context-free grammatical constructions for recognition of complex hierarchically structured images have been theoretically and practically proved. The following particular results have been achieved: the structure of grammatical rules has been extended, namely, such rules are introduced, which allow image fragments to intersect. It is demonstrated that after such obviously expedient extension the task of real image parsing remains still effectively solvable. It is proved that for a certain class of similarity functions such extension does not violate their additivity, which is a necessary condition of an effective parsing. Namely, similarity of a complex image is determined by a total similarity of its constituents, even if they intersect.

For the investigated class of two-dimensional grammar constructions an image derivation procedure was build, which consists in reviewing already derived image fragments and creating the new ones according to derivation rules. This procedure has a polynomial complexity, however its space complexity depends on an order of image fragments review. The task of optimal review ordering to minimize space complexity was formulated and solved.

A subclass of two-dimensional context-free grammar constructions was defined, which has a linear parsing complexity with respect to an image size. This complexity is much less then the corresponding one in a general case of context-free constructions.

Constructions of this subclass can be considered as a two-dimensional generalization of regular grammars.

The main principles of fast software creation for image recognition on a base of two dimensional context-free constructions have been formulated. The speed of parsing algorithms is provided by two principles: (i) certain image fragments are derived in a framework of such context-free construction subclasses, which are more effective than the general one, as in a framework of two-dimensional regular grammars;

(ii) parsing technique allows inclusion of external recognition procedures. Results of their work is used in a way that only such image derivations are taken into account, which contain (or do not contain) fragments specified by the external procedures.

A learning problem for context-free constructions is formulated like a problem of parameters tuning provided errorless recognition of a training set. A considerable difference of the problem from well-known learning problems consists in a format of the training set. Namely, each training example consists of an image and a hierarchical list of its constituents.

It is also shown that the formulated learning problem is equivalent to a system of linear inequalities. In spite of the fact, that the number of inequalities in the system increases exponentially with sizes of training images, it is shown that the system is polynomially solvable. An effective finite-step algorithm for its solution is developed.

A new problem of character templates learning for printed text recognition is formulated and solved as a problem of context-free constructions learning. Novelty of the approach consists in the following – in well-known learning approaches the templates are tuned in a way to provide errorless recognition of separated character images and our approach is intended for the systems, which should correctly recognize text lines as a whole, when individual characters are not isolated one from another. This approach is intended for recognition of essentially damaged text images and it has been experimentally tested on real examples.

Novel problems of sequences (in particular, text line images) recognition have been researched in their statistical formulations. It is shown, that a well-known problem consisting in a search of a sequence with maximum a posteriori probability in many cases is not the best one in comparison with other possible formulations. Several alternative problems are formulated and solved.

Key words: document images recognition, context-free grammatical constructions, context-free constructions learning, learning in structural recognition.

Подп. к печати 03.05.07г. Формат 60х84/16.

Бумага DATA COPY. Ризография. Усл. печ. лист. 1,16.

Учётно-изд. лист. 1,25.

Тираж 100. Зам. 7/ Напечатано ООО “ВИТУС” Ltd.

03680 Киев-680, просп. акад. Глушкова,