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

(JU-з

на правах рукописи

Хоанг Зянг

ПРОЕКТИРОВАНИЕ МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ ДЛЯ АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ РАСПОЗНАВАНИЯ ПЕЧАТНЫХ ДОКУМЕНТОВ НА ВЬЕТНАМСКОМ ЯЗЫКЕ

Специальность 05.13.12 -Системы автоматизации проектирования (приборостроение)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2008

003460029

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

Научный руководитель:

д.т.н., профессор Коробейников Анатолий Григорьевич

Официальные оппоненты:

д.т.н., профессор Арустамов Сергей Аркадьевич

к.т.н., Сарычев Дмитрий Юрьевич

Ведущая организация: Марийский государственный технический университет

Защита состоится "9" декабря 2008 г., в 15:50 часов на заседании диссертационного совета Д 212.227.05 при Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д. 49

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного университета информационных технологий, механики и оптики. Автореферат разослан " 7 " ноября 2008 г.

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

диссертационного совета Д 212.227.С

к.т.н, доцент

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

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

Работы В.М. Курейчика, И.П. Норенкова оказали существенное влияние на развитие САПР и послужили базой для создания новых подходов в совершенствовании систем автоматизированного проектирования (АП).

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

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

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

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

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

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

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

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

3. Разработка методики решения задачи сегментации и извлечения символов.

4. Разработка методики решения задачи распознавания символов на основе применения геометрического анализа и нейронных сетей.

5. Построение и обучение нейронной сети.

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

Методы исследования базируются на использовании теории и методов САПР, принципах системного подхода, теории

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

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

Основные положения, выносимые на защиту:

1. Методика первичной обработки изображения

2. Методика сегментации блоков

3. Методика извлечения строк из текстовых блоков

4. Методика извлечения символов из строки

5. Методика распознавания символов на основе применения геометрического анализа и нейронных сетей. Комбинирований алгоритм для повышения точности распознавания.

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

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

2. Полученные результаты используются для создания коммерческого ПО для распознавания вьетнамского языка.

3. Сокращение сроков и стоимости преобразования бумажных документов в текстовый цифровой документ.

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

Апробация результатов работы. Основные результаты работы докладывались на научно-технических конференциях. Среди них: Международная конференция «Интеллектуальные САПР - 2006» (3-10 сентября 2006 г., Геленджик), конференция ППС (8 января 2008 г. СПб ГУ ИТМО), V Всероссийская межвузовская конференция молодых ученых (15 - 18 апреля 2008 г. СПб ГУ ИТМО).

Публикации. Теоретические и практические результаты, представленные в диссертации, отражены в 6 научных работах, в

Структура и объём диссертационной работы. Диссертация состоит из введения, пяти глав, заключения, списка литературы из 42 наименований; изложена на 108 страницах машинописного текста, иллюстрированного 49 рисунками.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

- 22 латинские буквы: a,b,c,d,e,g,h,i,k,l,m,n,o,p,q,r,s,t,u,v,x,y.

- производные буквы с диакритическим знаком: а, а, ё, б, о", ir, d...

Диакритические знаки также используются для описания тонов вьетнамского языка. Значение слова зависит от его тона. Во вьетнамском языке имеется 6 тонов и обозначается следующим образом: а (нет диакритического знака), á, á, á, а, а. Когда основные буквы соединяются с диакритическими знаками, могут получиться сложные буквы, такие как а, а, й, и- и т. д.

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

Еще одно важное свойство вьетнамского языка - это его односложность. Каждый слог, состоящий из гласных и согласных букв пишется отдельно: с пробелом перед и после него. Например слово quoc hdi (парламент) состоит из двух слогов. Односложность

букв пишется отдельно: с пробелом перед и после него. Например слово quoc hgi (парламент) состоит из двух слогов. Односложность затрудняет применение словарных методов, чтобы поправить некорректно распознаваемые слова.

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

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

Процесс преобразования документов, хранимых в традиционных форматах (газета, книга...), в текстовый вид проведен на рис. 1.

Дискретизация входного

(5.

Э документа:

Входной документ (книга, газета ...)

преобразования документов в цифровые

цветовое цифровое изображение

<э

Подавление шумов

Бинаризация

изображение с низким уровнем шумов

бинарное изображение

Выравнивание страница

изображение с

корректным

выравниванием

блок-сегментация текстовые и

__графические

блоки

распознавание извлечение символов

извлечение строк

Текстовый файл

символы

строки

Рис. 1. Этапы получения, обработки и распознавания

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

Разработан алгоритм определения "связных компонентов", который используется практически на всех этапах обработки: подавлении шумов, сегментации, извлечении символов, распознавании и т. д. На рис. 2а и 26 представлены алгоритмы анализа связных компонентов.

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

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

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

В качестве расстояния можно выбрать минимальное или среднее значение вертикального и горизонтального измерения. Алгоритм вычисления ДЛКС представлен на рис. 3.

Процесс бинаризация ДЛКС с пороговым значением / разбивает исходное изображение на блоки. Чем меньше I, тем больше количество блоков. Если ? = 255, то все пиксели ДЛКС будут черными и все изображение - один блок. Это определяется как корневой блок. Далее производится бинаризация с t < 255. Получаются дочерние блоки. Если процесс повторить для каждого блока, то в результате получим дерево разделения исходного документа. Блоки одного уровня можно упорядочить с помощью их относительного положения. Для определения их упорядоченных положений, можно использовать, например, позиции их ограничивающих прямоугольников.

Рис. 2а. Алгоритм анализа связных компонентов

Рис. 2 б. Рекурсивный алгоритм подпрограммы Label для маркировки пикселей

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

Для извлечения строк из изображения применяется метод вертикальной проекции. Сначала строим вертикальную проекцию черно-белого текстового блока путем нахождения количества черных пикселей S, и крайней правой черной точки для каждой строки точек i, где / = 1 ..h, h - высота изображения. Очевидно х -координата крайней правой черной точки. Это не что иное, как длина данной строки точек Z,,.

Нормализированная вертикальная проекция равна:

Pii^Si/L;. (1)

Рис. 3 Алгоритм вычисления ДЛКС (Н, IV- высота и ширина изображения)

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

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

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

Блок-схема разработанного алгоритма представлена на рис. 4. После работы рассмотренного алгоритма, могут появиться связные компоненты, которые содержат больше одного символа. Эти символы надо разделить. Разделение связанных символов производится следующим образом:

Сначала рассматриваемый компонент передается на распознавание. Если получаемый рейтинг распознавания ниже определенного значения - значит это не один символ. При разбиении этого компонента построим горизонтальную проекцию для нахождения потенциальных точек разделения. Эти точки разделяют компонент наИ частей. Каждый символ может состоять из 1 до N-1 части подряд. Рассмотрим все возможные варианты комбинаций частей. Для каждого варианта вычисляется суммарный рейтинг распознавания. Выбирается вариант, который имеет максимальный суммарный рейтинг.

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

Рис. 4 Алгоритм извлечения символов из строки

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

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

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

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

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

Сначала изображение буквы

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

Рис. 5 Нормализация изображения букв

где т,п - координаты точки (ш=1 ...М,п=1 ...Ы) Т-количество образцов для обучения, Тг количество образцов, в которых данная

точка - черная. На этапе распознавания вычисляется решающая функция:

М N

^ЕХЖ* (з)

т=\ /т=|

где (Зтп = Рт п если точка (ш,п) распознаваемого изображения - черная и = 1 - Рт п в противном случае. Значения решающей функции С?,' вычисляются для всех букв алфавита (1 = 1 ... Э -количество букв в алфавите).

Анализ геометрических параметров букв

На этапе обучения для каждой буквы Wi вычисляются средние координаты центра тяжести (х^у,) и среднее отношение высоты к ширине буквы Ь(. На этапе распознавания вычисляются решающие функции:

С^^х-х.у+^у-у,)2 (4)

| (5)

где (х,у)- координаты центра тяжести, Ь - отношение высоты к ширине распознаваемого изображения • Принципал "воднаяяма"

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

(6)

где Ор-отклонения ям i-ого типа распознаваемого изображения от реального постоянного для каждой буквы

Таким образом, решение, что это буква,_ имеет место в случае максимального значения суммарной решающей функции:

G' =ki*G' г k2* Gi2-k3*G,3+k4*Gi4 (7)

где кгвесовые коэффициенты.

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

входной вектор скрытый слой

г—^ С

выходной слой выходной вектор

Л Г

' 221

221

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ В ходе работы над диссертацией получены следующие результаты.

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

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

3. Разработан алгоритм извлечения строк из текстовых блоков

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

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

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

7. Разработаны экспериментальные программные модули используя язык С++, среду программирования Visual Studio, среду для построения и моделирования нейронных сетей MathLab.

Основные результаты диссертации опубликованы в

следующих работах:

1. Хоанг 3. Алгоритмы распознавания текста. /В книге "Труды международных научно-технических конференций "Интеллектуальные системы" (IEEE AIS'06)" и "Интеллектуальные САПР (CAD-2006)". Научное издание в 3-х томах: М.: Изд-во Физико-математической литературы, 2006, Т.2.-580 с. -ISBN 5-9221-0684-4. стр. 496-497

2. Хоанг 3. К оценке защищенности систем информационных технологий /Труды 10-ой международной конференции "Теория и технология программирование и защиты информации" - СПб 18 мая 2006, стр. 114-118

3. Коробейников А. Г., Михайличенко О.В., Хоанг 3. Выбор коэффициентов матрицы дискретно-косинусного преобразования при построении стеганографических систем//Вестник компьютерных и информационных технологий № 11,2008 г. стр. 51-65

4. Хоанг 3. Разработка метода сегментации изображения для распознавания печатных документов. /Сборник материалов Всероссийской научно-практической конференции с международным участием: в 2. ч. - 4.2 Йошкар-Ола: Марийский государственный технический университет, 2008. - стр. 41-46.

5. Хоанг Зянг, А.Г.Коробейников, С.Н.Кузнецова, И. Б.Троников, В.А. Семенов. Метод сегментации изображения для распознавания печатных документов//Изв. вузов. Приборостроение. 2008. Т. 51, № 12. стр. 32-36

6. Хоанг Зянг, А.Г.Коробейников. Сегментация изображения для распознавания печатных документов. /Информационные технологии и телекоммуникационные системы. Т. 55, № 3. стр. 91-95

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел. (812) 233 46 69

Усл.печлист - 1,0 Тираж 100 экз. .

ВВЕДЕНИЕ.

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

РАСПОЗНАВАНИЯ ТЕКСТА.

ГЛАВА 2. ПОЛУЧЕНИЕ ЦИФРОВОГО ИЗОБРАЖЕНИЯ ИЗ ПЕЧАТНЫХ ДОКУМЕНТОВ И ПЕРВИЧНЫЕ ОБРАБОТКИ ИЗОБРАЖЕНИЯ.

2.1 Преимущество электронных документов по отношению к бумажным. Типы электронных Документов.

2.2 Процесс преобразования документов.

2.3 Дискретизация входного документа.

2.4 Бинаризация.

2.5 Связный компонент.

2.5.1 Понятие связного компонента.

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

2. 6 Подавление шумов.

2.6.1 Удаление малых шумовых блоков.

2.6.2 Подавление шума с помощью морфологических операций.

2.7 Выравнивание страницы.

2. 7.1 Метод Байрда.

2.7.2.Метод Гашизуме.

2.7.3.Метод Блумберга.

2.7.4.Метод Амина и By.

2.7.5. Разработанный метод.

ГЛАВА 3. СЕГМЕНТАЦИЯ БЛОКОВ ДОКУМЕНТА.

3.1 Анализ основных методов сегментации.

3.2 Динамическая локальная карта связи.

3.3 Анализ результатов применения алгоритма определения пороговых значений для многошкальной сегментации.

3. 4 Разработка алгоритма построения иерархического дерева сегментации.

3. 5 Идентификация текстовых блоков.

ГЛАВА 4. ВЫДЕЛЕНИЕ СТРОК И СИМВОЛОВ ИЗ ИЗОБРАЖЕНИЯ. КЛАСТЕРИЗАЦИЯ СИМВОЛОВ.

4.1 Разбиение текстовых блоков на строки.

4.2 Извлечение символов из строки.

4.2.1 Разделение связанных символов.

4.2.2 Объединение связных компонентов одного символа.

4.2.3 Извлечение символов на базе распознавания.

4.2.4 Целостный подход.

4.2.5 Разработанный метод.

ГЛАВА 5. РАЗРАБОТКА АЛГОРИТМОВ РАСПОЗНАВАНИЯ ВЬЕТНАМСКОГО ЯЗЫКА.

5.1 История развития оптического распознавания символов.

5.2 Обзор по современным опубликованным методам распознавания символов.

5.2.1 Метод Пелега (Peleg) и Розенфелда.

5.2.2 Метод Наги (Nagy) и др.

5.2.3 Метод Ли (Lee) на основе скрытой Марковской модели.

5.2.4 Распознавание символов на базе нейронных сетей.

5.3 Разработанный метод.

5.3.1. Рейтинговый подход.

5.3.2. Распознавание с помощью нейронных сетей.

5.3.3. Комбинированный подход.

ГЛАВА 6. ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ КОМПЛЕКСА МЕТОДОВ И

АЛГОРИТМОВ.

6.1 Обработка документа перед распознаванием.

6.1.1 Анализ компонентов.

6.1.2 Определение блоков.

6.1.3. Идентификация блоков.

6.1.4 Определения угла отклонения.

6.1.5 Извлечения строк из текстовых блоков.

6.1.6 Извлечения символов из строк.

6.2 Распознавание символов.

6.2.1 Распознавание с помощью рейтингового подхода.

6.2.2 Распознавание с помощью нейронных сетей.

6.2.3. Комбинированный подход.

Актуальность темы диссертационного исследования.

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

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

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

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

В то же время многие задачи проектирования (например, подавляющее большинство задач структурного синтеза) плохо поддаются автоматизации, решаются вручную, эвристически на основе опыта и интуиции разработчика. При этом качество получаемых решений определяющим образом зависит от творческих способностей человека. Такие задачи принято называть плохоформализуемыми, к ним относятся: 1) задачи, не имеющие точно выраженной математической постановки (в терминах САПР - задачи, не имеющие конструктивной ММ) и/или 2) задачи, решение которых алгоритмическими методами невозможно или неэффективно. Наряду с поиском и разработкой формальных подходов к решению таких задач перспективным является использование методов и средств искусственного интеллекта (ИИ).

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

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

• неоднозначность, неполнота и противоречивость исходных данных,

• неоднозначность, неполнота и противоречивость знаний о решаемой задаче,

• большое количество возможных решений.

Плохоформализуемые задачи - это чаще всего задачи в нечисловой форме.

Работы в области ИИ ведутся по нескольким тесно связанным друг с другом направлениям: автоматическое доказательство теорем, распознание образов и сцен, обработка естественного языка, автоматическое программирование, планирование целесообразного поведения роботов, консультирующие экспертные системы и так далее. Теоретические и практические результаты, достигнутые в каждом из этих разделов ИИ, находят или могут найти приложение в САПР. Среди них распознание образов является одним из развивающихся разделов ИИ и часто применяется для обработки входных данных для САПР. В данной работе основное внимание уделяется задаче оптического распознания образов, (англ.: OCR - Optical Character Recognition) которая представляет собой процесс преобразования изображений (с помощью сканера, фотоаппарата, фотокамеры и т.д), содержащих рукописный или машинописный текст в машинно-редактируемый текст. Это преобразование дает большую пользу для коммерческих и жизненных целей. OCR является одним из исследовательских разделов распознавания образов, искусственного интеллекта и компьютерной визуализации.

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

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

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

С 1960 по 1980-годам, оптическое распознавание символов непрерывно развивалось. Были разработаны более совершенные методы. Распознавание уже не просто сравнение символов с шаблоном. Появились статистические и синтаксические методы.

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

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

В середине 1980-годов на базе этих развитой создана OCR-система "Omnifont", которая может распознавать символы разных шрифтов и размеров с высокой точностью[6],[9].

Алгоритмы оптического распознавания символов (англ.: optical character recognition или OCR) алгоритмы постоянно развиваются и совершенствуются. В настоящий момент для некоторых языков, например английского, французского, русского, уже разработаны алгоритмы, распознающие печатные тексты с высокой эффективностью [1],[8]. Современное коммерческое ПО OCR для этих языков рекламируются с заявлением о точности распознавания выше 99%[10]. Но для более сложных языков, таких как вьетнамский язык, не решено еще много задач. Во вьетнамском языке букв и их комбинаций с диакритическими знаками примерно 190, и многие из них очень похожи друг на друга. Поэтому кроме обычных алгоритмов требуются специализированные алгоритмы для распознавания таких языков. На настоящий момент публикаций по теме "Распознавание вьетнамского языка" очень мало и они не решают многие задачи, проявляющие в процессе распознавания этого языка [2]. Например, в работе [2] авторы представляют метод распознавания документа вьетнамского языка. Основав на особенностях вьетнамского языка, они пытались минимизировать число символов и интегрировать проверку орфографии в процесс распознавания. Они также разработали статистические модели частоты присутствия слова в тексте для прогнозирования следующего ; слова, словарь вьетнамской частотности слова был создан, чтобы предсказать следующие слова. Но, несмотря на попытки этих авторов, строгие, эксперименты показывают, что их методы недостаточно эффективны для обработки сканируемых изображений с шумами, и предлагаемые модели не отражают все сложности вьетнамского языка. Поэтому, исходя из вышесказан-' ного, задача разработки математического обеспечения (МО) для систем автоматизированного проектирования (САПР) OCR — систем, специализированных для вьетнамского языка, является актуальной.

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

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

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

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

3. Разработка методики решения задачи сегментации и извлечения символов.

4. Разработка методики решения задачи распознавания символов на основе применения геометрического анализа и нейронных сетей.

5. Построение и обучение нейронной сети.

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

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

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

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

Основные положения, выносимые на защиту:

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

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

3. Разработан алгоритм извлечения строк из текстовых блоков

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

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

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

7. Разработаны экспериментальные программные модули используя язык С++, среду программирования Visual Studio, среду для построения и моделирования нейронных сетей MathLab.

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

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

2. Полученные результаты используются для создания коммерческого ПО для распознавания вьетнамского языка.

3. Сокращение сроков и стоимости преобразования бумажных документов в текстовой цифровой документ.

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

Апробация результатов работы. Основные результаты работы докладывались на научно-технических конференциях. Среди них: Международная конференция «Интеллектуальные САПР - 2006» (3—10 сентября 2006 г., Геленджик), конференция ППС (8 января 2008 г. СПб ГУ

ИТМО), V- Всероссийская межвузовская конференция молодых ученых (15-18 апреля 2008 г. СПб ГУ ИТМО).

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

Структура и объём диссертационной работы. Диссертация состоит из введения, шести глав, заключения, списка литературы из 42 наименований; изложена на 108 страницах машинописного текста, иллюстрированного 49 рисунками.

Заключение

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

Основные преимущества разработанных методов и алгоритмов

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

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

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

Будущие работы и усовершенствование

Как показано в главе 6, точность разработанного метода распознавания составляет примерно 95%. Это конечно не предел. Можно повысить этот коэффициент следующими путями:

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

Одна из главных причин ошибочного распознавания - это подобие нескольких букв (например, буквы 1, i и число 1, к и h) или буква с похожими диакритическими знаками (например, б, б, 6). Если разработать грамматический анализ как дополнительную операцию после распознавания, то можно значительно улучшить результат распознавания. Другое направление для получения более качественного документа - это обработка слов, разбиваемых на двух строках, причем первая строка заканчивается тире.

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

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

1. Энциклопедия Википедия Электронный ресурс. / WTKIMEDIA Project -Режим доступа: http://vi.wikipedia.org/wiki/ChLrQuocngir, свободный. Яз. вьетнамский.

2. David Doermann, Jian Liang, and Huiping Li. Progress in camera-based document image analysis // In Proceedings of the 7th International Conference on Document Analysis and Recognition (ICDAR'03) 2003. - Vol. 1. - P. 606-616.

3. Oivind Due Trier and Anil K. Jain. Goal-directed evaluation of binarization methods // IEEE Transactions on Pattern Analysis and Machine Intelligence -December 1995.-№ 17(12).-P. 1191-1201.

4. Azriel Rosenfeld and John L. Pfaltz. Sequential operations in digital picture processing // Journal of the ACM. October 1966. - № 13(4). - P. 471-494.

5. Ronald Lumia, Linda Shapiro, and Oscar Zuniga. A new connected components algorithm for virtual memory computers. // Computer Vision, Graphics, and Image Processing 1983. - № 22(2). -P.287-300.

6. Linda Shapiro and George Stockman. / Computer Vision. Prentice Hall, March -2000.

7. Henry S. Baird. The skew angle of printed documents. In Lawrence O'Gorman and R. Kasturi, editors. // Document Image Analysis 1995. - P. 204-208. - IEEE Computer Society Press.

8. Akihide Hashizume, Pen-Shu Yeh, and Azriel Rosenfeld. A method of detecting the orientation of aligned components. // Pattern Recognition Letters № 4. - April 1986.-P. 125-132.

9. Dan S. Bloomberg, Gary E. Kopec, and Lakshmi Dasari. Measuring document image skew and orientation. // In Proceedings of the SPIE Conference on Document Recognition II 1995. P. 302-316.

10. Alan Pearlman. Converting to ABBYY FineReader OCR 9.0. Электронный ресурс. Режим доступа:http://www.law.com/jsp/legaltechnology/pubArticleLT.jsp?id=1207219552296

11. Adnan Amin and Sue Wu. Robust skew detection in mixed text/graphics documents. // In Proceedings of the 8th International Conference on Document Analysis and Recognition. 2005. P. 247-251.

12. A. Jain and B. Yu. Document representation and its application to page decomposition. / IEEE trans. // On Pattern Analysisand Machine Intelligence. № 20(3). - March 1998. - P. 294-308.

13. O. Okun, D. Doermann, and M. Pietikainen. Page segmentation and zone classification: The state of the art. // In UMD 1999.

14. F. Wahl, K. Wong, and R. Casey. Block segmentation and text extraction in mixed text/image documents. // CGIP. 1982. - № 20. P. 375-390.

15. D. Wang and S. Srihari. Classification of newspaper image blocks using texture analysis. // CVGIP 1989. № 47. P. 327-352.

16. T. Pavlidis and J. Zhou. Page segmentation by white streams. // Proc. 1st Int. Conf. Document Analysis and Recognition (ICDAR). 1991. P. 945-953. - Int. Assoc. Pattern Recognition.

17. M. Hose and Y. Hoshino. Segmentation method of document images by two-dimensional Fourier transformation. // System and Computers in Japan. 2004 P. 57-65.

18. A. Jain. Fundamentals of digital image processing. Prentice Hall, 1990.

19. C. Tan and Z. Zhang. Text block segmentation using pyramid structure. // SPIE Document Recognition and Retrieval. San Jose, USA. - 2001 January 24-25. P.297-306.

20. S. S. G. Nagy and S. Stoddard. Document analysis with expert system. // Proceedings of Pattern Recognition in Practice II. June 1985.

21. R. B. Hennis. The IBM 1975 optical page reader: System design. // IBM Journal of Research and Development. №12(5). - P.346-353. - September 1968.

22. Robert M. Haralick, S. R. Sternberg, and X. Zhuang. Image analysis using mathematical morphology. // IEEE Transactions on Pattern Analysis and Machine Intelligence. № 9(4) - 1987. - P. 532-550.

23. George Nagy. Twenty years of document image analysis in PAMI. // IEEE Transactions on Pattern Analysis and Machine Intelligence, № 22(1) January 2000.-P. 38-62.

24. Yann LeCun, Leon Bossou, Yoshua Bengio, and Patrick Haner. Gradient-based learning applied to document recognition. // Proceedings of the IEEE. № 86(11) November 1998. - P. 2278-2324.

25. Richard G. Casey and Eric Lecolinet. A survey of methods and strategies in character segmentation. // IEEE Transactions on Pattern Analysis and Machine Intelligence. № 18(7) July 1996. - P. 690-706.

26. Gary Huang, Andrew McCallum, and Erik Learned-Miller. Cryptogram decoding for optical character recognition. // Technical Report 06-45 June 2006. University of Massachusetts Amherst.

27. Dilip Sarkar. Methods to Speed Up Error Back-Propagation Learning Algorithm // ACM Computing Surveys, Vol. 27, №. 4, December 1995

28. Gustav Tauschek. Reading machine Электронный ресурс. / U.S. Patent 2026329, December 1935. Режим доступа:http://www.google.com/patents?vid=USPAT2026329

29. Paul W. Handel. Statistical machine Электронный ресурс. / U.S. Patent 1915993, June 1933. Режим доступа:http://www.google.com/patents7vidKJSPAT 1915993

30. S. Mori, CY Suen, and K. Yamamoto. Historical review of OCR research and development. //Proceedings of the IEEE, Vol. 80(7), 1992. P. 1029-1058.

31. Mindy Bosker. Omni document technologies. // Proceedings of the IEEE, Vol. 80(7), July 1992. P. 1066-1078.

32. George Nagy. Document image analysis: What is missing ? // Proceedings of the8th International Conference on Image Analysis and Processing. 1995. - P. 577—587.

33. Simon Kahan, Theo Pavlidis, and Henry S. Baird. On the recognition of printed characters of any font and size. // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 9(2), March 1987. P. 274-287.

34. Shmuel Peleg and Azriel Rosenfeld. Breaking substitution ciphers using a relaxation algorithm. // Communications of the ACM, Vol. 22(11), November 1979.-P. 598-605.

35. George Nagy, Sharad Seth, and Kent Einspahr. Decoding substitution ciphers by means of word matching with application to OCR. // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 9(5), 1987. P. 710-715.

36. Dar-Shyang Lee. Substitution deciphering based on HMMs with application to compressed document processing. // IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24(12), December 2002. P. 1661-1666.

37. Алгоритм Баума-Велша Электронный ресурс. Режим доступа: http://ru.wikipedia.org/wiki/AлгopитмБayмa-Beлшa

38. Viterbi algorithm. Электронный ресурс. — Режим доступа: http://en.wikipedia.org/wiki/Viterbi algorithm

39. Ньейн Эй. Разработка и исследование ПО для распознавания и анализа объектов на изображении с помощью нейронной сети: Диссертации насоискание ученой степени кандидата технических наук. / Московский инженерно-физический институт. М., 2007

40. Тропченко А.Ю. Цифровая обработка изображений. Методы сжатия и вторичной обработки изображений. Распознавание объектов на изображении. СПб.: ИТМО- 1999.