Модифицированные методы и алгоритмы распознавание образов при решении проблем "Data mining"

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

государственный комитет связи, информатизации И ТЕЛЕКОММУНИКАЦИОННЫХ ТЕХНОЛОГИЙ

РЕСПУБЛИКИ УЗБЕКИСТАН

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Диссертация на соискание академической степени магистра

Модифицированные методы и алгоритмы распознавание образов при решении проблем «Data mining»

5А330201 - Компьютерные системы и их программное обеспечение

АБДУСАТТАРОВ УМИДЖОН

ИБРО?ИМЖОН Ў?ЛИ

Научный руководитель: д.т.н., академик

Камилов М.М.

Ташкент 2014 г.



Аннотация

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

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

· изучить алгоритмы распознавание текста и собрать необходимый теоретический минимум из существующей литературы;

· изучить алгоритм Виолы-Джонса и собрать необходимый теоретический минимум из существующей литературы;

· выбрать среду разработки и реализовать предложенные методы;

· проанализировать результаты проделанной работы;

· сделать обоснованные варианты и предложения об улучшении метода или работы программы.

Объект и предмет исследования. Объектом исследования является распознавание текста с изображения и лиц с видеопотока, предметом исследования назовем сам метод реализации, предложенный Полом Виолой и Майклом Джонсом.

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

Использованные методы. Для достижения поставленной цели использовались методы Пола Виола и Майкла Джонса, метод метрики, алгоритмы распознавания текстов и лиц.

Краткое содержание использованной литературы. Распознаванием текстов и лиц достаточно широко представлено в работах Шоломов Д.Л., Арлазаров В. В., Постников В. В., Шоломов Д.Л., Питерсон У., Уэлдон Э. и многих других ученых. Показано, что одним из эффективных методов разработки прикладного программного обеспечения для распознавания текстов и лиц являются методы Виола-Джонса и метрики.

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

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

- проведен анализ существующих методов по распознаванию текстов и лиц;

- разработан новый алгоритм на основе метода Виола-Джонса;

- разработан программный продукт в среде (C#) для распознавания текстов с изображений и лиц с видеопотоков.

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



Annotation

Subject topicality. Ability to perceive the outside world in the form of images and text allows a certain authenticity to recognize an infinite number of objects on the basis of acquaintance with a finite number of them, and the objective nature of the main properties of the images and the text allows you to simulate the process of their recognition.

The purpose and objectives of the study. Implementation of OCR, and persons on the selected method, the analysis of possible improvements on the stages of the process. To achieve this goal we had to solve the following tasks:

* OCR algorithms explore and collect the required theoretical minimum of the existing literature;

* explore Viola-Jones algorithm and collect the necessary theoretical minimum of the existing literature;

* choose the programming environment and implement the proposed methods;

* analyze the results of the work done;

* make informed choices and suggestions for improving the method or program.

Object and subject of study. The object of this study is to recognize text from the image and people with video, called himself the subject of research implementation method proposed by Paul Viola and Michael Jones.

Methods and tools for research. To solve the problems using data mining provisions, principles and methods of pattern recognition.

The methods used. To achieve this goal the methods used by Paul Viola and Michael Jones, the metric method, OCR algorithms and individuals.

Summary of literature. OCR, and persons is sufficiently represented in the works Sholomov DL Arlazarov VV, VV Postnikov, Sholomov DL, W. Peterson, E. Weldon and many other scientists. It is shown that one of the effective methods for developing application software for text recognition and those are the methods Viola-Jones and metrics.

Scientific and practical significance. Author developed application software for text recognition with images and those with video, thanks generalization can be used not only as a basis for the further implementation of such software, but also in the billing system.

Scientific novelty of the resulting work is as follows:

- An analysis of existing methods for recognizing texts and persons;

- Developed a new algorithm based on the method of Viola-Jones;

- Developed software environment (C #) for text recognition from images and those with video streams.

The structure of the thesis. The thesis consists of introduction, three chapters, conclusion, references and three software application sections.



Содержание

Введение

1. Анализ методов и моделей интеллектуального анализа данных (Data Mining)

1.1 Анализ задач и моделей интеллектуального анализа данных

1.2 Анализ методов и алгоритмов интеллектуального анализа данных

1.3 Анализ существующих методов и алгоритмов распознавания текста

1.4 Анализ существующих методов и алгоритмов распознавания лица

Выводы по главе I

2. Модификация методов и алгоритмов распознавания текста и лица

2.1 Модификация алгоритма распознавания текста с изображения

2.2 Модификация алгоритма распознавания лица человека с видеопотока

2.3 Корректировка результатов бесконтактного сканирования и фотографий документов

Выводы по главе II

3. Разработка прикладного программного обеспечения распознавания

3.1 Роль и значения программного обеспечения для решения задачи распознавания текстов и лиц

3.2 Назначения, состав и режим работы прикладного программного обеспечения «DPro»

3.3 Описания модуля «Распознавание текстов»

3.4 Описания модуля «Распознавания паспорта»

3.5 Описания модуля «Распознавания лиц»

Выводы по главе III

Заключение

Перечень использованной литературы

Приложение



Введение

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

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

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

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

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

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

Термин Data Mining часто переводится как добыча данных, извлечение информации, раскопка данных, интеллектуальный анализ данных, средства поиска закономерностей, извлечение знаний, анализ шаблонов, "извлечение зерен знаний из гор данных", раскопка знаний в базах данных, информационная проходка данных, "промывание" данных. Понятие "обнаружение знаний в базах данных" (Knowledge Discovery in Databases, KDD) можно считать синонимом Data Mining.

Понятие Data Mining, появившееся в 1978 году, приобрело высокую популярность в современной трактовке примерно с первой половины 1990-х годов. До этого времени обработка и анализ данных осуществлялся в рамках прикладной статистики, при этом в основном решались задачи обработки небольших баз данных [4].

О популярности Data Mining говорит и тот факт, что результат поиска термина "Data Mining" в поисковой системе Google (на январь 2014 года) - более 140 миллионов страниц.

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

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

Как отметил Президент И.А.Каримов «Высокими темпами растут высокотехнологичные и рыночные виды услуг, такие как услуги связи и информатизации - на 24,5 процента, по компьютерному программированию - на 18 процентов»[3].

В Республике Узбекистан также ведутся работы в данном направлении: были приняты Закон Республики Узбекистан: в 2004 г. «Об электронном документообороте» [2], в 2003 г «Об информатизации» [1].

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

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

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

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

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

* изучить алгоритмы распознавание текста и собрать необходимый теоретический минимум из существующей литературы;

* изучить алгоритм Виолы-Джонса и собрать необходимый теоретический минимум из существующей литературы;

* выбрать среду разработки и реализовать предложенные методы;

* проанализировать результаты проделанной работы;

* сделать обоснованные варианты и предложения об улучшении метода или работы программы.

Объект и предмет исследования. Объектом исследования является распознавание текста с изображения и лиц с видеопотока, предметом исследования назовем сам метод реализации, предложенный Полом Виолой и Майклом Джонсом.

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

Использованные методы. Для достижения поставленной цели использовались методы Пола Виола и Майкла Джонса, метод метрики, алгоритмы распознавания текстов и лиц.

Краткое содержание использованной литературы. Распознаванием текстов и лиц достаточно широко представлено в работах Чубукова И. А., Кевин Мерфи, Шоломов Д.Л., Арлазаров В. В., Постников В. В., Шоломов Д.Л., Питерсон У., Уэлдон Э. и многих других ученых. Показано, что одним из эффективных методов разработки прикладного программного обеспечения для распознавания текстов и лиц являются методы Виола-Джонса и метрики.

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

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

- проведен анализ существующих методов по распознаванию текстов и лиц;

- разработан новый алгоритм на основе метода Виола-Джонса;

- разработан программный продукт в среде Visual Studio 2013 (C#) для распознавания текстов и паспортов с изображений и лиц с видеопотоков.

Структура и объем работы. Магистерская диссертация состоит из введения, трех глав, заключения, списка литературы, приложения, 2 таблиц и из 44 изображений.

1. Анализ методов и моделей интеллектуального анализа данных (Data Mining)

1.1 Анализ задач и моделей интеллектуального анализа данных

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

Data Mining (добыча данных, интеллектуальный анализ данных, глубинный анализ данных) -- собирательное название, используемое для обозначения совокупности методов обнаружения в данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности. Термин введён Григорием Пятецким-Шапиро в 1989 году.

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

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

Задача косвенного анализа - создание групп данных или поиск определенных структур или схем в существующем наборе данных, например, определение демографической группы типа «Soccer Mom» (мамы юных футболистов). Каждая перепись населения США подразумевает интеллектуальный анализ данных, так как правительство стремится получить данные о каждом жителе и преобразовать их в информацию, пригодную для дальнейшего практического использования.

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

Задачи, решаемые методами Data Mining, принято разделять на описательные (англ. descriptive) и предсказательные (англ. predictive).

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

К описательным задачам относятся:

· поиск ассоциативных правил или паттернов (образцов);

· группировка объектов, кластерный анализ;

· построение регрессионной модели.

К предсказательным задачам относятся:

· классификация объектов (для заранее заданных классов);

· регрессионный анализ, анализ временных рядов.

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

· имеется достаточно крупная база данных;

· предполагается, что в базе данных находятся некие «скрытые знания».

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

Что означает «скрытые знания»? Это должны быть обязательно знания:

· ранее не известные -- то есть такие знания, которые должны быть новыми (а не подтверждающими какие-то ранее полученные сведения);

· нетривиальные -- то есть такие, которые нельзя просто так увидеть (при непосредственном визуальном анализе данных или при вычислении простых статистических характеристик);

· практически полезные -- то есть такие знания, которые представляют ценность для исследователя или потребителя;

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

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

Интеллектуальный анализ извлекает шаблоны и тренды, существующие в данных. Такие шаблоны и тренды могут быть собраны воедино и определены как модель интеллектуального анализа данных. Модели интеллектуального анализа данных могут применяться к конкретным бизнес-сценариям, например:

* прогнозирование продаж;

* почтовая рассылка определенным клиентам;

* определение продуктов, которые с высокой долей вероятности могут быть проданы вместе;

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

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

1.2 Анализ методов и алгоритмов интеллектуального анализа данных

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

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

Знания, добываемые методами Data mining, принято представлять в виде моделей.



Рис. 1.1 Модели представления знаний Data Mining

Методы построения таких моделей принято относить к области искусственного интеллекта.

Анализ подходов и методов решения задачи.

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

К методам и алгоритмам Data Mining относятся:

1. искусственные нейронные сети;

2. деревья решений, символьные правила;

3. методы ближайшего соседа и k-ближайшего соседа;

4. метод опорных векторов;

5. байесовские сети;

6. линейная регрессия;

7. корреляционно-регрессионный анализ;

8. иерархические методы кластерного анализа;

9. неиерархические методы кластерного анализа, в том числе алгоритмы k-средних и k-медианы;

10. методы поиска ассоциативных правил, в том числе алгоритм Apriori;

11. метод ограниченного перебора;

12. эволюционное программирование и генетические алгоритмы;

13. разнообразные методы визуализации данных и множество других методов.

Большинство аналитических методов, используемые в технологии Data Mining - это известные математические алгоритмы и методы. Новым в их применении является возможность их использования при решении тех или иных конкретных проблем, обусловленная появившимися возможностями технических и программных средств. Следует отметить, что большинство методов Data Mining были разработаны в рамках теории искусственного интеллекта.

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

Свойства методов Data Mining

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

Основные свойства и характеристики методов Data Mining: точность, масштабируемость, интерпретируемость, проверяемость, трудоемкость, гибкость, быстрота и популярность.

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

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



Таблица 1

Сравнительная характеристика методов Data mining

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

Классификация методов

Работа с данными

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

Непосредственное использование данных, или сохранение данных.

В этом случае исходные данные хранятся в явном детализированном виде и непосредственно используются на стадиях прогностического моделирования и/или анализа исключений. Проблема этой группы методов - при их использовании могут возникнуть сложности анализа сверхбольших баз данных (Рис. 1.2).

Рис. 1.2 Методы групп

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

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

Рис. 1.3 Методы групп

Логические методы, или методы логической индукции, включают: нечеткие запросы и анализы; символьные правила; деревья решений; генетические алгоритмы.

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

Методы кросс-табуляции: агенты, байесовские (доверительные) сети, кросс-табличная визуализация.

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

Методы на основе уравнений.

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

Подход к обучению математических моделей

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

В этой классификации различают две группы методов:

· статистические методы, основанные на использовании усредненного накопленного опыта, который отражен в ретроспективных данных;

· кибернетические методы, включающие множество разнородных математических подходов.

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

Статистические методы Data Mining

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

* предварительный анализ природы статистических данных (проверка гипотез стационарности, нормальности, независимости, однородности, оценка вида функции распределения, ее параметров и т.п.);

* выявление связей и закономерностей (линейный и нелинейный регрессионный анализ, корреляционный анализ и др.);

* многомерный статистический анализ (линейный и нелинейный дискриминантный анализ, кластерный анализ, компонентный анализ, факторный анализ и др.);

* динамические модели и прогноз на основе временных рядов.

Арсенал статистических методов Data Mining классифицирован на четыре группы методов (Рис. 1.4):

Рис. 1.4 Методы групп

Кибернетические методы Data Mining

Второе направление Data Mining - это множество подходов, объединенных идеей компьютерной математики и использования теории искусственного интеллекта (Рис. 1.5).

Рис. 1.5 Методы групп

Классификация по задачам

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

Описательные методы

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

Рис. 1.6 Методы групп

Прогнозирующие методы

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

Рис. 1.7 Методы групп

1.3 Анализ существующих методов и алгоритмов распознавания текста

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

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

Для повышения качества распознавания критически важных полей форм применяются различные методы. В частности, используются методы с введением в данные дополнительной избыточной информации. Широко известным примером такого метода из области теории информации являются коды Хемминга [7]. Ряд методов в области распознавания текстов предложен в работе [11].

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

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

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

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

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

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

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

Математическая постановка задачи

Задача распознавания с коррекцией сводится к перебору элементов вектора альтернатив для каждого символа x_i из слова . Для каждого набора , где a_i^ki - k_i-ый элемент вектора , соответствующего i-ому распознаваемому символу, который мы будем называть интерпретацией, производится его преобразование в линейную последовательность, которая подвергается соответствующей проверке

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

где n -- количество символов в слове .

Уже для 2 вариантов для каждого символа слова длиной 15 символов эта формула даёт 32768 вариантов интерпретации, что, при достаточно сложной функции проверки T, может приводить к длительным задержкам при распознавании. Но, как показывает опыт практического применения, большая часть слов распознается при проверке одного варианта для каждого символа, т.е. для слова длиной символов нужно рассмотреть всего лишь порядка 15 вариантов распознавания.

Алгоритм корректировки

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

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

1.4 Анализ существующих методов и алгоритмов распознавания лица

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

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

Решению такой задачи мешают некоторые факторы:

· Разный размер искомых объектов, а также масштаб изображений;

· Определяемый объект может находиться где угодно на изображении;

· Совершенно другой объект может быть похож на искомый;

· Предмет, который мы воспринимаем как что-то отдельное, на изображении никак не выделен, и находится на фоне других предметов, сливается с ними;

· Старые и необработанные фотографии -- на них всегда присутствуют «отвлекающие» систему царапины, помехи, искажения, на сканируемых фото не редко появляются разного рода муары;

· Не стоит забывать, что во многих алгоритмах распознавания (также и в Виола-Джонс) работа идет с 2D-пространстве непосредственно. Поэтому поворот искомого объекта и изменение угла обзора относительно заданных координатных осей проекции влияют на его проекцию в 2D. Один и тот же объект может давать совершенно разную картинку, в зависимости от поворота или расстояния до него. Искомое лицо может быть повернуто в плоскости изображения. Даже относительно небольшое изменение ориентации лица относительно камеры влечет за собой серьезное изменение изображения лица и о распознании мимики данного лица уже и речи быть не может;

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

· Расовая принадлежность людей: цвет кожи, расположение и размеры отдельных распознаваемых признаков;

· Сильное изменение выражения лица. Например, чересчур показное действо может сильно оказать влияние на правильное распознавание определенной эмоции;

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

· Часть лица вообще может быть невидима или обрезана;

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

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

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

· необходима универсальная коллекция тестовых данных;

· должны присутствовать одинаковые наборы данных;

· необходимы вычислительная мощность -- ресурсы уровня одной лаборатории для этого малы;

· высокая трудоемкость исследования данных алгоритмов;

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

Алгоритм Виолы--Джонса для распознавания лиц

Алгоритм Виолы--Джонса (англ. Viola-Jones object detection) -- алгоритм, позволяющий обнаруживать объекты на изображениях в реальном времени. Предложен в 2001 году Пол Виола (Paul Viola) и Майкл Джонс (Michael Jones). Хотя алгоритм может распознавать различные классы изображений, основной задачей при его создании было обнаружение лиц. Существует множество реализаций, в том числе в составе библиотеки компьютерного зрения OpenCV (функция cvHaarDetectObjects()).

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

Общая схема метода Виолы-Джонса

Алгоритм распознавания по методу Виолы-Джонса основан на "суммировании" пикселов (с определенными весовыми коэффициентами) под скользящим [по растру] окном. Распознавание в этом методе осуществляется по "прецедентам". C помощью "обучающей выборки" строится набор "сильных классификаторов", каждый из которых для квадратного окна говорит: "предположительно, в окне - лицо", или -"определенно, не лицо". Таким образом, для того, чтобы алгоритм признал картинку в окне за лицо, необходимо, чтобы все "сильные классификаторы" (stages) ответили: "да, лицо предположительно есть". Если хотя бы один из них отверг окно (сказал, что "лица определенно нет"), то алгоритм сразу же отвергает данное окно, другие "сильные классификаторы" не использует, и переходит к следующему окну.

Описание метода Viola Jones

Основные принципы, на которых основан метод, таковы:

· используются изображения в интегральном представлении, что позволяет вычислять быстро необходимые объекты;

· используются признаки Хаара, с помощью которых происходит поиск нужного объекта (в данном контексте, лица и его черт);

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

· все признаки поступают на вход классификатора, который даёт результат «верно» либо «ложь»;

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

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

Принцип сканирующего окна

В общем виде, задача обнаружения лица и черт лица человека на цифровом изображении выглядит именно так:

· Имеется изображение, на котором есть искомые объекты. Оно представлено двумерной матрицей пикселей размером w*h, в которой каждый пиксель имеет значение:

· от 0 до 255, если это черно-белое изображение;

· от 0 до 255³, если это цветное изображение (компоненты R, G, B).

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

rectangle_i = {x,y,w,h,a}, (1.1)

где x, y - координаты центра i-го прямоугольника, w - ширина, h - высота, a - угол наклона прямоугольника к вертикальной оси изображения.

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

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

Интегральное представление изображений

Для того, чтобы производить какие-либо действия с данными, используется интегральное представление изображений [3] в методе Виолы-Джонса. Такое представление используется часто и в других методах, к примеру, в вейвлет-преобразованиях, SURF и многих других разобранных алгоритмах. Интегральное представление позволяет быстро рассчитывать суммарную яркость произвольного прямоугольника на данном изображении, причем какой бы прямоугольник не был, время расчета неизменно.

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

(1.2)

где I(i,j) -- яркость пикселя исходного изображения.

Каждый элемент матрицы L[x,y] представляет собой сумму пикселей в прямоугольнике от (0,0) до (x,y), т.е. значение каждого пикселя (x,y) равно сумме значений всех пикселов левее и выше данного пикселя (x,y). Расчет матрицы занимает линейное время, пропорциональное числу пикселей в изображении, поэтому интегральное изображение просчитывается за один проход.

Расчет матрицы возможен по формуле (1.3):

L(x,y) = I(x,y) - L(x-1,y-1) + L(x,y-1) + L(x-1,y) (1.3)

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

Пусть в прямоугольнике ABCD есть интересующий нас объект D (Рис. 1.8):

Рис. 1.8 Прямоугольник ABCD

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

S(ABCD) = L(A) + L(С) -- L(B) -- L(D) (1.4)

Признаки Хаара

Признак -- отображение f: X => D_f, где D_f -- множество допустимых значений признака. Если заданы признаки f₁,…,f_n, то вектор признаков x = (f₁(x),…,f_n(x)) называется признаковым описанием объекта x ? X. Признаковые описания допустимо отождествлять с самими объектами. При этом множество X = D_f1* …* D_fn называют признаковым пространством [1].

Признаки делятся на следующие типы в зависимости от множества D_f:

· бинарный признак, D_f = {0,1};

· номинальный признак: D_f -- конечное множество;

· порядковый признак: D_f -- конечное упорядоченное множество;

· количественный признак: D_f -- множество действительных чисел.

Естественно, бывают прикладные задачи с разнотипными признаками, для их решения подходят далеко не все методы.

В стандартном методе Виолы-Джонса используются прямоугольные признаки, изображенные на рисунке ниже, они называются примитивами Хаара (Рис. 1.9):



Рис. 1.9 Примитивы Хаара

В расширенном методе Виолы - Джонса, использующемся в библиотеке OpenCV используются дополнительные признаки:

Рис. 1.10 Дополнительные признаки Хаара

Вычисляемым значением такого признака будет

F = X-Y, (1.5)

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

Признаки Хаара дают точечное значение перепада яркости по оси X и Y соответственно.

Сканирование окна

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

· есть исследуемое изображение, выбрано окно сканирования, выбраны используемые признаки;

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

· при сканировании изображения в каждом окне вычисляется приблизительно 200 000 вариантов расположения признаков, за счет изменения масштаба признаков и их положения в окне сканирования;

· сканирование производится последовательно для различных масштабов;

· масштабируется не само изображение, а сканирующее окно (изменяется размер ячейки);

· все найденные признаки попадают к классификатору, который «выносит вердикт».

...