Просмотр исходного текста страницы Рекуррентное преобразование Хафа в скользящем окне


При решении многих практических задач полезно иметь в каждой точке
изображения информацию о том, проходят ли через нее какие-либо прямолинейные
отрезки, и если да, то каковы их параметры. Для этой цели служит
предложенное в $\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{алгоритмическая реализация}$, позволяющая добиться
тех же результатов при существенно меньших вычислительных затратах. Суть
изменений заключается в том, чтобы перейти к рекуррентному заполнению
аккумулятора скользящего окна по аналогии с тем, как это делается для
ранговых фильтров. Для этого необходимо внести следующие модификации.

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

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

#[[#top| &#9757; К началу ]]
#[[Преобразование Хафа, его обобщения и модификации|&#9756; Преобразование Хафа, его обобщения и модификации]]