Articles / oktober 24, 2021

Hough-transform

Användning av gradientens riktning för att minska antalet rösterRedigera

En förbättring som föreslogs av O’Gorman och Clowes kan användas för att upptäcka linjer om man tar hänsyn till att den lokala gradienten för bildens intensitet nödvändigtvis kommer att vara ortogonal till kanten. Eftersom kantdetektering i allmänhet innebär att man beräknar intensitetsgradientens storlek, hittas gradientriktningen ofta som en bieffekt. Om en given punkt med koordinaterna (x,y) råkar ligga på en linje, ger den lokala gradientens riktning θ-parametern som motsvarar linjen, och r-parametern erhålls då omedelbart. (Shapiro och Stockman, 305) Gradientens riktning kan uppskattas med en noggrannhet på 20°, vilket förkortar sinusoidspåret från hela 180° till ungefär 45°. Detta minskar beräkningstiden och har den intressanta effekten att antalet onödiga röster minskar, vilket ökar synligheten av de spikar som motsvarar verkliga linjer i bilden.

Kernel-based Hough transform (KHT)Edit

Fernandes och Oliveira föreslog ett förbättrat röstningssystem för Hough-transformen som gör det möjligt för en mjukvaruimplementering att uppnå realtidsprestanda även på relativt stora bilder (t.ex. 1280×960). Den kärnbaserade Hough-transformen använder samma ( r , θ ) {\displaystyle (r,\theta )}

$(r,\theta )$

parametrisering som föreslagits av Duda och Hart men arbetar med kluster av ungefär kollinjära pixlar. För varje kluster avges röster med hjälp av en orienterad elliptisk-Gaussiansk kärna som modellerar den osäkerhet som är förknippad med den bäst passande linjen med avseende på motsvarande kluster. Detta tillvägagångssätt förbättrar inte bara röstningssystemets prestanda avsevärt, utan ger också en mycket renare ackumulator och gör transformatorn mer robust mot upptäckt av falska linjer.

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

Limberger och Oliveira föreslog en deterministisk teknik för att upptäcka plan i oorganiserade punktmoln vars kostnad är n log ( n ) {\displaystyle n\log(n)}

$n\log(n)$

i antalet prover, vilket ger prestanda i realtid för relativt stora datamängder (upp till 10 5 {\displaystyle 10^{5}}

$10^{5}$

punkter på en 3,4 GHz CPU). Den bygger på en snabb röstningsstrategi för Hough-transform för plana regioner, inspirerad av den kärnbaserade Hough-transformen (KHT). Denna 3D Kernel-based Hough transform (3DKHT) använder en snabb och robust algoritm för att segmentera kluster av ungefärligt samplanära prover, och avger röster för enskilda kluster (istället för för enskilda prover) på en ( θ , ϕ , ρ {\displaystyle \theta ,\phi ,\rho }

$\theta ,\phi ,\rho$

) sfärisk ackumulator med hjälp av en trevarierad gaussisk kärna. Metoden är flera storleksordningar snabbare än befintliga (icke-deterministiska) tekniker för att upptäcka plan i punktmoln, t.ex. RHT och RANSAC, och skalar bättre med storleken på datamängderna. Den kan användas i alla tillämpningar som kräver snabb upptäckt av plana element i stora datamängder.

Hough-transform av kurvor och dess generalisering för analytiska och icke-analytiska formerRedigera

Och om den version av transformationen som beskrivs ovan endast gäller för att hitta raka linjer, kan en liknande transform användas för att hitta vilken form som helst som kan representeras av en uppsättning parametrar. En cirkel kan till exempel omvandlas till en uppsättning av tre parametrar som representerar dess centrum och radie, så att Hough-rummet blir tredimensionellt. Godtyckliga ellipser och kurvor kan också hittas på detta sätt, liksom vilken form som helst som lätt kan uttryckas som en uppsättning parametrar.

Farandes och Oliveira föreslog en generalisering av Hough-transformen för att upptäcka analytiska former i utrymmen med valfri dimensionalitet. I motsats till andra Houghtransform-baserade metoder för analytiska former är Fernandes teknik inte beroende av vilken form man vill upptäcka och inte heller av typen av indata. Upptäckten kan styras till en typ av analytisk form genom att ändra den antagna geometriska modellen där data har kodats (t.ex. euklidisk rymd, projektiv rymd, konform geometri och så vidare), medan den föreslagna formuleringen förblir oförändrad. Dessutom garanterar den att de avsedda formerna representeras med minsta möjliga antal parametrar, och den gör det möjligt att samtidigt upptäcka olika typer av former som bäst passar en inmatningsuppsättning av poster med olika dimensioner och olika geometriska definitioner (t.ex. samtidig upptäckt av plan och sfärer som bäst passar en uppsättning punkter, räta linjer och cirklar).

För mer komplicerade former i planet (dvs, former som inte kan representeras analytiskt i något 2D-rum) används den generaliserade Hough-transformen, som gör det möjligt för en funktion att rösta för en viss position, orientering och/eller skalning av formen med hjälp av en fördefinierad uppslagstabell.Hough-transformen ackumulerar bidrag från alla pixlar i den detekterade kanten.

Process för detektering av cirklarRedigera

Huvudsartikel: Det är relativt enkelt att ändra algoritmen för att upptäcka cirkulära former i stället för linjer.

Först skapar vi ackumulatorutrymmet, som består av en cell för varje pixel. Initialt sätts varje cell till 0.
För varje kantpunkt (i, j) i bilden, ökas alla celler som enligt ekvationen för en cirkel ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}
$(i-a)^{2}+(j-b)^{2}=r^{2}$

skulle kunna vara centrum för en cirkel. Dessa celler representeras av bokstaven a {\displaystyle a}

$a$

i ekvationen.
För varje möjligt värde av a {\displaystyle a}
$a$

som hittats i föregående steg, hitta alla möjliga värden av b {\displaystyle b}

$b$

som uppfyller ekvationen.
Sök efter lokala maxima i ackumulatorrummet. Dessa celler representerar cirklar som upptäcktes av algoritmen.

Om vi inte känner till radien för den cirkel vi försöker lokalisera i förväg kan vi använda ett tredimensionellt ackumulatorrum för att söka efter cirklar med en godtycklig radie. Detta är naturligtvis mer beräkningskrävande.

Denna metod kan också upptäcka cirklar som delvis ligger utanför ackumulatorutrymmet, så länge tillräckligt mycket av cirkelns yta fortfarande finns inom det.

Upptäckt av 3D-objekt (plan och cylindrar)Redigera

Hough-transformationen kan också användas för att upptäcka 3D-objekt i avståndsdata eller 3D-punktmoln. Utvidgningen av den klassiska Hough-transformen för detektering av plan är ganska okomplicerad. Ett plan representeras av dess explicita ekvation z = a x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d}

$z=a_{x}x+a_{y}y+d$

för vilken vi kan använda ett 3D Hough-område som motsvarar a x {\displaystyle a_{x}}

$a_{x}$

, a y {\displaystyle a_{y}}

$a_{y}$

och d {\displaystyle d}

$d$

. Denna utvidgning lider av samma problem som dess motsvarighet i 2D, dvs. nära horisontella plan kan upptäckas på ett tillförlitligt sätt, medan prestandan försämras när planets riktning blir vertikal (stora värden på a x {\displaystyle a_{x}}

$a_{x}$

och a y {\displaystyle a_{y}}

$a_{y}$

förstärker bruset i data). Denna formulering av planet har använts för att upptäcka plan i punktmoln som förvärvats från flygburen laserskanning och fungerar mycket bra eftersom alla plan i den domänen är nästan horisontella.

För generaliserad plandetektering med hjälp av Hough-transformen kan planet parametriseras med dess normalvektor n {\displaystyle n}

$n$

(med sfäriska koordinater) och dess avstånd från ursprunget ρ {\displaystyle \rho }

$\rho$

vilket resulterar i ett tredimensionellt Hough-rum. Detta resulterar i att varje punkt i indatadata röstar för en sinusformad yta i Hough-rummet. Skärningen av dessa sinusytor visar att det finns ett plan. Ett mer generellt tillvägagångssätt för mer än tre dimensioner kräver sökheuristik för att vara genomförbart.

Hough-transformen har också använts för att hitta cylindriska objekt i punktmoln med hjälp av en tvåstegsmetod. Det första steget hittar cylinderns orientering och det andra steget hittar position och radie.

Användning av viktade funktionerRedigera

En vanlig variationsdetalj. Det vill säga, att hitta de bins med det högsta antalet i ett steg kan användas för att begränsa intervallet av värden som söks i nästa steg.

Noggrant valt parameterutrymmeRedigera

Ett högdimensionellt parameterutrymme för Hough-transformationen är inte bara långsamt, utan om det implementeras utan förutseende kan det lätt överträffa det tillgängliga minnet. Även om programmeringsmiljön tillåter tilldelning av en matris som är större än det tillgängliga minnesutrymmet genom virtuellt minne, kommer det antal sidbyten som krävs för detta att bli mycket krävande eftersom ackumulatormatrisen används på ett slumpmässigt sätt och sällan stannar i sammanhängande minne när den hoppar från index till index.

Tänk på uppgiften att hitta ellipser i en 800×600 bild. Om man antar att ellipsernas radier är orienterade längs huvudaxlarna är parameterutrymmet fyrdimensionellt. (x,y) definierar ellipsens centrum, och a och b anger de två radierna. Genom att låta centrum vara var som helst i bilden läggs begränsningen 0<x<800 och 0<y<600 till. Om radierna ges samma värden som begränsningar är det som återstår en sparsamt fylld ackumulatormatris med mer än 230 miljarder värden.

Ett program som är utformat på detta sätt kommer sannolikt inte att tillåtas allokera tillräckligt med minne. Detta betyder inte att problemet inte kan lösas, utan bara att nya sätt att begränsa storleken på ackumulatormatrisen måste hittas, vilket gör det genomförbart. Till exempel:

Om det är rimligt att anta att ellipserna var för sig finns helt och hållet inom bilden kan radiernas omfång minskas. De största radierna kan vara om ellipsens centrum ligger i mitten av bilden, vilket gör att ellipsens kanter kan sträcka sig till kanterna. I detta extrema fall kan radierna endast vara hälften så stora som bildstorleken i samma riktning. Genom att minska intervallet för a och b på detta sätt minskas ackumulatormatrisen till 57 miljarder värden.
Trafiken mellan noggrannhet och utrymme i uppskattningen av Hough-transformen ackumulerar bidrag från alla pixlar i den detekterade kanten. Hough-transformen ackumulerar bidrag från alla pixlar i den upptäckta kanten. han centrum: Om centrum förutspås vara avvikande med 3 på både x- och y-axeln minskar detta storleken på ackumulatormatrisen till cirka 6 miljarder värden.
Trade accuracy for space in the estimation of the radii: Om radierna beräknas avvika med 5 vardera minskar storleken på ackumulatormatrisen ytterligare, med cirka 256 miljoner värden.
Skärning av bilden till intressanta områden. Detta är bildberoende och därför oförutsägbart, men tänk dig ett fall där alla intressanta kanter i en bild finns i den övre vänstra kvadranten av bilden. Ackumulatormatrisen kan minskas ytterligare i detta fall genom att begränsa alla fyra parametrarna med en faktor 2, vilket ger en total minskningsfaktor på 16.

Om man tillämpar bara de tre första av dessa begränsningar på det angivna exemplet minskas storleken på ackumulatormatrisen med nästan en faktor 1 000, vilket gör att den kommer ner till en storlek som med större sannolikhet ryms i en modern dators minne.

Effektiv algoritm för ellipsdetekteringRedigera

Yonghong Xie och Qiang Ji ger ett effektivt sätt att implementera Hough-transformationen för ellipsdetektering genom att övervinna minnesproblemen. Såsom diskuteras i algoritmen (på sidan 2 i artikeln) använder detta tillvägagångssätt endast en endimensionell ackumulator (för den mindre axeln) för att upptäcka ellipser i bilden. Komplexiteten är O(N3) i antalet icke-nollpunkter i bilden.

Universe