Ідея алгоритму Хафа наступна. З курсу аналітичної геометрії ми знаємо, що існує багато типів рівнянь прямої лінії. Найбільш поширеним є рівняння з кутовим коефіцієнтом $y=ax+b$, тобто пряма лінія повністю задається набором двох параметрів $(a,b)$. Тоді в новій системі координат $aOb$ кожна пряма лінія задається точкою. Така площина називається простором Хафа, з точки зору математики простір Хафа є фазовим простором. В алгоритмі Хафа зручніше користуватися рівнянням прямої лінії у полярних координатах $r=x \cos \theta+ y \sin \theta$, оскільки тоді не потрібно окремо розглядати вертикальні і горизонтальні лінії.
В загальному випадку для кожної точки $(x_0,y_0)$, ми можемо визначити сім'ю прямих ліній якi проходить через цю точку: $$ r_\theta=x_0\cos \theta+ y_0 \sin \theta $$ Кожна пара параметрів $(r_\theta,x_\theta)$ визначає множину всіх ліній що проходять через точку $(x_0,y_0).$ Якщо для даної точки $(x_0,y_0)$ ми побудуємо сім'ю ліній які проходять через цю точку ми отримуємо синусоїду. Наприклад для $x_0=8$ i $y_0=6$ ми отримуємо ( у фазовому просторі $\theta - r$):
Всі прямі які проходять через дану точку задаються деякою кривою в цьому фазовому просторі. Якщо розглянути фазову криву іншої точки цієї ж прямої, то ці криві обов'язково перетнуться. Якщо три точки лежать на одній прямій то відповідні фазові криві перетнуться в деякій точці. Ми можемо зробити ту ж саму операцію вище для всіх точок зображення. Якщо криві двох різних точок перетинаються в координатній площині $\theta - r$, це означає, що обидві точки належать одній прямій лінії. Наприклад, для попереднього прикладу, побудуємо для ще двох точок: $x_1 = 4, y_1 = 9 і x_2 = 12, y_2 = 3,$ отримаємо:
Отже, пряма лінія може бути виявлена підрахунком кількості перетинів між кривими. Чим більше кривих перетинається, тим більше точок прямої лінія, які відповідає цим перетинам, буде знайдено. Загалом, ми можемо визначити поріг мінімальної кількості перетинів, необхідних для виявлення лінії.
Алгоритм Хафа відстежує перетин між кривими для кожної точки бінарного зображення і кожен такий перетин підсумовується в окремому масиві який називається акамулятором. Якщо число перетинів в деякій точці $(\theta, r)$ перевищує задане порогове значення, то алгоритм визначає його як знайдену пряму лінію на зображенні з параметрами $(\theta, r)$ з яких вже можна відновити лінію в декартових координатах.
Ідея алгоритму Хафа може бути застосована також для виявлення кіл, еліпсів або інших кривих, які можна задати параметрично. Алгоритм також виявляє прямі і у випадку якщо деякі ділянки прямої втрачені. Основний недолік методу Хафа - він знаходить багато хибних ліній ( кіл) і для їхнього усунення потрібно або додатково обробляти масив акумуляторів, або вручну підлаштовувати параметри, що зменшує універсальність методу.
Немає коментарів:
Дописати коментар