Перетво́рення Га́фа () — це методика виділяння ознак, вживана в , комп'ютерному баченні та цифровій обробці зображень. and Stockman, George. "Computer Vision", Prentice-Hall, Inc. 2001 Призначення цієї методики — знаходити недосконалі примірники об'єктів певного класу фігур за допомогою процедури голосування. Цю процедуру голосування виконують у , з якого кандидатури об'єктів отримують як локальні максимуми у так званому накопичувальному просторі (), явно створюваному алгоритмом для обчислення перетворення Гафа.
Класичне перетворення Гафа стосувалося встановлюванням прямих на зображенні, але пізніше його було розширено для встановлювання положень довільних фігур, найчастіше — кіл або еліпсів. Перетворення Гафа, яке сьогодні використовують повсюдно, було винайдено 1972 року та , які назвали його «узагальненим перетворенням Гафа» ()Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," Comm. ACM, Vol. 15, pp. 11–15 (January, 1972) на честь відповідного патенту Пола Гафа 1962 року.Hough, P.V.C. Method and means for recognizing complex patterns, U.S. Patent 3,069,654, Dec. 18, 1962 P.V.C. Hough, Machine Analysis of Bubble Chamber Pictures, Proc. Int. Conf. High Energy Accelerators and Instrumentation, 1959 Це перетворення було популяризовано у спільноті комп'ютерного бачення через статтю в журналі 1981 року під назвою «Узагальнення перетворення Гафа для виявляння довільних фігур».
Історія
Первинно його було винайдено для машинного аналізу фотографій бульбашкових камер (Гаф, 1959).
Перетворення Гафа було запатентовано 1962 року як та передано Комісії з атомної енергії США під назвою «Метод і засоби для розпізнавання складних моделей». У цьому патенті використано параметрування нахилу-відтину для прямих, що незграбно призводить до необмеженого простору перетворення, оскільки нахил може сягати нескінченності.
Параметрування ро-тета, повсюдно використовуване сьогодні, було вперше описано в
хоча воно вже було стандартом для перетворення Радона щонайменше з 1930-х років.
Варіацію О'Ґормана та Клоуза описано в
Розповідь про те, як було винайдено сучасний вигляд перетворення Гафа, наведено в
Теорія
В автоматизованому аналізі цифрових зображень часто виникає підзадача виявляння простих фігур, таких як прямі, кола або еліпси. У багатьох випадках як етап попередньої обробки можливо використовувати виявляч контурів, щоб отримувати точки або пікселі зображення, які знаходяться на потрібній кривій у просторі зображення. Проте через недосконалість даних зображення або виявляча контурів можуть бути відсутні точки або пікселі на бажаних кривих, а також просторові відхилення між ідеальною прямою/колом/еліпсом і шумними контурними точками, отриманими з виявляча контурів. З цих причин групувати виділені контурні ознаки у відповідний набір прямих, кіл або еліпсів часто нетривіально. Мета перетворення Гафа полягає у розв'язанні цієї проблеми, уможливлюючи групування контурних точок в об'єкти-кандидати шляхом виконання процедури явного голосування над набором параметрованих об'єктів зображення (Шапіро та Стокман, 304).
Виявляння прямих
Найпростіший випадок перетворення Гафа — виявляння прямих. У загальному випадку пряму можливо подати у вигляді точки (b, m) у просторі параметрів. Проте вертикальні прямі становлять проблему. Вони призводили б до необмежених значень параметра нахилу m. Таким чином, з обчислювальних міркувань Дуда й Гарт запропонували використовувати
де — відстань від початку координат до найближчої точки на прямій, а — кут між віссю та прямою, що сполучає початок координат із цією найближчою точкою.
Інтуїтивне розуміння для цього вигляду, подібно до рівняння площини, полягає в тому, що кожен вектор на прямій мусить бути перпендикулярним (ортогональним) цьому відрізкові довжини що йде від початку координат. Легко побачити, що точка перетину лінії цієї функції та цього перпендикуляра, який виходить з початку координат, перебуває в . Отже, для будь-якої точки на цій прямій вектор мусить бути ортогональним до вектора . Тож ми отримуємо, що для будь-якої точки на лінії цієї функції повинно виконуватися рівняння . Отже, . Оскільки , а , ми отримуємо . Оскільки , ми отримуємо остаточний вигляд .
Відтак, із кожною прямою зображення можливо пов'язати пару . Площину іноді називають простором Гафа () для множини прямих у двох вимірах. Це подання робить перетворення Гафа концептуально дуже близьким до двовимірного перетворення Радона. Насправді перетворення Гафа математично еквівалентне перетворенню Радона, але обидва перетворення мають різні обчислювальні інтерпретації, традиційно пов'язувані з ними.A short introduction to the Radon and Hough transforms and how they relate to each other. CiteSeerX.
Для заданої однієї точки на площині множина всіх прямих, що проходять через неї, відповідає синусоїдній кривій на площині (r, θ), унікальній для цієї точки. Множина з двох або більше точок, які утворюють пряму, даватиме перетин синусоїд на (r, θ) для цієї прямої. Таким чином, задачу виявляння можливо перетворити на задачу знаходження конкурентних кривих.
Імовірнісна інтерпретація
Для заданої фігури, параметрованої набором , що набуває значень у множині , званій простором цієї фігури (), перетворення Гафа можливо інтерпретувати як зворотне перетворення розподілу ймовірності в просторі зображення до простору фігури , й інтерпретувати виявляння фігури як оцінювання максимальної правдоподібності.
У явному вигляді, перетворення Гафа виконує наближене наївне баєсове висновування. Ми починаємо з рівномірного апріорного в просторі фігури. Ми розглядаємо лише позитивні свідчення та ігноруємо всі негативні, щоби могти виявляти частково затулені фігури.
Ми підсумовуємо логарифмічну правдоподібність у просторі фігури з точністю до адитивної сталої. Наївне баєсове припущення означає, що всі пікселі в просторі зображення надають незалежні свідчення, тож їхні правдоподібності перемножуються, тобто їхні логарифмічні правдоподібності додаються. Свобода в адитивній сталій дозволяє нам не виконувати жодних операцій над «пікселями тла» в просторі фігури.
Зрештою, ми виконуємо оцінку максимальної правдоподібності, обираючи піки логарифмічної правдоподібності в просторі фігури.
Втілення
Алгоритм перетворення Гафа для прямих оцінює два параметри, що визначають пряму. Простір перетворення має два виміри, й кожну точку в просторі перетворення використовують як накопичувач для виявляння або встановлювання прямої, описаної рівнянням . Кожна точка на виявлених у зображенні контурах вносить свій внесок у накопичувачі.
Розмірність накопичувача дорівнює числу невідомих параметрів, тобто двом, розглядаючи квантовані значення r та θ в парі (r, θ). Для кожного пікселя в (x, y) та його околу алгоритм перетворення Гафа визначає, чи є достатньо свідчення прямої в цьому пікселі. Якщо так, він розраховує параметри (r, θ) цієї прямої, а потім знаходить засік накопичувача, до якого потрапляють ці параметри, й збільшує значення цього засіку.
Шляхом знаходження засіків із найвищими значеннями, як правило, шляхом пошуку локальних максимумів у накопичувальному просторі, можливо виділяти найправдоподібніші прямі та зчитувати їхні (наближені) геометричні визначення (Шапіро та Стокман, 304). Найпростіший спосіб знаходити ці піки — застосовувати поріг якогось вигляду, але інші методики можуть видавати кращі результати за різних обставин — визначати, які прямі знайдено, а також скільки. Оскільки видані прямі не містять жодної інформації про довжину, на наступному кроці часто необхідно знайти, які частини зображення збігаються з якими прямими. Крім того, через похибки недосконалості на етапі виявляння контурів зазвичай будуть похибки в накопичувальному просторі, що може робити пошук відповідних піків і, отже, відповідних прямих, нетривіальним.
Кінцевий результат перетворення Гафа для прямих — двовимірний масив (матриця), подібна до накопичувача, — одним виміром цієї матриці є квантований кут θ, а іншим — квантована відстань r. Кожен елемент цієї матриці має значення, що дорівнює сумі точок або пікселів, розташованих на прямій, поданій квантованими параметрами (r, θ). Отже, елемент із найвищим значенням вказує пряму, яка найбільше подана у вхідному зображенні.
Приклади
Приклад 1
Розгляньмо три точки даних, показані тут як чорні крапки.
Через кожну точку даних відкладено декілька прямих, які проходять під різними кутами. Їх тут показано різними кольорами. Перетворення Гафа накопичує внески від усіх пікселів у виявленому контурі. Для кожної прямої існує опорний відрізок, який перпендикулярний до неї й перетинає початок координат. У кожному випадку однин з них показано стрілкою. Розраховують довжину (тобто перпендикулярну відстань до початку координат) і кут кожного опорного відрізка. Довжини та кути наведено в таблиці під діаграмами.
З цих розрахунків видно, що в усіх випадках опорний відрізок під кутом 60° має схожу довжину. Отже, зрозуміло, що відповідні прямі (сині на зображенні вище) дуже схожі. Таким чином, можливо вважати, що всі точки лежать близько до синьої прямої.
Приклад 2
Нижче наведено інший приклад, який показує результати перетворення Гафа на растровому зображенні, що містить дві товсті прямі.
Результати цього перетворення було збережено в матриці. Значення комірок подає кількість кривих через кожну точку. Вищі значення комірок відображено яскравіше. Дві виразно яскраві плями — параметри Гафа цих двох прямих. За положенням цих плям можливо визначити кут і відстань від центру зображення цих двох прямих у первинному зображенні.
Варіації та розширення
Використання напрямку градієнта для зниження числа голосів
Вдосконалення, запропоноване О'Ґорманом і Клоузом, можливо використовувати для виявляння ліній, якщо брати до уваги, що локальний градієнт яскравості зображення обов'язково буде ортогональним до контуру. Оскільки виявляння контурів зазвичай передбачає обчислення величини градієнта яскравості, напрямок градієнта часто знаходять як побічний ефект. Якщо задана точка з координатами (x, y) і справді перебуває на прямій, то локальний напрямок градієнта дає параметр θ, що відповідає згаданій лінії, й тоді негайно отримується параметр r. (Шапіро та Стокман, 305) Напрямок градієнта можливо оцінювати з точністю до 20°, що скорочує синусоїду від повних 180° до приблизно 45°. Це зменшує час обчислення та має цікавий ефект зменшення кількості марних голосів, відтак покращуючи видимість піків, що відповідають реальним прямим на зображенні.
Ядрове перетворення Гафа
Фернандес та Олівейра запропонували вдосконалену схему голосування для перетворення Гафа, яка дозволяє програмному втіленню досягати продуктивності реального часу навіть на відносно великих зображеннях (напр., 1280×960). Ядрове перетворення Гафа () використовує те саме параметрування , запропоноване Дудою й Гартом, але працює з кластерами приблизно колінеарних пікселів. Голосування для кожного кластера проводять з використанням спрямованого еліптично-гауссового ядра, яке моделює невизначеність, пов'язану з найкращим допасовуванням прямої до відповідного кластера. Цей підхід не лише значно покращує продуктивність цієї схеми голосування, але також створює набагато чистіший накопичувач і робить перетворення стійкішим до виявляння помилкових ліній.
Тривимірне ядрове перетворення Гафа для виявляння площин