Санкт-Петербургский государственный университет Математико-механический факультет





Скачать 301.99 Kb.
НазваниеСанкт-Петербургский государственный университет Математико-механический факультет
страница6/6
Дата публикации17.07.2013
Размер301.99 Kb.
ТипДипломная работа
100-bal.ru > Информатика > Дипломная работа
1   2   3   4   5   6

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


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

Одной из задач работы было спроектировать расширяемую архитектуру приложения. В связи с этим, прототип построен таким образом, что в дальнейшем можно заменить различные независимые элементы распознавателя, такие как, например, источник изображения (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 называют интерфейс.
1   2   3   4   5   6

Похожие:

Санкт-Петербургский государственный университет Математико-механический факультет iconСанкт-Петербургский Государственный Университет Математико-механический факультет
Сергей Николаевич Кучер, проректор краевого государственного образовательного учреждения дополнительного профессионального образования...
Санкт-Петербургский государственный университет Математико-механический факультет iconСанкт-Петербургский государственный морской технический университет...
Рецензия на книгу: С. А. Остроумов "Биотический механизм самоочищения пресных и морских вод: элементы теории и приложения" (Москва,...
Санкт-Петербургский государственный университет Математико-механический факультет iconМатематико-механический факультет
Государственное образовательное учреждение высшего профессионального образования
Санкт-Петербургский государственный университет Математико-механический факультет icon«Санкт-Петербургский государственный университет» (СПбГУ) Исторический факультет утверждаю
Краснодарский государственный историко-археологический музей-заповедник им. Е. Д. Фелицына
Санкт-Петербургский государственный университет Математико-механический факультет iconОбзор современных систем управления бизнес-процессами
Агапова Татьяна, математико-механический факультет, 2 курс
Санкт-Петербургский государственный университет Математико-механический факультет iconПсихическое здоровье в Германии и России: Клиническая и исследовательская инициатива
Санкт-Петербургский научно-исследовательский Санкт-Петербургский государственный университет
Санкт-Петербургский государственный университет Математико-механический факультет iconМатематико-механический факультет asmpy ассемблер python compiled (*. pyc ) файлов
Государственное образовательное учреждение высшего профессионального образования
Санкт-Петербургский государственный университет Математико-механический факультет iconСанкт-петербургский Государственный университет Восточный факультет Филиппов Е. А. Аннотация
Метадическая разработка интегрированного урока с использованием возможностей интерактивной доски
Санкт-Петербургский государственный университет Математико-механический факультет iconПравительство Российской Федерации Санкт Петербургский государственный...
Муниципальное автономное образовательное учреждение «Средняя общеобразовательная школа №21»
Санкт-Петербургский государственный университет Математико-механический факультет iconСанкт-Петербургский центр научно-технической информации «Прогресс»,...
Особенности размещения государственного заказа в связи с изменениями в федеральном
Санкт-Петербургский государственный университет Математико-механический факультет icon«Санкт-Петербургский государственный университет» (СПбГУ) Исторический факультет утверждаю
Учебно-методический комплекс по дисциплине «Биохимия молока и мяса» составлен на основе
Санкт-Петербургский государственный университет Математико-механический факультет iconПрограмма по формированию навыков безопасного поведения на дорогах...
Санкт-Петербургский Государственный Политехнический Университет, Факультет Иностранных Языков
Санкт-Петербургский государственный университет Математико-механический факультет iconРоссийской Федерации Санкт Петербургский государственный университет Физический факультет
Цель изучения дисциплины: Обучение магистрантов аналитическим методам анализа структуры и эволюции нелинейных полей
Санкт-Петербургский государственный университет Математико-механический факультет iconОсновная образовательная программа (ооп) бакалавриата, реализуемая...
«Санкт-Петербургский государственный университет телекоммуникаций им проф. М. А. Бонч-Бруевича» (СПбгут) по направлению подготовки...
Санкт-Петербургский государственный университет Математико-механический факультет iconОсновная образовательная программа (ооп) бакалавриата, реализуемая...
«Санкт-Петербургский государственный университет телекоммуникаций им проф. М. А. Бонч-Бруевича» (СПбгут) по направлению подготовки...
Санкт-Петербургский государственный университет Математико-механический факультет iconСанкт-Петербургский государственный университет Факультет философии и политологии
Контрольная работа по дисциплине «Культура речи и деловое общение» является допуском студента заочной формы обучения к зачету


Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
100-bal.ru
Поиск