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

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

Используемая в алгоритме модель машинного обучения

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

«Машинное обучение -- это наука, изучающая компьютерные алгоритмы, автоматически улучшающиеся во время работы» (Michel, 1996)

Ниже показан процесс обучения машины (Рис 1.11):



Рис. 1.11 Обучение машины

Данный процесс входит в концепцию и технологию под названием Data mining (извлечение информации и интеллектуальный анализ данных), куда входят помимо Машинного обучения такие дисциплины, как Теория баз данных, Искусственный интеллект, Алгоритмизация, Распознавание образов и прочие.

Машинное обучение в методе Виолы-Джонса решает такую задачу как классификация.

Обучение классификатора в методе Виолы-Джонса

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

Классифицировать объект -- значит, указать номер (или наименование класса), к которому относится данный объект.

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

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

Обучающая выборка - конечное число данных.

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

Постановка классификации выглядит следующим образом:

Есть X - множество, в котором хранится описание объектов, Y - конечное множество номеров, принадлежащих классам. Между ними есть зависимость - отображение Y*: X => Y. Обучающая выборка представлена X_m = {(x₁,y₁), …, (x_m,y_m)}. Конструируется функция f от вектора признаков X, которая выдает ответ для любого возможного наблюдения X и способна классифицировать объект x?X. Данное простое правило должно хорошо работать и на новых данных.

Принципы решающего дерева в разрабатываемом алгоритме

Дерево принятия решений -- это дерево, в листьях которого стоят значения целевой функции, а в остальных узлах -- условия перехода (к примеру, на Лице есть Улыбка), определяющие по какому из ребер идти. Если для данного наблюдения условие равно истине то осуществляется переход по левому ребру, если же ложь -- по правому [4]. Для примера, дерево представлено на следующем рисунке (Рис 1.12):



Рис. 1.12 Дерево принятия решений

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

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

1. Изучены и проанализированы виды и методы групп интеллектуального анализа данных.

2. Изучены и проанализированы существующие методы распознавания текстов и лиц.

3. Исследованы и проанализированы использованные методы в существующих алгоритмах.

4. Изучена и приведена общая постановки задачи распознавания текстов и лиц.

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

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

Распознавание образов или теория распознавания образов, это раздел информатики и смежных дисциплин, развивающий основы и методы классификации и идентификации предметов, явлений, процессов, сигналов, ситуаций и т. п. объектов, которые характеризуются конечным набором некоторых свойств и признаков. Данное определение нам дает Wikipedia[12].

Также она утверждает, что можно выделить два основных направления

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

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

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

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

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

· Сравнение с заранее подготовленным шаблоном;

· Распознавание с использованием критериев, распознаваемого объекта;

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

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

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

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

Рис. 2.1 Выявления распознавания текста

Данное изображение обрабатывается двумя фильтрами: Медианным и монохромом (Приложение). В приложении прикладного программного обеспечения использовалась измененная версия медианного фильтра с увеличением значения компоненты красного цвета.

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

Сегментация

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

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

Рис. 2.2 Выявление распознавания текста

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

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

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

Метрика Хэмминга - метрика, которая показывает, как сильно объекты не похожи между собой.

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

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

Но как показала практика, подсчет одной лишь метрики не дает положительного результата, так многие буквы похожи между собой. Например «j» «i», что приводит к ошибочному распознаванию.

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

Экспериментом было выяснено, что такие буквы как «H» «I» «i» «O» «o» «X» «x» «l» обладают суперсимметрией (полностью совпадают со своими отражениями и значимые пиксели распределены равномерно по всему изображению), поэтому они были вынесены в отдельный класс, что сокращает перебор всех метрик примерно в 6 раз. Аналогичные действия были проведены в отношении других букв. В среднем уменьшение перебора достигает примерно 3 раза.

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

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

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

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

Предлагаемый ниже метод предполагает возможное избавление от:

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

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

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



Рис. 2.3 Этапы расспознавания лица

Предварительная обработка изображения.

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

Изображение в градациях серого

Для начала нужно перевести изображение в градации серого (Рис. 2.4). Для этого удобно представить изображение в цветовой модели YUV. Для этого выполняется конверсия:



Рис. 2.4 Конвертация цветного изображения в градациях серого

*Y = 0.299 * R + 0.587 * G + 0.114 * B;

*U = -0.14713 * R - 0.28886 * G + 0.436 * B;

*V = 0.615 * R - 0.51499 * G - 0.10001 * B; (2.1)

где R, G и B - это интенсивности заданных цветов, если совсем точно, то это матрицы, описывающие компоненты модели (R,G,B). Y в формуле - это яркостная составляющая, а U и V -- цветоразностные составляющие, так называемые сигналы цветности (эти три параметра тоже представлены матрицами, описывающими компоненты модели (Y,U,V)). Присутствующие в формуле коэффициенты перевода постоянны и определяются особенностями человеческого восприятия. Для полутонового изображения важно только значение первой составляющей.

Оператор Собеля

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



Таблица 2

Маски, используемые оператором Собеля.

- 1	-2	-1		-1	0	1
0	0	0		-2	0	2
1	2	1		-1	0	1

По ним получаем составляющие градиента G_x и G_y:

G_x = (z₇ + 2z₈ + z₉ ) - (z₁ + 2z₂ + z₃ )

G_y = (z₃ + 2z₆ + z₉ ) - (z₁ + 2z₄ + z₇ ) (2.2)

Для вычисления величины градиента эти составляющие необходимо использовать совместно:

или (2.3)

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



Рис. 2.5 Перевод изображения в граничные контуры

Пороговая классификация

Далее, то же полутоновое изображение подвергается пороговой классификации, или выбору порога по яркости. Смысл такого порога заключается в том, чтобы отделить искомый светлый объект и темный фон, где объект -- это совокупность тех пикселей, яркость которых превышает порог (I>T), а фон -- совокупность остальных пикселей, яркость которых ниже порога (I<T). Примерный алгоритм работы с глобальным порогом в автоматическом режиме выглядит так:

Рис. 2.6 Изображение подвергнутое пороговой классификации

· Выбирается начальная оценка порога Т - это может быть средний уровень яркости изображения (полусумма минимальной и максимальной яркости, min+max/2) или любой другой критерий порога;

· Производится некая сегментация изображения с помощью порога Т -- в результате образуются две группы пикселей: G₁, состоящая из пикселей с яркостью больше T, и G₂, состоящая из пикселей с яркостью меньше или равной T;

· Вычисляются средние значения м₁ и м₂ яркостей пикселей по областям G₁ и G₂;

· Вычисляется новое значение порога T = 0.5 * (м₁ + м₂);

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

Бинаризация методом Отсу

Оператор Собеля не может этого сделать, так как дает очень много шумов и помех, поэтому полутоновое изображение необходимо бинаризировать. Значения яркостей пикселей изображения можно рассматривать как случайные величины, а их гистограмму - как оценку плотности распределения вероятностей. Если плотности распределения вероятностей известны, то можно определить оптимальный (в смысле минимума ошибки) порог для сегментации изображения на два класса c0 и c1 (объекты и фон). Суть метода Отсу заключается в том, чтобы выставить порог между классами таким образом, чтобы каждый из них был как можно более «плотным». Если выражаться математическим языком, то это сводится к минимизации внутриклассовой дисперсии, которая определяется как взвешенная сумма дисперсий двух классов (т.е. это сумма отклонений от математических ожиданий данных классов):

у_w² = w₁ * у₁² + w₂ * у₂² (2.4)

где у_w - внутриклассовая дисперсия, у₁ и у₂ - дисперсии, а w₁ и w₂ -- вероятности первого и второго классов соответственно.

Общая схема быстрого алгоритма такова:

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

· Начиная с порога t = 1, проходим через всю гистограмму, на каждом шаге пересчитывая дисперсию у_b(t). Если на каком-то из шагов дисперсия оказалась больше максимума, то дисперсия обновляется и T = t.

· Искомый порог равен T. В более точной реализации есть параметры, которые позволяют убыстрить алгоритм, к примеру, проход через гистограмму делается не от 1 до 254, а от min до (max -1) яркости. «Классическая» бинаризация показана на рисунке 2.7.

Рис. 2.7 Классическая бинаризация изображения

Детектор границ Канни

Итак, исходя из предыдущих шагов обработки изображения, получены края изображения и разбиение порогом в соответствии со значениями яркости. Теперь, чтобы закрепить результат, необходимо применить детектор границ Канни (Canny) для нахождения и окончательного связывания краёв объектов на изображении в контуры.

С помощью алгоритма Канни решаются такие задачи:

· Подавление «ложных» максимумов. Только некоторые из максимумов отмечаются как границы;

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

· Подавление всех неоднозначных краёв, не принадлежащих каким-либо границам областей. Связывание краёв в контуры. После подавления локальных неопределенностей, края становятся более точными и тонкими. Таким образом, получается двоичное изображение, содержащее границы (так называемые «тонкие края»).

Рис. 2.8 Двоичное изображение

Выделение границ Канни использует два порога фильтрации:

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

· если ниже - пиксель подавляется;

· точки со значением, попадающим в диапазон между порогами, принимают фиксированное среднее значение;

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

Причесывание изображения

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

Рис. 2.9 Морфологическая операция дилатации - расширения

Дополнительные примитивы Хаара

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

Рис. 2.10 Признаки Хаар.

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



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

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

Дано:

1. снимок прямоугольного документа с искажениями

2. контуры документа на снимке

Задача: привести документ к исходной форме кратчайшим путем

Входные условия:

1. пропорции исходного документа нам точно не известны

2. расстояние до плоскости, на которой лежит документ нам не известно

3. референсных объектов, на которые можно ориентироваться (например, правильный квадрат, попавший в объектив) на снимке нет

Решение:

Итак, чтобы решить задачу в целом, предлагаем разбить её на две отдельные части:

1. Нахождение, собственно, искаженного контура документа на отсканированном изображении.

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

Можно, конечно, было попытаться изобрести велосипед, и некоторым это до сих пор удается, но мы пошли более легким путем и использовали инструментарий OpenCV. Работаем мы по большей части в среде.NET, через C# Wrapper OpenCVSharp. Также OpenCVSharp доступен в виде Nuget-пакета в среде Visual Studio. «Вот это всё» и будем использовать.

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

Рис. 2.11 Исправлению перспективного изображения

Для того чтобы найти контур на представленном изображении, необходимо избавиться от мелких деталей, которые могут мешать. Это можно сделать, применив «заклинание размытия» по Гауссу малой мощности, предварительно сконвертировав изображение в оттенки серого:

imgSource.CvtColor(imgGrayscale, ColorConversion.BgrToGray);

imgSource.Smooth(imgSource, SmoothType.Gaussian, 15);

Вот, что получилось в результате применения вышеописанной цепочки:



Рис. 2.12 Предварительная конвертация изображения в оттенки серого

Далее необходимо сделать изображение черно-белым:

imgSource.Threshold(imgSource, 0, 255, ThresholdType.Binary | ThresholdType.Otsu);

Рис. 2.13 Черно белое изображение

На полученном изображении легко найти контур документа. Будем искать максимальный внешний контур. В OpenCVSharp есть замечательный класс CvContourScanner, который может перечислять все найденные контуры изображения. С использованием Linq можно эти контуры отсортировать по площади и взять первый, который и будет самым максимальным.

using (var storage = new CvMemStorage())

using (var scanner = new CvContourScanner(image, _storage, CvContour.SizeOf, ContourRetrieval.External, ContourChain.ApproxSimple))

{

var largestContour = scanner.OrderBy(contour => Math.Abs(contour.ContourArea())).FirstOrDefault();

}

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

Рис. 2.14 Результат распознавания контура

Нашли контур. Однако он мало что может показать - необходимо знать точно координаты всех угловых точек - точек пересечения сторон документа. Очевидно, что для нахождения координат этих точек желательно описать стороны найденного контура уравнениями прямой линии. В библиотеке OpenCV есть инструмент, использующий преобразование Хара. «Кастуем» этот метод на изображение, полученное на предыдущем шаге:

var lineSegments = imgSource.HoughLines2(storage, HoughLinesMethod.Probabilistic, 1, Math.PI / 180.0, 70, 100, 1).ToArray<CvLineSegmentPoint>();

Но этот метод не вернет нам 4 линии, которые мы бы ожидали получить. Их будет 100, а может быть 200, а может вообще не быть. Дело в том, что данный метод ищет все участки, которые были приняты за линии, и удовлетворяющие входным параметрам. Тем не менее, с этими данными уже можно что-то делать, например, разложить их по кучкам: вертикальные отдельно, горизонтальные отдельно:

var verticalSegments = segments.Where(s => Math.Abs(s.P1.X - s.P2.X) < Math.Abs(s.P1.Y - s.P2.Y)).ToArray(); var horizontalSegments = segments.Where(s => Math.Abs(s.P1.X - s.P2.X) >= Math.Abs(s.P1.Y - s.P2.Y)).ToArray();

Отрезки линий, которые «динамичнее» изменяются по вертикали - это вертикальные; по горизонтали - горизонтальные. Стало намного проще, можно даже нарисовать, что получилось:



Рис. 2.15 Результат

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

Рис. 2.16 Результат

Осталось теперь отсортировать все найденные точки по часовой стрелке относительно центра масс этих точек:

(2

- среднее арифметическое по каждой из координат). После этого из отсортированного массива создаем контур и аппроксимируем его средствами OpenCVSharp:

contour = contour.ApproxPoly(CvContour.SizeOf, storage, ApproxPolyMethod.DP, contour.ArcLength() * 0.02, true);

Мы, наконец-то получили искомые точки искаженного контура:

Рис. 2.17 Результат

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

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

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

Рис. 2.18 Результат

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



Рис. 2.19 Результат

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

Рис. 2.20 Результат

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

(2.5)

где:

deltaX, deltaY - это отклонения центра масс от точки пересечения диагоналей, соответственно;

targetWidth, targetHeight - размеры результирующего контура;

topWidth, bottomWidth, leftHeight, rightHeight - размеры искаженного контура.

А вот результат применения этой формулы:

Рис. 2.21 Результат

Для сравнения приведем пропорции исходного документа, отсканированного без искажений:

Рис. 2.22 Результат

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

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



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

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

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

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

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

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

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

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

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

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

3.2 Назначения, состав и режим работы ППО «DPro»

Целью разработанного прикладного программного обеспечения является распознавание текстов с изображений и лиц (образов) с видеопотоков.

Для разработки данного программного обеспечения выбран алгоритмический язык программирования C#.

Разработанное программное обеспечение состоит из 9 компонентов, все из которых по выполняемым функциям объединены в три модуля.



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

Рис. 3.1 Общая структура программы

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

Рис. 3.2 Окно запуска программы

Потом в трейбаре появляется иконка. Здесь мы можем запустить один из трех модулей («Распознавание текстов», «Распознавания паспорта» и «Распознавание лиц»).

Рис. 3.3 Выбор модулей программы из трейбара

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

Модуль «Распознавание текстов» предназначен для распознавания текстов с изображений. Модуль работает в двойном режиме: автоматический и ручной режим. Автоматический режим запускается автоматически после загрузки изображения.

Рис 3.4 Загрузка изображения в программу

Если пользователь хочет изменить язык распознавания, но не хочет заново загрузить изображения, чтобы распознавать его, то пользователь должен просто нажать на кнопку «Распознать» на верхнем правом углу. Это второй, ручной режим работы программы.

После распознавания откроется второй экран с результатом:

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

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

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

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



Рис. 3.6 Главное окно модуля «Распознавания паспорта»

Чтобы отсканировать паспорт и получить изображения, мы должны нажать на кнопку «Сканировать» в верхнем левом углу, чтобы загрузить изображение паспорта с жесткого диска мы должны нажать на кнопку «Загрузить» в верхнем левом углу. После сканирования (загрузки) паспорта программа распознает его и выводит на экран результат:

Рис. 3.7 Результат модуля «Распознавания паспорта»

На качество результата влияет качество и расположение изображения.

Этот модуль можно использовать в биллинговых системах или учете клиентов компании.

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

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

Рис. 3.8 Главное окно модуля «Распознавания лиц»

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



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

Рис. 3.9 Окно распознавания модуля «Распознавания лиц»

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

Рис. 3.10 Распознавание и идентификация лиц в реальном времени

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

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

1. Рассмотрен процесс работы программного обеспечения;

2. Получены ожидаемые результаты;

3. Выполнены процессы распознавания текста из изображения, распознавание паспорта из изображения и распознавание лица из видеопотока.



Заключение

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

Полученные результаты данной работы:

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

* изучен алгоритм Виолы-Джонса;

* выбрана среда разработки и реализации метода разработки;

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

Разработан программный комплекс для распознавания текстов, паспортов и лиц.



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

I. Законы Республики Узбекистан

1. Закон Республики Узбекистан «Об информатизации»// 11декабря 2003 года.

2. Закон Республики Узбекистан № 611-II от 29.04.2004 «Об электронном документообороте».

II. Книга Президента Республики Узбекистан Каримова И.А.

3. Каримов И.А. По пути преодоления последствий мирового кризиса, модернизации страны и достижения уровня развитых государств Ислам Абдуганиевич Каримов. Ред. Х. Кутлуков,// Ташкент: Узбекистан, 2010. 248 с.

III. Литературы

4. Чубукова И. А. Курс лекций по Data Mining. М., 2008. 7 с.

5. Шоломов Д.Л. Синтаксические методы контекстной обработки в задачах распознавания текста. М., 2007.

6. Арлазаров В. В., Постников В. В., Шоломов Д.Л. Cognitive Forms -- система массового ввода структурированных документов. //"Управление информационными потоками" Сборник трудов Института системного анализа РАН./ М., УРСС, 2011 г.

7. Kevin P. Murphy. “Machine learning: a probabilistic perspective”. The Mit Press, August 24, 2012. p 3.

8. Christopher M. Bishop. “Pattern recognition and machine learning”. Springer, October 1, 2010. p 103, p 142.

9. Арлазаров В.В. Структурирование визуальных представлений информационной среды и методы определения надежности распознавания. М., 2010. 159 с, 168 с.

10. Горелик А. Л., Скрипкин В. А. Методы распознавания. 4-е изд. М.: Высшая школа, 2010. 262 с.

11. Фомин Я. А. Распознавание образов: теория и применения. 2-е изд. М.: ФАЗИС, 2012. 429 с.

IV. Интернет сайты

12. http://ru.wikipedia.org/wiki/Теория_распознавания_образов - Сайт Wikipedia, Теория распознавания образов.

13. http://en.wikipedia.org/wiki/Pattern_recognition.

14. http://www.fidis.net/resources/deliverables/hightechid/int-d37001/doc/.

15. http://www.facerecognition.it/index.asp.

16. http://en.wikipedia.org/wiki/Template_matching.

17. http://en.wikipedia.org/wiki/Convolution.

18. http://en.wikipedia.org/wiki/Edge_detection.

19. http://en.wikipedia.org/wiki/Sum_of_absolute_differences.

20. http://rkb.home.cern.ch/rkb/AN16pp/node169.html#168.

21. http://en.wikipedia.org/wiki/Euclidean_distance.

22. http://en.wikipedia.org/wiki/Cross-correlation.

23. http://en.wikipedia.org/wiki/Linear_subspace.

24. http://open-cv.com.

25. http://mgu-cv.com.



Приложение

Программная реализация распознавание текста, паспорта и лица человека.

а) Реализация «Медианного фильтра».

public static void Median(ref Bitmap image)

{

var arrR = new int[8];

var arrG = new int[8];

var arrB = new int[8];

var outImage = new Bitmap(image);

for (int i = 1; i < image.Width - 1; i++)

for (int j = 1; j < image.Height - 1; j++)

{

for (int i1 = 0; i1 < 2; i1++)

for (int j1 = 0; j1 < 2; j1++)

{

var p = image.GetPixel(i + i1 - 1, j + j1 - 1);

arrR[i1 * 3 + j1] = ((p.R + p.G + p.B) / 3) & 0xff;

arrG[i1 * 3 + j1] = ((p.R + p.G + p.B) / 3) >> 8 & 0xff;

arrB[i1 * 3 + j1] = ((p.R + p.G + p.B) / 3) >> 16 & 0xff;

}

Array.Sort(arrR);

Array.Sort(arrG);

Array.Sort(arrB);

outImage.SetPixel(i, j, Color.FromArgb(arrR[3], arrG[4], arrB[5]));

}

image = outImage;

}

б) Реализация «Монохромного фильтра».

public static void Monochrome(ref Bitmap image, int level)

{

for (int j = 0; j < image.Height; j++)

{

for (int i = 0; i < image.Width; i++)

{

var color = image.GetPixel(i, j);

int sr = (color.R + color.G + color.B) / 3;

image.SetPixel(i, j, (sr < level ? Color.Black: Color.White));

}

}

}

в) Распознавание текста.

public static class RecognizeHelper

{

public static string ReadTextFromImage(string ImagePath, MODI.MiLANGUAGES language)

{

try

{

MODI.Document ModiObj = new MODI.Document();

ModiObj.Create(ImagePath);

ModiObj.OCR(language, true, true);

MODI.Image ModiImageObj = (MODI.Image)ModiObj.Images[0];

string text = ModiImageObj.Layout.Text;

ModiObj.Close();

return text;

}

catch (Exception ex)

{

throw new Exception(ex.Message);

}

}

}

public partial class RecognizeForm: WaitForm

{

string filePath = string.Empty, rText = string.Empty;

bool isClosed = false;

MODI.MiLANGUAGES language = MODI.MiLANGUAGES.miLANG_ENGLISH;

public RecognizeForm(string filePath, MODI.MiLANGUAGES language)

{

InitializeComponent();

this.progressPanel1.AutoHeight = true;

this.filePath = filePath;

this.language = language;

}

public string RecognizedText

{

get { return rText; }

}

public bool IsClosed

{ get { return isClosed; } }

#region Overrides

public override void SetCaption(string caption)

{

base.SetCaption(caption);

this.progressPanel1.Caption = caption;

}

public override void SetDescription(string description)

{

base.SetDescription(description);

this.progressPanel1.Description = description;

}

public override void ProcessCommand(Enum cmd, object arg)

{

base.ProcessCommand(cmd, arg);

}

#endregion

public enum WaitFormCommand

{

}

private void RecognizeForm_Shown(object sender, EventArgs e)

{

rText = RecognizeHelper.ReadTextFromImage(filePath, language);

isClosed = true;

DialogResult = System.Windows.Forms.DialogResult.OK;

}

}

public partial class ResultForm: MainFormEx

{

string result = string.Empty;

public ResultForm(string result)

{

InitializeComponent();

this.result = result;

}

private void ResultForm_Shown(object sender, EventArgs e)

{

richEditControl1.Text = result;

}

}

public partial class AccessPoint: SplashScreen

{

private PassportData passportData = null;

private List<string> listOfAuthority = null;

public PassportData PassportData

{

get

{

return passportData;

}

set

{

passportData = value;

}

}

public List<string> ListOfAuthority

{

get

{

return listOfAuthority;

}

set

{

listOfAuthority = value;

}

}

public AccessPoint()

{

InitializeComponent();

}

#region Overrides

public override void ProcessCommand(Enum cmd, object arg)

{

base.ProcessCommand(cmd, arg);

}

#endregion

public enum SplashScreenCommand

{

}

private void exitButton_ItemClick(object sender, DevExpress.XtraBars.ItemClickEventArgs e)

{

this.Close();

}

private void notifyIcon1_MouseDown(object sender, MouseEventArgs e)

{

if (e.Button == System.Windows.Forms.MouseButtons.Right)

popupMenu1.ShowPopup(Cursor.Position);

}

private void textButton_ItemClick(object sender, DevExpress.XtraBars.ItemClickEventArgs e)

{

var textForm = new MainForm();

textForm.Show();

}

private void passportButton_ItemClick(object sender, DevExpress.XtraBars.ItemClickEventArgs e)

{

ScanPassport passportForm = new ScanPassport(passportData, listOfAuthority);

passportForm.Show();

}

private void faceButton_ItemClick(object sender, DevExpress.XtraBars.ItemClickEventArgs e)

{

MultiFaceRecognizeForm frForm = new MultiFaceRecognizeForm();

frForm.Show();

}

private void AccessPoint_Shown(object sender, EventArgs e)

{

BackgroundWorker bw = new BackgroundWorker();

bw.DoWork += (a, c) =>

{

DataBaseHelper manager = new DataBaseHelper();

c.Result = manager.CreateDataBase();

};

bw.RunWorkerCompleted += (a, c) =>

{

var result = c.Result as ActionResults;

if (result.Error != null)

{

XtraMessageBox.Show(result.Error.Message);

this.Close();

}

else

{

notifyIcon1.Visible = true;

this.Hide();

}

};

bw.RunWorkerAsync();

}

}

г) Распознавание паспортов.

public static class EditImage

{

public static Image CropImage(this Image image, Rectangle selection)

{

try

{

Bitmap bmp = image as Bitmap;

if (bmp != null)

{

Bitmap cropBmp = bmp.Clone(selection, bmp.PixelFormat);

image.Dispose();

return cropBmp;

}

else

return null;

}

catch

{

return null;

}

}

public static bool ResizeImage(string imageLocation, Size size)

{

try

{

Image img;

using (Image imgToResize = Image.FromFile(imageLocation))

{

img = (Image)(new Bitmap(imgToResize, size));

}

img.Save(imageLocation, System.Drawing.Imaging.ImageFormat.Jpeg);

return true;

}

catch

{ return false; }

}

public static Image ResizeImage(Image image, Size size)

{

try

{

Image img = (Image)(new Bitmap(image, size));

return img;

}

catch

{ return null; }

}

}

public partial class PleaseWaitForm: WaitForm

{

string imageLocation = string.Empty;

string lastName = string.Empty, firstName = string.Empty, middleName = string.Empty;

string passportNo = string.Empty, authority = string.Empty;

DateTime birthday, dateOfIssue, dateOfExpire;

bool sex, isUnlimited, isClosed = false, isBioPassport = false;

Image picture = null;

private List<Dictionary<string, Rectangle>> rectangles = null;

public string LastName { get { return lastName; } }

public string FirstName { get { return firstName; } }

public string MiddleName { get { return middleName; } }

public string PassportNo { get { return passportNo; } }

public string Authority { get { return authority; } }

public DateTime Birthday { get { return birthday; } }

public DateTime DateOfIssue { get { return dateOfIssue; } }

public DateTime DateOfExpire { get { return dateOfExpire; } }

public bool Sex { get { return sex; } }

public bool IsUnlimited { get { return isUnlimited; } }

public bool IsClosed { get { return isClosed; } }

public Image Picture { get { return picture; } }

public List<Dictionary<string, Rectangle>> Rectangles { get { return rectangles; } }

void fillList()

{

//Simple Passport

Dictionary<string, Rectangle> pRect = new Dictionary<string, Rectangle>();

pRect.Add("lastname", new Rectangle(new Point(136, 70), new Size(564, 100)));

pRect.Add("firstname", new Rectangle(new Point(136, 224), new Size(564, 76)));

pRect.Add("middlename", new Rectangle(new Point(136, 300), new Size(564, 74)));

pRect.Add("birthday", new Rectangle(new Point(136, 444), new Size(564, 78)));

pRect.Add("dateOfIssue", new Rectangle(new Point(136, 522), new Size(564, 72)));

pRect.Add("dateOfExpire", new Rectangle(new Point(790, 530), new Size(350, 74)));

pRect.Add("sex", new Rectangle(new Point(1020, 160), new Size(200, 80)));

pRect.Add("passportNo", new Rectangle(new Point(1050, 1100), new Size(400, 100)));

pRect.Add("authority", new Rectangle(new Point(136, 760), new Size(1284, 74)));

pRect.Add("picture", new Rectangle(new Point(85, 1235), new Size(400, 535)));

pRect.Add("lastnameEng", new Rectangle(new Point(500, 1190), new Size(700, 70)));

pRect.Add("firstnameEng", new Rectangle(new Point(500, 1260), new Size(700, 75)));

pRect.Add("birthdayEng", new Rectangle(new Point(500, 1415), new Size(420, 75)));

pRect.Add("dateOfIssueEng", new Rectangle(new Point(500, 1565), new Size(420, 75)));

pRect.Add("dateOfExpireEng", new Rectangle(new Point(980, 1565), new Size(480, 100)));

pRect.Add("sexEng", new Rectangle(new Point(980, 1415), new Size(170, 85)));

//BioPassport

Dictionary<string, Rectangle> bRect = new Dictionary<string, Rectangle>();

bRect.Add("lastname", new Rectangle(new Point(70, 320), new Size(730, 85)));

bRect.Add("firstname", new Rectangle(new Point(70, 405), new Size(730, 90)));

bRect.Add("middlename", new Rectangle(new Point(70, 495), new Size(730, 90)));

bRect.Add("birthday", new Rectangle(new Point(70, 585), new Size(310, 80)));

bRect.Add("dateOfIssue", new Rectangle(new Point(500, 1620), new Size(350, 65)));

bRect.Add("dateOfExpire", new Rectangle(new Point(500, 1685), new Size(350, 75)));

...