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

Перетворення Гафа — це методики виявляння об'єктів, критичний крок у багатьох втіленнях комп'ютерного бачення та добування даних із зображень. Зокрема, рандомізо́ване перетво́рення Га́фа (англ. Randomized Hough transform) — це ймовірнісний варіант класичного перетворення Гафа, який широко використовують для виявляння кривих (прямих, кіл, еліпсів тощо). Основна ідея перетворення Гафа (ПГ, англ. HT) полягає у втіленні процедури голосування для всіх потенційних кривих на зображенні, й після завершення цього алгоритму криві, які існують на зображенні, матимуть відносно високі оцінки голосування. Рандомізоване перетворення Гафа (РПГ, англ. RHT) відрізняється від ПГ тим, що воно намагається уникнути проведення обчислювально витратного процесу голосування для кожного ненульового пікселя на зображенні, використовуючи геометричні властивостей аналітичних кривих, і відтак підвищити часову ефективність та знизити вимоги первинного алгоритму до обсягу зберігання.

Мотив

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

Втілення

У порівнянні з ПГ, РПГ використовує той факт, що деякі аналітичні криві можливо однозначно визначити певною кількістю точок на них. Наприклад, пряму можливо визначити двома точками, а еліпс (або коло) — трьома. Для ілюстрування основної ідеї РПГ можливо використати випадок виявляння еліпса. Весь процес загалом складається з трьох етапів:

1. Допасувати еліпси випадково вибраними точками.
2. Уточнити накопичувальний масив та відповідні оцінки.
3. Вивести еліпси з оцінками, вищими за певний попередньо визначений поріг.

Допасовування еліпса

Одне з поширених рівнянь для визначення еліпса: ${\displaystyle a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1}$

з обмеженням ${\displaystyle ac-b^{2}>0}$

Проте еліпс можливо однозначно визначити, якщо знати три точки на ньому, та дотичні до них.

РПГ починається з випадкового обрання трьох точок на еліпсі. Нехай це будуть ${\displaystyle X_{1}}$, ${\displaystyle X_{2}}$ та ${\displaystyle X_{1}}$. Перший крок — знайти дотичні до цих трьох точок. Їх можливо знайти, допасувавши пряму методом найменших квадратів для маленького вікна сусідніх пікселів.

Наступний крок — знайти точки перетину дотичних. Це можливо легко зробити, розв'язавши систему рівнянь прямих, знайдених на попередньому кроці. Тоді нехай точки перетину — ${\displaystyle T_{12}}$ та ${\displaystyle T_{23}}$, а середини відрізків ${\displaystyle X_{1}X_{2}}$ та ${\displaystyle X_{2}X_{3}}$ — ${\displaystyle M_{12}}$ та ${\displaystyle M_{23}}$. Тоді центр еліпса лежатиме на перетині ${\displaystyle T_{12}M_{12}}$ та ${\displaystyle T_{23}M_{23}}$. Знов-таки, координати точки перетину можливо визначати, розв'язуючи систему рівнянь прямих: докладний процес тут пропущено для стислості.

Нехай знайдені на попередньому кроці координати центру еліпса — ${\displaystyle (x_{0},y_{0})}$. Тоді цей центр можливо перенести до початку координат через ${\displaystyle x'=x-x_{0}}$ та ${\displaystyle y'=y-y_{0}}$, щоб уможливити спрощення рівняння еліпса до

${\displaystyle ax'^{2}+2bx'y'+cy'^{2}=1}$

Тепер ми можемо знайти решту параметрів еліпса, ${\displaystyle a}$, ${\displaystyle b}$ та ${\displaystyle c}$, підставивши координати ${\displaystyle X_{1}}$, ${\displaystyle X_{2}}$ та ${\displaystyle X_{3}}$ до рівняння вище.

Накопичування

Параметрами еліпса, визначеними на попередньому етапі, можливо відповідно уточнювати накопичувальний масив. На відміну від класичного перетворення Гафа, РПГ не зберігає як накопичувальний масив «ґратку засіків». Натомість, воно спершу обчислює подібності між нововиявленим еліпсом та тими, що вже зберігаються в накопичувальному масиві. Для обчислювання подібності можливо використовувати різні метрики. Якщо подібність перевищує певний попередньо визначений поріг, воно замінює еліпс у накопичувачі усередненням обох, і додає 1 до його оцінки. Інакше поміщує цей еліпс до порожнього положення в накопичувачі, й призначає оцінку 1.

Завершення

Щойно оцінка одного потенційного еліпса долає порогове значення, його визначають як присутній на зображенні (іншими словами, цей еліпс виявляється), і його слід усунути з зображення та накопичувального масиву, щоб алгоритм міг швидше виявити інші потенційні еліпси. Алгоритм завершується, коли число ітерацій досягає максимальної межі, або коли виявлено всі еліпси.

Псевдокод РПГ:

поки (ми знаходимо еліпси ТА не досягли максимальної епохи) { для (фіксованого числа ітерацій) { Знайти потенційний еліпс. якщо (еліпс схожий на еліпс у накопичувачі) то Замінити той що в накопичувачі усередненням обох, і додати 1 до оцінки; інакше Вставити еліпс до вільного місця в накопичувачі з оцінкою 1; } Обрати еліпс із найкращою оцінкою й зберегти його в таблиці найкращих еліпсів; Усунути з зображення пікселі найкращого еліпса; Спорожнити накопичувач; } 

Примітки

1. D.H. Ballard, "Generalizing the Hough Transform to Detect Arbitrary Shapes", Pattern Recognition, Vol.13, No.2, p.111-122, 1981 (англ.)
2. L. Xu, E. Oja, and P. Kultanan, "A new curve detection method: Randomized Hough transform (RHT)", Pattern Recog. Lett. 11, 1990, 331-338. (англ.)
3. S. Inverso, “Ellipse Detection Using Randomized Hough Transform”, www.saminverso.com/res/vision/EllipseDetectionOld.pdf, May 20, 2002 (англ.)