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

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

Санкт-Петербургскийгосударственныйуниверситет

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

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

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

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

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……………. PhDD. S. Shalimov

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

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

Head of Department,

Saint-Petersburg

2011

Оглавление

Введение. 3

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

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

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

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

Сервис MOCRT. 3

GoogleGoggles. 3

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

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

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

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

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

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

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

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

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

Прототип. 3

Заключение. 3

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

· Online

· Offline

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

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

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

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

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

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

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

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

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

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

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

· Сервис MOCRT [8]

· Google Goggles [9]

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

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

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

Сервис MOCRT

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

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

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

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

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

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

GoogleGoggles

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

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

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

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

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

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

· ...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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