Разработка программы распознавания зрительных образов

Аннотация.

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

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

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

Введение

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

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

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

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

1. Постановка задачи и технико-экономическое обоснование

1.1 Описание решаемой проблемы.

Распознавание образов (объектов, сигналов, ситуаций, явлений или процессов) — едва ли не самая распространенная задача, которую человеку приходится решать практически ежесекундно от первого до последнего дня своего существования. Для решения этой задачи человек использует огромные ресурсы своего мозга, включая одновременно около 10−12 млрд. нейронов. Именно это дает возможность людям мгновенно узнавать друг друга, с большой скоростью читать печатные и рукописные тексты, безошибочно водить автомобиль в сложном потоке уличного движения, осуществлять отбраковку деталей, разгадывать коды, древнюю египетскую клинопись и т. д.

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

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

В настоящее время наибольших успехов удалось добиться в распознавании печатных символов. Широкое распространение получили известные программы распознавания текстовой информации — Fine Reader и CuneiForm. Функции обнаружения и распознавания военных объектов противника уже давно закладываются в бортовые компьютеры самолетов, ракет, кораблей и подводных лодок. Немалое значение распознавание образов играет и в задаче создания технического зрения для интеллектуальных роботов.

В целом проблему распознавания можно разделить на две части: обучение и распознавание. Обучение осуществляется путем показа отдельных объектов с указанием их принадлежности тому или иному классу. В результате обучения распознающая система должна приобрести способность одинаково реагировать на все объекты одного класса и по-разному — на все объекты различных классов. В случае обучения можно действовать «с позиции грубой силы»: заложить в компьютер как можно больше известных образов-шаблонов и сравнивать с ними поступающие на вход системы для распознавания неизвестные образы. С первого взгляда этот путь кажется перспективным, но рассмотрим систему светочувствительных элементов — 32×48 (1536 элементов), с помощью которой будет считываться зрительное изображение для распознавания. Современные матрицы светочувствительных элементов обладают более совершенными техническими характеристиками — до 10 мегапикселей, т. е. до 10 миллионов элементов. Рассматриваемая система имеет значительно меньшее количество элементов, но даже на такой грубой сетке можно воспринять порядка 10⁴⁶⁰ возможных образов. Налицо комбинаторный взрыв. Хранить в памяти такое число шаблонных изображений и осуществлять с ними сравнение поступающих на вход образов невозможно, по крайней мере, для современных технических средств. Поэтому на практике системы распознавания на первой стадии обязательно обрабатывают изображение и выделяют характерные признаки, качественные или количественные. Таким образом, количество информации для распознавания существенно уменьшается. Одной из центральных задач распознавания является выбор исходного описания объекта: геометрический или структурный подход. Геометрический основывается на различии формы объектов. Структурный подход основан на анализе элементов объекта. При этом сначала выделяют фрагменты всех объектов и характеристики их взаимного расположения. Все это образует исходную БД — словарь, позволяющий строить различные гипотезы. Из них отбираются наиболее существенные для данного конкретного случая, и затем выполняется описание единого образа объектов, который используется для идентификации других объектов.

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

1.2 Назначение и область применения разрабатываемого средства.

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

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

1.3 Обоснование проведения работы.

В данном проекте разрабатывается программное средство, работающее под управлением операционной системы Microsoft Windows XP Professional. Данное программное средство может работать и в других ОС семейства Windows NT. При незначительных изменениях может быть перекомпилировано для ОС Windows, не относящихся к семейству NT, например Windows 98, так как написано на языке Delphi 7. При необходимости может быть портировано под платформу Linux.

Данную разработку можно использовать и как базовую основу дальнейших исследований.

1.3.1 Обоснование показателей эффективности проводимой работы

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

Система будет использоваться с одной из самых распространенных операционных систем Windows XP. Данные системы обладают высокими показателями безопасности и стабильности. Разрабатываемое программное средство дополняет набор существующих средств данной операционной системы.

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

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

В реальных системах может быть использована для:

— обнаружения на изображении объектов, интересных с точки зрения поставленной задачи;

— классификации объектов;

— контроля за движением объектов или изменением формы объекта;

— слежения за степенью удаленности объекта.

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

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

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

2. Обзор существующих методов решения

2.1 Обзор современной ситуации в разработке средств распознавания образов.

Несмотря на продолжительное время, потраченное на исследования в области искусственного интеллекта, на данный момент не существует оптимальных методов, позволяющих однозначно решить проблему распознавания образов. Это направление находится на стадии научных исследований и разработок. Многие компании и научные институты вкладывают большие ресурсы в решение данной проблемы. Все успехи находятся в разряде ноу-хау (know-how), стоят больших денег и не выкладываются в открытый доступ. Не существует известных сколько-нибудь успешно работающих систем. Отсутствуют также широко доступные компоненты и модули для прикладных программистов.

В настоящее время наибольших успехов удалось добиться в распознавании зрительных образов, таких как печатные символы. Не вызывает сомнений полезность известных программ распознавания текстовой информации — FineReader и CuneiForm. Распознавание символов по их графическому представлению — одна из самых старых и традиционных задач искусственного интеллекта. Еще в 1960;1970;е гг. были написаны десятки диссертаций и предложены сотни методов решения этой проблемы. Однако, только сейчас, когда сканеры и компьютеры стали общедоступны, распознавание символов получило полноценное практическое применение.

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

2.2 Обзор существующих подходов к процессу распознавания.

2.2.1 Методы, использующиеся для распознавания образов

Можно выделить 4 группы методов распознавания:

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

2) Статистические методы. Строится распределение для каждого класса и классифицируется по правилу Байеса. Распределение можно построить, используя тренировочную коллекцию. Тренировочная коллекция — коллекция объектов, для которых заведомо известны их образы. Например, коллекция аудио записей для каждого звука или коллекция изображений каждой буквы алфавита. Правило Байеса звучит так: «Пусть даны два распределения A, B и значение X, порожденное одним из этих распределений. Задача состоит в определении, каким из этих распределений было порождено значение X.».

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

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

4) Структурные и синтаксические методы. Разбирается объект на элементы. Строится правило в зависимости от вхождения / невхождения отдельных элементов и их последовательностей.

2.2.2 Методы распознавания символов

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

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

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

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

Структурными элементами являются линии, составляющие символ. Так, для буквы «Р» — это вертикальный отрезок и дуга.

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

Каждый искусно подобранный признак резко сокращает число возможных букв. Например, достаточно знать, что верхний левый угол буквы скруглен, и из 33 букв русского алфавита остаются лишь 9 кандидатов (а, б, е, з, о, с, ф, э, я). Букв, содержащих две «ноги» (вертикальные отрезки на всю высоту буквы) всего 10 (и, й, л, м, н, п, ц, ш, щ, ы). Таким образом, задав несколько простых вопросов, можно по ответам на них однозначно определить букву. Как видим, это тот самый подход, который заложен в пандемониуме и персептроне.

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

2.2.3 Организация системы распознавания

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

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

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

Рисунок 2.1 — Пандемониум Селфриджа Система распознавания образов, предложенная Оливером Селф-риджем [1] и называемая пандемониумом, состоит из элементов — демонов. Демоны — это относительно автономные сущности, выполняющие элементарные функции. На самом нижнем уровне находятся демоны данных, или демоны изображения (рисунок 2.1), которые играют роль светочувствительных элементов сетчатки глаза.

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

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

О. Селфридж так образно описал работу предлагаемого устройства [1]: «Задача демона понимания состоит в том, чтобы исследовать поступающие признаки и выкрикивать название своего класса, если он считает, что объект относится именно к этому классу. Демон должен кричать громко, если он уверен в своем решении, и тихо, если не уверен. Однако общий шум, производимый демоном понимания, зависит не только от его стараний, но и от способности кричать. Последнее определяет всемогущий демон решения, который наделяет демонов первого порядка сильными или слабыми голосами. Таким образом, каждый демон понимания выкрикивает название своего класса с интенсивностью, зависящей от его собственных оценок и от силы данного ему голоса. Демон решения, который ведет себя как председатель собрания, где проводится голосование, решает, название какого класса было выкрикнуто громче всех».

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

(2.1).

где w_ij — весовые множители, устанавливающие значимость признаков, поступающих для суммирования; d_j — выходной сигнал j-го вычислительного демона.

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

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

Таблица 2.1 — Весовые множители, устанавливающие значимость признаков для объектов распознавания.

Допустим, что на считывающем устройстве пандемониума появляется образ в виде кошки. Вычислительные демоны сформируют следующие признаки: d₁ = 1 (что означает — есть усы), d₂= 1 (есть шерсть), d₃=1 (имеется хвост), d₄= 0 (вес более 50 кг).

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

демон кошки — D₁ = 10*1 + 10*1 + 10*1 + 0*0 = 30;

демон собаки — D₂ = 0*1 + 10*1 + 8*1 + 0*0 = 18;

демон человека — D₃ = 2*1 + 0*1 + 0*1 + 10*0 = 2.

Таким образом, наибольшее число баллов набрала кошка.

Теперь предположим, что на входе появился человек. Вычислительные демоны дадут признаки: d₁ = 0 (что означает — нет усов), d₂ = 0 (нет шерсти), d₃ = 0 (нет хвоста), d₄ = 1 (вес более 50 кг).

Демоны понимания произведут обработку поступивших признаков:

демон кошки — D₁ = 10*0 + 10*0 + 10*0 + 0*1 = 0;

демон собаки — D₂ =0*0 + 10*0 + 8*0 + 0*1 = 0;

демон человека — D₃ = 2*0 + 0*0 + 0*0 + 10*1 = 10.

Вывод очевиден — на входе человек.

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

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

(2.2).

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

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

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

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

Термин «персептрон» был введен в 1950;х гг. Фрэнком Розенблаттом для некоторого класса интеллектуальных систем распознавания образов, способных обучаться на опыте. Первоначально персептрон Розенблатта (рисунок 2.2) содержал узлы трех типов. Сенсорные, или с-узлы, имитировали светочувствительные клетки сетчатки глаза. Они соответствовали демонам изображения, или демонам данных, пандемониума Селфриджа. Обычно предполагается, что с-узлы являются элементами типа «все или ничего», но это не обязательно.

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

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

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

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

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

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

Рисунок 2.3 — Многослойный персептрон Гамбы На рисунке 2.3 приведена схема популярного в свое время многослойного персептрона Гамбы, являющегося развитием изложенного выше однослойного персептрона.

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

2.2.4 Предварительная обработка изображений.

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

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

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

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

Разделение по порогу. Сегментация осуществляется исключительно на основе значения функции зачерненности каждого элемента изображения. Если функция f (х, у) >, где — значение некоторой пороговой величины, то соответствующий элемент изображения классифицируется как компонента распознаваемого образа, в противном случае он относится к фону.

Рисунок 2.4 — Распределение функции зачерненности у = f (х, у) в плоскости х — у (а), в сечении у = 0 (б), распределение ее производной по х (в), модуля производной (г) и особенностей поля производной (д) Рисунок 2.5 — Правило формирования цепного кода На сегментированном таким образом изображении легко выделить контуры распознаваемого образа. Обозначим через S некоторое интересующее нас подмножество элементов изображения, относящееся к компонентам образа, а через S' - дополнение подмножества (фон). Тогда контур будет состоять из элементов подмножества S, которые имеют в качестве соседних элементы подмножества S'. Пользуясь этим правилом, несложно создать алгоритм, выявляющий контурные пикселы.

Обнаружение края. Обычно граница между компонентами образа и фоном характеризуется резким изменением функции зачерненности. Поэтому обнаружить эту границу можно путем дифференцирования функции f (х, y) по координатам, как схематично показано на рис. x.x. Ложные края можно удалить, а утраченные — восстановить, используя априорную информацию об образе.

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

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

Рисунок 2.6 — Распознаваемый образ S и случайные частицы Q₁ и Q₂ до (а) и после (б) применения операции поверхностного разрушения Рисунок 2.7 — Изображение буквы и ее остова С выявленным компонентом образа можно производить операции поверхностного разрушения (сжатия, прореживания) и наращивания (расширения). Эти операции применяют для улучшения качества изображения. Для реализации указанных операций необходимо перемещать некоторый структурирующий элемент по изображению образа. Если структурирующий элемент полностью укладывается в подмножество S, перемещение структурирующего элемента продолжается дальше без модификации изображения. Если же структурирующий элемент не входит в S полностью, то элемент изображения, соответствующий положению опорного пиксела структурирующего элемента, удаляется. На рисунке 2.6 приведен пример этой операции. Структурирующий элемент (см. рисунок 2.6, а) состоит из центрального пиксела, являющегося опорным, и четырех соседних с ним пикселов. На рисунке 2.6, б удаленные после операции поверхностного разрушения пикселы изображены штриховыми линиями.

Операция, обратная поверхностному разрушению, называется наращиванием. Эту операцию можно также трактовать как поверхностное разрушение подмножества S'.

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

Операции разрушения и наращивания можно применять многократно. Таким способом можно добиться очищения изображений — удаления малых случайных частиц (таких как Q₁ и Q₂ на рисунке 2.6, а) и заполнения случайных промежутков.

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

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

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

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

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

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

Рисунок 2.8 — Расположение пикселов при поиске горизонтальных (а) и наклонных (б) отрезков изображения Новый массив опять рассматривается с помощью ячейки 7×7 (рисунок 2.9), которая при определенных условиях указывает на наличие некоторого морфологического признака символа. Таким признаком может быть изменение направления линии; острые, прямые или тупые углы; слияние или пересечение линий. Всего получается 54 различных морфологических признака.

Рисунок 2.9 — Пример заполнения решетки на втором этапе сканирования: Н — наличие горизонтального участка; V — наличие вертикального участка; D и d — наличие наклонных участков Представление символа сводится к перечислению его морфологических признаков с указанием их примерного расположения. Простая программа, составленная на основе статистических данных, собранных на свободно написанных цифрах, позволяет осуществлять довольно надежное распознавание.

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

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

В настоящее время получили распространение две конкурирующие между собой системы распознавания текстовой информации — FineReader (компания «Бит») и CuneiForm (компания «Cognitive Technologies»). Разработчики этих систем тщательно оберегают свои ноу-хау, однако некоторые принципы, используемые этими программами, становятся известными.

2.3.1 Основные принципы работы системы FineReader

Компанией «Бит» была разработана специальная технология распознавания символов, которая получила название фонтанного преобразования (от англ. font — шрифт), а на ее основе — коммерческий продукт — система оптического распознавания FineReader.

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 2.10 — Пример задания конкретизирующих параметров.

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

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

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

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

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

2.3.2 Основные принципы работы системы CuneiForm

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

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

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

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

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

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

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

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

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

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

Как утверждают разработчики, результаты применения CuneiForm 96 показали, что использование самообучающихся алгоритмов позволяет повысить точность распознавания низкокачественных текстов в 4 — 5 раз. Но главное преимущество заключается в том, что самообучающиеся системы обладают гораздо большим потенциалом повышения точности распознавания, открывая новое направление в теории распознавания символьной информации.

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

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

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

Последняя версия CuneiForm 2000 отличается, главным образом, тем, что в ней используется несколько алгоритмов распознавания на основе нейронных сетей. Их применение, по утверждению разработчиков, повысило качество распознавания текстов на 60%.

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

Рисунок 2.11 — Схема распознавания текста с помощью персептрона с предварительным выделением признаков по методу Паркса (слева) и путем непосредственного сканирования изображения (справа).

3. Выбор метода решения

3.1 Выбор общей модели функционирования программного средства.

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

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

3.1.1 Преимущества систем распознавания образов на основе нейросетей

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

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

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