Hough-transformation

Brug af gradientens retning til at reducere antallet af stemmerRediger

En forbedring foreslået af O’Gorman og Clowes kan bruges til at detektere linjer, hvis man tager hensyn til, at den lokale gradient af billedets intensitet nødvendigvis vil være ortogonal til kanten. Da kantdetektion generelt indebærer beregning af intensitetsgradientens størrelse, findes gradientens retning ofte som en sideeffekt. Hvis et givet punkt med koordinaterne (x,y) tilfældigvis befinder sig på en linje, giver den lokale gradientretning θ-parameteren, der svarer til denne linje, og r-parameteren fås derefter straks. (Shapiro og Stockman, 305) Gradientens retning kan estimeres med en nøjagtighed på 20°, hvilket forkorter sinusoidens spor fra de fulde 180° til ca. 45°. Dette reducerer beregningstiden og har den interessante effekt, at antallet af ubrugelige afstemninger reduceres, hvilket øger synligheden af de spidser, der svarer til reelle linjer i billedet.

Kernel-baseret Hough-transformation (KHT)Edit

Fernandes og Oliveira foreslog en forbedret afstemningsordning for Hough-transformationen, der gør det muligt for en softwareimplementering at opnå realtidspræstation selv på relativt store billeder (f.eks. 1280×960). Den kernebaserede Hough-transformation anvender den samme ( r , θ ) {\displaystyle (r,\theta )}

parameterisering, der er foreslået af Duda og Hart, men opererer på klynger af omtrent kollineære pixels. For hver klynge afgives der stemmer ved hjælp af en orienteret elliptisk-Gaussiansk kerne, der modellerer den usikkerhed, der er forbundet med den bedst tilpassede linje i forhold til den tilsvarende klynge. Denne fremgangsmåde forbedrer ikke blot afstemningsordningens ydeevne betydeligt, men giver også en meget renere akkumulator og gør transformationen mere robust over for detektion af falske linjer.

3-D Kernel-baseret Hough-transformation til detektering af planer (3DKHT)Edit

Limberger og Oliveira foreslog en deterministisk teknik til detektering af planer i uorganiserede punktskyer, hvis omkostninger er n log ( n ) {\displaystyle n\log(n)}

i antallet af prøver og opnår realtidspræstation for relativt store datasæt (op til 10 5 {\displaystyle 10^{5}}

punkter på en 3,4 GHz CPU). Den er baseret på en hurtig Hough-transform afstemningsstrategi for plane regioner, inspireret af den kernebaserede Hough-transformation (KHT). Denne 3D Kernel-baserede Hough-transformation (3DKHT) anvender en hurtig og robust algoritme til at segmentere klynger af omtrent samplanære prøver og afgiver stemmer for individuelle klynger (i stedet for for individuelle prøver) på en ( θ , ϕ , ρ {\displaystyle \theta ,\phi ,\rho }

) sfærisk akkumulator ved hjælp af en trevariat Gaussisk kerne. Denne fremgangsmåde er flere størrelsesordener hurtigere end eksisterende (ikke-deterministiske) teknikker til detektering af planer i punktskyer, såsom RHT og RANSAC, og den skalerer bedre med størrelsen af datasættene. Den kan anvendes i forbindelse med enhver applikation, der kræver hurtig detektion af plane træk i store datasæt.

Hough-transformation af kurver og dens generalisering til analytiske og ikke-analytiske formerRediger

Selv om den ovenfor beskrevne version af transformationen kun gælder for at finde lige linjer, kan en lignende transformation bruges til at finde enhver form, der kan repræsenteres af et sæt parametre. En cirkel kan f.eks. transformeres til et sæt af tre parametre, der repræsenterer dens centrum og radius, således at Hough-rummet bliver tredimensionalt. Vilkårlige ellipser og kurver kan også findes på denne måde, ligesom enhver form, der let kan udtrykkes som et sæt parametre.

Den generalisering af Hough-transformationen til påvisning af analytiske former i rum med en hvilken som helst dimensionalitet blev foreslået af Fernandes og Oliveira. I modsætning til andre Hough-transform-baserede metoder til analytiske former afhænger Fernandes’ teknik hverken af den form, man ønsker at opdage, eller af inputdatatypen. Detekteringen kan styres til en type analytisk form ved at ændre den antagne geometriske model, hvor dataene er blevet kodet (f.eks. euklidisk rum, projektivt rum, konform geometri osv.), mens den foreslåede formulering forbliver uændret. Desuden garanterer den, at de tilsigtede former repræsenteres med det mindst mulige antal parametre, og den giver mulighed for samtidig påvisning af forskellige former, der passer bedst til et input sæt af poster med forskellige dimensioner og forskellige geometriske definitioner (f.eks. samtidig påvisning af planer og kugler, der passer bedst til et sæt af punkter, rette linjer og cirkler).

For mere komplicerede former i planen (dvs, former, der ikke kan repræsenteres analytisk i et eller andet 2D-rum), anvendes den generaliserede Hough-transformation, som gør det muligt for en funktion at stemme for en bestemt position, orientering og/eller skalering af formen ved hjælp af en foruddefineret opslagstabel.Hough-transformationen akkumulerer bidrag fra alle pixels i den detekterede kant.

CirkeldetektionsprocesRediger

Det er relativt ligetil at ændre algoritmen til at detektere cirkulære former i stedet for linjer.

• Først opretter vi akkumulatorrummet, som består af en celle for hver pixel. I første omgang sættes hver celle til 0.
• For hvert kantpunkt (i, j) i billedet inkrementeres alle celler, som i henhold til ligningen for en cirkel ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}
  

  kunne være centrum for en cirkel. Disse celler er repræsenteret ved bogstavet a {\displaystyle a}

  

  i ligningen.

• For hver mulig værdi af a {\displaystyle a}
  

  fundet i det foregående trin, skal du finde alle mulige værdier af b {\displaystyle b}

  

  , som opfylder ligningen.

• Søg efter lokale maksima i akkumulatorrummet. Disse celler repræsenterer cirkler, der blev opdaget af algoritmen.

Hvis vi ikke på forhånd kender radius af den cirkel, vi forsøger at lokalisere, kan vi bruge et tredimensionelt akkumulatorrum til at søge efter cirkler med en vilkårlig radius. Dette er naturligvis mere beregningsmæssigt dyrt.

Denne metode kan også detektere cirkler, der ligger delvist uden for akkumulatorrummet, så længe nok af cirklens areal stadig er til stede inden for det.

Detektion af 3D-objekter (planer og cylindre)Rediger

Hough-transformationen kan også bruges til detektion af 3D-objekter i afstandsdata eller 3D-punktskyer. Udvidelsen af den klassiske Hough-transformation til detektion af planer er ret ligetil. Et plan repræsenteres ved sin eksplicitte ligning z = a x x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d}

hvortil vi kan anvende et 3D Hough-rum svarende til a x {\displaystyle a_{x}}

, a y {\displaystyle a_{y}}

og d {\displaystyle d}

. Denne udvidelse lider under de samme problemer som dens 2D-modstykke, dvs. at næsten vandrette planer kan detekteres pålideligt, mens ydeevnen forringes, når planernes retning bliver lodret (store værdier af a x {\displaystyle a_{x}}

og a y {\displaystyle a_{y}}

forstærker støjen i dataene). Denne formulering af planen er blevet anvendt til detektion af planer i punktskyer erhvervet fra luftbåren laserscanning og fungerer meget godt, fordi alle planer i dette domæne er næsten vandrette.

For generaliseret plandetektion ved hjælp af Hough-transformation kan planen parametriseres ved dens normalvektor n {\displaystyle n}

(ved hjælp af sfæriske koordinater) og dens afstand fra oprindelsen ρ {\displaystyle \rho }

, hvilket resulterer i et tredimensionalt Hough-rum. Dette resulterer i, at hvert punkt i inputdataene stemmer for en sinusformet overflade i Hough-rummet. Skæringspunktet mellem disse sinusflader angiver tilstedeværelsen af et plan. En mere generel fremgangsmåde for mere end 3 dimensioner kræver søgeheuristik for at forblive gennemførlig.

Hough-transformationen er også blevet anvendt til at finde cylindriske objekter i punktskyer ved hjælp af en tilgang i to trin. Det første trin finder cylinderens orientering, og det andet trin finder positionen og radius.

Brug af vægtede funktionerRediger

En almindelig variationsdetalje. Det vil sige, at det at finde de bins med det højeste antal i det ene trin kan bruges til at begrænse intervallet af værdier, der søges i det næste trin.

Omhyggeligt valgt parameterrumRediger

Et højdimensionelt parameterrum for Hough-transformationen er ikke blot langsomt, men kan, hvis det gennemføres uden forudseenhed, let overskride den tilgængelige hukommelse. Selv hvis programmeringsmiljøet tillader allokering af et array, der er større end den tilgængelige hukommelsesplads via virtuel hukommelse, vil det antal sideskift, der er nødvendige for dette, være meget krævende, fordi akkumulatorarrayet bruges på en måde, hvor der er tilfældig adgang, og sjældent stopper i sammenhængende hukommelse, når det hopper fra indeks til indeks.

Tænk på opgaven med at finde ellipser i et 800×600-billede. Hvis man antager, at ellipsernes radius er orienteret langs hovedakserne, er parameterrummet firedimensionalt. (x,y) definerer ellipsens centrum, og a og b angiver de to radier. Hvis man tillader, at centrum kan være hvor som helst i billedet, tilføjes begrænsningen 0<x<800 og 0<y<600. Hvis radiuserne får de samme værdier som begrænsninger, er der tilbage et sparsomt fyldt akkumulator array med mere end 230 milliarder værdier.

Et program, der er udformet på denne måde, vil sandsynligvis ikke få lov til at allokere tilstrækkelig hukommelse. Dette betyder ikke, at problemet ikke kan løses, men blot at der skal findes nye måder at begrænse størrelsen af akkumulatorarrayet på, hvilket gør det muligt. F.eks.:

1. Hvis det er rimeligt at antage, at ellipserne hver især er indeholdt helt inden for billedet, kan radiusernes rækkevidde reduceres. De største radier kan være, hvis ellipsens centrum ligger i midten af billedet, så ellipsens kanter kan strække sig til kanterne. I dette ekstreme tilfælde kan radierne kun være halvt så store som billedets størrelse i samme retning. Ved at reducere intervallet for a og b på denne måde reduceres akkumulatormatrixen til 57 milliarder værdier.
2. Trade nøjagtighed for plads i vurderingen af Hough-transformationen akkumulerer bidrag fra alle pixels i den detekterede kant. Hough-transformationen akkumulerer bidrag fra alle pixels i den detekterede kant. han centrum: Hvis centrum forudsiges at være afvigende med 3 på både x- og y-aksen, reducerer dette størrelsen af akkumulatormatrixen til ca. 6 milliarder værdier.
3. Trade nøjagtighed for plads i estimeringen af radierne: Hvis radiuserne skønnes at afvige med 5 hver især, reduceres størrelsen af akkumulatormatrixen yderligere, nemlig med ca. 256 millioner værdier.
4. Billedet beskæres til de interessante områder. Dette er billedafhængigt og derfor uforudsigeligt, men forestil dig et tilfælde, hvor alle de interessante kanter i et billede befinder sig i den øverste venstre kvadrant af billedet. I dette tilfælde kan akkumulatormatrixen reduceres yderligere ved at begrænse alle 4 parametre med en faktor 2, hvilket giver en samlet reduktionsfaktor på 16.

Gennem at anvende blot de tre første af disse begrænsninger på det nævnte eksempel reduceres størrelsen af akkumulatormatrixen med næsten en faktor 1000, hvilket bringer den ned på en størrelse, der er meget mere egnet til at passe i en moderne computers hukommelse.

Effektiv algoritme til ellipsedetektionRediger

Yonghong Xie og Qiang Ji giver en effektiv måde at implementere Hough-transformationen til ellipsedetektion på ved at overvinde hukommelsesproblemerne. Som det fremgår af algoritmen (på side 2 i artiklen), bruger denne metode kun en endimensional akkumulator (til den mindre akse) til at registrere ellipser i billedet. Kompleksiteten er O(N3) i antallet af ikke-nul-punkter i billedet.