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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

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

Абрамов Евгений Сергеевич

МОДЕЛИРОВАНИЕ СИСТЕМ РАСПОЗНАВАНИЯ ИЗОБРАЖЕНИЙ (НА ПРИМЕРЕ ПЕЧАТНЫХ ТЕКСТОВ)

05.13.01 - (ис1емный анализ, управление и обработка информации (по прикладной математике и процессам управления)

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

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

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

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

профессор Андрианов Сергей Николаевич.

Официальные оппоненты: доктор физ.-мат. наук, проф.

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

Защита состоится « 26 » апреля 2006 г. в 13 часов на заседании Диссертационного Совета Д-212.232,50 но защите диссертаций на соискание ученой сгепени доктора наук при Санкт-Петербургском государственном университете по адресу: 199034, Санкт-Петербург, Университетская наб., 7/9, Менделеевский центр.

С диссертацией можно ознакомиться в Научной библиотеке им. A.M. Горького СПбГУ.

Автореферат разослан « 22 » марта 2006 г.

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

диссертационного совета

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

профессор Курбатова Г.И.

Братчиков Игорь Леонидович (СПбГУ),

кандидат техн. наук Епифанов Николай Анатольевич (ЗАО «Моторола ЗАО»).

Университет им. А.И. Герцена

хоОбА

Общая характеристика работы Актуальность темы

В настоящее время одними из важных чадам компьютерной обработки информации являются задачи автоматического распознавания образов. Для решения данного класса задач уже более полувека ведутся исследования в таких областях науки как математическая с1атистика, искусственный интеллект, принятие решений, цифровая обработка сигналов и т.п. Математические модели, лежащие в основе процесса распознавания образов описаны в работах Н. Винера. А. А. Ляпунова. М. Бонгарда. Р. Фишера. А. Н. Колмогорова, А. А. Харкевича и других ученых.

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

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

Таким образом, в настоящее время актуальным является создание программного обеспечения для распознавания текстов с откры-

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

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

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

Цели работы

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

1. Формализация задачи распознавания печатного текста и разделение ее на этапы.

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

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

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

Научная новизна

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

2. Предложены методики оценки полезности и понижения размерности вектора признаков в задачах распознавания изображений.

3. Разработан метод предварительной обработки (фильтрации) изображения для задач распознавания текстов.

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

Практическая ценность

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

строении систем распознавания текстов.

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

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

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

Апробация работы

Результаты данной работы докладывались на «XXXITI-XXXVI научных конференциях студентов и аспирантов факультета ПМ-ПУ» в 2002-2005ii'., на конференции «Технологии Microsoft в теории и практике программирования» в 2006 г., а также на семинарах кафедры компькнерного моделирования и мноюироцессорных систем факультета ПМ-ПУ СПбГУ и семинарах группы разработчиков проекта «Система распознавания текстов с oi крытым кодом» фирмы Digital Design.

Публикации

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

Структура и объем работы

Работа состоит из введения, пяти глав, заключения, списка цитируемой литературы и приложения. Список литературы включает 98 наименований. Работа изложена на 113 страницах и 20 страницах приложения, содержит 17 рисунков.

Содержание работы

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

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

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

2. Основные определения. Вводятся определения понятий и терминов, используемых в работе, таких как «образ», «сигнал», «распознавание» и т. п.

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

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

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

На основе проведенного в первой главе анализа, в заключении сформулированы следующие выводы:

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

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

Глава 2 посвящена формализации задач распознавания и обработки текстовой информации.

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

2. Задача выбора признаков. Здесь обсуждается и формализуется задача выбора метода выделения признаков изображений

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

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

4. Задача классификации векторов признаков. Параграф посвящен формализации проблемы классификации векторов признаков в задаче распознавания текстов.

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

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

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

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

Рассмотрим изображение об ьекга О, который необходимо распо-!на'1 ь (см. рис. 1). Введем N радиус-векторов г к, имеющих начало в центре изображения С и отстоящих друг от друга на некоторое уг-

ловое смещение а. Вдоль каждого век тора существую г точки изображения, принадлежащие объекту О и точки, не принадлежащие этому объекту.

Данные точки формируют отрезки Вы, 1 < I < Л^, которые представляют собой «куски» объекта О, вдоль вектора г к■ Дтгя каждого из отрезков мы можем определи ть его длину Ьы и расстояние от центра изображения до середины отрезка (1к1 ■ Будем использо-Рис. 1. Схема получения некто- пать в качестве элемента вектора

ра признаков изображения.

признаков величину

тк = 2_^<1ыЬк1, к = ¡=1

которую назовем моментом изображения вдоль вектора 1\. Вводя нормировку

тк

тк

к

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

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

строенного по описанной выше схеме. По результатам экспериментов. уверенное распознавание тестовой выборки достигалось при размерности вектора признаков равной 200.

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

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

Второй метод основан на введении количественной характеристики полезности элемента вектора признаков.

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

ментов). Для каждою -^алойного изображения с номером к эюг векюр принимав! значение v^l_ к — 1. N. Обозначим ггк элсмеш век-гора признаков с номером г, который соогвен'твуе! г-му лучу на данном изображении. Ра«чмо!рим последова!ельностъ значений г-го элемен'а век юра признаков {¿^ }/,="П\г на вгсх изображениях из базы данных эталонов и упорядочим ее по возрастанию:

С ^ < <ъ\2< ...<и1км= <ах- (1)

Введем в рассмотрение величины

у>1=ь1+1-и'кт, & = 1. N — 1, (2)

—Vх

п _ ^тах с шт

а ~ N

Величина (2) представляет собой расстояние между соседними значениями упорядоченной по возрастанию последовательности (1), а величина (3) среднее рассюяние между элементами последовательности (1).

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

£

я-1

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

3

шшетво ошибок

Риг. 2. Зависимость ошибочно классифицированных симвотов от размерности пек-юра признаков а при увеличении размерности вектора. б — при использовании функционала (4) , I, г я выбора расположения лучей' в при поиске оптимального расположения лучей на изображении

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

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

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

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

Глава 4 содержит описание алгоритмов, разработанных автором на основе результатов главы 3 и программного продукта, реализующего данные алгоритмы.

1. Выбор средств разработки программного обеспечения. Параграф содержит обоснование выбора средств разработки, использованных при реализации компьютерной модели системы распознавания. Для проведения экспериментов и отладки алгоритмов была выбрана среда Matlab. Реализации системы распознавания текстов выполняла(ь на языке Java с использованием JDK 1.5.0.

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

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

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

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

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

1. Тестирование системы распознавания текстов. На примере реальных текстов проводилась экспериментальная оценка качества распознавания символов по сравнению с системой FineReader.

Image Transform..

Interfere

heatureExtractei interfere

Classifier Interface

,,, >

• imatc

cUsi

, ЗтздвТгагвРвгтег CJhirWftjWefÄtr i«

' Di.1i itn.*jr

CU»

! 6es Property

у FeatureExtract« (.HteneiAentteatuwExtraaor

* Otts

EtaUmlmase

Cfassifter Nmauanfttr

Рис. 3. Структура системы распознавания текстов.

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

2. Оценка эффективности предложенных методов распознавания текстов. Пара! раф посвящен оценке времени работы предложенных методов распознавания текстов. Приводятся результаты сравнения быстродействия с FineReader.

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

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

Результаты, выносимые на защиту

1. Разработан метод фильтрации изображений символов перед распознаванием, использующий аппарат вейвлет-анадиза.

2. Предложен критерий выбора вектора признаков в задаче распознавания изображений.

3. Разработаны и протестированы ап'оритмы выделения признаков и принятия решений в задаче распознавания тексюв.

4. Построена и реашзована в виде программною продукта компьютерная модель системы распознавания текстов с оiкрытым кодом.

Публикации по теме диссертации

1. Абрамов Е. С. Применение стандарта DICOM для хранения медицинских изображений // Процессы управления и устойчивость: Труды 33-й научной конференции аспирантов и студентов / Под ред. В.Н. Старкова. - СПб.: НИИ Химии СПбГУ. 2002. - С. 323-326.

2. Абрамова A.C.. Абшмов К. С. Технологии проектирования распределенных вычислительных систем с дистанционным доступом / > Процессы управления и устойчивоеib. Труды 34-й научной конференции аспирантов и сгудешов / Под ред. Н В. Смирнова. В.Н. Стркова - СПб.- Изд-во С.-Петерб. ун-та, 2003. - С. 299-304.

3. Абрамов Е. С. Применение вейвлет-преобразований к распознаванию jeKCTOB ' Процессы управления и устойчивость: Труды 35-й межвузовской научной конференции аспирантов и студентов / Под ред. П.В. Смирнова. В.Н. Стркова. — СПб.: Изд-во С.-Петерб. ун-•ia. 2004. - С. 347-351.

4. Абрамов Е.С. О выборе вейвлет-базиеа для кодирования изображений , ' Процессы управления и усхойчивость: Труды 36-й межвузовской научной конференции аспирантов и студентов / Под ред. Н.В. Смиррюва, В.Н. Старкова. — СПб.: Изд-во С.-Петерб. ун-та. 2005. - С. 235 239.

5. Абрамов Е. С. О выделении признаков изображений в задаче распознавания 1 екстов. - СПб.. 2005. 24с. - Деп. в ВИНИТИ от 28.12.2005. № 1757-В2005.

6. Абрамов Е. С.. Абрамова A.C. Применение технологии ОрепМР для построения обучающей системы управления движением пучков заряженных частиц // Технологии Microsoft в теории и практике программирования. Материалы конференции / Под ред. и рос}). Р. Г. С j рож и на. Нижний Hobi ород: Изд-во Нижегородского госуниверситета. 2006. - С. 6-7.

Подписано в печать >5".03 2006 Формат бумаги 60x84 1/16 Бумага офсетная Печать ризографическаная Уел печ л. 1,0.

Тираж 100 экз. Заказ 3742. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ. 198504, Санкт-Петербург, Старый Петергоф, Университетский пр 26

-7-Ъ Trf

-7Z7%

Введение

1 Современные методы распознавания текста и анализа изображений

1.1 Базовые концепции распознавания образов.

1.1.1 Существующие парадигмы теории и практики распознавания образов.

1.1.2 Формализация проблемы распознавания образов

1.2 Основные определения.

1.3 Современные методы решения задач распознавания изображений

1.3.1 Признаки, используемые при распознавании изображений

1.3.2 Методы выбора признаков объектов для задач распознавания

1.3.3 Методы классификации признаков.

1.4 Методы предварительной обработки изображений.

1.4.1 Классификация искажений изображений символов

1.4.2 Методы предварительной обработки и борьбы с искажениями изображений.

2 Задача распознавания печатных текстов

2.1 Формализация задачи распознавания текстов.

2.2 Задача выбора признаков.

2.3 Задача обеспечения помехоустойчивости признаков.

2.4 Задача классификации векторов признаков.

3 Решение поставленных задач

3.1 Этапы решения задачи распознавания печатных текстов

3.2 Выбор методики выделения векторов признаков.

3.3 Построение векторов признаков изображений символов

3.4 Совершенствование метода получения векторов признаков

3.5 Фильтрация искажений изображений символов.

3.6 Классификация векторов признаков.

4 Программная реализация методов решения задач

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

4.2 Общий алгоритм решения задачи распознавания текста

4.3 Алгоритм распознавания символов.

4.3.1 Алгоритм предварительной обработки изображения

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

4.3.3 Алгоритм классификации признаков изображения

4.4 Структура системы распознавания текстов.

4.5 Оценка возможности масштабирования рассмотренных алгоритмов

5 Вычислительный эксперимент

5.1 Тестирование системы распознавания текста.

5.2 Оценка эффективности предложенных методов распознавания текстов.

Задачи, решаемые при помощи ЭВМ. В течение последних 60-ти лет вычислительная техника развиваласьмительными темпами. Это развитие состояло как в увеличении производительности вычислительных машин, так и в уменьшении их размеров. В настоящее время персональный компьютер значительно превосходит по производительности суперкомпьютер 70х-80х годов 20-го века.

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

Казалось бы, что современные компьютеры становятся все «умнее», и сейчас они могут решать те задачи, которые еще недавно были им не под силу. Однако, имеются задачи, которые не могут быть решены с использованием ЭВМ и сейчас.

Существует два типа задач, которые не решаются при помощи ЭВМ.

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

Во-вторых, существуют задачи, которые не имеют алгоритмического решения. Такие задачи не стали решаться лучше с ростом производительности вычислительных машин. Хорошим примером такого рода задач является задача создания искусственного интеллекта. Для того, чтобы решить эту задачу, необходимо знать, как действует интеллект человеческий, то есть необходимо разобраться в том, как «работает» человеческий мозг. Существует ли универсальный алгоритм, по которому он действует? На этот вопрос мы не можем ответить. Поэтому нам приходится руководствоваться догадками и предположениями о том, как действует человеческий разум для того, чтобы попытаться смоделировать его работу.

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

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

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

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

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

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

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

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

35, 39, 66], работа которых основывается на цифровой обработке данных.

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

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

• повышение качества выполняемых работ;

• повышение скорости решения задач.

Развитие теории распознавания образов. В течение достаточно продолжительного времени проблема распознавания образов привлекает внимание специалистов в области прикладной математики, а затем и информатики. В частности, можно отметить работы Р. Фишера, выполненные в 20-х годах и приведшие к формированию дискриминантного анализа, как одного из разделов теории и практики распознавания образов. В 40-х годах А. Н. Колмогоровым и А. Я. Хинчиным поставлена задача о разделении смеси двух распределений. Наиболее плодотворными явились 50-60-е годы XX века. В это время на основе массы работ появилась теория статистических решений. В результате этого появления найдены алгоритмы, обеспечивающие отнесение нового объекта к одному из заданных классов, что явилось началом планомерного научного поиска и практических разработок. В рамках кибернетики начало формироваться новое научное направление, связанное с разработкой теоретических основ и практической реализации устройств, а затем и систем, предназначенных для распознавания объектов, явлений, процессов. Иными словами, появилась новая научная дисциплина, которая получила название «Распознавание образов».

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

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

Несмотря на многолетние усилия исследователей, задача распознавания изображений остается не решенной до сих пор. В настоящее время существуют программы распознавания текстов, (например, ABBYY FineReader, Readiris, ScanSoft OmniPage, Cognitive Technologies CuneiForm) каждая из которых предлагает свою реализацию решения задачи распознавания. Эти программы позволяют достичь приемлемого качества распознавания для узкого круга задач и для каждой из них находится такой текст, который хорошо читается человеком и очень плохо поддается распознаванию программой. Это происходит потому, что качество распознавания текста такими программами в значительной степени зависит от влияния факторов, которые при чтении текста человеком не вызывают у него никаких затруднений. Например, человек может читать с любого разумного расстояния текст развернутый в пространстве практически под любым углом, напечатанный на плохой бумаге и содержащий символы любого размера, причем способ начертания этих символов также не играет никакой роли. Для машины же даже небольшое отклонение угла расположения текста, качества печати и начертания символов от заложенных в программу приведут к значительным отклонениям результатов распознавания от приемлемых. Поэтому нельзя сказать, что задача распознавания печатного текста решена. Актуальность решения этой задачи не вызывает сомнений поскольку обучение компьютеров чтению откроет возможность автоматизации таких процессов, как получение электронных копий различных документов и книг, поиск информации в бумажных источниках и т. п.

Тематика данной работы. В данной работе рассматривается задача распознавания печатных текстов. Эта задача была выбрана по причине ее высокой практической ценности и актуальности. Можно сказать, что решение этой задачи выведет теорию распознавания образов на новый виток развития и позволит автоматизировать многие процессы управления. Кроме того, задача распознавания текста решалась в рамках проекта «система распознавания текста с открытым кодом», разрабатываемого при поддержке фирмы Digital Design.

Заключение

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

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

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

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

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

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

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

Перспективы дальнейшей работы

В качестве возможных перспектив можно выделить следующие основные направления:

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

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

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

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

1. Разработан метод фильтрации изображений символов перед распознаванием, использующий аппарат вейвлет-анализа.

2. Предложен критерий выбора вектора признаков в задаче распознавания изображений.

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

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

1. Абрамов Е. С. О выделении признаков изображений в задаче распознавания текстов. СПб., 2005. 24с. - Деп. в ВИНИТИ от 28.12.2005. № 1757-В2005. «Вестник СПбГУ. Сер. 1.»

2. Абрамов Е. С. Применение стандарта DICOM для хранения медицинских изображений // Процессы управления и устойчивость: Труды 33-й научной конференции аспирантов и студентов / Под ред. В.Н. Старкова. СПб.: НИИ Химии СПбГУ, 2002. - С. 323-326.

3. Александреску А. Современное проектирование на С++: Обобщенное программирование и прикладные шаблоны проектирования. — М.:Издательский дом «Вильяме», 2002.

4. Анисимов Б. В., Курганов В. Д., Злобин В. К. Распознавание и цифровая обработка изображений. — М.: Высш. шк., 1983.

5. Астафьева Н. М. Вейвлет-анализ: основы теории и примеры применения. М: УФН, 1996. - Т.166. - №11. - С. 1145-1170.

6. Бахвалов Н.С. Жидков Н.П. Кобельков Г. М. Численные методы: Учеб. пособие. — М.: Наука. Гл. ред. физ.-мат. лит., 1987.

7. Белозерский С. А. Основы построения систем распознавания образов: Курс лекций. — Донецк: Дон. Гос. Инст. искусственного интеллекта, 1997.

8. Бишоп Д. Эффективная работа: Java 2 / Пер. с англ.; под ред. А. Падалки. — СПб: Питер: К: Издательская группа БХВ, 2002.

9. Буч Г. Объектно-ориентированный анализ и проектирование / пер. с англ.; под ред. И. Романовского и Ф. Андреева. — 2-е изд. — М.: Бином, 2001.

10. Васильев В. И. Распознающие системы: Справочник. — Киев: Наукова думка, 1983.

11. Гамма Э., Хелм Р., Джонсон Р., Влиссидес Дж. Приемы объектно-ориентированного проектирования. Паттерны проектирования. — СПб: Питер, 2001.

12. Гантмахер Ф.Р. Теория матриц. — 2-е изд., доп. — М.: Наука, 1966.

13. Гашников М. В. и др. Методы компьютерной обработки изображений. 2-е изд., испр. - М.: ФИЗМАТЛИТ, 2003.

14. Говорухин В., Цибулин Б. Компьютер в математическом исследовании. СПб.: Питер, 2001.

15. Гонсалес Р., Вудс Р. Цифровая обработка изображений: Пер. с англ. — Техносфера, 2005.

16. Гришкин В.М. Прогнозирующий вейвлет-фильтр // Процессы управления и устойчивость: Труды Зб-й межвузовской научной конференции аспирантов и студентов / Под ред. Н.В. Смирнова, В.Н. Старкова. — СПб.: Изд-во С.-Петерб. ун-та, 2005. С. 265-271.

17. Гренандер У. Лекции по теории образов: Том 1: Синтез образов / Пер. с англ.; под ред. Ю. Журавлева. — М.: Мир, 1979.

18. Гренандер У. Лекции по теории образов: Том 2: Анализ образов / Пер. с англ.; под ред. Ю. Журавлева. — М.: Мир, 1981.

19. Гренандер У. Лекции по теории образов: Том 3: Регулярные структуры / Пер. с англ.; под ред. Ю. Журавлева. — М.: Мир, 1983.

20. Гурко А. В., Копейкин М.В. Применение нечетких множеств для распознавания объектов // Процессы управления и устойчивость: Труды 34-й научной конференции аспирантов и студентов / Под ред. Н.В.

21. Смирнова, В.Н. Старкова. — СПб.: Изд-во С.-Петерб. ун-та, 2003. — С. 346-349.

22. Дащенко А. Ф. Кириллов В.Х., Коломиец JI. В. Оробей В. Ф. Matlab в инженерных и научных расчетах. — Одесса, «Астропринт», 2003.

23. Дейтел X. М., Дейтел П. Д., Сантри С. И. Технологии программирования на Java 2: Книга 1. Графика, JavaBeans, Интерфейс пользователя / Пер. с англ.; под ред. А. И. Тихонова. — М.: ООО «Вином пресс», 2003.

24. Дейтел X. М., Дейтел П. Д., Сантри С. И. Технологии программирования на Java 2: Книга 2. Распределенные приложения / Пер. с англ.; под ред. А. И. Тихонова. — М.: ООО «Бином пресс», 2003.

25. Дейтел X. М., Дейтел П. Д., Сантри С. И. Технологии программирования на Java 2: Книга 3. Корпоративные системы, сервлеты, JSP, Web-сервисы / Пер. с англ.; под ред. А. И. Тихонова. — М.: ООО «Бином пресс», 2003.

26. Дремин И. В., Иванов О. В, Нечитайло В. А. Вейвлеты и их использование М.: УФН, 2001. - Т. 171. - №5. - С. 465-501.

27. Дуда Р., Харт П. Распознавание образов и анализ сцен / Пер. с англ.; под ред. В. Л. Стефашока. — М.: Мир, 1976.

28. Зверев В. А. Стромков А. А. Выделение сигналов из помех численными методами. — Нижний Новгород: ИПФ РАН, 2001.

29. Коллерс П., Халле М., Иден М. и др. Распознавание образов / Пер. с англ. JL И. Титомира. — М.: Мир, 1970.

30. Круглов В. В., Дли М. И., Голунов Р. Ю. Нечеткая логика и искусственные нейронные сети. — М.: Физматлит, 2001.

31. Лакно В. Д. Биоинформатика и высокопроизводительные вычисления. Вестник РФФИ; № 3(21), 2000.

32. Люгер Д. Ф. Искусственный интеллект: стратегии и решения сложных проблем, 4-е изд.: Пер. с англ. — М.: Издательский дом «Вильяме», 2005.

33. Макконелл Дж. Основы современных алгоритмов: 2-е дополненное издание / Пер. с англ.; под ред. С. К. Ландо. — М.: Техносфера, 2004.

34. Новиков И. Я, Стечкин С. Б. Основы теории всплесков. — М.: Успехи мат. наук, 1998.

35. Патрик Э. А. Основы теории распознавания образов / Пер. с англ.; под ред. Б. Р. Левина. — М.: Советское радио, 1980.

36. Петров Б. Н., и др. Проблемы управления релятивистскими и квантовыми динамическими системами. — М.: Наука, 1982.

37. Прэтт У. Цифровая обработка изображений: Пер. с англ. — М.: Мир, 1982. Кн.1. - 312 с.

38. Прэтт У. Цифровая обработка изображений: Пер. с англ. — М.: Мир, 1982. Кн.2. - 480 с.

39. Пытьев Ю. П. Математические методы интерпретации эксперимента: Учеб. пособие для вузов. — М.: Высш. шк., 1989.

40. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов / Пер. с англ.; под ред. Ю. А. Александрова. — М.: Мир, 1978.

41. Сато Ю. Обработка сигналов: первое знакомство / Пер. с англ. — М.: Додэка, 2002.

42. Страуструп Б. Язык программирования С++. Специальное издание / Пер. с англ.; под ред. Ф. Андреева, А. Ушакова. — М.: ООО «Бином пресс», 2004.

43. Ту Дж., Гонсалес Р. Принципы распознавания образов / Пер. с англ.; под ред. Ю. И. Журавлева. — М.: Мир, 1978.

44. Файн В. С. Опознавание изображений (основы непрерывно-групповой теории и ее приложения). — М.: Наука, 1970.

45. Фаулер М., Скотт К. иМЬ. Основы. / Пер. с англ.; под ред. А. Галунова. — СПб: Символ-плюс, 2002.

46. Френке. JI. Теория сигналов / Пер. с англ.; под ред. Д. Е. Вакмана. — М.: «Сов. радио», 1974.

47. Фу К. Структурные методы в распознавании образов / Пер. с англ.; под ред М. А. Айзермана. — М.: Мир, 1977.

48. Фукунага К. Введение в статистическую теорию распознавания образов: Пер. с англ. — М.: Наука, 1979.

49. Фурман Я. А. и др. Введение в контурный анализ; приложение к обработке изображений и сигналов. — М.: Физматлит, 2003.

50. Хабибуллин И. Ш. Самоучитель Java. — СПб.: БХВ-Петербург, 2001.

51. Шеннон К. Работы по теории информации и кибернетике: Пер. с англ. — М.: Издательство иностранной литературы, 1963.

52. Математический энциклопедический словарь / Гл. ред. Ю. В. Прохоров; Ред. кол.: С. И. Адян, Н.С. Бахвалов, В. И. Битюцков, А. П. Ершов, Л. Д. Кудрявцев, А. Л. Онищик, А. П. Юшкевич. — М.: Сов. энциклопедия, 1988.

53. Allen R. L., Mills D.W. Signal analysis: time, frequency, scale and structure. — Piscataway: Wiley, 2004.

54. Amit Y. 2D object détection and récognition. — MIT, 2002.

55. Bow S. T. Pattern recognition and image preprocessing. — 2nd ed. — M.Dekker, 2002.

56. Bultheel A. Wavelets, with applications in signal and image processing. — 2002.

57. Chen G. Applications of wavelet transforms in pattern recognition and de-noising. — Concordia Univ. of Canada, 1999.

58. Chui C. K. An Introduction to Wavelets. — Calif.: Academic Press, 1992.

59. Daubechies I. Ten lectures on wavelets. — IAS/Park, 1997.

60. DeVore R. A., Lucier B. J. Wavelets. — Acta Numerica, A. Iserles, Cambridge University, 1992. — Vol. 1, pp 1-56.

61. Duda R., Hart P., Stork D. Pattern Classification. 2nd ed. - Willey, 2001.

62. Duin R. P. W. Four scientific approaches to pattern recognition. — The Netherlands: Delft University: Pattern Recognition Group: Department of Applied Physics of Technology, 2000.

63. Duin R. P. W., Pekalska E. Automatic pattern recognition by similarity representations // Electronic letters online — 2001. — Vol. 37, No. 3, pp. 159-160.

64. Duin R. P. W., Pekalska E. Classifiers for dissimilarity based pattern recognition // 15th International Conference on Pattern Recognition: Proceedings. pp. 12-16. Delft: Delft Univ. of technology, 2000.

65. Duin R. P. W., Ruli F., Ridder D. A note on core research issues for statistical pattern recognition // Pattern Recognition Letters — 2002. — No. 23, pp. 493-499.

66. Goswami J.C., Chan A. K. Fundamentals of wavelets. Theory, algorithms, and applications. — Wiley, 2000.

67. Kak A. C., Slaney M. Principles of Computerized Tomographic Imaging.

68. Society of Industrial and Applied Mathematics, 2001.

69. Lemaur G. On the choice of wavelet basis function for image processing.

70. Universite de Mons-Hainaut, 2003.

71. Lyons R. G. Understanding digital signal processing. — Upper Saddle River: Prentice Hall PTR, 2001.

72. Luo. G. Feature extraction by a wavelet algorithm for land classification.

73. Buckinghamshire: Chilterns University College, 2003.

74. Manassah J. T. Elementary mathematical and computational tools for electrical and computer engineers using matlab. — New York: CRC Press, 2001.

75. Marques de Sa J.P. Pattern recognition: concepts, methods, and applications. — Berlin: Springer, 2001.85j Mathews J. H., Fink D. K. Numerical methods using matlab: third edition. Upper Saddle River: Prentice Hall, 1999.

76. Meyer Y. Wavelets and Operators. — Cambridge: Cambridge Univ. Press, 1992

77. Ndjountche T., Unbehauen R. Image restoration: the wavelet-based approach. // International Journal of Pattern Recognition and Artificial Intelligence. 2003. - Vol. 17, No 1, pp. 151-162.

78. Nixon M.S., Aguado A.S. Feature extraction and image processing. — Oxford: Newnes, 2002.

79. Petrou M., Bosdogianni P. Image processing, the fundamentals. — Wiley, 1999.

80. Piater J. H. Visual feature learning: Submitted to the graduate school of the University of Massachusetts Amherst in partial fulfillment of the requirements for the degree of doctor of philosophy. — Massachusetts: Univ. of Massachusetts, 2001.

81. Wang Shuen-Shang et al. Invariant pattern recognition by moment Fourier descriptor. // Pattern recognition. — 1994. — Vol. 27, pp. 1735-1742.

82. Webb A. Statistical Pattern Recognition. — 2nd ed. — Wiley, 2002.

83. Абрамов С. M. и др. Суперкомпыотерные и GRID-технологии. — http://www.botik.ru/PSI/RCMS/activity/publications/2005.html, 2005.

84. Хабаров С. П. Экспертные системы: Курс лекций. — http: / / firm.trade.spb.ru / serp / maines.htm