Transformata Hougha

Użycie kierunku gradientu do zmniejszenia liczby głosówEdit

Ulepszenie zaproponowane przez O’Gormana i Clowesa może być użyte do wykrywania linii, jeśli weźmie się pod uwagę, że lokalny gradient intensywności obrazu będzie z konieczności ortogonalny do krawędzi. Ponieważ wykrywanie krawędzi zazwyczaj polega na obliczaniu wielkości gradientu intensywności, kierunek gradientu jest często znajdowany jako efekt uboczny. Jeśli dany punkt o współrzędnych (x,y) rzeczywiście znajduje się na linii, wówczas lokalny kierunek gradientu daje parametr θ odpowiadający tej linii, a parametr r jest natychmiast uzyskiwany. (Shapiro i Stockman, 305) Kierunek gradientu może być oszacowany z dokładnością do 20°, co skraca ślad sinusoidy z pełnych 180° do około 45°. Skraca to czas obliczeń i ma interesujący efekt w postaci zmniejszenia liczby bezużytecznych głosów, co zwiększa widoczność kolców odpowiadających prawdziwym liniom na obrazie.

Przekształcenie Hougha oparte na jądrze (KHT)Edit

Fernandes i Oliveira zaproponowali ulepszony schemat głosowania dla przekształcenia Hougha, który pozwala na implementację programową w czasie rzeczywistym nawet na stosunkowo dużych obrazach (np. 1280×960). Oparta na jądrze transformata Hougha wykorzystuje ten sam ( r , θ ) {displaystyle (r,θ )}

parametryzację zaproponowaną przez Dudę i Harta, ale operuje na klastrach w przybliżeniu współliniowych pikseli. Dla każdego klastra, głosy są oddawane przy użyciu zorientowanego eliptyczno-gaussowskiego jądra, które modeluje niepewność związaną z najlepiej dopasowaną linią w odniesieniu do odpowiedniego klastra. Podejście to nie tylko znacząco poprawia wydajność schematu głosowania, ale również produkuje znacznie czystszy akumulator i sprawia, że transformacja jest bardziej odporna na wykrywanie fałszywych linii.

3-D Kernel-based Hough transform for plane detection (3DKHT)Edit

Limberger i Oliveira zaproponowali deterministyczną technikę wykrywania płaszczyzn w nieuporządkowanych chmurach punktów, której koszt wynosi n log ( n ) {{displaystyle n\log(n)}

w liczbie próbek, osiągając wydajność w czasie rzeczywistym dla stosunkowo dużych zbiorów danych (do 10 5 {displaystyle 10^{5}}

punktów na procesorze 3,4 GHz). Jest ona oparta na szybkiej strategii głosowania transformaty Hougha dla regionów planarnych, zainspirowanej transformatą Hougha opartą na jądrze (KHT). Ta trójwymiarowa transformacja Hougha oparta na jądrze (3DKHT) wykorzystuje szybki i odporny algorytm do segmentacji klastrów w przybliżeniu współpłaszczyznowych próbek i oddaje głosy na poszczególne klastry (zamiast na poszczególne próbki) na ( θ , ϕ , ρ {displaystyle \theta ,\phi ,\rho }

) akumulatora sferycznego przy użyciu trójczynnikowego jądra gaussowskiego. Metoda ta jest o kilka rzędów wielkości szybsza niż istniejące (niedeterministyczne) techniki detekcji płaszczyzn w chmurach punktów, takie jak RHT i RANSAC, i lepiej skaluje się wraz z rozmiarem zbiorów danych. Można ją stosować w każdej aplikacji, która wymaga szybkiego wykrywania cech planarnych na dużych zbiorach danych.

Transformata Hougha krzywych i jej uogólnienie dla kształtów analitycznych i nieanalitycznychEdit

Pomimo że opisana powyżej wersja transformaty ma zastosowanie tylko do znajdowania linii prostych, podobna transformata może być użyta do znajdowania dowolnego kształtu, który może być reprezentowany przez zbiór parametrów. Na przykład okrąg może zostać przekształcony w zestaw trzech parametrów reprezentujących jego środek i promień, dzięki czemu przestrzeń Hougha staje się trójwymiarowa. W ten sposób można również znaleźć arbitralne elipsy i krzywe, a także dowolny kształt, który łatwo wyrazić jako zbiór parametrów.

Uogólnienie transformaty Hougha do wykrywania kształtów analitycznych w przestrzeniach o dowolnej wymiarowości zostało zaproponowane przez Fernandesa i Oliveirę. W przeciwieństwie do innych metod wykrywania kształtów analitycznych opartych na transformacie Hougha, technika Fernandesa nie zależy od kształtu, który chcemy wykryć, ani od typu danych wejściowych. Detekcja może być dostosowana do typu kształtu analitycznego poprzez zmianę założonego modelu geometrii, w którym dane zostały zakodowane (np. przestrzeń euklidesowa, przestrzeń rzutowa, geometria konforemna, itd.), podczas gdy proponowane sformułowanie pozostaje niezmienione. Gwarantuje również, że zamierzone kształty są reprezentowane przy najmniejszej możliwej liczbie parametrów i pozwala na równoczesne wykrywanie różnych rodzajów kształtów, które najlepiej pasują do wejściowego zbioru wpisów o różnych wymiarach i różnych definicjach geometrycznych (np. równoczesne wykrywanie płaszczyzn i sfer, które najlepiej pasują do zbioru punktów, linii prostych i okręgów).

Dla bardziej skomplikowanych kształtów na płaszczyźnie (tj, kształtów, które nie mogą być reprezentowane analitycznie w jakiejś przestrzeni 2D), używana jest uogólniona transformata Hougha, która pozwala funkcji głosować za konkretną pozycją, orientacją i/lub skalowaniem kształtu przy użyciu predefiniowanej tabeli look-up.Transformata Hougha kumuluje wkłady od wszystkich pikseli w wykrytej krawędzi.

Proces wykrywania okręguEdit

Modyfikacja algorytmu w celu wykrywania kształtów kołowych zamiast linii jest stosunkowo prosta.

• Początkowo tworzymy przestrzeń akumulatora, która składa się z komórki dla każdego piksela. Początkowo każda komórka jest ustawiona na 0.
• Dla każdego punktu brzegowego (i, j) w obrazie inkrementujemy wszystkie komórki, które zgodnie z równaniem okręgu ( i – a ) 2 + ( j – b ) 2 = r 2 {(i-a)^{2}+(j-b)^{2}=r^{2}}
  

  może być środkiem okręgu. Komórki te są reprezentowane przez literę a {{displaystyle a}

  

  w równaniu.

• Dla każdej możliwej wartości a {{displaystyle a}
  

  znalezionej w poprzednim kroku, znajdź wszystkie możliwe wartości b {{displaystyle b}

  

  , które spełniają równanie.

• Poszukaj lokalnych maksimów w przestrzeni akumulatorów. Komórki te reprezentują okręgi, które zostały wykryte przez algorytm.

Jeśli nie znamy wcześniej promienia okręgu, który próbujemy zlokalizować, możemy użyć trójwymiarowej przestrzeni akumulatorów do wyszukiwania okręgów o dowolnym promieniu. Oczywiście, jest to bardziej kosztowne obliczeniowo.

Ta metoda może również wykrywać okręgi, które są częściowo poza przestrzenią akumulatora, tak długo, jak wystarczająca część obszaru okręgu jest nadal w niej obecna.

Wykrywanie obiektów 3D (płaszczyzny i cylindry)Edycja

Transformata Hougha może być również używana do wykrywania obiektów 3D w danych o zasięgu lub chmurach punktów 3D. Rozszerzenie klasycznej transformaty Hougha do wykrywania płaszczyzn jest dość proste. Płaszczyzna jest reprezentowana przez jednoznaczne równanie z = a x x + a y y + d {displaystyle z=a_{x}x+a_{y}y+d}.

dla którego możemy użyć trójwymiarowej przestrzeni Hougha odpowiadającej a x {displaystyle a_{x}}

, a y {{displaystyle a_{y}}

oraz d {displaystyle d}

. Rozszerzenie to cierpi na te same problemy co jego odpowiednik 2D, tzn. płaszczyzny w pobliżu poziomu mogą być wiarygodnie wykrywane, natomiast wydajność pogarsza się, gdy kierunek płaszczyzny staje się pionowy (duże wartości a x {displaystyle a_{x}}

i a y {displaystyle a_{y}}

wzmacniają szum w danych). To sformułowanie płaszczyzny zostało użyte do wykrywania płaszczyzn w chmurach punktów pozyskanych z lotniczego skanowania laserowego i działa bardzo dobrze, ponieważ w tej dziedzinie wszystkie płaszczyzny są prawie poziome.

Do uogólnionej detekcji płaszczyzny przy użyciu transformaty Hougha, płaszczyzna może być sparametryzowana przez jej wektor normalny n {\i0}

(używając współrzędnych sferycznych) i jej odległość od początku ρ {displaystyle \rho }

w wyniku czego otrzymujemy trójwymiarową przestrzeń Hougha. W wyniku tego każdy punkt w danych wejściowych głosuje na sinusoidalną powierzchnię w przestrzeni Hougha. Przecięcie tych sinusoidalnych powierzchni wskazuje na obecność płaszczyzny. Bardziej ogólne podejście dla więcej niż 3 wymiarów wymaga heurystyki wyszukiwania, aby pozostać wykonalnym.

Przekształcenie Hougha zostało również wykorzystane do znalezienia obiektów cylindrycznych w chmurach punktów przy użyciu podejścia dwuetapowego. Pierwszy krok znajduje orientację cylindra, a drugi krok znajduje pozycję i promień.

Using weighted featuresEdit

Jeden wspólny szczegół wariacji. To znaczy, znalezienie koszy z największą liczbą w jednym etapie może być użyte do ograniczenia zakresu wartości wyszukiwanych w następnym.

Starannie dobrana przestrzeń parametrówEdit

Wysokowymiarowa przestrzeń parametrów dla transformaty Hougha jest nie tylko powolna, ale jeśli zostanie zaimplementowana bez przemyślenia, może łatwo przekroczyć dostępną pamięć. Nawet jeśli środowisko programistyczne pozwala na przydzielenie tablicy większej niż dostępna przestrzeń pamięci poprzez pamięć wirtualną, liczba wymaganych do tego zamiany stron będzie bardzo wymagająca, ponieważ tablica akumulatorów jest używana w sposób losowy, rzadko zatrzymując się w ciągłej pamięci, ponieważ przeskakuje z indeksu na indeks.

Rozważmy zadanie znalezienia elips na obrazie 800×600. Zakładając, że promienie elips są zorientowane wzdłuż osi głównych, przestrzeń parametrów jest czterowymiarowa. (x,y) definiuje środek elipsy, a a i b oznaczają dwa promienie. Dopuszczając środek w dowolnym miejscu obrazu, dodajemy ograniczenie 0<x<800 i 0<y<600. Jeśli promienie otrzymają te same wartości jako ograniczenia, pozostanie nam słabo wypełniona tablica akumulatorów zawierająca ponad 230 miliardów wartości.

Tak skonstruowany program prawdopodobnie nie będzie miał możliwości przydzielenia wystarczającej ilości pamięci. Nie oznacza to, że problemu nie da się rozwiązać, a jedynie, że należy znaleźć nowe sposoby ograniczenia rozmiaru tablicy akumulatorów, co czyni go wykonalnym. Na przykład:

1. Jeśli rozsądnie jest założyć, że elipsy są w całości zawarte w obrazie, można zmniejszyć zakres promieni. Największy promień może być, jeśli środek elipsy jest w środku obrazu, pozwalając krawędziom elipsy rozciągać się do krawędzi. W tym skrajnym przypadku promienie mogą być tylko o połowę mniejsze od rozmiaru obrazu zorientowanego w tym samym kierunku. Zmniejszenie zakresu a i b w ten sposób redukuje tablicę akumulatorów do 57 miliardów wartości.
2. Trade dokładność dla przestrzeni w estymacji transformaty Hough akumuluje wkłady ze wszystkich pikseli w wykrytej krawędzi. Transformata Hougha kumuluje wkłady ze wszystkich pikseli w wykrytej krawędzi. he center: Jeśli przewiduje się, że środek jest oddalony o 3 zarówno na osi x, jak i y, zmniejsza to rozmiar tablicy akumulatorów do około 6 miliardów wartości.
3. Trade accuracy for space in the estimation of the radii: Jeśli promienie zostaną oszacowane jako oddalone o 5, następuje dalsza redukcja rozmiaru tablicy akumulatorów, o około 256 milionów wartości.
4. Przycinanie obrazu do obszarów zainteresowania. Jest to zależne od obrazu, a zatem nieprzewidywalne, ale wyobraź sobie przypadek, w którym wszystkie krawędzie zainteresowania w obrazie są w lewym górnym kwadrancie tego obrazu. Tablica akumulatorów może być zmniejszona jeszcze bardziej w tym przypadku przez ograniczenie wszystkich 4 parametrów o współczynnik 2, dla całkowitego współczynnika redukcji 16.

Przez zastosowanie tylko pierwszych trzech z tych ograniczeń do przykładu podanego o, rozmiar tablicy akumulatorów jest zmniejszony prawie o współczynnik 1000, sprowadzając go do rozmiaru, który jest znacznie bardziej prawdopodobne, aby zmieścić się w pamięci nowoczesnego komputera.

Wydajny algorytm wykrywania elipsEdit

Yonghong Xie i Qiang Ji podają wydajny sposób implementacji transformaty Hougha do wykrywania elips poprzez przezwyciężenie problemów z pamięcią. Jak omówiono w algorytmie (na stronie 2 pracy), to podejście używa tylko jednowymiarowego akumulatora (dla osi mniejszej) w celu wykrycia elips na obrazie. Złożoność jest O(N3) w liczbie niezerowych punktów w obrazie.