Метод максимальных площадей

1.         Метод максимальных площадей.

2.         Метод гистограмм.

Алгоритм был реализован с помощью библиотеки для обработки изображений OpenСV. При тестировании алгоритма использовались изображения игровой доски для игры в го с белыми и чёрными камнями. Пример его работы представлен на рис .

№	Эталонное изображение	Исследуемое изображение	Разностное изображение	Бинаризированое изображение , при =10	Отфильтрованное изображение
1
2
3

Рис. Пример работы алгоритма.

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

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

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

Предложим следующий алгоритм решения:

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

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

3. Повторяем пункт 2 до тех пор, пока не получим конечное количество подмножеств .

Метод был адаптирован и реализован функциями библиотеки OpenCV. Пример его работы представлен на рис.

№	Разностное изображение	Результат: области правильной формы
		Круг	Прямоугольник
1
2
3

Рис. Пример работы алгоритма для разных областей правильной формы.

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

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

В третьей строке исходным является изображение камня на игровой доске. Аналогично, в результате работы алгоритма область движения камня сводиться к однородной области правильной формы (круг, прямоугольник). 1.3 Метод гистограмм

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

Нужно построить изображение в оттенках серого цвета, содержащее необходимые нам объекты.

Введём оператор, который преобразует функцию яркости изображения  в функцию количественного распределения пикселей с определенным значением яркости (гистограмму) (где k – численное значение яркости):

Обратный оператор  преобразует гистограмму в изображение в оттенках серого.

Алгоритм состоит из следующих этапов:

1.         Построение гистограмм искомого объекта  и исходного изображения

2.         Формируем новую гистограмму, как нормированное произведение  и :

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

Метод был адаптирован и реализован функциями библиотеки OpenCV. Результаты применения метода приведены на рис.

		Доска	Черный камень	Белый камень
Искомое изображение
Гистограмма искомого изображения
Исходное изображение		По гистограмме доски	По гистограмме черного камня	По гистограмме белого камня
№
1
2
3

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

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

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

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

Контрольными точками могут быть, например:

1.         Видимый центр изображения.

2.         Центр масс изображения.

3.         Точка, заметно отличающаяся от остальных по цвету.

4.         Центр маркера, поставленного на объекте

и др.

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

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

Используются частные случаи аффинных преобразованияй:

1.         Растяжение (сжатие) вдоль координатных осей, задаваемое в виде:

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

.

2.         Поворот вокруг начальной точки на угол , описываемый формулой:

Матрица вращения (для однородных координат)

.

3.         Перенос, задаваемый простейшими соотношениями:

Матрица переноса имеет вид

.

2. Задача распознавание объекта

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

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

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

В методах описания свойств объекта для нахождения можно выделить два крайних направления:

Обобщение и использование эмпирических данных и правил об объекте (top-down, bottom-up)

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

1.         Божьи коровки обычно рыжего или красного цвета;

2.         На спине у них обычно присутствует некоторое количество черных пятнен (можно также посчитать примерное соотношения размера пятен с размером насекомого);

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

4.         Сверху божья коровка выглядит примерно как эллипс;

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

1.         Приблизительно известны ожидаемые размеры божьих коровок (то есть известно увеличение камеры и расстояние до снимаемого объекта);

2.         Нас интересуют только божьи коровки, сидящие на листьях (значит, если принять, что листья зеленые, можно рассматривать только объекты, находящиеся на зеленом фоне);

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

Моделирование внешнего вида объекта, использование инструментария распознавания образов (pattern recognition) .

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

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

Примеры часто используемых классификаторов:

1.         Метод наименьших квадратов;

2.         Прямое сравнение по какой-либо метрике пространства векторов признаков (например, сумме разности каждого элемента вектора) тестового изображения с изображениями-шаблонами (template-matching);

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

4.         Метод опорных векторов (support vector machines) – для распознавания изображений;

5.         Моделирование многомерной функции распределения векторов признаков изображений объекта, оценка вероятности принадлежности тестового изображению к смоделированному распределению (факторный анализ, метод главных компонент, анализ независимых компонент, линейный дискриминантный анализ);

6.         Деформируемые модели;

Прямое представление черно-белого изображения размера m*n в качестве вектора порождает пространство размерности m*n (яркость каждого пикселя – значение элемента вектора в таком пространстве). То есть изображение сравнительно небольшого разрешения (100x100) порождает пространство размерности 10,000. Работать в таком пространстве непросто, поэтому применяются различные методики снижения размерности, например метод главных компонент (principal components analysis, PCA)

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