Узагальнене перетворення Гафа

Узага́льнене перетво́рення Га́фа (УПГ , англ. generalized Hough transform, GHT), представлене Даною Г. Баллард^[en] 1981 року, — це видозміна перетворення Гафа з використанням принципу зіставляння з шаблоном^[en].^[1] Перетворення Гафа первинно було розроблено для виявляння аналітично визначених фігур (наприклад, прямих, кіл, еліпсів тощо). У цих випадках ми маємо знання про фігуру й прагнемо з'ясувати її розташування та спрямування в зображенні. Ця видозміна дозволяє використовувати перетворення Гафа для виявляння довільного об'єкта, описаного його моделлю.

Задачу знаходження об'єкта (описаного моделлю) у зображенні можливо розв'язувати, знаходячи положення моделі в зображенні. За допомогою узагальненого перетворення Гафа задача знаходження положення моделі перетворюється на задачу знаходження параметра перетворення, який відображує модель у зображення. За значенням параметра перетворення можливо визначити положення моделі в зображенні.

Первинне втілення УПГ використовувало інформацію про контури для визначання відображення з напрямку контурної точки до опорної точки фігури. У випадку бінарного зображення, де пікселі можуть бути або чорними, або білими, кожен чорний піксель зображення може бути чорним пікселем бажаного шаблону, створюючи таким чином геометричне місце опорних точок у просторі Гафа. Кожен піксель зображення голосує за відповідні йому опорні точки. Точки максимума простору Гафа вказують на можливі опорні точки шаблона в зображенні. Цей максимум можливо знаходити, скануючи простір Гафа, або розв'язуючи послаблену систему рівнянь^[en], кожне з яких відповідає чорному пікселю.^[2]

Історія

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

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

Теорія узагальненого перетворення Гафа

Щоб узагальнити алгоритм Гафа на неаналітичні криві, Баллард визначає наступні параметри для узагальненої фігури: a={y,s,θ}, де y — опорна точка відліку фігури, θ — її спрямування, а s = (s_x, s_y) описує два ортогональні масштабні коефіцієнти. Алгоритм може обчислювати найкращий набір параметрів для заданої фігури з піксельних даних контурів. Ці параметри не мають рівноправного статусу. Розташування опорної точки відліку, y, описують у термінах шаблонної таблиці, яку називають R-таблицею можливих напрямків контурних пікселів. Обчислення додаткових параметрів s та θ відтак досягають прямими перетвореннями цієї таблиці. Ключовим узагальненням на довільні фігури є використання інформації про напрямок. За будь-якої фігури та фіксованої опорної точки на ній, замість параметричної кривої, інформацію, що надають контурні пікселі, зберігають у вигляді R-таблиці на етапі перетворення. Для кожної контурної точки на перевірному зображенні властивості цієї точки шукають в R-таблиці, отримують опорну точку, й збільшують відповідну комірку в матриці, званій накопичувальною матрицею (англ. Accumulator matrix). Комірка з максимумом «голосів» у накопичувальній матриці може бути можливою точкою існування фіксованої опорної точки об'єкта в перевірному зображенні.

Побудова R-таблиці

Оберіть опорну точку y для фігури (зазвичай всередині неї). Для кожної граничної точки x обчисліть ɸ(x), напрямок градієнта, та r = y − x, як показано на рисунку. Збережіть r як функцію ɸ. Зауважте, що кожен індекс ɸ може мати багато значень r. Можливо зберігати або різниці координат між фіксованою опорною точкою та контурною точкою ((x_c − x_ij), (y_c − y_ij)), або як радіальну відстань та кут між ними (r_ij, α_ij). Коли це буде зроблено для кожної точки, R-таблиця повністю подаватиме шаблонний об'єкт. Також, оскільки ця фаза породження є оборотною, ми можемо використовувати її для виявляння присутності об'єкта в інших місцях зображення.

i	ɸ_i	R_{ɸ_i}
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, y₁, y₂, .. y_n відповідно, то для коефіцієнта масштабування 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] запропонували метод, який включає рекурсивний поділ^[en] зображення на підзображення, кожне зі своїм власним простором параметрів, упорядкованих у квадродеревну структуру. Це призводить до підвищення ефективності пошуку кінцевих точок відрізків та кращої стійкості та надійності при виділянні ліній у зашумлених ситуаціях, за дещо збільшених витрат пам'яті.

Втілення

Втілення використовує такі рівняння:^[6]

x=x_{c}+x'\ \

або

\ \ x_{c}=x-x'

y=y_{c}+y'\ \

або

\ \ y_{c}=y-y'

\cos(\pi -\alpha )=x'/r\ \

або

\ \ x'=r\cos(\pi -\alpha )=-r\cos(\alpha )

\sin(\pi -\alpha )=y'/r\ \

або

\ \ 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 . . . y_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_max][s_min . . . s_max]

(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[x_c][y_c][Θ][s])

(3) Можливі розташування контуру об'єкта задано локальними максимумами в A[x_c][y_c][Θ][s]

Якщо A[x_c][y_c][Θ][s] > T, то в (x_c, y_c) розташовано контур об'єкта, який зазнав повороту Θ та був масштабованим на s.

Переваги та недоліки

Переваги

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

Недоліки

Воно має значні вимоги до обчислень та зберігання, які стають гострими, коли потрібно враховувати спрямування та масштаб об'єкта.

Пов'язана праця

Баллард запропонував використовувати інформацію про спрямування контурів, щоби зменшити витратність обчислень. Було запропоновано багато ефективних методик УПГ, таких як SC-GHT (використання нахилу, англ. slope, та кривини, англ. curvature, як локальних властивостей).^[7] Дейвіс та Ям^[8] також запропонували розширення праці Мерліна щодо обертово та масштабоінваріантного зіставляння, яке доповнює працю Балларда, але не включає використання Баллардом інформації про нахил контуру та складені структури

Див. також

Примітки

↑ D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol.13, No.2, p.111-122, 1981 (англ.)
↑ Jaulin, L.; Bazeille, S. (2013). Image Shape Extraction using Interval Methods (PDF). In Proceedings of Sysid 2009, Saint-Malo, France. (англ.)
↑ Merlin, P. M.; Farber, D. J. (January 1975). A Parallel Mechanism for Detecting Curves in Pictures. IEEE Transactions on Computers. C-24 (1): 96—98. doi:10.1109/t-c.1975.224087. ISSN 0018-9340. (англ.)
↑ L. Davis, "Hierarchical Generalized Hough Transforms and Line Segment Based Generalized Hough Transforms", University of Texas Computer Sciences, Nov 1980 (англ.)
↑ J.A. Heather, Xue Dong Yang, "Spatial Decomposition of the Hough Transform", The 2nd Canadian Conference on Computer and Robot Vision, 2005. (англ.)
↑ Ballard and Brown, section 4.3.4, Sonka et al., section 5.2.6 (англ.)
↑ A. A. Kassim, T. Tan, K. H. Tan, "A comparative study of efficient generalised Hough transform techniques", Image and Vision Computing, Volume 17, Issue 10, Pages 737-748, August 1999 (англ.)
↑ L. Davis and S. Yam, "A generalized hough-like transformation for shape recognition". University of Texas Computer Sciences, TR-134, Feb 1980. (англ.)