Transformata Hougha: Znalezienie ukrytych linii i okręgów w obrazach z szumem

Problem: Znalezieniekształtów w polu pikseli krawędziowych

Zastosowanie detektora krawędzi, takiego jak Canny, do fotografii drogi, parkingu lub stosu monet zwraca nasz uwagę na rozrzut pojedynczych pikseli krawędziowych — punktów, a nie linii czy okręgów. Niektóre z tych punktów rzeczywiście leżą poziomo na oznaczeniach drogowych lub obrzeżach monet; inne to szum, przerwy lub niespokojne elementy. Pytanie, które odpowiada transformacja Hougha, pierwszy opatentowana w 1962 roku przez Paul Hougha i późniejsza zgenerymalizowana dla dowolnych kształtów, brzmi: dana ta sciana pikseli krawędziowych, które z nich są zgodne z leżeniem na jednej linii lub jednym okręgu, nawet jeśli ta linia czy okrąg jest przerwany, częściowo ukryty lub zagłębiony w szum?

Naiwna metoda — poszukiwanie po pikselach połączeń równoległych — szybko nieudolnie radzi sobie z szumem i przerwami, ponieważ brak jest bezpiecznego sposobu na lokalne określenie, czy przerwa w linii oznacza „linia kończy się tutaj” czy „linia kontynuuje się, ale ta sekcja jest brakująca”. Transformacja Hougha unika tego całkowicie za pomocą ciekawego zmiany perspektywy: zamiast poszukiwania linii w przestrzeni pikseli obrazu, szuka ich w przestrzeni parametrów linii.

Linie jako Punkty: Kluczowe Przełomowe Przejęcie Wraz z Prostranstwem Parametrycznym

Linia jest obecnie opisana przez nachylenie i przesunięcie, y = mx + b, ale Hough używa innej, lepiej zachowującej się parametryzacji, która unika problemu pionowych linii mających nieskończoną nachylenie: postać polarna ρ = x·cos(θ) + y·sin(θ), gdzie ρ (rho) to prostopadła odległość od początku obrazu do linii, a θ (theta) jest kątem tej prostopadłości. Każda możliwa prosta w obrazie odpowiada dokładnie jednemu punktowi (ρ, θ) w tym dwuwymiarowym przestrzeni parametrycznej, i odwrotnie.

Oto kluczowe przełomowe przejęcie, które sprawia, że cała metoda działa: pojedynczy piksel krawędziowy na pozycji (x, y) w samotności nie definiuje linii — ale ogranicza, jakie linie mógłby on należeć. Dla każdego kąta θ od 0° do 180° istnieje dokładnie jedna wartość ρ, która sprawia, że równanie jest prawdziwe dla tego konkretnego (x, y). Narysowanie ρ w zależności od θ dla wszystkich możliwych kątów tworzy sinusoidalną krzywą w przestrzeni parametrycznej — nie pojedynczy punkt, ale cała krzywa, reprezentująca każdą linię, która mogłaby przechodzić przez ten jeden piksel.

Teraz powtarzaj to dla każdego piksela krawędziowego w obrazie, a coś zaskakującego dzieje się: jeśli kilka pikseli krawędziowych rzeczywiście leży na tej samej prostej, ich oddzielne sinusoidalne krzywe w przestrzeni parametrycznej przecinają się we wspólnym punkcie (ρ, θ), ponieważ ten punkt jest jedyną opisem linii zgodnym z wszystkimi nimi. Punkty nie leżące na wspólnej linii tworzą krzywe, które przecinają się przypadkowo i nie wzmacniają siebie.

Akumulator: Przekształcanie przecięć w głosy

W praktyce ta szukanie przecięć jest zaimplementowane jako system głosowania przy użyciu tablicy 2D o nazwie akumulator, która ma jedno wymiar dla dyskretnych wartości ρ i jedno dla dyskretnych wartości θ. Algorytm przetwarza piksele krawędziowe jeden po drugim: dla każdego piksela oblicza ρ dla każdego kandydatu θ (zazwyczaj z krokiem co stopni) i inkrementuje odpowiedniego akumulatora komórki o jedno — głosując za kombinację (ρ, θ), która jest uważana za prawdopodobną linię.

Po tym, jak każdy piksel krawędziowy zakończył głosowanie, komórki w akumulatorze z niezwykle wysokim licznikiem głosów odpowiadają kombinacjom (ρ, θ), które zgadzają się wiele piksele krawędziowych — inaczej mówiąc, rzeczywiste linie na obrazie. Algorytm przeszukuje akumulator w poszukiwaniu lokalnych maksimum powyżej wybranego próg głosowania i zwraca każdą taką komórkę jako wykrytą linię. Kluczowe jest, że ten proces głosowania jest naturalnie odporny na braki i średnie szumy: zniszczona oznaczenie drogi nadal przyczynia się do wszystkich głosów pikseli krawędziowych tej samej komórce akumulatora, więc linię wykrywa nawet jeśli nie ma jednego ciągłego ciągu pikseli bez braków na obrazie. W przeciwieństwie do tego, izolowane piksele szumu krawędziowego głosują w różnych (ρ, θ) komórkach i rzadko zbierają wystarczającą liczbę głosów w jednej komórce, aby przekroczyć próg wykrywania.

Standardowy transformator Hougha linii zgłasza nieskończone linie (parę ρ, θ bez początku ani końca), co często jest więcej niż potrzebujesz. Popularna wersja zmienna, transformator Hougha probabilistyczny, losowo próbuje tylko podzbior edge pikseli dla efektywności i dodatkowo śledzi i łączy połączone sekcje na każdym wykrytym linii, zwracając skończone segmenty liniowe z rzeczywistymi (x1, y1) do (x2, y2) końcowymi punktami, oraz dwa dodatkowe parametry: minimalna długość sekcji poniżej której wykrycie jest odrzucone, i maksymalny brak, który nadal może być przekroczony jako jedno ciągłe segment.

Rozszerzanie Idei na Okręgi

Ten sam zasada głosowania prosi się o rozszerzenie bezpośrednio do okręgów, opisanych trzema parametrami zamiast dwóch: współrzędnymi środka (a, b) i promieniem r, spełniającymi równanie (x−a)² + (y−b)² = r². W teorii, to oznacza akumulator trójwymiarowy indeksowany przez (a, b, r), który jest znacznie droższy do wypełnienia i wyszukania niż dwuwymiarowy akumulator linii, ponieważ liczba komórek rośnie z zakresu możliwych promieni oraz rozmiarów obrazu.

Zaimplementowanie OpenCV, metoda Hough Gradient, zmniejsza tę kosztowość za pomocą strategii dwóch faz. Na pierwszym kroku używa ona kierunku gradientu na każdym pikselu brzegowym (gradient każdego punktu brzegowego wskazuje ku centrum lub od centrum dowolnego okręgu, na którym leży), aby głosować tylko dla dwuwymiarowych współrzędnych środka (a, b), co jest znacznie tańsze niż wyszukiwanie po wszystkich trzech parametrach jednocześnie. Po odkryciu kandydatów na centra, wykonuje drugą, skupioną fazę, aby wyznaczyć najlepszy dopasowany promień dla każdego kandydata na środek, sprawdzając, jak dobrze piksele brzegowe w różnych odległościach od tego centrum się zgadzają. Ta dwufazowa strategia jest powodem, dla którego cv2.HoughCircles przyjmuje osobne parametry próg dla wykrywania centrów (param2) i wewnętrznie korzysta z detekcji krawędzi Canny-stylu jako etapu przetwarzania (kontrolowanego przez parametr param1), oraz parametr minDist, aby uniknąć raportowania osobnych nadmiernych okręgów z powodu bliskich sygnałów szumu.

Gdzie rzeczywiście stosuje się transformację Hougha

Dzięki temu, że jasno toleruje przerywania, częściowe zablokowanie i średnie szumy, transformacja Hougha pozostaje praktycznym narzędziem nawet po kilku dekadach od jej wynalezienia, szczególnie w ograniczonych, strukturalnych ujęciach, gdzie kształty poszukiwane są z góry znane. Wykrywanie marzeń drogowych w wcześniejszych systemach asystencji kierowcy używało bezpośrednio detekcji linii Hougha na krawędziach Canny z kamery skierowanej do przodu. Zastosowania skanowania dokumentów wykorzystują ją do znalezienia czterech głównych krawędzi strony dla poprawy perspektywy. Kontrola jakości w przemyśle wykorzystuje detekcję okręgów Hougha do liczenia i zweryfikowania obecności dziur, gwoździ lub kapeluszy na linii produkcji, a nadal jest standardowym przykładem klasyowym dla liczenia monet czy wykrywania oczu w portrecie. Jej głównym ograniczeniem jest to, co można się spodziewać od metody opartej na znanych parametrycznych kształtach: wykrywa linie i okręgi wiarygodnie, ale nie ma prostej metody do wyszukiwania ogólnych lub nieprawidłowych konturów, co jest obszarem, w którym dominują tracenia konturu i, w współczesnych przepływnościach danych, detektorzy obiektów nauczonech zamiast tego.

Często zadawane pytania