Алгоритм преобразования Хафа

Алгоритм преобразования Хафа использует массив, называемый аккумулятором, для определения присутствия прямой y = mx + b. Размерность аккумулятора равна количеству неизвестных параметров пространства Хафа. Например, для линейной трансформации нужно использовать двумерный массив, так как имеются два неизвестных параметра: m и b. Два измерения аккумулятора соответствуют квантованным значениям параметров m и b. Для каждой точки и её соседей алгоритм определяет, достаточен ли вес границы в этой точке. Если да, то алгоритм вычисляет параметры прямой и увеличивает значение
в ячейке аккумулятора, соответствующей данным параметрам. Потом, найдя ячейки аккумулятора с максимальными значениями, обычно поиском локального максимума в пространстве аккумулятора, могут быть определены наиболее подходящие прямые. Самый простой способ - это пороговая фильтрация. Однако
в разных ситуациях разные методы могут давать разные результаты. Так как полученные прямые не содержат информацию о длине, следующим шагом является нахождение частей изображения, соответствующих найденным прямым. Более того, из-за ошибок на этапе определения границ фигур в пространстве аккумулятора также будут содержаться ошибки. Это делает поиск подходящих линий нетривиальным.

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

1.3.5 Принцип  метода Виолы-Джонса

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

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

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

Элементы матрицы рассчитываются по формуле(1):

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

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

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

Признак-отображение, где Df —множество допустимых значений признака. Если заданы признаки f1,…, fn, то вектор признаков x=(f1(x),…,fn(x)) называется признаковым описанием объекта x. Признаковые описания допустимо сопоставлять с самими объектами. При этом множество X=Df1*…*Dfn называют признаковым пространством.

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

• бинарный признак, Df={0,1};
• номинальный признак: Df — конечное множество;
• порядковый признак: Df — конечное упорядоченное множество;
• количественный признак: Df — множество действительных чисел.

Признак Хаара вычисляется по смежным прямоугольным областям.
 В стандартном методе Виолы–Джонса используются прямоугольные примитивы, изображенные на рисунке 3.

            Рисунок 1.3 - Примитивы Хаара

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

F = X — Y,

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

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

Для поиска объекта на цифровом изображении используется обученный классификатор. Классификатор формируется на примитивах Хаара.

Структура классификатора:

где maxWeakCount – количество слабых классификаторов;

stageThereshold – максимальный порог яркости;

weakClassifiers – набор слабых классификаторов, на основе которых выносится решение о том, находится объект на изображении или нет;

internalNodes и leafValues – параметры конкретного слабого классификатора.

Первые два значения в internalNodes не используются, третье - номер признака
 в общей таблице признаков, четвертое- пороговое значение слабого классификатора. Если значение признака Хаара меньше порога слабого классификатора, выбирается первое значение leafValues, если больше -  второе.

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