ОПИСАНИЕ ИСПОЛЬЗУЕМЫХ АЛГОРИТМОВ

ВВЕДЕНИЕ

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

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

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

ОБЗОР ПРЕДМЕТНОЙ ОБЛАСТИ

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

Вторым этапом является формирование признаков для распознаваемых объектов на изображении и далее, непосредственно, само распознавание.

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

Вернемся непосредственно к методам предварительной обработки.

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

Перевод в полутоновое изображение.

В приложение поступает цветное изображение формата .bmp, каждый пиксель которого имеет различный значения R,G,B. Это значения соответственно красного, зеленого и синего цвета. Известны следующие методы перевода цветного изображения в полутоновое:

· I=(R+G+B)/3, где I – яркость исследуемого пикселя;

· I=0,5*(max(R,G,B)+min(R,G,B)) , где I – яркость исследуемого пикселя.

· Y=0.299 R+0.587 G+0.114B.

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

Бинаризация полутонового изображения.

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

Методы бинаризации

Бинаризация с нижним порогом

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

Все значения вместо критерия становятся 1, в данном случае 255 (белый) и все значения (амплитуды) пикселей, которые больше порога t — 0 (черный).

Метод Бернсена

Обычная квадратная апертура с нечетным числом пикселей пробегает в цикле по всем пикселям исходного изображения. На каждом шаге находится Min и Max. Находится среднее значение Avg= (Min + Max) /2. Если текущий пиксель больше Avg<E — он становится белым, иначе — чёрным. E — некая константа заданная пользователем.
Если среднее меньше порога контраста — то текущий пиксель становится того цвета, который задавался параметром «цвет сомнительного пикселя». Имеет ряд недостатков: после обработки монотонных областей яркости формируются сильные паразитные помехи, в некоторых случаях приводит к появлению ложных черных пятен.

Метод «MOD»

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

Выделение контуров

Все алгоритмы делятся на 2 типа: сканирующие, отслеживающие.

Отслеживающие алгоритмы

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

Сканирующие алгоритмы

Сканирующие алгоритмы просматривают все изображение и выделяют контурные точки без отслеживания контура объекта. Например, один из алгоритмов обрабатывает полосу изображения и определяет контурные точки в процессе движения по всему изображению. В полосе одновременно хранятся 2 строки изображения (текущие и предыдущие). При обработке анализируются координаты черных серий одних строк слева – направо и определяются пять ситуация:

1. «Начало» - черная серия текущей строки полностью закрывается белой серией предыдущей строки.

2. «Продолжение» - частичное перекрытие черных серий обоих строк.

3. «Ветвление» - две соседние черные серии текущей строки закрываются черной серией предыдущей строки.

4. «Слияние» - противоположно «продолжению».

5. «Конец» - противоположно «началу».

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

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

Системы распознавания делятся на:

· Системы без обучения

· Системы с учителем

· Самообучающиеся системы

Системы без обучения

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

Эти системы с одной стороны являются достаточно простыми, но не универсальными. Основные из них:

· метод совмещения с эталоном

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

· метод зондов

Метод зондов заключается в распознании объектов по «накладываемым» на него рискам – зондам. Принадлежность к тому или иному классу определяется по совпадению количества пересечений зондов с объектом с заранее известным соотношением для классов.

· метод маркировки изображений

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

· метод, основанный на характеристических точках

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

Системы с учителем

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

К системам с учителям относятся:

· метод дробящих эталонов

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

Распознавание: определяется расположение неизвестного объекта относительно геперсфер первого уровня. Если объект попал в гиперсферу, соответствующую одному и только одному классу, распознавание заканчивается, иначе определяется положение объекта относительно гиперсфер второго уровня и так до тех пор, пока эта принадлежность не будет определена однозначно.

· метод ближайшего соседа

Обучение: запоминаются все объекты обучающей выбоки.

Распознавание: неизвестный объект относится к тому классу, чей представитель оказывается наиболее близким к этому классу.

· метод k-ближайших соседей

Обучение: в центре с неизвестным объектом строится гиперсфера, объемом V.

Распознавание: осуществляется по большинству представителей какого-либо класса, попавших внутрь этой гиперсферы.

· персептрон

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

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

Самообучающиеся системы

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

· индекс;

· исправленные индексы;

· алгоритм «Спектр»;

· алгоритм «Объединение»;

· алгоритм «Оптимальная объективная классификация»;

· алгоритм «Форель» и другие.

ПОСТАНОВКА ЗАДАЧИ

В ходе выполнения курсового проекта необходимо разработать приложение, которое должно определять владельца ладони руки. Язык исполняемого приложения – С#.

Исходными данными для программы является цветное изображение в формате *.jpg или *bmp.

В данном приложении должны быть реализованы следующие функции:

1. Загрузка изображений рук.

2. Перевод цветного изображения в полутоновое.

3. Бинаризация.

4. Центрирование изображения.

5. Оконтуривание, нахождение и удаления запястья, нахождение кончиков пальцев.

6. Распознавание (формирование признаков, распознавание).

Среда разработки приложения – Microsoft Visual Studio 2012.

Тип приложения – Windows Form Application.

Операционная система – Windows 7.

Функциональные схемы приложения приведены на рисунках 2.1, 2.2 и 2.3.