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

Обобщенное преобразование Хафа ( GHT ), представленное Даной Х. Баллард в 1981 году, представляет собой модификацию преобразования Хафа , использующую принцип сопоставления шаблонов . ^[1] Преобразование Хафа изначально было разработано для обнаружения аналитически определенных форм (например, линии , круга , эллипса и т. д.). В этих случаях мы знаем форму и стремимся выяснить ее расположение и ориентацию на изображении. Эта модификация позволяет использовать преобразование Хафа для обнаружения произвольного объекта, описываемого его моделью.

Проблему поиска объекта (описанного моделью) на изображении можно решить, найдя положение модели на изображении. С помощью обобщенного преобразования Хафа проблема определения положения модели преобразуется в проблему поиска параметра преобразования, который отображает модель в изображение. По значению параметра преобразования можно определить положение модели на изображении.

Исходная реализация GHT использовала информацию о краях для определения сопоставления ориентации точки края с опорной точкой формы. В случае бинарного изображения , где пиксели могут быть черными или белыми, каждый черный пиксель изображения может быть черным пикселем желаемого шаблона, создавая таким образом локус опорных точек в пространстве Хафа. Каждый пиксель изображения голосует за соответствующие ему контрольные точки. Максимальные точки пространства Хафа указывают на возможные опорные точки узора на изображении. Этот максимум можно найти путем сканирования пространства Хафа или решения расслабленной системы уравнений , каждое из которых соответствует черному пикселю. ^[2]

История

Мерлин и Фарбер ^[3] показал, как использовать алгоритм Хафа, когда искомые кривые невозможно описать аналитически. Это был предшественник алгоритма Балларда, который ограничивался перемещением и не учитывал вращение и изменения масштаба . ^[4]

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

Теория обобщенного преобразования Хафа

Чтобы обобщить алгоритм Хафа на неаналитические кривые, Баллард определяет следующие параметры для обобщенной формы: a={y,s,θ}, где y — исходное начало формы, θ — ее ориентация, а s = (s _x , s _y ) описывает два ортогональных масштабных коэффициента. Алгоритм может вычислить лучший набор параметров для заданной формы на основе данных краевых пикселей. Эти параметры не имеют равного статуса. Местоположение опорного источника, y , описывается в терминах таблицы шаблонов, называемой таблицей R возможных ориентаций краевых пикселей. Затем вычисление дополнительных параметров s и θ выполняется путем прямых преобразований этой таблицы. Ключевым обобщением произвольных форм является использование информации о направлении. При любой форме и фиксированной опорной точке на ней вместо параметрической кривой информация, предоставляемая граничными пикселями, сохраняется в виде R-таблицы на этапе преобразования. Для каждой краевой точки тестового изображения свойства точки просматриваются в R-таблице, извлекается опорная точка и увеличивается соответствующая ячейка в матрице, называемой матрицей аккумулятора. Ячейка с максимальным количеством «голосов» в матрице Аккумулятора может быть возможной точкой существования фиксированной ссылки объекта на тестовом изображении.

Построение R-таблицы

Выберите опорную точку y для фигуры (обычно выбирается внутри фигуры). Для каждой граничной точки x вычислите ɸ(x) , направление градиента и r = y – x, как показано на изображении. Сохраните r как функцию ɸ . Обратите внимание, что каждый индекс ɸ может иметь множество значений r . Можно либо сохранить разность координат между фиксированной привязкой и точкой края ((x _c – x _ij ), (y _c – y _ij )) или как радиальное расстояние и угол между ними (r _ij , α _ij ) . Сделав это для каждой точки, R-таблица будет полностью представлять объект шаблона. Кроме того, поскольку фаза генерации обратима, мы можем использовать ее для локализации появления объектов в других местах изображения.

я	ɸ _я	Р _{ɸ _я}
1	0	(р ₁₁ , а ₁₁ ) (р ₁₂ , а ₁₂ )... (р _1н , а _1н )
2	Δɸ	(р ₂₁ , а ₂₁ ) (р ₂₂ , а ₂₂ )... (р _2м , а _2м )
3	2Δɸ	(р ₃₁ , а ₃₁ ) (р ₃₂ , а ₃₂ )... (р _3к , а _3к )
...	...	...

Локализация объекта

Для каждого краевого пикселя x изображения найдите градиент ɸ и увеличьте все соответствующие точки x+r в массиве аккумуляторов A (инициализированном максимальным размером изображения), где r — запись таблицы, индексированная ɸ , т. е. r (ɸ) . Эти точки входа дают нам каждую возможную позицию для контрольной точки. Хотя некоторые ложные точки могут быть вычислены, учитывая, что объект существует на изображении, максимум будет иметь место в контрольной точке. Максимумы в A соответствуют возможным экземплярам формы.

Обобщение масштаба и ориентации

При фиксированной ориентации формы массив аккумуляторов был двумерным в координатах опорной точки. Для поиска форм произвольной ориентации θ и масштаба s в описание формы добавляются эти два параметра. Массив аккумуляторов теперь состоит из четырех измерений, соответствующих параметрам (y, s, θ) . R-таблицу также можно использовать для увеличения этого пространства большего размера, поскольку разные ориентации и масштабы соответствуют легко вычисляемым преобразованиям таблицы. Обозначим конкретную R-таблицу для формы S через R(ɸ) . Простые преобразования этой таблицы позволят ей обнаруживать масштабированные или повернутые экземпляры одной и той же формы. Например, если форма масштабируется как s и это преобразование обозначается T _s .затем T _s [R(ɸ)] = sR(ɸ), т. е. все векторы масштабируются по s . Кроме того, если объект вращается на θ и это преобразование обозначается T _θ , то Т _θ [R(ɸ)] = Rot{R[(ɸ-θ)mod2π],θ} т. е. все индексы увеличиваются на – θ соответствующие векторы r , а затем они поворачиваются на по модулю 2π, находятся θ .Еще одним свойством, которое будет полезно при описании состава обобщенных преобразований Хафа, является смена опорной точки. Если мы хотим выбрать новую опорную точку ỹ такую, что y-ỹ = z , тогда модификация R-таблицы задается как R(ɸ)+ z , то есть z добавляется к каждому вектору в таблице.

Альтернативный способ использования пар ребер

Пара краевых пикселей может использоваться для уменьшения пространства параметров. Используя R-таблицу и свойства, описанные выше, каждый краевой пиксель определяет поверхность в четырехмерном аккумуляторном пространстве a = (y, s, θ) . Два краевых пикселя в разных ориентациях описывают одну и ту же поверхность, повернутую на одинаковую величину относительно θ . Если эти две поверхности пересекаются, точки их пересечения будут соответствовать возможным параметрам a формы . Таким образом, теоретически возможно использовать две точки в пространстве изображений, чтобы свести локус в пространстве параметров к одной точке. Однако трудности с нахождением точек пересечения двух поверхностей в пространстве параметров сделают этот подход неосуществимым в большинстве случаев.

Составные формы

Если форма S имеет составную структуру, состоящую из подчастей 1 _, S 2 _, .. S _N и опорными точками для форм S , S ₁ , S ₂ , .. SN _S являются y , y ₁ , y ₂ , . n y _. соответственно, тогда для масштабного коэффициента s и ориентации θ обобщенное преобразование Хафа R _s (ɸ) определяется выражением $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ . Проблема с этим преобразованием заключается в том, что выбор ссылки может сильно повлиять на точность. Чтобы преодолеть эту проблему, Баллард предложил сгладить полученный аккумулятор с помощью составного шаблона сглаживания. Составной шаблон сглаживания H(y) представляет собой составную свертку отдельных шаблонов сглаживания подформ. $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ . Тогда улучшенный аккумулятор определяется как A _s = A*H , а максимумы в A _s соответствуют возможным экземплярам формы.

Пространственная декомпозиция

Заметив, что глобальное преобразование Хафа можно получить путем суммирования локальных преобразований Хафа непересекающейся подобласти, Хизер и Янга ^[5] предложил метод, который включает рекурсивное разделение изображения на части изображения, каждое из которых имеет собственное пространство параметров и организовано в структуру квадродерева . Это приводит к повышению эффективности поиска конечных точек отрезков линий, а также к повышению устойчивости и надежности извлечения линий в шумных ситуациях при незначительном увеличении затрат памяти.

Выполнение

В реализации используются следующие уравнения: ^[6]

x=x_{c}+x'\ \ or\ \ x_{c}=x-x'

y=y_{c}+y'\ \ or\ \ y_{c}=y-y'

\cos(\pi -\alpha )=x'/r\ \ {\text{or}}\ \ x'=r\cos(\pi -\alpha )=-r\cos(\alpha )

\sin(\pi -\alpha )=y'/r\ \ {\text{or}}\ \ y'=r\sin(\pi -\alpha )=r\sin(\alpha )

Объединив приведенные выше уравнения, мы имеем:

x_{c}=x+r\cos(\alpha )

y_{c}=y+r\sin(\alpha )

Построение R-таблицы

(0) Преобразуйте изображение формы образца в изображение края, используя любой обнаружения края, алгоритм например детектор края Канни.

(1) Выберите контрольную точку (например, (x _c , y _c ) )

(2) Нарисуйте линию от контрольной точки до границы.

(3) Вычислить ɸ

(4) Сохраните опорную точку (x _c , y _c ) как функцию ɸ в таблице R(ɸ) .

Обнаружение:

(0) Преобразуйте изображение формы образца в изображение края, используя любой алгоритм обнаружения края, например детектор края Канни .

(1) Инициализируйте таблицу аккумуляторов: A[x _cmin . . . x _cmax ][y _cmin . . . у _cmax ]

(2) Для каждой краевой точки (x, y)

(2.1) Используя угол градиента ɸ , извлеките из R-таблицы все значения (α, r), индексированные под ɸ .

(2.2) Для каждого (α,r) вычислите возможные опорные точки:

x _c = x + r cos(α)

y _c = y + r sin(α)

(2.3) Увеличение счетчиков (голосование):

++A([[x _c ]][y _c ])

(3) Возможные положения контура объекта задаются локальными максимумами в A[x _c ][y _c ] .

Если A[x _c ][y _c ] > T , то контур объекта расположен в точке (x _c , y _c )

Общий случай:

Предположим, что объект подвергся некоторому вращению Θ и равномерному масштабированию s :

(x ′ , y ′ ) → (x″, y″)

x″ = (x ′ cos(Θ) – y ′ sin(Θ))s

y″ = (x ′ sin(Θ) + y ′ cos(Θ))s

Замена x ′ на x″ и y ′ на y″:

x _c = x – x″ или x _c = x - (x ′ cos(Θ) – y ′ sin(Θ))s

y _c = y – y″ или y _c = y - (x ′ sin(Θ) + y ′ cos(Θ))s

(1) Инициализируйте таблицу аккумуляторов: A[x _cmin . . . x _cmax ][y _cmin . . . y _cmax ][q _min . . . q _макс ][с _мин . . . s _макс ]

(2) Для каждой краевой точки (x, y)

(2.1) Используя угол градиента ɸ , извлеките все значения (α, r) из R-таблицы.

(2.2) Для каждого (α, r) вычислите возможные опорные точки:

x ′ = r cos(α)

y ′ = r sin(α)

for( Θ = Θ _min ; Θ ≤ Θ _max ; Θ++ )

for( s = s _min ; s ≤ s _max ; s++ )

x _c = x - (x ′ cos(Θ) – y ′ sin(Θ))s

y _c = y - (x ′ sin(Θ) + y ′ cos(Θ))s

++(A[xc _] [yc _] [Θ][s])

(3) Возможные положения контура объекта задаются локальными максимумами в A[x _c ][y _c ][Θ][s]

Если A[x _c ][y _c ][Θ][s] > T , то контур объекта расположен в точке (x _c , y _c ) , подвергся вращению Θ и масштабирован на s .

Преимущества и недостатки

Преимущества

Он устойчив к частичным или слегка деформированным формам (т. е. устойчив к распознаванию при окклюзии).
Он устойчив к присутствию дополнительных структур на изображении.
Толерантен к шуму.
Он может найти несколько вхождений фигуры за один проход обработки.

Недостатки

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

Связанная работа

Баллард предложил использовать информацию об ориентации края, чтобы снизить стоимость вычислений. Было предложено множество эффективных методов GHT, таких как SC-GHT (использование наклона и кривизны как локальных свойств). ^[7]Дэвис и Ям ^[8] также предложил расширение работы Мерлина для сопоставления инвариантов ориентации и масштаба, которое дополняет работу Балларда, но не включает использование Баллардом информации о наклоне края и составных структур.

См. также

Ссылки

^ Д. Х. Баллард, «Обобщение преобразования Хафа для обнаружения произвольных форм», Распознавание образов, том 13, № 2, стр. 111-122, 1981
^ Жолен, Л.; Базейль, С. (2013). Извлечение формы изображения с использованием интервальных методов (PDF) . В Proceedings of Sysid 2009, Сен-Мало, Франция.
^ Мерлин, премьер-министр; Фарбер, ди-джей (январь 1975 г.). «Параллельный механизм обнаружения кривых на изображениях» . Транзакции IEEE на компьютерах . С-24 (1): 96–98. дои : 10.1109/tc.1975.224087 . ISSN 0018-9340 . S2CID 27723442 .
^ Л. Дэвис, «Иерархические обобщенные преобразования Хафа и обобщенные преобразования Хафа на основе линейных отрезков» , Техасский университет компьютерных наук, ноябрь 1980 г.
^ Дж. А. Хизер, Сюэ Донг Ян, «Пространственное разложение преобразования Хафа» , 2-я канадская конференция по компьютерному и роботизированному зрению, 2005.
^ Баллард и Браун, раздел 4.3.4, Сонка и др., раздел 5.2.6.
^ А. А. Кассим, Т. Тан, К. Х. Тан, «Сравнительное исследование эффективных методов обобщенного преобразования Хафа», Image and Vision Computing, том 17, выпуск 10, страницы 737-748, август 1999 г.
^ Л. Дэвис и С. Ям, «Обобщенное преобразование типа Хаф для распознавания формы» . Техасский университет компьютерных наук, TR-134, февраль 1980 г.

Внешние ссылки

Реализация OpenCV обобщенного преобразования Хафа http://docs.opencv.org/master/dc/d46/classcv_1_1GeneralizedHoughBallard.html
Учебное пособие и реализация обобщенных преобразований Хафа http://www.itriacasa.it/generalized-hough-transform/default.html
Практическая реализация обобщенного преобразования Хафа http://www.irit.fr/~Julien.Pinquier/Docs/Hough_transform.html
Реализация обобщенных преобразований Хафа на FPGA, Цифровая библиотека IEEE https://ieeexplore.ieee.org/document/5382047/
Реализация MATLAB обобщенного преобразования Хафа http://www.mathworks.com/matlabcentral/fileexchange/44166-generalized-hough-transform

[1] Д. Х. Баллард, «Обобщение преобразования Хафа для обнаружения произвольных форм», Распознавание образов, том 13, № 2, стр. 111-122, 1981

[2] Жолен, Л.; Базейль, С. (2013). Извлечение формы изображения с использованием интервальных методов (PDF) . В Proceedings of Sysid 2009, Сен-Мало, Франция.

[3] Мерлин, премьер-министр; Фарбер, ди-джей (январь 1975 г.). «Параллельный механизм обнаружения кривых на изображениях» . Транзакции IEEE на компьютерах . С-24 (1): 96–98. дои : 10.1109/tc.1975.224087 . ISSN 0018-9340 . S2CID 27723442 .

[4] Л. Дэвис, «Иерархические обобщенные преобразования Хафа и обобщенные преобразования Хафа на основе линейных отрезков» , Техасский университет компьютерных наук, ноябрь 1980 г.

[5] Дж. А. Хизер, Сюэ Донг Ян, «Пространственное разложение преобразования Хафа» , 2-я канадская конференция по компьютерному и роботизированному зрению, 2005.

[6] Баллард и Браун, раздел 4.3.4, Сонка и др., раздел 5.2.6.

[7] А. А. Кассим, Т. Тан, К. Х. Тан, «Сравнительное исследование эффективных методов обобщенного преобразования Хафа», Image and Vision Computing, том 17, выпуск 10, страницы 737-748, август 1999 г.

[8] Л. Дэвис и С. Ям, «Обобщенное преобразование типа Хаф для распознавания формы» . Техасский университет компьютерных наук, TR-134, февраль 1980 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]