Аппроксимация линии по точкам контура через преобразования Хафа (Line approximation by contour points through Hough transforms)

Автор: | 19.02.2021
Нет комментариев

Tags: Преобразования Хафа Line approximation

Введение
Аппроксимация прямой
Обобщение преобразований Хафа
Аппроксимация эллипса
Полезные ссылки

Введение

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

Контуры в Python — это список  всех контуров изображения. Каждый отдельный контур представляет собой массив Numpy с координатами (x, y) граничных точек объекта.

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

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

Аппроксимация прямой

Как это работает? Вы должны вспомнить школьную формулу y=(x*cos(theta)+rho)/sin(theta).

Где theta –угол линии, а rho является расстоянием от линии до центра координат (0, 0).
Важным является то, что линия может быть описана всего двумя переменными: углом наклона и расстоянием до центра координат.

Алгоритм проходит по всем пикселям в монохромном изображении, пропуская белые пиксели. Когда он попал на чёрный пиксель, то пытается «нарисовать» всевозможные линии, проходящие через этот пиксель с шагом в 1 градус. Это означает, что каждый пиксель имеет 180 воображаемых линий, проходящих через него.

Почему не 360? Да потому что углы 180-360 являются копиями линий с углами 0-180 градусов.

Это множество линий называется накопителем, двумерным массивом с размерностями theta и rho, которые были в формуле выше. Каждая воображаемая линия представлена одним значением в накопителе. Кстати, метод называется преобразованием, потому что он преобразовывает линии из (x, y) в массив (theta, tho). Каждая воображаемая линия добавляет значение в накопитель, повышая вероятность того, что воображаемая линия совпадает с реальной. Это как голосование. Настоящие линии имеют больше всего «голосов».

После того, как все пиксели и их 180 воображаемых линий «проголосовали», мы должны найти максимальное значение в накопителе. Накопителем он называется потому что накапливает голоса. Победителем голосования является самая выразительная линия. Её параметры theta и rho могут использоваться с помощью формулы выше чтобы нарисовать её.

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

Посмотрев на это изображение, можно понять, как же работает обнаружение линий. Алгоритм преобразования Хафа пропускает белые пиксели. На каждом чёрном пикселе он рисует четыре воображаемых зелёных линии (на самом деле их 180, но для простоты мы возьмём четыре), проходящие через текущий пиксель. Первый пиксель голосует за линии A, B, C и D. Второй пиксель голосует за линии E, B, G, H. Третий за I, B, K, L. За линию B проголосовали все три пикселя, а остальные линии получили всего по одному голосу. Таким образом, линия B победила в голосовании.

Обобщение преобразований Хафа

Преобразование Хафа важно понять, если вы хотите заниматься распознаванием образов. Концепция виртуальных линий, которые могут быть реальными с помощью голосования, может быть распространена на любую геометрическую фигуру. Прямая линия – простейшая из них. Если вам надо найти окружность, то понадобится накопитель с тремя размерностями: x, y и r. Где x и y являются координатами центра нашей окружности, а r радиусом. Преобразование Хафа может быть оптимизировано ограничением области и возможных углов исходного изображения. Нам не надо анализировать все линии, только те, что близки к центру. В нашем случае, именно от них мы и можем отталкиваться.

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

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

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

Аппроксимация эллипса

Идеальный эллипс описывается уравнением кривой второго порядка:

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

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

Сначала находим граничные точки любым из градиентных методов. Берем случайные шесть точек из массива Math.Rand() и по ним строим эллипс. И так много-много раз (эмпирически для изображения размером 700х700 пикселей — достаточно двух тысяч итераций).

Из полученных данных можно было построить зависимость x = f(y), где (x,y) — это координаты центра эллипса;  Точка — в которой полученные координаты встречаются чаще всего — наша искомая точка. По количеству совпадений определяется вес каждой точки. Точки, в которых вес > порога, считаются центрами эллипса. Абсолютно идентичная картина и в случае с перебором полученного массива длин осей эллипса  R1 = f(R2) — где R1 и R2 — это длины осей эллипса, которые принимаем за координаты.

Полезные ссылки: