

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

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

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

Історія

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

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

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

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

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

Оберіть опорну точку y для фігури (зазвичай всередині неї). Для кожної граничної точки x обчисліть ɸ(x), напрямок градієнта, та r = y − x, як показано на рисунку. Збережіть r як функцію ɸ. Зауважте, що кожен індекс ɸ може мати багато значень r. Можливо зберігати або різниці координат між фіксованою опорною точкою та контурною точкою ((xc − xij), (yc − yij)), або як радіальну відстань та кут між ними (rij, αij). Коли це буде зроблено для кожної точки, R-таблиця повністю подаватиме шаблонний об'єкт. Також, оскільки ця фаза породження є оборотною, ми можемо використовувати її для виявляння присутності об'єкта в інших місцях зображення.
 Виявляння геометрії фігури для узагальненого перетворення Гафа




 i 

 ɸi 

 Rɸi


 1 

 0 

 (r11, α11) (r12, α12)... (r1n, α1n)


 2 

 Δɸ 

 (r21, α21) (r22, α22)... (r2m, α2m)


 3 

 2Δɸ 

 (r31, α31) (r32, α32)... (r3k, α3k)


 ... 

 ... 

 ...


Виявляння присутності об'єкта

Для кожного контурного пікселя x у зображенні знайти градієнт ɸ та збільшити всі відповідні точки x+r у накопичувальному масиві A (первинно встановленому до максимального розміру зображення), де r — запис таблиці з індексом ɸ, тобто r(ɸ). Ці точки запису дають нам кожне можливе положення опорної точки. Незважаючи на те, що може бути обчислювано деякі фіктивні точки, якщо об'єкт у зображенні присутній, то максимум матиме місце в опорній точці. Максимуми в A відповідають можливим примірникам фігури.

Узагальнення масштабу та спрямування

Для незмінного спрямування фігури накопичувальний масив був двовимірним, у координатах опорної точки. Щоби шукати фігури довільного спрямування θ та масштабу s, до опису фігури додають ці два параметри. Накопичувальний масив тепер складається з чотирьох вимірів, що відповідають параметрам (y, s, θ). Для збільшування цього простору більшої вимірності також можливо використовувати R-таблицю, оскільки різні спрямування та масштаби відповідають легко обчислюваним її перетворенням. Позначмо конкретну R-таблицю для фігури S через R(ɸ). Прості перетворення цієї таблиці дозволять їй виявляти масштабовані або повернуті екземпляри тієї ж фігури. Наприклад, якщо фігуру масштабовано на s і це перетворення позначено через Ts, тоді TsR(ɸ) = sR(ɸ), тобто всі вектори масштабуються на s. Також, якщо об'єкт повертають на θ, і позначують це перетворення через Tθ, то Tθ R(ɸ) = Rot{R(ɸ-θ)mod2π,θ}, тобто всі індекси збільшують на — θ за модулем 2π, знаходять відповідні вектори r, а потім повертають їх на θ. Ще одна властивість, яка буде корисною при описуванні побудови узагальнених перетворень Гафа, це зміна опорної точки. Якщо ми хочемо обрати нову опорну точку ỹ так, що y − ỹ = z, то зміну R-таблиці задають через R(ɸ) + z, тобто додають z до кожного вектора в таблиці.

Альтернативний спосіб з використанням пар контурів

Для зменшення простору параметрів можливо використовувати пари контурних пікселів. З використанням R-таблиці та описаних вище властивостей, кожен контурний піксель визначає поверхню в чотиривимірному накопичувальному просторі a = (y, s, θ). Два контурні пікселі в різних спрямуваннях описують ту саму поверхню, повернуту на однакову величину відносно θ. Якщо ці дві поверхні перетинаються, то точки, де вони перетинаються, відповідатимуть можливим параметрам a для фігури. Таким чином, теоретично можливо використовувати дві точки в просторі зображень, щоби зменшувати геометричне місце в просторі параметрів до єдиної точки. Проте труднощі пошуку точок перетину двох поверхонь у просторі параметрів робитимуть цей підхід неможливим для більшості випадків.

Складені фігури

Якщо фігура S має складену структуру, яка складається з частин S1, S2, .. SN, а точки відліку для фігур S, S1, S2, .. SN — y, y1, y2, .. yn відповідно, то для коефіцієнта масштабування s та спрямування θ узагальнене перетворення Гафа Rs(ɸ) задають через . Проблема з цим перетворенням полягає в тому, що вибір опорних точок може сильно впливати на точність. Щоби подолати це, Баллард запропонував згладжувати отримуваний накопичувач складеним згладжувальним шаблоном. Складений згладжувальний шаблон H(y) задають як складену згортку окремих згладжувальних шаблонів підфігур, . Тоді вдосконалений накопичувач задають через As = A*H, а максимуми в As відповідають можливим примірникам фігури.

Просторовий розклад

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

Втілення

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

:  або 

:  або 

:  або 

:  або 

Поєднуючи наведені вище рівняння, ми маємо:

: 

: 

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

: (0) Перетворити зразкове зображення фігури на контурне зображення за допомогою будь-якого алгоритму виявляння контурів, наприклад, виявляча контурів Кенні
: (1) Обрати опорну точку (наприклад, (xc, yc))
: (2) Провести лінію від опорної точки до межі
: (3) Обчислити ɸ
: (4) Зберегти опорну точку (xc, yc) як функцію ɸ у таблиці R(ɸ).

Виявляння:

: (0) Перетворити зразкове зображення фігури на контурне за допомогою будь-якого алгоритму виявляння контурів, наприклад виявляча контурів Кенні.
: (1) Встановити в первинний стан накопичувальну таблицю: Axcmin . . . xcmaxycmin . . . ycmax
: (2) Для кожної контурної точки (x, y)
:: (2.1) Використовуючи кут градієнта ɸ, добути з R-таблиці всі значення (α, r) за індексом ɸ.
:: (2.2) Для кожного (α,r) обчислити потенційні опорні точки:
::: xc = x + r cos(α)
::: yc = y + r sin(α)
:: (2.3) Збільшити лічильники (голосування):
:::: ++A(xcyc)
: (3) Можливі місця розташування контуру об'єкта задано локальними максимумами в Axcyc.
:: Якщо Axcyc > T, то в (xc, yc) розташовано контур об'єкта

Загальний випадок:

Припустімо, що об'єкт зазнав деякого обертання Θ та рівномірного масштабування s:

: (x′, y′) --> (x″, y″)
: x″ = (x′ cos(Θ) − y′ sin(Θ))s
: y″ = (x′ sin(Θ) + y′ cos(Θ))s
: Заміна x′ на x″ та y′ на y″:
: xc = x − x″ або xc = x − (x′ cos(Θ) − y′ sin(Θ))s
: yc = y − y″ або yc = y − (x′ sin(Θ) + y′ cos(Θ))s

: (1) Встановити у первинний стан накопичувальну таблицю: Axcmin . . . xcmaxycmin . . . ycmaxqmin . . . qmaxsmin . . . smax
: (2) Для кожної контурної точки (x, y)
:: (2.1) Використовуючи її кут градієнта ɸ, отримати всі значення (α, r) з R-таблиці
:: (2.2) Для кожного (α, r) обчислити потенційні опорні точки:
:::: x′ = r cos(α)
:::: y′ = r sin(α)
:::: for(Θ = Θmin; Θ ≤ Θmax; Θ++)
::::: for(s = smin; s ≤ smax; s++)
:::::: xc = x − (x′cos(Θ) − y′sin(Θ))s
:::::: yc = y − (x′sin(Θ) + y′cos(Θ))s
:::::: ++(AxcycΘs)
: (3) Можливі розташування контуру об'єкта задано локальними максимумами в AxcycΘs
: Якщо AxcycΘs > T, то в (xc, yc) розташовано контур об'єкта, який зазнав повороту Θ та був масштабованим на s.

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

Переваги

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

Недоліки

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

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

Див. також

* Перетворення Гафа
* Рандомізоване перетворення Гафа
* Перетворення Радона
* 
* 

Примітки


Посилання

* Втілення 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  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

