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

Преобразование обобщается Хаф ( 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 . Можно либо сохранить разности координат между фиксированной точкой отсчета и точкой края ((x _c - x _ij ), (y _c - y _ij )) или как радиальное расстояние и угол между ними (r _ij, α _ij ) . Сделав это для каждой точки, R-таблица будет полностью представлять объект шаблона. Кроме того, поскольку фаза генерации обратима, мы можем использовать ее для локализации вхождений объектов в других местах изображения.

Геометрия обнаружения формы для обобщенного преобразования Хафа

я	ɸ _я	R _{ɸ _я}
1	0	(r ₁₁ , α ₁₁ ) (r ₁₂ , α ₁₂ )… (r _1n , α _1n )
2	Δɸ	(r ₂₁ , α ₂₁ ) (r ₂₂ , α ₂₂ )… (r _2m , α _2m )
3	2Δɸ	(r ₃₁ , α ₃₁ ) (r ₃₂ , α ₃₂ )… (r _3k , α _3k )
...	...	...

Локализация объекта [ править ]

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

Обобщение масштаба и ориентации [ править ]

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

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

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

Составные формы [ править ]

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

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

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

Реализация [ править ]

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

${\ displaystyle x = x_ {c} + x '\ или \ \ x_ {c} = x-x'}$

${\ displaystyle y = y_ {c} + y '\ или \ \ 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) Преобразуйте изображение формы образца в изображение края, используя любой алгоритм обнаружения краев , например детектор краев Canny.

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

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

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

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

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

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

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

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

(2.1) , используя угол градиента ɸ , извлечь из 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 "= (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 _мин . . .q _макс ] [с _мин . . . с _макс ]

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

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

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

х '= r cos (α)

у '= г sin (α)

для ( ϴ = ϴ _min ; ϴ ≤ ϴ _max ; ϴ ++ )

для ( s = s _min ; s ≤ s _max ; s ++ )

x _c = x - (x'cos (ϴ) - y'sin (ϴ)) s

y _c = y - (x'sin (ϴ) + y'cos (ϴ)) s

++ (A [x _c ] [y _c ] [ϴ] [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
^ Jaulin, L .; Базель, С. (2013). Извлечение формы изображения с использованием интервальных методов (PDF) . In Proceedings of Sysid 2009, Сен-Мало, Франция.
^ Мерлин, PM; Фарбер, ди-джей (январь 1975 г.). «Параллельный механизм обнаружения кривых на изображениях». Транзакции IEEE на компьютерах . С-24 (1): 96–98. DOI : 10.1109 / tc.1975.224087 . ISSN 0018-9340 .
^ Л. Дэвис, «Иерархические обобщенные преобразования Хафа и обобщенные преобразования Хафа на основе линейных сегментов» , Техасский университет компьютерных наук, ноябрь 1980 г.
↑ JA Heather, Xue Dong Yang, «Пространственная декомпозиция преобразования Хафа» , 2-я канадская конференция по компьютерному зрению и зрению роботов, 2005.
^ Баллард и Браун, раздел 4.3.4, Сонка и др., Раздел 5.2.6
^ AA Kassim, T. Tan, KH Tan, "Сравнительное исследование эффективных обобщенных методов преобразования Хафа", Image and Vision Computing, Volume 17, Issue 10, Pages 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
Реализация обобщенных преобразований Хафа в ПЛИС, IEEE Digital Library http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5382047&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp% 3Farnumber% 3D5382047
Реализация в MATLAB обобщенного преобразования Хафа http://www.mathworks.com/matlabcentral/fileexchange/44166-generalized-hough-transform

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

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

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

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

[5] JA Heather, Xue Dong Yang, «Пространственная декомпозиция преобразования Хафа» , 2-я канадская конференция по компьютерному зрению и зрению роботов, 2005.

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

[7] AA Kassim, T. Tan, KH Tan, "Сравнительное исследование эффективных обобщенных методов преобразования Хафа", Image and Vision Computing, Volume 17, Issue 10, Pages 737-748, август 1999

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

[1]