Размещено на http://www.allbest.ru/

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



Введение

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

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

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

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

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

1. Изучить принципы работы OCR-систем;

2. Изучить работу классификаторов символов;

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

4. Реализовать программный модуль.

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

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

Основными источниками информации послужили сайт для Android-разработчиков developers.android.com и книга Хайкина «Нейронные сети: полный курс», а также книги по распознаванию изображений.

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

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

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

Вторая глава является детальным изложением процесса реализации простейшей OCR-системы для Android.

Третья глава рассматривает практическую часть ВКР.

В заключении сделаны основные выводы и результаты по проделанной работе.



Глава 1

1.1 История появления систем OCR

Попытки автоматического распознавания предпринимались, начиная с 30-х годов XX века, однако первый OCR-аппарат от американской компании Intelligent Machines Research Corporation появился только в 1952 году. Первые OCR-аппараты не имели ничего общего с компьютерной техникой. В них свет, отраженный от подсвеченного участка оригинала, проходил через сложную систему зеркал, причем некоторые из них были расположены на вращающихся дисках. В результате из общего потока поочередно выделялись узкие световые пучки, соответствующие небольшим участкам оригинала -- аналогам пикселов электронного изображения. Эти «квазипикселы» поступали на вход фотоэлектронного умножителя -- оптико-электронного преобразователя с большим коэффициентом усиления. Полученные сигналы обрабатывались электронной схемой. В ходе обработки устанавливалось, является подсвеченная точка оригинала белой или черной. На основе полученной информации OCR-аппарат воспроизводил образ подсвеченного знака.

Возможности этих машин были ограничены рядом условий. Для уверенного распознавания требовались исключительно хорошее качество, высокая контрастность и отсутствие каких-либо повреждений оригиналов. Кроме того, распознавать можно было далеко не все надписи, а только набранные определенными шрифтами. Именно с этой целью в 60-х годах были разработаны и стандартизованы специальные шрифты -- OCR-A (в США) и OCR-B (в Европе).

В 70-х годах компания Kurzweil Computer Products предприняла качественно новый шаг в развитии OCR, создав систему, способную учиться распознавать шрифты. Результаты обучения, продолжавшегося обычно несколько часов, записывались на диск, и система приобретала способность распознавать тексты, набранные выученным шрифтом. В то же время в отечественном Научно-исследовательском центре электронной и вычислительной техники (НИЦЭВТ CCCР) группой под руководством Александра Шамиса велись исследования по распознаванию рукопечатных, то есть написанными от руки печатными буквами, надписей. Впоследствии результаты деятельности группы неоднократно находили воплощение в программном коде. Наиболее известной OCR-системой, на практике реализующей методики группы Шамиса, является созданная в России ABBYY FineReader. В 1986 году компания Calera Recognition Systems разработала систему, позволяющую работать с неизвестными ей шрифтами без предварительного многочасового обучения. Это была первая OCR-система, обладавшая искусственным интеллектом. Вместо применявшейся ранее методики посимвольного сравнения с шаблонами она действовала по методу обобщения, ныне более известному как принцип нейронной сети. Разработчики предоставили в распоряжение программы свыше 10 тыс. образцов начертания каждой буквы, и, обобщая их, система получала представление об основных закономерностях начертания знака, что и позволяло обходиться без длительного обучения.

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



1.2 Принцип работы современной OCR-системы

алгоритм классификатор программный модуль

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

Любой высокоуровневый объект может быть представлен как набор объектов более низкого уровня: буквы образуют слова, слова - строки и т.д. Поэтому анализ всегда начинается в направлении сверху вниз. Программа делит страницу на объекты, их, в свою очередь, на объекты низших уровней и т.д., вплоть до символов. Когда символы выделены и распознаны, начинается обратный процесс - сборка объектов высших уровней, которая завершается формированием целой страницы. Такая процедура называется многоуровневым анализом документа, или MDA (Multilevel Document Analysis).

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

Схема алгоритма работы OCR-системы представлена на рис. 1.2.1.

Рис. 1.2.1 Алгоритм работы OCR-системы

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

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

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

Рис. 1.2.2 Объединение нескольких букв в одну компоненту связанности

Рис. 1.2.3 Распадение изображений букв на несвязанные компоненты

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

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

Рис. 1.2.4 Архитектура классификатора

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

Рис. 1.2.5 Простой классификатор

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

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

По результатам опросов, проведенных компанией ABBYY среди пользователей ее продукта FineReader, к наиболее важным аспектам работы систем распознавания пользователи относят следующие:

· точность распознавания - 95%;

· точность сохранения оформления в документах для текстовых процессоров - 89%;

· точность сохранения оформления для последующей электронной публикации (в форматах PDF, HTML) - 87%;

· работа с таблицами и многоколоночными текстами - 87%;

· простота использования - 85%;

· надежность работы - 82%;

· удобный поиск ошибок и сверка с оригиналом - 80%;

· работа с цветом (сохранение цветных картинок, цвета шрифта и фона) - 63%;

· прямой экспорт в другие приложения - 61%;

· скорость - 55%;

· многоязычное распознавание - 25%.

В настоящее время на рынке систем распознавания существует ряд разработок, ориентированных как на различные сферы деятельности пользователя, так и на разные платформы. Отдельная отрасль рынка ориентирована на Apple. Практически все популярные системы распознавания имеют в настоящее время версии для iOS. Абсолютным же лидером продаж OCR-систем в России и одним из лидеров продаж за рубежом в течение нескольких лет остается система ABBYY FineReader.



1.3 Анализ существующих решений

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

1.3.1 Распознавание по шаблонам

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

1.3.2 Структурный подход

Самая продаваемая в мире система OCR - Caere OmniPage Professional использует алгоритм, основанный на нахождении общих специфических особенностей символов. Эта система содержит 100 различных алгоритмов для идентификации 100 различных символов: верхнего и нижнего регистра от «A» до «Z», записи чисел и символов пунктуации. Каждый из этих алгоритмов ищет «особенности» начертаний типа «островов», «полуостровов», точек, прямых оттисков и дуг. Экспертные системы также рассматривают горизонтальные и вертикальные проекции оттисков буквы и обращают внимание на основные особенности в созданных кривых, суммируя в них число темных пикселей. К сожалению, нечеткий текст может стать специфической проблемой для этих структурных алгоритмов, так как отсутствующий пиксель может разбивать длинный штрих или кривую, а дополнительное пятно грязи может закрывать петлю.

1.3.3 Контекстное распознавание

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

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

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

1.4 Задача классификации

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

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

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

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

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

1.4.1 Признаковая классификация

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

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

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

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

где  - i-й признак из j-го эталонного вектора; 

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

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

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



где  - вес i-го признака.

1.5 Понятие нейронной сети

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

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

Рис. 1.6.1 Упрощенная модель нейронной сети

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

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

· нулевой слой состоит из вершин-истоков (входных рецепторов) ;

· ребра (синапсы), входящие в вершины (нейроны) (k+1)-го слоя, выходят из вершин (рецепторов или нейронов) k-го слоя;

· все стоки (выходные нейроны) принадлежат одному и тому же L-му слою.

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

1.5.1 Преимущества нейронных сетей

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

Ниже приведены некоторые преимущества нейронных сетей перед традиционными вычислительными системами.

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

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

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

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

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

1.6 Карты самоорганизации

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

В картах самоорганизации (self-organizing map) нейроны помещаются в узлах решетки, обычно одно- или двухмерной. Карты более высокой размерности также возможны, но используются достаточно редко. Нейроны в ходе конкурентного процесса избирательно настраиваются на различные входные образы (возбудители) или классы входных образов. Таким образом, положения настроенных нейронов (нейронов-победителей) упорядочиваются по отношению друг к другу так, что на решетке создается значимая система координат. Самоорганизующиеся системы характеризуются формированием топографических карт (topographic map) входных образов, в которых пространственное местоположение (т.е. координаты) нейронов решетки является индикатором встроенных статистических признаков, содержащихся во входных примерах. Отсюда берет свое происхождение и само название “самоорганизующиеся карты”.

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

Правилами адаптации, сформулированными на микроуровне одного нейрона.

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

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

Рис 1.7.1 Двумерная решетка нейронов

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

1) Конкуренция. Нейроны в сети конкурируют между собой за право быть активированными. Нейроном-победителем объявляется тот нейрон, для которого евклидово расстояние между вектором весов и вектором входных сигналов оказалось минимальным;

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

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

1.7 Самоорганизующаяся карта Кохонена

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

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



1.8 Операционная система Android

Android - это основанная на Linux платформа для мобильных телефонов, разработанная Open Handset Alliance (OHA), инициированным Google. Она позволяет создавать Java-приложения, управляющие устройством через разработанные Google библиотеки. Также есть возможность писать приложения на C и других языках программирования с помощью Android Native Development Kit, выпущенного 30 апреля 2009 года. Среди основных улучшений появилась поддержка записи и просмотра видео в режиме камеры; поддержка Bluetooth A2DP; возможность автоматически подключаться к Bluetooth-гарнитуре. Первым устройством, работающим под управлением Android, стал разработанный компанией HTC смартфон T-Mobile G1, презентация которого состоялась 23 сентября 2008 года. Вскоре последовали многочисленные анонсы других производителей смартфонов о намерении выпустить устройства с Android.

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

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

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

· Равноправие приложений. Для Android нет разницы между основными приложениями телефона и сторонним программным обеспечением - можно изменить даже программу для набора номера или заставку экрана;

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

Кроме того, Android обладает и другими функциональными возможностями. Так, например, для выполнения приложений используется виртуальная Java-машина Dalvik с низким потреблением памяти. Dalvik позволяет поддерживать одновременную работу нескольких приложений и открывает файлы в специальном формате dex, оптимизированном для мобильных устройств.

В Android реализована поддержка 2D/3D-графики (причем одновременно можно использовать двух- и трехмерную графику), изображений, аудио и видео. Для хранения данных используется популярная легковесная СУБД SQLite. Доступна поддержка GSM, EDGE, 3G, Bluetooth, Wi-Fi, фото- и видеокамеры, GPS, компаса, акселерометра.

В работе платформы применяется также ряд библиотек, отвечающих за шифрование данных, чтение форматов аудио и видео, поддержку 2D и 3D-графики, шрифтов и т.д. В платформе от Google также задействована библиотека LibWebCore (WebKit), которая является движком для web-браузера Android. Стоит отметить, что данный движок используется в популярном браузере Safari от компании Apple.

Одним словом, Android - это программная платформа для мобильных устройств, которая включает в себя операционную систему, программное обеспечение промежуточного слоя (middleware), а также основные пользовательские приложения (e-mail-клиент, календарь, карты, браузер, контакты и другие).Как видно, у платформы от Google есть целый ряд преимуществ. Однако стоить обратить внимание и на недостатки Android.Так, например, многие эксперты отмечают, что платформа базируется на Java, поэтому преимущества и возможности операционной системы Linux на Android используются не в полной мере.

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

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

Так, например, Android уже стоит на ряде моделей Asus EE PC, а также портирован на нетбуки компаний MSI, Dell и Acer. Еще ряд производителей нетбуков заявили о скором выпуске устройств на базе мобильной платформы от Google.Кроме того, появление Google Android заставило многих крупных производителей микроэлектроники начать разработку устройств, которые до этого компании вообще не производили.

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



Глава 2 Java

2.1 Обоснование выбора технологий

Когда операционная система Android была презентована, Java был единственным официально поддерживаемым языком для создания программного обеспечения для Android.

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

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

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

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

В последнее время был внесен ряд усовершенствований, которые несколько увеличили скорость выполнения программ на Java:

· применение технологии трансляции байт-кода в машинный код непосредственно во время работы программы (JIT-технология) с возможностью сохранения версий класса в машинном коде;

· широкое использование платформенно-ориентированного кода (native-кода) в стандартных библиотеках;

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

Язык Java активно используется для создания мобильных приложений под операционную систему Android. При этом программы компилируются в байт-код специального формата, для использования их виртуальной машиной Dalvik. Для такой компиляции используется дополнительный инструмент, а именно Software Development Kit, разработанный компанией Google. И, несмотря на то, что в данный момент разработка под Android ведётся на многих языках, для реализации OCR-системы был выбран язык Java, так как на нём написан Android SDK, упрощающий разработку, и требующиеся библиотеки, о которых будет подробно рассказано в последующих главах.

Разработку приложений можно вести в среде Eclipse, используя при этом плагин - Android Development Tools.

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

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

Android Studio использует быстро развивающуюся систему автоматической сборки проектов Gradle, которая интегрированна в среду. Gradle пытается объединить в себе все плюсы таких систем сборки проектов как Ant, Maven и Ivy. Так как Gradle работает в запущеной JVM, она успешно использует библиотеки задач Ant, средства управления зависимостями Apache Ivy и другие существующие инструменты (TestNG, JUnit, Surefire, Emma). То есть в сборку возможно интегрировать любой инструмент, работающий в JVM. Ко всему прочему, в отличие от других систем сборки, вместо привычного языка разметки XML Gradle использует диалект Groovy, который позволяет создавать циклы, работать с файлами, сетью и многое другое.

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

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

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

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

В настоящий момент данная библиотека не разрабатывается. Последний релиз состоялся в 2007 году.

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

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

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

Encog является одним из передовых фреймворков в области машинного обучения, который поддерживает множество усовершенствованных алгоритмов. Поддерживаются алгоритмы машинного обучения, такие как методы опорных векторов, искусственных нейронных сетей, сетей Байеса, скрытых Марковских моделей и генетические алгоритмы. Большинство обучающих алгоритмов Encog являются многопоточными и хорошо масштабируются для многоядерных систем. Encog может использовать графический процессор для увеличения скорости обработки. Имеется приложение для ознакомления с алгоритмами машинного обучения. Encog в активном развитии начиная с 2008 года. Также принципиальным является то, что данный фреймворк поддерживает Java и может быть использован в приложениях под Android.

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

compile group: 'org.encog', name: 'encog-core', version: '3.2.0'.

2.2 Проектирование системы

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

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

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

2.3 Создание базовой библиотеки для работы с нейронной сетью

Для создания классификатора была выбрана реализация самоорганизующейся карты Кохонена из библиотеки Encog в виде класса org.encog.neural.som.SOM. На её основе был создан класс MultiSom, расширяющий SOM и добавляющий к его функционалу метод matches, принимающий в качестве параметра массив пикселей и возвращающий вектор веса. Это нужно для того, чтобы определить наилучшую единицу соответствия, то есть букву, изображение которой в обучающей выборке максимально совпадает с распознаваемым изображением.

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

Самоорганизующаяся карта состоит из узлов. В каждом узле находится символ. Приложением будут распознаваться латинские символы и цифры, следовательно, количество узлов системе 36, 26 из которых - символы латинского алфавита, и 10 - цифры. Символ представлен объектом класса CharData. Для обучения сети используется класс Engine.

Для хранения эталонных изображений рукописных символов используется класс ImageData. Он позволяет сохранять изображение в памяти и преобразовывать его в одномерный массив пикселей.

...