Рекуррентное преобразование Хафа в скользящем окне

Материал из Техническое зрение
Перейти к: навигация, поиск

При решении многих практических задач полезно иметь в каждой точке изображения информацию о том, проходят ли через нее какие-либо прямолинейные отрезки, и если да, то каковы их параметры. Для этой цели служит предложенное в $\textit{рекуррентное преобразование Хафа в скользящем окне }$($\textit{RHT}$).

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

Для корректного переноса результата голосования в каждом отдельном окне в финальный единый аккумулятор, необходимо изменить параметризацию пространства Хафа. Будем описывать прямую в окне параметрами ($x,Q$). Здесь $x$ - координата пересечения оси $X$ окна, а $Q$ - угол наклона этой прямой к оси $X$. После голосования всех точек окна получим аккумулятор, в котором в точке ($x,Q$) будет содержаться количество точек, лежащих на прямой, проходящей в этом окне через точку ($x,0$) под углом $Q$. Теперь для переноса в конечный массив необходимо определить для каждой точки на оси $Ox$ окна прямую, за которую проголосовало наибольшее количество точек, после чего эти результаты можно перенести в конечный массив в соответствующие ячейки. Однако очевидно, что при параметризации $(x,Q)$ мы можем захватить далеко не все прямые, так как часть из них будут пересекать ось $Ox$ далеко за пределами окна или не пересекать вообще. Для решения этой проблемы введем дополнительную параметризацию $(y,Q)$. Проход с параметризацией $(x,Q)$ назовем $\textit{проходом по строкам}$. При проходе по строкам будем идти окном от самого нижнего левого положения и полностью проходить по строке исходного изображения до крайне правого положения, а затем подниматься на строку вверх. При проходе по столбцам будем идти окном от самого нижнего левого положения и полностью проходить по столбцу исходного изображения до самого верхнего положения, а затем смещаться на столбец влево. После окончания обоих проходов, их результаты объединяются при помощи операции "максимум", в результате чего в финальном аккумуляторе оказываются записанными те отрезки, за которые было подано максимальное количество голосов. Кроме этого, учитывая, что мы используем два прохода и можем иметь угол наклона как по отношению к оси $Ox$, так и к оси $Oy$, массив аккумулятора также должен содержать некоторый флаг, определяющий, какой тип значения угла содержится в данной ячейке.

Заполненный таким образом массив аккумулятора содержит все возможные для данного изображения варианты расположения элементов прямых линий - линеаментов. После этого необходимо выделить наиболее достоверные отрезки. Возможны следующие варианты такой обработки: $\textit{пороговое отсечение}$ и $\textit{выделение локальных максимумов.}$ Параметрами здесь являются некоторое пороговое значение и размеры прямоугольной области, в которой ведется поиск максимума.

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

  1. $\textit{Переход к натуральной параметризации прямых.}$ Целесообразно использовать параметризацию ($x,dx$) для прохода по строкам и ($y,dy$) для прохода по столбцам. Здесь $x$ - также точка пересечения прямой оси $Ox$, $y$ - соответственно оси $Oy$; параметр $dx$ - смещение координаты $x$ при изменении координаты $y$ на половину высоты окна, $dy$ определяется аналогично.
  2. $\textit{Оптимизация процедуры голосования одной точки.}$ В случае, когда используется параметризация $(x,dx)/(y,dy)$, функция отклика каждой точки исходного пространства в точности представляет собой дискретную прямую в аккумуляторе, формируемую при помощи операций целочисленного сложения.
  3. $\textit{Переход к рекуррентной реализации преобразования.}$ Рассмотрим результат обработки

двух, следующих друг за другом позиций окна X$_{i}$ и $X_{i+1}$ строки $Y_{j}$. Обработка позиции $X_{i}$ заполняет конечный массив в диапазоне ($X_{i}-W/2$; $Y_{j})-(X_{i}+W/2$; $Y_{j})$, обработка позиции $X_{i+1}$ заполняет конечный массив в диапазоне $(X_{i+1}-W/2$; $Y_{j})-(X_{i+1}+W/2$; $Y_{j})$. Как видно, результаты двух соседних преобразований пересекается в диапазоне $(X_{i+1}-W/2$; $Y_{j})-(X_{i}+W/2$; $Y_{j})$ и при пересечении выбираются ячейки с максимальным количеством голосов. Это позволяет создать единый аккумулятор для всей строки и обрабатывать всю строку целиком, после чего для каждой координаты $x$ производится операция max по столбцу аккумулятора, и определяется наилучший вариант смещения $dx$. Полученный результат заносится в соответствующую строку финального аккумулятора для всего изображения. Проход по столбцам аналогичен, изменяются только базовые оси.


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


5-2-9.jpg

Пример применения RHT: $\textit{a}$ - исходное полутоновое изображение; $\textit{б}$ - исходный бинарный контурный препарат; $\textit{в}$ - результат обнаружения линеаментов. На исходном контурном препарате выделены локальные прямолинейные структуры

Файл:5-2-.10jpg

Пример обнаружения линеаментов с использованием RHT с различными параметрами размера окна: $\textit{a}$ - маленький размер окна фильтрации; $\textit{б}$ - средний размер окна; $\textit{в}$ - большой размер окна. Выделены линеаменты различных размеров

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

  1. ☝ К началу
  2. ☜ Преобразование Хафа, его обобщения и модификации
Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты