Дипломная работа Фомина Алексея Дмитриевича 545 группа



Скачать 301.89 Kb.
Дата09.01.2017
Размер301.89 Kb.
Просмотров144
Скачиваний0
ТипДиплом
Санкт-Петербургский государственный университет

Математико-механический факультет

Кафедра системного программирования

Автоматизированная система учета расходования личных средств

Дипломная работа

Фомина Алексея Дмитриевича

545 группа

Научный руководитель ……………. к. ф.-м. н. Д. С. Шалымов

Рецензент ……………. к. ф.-м. н. А. Н. Иванов

«Допустить к защите» ……………. д. ф.-м. н. А. Н. Терехов

Зав. кафедрой

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

2011

Saint-Petersburg State University

Mathematics & Mechanics Faculty

Software Engineering Department

Automated system for analyzing personal funds

Graduate paper by

Alexey Fomin

545 group

Scientific advisor ……………. PhD D. S. Shalimov

Reviewer ……………. PhD А. N. Ivanov

«Approved by» ……………. Professor А. N. Terekhov

Head of Department,

Saint-Petersburg

2011

Оглавление


Введение 4

Постановка задачи 6

Обзор существующих подходов 7

Существующие системы распознавания 8

Сервис MOCRT 9

Google Goggles 10

Алгоритмы распознавания 10

Существующие системы обработки чеков 12

Теоретическая часть 14

Сегментация текста 14

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

Построение вектора признаков 23

Распознавание символа по вектору признаков 26

Практическая часть 32

Архитектура приложения 33

Прототип 36

Заключение 38

Список литературы 40




Введение


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

Для решения задачи распознавания текста потенциально применим рандомизированный алгоритм типа стохастической оптимизации [1]. Этот алгоритм активно разрабатывается на математико-механическом факультете СПбГУ. Алгоритм хорошо себя показал в задаче самообучения, была доказана состоятельность оценок при почти произвольных помехах [2]. Основной целью данной дипломной работы является разработка алгоритма распознавания текста на основе этого метода и реализация прототипа под мобильную платформу.

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

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




Постановка задачи


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

  1. Разработка алгоритма распознавания печатных символов на основе рандомизированного алгоритма типа стохастической оптимизации SPSA (Simultaneous Perturbation Stochastic Approximation) [1]

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

  3. Реализация прототипа распознавателя под мобильную платформу iOS

Обзор существующих подходов


Основная часть данной работы – распознавание текста с изображения. Этой задачей занимаются уже давно, и разработано немало эффективных алгоритмов. Точность распознавания лучших из них превышает 99%1.

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



  • Online

  • Offline

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

Online распознаватель, в отличие от offline, распознает текст в момент его написания. Обычно,online методы применяются для распознавания именно рукописного текста. Такой распознаватель получает дополнительную информацию:



  • Разрывность линий при письме

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

  • Направление ввода (слева направо, справа налево или иначе)

  • Скорость рисования отдельных элементов

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

Существующие системы распознавания


Одним из наиболее известных open-source проектов по распознаванию текста является разработанный компанией HP-Labs Tesseract-OCR [6]. В систему включены многие эвристики для сегментации текста. Непосредственно для распознавания применяется нейронная сеть, которую необходимо обучать для конкретных шрифтов. Tesseract-OCR можно использовать в качестве библиотеки распознавания в собственных приложениях. В частности, в задаче мобильной обработки чеков можно было бы либо распознавать изображение на серверной части, используя непосредственно Tesseract-OCR, либо портировать Tesseract-OCR на мобильную платформу.

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



  • Мобильные программы компании ABBYY [7]

  • Сервис MOCRT [8]

  • Google Goggles [9]

Мобильные программы компании ABBYY

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

Кроме того можно приобрести лицензию на использование движка распознавания ABBYY Mobile OCR Engine и использовать разработанный компанией распознаватель в своих приложениях. В частности можно использовать такой подход в задаче мобильного распознавания чеков. Но это не является однократным приоббретением продукта – для использования движка необходимо регулярно оплачивать лицензию.

Сервис MOCRT


Mobile OCR Translation on-line. Сервис является примером примитивной реализации функционала автоматического перевода печатного текста с использованием мобильного телефона. Сценарий работы следующий:

  • Пользователь отправляет фотографию интересующей его страницы текста веб-сервису;

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

  • Распознанный текст передается сервису переводов translate.google.com;

  • Пользователю отпраляется результат перевода.

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

Google Goggles


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

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


Основные алгоритмы, приеменяемые в распознавании образов и, в частности, текста:

  • Искусственные нейронные сети

  • Метод опорных векторов

  • Скрытые Марковские Модели

  • ...

Искусственная нейронная сеть [10] – группа взаимосвязанных процессов – простых нейронов. Концепция алгоритма заключается в попытке симулирования работы нейронов человеческого мозга. Простой нейрон представляет собой процессор, в который поступают сигналы от некоторых других нейронов, и который также может вырабатывать сигнал. Принято говорить, что нейронные сети не программируют, а обучают. Обучение нейронной сети заключается в установке весов, определяющих связи между нейронами. Часто искуственные нейронные сети применяют в задаче распознавания образов.

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

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

Метод опорных векторов [11]. Рассматривается пространство большей размерности, чем классифицируемые данные. В этом пространстве, ищется гиперплоскость, наиболее явно разделяющая пространство на два кластера. Это определяется «толщиной зазора» данной гиперплоскости – в простейшем случае наименьшим расстоянием от нее до элементов кластеров.

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

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

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

Существующие системы обработки чеков


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

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

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

Теоретическая часть


Распознавание информации с чека включает в себя 3 этапа:

  • Сегментация текста

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

  • Формирование данных


Сегментация текста


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

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

Выделение границ символа из изображения чека делится на четыре этапа:


  1. Выделение изображения непосредственно чека (кадрирование изображения)

  2. Разбиение полученного изображения на строки (горизонтальная сегментация)

  3. Выделение левой и правой части строк (если присутствует явное разделение)

  4. Разбиение участков строки на символы

Выделение изображения непосредственно чека

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





Рис.1 Бинаризация изображения. Слева – исходное изображение, справа – его бинарное представлениеd:\university\diplom\images\check_small.jpg
d:\university\diplom\images\ckeck_bw.bmp

Для выделения фона вводится понятие связности точек:

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

Свойство связности – транзитивное замыкание непосредственной связности.

Связная область с центром в точке А – это множество всех точек, связных с точкой А.d:\university\diplom\images\connected_area_1.bmp
d:\university\diplom\images\connected_area_2.bmp


Рис.2 Связные области. На изображении слева красным выделена точка А. На изображении справа красным выделена область с центром в точке А

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



Рис.3 Удаление фона. Слева на изображении красным цветом выделены области, связные с угловыми точками изображения, Справа приведено изображение после удаления фона.d:\university\diplom\images\ckeck_bw_background.bmp
d:\university\diplom\images\ckeck_bw_background_removed.bmp

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

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

Рис.4 Строка после горизонтальной сегментацииd:\university\diplom\images\one_line_good.bmp

Для последующего разбиения строк на символы используется вертикальная гистограмма6: ее минимумам соответствуют границы между словами и между символами внутри одного слова в зависимости от сохранения гистограммой минимального значения в последующих точках. d:\university\diplom\images\parsed line.bmp



Рис.5 Результат вертикальной сегментации. Сверху – символы левой половины чека. Снизу - правой

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


Распознаватели символов можно разделить на следующие основные группы по типу принимаемых ими данных:

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

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

  • Модельное представление. Оно применяется достаточно редко и в основном в online-распознавателях. Изображение разбивается на некоторые примитивы: например, окружности и отрезки, по взаимному расположению которых распознаватель классифицирует входное изображение.

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

Несмотря на то, что в данной задаче заранее доступны шрифты7, за счет невысокого качества изображения, трудно достичь точности выделения границ символа, достаточной для работы непосредственно с растровыми изображениями. Кроме того, при реализации такого шаблонного распознавателя было обнаружено, что у некоторых символов на кассовом чеке большинство точек совпадают. Так, например, “3” и “9” с достаточной частотой распознавались неправильно, а точность распознавания чисел критична для разрабатываемой системы: ошибка в наименовании товара8 не так страшна, как в итоговой стоимости, которая оказывает существенное влияние на статистику. По этой причине был разработан алгоритм, принимающий во входе вектор признаков изображения.

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


  • Отношение числа точек символа к числу точек в занимаемом им прямоугольнике (степень заполнения области)

  • Отношение числа точек в нижней половине символа к общему числу точек символа

  • Отношение числа точек в левой половине символа к общему числу точек символа

  • Соотношение высоты символа к его ширине

  • Количество замкнутых областей

  • Количество точек пересечений

  • Количество концевых точек

  • Среднеквадратичное расстояние между точками пересечений

  • Среднеквадратичное расстояние между точками пересечений и концевыми точками


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


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

Вычисление количества замкнутых областей


Замкнутой областью будем называть связную область нулевых точек, не содержащую точек, лежащих на границе изображения символа.d:\university\diplom\images\filled_areas.bmp


Рис.6 Замкнутые области изображения

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


Скелетизация изображения


Для исследования точек пересечений изображения строится так называемый каркас изображения. В различных источниках понятие каркаса изображения определяют немного по-разному. Канонична лишь его фундаментальная идея – обнаружение внутри изображения линий, сохраняющих топологическую структуру объекта.d:\university\diplom\images\letter_a_skelet_bad.bmp
d:\university\diplom\images\letter_a_skelet.bmp
d:\university\diplom\images\letter_a.bmp


Рис.7 Скелетизация изображения. Слева направо: исходное изображение, идеальный скелет и альтернативный скелет

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

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

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

Точки скелета, имеющие ровно одного соседа, являются концевыми.

Распознавание символа по вектору признаков


Задача распознавания символа может рассматриваться как задача классификации11.

На входе имеется m-мерный вектор свойств изображения, его необходимо отнести к некоторому классу – символу. Все классы заранее известны:



  • 33 строчные и 33 заглавные буквы русского языка12

  • Латинские символы, не присутствующие в предыдущем наборе символов: d D f F g G h i j J L m n N q Q r R s S t U v V w W z Z

  • Другие символы: . = ≡ *

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

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


Алгоритм распознавания на основе SPSA


SPSA – Simultaneous Perturbation Stochastic Approximation – рандомизированный алгоритм типа стохастической оптимизации. Он активно разрабатывался на математико-механическом факультете СПбГУ [1,2,3,4,5]. Алгоритм хорошо показал себя в задаче самообучения, была теоретически обоснована его состоятельность [2].

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

Введем систему обозначений, аналогичную введенной в [2].

Входной вектор признаков xn ϵ Rm. Оценка векторов центров кластеров – матрица ηn ϵ Rr x m. Строки этой матрицы – векторы центров r кластеров.

В основе рассматриваемого рандомизированного алгоритма - использование случайного пробного возмущения. Δn ϵ Rr – вектор, состоящий из ±1, независимая случайная величина с распределением Бернулли по каждой из координат.

n} {βn} – бесконечно малые последовательности, ряд из которых расходится:









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

Правило итеративного построения приближения центров кластеров:

Здесь – r-мерный вектор, составленный из значений характеристических функций , k = 1, 2,…,r, определяющих принадлежность xn кластеру k. В данной задаче, он состоит из одной единицы на позиции соответствующей кластеру с центром, ближайшим к xn и нулей на остальных позициях.

Y() = Q() + - r-мерные векторы, составленные из измеренных с помехами в соответствующих точках значений функций потерь; - соответствующие вектора из ошибок наблюдений. В данной задаче это квадраты расстояний до центров кластеров.

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

Алгоритм SPSA отличается:


  • устойчивостью к почти произвольным помехам14, что компенсирует погрешность при построении вектора признаков;

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

  • простотой реализации, что особенно актуально в мобильных устройствах.

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

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

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

Практическая часть


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

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


Архитектура приложения



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






  • Image Provider

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

  • Prior Modifier

Первичная обработка изображения. Выполняет бинаризацию изображения, адаптивно выбирая пороговое значение яркости. Удаляет фон изображения.

  • Segmentator

Выполняет разбиение изображения на строки.

  • Data Grabber

Обработчик данных. Объект DataGrabber реализует протокол16 IDataGrabber. В приложении хранится список DataGrabber’ов. Каждому из этих объектов передается список изображений строк. Каждый объект, применяя свои эвристики, распознает входящие строки и извлекает необходимую ему информацию. Таким образом некоторые строки могут распознаваться несколько раз. Это обусловлено тем, что DataGrabber владеет информацией о представлении обрабатываемых им данных, а значит может более точно распознать интересующую его строку, предполагая где изображен текст, а где цифры, а также используя специфичный словарь. В реализованном прототипе список DataGrabber’ов состоит из одного SumGrabber’а, который ищет строку, на которой слева находится поле «итого» или аналогичное ему, а справа число с не более чем двумя знаками после запятой.

  • Character Recognizer и Numeric Recognizer

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

  • Vocabulary Provider

Выдает ближайшее словарное слово и вычисляет Расстояние Левенштейна [16] для определения корректности замены слова словарным. В реализованном прототипе есть один словарь, содержащий слова «итог», «итого» и «сумма». В дальнейшем можно организовать набор словарей, позволяющий различным DataGrabber’ам использовать различные корректировки.

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


Прототип


Прототип был реализован под операционную систему iOS. В качестве среды разработки использовался пре-релиз AppCode[15]. Данная среда разработки предоставляет разработчику мощный синтаксический анализатор и интеллектуальную систему подсказок и рефакторинга. В сравнении с предоставляемой Apple средой XCode, AppCode значительно функциональнее и позволяет больше работы выполнять автоматически, что снижает вероятность возникновения ошибок в коде.

Основной проблемой при реализации прототипа было ограничение по памяти. На iOS отсутствует сборка мусора, и контролировать выделение памяти необходимо вручную. В большинстве случаев применяется отложенное освобождение памяти, но при реализации прототипа пришлось обработать bottle neck’и и заменить отложенное освобождение явным. По показаниям профилятора итоговое приложение занимает около 5 мегабайт оперативной памяти (не включая входное изображение) при лимите на iPhone в 30 мегабайт. Это говорит о допустимости использования алгоритма на данной мобильной платформе. Время обработки изображения чека колеблется в зависимости от качества изображения, но не более 20 секунд. Это время можно считать допустимым для данной задачи. Также было выявлено, что большую часть времени работают первичная обработка изображения и сегментация его на строки, а не основная часть работы – распознаватель. Это позволит при необходимости оптимизировать работу приложения, заменив эти модули.

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

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

В результате эксперимента 5 изображений не были распознаны. Из них 4 из-за некорректной сегментации – не была обнаружена строка с итоговой стоимостью; и в 1 была неправильно распознана цифра. Tesseract-ocr корректно распознал все числа, изображенные на чеках, что свидетельствует о достаточном качестве изображения.

Заключение


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

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

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

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

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

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

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

  • Классификация расходов по группам товаров;

  • Отслеживание изменения цен;

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

  • Анализ популярности товаров

  • Выявление регулярного адаптивного списка покупок

Список литературы


[1] Граничин О.Н., Поляк Б.Т.  Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах // М.: Наука. 2003. 291 с.

[2] Граничин О.Н., Измакова О.А. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения // Автоматика и телемеханика, 2005, № 8, с. 52-63.

[3] Шалымов Д.С. Рандомизированный алгоритм стохастической аппроксимации в задаче распознавания печатных текстов арабского языка // Труды VIII Международной конференции «Идентификация систем и задачи управления» SICPRO ‘09. Москва, 2009 г.

[4] Граничин О.Н., Шалымов Д.С. Решение задачи автоматического распознавания отдельных слов речи при помощи рандомизированного алгоритма стохастической аппроксимации // Нейрокомпьютеры: разработка, применение, 2009, № 3, с. 58-64.

[5] Шалымов Д.С. Математическое обеспечение для разработки и анализа систем распознавания образов, использующих рандомищированные алгоритмы // диссертационная работа, 2009

[6] http://code.google.com/p/tesseract-ocr/

[7] http://www.abbyy.ru/mobile/

[8] http://mocrt.e-ur.asia/up/

[9] http://www.google.com/mobile/goggles/

[10] http://en.wikipedia.org/wiki/Artificial_neural_network

[11] http://en.wikipedia.org/wiki/Support_vector_machine

[12] http://en.wikipedia.org/wiki/Hidden_Markov_model

[13] http://hitfounder.livejournal.com/26404.html

[14] http://marketimho.ru/



[15] http://www.jetbrains.com/objc/

[16] http://en.wikipedia.org/wiki/Levenshtein_distance

[17] http://www.apple.com/iphone/ios4/

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

2 Рукописный ввод в первых карманных компьютерах фирмы Palm http://en.wikipedia.org/wiki/Palm_(PDA)

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

4 Значение точки – цвет ее бинарного представления, 0 или 1.

5 Зависимость количества ненулевых пикселей в строке от ее номера.

6 Зависимость количества ненулевых пикселей в столбце от его номера.

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

8 Кроме того, ошибки в наименовании товара могут быть исправлены применением словаря. Числа же не могут быть откорректированы подобным способом.

9 Буква Ы воспринимается как 2 отдельных символа: “ь” и “I”

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

11 Кластеризация, при которой заранее известно число кластеров

12 Как отмечалось ранее, буква ы рассматривается как пара символов Ь и I

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

14 Почти произвольная помеха – ограниченная (допустима неслучайная) величина

15 Такое изначальное приближение должно сильно не соответствовать реальным центрам кластеров, что не выполняется в реализованном прототипе.

16 Протоколом в языке Objective C называют интерфейс.


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал