Przekształcony Hough – Wikipedia

. Hough Transform to technika rozpoznawania form wymyślonych w 1959 roku przez Paula Hougha ^{[[[ Pierwszy ]} , będąc przedmiotem patentu ^{[[[ 2 ]} i używane w przetwarzaniu obrazów cyfrowych.

Najprostsza aplikacja umożliwia wykrycie linii obecnych na obrazie, ale można wprowadzić modyfikacje w tej technice w celu wykrywania innych form geometrycznych: jest to Uogólniona transformacja Hough Opracowany przez Richarda Dudy i Petera Hart w 1972 roku.

Problemem jest badania i wykrywanie linii, które ostatecznie byłyby obecne na obrazie analizowanym pomimo niedoskonałości obrazu: brakujące punkty (linia może być częściowo maskowana przez obiekt), szum. Transformacja Hough polega na reprezentowaniu każdego punktu zarysowego wykrytego w dwuwymiarowej przestrzeni parametrów:

• Linia charakteryzuje się dwoma parametrami, jest zatem reprezentowana przez punkt w tej przestrzeni parametrów;
• Jeśli weźmiemy pod uwagę wszystkie linie przechodzące przez punkt, obraz tego zestawu jest krzywą w przestrzeni parametrów.

Transformacja Hough z punktu na analizowanym obrazie jest krzywą przestrzeni parametrów odpowiadających wszystkim linii przechodzącym przez ten punkt.

Jeśli punkty są kolinearne, wszystkie krzywe przestrzeni parametrów są odcięte do punktu reprezentującego prawą.

Ze względu na obrazy obrazu wykryte punkty nie są doskonale wyrównane, dlatego krzywe nie są doskonale konkurujące. Metoda polega zatem na dyskretyzacji przestrzeni parametrów, przecinaniu jej na małe prostokąty i liczenie dla każdego prostokąta liczba przechodzących tam krzywej. W ten sposób budujemy tak -podsumowaną macierz akumulacji, Maxima Przemienniki tej macierzy odpowiadają prawdopodobnym wierszom.

Algorytm ma zatem trzy kroki:

• Dla każdego wykrytego punktu zarysu określenie odpowiedniej krzywej w przestrzeni przestrzeni;
• konstrukcja macierzy akumulacji z tych krzywych;
• Wykrywanie pików w macierzy akumulacji.

Równanie kartezjańskie prawa ( D ) może być napisane w swojej „normalnej” formie, która obejmuje współrzędne polarne ( R W th ) .

Początkowo Hough scharakteryzował linie swoim nachyleniem i pierwotnie rzędnym ^{[[[ Pierwszy ]} . Wadą tego podejścia jest to, że nachylenie maleje w kierunku nieskończoności, gdy prawo maleje w kierunku pionowego. W 1972 r. Duda i Hart zaproponowali parametryzację przez współrzędne polarne ( R W th ) ^{[[[ 3 ]} który był używany w sposób uniwersalny.

Linia ( D ) można scharakteryzować parametrami polarnymi ( R W th ) :

• R jest odległością od prawej strony pochodzenia odniesienia,
• th jest kąt prostopadły do ​​prawej z osi X .

Dane kontaktowe ( X W I ) Punkty tego prawego sprawdź równanie „normalne” SO:

R = X ⋅ cos ( th ) + I ⋅ grzech ( th )

Najpierw zakłada się, że jeśli linie lub segmenty linii będą obecne na obrazie, będą one częścią konturów obecnych na obrazie. Dlatego początkowo zaczynamy od zidentyfikowania wszystkich konturów tego obrazu, na przykład przy użyciu lokalnych pomiarów gradientu między wartościami pikseli wokół każdego punktu obrazu jako filtra kuszącego. Punkty obrazu przedstawiające najwyższe gradienty w ich sąsiedztwie, ogólnie dla obrazu (ustalony próg), albo w porównaniu z gradientami zwykle obecnymi w szerszej dzielnicy wokół punktu (próg dynamiczny), są najbardziej prawdopodobne do konturów do konturów tego obrazu.

W ten sposób zidentyfikowano każdy punkt konturów ( X W I ) Następnie zezwoli na rzut w płaszczyźnie (przekształcony plan) współrzędnych polarnych wszystkich linii przechodzących przez ten punkt. Równania linii przechodzących do każdego z tych punktów ( X W I ) są zatem reprezentowane przez parę ( R W th ) weryfikacja

R = X ⋅ cos ( th ) + I ⋅ grzech ( th )

W punkcie ( X W I ) Zarys, zatem dopasowujemy krzywą R = F ( th ) Lub th Weź wszystkie możliwe wartości od 0 do 2 Liczba Pi rad (0 do 360 ° ), z

F ( th ) = X ⋅ cos ( th ) + I ⋅ grzech ( th ).

Ta krzywa jest sinusoid. W praktyce różnimy się th od 0 do Liczba Pi rad (0 do 180 ° ) i rozważamy promień algebraiczny (dodatni lub negatywny). Parametr R przyjmie wartości pomiędzy – R I + R Lub R jest dużą przekątną obrazu: R = √ L ² + H ² W L będąc szerokością obrazu i H jego wzrost.

Kiedy krzywe R ( th ) Odpowiadając dwa punkty, punkt przecięcia charakteryzuje prawe przejście przez dwa punkty.

Więc w planie ( th W R ) , kojarzymy z każdym punktem gęstość odpowiadającą liczbie krzywej, która tam przechodzi. Im wyższa gęstość, tym więcej jest wokół tego prawa. Prawo jest zatem najprawdopodobniej segmentem na obrazie.

W praktyce przekształcona przestrzeń Hough będzie reprezentowana przez obraz, którego odcięcie będzie kąty th , którego rozkazuje wartości R i czyje intensywność w dowolnym momencie ( th W R ) to liczba wystąpień ( th W R ) Z oryginalnego obrazu. Nie powstaje tutaj hipoteza ciągłości prawej linie lub segmentów obrazu początkowego, co sprawia, że ​​przekształcony jest solidny do braku punktów: częściowe maskowanie linii i szum na obrazie.

Wartości th może być dyskretyzowane na przykład w stopniach (w zależności od pożądanej dokładności) i wartości R W pikselach reprezentujących odległość (zawsze niższa w wartości bezwzględnej do średnicy obrazu początkowego), częstotliwość ograniczona liczbą punktów wybranych w konturach obrazu początkowego.

Algorytm jest zatem w pseudo-kodzie:

Bez względu na: i% obraz macierzy
J ← Kontury i% np.
Definiuje: δ% bez dyskretyzacji
1. m ← 0% inicjalizacja macierzy akumulacji
2. Dla każdego piksela (x, y)
3. dla θ od 0 do 180 z krokiem δ
4. ρ ← X*cos (θ) + y*sin (θ)
5. M (ρ, θ) ← M (ρ, θ) + 1
6. Koniec pętli
7. Koniec pętli
Wykrywanie pików M 

Przykład transformacji Hough.

W transformacji Hough, więc -podnoszony standardowo przekształcony w Hough lub SHT, każda linia jest wektorem współrzędnych parametrycznych:

• th : l’angle;
• R : standard wektorowy (długość segmentu prostopadle do kątu w prawo th i przechodząc przez pochodzenie).

Przekształcając wszystkie możliwe linie, które przechodzą przez punkt, to znaczy poprzez obliczenie wartości R dla każdego th , Otrzymuje się pojedynczy sinusoid zwany „przestrzenią Hough”. Jeśli krzywe związane z dwoma punktami wycięte, miejsce, w którym odcinają się w przestrzeni Hough, odpowiada parametrom prawa, który łączy te dwa punkty.

Wykrywanie konturu obejmuje określenie gradientu kontrastu obrazu. W rzeczywistości kierunek tego gradientu jest prostopadły do ​​kierunku konturu. Zamiast rysować sinusoidów th różni się od 0 do 180 ° , możesz ograniczyć się do plaży wokół w ten sposób znalezionych orientacji. Ta metoda została zaproponowana przez O’Gormana i Clowesa w 1976 roku ^{[[[ 4 ]} i nazywa się GHT ( Transformacja Hough oparta na gradientach , przekształcony z hugh z gradientu).

Fernandes et oliveira ^{[[[ 5 ]} zaproponował poprawę przyspieszenia leczenia do tego stopnia, że ​​można przetwarzać obrazy w czasie rzeczywistym do 1280 × 960 pikseli. Metoda jest następująca:

• Grupują piksele konturowe wykryte w kanałach ( klastry ) Globalnie tworzące właściwe segmenty:
  • Łączą piksele w pobliżu, tworząc łańcuch,
  • Przechodząc prawe przejście przez końce każdego łańcucha, określają piksel najdalszego łańcucha i przecinają łańcuch na dwie części; Jeżeli pod-Chantas tworzą segment „bardziej liniowy”, podział jest zachowany; Ten krok odbywa się rekurencyjnie, zatrzymując minimalny rozmiar;
• Dla każdego łańcucha, poprzez regresję liniową, określają prawo i dyspersję wokół tego prawa:
  • Aby uniknąć problemu powiązanego z liniami pionowymi, umieszczają się w odniesieniu, którego oś osi X to prawo łączące końce,
  • Odchylenia standardowe oszacowane na pochodzeniu i uporządkowanej rzędnej są używane do określenia standardowych odchyleń na parametrach R I th ;
• Dla każdego łańcucha gromadzą się w klasyczny sposób, ale ograniczając się do „jądra eliptycznego Gaussa”: elipsa skoncentrowana na punkcie ( th W R ) charakterystyczne dla linii regresji i których małe i duże osie są określane przez odchylenia standardowe; Przypadek elipsy z pola definicji ([ – R ; + R ], [0; 180 °]) jest traktowane;
• Matryca akumulacji jest „wygładzona” przez produkt splotowy z jądrem Gaussa 3 × 3: pomaga to złagodzić bardzo małe izolowane szczyty i zbierać małe pobliskie szczyty.

Ta metoda nazywa się KHT ( Transformacja Hough na bazie jądra , przekształcone z hugh z jąder).

Metoda może mieć zastosowanie do dowolnej krzywej reprezentowanej przez równanie kartezjańskie lub parametryczne.

Wykrywanie kół [[[ modyfikator |. Modyfikator i kod ]

Metoda wykrywania koła jest również ochrzczona HCT ( Hough Circle Transform ) .

W tej metodzie okrąg jest opisany przez jego równanie kartezjańskie:

( X – A ) ² + ( I – B ) ² = R ²

Lub

• punkt współrzędnej ( A W B ) jest środkiem koła;
• R jest działem.

W kosmosie ( A W B W R ) , okrąg charakteryzuje się punktem. Zestaw kręgów przechodzących przez punkt M ( X W I ) Biorąc pod uwagę stożek szczytowy ( A = X W B = I W R = 0) To osie R . „Dobry kandydat” odpowiada przecięciu kilku stożków.

Jeśli promień pożądanego koła jest znany, możemy być umieszczone w płaszczyźnie ( A W B ) . W tym planie wszystkie koła przechodzą M jest opisany przez środkowe koło ( A = X W B = I ) i promień R . Dobry kandydat znajduje się zatem na skrzyżowaniu kilku kręgów. Budujemy macierz akumulacji A : każdy element A _{I W J} macierzy zawiera liczbę kół przechodzących przez punkt lub kwadrat o kilku pikselach, odpowiadający temu elementowi.

Jeśli promień jest nieznany, metodą badawczą jest zbudowanie hipermatora akumulacji, z której każda komórka A _{I W J} odpowiada kostce przestrzeni ( A W B W R ) , przez zamiatanie wszystkich możliwych promieni 1 piksela do wymiaru obrazu.

Aplikacje

Okrąg jest rzutem sferycznego obiektu na płaszczyźnie lub odcinka okrągłego (cylindra, stożka, torusa), pod warunkiem, że oś obiektu jest prostopadła do płaszczyzny projekcyjnej (w przeciwnym razie rzut jest elipsą). Rozpoznawanie form okrągłych można użyć do wykrywania głów, a zatem ludzi na zdjęciu lub obrazie nadzoru wideo ^{[[[ 6 ]} . Można go również użyć do wykrywania tętniaków na angiogramie ^{[[[ 7 ]} .

Wykrywanie elipsy [[[ modyfikator |. Modyfikator i kod ]

Osie symetrii par punktów na tej samej poziomej lub pionowej (Yin i Chen 1994) oraz oznaczanie środka elipsy przy użyciu średnich punktów (Ho i Chen 1995).

Określenie środka elipsy z punktów punktów: krzywizna jest podłączona do stycznych (Aguado i Nixon 1995), centrum znajduje się po prawej, łącząc przecięcie dwóch stycznych w środku segmentu (Alvarez i Coll. 2007 ).

Elipsa charakteryzuje się pięcioma parametrami, zazwyczaj:

• X ₀ : odcięta jego centrum;
• I ₀ : porządek jego centrum;
• A : pół długości dużej osi;
• B : pół długości małej osi;
• th : nachylenie dużej osi w porównaniu do osi X .

Oznacza to, że bezpośrednie wdrożenie transformacji Hough odbywa się w przestrzeni pięciodwozimnej, która implikuje znaczący okres obliczeń i wymaga dużej pojemności pamięci. Zaproponowano kilka algorytmów w celu zmniejszenia liczby niezbędnych parametrów.

En 1978, Tsuji et matsumoto ^{[[[ 8 ]} Zaproponuj użycie gradientu kontrastu do określenia prostopadłego do stycznej. Biorąc pod uwagę punkty z równoległymi stycznymi, określają pozycję ośrodków elipsy. Następnie używają właściwości geometrycznych do oddzielenia elipsów od innych obiektów o tej samej właściwości, ostatecznie parametry elipsów są określone metodą najmniejszych kwadratowych

En 1994, Yin et Chen ^{[[[ 9 ]} Zaproponuj wybranie grup pięciu punktów, wystarczającej liczby do określenia elipsy. W tym celu punkty są klasyfikowane w podsumowaniu. Obraz wykrytych punktów konturu nazywa się F. Algorytm wykonuje skanowanie górnego i dolnego przez poziomy prawy i bierze punkty znajdujące się po prawej stronie. Rozważa w ten sposób środowiska segmentów, te środowiska segmentowe tworzą obraz o nazwie G. Dla danej elipsy segmenty znajdują się po tej samej prawej, prawej zależnej od nachylenia wielkiej osi; Prawo to nazywa się „osą symetrii”, ponieważ punkty są symetryczne nie przez odbicie, ale podobieństwo raportu 1. Linie te są określane przez konwencjonalną transformację Hough G. Następnie algorytm tworzy pod -obrazy F formowane punkty generujące generowanie punktów generujących punkty dane prawo g; Zatem punkty F są klasyfikowane zgodnie z ich możliwym należącym do elipsy o danej osi symetrii. Każdy podmiot jest następnie traktowany osobno. W podmiotu, dla każdej pary punktów ( A W B ) Algorytm określa pięć punktów:

• dwa punkty ( I W F ) ” wokół A », To znaczy na granicy kwadratowej strony okna C , Tel L’gle Eâf jest kompatybilny z kierunkiem krzywizny elipsy;
• Dwa symetryczne punkty ( G W H ) ;
• Piąty punkt I znajdujący się na mediatorze [[[ NP ] lub [[[ Fh ] .

Parametry elipsy są określone na podstawie tych pięciu punktów, a macierz akumulacji jest aktualizowana dla tego zestawu parametrów. Granice tej metody to:

• Obraz musi mieć wystarczającą liczbę punktów na elipsę;
• Niektóre wygenerowane podmioty nie zawierają elipsy, a zatem spożywają czas obliczania bez zysku;
• szerokość C Z kwadratowego okna musi być wystarczająco duży, aby pięć punktów mogło zostać rozmieszczone, co gwarantuje dobrą precyzję przy określaniu parametrów, ale musi być mniejsza niż połowa długości małej osi każdej elipsy.

W 1995 roku jesteś Chen ^{[[[ dziesięć ]} Utwórz dwie podprzestrzenia w podobny sposób jak Yin i Chen. Pierwszy polega na uwzględnieniu par punktów zarysowych znajdujących się na tej samej prawej poziomej i przyjmowaniu w ten sposób utworzonych segmentów. Druga podprzestrzeń jest zbudowana w ten sam sposób, ale biorąc pod uwagę pary punktów znajdujących się na tej samej pionowej. Algorytm wykonuje następnie wykrywanie linii utworzonych przez te średnie punkty z konwencjonalną transformacją Hough, przecięcie tych linii nadaje centrom elipsy. Następnie określają pozostałe trzy parametry (określenie dużej i małej osi).

Podobną metodą jest rozważenie par punktów: gradient umożliwia dostęp do stycznej, jeśli styczne nie są równoległe, wycinają się w punkcie T . Prawa łącząca ten punkt w środku segmentu przechodzi przez Center Elipsy ^{[[[ 11 ]} .

Z hipotezą to [[[ A _Pierwszy A ₂ ] to duża oś, elipsy są koniecznie na szarym dysku. Każda komórka macierzy akumulacji (w jednym wymiarze, B ) zawiera tylko dwa zdarzenia, dlatego hipoteza ” [[[ A _Pierwszy A ₂ ] jest dużą oś ”jest odrzucane (11 i JI 2002).

W 2002 roku Xie i Ji zaproponowali metodę przeprowadzającą wyszukiwanie jednego parametru, długość pół dziecka ^{[[[ dwunasty ]} . Biorą parę punktów A _Pierwszy ( X _Pierwszy W I _Pierwszy ) I A ₂ ( X ₂ W I ₂ ) Wystarczająco odległe i zakładaj, że znajdują się one na dużej osi elipsy. Z tą hipotezą centrum elipsy jest koniecznie pośrodku O z [[[ A _Pierwszy A ₂ ] , długość dużej osi to 2 A = A _Pierwszy A ₂ a nachylenie wielkiej osi jest th = ArcTan (( I ₂ – I _Pierwszy )/( X ₂ – X _Pierwszy )) . Następnie rozważają każdy punkt zarys M : Jeśli jest wystarczająco blisko do O Być w stanie być na dużej elipsie osiowej [[[ A _Pierwszy A ₂ ] , potem punkt M Używane do obliczenia pół chłopaka B elipsy. To jest ten parametr B który służy do budowy macierzy akumulacji. Jeśli macierz zawiera pik wystarczająco duży, aby scharakteryzować elipsę, wówczas elipsa jest zachowana. Następnie algorytm przechodzi do innej pary ( A _Pierwszy W A ₂ ) . Algorytm polega zatem na tworzeniu transformacji Hough dla każdej pary wystarczająco odległych punktów, ale ta transformacja odbywa się tylko na jednym parametrze. Z drugiej strony obraz musi zawierać końce dużej osi, aby elipsa została wykryta.

Aplikacje

Elipsa jest rzutem okrągłego przekroju na płaszczyźnie. Wykrywanie elipsy umożliwia zatem wykrywanie obiektów cylindrycznych lub torycznych, takich jak źrenice oczu, panele sygnalizacyjne i koła pojazdu.

Bibliografia [[[ modyfikator |. Modyfikator i kod ]

• [Duda et Hart 1972] (W) R. O. Wątpliwość i P. E. Jeleń W ‘ Użycie transformacji Hough do wykrywania linii i krzywych na zdjęciach » W Comm. ACM W tom. 15, Styczeń 1972 W P. 11-15 .
• [Hart 2009] (W) P. E. Jeleń W ‘ Jak wynaleziono transformację Hough » W Magazyn przetwarzania sygnałów IEEE W tom. 26, N ^O 6, Listopad 2009 W P. 18–22 ( Czytaj online ) .
• [Hough 1959] (W) P.V.C. Pęcina W «Analiza maszyny zdjęć komory bąbelkowej» , W Proc. Int. Conf. Akceleratory o wysokiej energii i oprzyrządowanie W 1959 .
• [Tarsha-Kurdi i Col. 2007] (W) F. Tarsha , T. Kraj i gramy Grussmeyer W ‘ Hough-transform i rozszerzone algorytmy RANSAC do automatycznego wykrywania samolotów dachowych budynków 3D z danych Lidar » W Międzynarodowe archiwa fotogrametrii, teledetekcji i nauki o informacjach przestrzennych W tom. 36, N ^O 3/w52, 2007 W P. 407-412 .

Linki zewnętrzne [[[ modyfikator |. Modyfikator i kod ]

• Scikit-Imagage Transformacja Hough (po prawej, okręgu, elipsy) w bibliotece Scikit-Image (Python).

Powiązane artykuły [[[ modyfikator |. Modyfikator i kod ]