Hough-transformatie

De gradiëntrichting gebruiken om het aantal stemmen te verminderenEdit

Een door O’Gorman en Clowes voorgestelde verbetering kan worden gebruikt om lijnen te detecteren als men er rekening mee houdt dat de lokale gradiënt van de beeldintensiteit noodzakelijkerwijs loodrecht op de rand zal staan. Aangezien bij kantdetectie meestal de grootte van de intensiteitsgradiënt wordt berekend, wordt de richting van de gradiënt vaak als neveneffect gevonden. Als een gegeven punt met coördinaten (x,y) inderdaad op een lijn ligt, dan geeft de lokale richting van de gradiënt de θ parameter die overeenkomt met die lijn, en de r parameter wordt dan onmiddellijk verkregen. (Shapiro en Stockman, 305) De richting van de gradiënt kan tot op 20° nauwkeurig worden geschat, waardoor het spoor van de sinusoïde wordt ingekort van de volle 180° tot ruwweg 45°. Dit vermindert de rekentijd en heeft het interessante effect dat het aantal nutteloze stemmen wordt verminderd, waardoor de zichtbaarheid van de pieken die corresponderen met echte lijnen in het beeld wordt verbeterd.

Kernel-based Hough transform (KHT)Edit

Fernandes en Oliveira stelden een verbeterd stemschema voor de Hough transform voor, waarmee een software-implementatie zelfs op relatief grote beelden (b.v. 1280×960) real-time prestaties kan bereiken. De Kernel-gebaseerde Hough-transformatie maakt gebruik van dezelfde ( r , θ )

parametrisering zoals voorgesteld door Duda en Hart, maar werkt op clusters van ongeveer collineaire pixels. Voor elke cluster wordt gestemd met behulp van een georiënteerde elliptisch-Gaussische kernel die de onzekerheid modelleert die samenhangt met de best passende lijn ten opzichte van de overeenkomstige cluster. De aanpak verbetert niet alleen de prestaties van het stemschema aanzienlijk, maar levert ook een veel schonere accumulator op en maakt de transformatie robuuster voor de detectie van valse lijnen.

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

Limberger en Oliveira stelden een deterministische techniek voor vlakdetectie in ongeorganiseerde puntenwolken voor, waarvan de kosten n log ( n ) zijn {\displaystyle n\log(n)}

in het aantal monsters, waarbij real-time prestaties worden bereikt voor relatief grote datasets (tot 10 5 {\displaystyle 10^{5}}

punten op een 3,4 GHz CPU). Het is gebaseerd op een snelle Hough-transform stemstrategie voor vlakke gebieden, geïnspireerd op de Kernel-gebaseerde Hough-transformatie (KHT). Deze 3D Kernel-gebaseerde Hough-transformatie (3DKHT) gebruikt een snel en robuust algoritme om clusters van ongeveer co-planaire monsters te segmenteren, en brengt stemmen uit voor individuele clusters (in plaats van voor individuele monsters) op een ( θ , ϕ , ρ {{displaystyle \theta,\phi,\rho }

) sferische accumulator met behulp van een trivariate Gaussiaanse kernel. De aanpak is verscheidene grootteordes sneller dan bestaande (niet-deterministische) technieken voor vlakdetectie in puntwolken, zoals RHT en RANSAC, en schaalt beter met de grootte van de datasets. Het kan worden gebruikt voor elke toepassing die snelle detectie van vlakke kenmerken op grote datasets vereist.

Hough transform van krommen, en zijn veralgemening voor analytische en niet-analytische vormenEdit

Hoewel de hierboven beschreven versie van de transformatie alleen van toepassing is op het vinden van rechte lijnen, kan een soortgelijke transformatie worden gebruikt voor het vinden van elke vorm die kan worden voorgesteld door een set parameters. Een cirkel, bijvoorbeeld, kan worden getransformeerd in een set van drie parameters, die zijn middelpunt en straal voorstellen, zodat de Hough ruimte driedimensionaal wordt. Arbitraire ellipsen en krommen kunnen ook op deze manier worden gevonden, evenals elke vorm die gemakkelijk kan worden uitgedrukt als een verzameling parameters.

De veralgemening van de Hough transform voor het detecteren van analytische vormen in ruimten met elke dimensionaliteit werd voorgesteld door Fernandes en Oliveira. In tegenstelling tot andere Hough transform-gebaseerde benaderingen voor analytische vormen, hangt Fernandes’ techniek niet af van de vorm die men wil detecteren, noch van het type invoergegevens. De detectie kan worden gestuurd naar een type analytische vorm door het veronderstelde model van de geometrie waarin de gegevens zijn gecodeerd te veranderen (b.v. euclidische ruimte, projectieve ruimte, conforme geometrie, enzovoort), terwijl de voorgestelde formulering ongewijzigd blijft. Bovendien garandeert ze dat de bedoelde vormen worden voorgesteld met het kleinst mogelijke aantal parameters, en maakt ze de gelijktijdige detectie mogelijk van verschillende soorten vormen die het best passen bij een inputverzameling van gegevens met verschillende dimensionaliteiten en verschillende geometrische definities (b.v. de gelijktijdige detectie van vlakken en bollen die het best passen bij een verzameling punten, rechte lijnen en cirkels).

Voor meer ingewikkelde vormen in het vlak (d.w.z, vormen die niet analytisch kunnen worden voorgesteld in een of andere 2D-ruimte), wordt de gegeneraliseerde Hough-transformatie gebruikt, waarmee een kenmerk kan worden gestemd voor een bepaalde positie, oriëntatie en/of schaling van de vorm met behulp van een vooraf gedefinieerde opzoektabel.De Hough-transformatie accumuleert bijdragen van alle pixels in de gedetecteerde rand.

Cirkel detectieprocesEdit

Het algoritme aanpassen om cirkelvormen te detecteren in plaats van lijnen is relatief eenvoudig.

• Eerst maken we de accumulatorruimte, die bestaat uit een cel voor elke pixel. Aanvankelijk wordt elke cel op 0 gezet.
• Voor elk randpunt (i, j) in de afbeelding worden alle cellen opgehoogd, die volgens de vergelijking van een cirkel ( i – a ) 2 + ( j – b ) 2 = r 2 {displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}
  

  zou het middelpunt van een cirkel kunnen zijn. Deze cellen worden voorgesteld door de letter a {{displaystyle a}

  

  in de vergelijking.

• Voor elke mogelijke waarde van a {{displaystyle a}
  

  gevonden in de vorige stap, zoek alle mogelijke waarden van b {{displaystyle b}

  

  die voldoen aan de vergelijking.

• Zoek naar lokale maxima in de accumulatorruimte. Deze cellen staan voor cirkels die door het algoritme zijn gedetecteerd.

Als we de straal van de cirkel die we proberen te lokaliseren niet van tevoren weten, kunnen we een driedimensionale accumulatorruimte gebruiken om te zoeken naar cirkels met een willekeurige straal. Uiteraard is dit computationeel duurder.

Deze methode kan ook cirkels detecteren die gedeeltelijk buiten de accumulatorruimte liggen, zolang er maar genoeg van het gebied van de cirkel nog in aanwezig is.

Detectie van 3D-objecten (vlakken en cilinders)

Hough transform kan ook worden gebruikt voor de detectie van 3D-objecten in range data of 3D-puntenwolken. De uitbreiding van de klassieke Hough transform voor vlakdetectie is vrij rechttoe rechtaan. Een vlak wordt voorgesteld door zijn expliciete vergelijking z = a x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d}

waarvoor we een 3D Hough-ruimte kunnen gebruiken die overeenkomt met a x {{x}}

, a y {\displaystyle a_{y}}

en d {\displaystyle d}

. Deze uitbreiding lijdt aan dezelfde problemen als zijn 2D tegenhanger, d.w.z. dat bijna horizontale vlakken betrouwbaar kunnen worden gedetecteerd, terwijl de prestaties verslechteren naarmate de vlakrichting verticaal wordt (grote waarden van a x {\displaystyle a_{x}}

en a y {\displaystyle a_{y}}

versterken de ruis in de gegevens). Deze formulering van het vlak is gebruikt voor de detectie van vlakken in de puntenwolken die zijn verkregen met laserscanning vanuit de lucht en werkt zeer goed omdat in dat domein alle vlakken bijna horizontaal zijn.

Voor algemene vlakdetectie met behulp van de Hough-transformatie kan het vlak worden geparametriseerd door zijn normaalvector n {{\displaystyle n}

(met sferische coördinaten) en de afstand tot de oorsprong ρ {{\displaystyle \rho }

, wat resulteert in een driedimensionale Hough-ruimte. Dit resulteert in elk punt in de invoergegevens dat stemt voor een sinusoïdaal oppervlak in de Hough-ruimte. Het snijpunt van deze sinusvormige oppervlakken geeft de aanwezigheid van een vlak aan. Een meer algemene aanpak voor meer dan 3 dimensies vereist zoek-heuristieken om haalbaar te blijven.

Hough transform is ook gebruikt om cilindrische objecten in puntenwolken te vinden met een aanpak in twee stappen. De eerste stap vindt de oriëntatie van de cilinder en de tweede stap de positie en radius.

Using weighted featuresEdit

Een veel voorkomende variatie detail. Dat wil zeggen, het vinden van de bins met de hoogste telling in de ene stap kan worden gebruikt om het bereik van de gezochte waarden in de volgende te beperken.

Zorgvuldig gekozen parameterruimteEdit

Een hoog-dimensionale parameterruimte voor de Hough-transformatie is niet alleen traag, maar kan, indien geïmplementeerd zonder voorbedachte rade, gemakkelijk het beschikbare geheugen overschrijden. Zelfs als de programmeeromgeving de toewijzing van een array groter dan de beschikbare geheugenruimte via virtueel geheugen toestaat, zal het aantal pagina swaps dat hiervoor nodig is zeer veeleisend zijn, omdat de accumulator array wordt gebruikt op een willekeurig benaderde manier, zelden stoppend in aaneengesloten geheugen als het van index naar index springt.

Overweeg de taak van het vinden van ellipsen in een 800×600 afbeelding. Aangenomen dat de stralen van de ellipsen georiënteerd zijn langs de hoofdassen, is de parameterruimte vier-dimensionaal. (x,y) definieert het middelpunt van de ellips, en a en b geven de twee stralen aan. Als we toestaan dat het middelpunt overal in het beeld ligt, voegen we de restrictie 0<x<800 en 0<y<600 toe. Als de stralen dezelfde waarden krijgen als de constraints, blijft er een schaars gevulde accumulator array over van meer dan 230 miljard waarden.

Het is onwaarschijnlijk dat een programma dat zo is opgezet, voldoende geheugen mag toewijzen. Dit betekent niet dat het probleem niet kan worden opgelost, maar alleen dat er nieuwe manieren moeten worden gevonden om de grootte van de accumulator array te beperken, waardoor het haalbaar wordt. Bijvoorbeeld:

1. Als het redelijk is aan te nemen dat de ellipsen elk geheel binnen het beeld liggen, kan het bereik van de stralen worden verkleind. De radii kunnen het grootst zijn als het middelpunt van de ellips in het midden van het beeld ligt, zodat de randen van de ellips zich naar de randen kunnen uitstrekken. In dit extreme geval kunnen de stralen elk slechts de halve grootte van de in dezelfde richting georiënteerde afbeeldingsgrootte zijn. Door het bereik van a en b op deze manier te verkleinen, wordt de accumulator-reeks gereduceerd tot 57 miljard waarden.
2. Het ruilen van nauwkeurigheid voor ruimte bij de schatting van de Hough-transformatie accumuleert bijdragen van alle pixels in de gedetecteerde rand. De Hough-transformatie accumuleert bijdragen van alle pixels in de gedetecteerde rand. het centrum: Als wordt voorspeld dat het middelpunt er zowel op de x-as als op de y-as 3 naast ligt, wordt de accumulator-array ongeveer 6 miljard keer zo groot.
3. Handelsnauwkeurigheid voor ruimte bij de schatting van de stralen: Als de stralen elk met 5 worden geschat, neemt de omvang van de accumulator array verder af, met ongeveer 256 miljoen waarden.
4. Snijd het beeld bij tot gebieden die van belang zijn. Dit is afhankelijk van het beeld, en daarom onvoorspelbaar, maar stel je een geval voor waarin alle randen van belang in een beeld in het kwadrant linksboven van dat beeld liggen. De accumulator-reeks kan in dit geval nog verder worden verkleind door alle 4 parameters met een factor 2 te beperken, voor een totale verkleiningsfactor van 16.

Door alleen de eerste drie van deze beperkingen toe te passen op het genoemde voorbeeld, wordt de omvang van de accumulator-reeks met bijna een factor 1000 verkleind, waardoor deze wordt teruggebracht tot een omvang die veel waarschijnlijker is dat hij in het geheugen van een moderne computer past.

Efficiënt algoritme voor ellipsdetectieEdit

Yonghong Xie en Qiang Ji geven een efficiënte manier om de Hough transform voor ellipsdetectie te implementeren door de geheugenproblemen op te lossen. Zoals besproken in het algoritme (op pagina 2 van het artikel), gebruikt deze aanpak slechts een één-dimensionale accumulator (voor de korte as) om ellipsen in het beeld te detecteren. De complexiteit is O(N3) in het aantal niet-nul punten in het beeld.