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

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

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

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

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

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

• Переход к натуральной параметризации прямых. Целесообразно использовать параметризацию (x,dx) для прохода по строкам и (y,dy) для прохода по столбцам. Здесь x – также точка пересечения прямой оси Ox, y – соответственно оси O y; параметр dx – смещение координаты х при изменении координаты y на половину высоты окна, dy определяется аналогично.

• Оптимизация процедуры голосования одной точки. В случае, когда используется параметризация (x,dx)/(y,dy), функция отклика каждой точки исходного пространства в точности представляет собой дискретную прямую в аккумуляторе, формируемую при помощи операций целочисленного сложения.

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

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

@Рис. 5.2.9. Пример применения RHT: a – исходное полутоновое изображение; b – исходный бинарный контурный препарат; c – результат обнаружения линеаментов. На исходном контурном препарате выделены локальные прямолинейные структуры.

@Рис. 5.2.10. Пример обнаружения линеаментов с использованием RHT с различными параметрами размера окна: a – маленький размер окна фильтрации; b – средний размер окна; c - большой размер окна. Выделены линеаменты различных размеров.

В работах [140], [143], [144], [145], [146], [147], [148], [150], [154], [155], [173], [197], [198], [203], [208], [210], [213], [244], [245], [248], [250], [255], [258] содержится еще целый ряд интересных идей относительно использования различных модификаций и обобщений преобразования Хафа.