Generaliserad Hough-transform

Den generaliserade Hough-transformen ( GHT ), som introducerades av Dana H. Ballard 1981, är modifieringen av Hough-transformen med hjälp av principen om mallmatchning . Hough-transformen utvecklades ursprungligen för att detektera analytiskt definierade former (t.ex. linje , cirkel , ellips etc.). I dessa fall har vi kunskap om formen och siktar på att ta reda på dess placering och orientering i bilden. Denna modifiering gör att Hough-transformen kan användas för att detektera ett godtyckligt objekt som beskrivs med dess modell.

Problemet med att hitta objektet (beskrivet med en modell) i en bild kan lösas genom att hitta modellens position i bilden. Med den generaliserade Hough-transformen förvandlas problemet med att hitta modellens position till ett problem att hitta transformationens parameter som kartlägger modellen i bilden. Givet värdet på transformationens parameter kan modellens position i bilden bestämmas.

Den ursprungliga implementeringen av GHT använde kantinformation för att definiera en mappning från orienteringen av en kantpunkt till en referenspunkt för formen. I fallet med en binär bild där pixlar kan vara antingen svarta eller vita, kan varje svart pixel i bilden vara en svart pixel av det önskade mönstret, vilket skapar ett lokus av referenspunkter i Hough-utrymmet. Varje pixel i bilden röstar för dess motsvarande referenspunkter. De maximala punkterna i Hough-utrymmet indikerar möjliga referenspunkter för mönstret i bilden. Detta maximum kan hittas genom att skanna Hough-utrymmet eller genom att lösa en avslappnad uppsättning ekvationer, var och en av dem motsvarar en svart pixel.

Historia

Merlin och Farber visade hur man använder en Hough-algoritm när de önskade kurvorna inte kunde beskrivas analytiskt. Det var en föregångare till Ballards algoritm som var begränsad till translation och inte tog hänsyn till rotation och skalförändringar .

Merlin-Farber-algoritmen är opraktisk för verklig bilddata eftersom den i en bild med många kantpixlar hittar många falska positiva resultat på grund av repetitiva pixlarrangemang.

Teori om generaliserad Hough-transform

För att generalisera Hough-algoritmen till icke-analytiska kurvor, definierar Ballard följande parametrar för en generaliserad form: a={y,s,θ} där y är ett referensursprung för formen, θ är dess orientering och s = (s _x , s _y ) beskriver två ortogonala skalfaktorer. En algoritm kan beräkna den bästa uppsättningen parametrar för en given form från kantpixeldata. Dessa parametrar har inte samma status. Referensursprungspositionen, y , beskrivs i termer av en malltabell som kallas R-tabellen över möjliga kantpixelorientering. Beräkningen av de ytterligare parametrarna s och 6 åstadkommes sedan genom enkla transformationer till denna tabell. Den viktigaste generaliseringen till godtyckliga former är användningen av riktningsinformation. Givet vilken form som helst och en fast referenspunkt på den, istället för en parametrisk kurva, lagras informationen som tillhandahålls av gränspixlarna i form av R-tabellen i transformationssteget. För varje kantpunkt på testbilden slås punktens egenskaper upp på R-tabellen och referenspunkten hämtas och lämplig cell i en matris som kallas ackumulatormatrisen inkrementeras. Cellen med maximalt antal "röster" i ackumulatormatrisen kan vara en möjlig punkt för existens av fast referens för objektet i testbilden.

Bygga R-bordet

Välj en referenspunkt y för formen (vanligtvis vald inuti formen). För varje gränspunkt x , beräkna ɸ(x) , gradientriktningen och r = y – x som visas i bilden. Lagra r som en funktion av ɸ . Lägg märke till att varje index för ɸ kan ha många värden på r . Man kan antingen lagra koordinatskillnaderna mellan den fasta referensen och kantpunkten ((x _c – x _ij ), (y _c – y _ij )) eller som det radiella avståndet och vinkeln mellan dem (r _ij , α _ij ) . Efter att ha gjort detta för varje punkt kommer R-tabellen att representera mallobjektet fullt ut. Eftersom genereringsfasen är inverterbar kan vi också använda den för att lokalisera objektförekomster på andra ställen i bilden.

Geometri för formdetektering för generaliserad Hough-transform

i	ɸ _i	R _{ɸ _i}
1	0	(r11 _, α11 ₎₍ r12 _, α12 ₎ ... (rln _, α1n )
2	Δɸ	(r ₂₁ , α ₂₁ ) (r ₂₂ , α ₂₂ )... (r _2m , α _2m )
3	2Δɸ	(r ₃₁ , α ₃₁ ) (r ₃₂ , α ₃₂ )... (r _3k , α _3k )
...	...	...

Objektlokalisering

För varje kantpixel x i bilden, hitta gradienten ɸ och inkrementera alla motsvarande punkter x+r i ackumulatormatrisen A (initierad till en maximal storlek på bilden) där r är en tabellpost indexerad med ɸ , dvs. r (ɸ) . Dessa ingångspunkter ger oss varje möjlig position för referenspunkten. Även om vissa falska punkter kan beräknas, med tanke på att objektet finns i bilden, kommer ett maximum att inträffa vid referenspunkten. Maxima i A motsvarar möjliga instanser av formen.

Generalisering av skala och orientering

För en fixerad formorientering var ackumulatormatrisen tvådimensionell i referenspunktskoordinaterna. För att söka efter former med godtycklig orientering θ och skala s läggs dessa två parametrar till i formbeskrivningen. Ackumulatormatrisen består nu av fyra dimensioner som motsvarar parametrarna (y, s, θ) . R-tabellen kan också användas för att öka detta större dimensionella utrymme eftersom olika orienteringar och skalor motsvarar lättberäknade transformationer av bordet. Beteckna en viss R-tabell för en form S med R(ɸ) . Enkla transformationer till den här tabellen gör att den kan upptäcka skalade eller roterade instanser av samma form. Till exempel, om formen skalas med s och denna transformation betecknas med T _s . då T _s [R(ɸ)] = sR(ɸ) , dvs alla vektorer skalas med s . Dessutom, om objektet roteras med θ och denna transformation betecknas med T _θ , då T _θ [R(ɸ)] = Rot{R[(ɸ-θ)mod2π],θ}, dvs alla index inkrementeras med – θ modulo 2π, de lämpliga vektorerna r hittas, och sedan roteras de med θ . En annan egenskap som kommer att vara användbar för att beskriva sammansättningen av generaliserade Hough-transformer är förändringen av referenspunkten. Om vi vill välja en ny referenspunkt ỹ så att y-ỹ = z så ges modifikationen av R-tabellen av R(ɸ)+ z , dvs z adderas till varje vektor i tabellen.

Alternativt sätt med par av kanter

Ett par kantpixlar kan användas för att minska parameterutrymmet. Med användning av R-tabellen och egenskaperna som beskrivits ovan, definierar varje kantpixel en yta i det fyrdimensionella ackumulatorutrymmet av a = (y, s, θ) . Två kantpixlar i olika orienteringar beskriver samma yta som roteras lika mycket med avseende på θ . Om dessa två ytor skär varandra kommer punkter där de skär varandra att motsvara möjliga parametrar a för formen. Således är det teoretiskt möjligt att använda de två punkterna i bildrymden för att reducera platsen i parameterrymden till en enda punkt. Svårigheterna att hitta skärningspunkterna för de två ytorna i parameterrymden kommer dock att göra detta tillvägagångssätt omöjligt i de flesta fall.

Sammansatta former

Om formen S har en sammansatt struktur bestående av underdelarna S ₁ , S ₂ , .. S _N och referenspunkterna för formerna S , S ₁ , S ₂ , .. S _N är y , y ₁ , y ₂ , . .y ges _n , sedan för en skalfaktor s och orientering θ , den generaliserade Hough-transformen R _s (ɸ) av $R_{\phi }=T_{s}\left\{T_{\theta}\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right ]\right\}$ . Problemet med denna transformation är att valet av referens i hög grad kan påverka noggrannheten. För att övervinna detta har Ballard föreslagit att utjämna den resulterande ackumulatorn med en sammansatt utjämningsmall. Den sammansatta utjämningsmallen H(y) ges som en sammansatt faltning av individuella utjämningsmallar av underformerna. $H(y)=\summa _{i=1}^{N}h_{i}(y-y_{i})$ . Sedan ges den förbättrade ackumulatorn av A _s = A*H och maxima i A _s motsvarar möjliga instanser av formen.

Rumslig nedbrytning

Heather och Yang observerade att den globala Hough-transformen kan erhållas genom att summera lokala Hough-transformers av disjunkta subregioner, och Heather och Yang föreslog en metod som involverar den rekursiva underuppdelningen av bilden i underbilder, var och en med sitt eget parameterutrymme och organiserade i en quadtree- struktur. Det resulterar i förbättrad effektivitet när det gäller att hitta ändpunkter för linjesegment och förbättrad robusthet och tillförlitlighet vid extrahering av linjer i bullriga situationer, till en något ökad minneskostnad.

Genomförande

Implementeringen använder följande ekvationer:

x=x_{c}+x'\ \ eller\ \ x_{c}=xx'

y=y_{c}+y'\ \ or\ \ y_{c}=yy'

\cos(\pi -\alpha )=x'/r\ \ {\text{eller}}\ \ x'=r\cos(\ pi -\alpha )=-r\cos(\alpha )

\ sin(\pi -\alpha )=y'/r\ \ {\text{eller}}\ \ y'=r\sin(\pi -\alpha )=r\sin(\alpha )

Genom att kombinera ovanstående ekvationer har vi:

x_{c}=x+r\cos(\alpha )

y_{c}=y+ r\sin(\alpha )

Konstruera R-bordet

(0) Konvertera exempelformbilden till en kantbild med valfri kantdetekteringsalgoritm som Canny edge detector

(1) Välj en referenspunkt (t.ex. (x _c , y _c ) )

(2) Rita en linje från referenspunkten till gränsen

(3) Beräkna ɸ

(4) Lagra referenspunkten (x _c , y _c ) som en funktion av ɸ i R(ɸ) -tabellen.

Upptäckt:

(0) Konvertera provformbilden till en kantbild med valfri kantdetekteringsalgoritm som Canny edge detector .

(1) Initiera ackumulatortabellen: A[x _cmin . . . x _cmax ][y _cmin . . . y _cmax ]

(2) För varje kantpunkt (x, y)

(2.1) Använd gradientvinkeln ɸ , hämta från R-tabellen alla (α, r) värden indexerade under ɸ . (2.2)

Beräkna referenspunkterna för varje (α,r) :

x _c = x + r cos(α)

y _c = y + r sin(α)

(2.3) Öka räknarna (röstning):

++A( [[x _c ]][y _c ])

(3) Möjliga placeringar av objektkonturen ges av lokala maxima i A[x _c ][y _c ] .

Om A[x _c ][y _c ] > T , då är objektkonturen placerad vid (x _c , y _c )

Allmänt fall:

Antag att objektet har genomgått en viss rotation Θ och enhetlig skalning s :

(x ′ , y ′ ) --> (x″, y″)

x″ = (x ′ cos(Θ) – y ′ sin(Θ))s

y″ = (x ′ sin(Θ) + y ′ cos (Θ))s

Ersätter x ′ med x″ och y ′ med y″:

x _c = x – x″ eller x _c = x - (x ′ cos(Θ) – y ′ sin(Θ))s

y _c = y – y″ eller y _c = y - (x ′ sin(Θ) + y ′ cos(Θ))s

(1) Initiera ackumulatortabellen: A[x _cmin . . . x _cmax ][y _cmin . . . y _cmax ][q _min . . . q _max ][s _min . . . s _max ]

(2) För varje kantpunkt (x, y)

(2.1) Använd dess gradientvinkel ɸ , hämta alla (α, r) värden från R-tabellen (2.2

) Beräkna för varje (α, r) . kandidatreferenspunkterna:

x ′ = r cos(α)

y ′ = r sin(α)

for( Θ = Θ _min ; Θ ≤ Θ _max ; Θ++ )

för( s = s _min ; s ≤ s _max ; s++ )

x _c = x - (x ′ cos(Θ) – y ′ sin(Θ))s

y _c = y - (x ′ sin(Θ) + y ′ cos(Θ))s

++(A[x _c ][y _c ][Θ][s])

(3) Möjliga placeringar av objektkonturen ges av lokala maxima i A[x _c ][y _c ][Θ][s]

Om A[x _c ][y _c ][Θ][s] > T , då är objektkonturen belägen vid (x _c , y _c ) , har genomgått en rotation Θ , och har skalats med s .

Fördelar och nackdelar

Fördelar

Den är robust mot partiella eller lätt deformerade former (dvs. robust mot igenkänning under ocklusion).
Den är robust mot närvaron av ytterligare strukturer i bilden.
Den är tolerant mot buller.
Den kan hitta flera förekomster av en form under samma bearbetningspass.

Nackdelar

Den har betydande beräknings- och lagringskrav som blir akuta när objektorientering och skala måste beaktas.

Relaterat arbete

Ballard föreslog att man skulle använda orienteringsinformation för kanten för att minska kostnaden för beräkningen. Många effektiva GHT-tekniker har föreslagits såsom SC-GHT (användning av lutning och krökning som lokala egenskaper). Davis och Yam föreslog också en utvidgning av Merlins arbete för orientering och skalinvariant matchning som kompletterar Ballards arbete men inte inkluderar Ballards användning av kantlutningsinformation och sammansatta strukturer

Se även

externa länkar

OpenCV- implementering av generaliserad Hough-transform http://docs.opencv.org/master/dc/d46/classcv_1_1GeneralizedHoughBallard.html
Handledning och implementering av generaliserade Hough-transformers http://www.itriacasa.it/generalized-hough-transform/default.html
Praktisk implementering av generaliserad Hough-transform http://www.irit.fr/~Julien.Pinquier/Docs/Hough_transform.html
FPGA-implementering av generaliserade Hough-transformationer, IEEE Digital Library http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5382047&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp% 3Farnummer%3D5382047
MATLAB- implementering av generaliserad Hough-transform http://www.mathworks.com/matlabcentral/fileexchange/44166-generalized-hough-transform