Hough transformere

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. marts 2021; checks kræver 2 redigeringer .

Hough Transform er en beregningsalgoritme , der bruges til parametrisk identifikation af de geometriske elementer i et rasterbillede (1962 patent af Paul Hough). Anvendes til billedanalyse, digital billedbehandling og computersyn . Designet til at søge efter objekter, der tilhører en bestemt klasse af figurer ved hjælp af afstemningsproceduren. Afstemningsproceduren anvendes på parameterrummet, hvorfra objekter af en bestemt klasse af figurer opnås i henhold til det lokale maksimum i det såkaldte akkumulatorrum , som bygges ved beregning af Hough-transformationen.

Den klassiske Hough-transformationsalgoritme beskæftiger sig med at identificere linjer i et billede, men senere blev algoritmen udvidet til at identificere positionen af en vilkårlig figur, oftest ellipser og cirkler . Hough-transformationen, som den bruges i dag, blev opfundet i 1981. Denne algoritme blev kaldt den " generaliserede Hough transformation " og blev foreslået af Dana Ballard .

Teori

I den automatiserede analyse af digitale billeder opstår ofte problemet med at identificere simple former, såsom linjer, cirkler eller ellipser. I mange tilfælde bruges en kantsøgningsalgoritme som en forbehandling for at opnå punkter, der er på en kurve i et billede. Men enten på grund af billedstøj eller en ufuldkommen kantdetektionsalgoritme, kan "tabte" punkter på kurven forekomme, såvel som små afvigelser fra den ideelle form af en lige linje, cirkel eller ellipse. Af disse grunde er det ofte ret svært at tilskrive de fundne grænser til de tilsvarende linjer, cirkler og ellipser i billedet. Formålet med Hough-transformationen er at løse problemet med at gruppere grænsepunkter ved at anvende en bestemt stemmeprocedure på et sæt parameteriserede billedobjekter.

I det enkleste tilfælde er Hough-transformationen en lineær transformation til linjedetektion. Den rette linje kan gives ved ligningen y = mx + b og kan beregnes ud fra et hvilket som helst par af punkter ( x, y ) i billedet. Hovedideen med Hough-transformationen er at tage højde for egenskaberne ved en lige linje, ikke som en ligning konstrueret ud fra et par billedpunkter, men i forhold til dens parametre, det vil sige, m er hældningen og b er skæringspunktet med y-aksen. Ud fra dette kan den rette linje givet af ligningen y = mx + b repræsenteres som et punkt med koordinater ( b, m ) i parameterrummet.

Linjer parallelt med y-aksen har dog uendelige værdier for parameteren m [1] [2] . Derfor er det mere bekvemt at repræsentere linjen ved hjælp af andre parametre, kendt som og [ rho, theta ]. Parameteren er længden af radiusvektoren for punktet på linjen tættest på origo (det vil sige normalen til linjen trukket fra origo), og er vinklen mellem denne vektor og x-aksen. Med en sådan beskrivelse af lige linjer opstår der ikke uendelige parametre. $r$ $\theta$ $r$ $\theta$

Således kan ligningen for en ret linje skrives som

y=\left(-{\cos \theta \over \sin \theta}\right)x+\left({r \over {\sin \theta }}\right)

eller efter konvertering

r=x\cos \theta +y\sin \theta

Derfor er det muligt at tilknytte hver linje i det originale billede (i XY-planet) et punkt med koordinaterne r, θ i parameterplanet, hvilket er unikt forudsat at og , eller at og . $\theta \in [0,\pi ]$ $r\in \mathbf {R}$ $\theta \in [0,2\pi ]$ $r\geq 0$

Planet ( r,θ ) kaldes undertiden Hough Space for et sæt linjer i det 2-dimensionelle tilfælde. Hough-transformationen er konceptuelt meget tæt på 2D Radon- transformationen og kan opfattes som dens diskrete repræsentation.

Gennem hvert punkt i planet kan der være uendeligt mange linjer. Hvis dette punkt har koordinater , svarer alle linjer, der går igennem det, til ligningen: $(x_{0},y_{0})$

$r(\theta )=x_{0}\cdot \cos \theta +y_{0}\cdot \sin \theta$ .

Dette svarer til en sinusformet linje i Hough-rummet ( r, θ ), som igen er unik for et givet punkt og entydigt definerer det. Hvis disse linjer (kurver) svarende til to punkter overlapper hinanden, så svarer punktet (i Hough space ), hvor de skærer hinanden, til rette linjer (på den oprindelige billedplacering), der passerer gennem begge punkter. Generelt definerer et sæt punkter, der danner en lige linje, sinusoider, der skærer hinanden ved parameterpunktet for den linje. Således kan problemet med at detektere kollineære punkter reduceres til problemet med at detektere krydsende kurver.

Implementering

Hough-transformationsalgoritmen bruger et array kaldet akkumulatoren til at bestemme tilstedeværelsen af linjen y = mx + b . Akkumulatorens dimension er lig med antallet af ukendte parametre for Hough-rummet. For eksempel, for en lineær transformation, skal du bruge en todimensional matrix, da der er to ukendte parametre: m og b . Akkumulatorens to dimensioner svarer til de kvantiserede værdier af parametrene m og b . For hvert punkt og dets naboer bestemmer algoritmen, om vægten af grænsen på det punkt er tilstrækkelig. Hvis ja, så beregner algoritmen parametrene for linjen og øger værdien i akkumulatorcellen svarende til de givne parametre.

Derefter, ved at finde cellerne i akkumulatoren med maksimale værdier, normalt ved at søge efter et lokalt maksimum i akkumulatorrummet, kan de bedst egnede linjer bestemmes. Den nemmeste måde er tærskelfiltrering. Forskellige metoder kan dog give forskellige resultater i forskellige situationer. Da de opnåede linjer ikke indeholder information om længden, er næste trin at finde de dele af billedet, der svarer til de fundne linjer. På grund af fejl på stadiet med bestemmelse af grænserne for figurer vil akkumulatorrummet desuden også indeholde fejl. Dette gør det ikke-trivielt at finde passende linjer.

Eksempel

Overvej det originale testbillede af tre sorte prikker. Tjek om punkterne er på en lige linje.

Gennem hvert punkt tegnet (for overskuelighedens skyld) kun seks lige linjer med forskellige vinkler.
En vinkelret tegnes til hver linje fra origo.
For alle rette linjer er længden af den tilsvarende vinkelret og dens vinkel med abscisseaksen tabuleret.
Disse tabeller er resultatet af Hough-transformationen og kan tjene som grundlag for en grafisk repræsentation i "Hough-rummet".

Koordinaterne for skæringspunktet for sinusoiderne bestemmer parametrene for den lige linje, der er fælles for de punkter, der kontrolleres på det originale billede.

Det følgende eksempel viser resultaterne af Hough-transformationen for et billede med to skærende linjer.

Resultaterne af denne transformation lagres i matrixen. Værdierne i cellerne i matrixen repræsenterer antallet af kurver, der passerer gennem punktet. De maksimale værdier i cellerne svarer til to lysere punkter på billedet og parametrene for de tilsvarende linjer. De to lyse pletter er skæringspunkterne mellem to buede linjer. Fra disse pletter kan du bestemme vinklen og afstanden til den lige linje i det originale billede.

Begrænsninger

Hough-transformationen er kun effektiv, hvis der er et betydeligt antal "hits" i det tilsvarende element i Hough-rummet, kun da er det muligt at bestemme figuren med tillid og negligere baggrundsstøjen. Dette betyder, at størrelsen af elementet ikke bør være meget lille, ellers vil nogle værdier falde ind i tilstødende elementer, hvilket reducerer synligheden af det ønskede element.

Når antallet af parametre er stort (større end tre), er det gennemsnitlige antal hits på et element lille, og derfor vil det korrekte element ikke være meget forskelligt fra dets naboer. Algoritmen skal således bruges med stor omhu for ikke at definere andet end lige linjer og cirkler.

Algoritmens effektivitet bestemmes i høj grad af kvaliteten af inputdataene: grænserne for figurerne på stadiet af billedforbehandling skal være klart defineret. Det er svært at bruge Hough-transformationen på støjende billeder. For støjende billeder kræves et forbehandlingstrin for at reducere støjen. I tilfælde af at billedet er beskadiget, plettet , som i tilfældet med et radarindikatorbillede , er Radon-transformationen at foretrække til linjedetektion, da den har en god dæmpende effekt på stabling.

Se også

Noter

↑ PDF-dokument: Brug af Hough-transformationen til at opdage linjer og kurver i billeder (link ikke tilgængeligt) . Hentet 23. maj 2008. Arkiveret fra originalen 13. marts 2012. (ubestemt)
↑ Hough Transform . Hentet 2. november 2014. Arkiveret fra originalen 2. november 2014. (ubestemt)