Transformata Hougha – wykrywanie linii prostych

Cześć
Jestem świeżo po Warszawskich Dniach Informatyki, a głowa boli od nadmiaru informacji, więc weźmiemy coś prostego. Dzisiaj będzie o wykrywaniu linii prostych, a posłuży nam do tego transformata Hougha w najprostszej postaci. Poniżej wstawiam wam ciekawe zajawki. Pierwszy filmik pokazuje samochodzik robot, który trzyma się swojego pasa. Drugi filmik pokazuje trochę większy samochodzik i wykrywanie pasów drogowych, tak więc jak zastanawiacie się na jakiej zasadzie działa autopilot w samochodach Tesli to macie już część odpowiedzi. Ostatni filmik pokazuje śledzienie oka (a dokładnie koła) przy użyciu zmodyfikowanej transformaty Hougha.

Teoria

Do działania algorytmu jako wejście musimy podać obraz po zastosowaniu algorytmu wykrywania krawędzi i binaryzacji. Można zastosować wykrywanie krawędzi metodą Prewitt, Sobla lub Laplaca, które opisywałem już tutaj. Jednak lepsze efekty daje zastosowanie wykrywanie krawędzi algorytmem Cannego, którego opis pojawi się niebawem na blogu.

Prosta kierunkowa

Rozważmy teraz najprostsze równanie linii, znane wam zapewne z podstawówki y= ax + b . Niżej na wizualizacji mamy dwa obrazy. Ten po lewej na którym wykrywamy linię z zaznaczonymi dwoma punktami  P_{1}, P_{2} na linii y = -1x+3, a po prawej stronie mamy przestrzeń parametrów. Wartości punktów podstawiamy do równania prostej i dostajemy równanie prostej od parametrów a i b, dzięki czemu dostajemy linię S_{1} i S_{2}

Wyszukujemy przecięcia linii poprzez podstawienie lewej strony do prawej. Dostajemy wynik zgodnie z założoną wcześniej linią.

Stosowane równanie linii prostej ma dwa zasadnicze problemy. Brak możliwości przedstawienia linii pionowej i przy próbie przedstawienia linii prawie pionowej wartości parametrów a i b rosną do nieskończoności.

Prosta biegunowa

Do rozwiązania problemów przedstawionych wyżej, używa się równania prostej w postaci biegunowej. Zmienna r oznacza odległość prostej od środka układu, a zmienna \varphi oznacza kąt jaki tworzy oś ox z prostą łączącą środek układu z prostą. Całą resztę liczy się podobnie jak w przypadku prostej kierunkowej.

Głosowanie

Oczywiście wiadomo, że pikseli z krawędziami na obrazie będzie więcej, nie wszystkie muszą być na prostej, lub na obrazie możemy mieć kilka prostych. Dlatego powstała idea głosowania na prostę. Do tego celu używamy akumulatora, to taka duża tablica dwuwymiarowa, gdzie współrzędnymi są r i \varphi. Oczywiście pojedyncza komórka akumulatora nazywana często koszykiem nie odpowiada jednej prostej, a wielu prostym o bardzo podobnym r i \varphi, co jest zależne od dokładności. Podczas głosowania każdy piksel oddaje głos na wiele prostych przechodzących przez ten punkt, czyli tłumacząc na bardziej zrozumiały język, dla każdego piksela rysujemy falkę w akumulatorze.

Oczywiście linia jest tam gdzie koszyk ma największą liczbę głosów, lub gdzie koszyki mają więcej głosów niż zadany próg.

Głosy na tą samą prostą mogą wpadać do obocznych koszyków. O dziwo zwiększanie dokładności akumulatora w nieskończoność nie daje lepszych wyników, a nawet je pogarsza. W takim przypadku należało by zmniejszyć dokładność akumulatora, można też „rozmyć” akumulator czyli zastosować splot z funkcją Gaussa.

Tutaj pokazane jest jak to działa w praktyce.

Praktyka

Uzbrojeni w teoretyczną wiedzę teoretycznie powinniście być w stanie zaimplementować ten algorytm. Jednak możecie napotkać na pewne praktyczne problemy.

Wielkość akumulatora

Wiadomo że zmienne mogą przyjąć wartość 0^{\circ}\leq \varphi \leq 360^{\circ}, -R \leq r \leq R, gdzie R to przekątna obrazu. Czy aby na pewno? Właśnie nie koniecznie, nie potrzebna nam jest jedna ćwiartka obrotu, gdyż te linie nigdy nie najdą na obszar obrazu. Możemy cały ten obszar przyciąć na dwa sposoby:

Możemy przyciąć ostatnią ćwiartkę -90^{\circ}\leq \varphi \leq 180^{\circ}, przy tak postawionym zakresie możemy też uciąć ujemną część przestrzeni r gdyż wszystkie linie da się przedstawić za pomocą dodatnich promieni. 0 \leq r \leq R

Drugi sposób to drastyczniejsze przycięcie obrotu 0^{\circ}\leq \varphi \leq 180^{\circ}, jednak zostawiamy ujemny zakres promienia -R \leq r \leq R, aby pokryć dodatkową uciętą ćwiartkę obrotu.

Oba podejścia mają swoje wady i zalety. Całą przestrzeń trzeba jeszcze poszatkować na koszyki, najlepiej jest sparametryzować ilość koszyków w pionie i poziomie.

Przeliczanie indeksów

Leżeli już mamy odpowiednio podzielony akumulator na koszyki, to musimy jeszcze napisać funkcję, która przekształca nam wartości r\ \varphi na odpowiednie indeksy tablicy akumulatora i na odwrót, czyli dla indeksów akumulatora dostajemy jakieś wartości r\ \varphi, które reprezentują koszyk.
Z doświadczenia wiem, że lepiej jest rozpisać sobie prosty przykład na kartce i napisać testy jednostkowe sprawdzające działanie tej funkcji (sprawdzając przy okazji czy nie zaimplementowaliście lepiej niż policzyliście).

Koniec

Dzisiaj matematyki starczy. W kolejnej części artykułu opiszę jak uogólniać tą metodę aby wykrywać różne kształty. Opiszę również jak można optymalizować działanie programu. Dla chętnych, których interesuje implementacja podrzucam kod na GitHubie, który jakiś czas temu napisałem z kolegą na studiach. Od przedstawionego algorytmu tutaj rożni go sposób głosowania, który został zoptymalizowany (o tej optymalizacji będzie w następnym artykule).

One Pingback/Trackback

    31 March 2017 at 10:03am
    Transformata Hougha – wykrywanie linii prostych by ...
  • dotnetomaniak.pl