Den Hough omdanne er en anerkendelse mønster teknik opfundet i 1959 af Paul Hough , emnet for et patent, og anvendes i digital billedbehandling .
Den enkleste applikation gør det muligt at detektere linjerne i et billede, men der kan foretages ændringer til denne teknik for at detektere andre geometriske former: dette er den generaliserede Hough-transformation udviklet af Richard Duda og Peter Hart i 1972.
Det stillede problem er at søge efter og opdage linjer, som muligvis ville være til stede i et analyseret billede på trods af billedets mangler: manglende punkter (linjen kan delvist maskeres af et objekt), støj. Hough-transformeringen består i at repræsentere hvert kantpunkt, der detekteres i et todimensionalt parameterrum:
Hough-transformationen af et punkt i det analyserede billede er kurven for parametrerummet svarende til sættet med lige linjer, der passerer gennem dette punkt.
Hvis punkter er kollektive, krydser alle kurverne i parameterrummet det punkt, der repræsenterer den pågældende linje.
På grund af billedets ufuldkommenheder er de opdagede punkter ikke perfekt justeret, og derfor er kurverne ikke perfekt samtidige. Metoden består derfor i at diskretisere parameterrummet, at skære det i små rektangler og at tælle antallet af kurver, der passerer gennem det for hvert rektangel. En såkaldt akkumuleringsmatrix konstrueres således, hvor den lokale maksimum for denne matrix svarer til sandsynlige linjer.
Algoritmen har derfor tre faser:
Oprindeligt karakteriserede Hough linjer ved deres hældning og deres y-skæring . Ulempen ved denne tilgang er, at hældningen har en tendens til uendelig, når linjen har en tendens til at være lodret. I 1972 foreslog Duda og Hart en parametrisering af polære koordinater (ρ, θ), som siden er blevet brugt universelt.
En linje (D) kan karakteriseres ved polære parametre (ρ, θ):
Koordinaterne ( x , y ) for punkterne i denne lige linje verificerer den såkaldte "normale" ligning:
ρ = x ⋅ cos (θ) + y ⋅ sin (θ)Det antages først og fremmest, at hvis linjer eller lige segmenter er til stede i et billede, vil de være en del af de konturer, der findes i billedet. Det første trin er derfor at identificere alle konturpunkterne i dette billede, for eksempel ved hjælp af teknikker til måling af lokale gradienter mellem værdierne af pixels omkring hvert punkt i billedet, såsom Canny-filteret . Punktene i billedet, der viser de højeste gradienter i deres kvarter, enten globalt for billedet (fast tærskelværdi) eller i forhold til de gradienter, der generelt er til stede i et bredere kvarter omkring punktet (dynamisk tærskelværdi), er mest sandsynligt at høre til konturerne af dette billede.
Hver af punkterne i de således identificerede konturer ( x , y ) tillader derefter en projektion i et plan (det transformerede plan) af de polære koordinater for alle de linjer, der passerer gennem dette punkt. Ligningerne af linjerne, der passerer gennem hvert af disse punkter ( x , y ), er derfor repræsenteret af et par (ρ, θ), der verificerer
ρ = x ⋅ cos (θ) + y ⋅ sin (θ)Ved punktet ( x , y ) i konturen svarer vi derfor til en kurve ρ = ƒ (θ) hvor θ tager alle mulige værdier fra 0 til 2 π rad (0 til 360 ° ), med
ƒ (θ) = x ⋅ cos (θ) + y ⋅ sin (θ).Denne kurve er en sinusbølge. I praksis varierer vi θ fra 0 til π rad (0 til 180 ° ), og vi betragter en algebraisk radius (positiv eller negativ). Parameteren ρ tager værdier mellem –R og + R hvor R er billedets store diagonal: R = √ l 2 + h 2 , l er bredden på billedet og h dets højde.
Når kurverne ρ (θ) svarende til to punkter mødes, kendetegner skæringspunktet linjen, der passerer gennem de to punkter.
Derfor forbinder vi i planet (θ, ρ) med hvert punkt en tæthed svarende til antallet af kurver, der passerer gennem det. Jo større tæthed, jo flere konturpunkter findes der på denne linje. Linjen er derfor sandsynligvis et segment i billedet.
I praksis vil det transformerede Hough-rum blive repræsenteret af et billede, hvis abscisser er vinklerne θ, hvis ordinater er værdierne for ρ, og hvis intensitet på ethvert punkt (θ, ρ) er antallet af forekomster af (θ, ρ ) fra det originale billede. Der antages ikke nogen antagelse om kontinuitet af de lige linjer eller lige segmenter af startbilledet, hvilket gør transformationen robust til fraværet af punkter: delvis maskering af linjerne og støj i billedet.
Værdierne for θ kan for eksempel diskretiseres i grader (i henhold til den ønskede præcision), og værdierne for ρ i pixels repræsenterer afstanden (altid mindre i absolut værdi end diameteren på startbilledet), frekvensen begrænset af antallet af punkter valgt i konturerne af startbilledet.
Algoritmen er derfor i pseudokode:
Importe : I % image matricielle J ← contours de I % p.ex. filtre de Canny Définit : δ % pas de discrétisation 1. M ← 0 % initialisation de la matrice d'accumulation 2. pour chaque pixel (x, y) de J faire 3. pour θ allant de 0 à 180 avec le pas δ 4. ρ ← x*cos(θ) + y*sin(θ) 5. M(ρ, θ) ← M(ρ, θ) + 1 6. fin de boucle 7. fin de boucle Détection des pics de M
I Houghtransformationen, også kendt som standard Houghtransformationen eller SHT, er hver linje en vektor med parametriske koordinater:
Ved at transformere alle de mulige linjer, der passerer gennem et punkt, dvs. ved at beregne værdien af ρ for hver θ, opnår vi en enkelt sinusformet kaldet "Hough space". Hvis kurverne forbundet med to punkter krydser hinanden, svarer det sted, hvor de krydser hinanden i Hough-rummet, parametrene for en linje, der forbinder disse to punkter.
Konturregistrering indebærer bestemmelse af billedets kontrastgradient. Faktisk er retningen af denne gradient vinkelret på konturens retning. I stedet for at tegne sinusoiderne for θ, der varierer fra 0 til 180 ° , kan vi begrænse os til et område omkring de således viste orienteringer. Denne metode blev foreslået af O'Gorman og Clowes i 1976 og kaldes GHT ( gradientbaseret Hough-transformation ).
Fernandes og Oliveira har foreslået en forbedring for at fremskynde behandlingen til det punkt, hvor de kan behandle billeder op til 1280 × 960 pixels i realtid. Metoden er som følger:
Denne metode kaldes KHT ( Kernel-based Hough transform ).
Metoden kan anvendes på en hvilken som helst kurve, der er repræsenteret af en kartesisk eller parametrisk ligning.
Den cirkel påvisningsmetode kaldes også HCT ( Hough cirkel transformation ) .
I denne metode er en cirkel beskrevet ved sin cartesiske ligning :
( x - a ) 2 + ( y - b ) 2 = r 2eller
I rummet ( a , b , r ) er en cirkel karakteriseret ved et punkt. Sættet af cirkler, der passerer gennem et givet punkt M ( x , y ), danner en kegle af toppunktet ( a = x , b = y , r = 0) og af aksen r . En "god kandidat" er skæringspunktet mellem flere kegler.
Hvis radius af den søgte cirkel er kendt, kan vi derefter placere os i planet ( a , b ). I dette plan er cirkelsættet, der passerer gennem M, beskrevet af cirklen med centrum ( a = x , b = y ) og radius r . En god kandidat er derfor i krydset mellem flere cirkler. Vi konstruere en ophobning matrix A: hvert element A i, j af matrixen indeholder nummeret på cirkler passerer gennem det punkt, eller også gennem en kvadratisk af flere pixels, der svarer til dette element.
Hvis radiusen er ukendt, består søgemetoden i at konstruere en akkumuleringshypermatrix, hvor hver celle Ai , j, k svarer til en terning af rummet ( a , b , r ) ved at scanne alle mulige stråler på 1 pixel op til billedets størrelse.
Ansøgninger
En cirkel er projektionen af en sfærisk genstand på et plan eller af et cirkulært snit (cylinder, kegle, torus) forudsat at objektets akse er vinkelret på projektionsplanet (ellers er fremspringet en ellipse). Genkendelsen af cirkulære former kan bruges til at detektere hoveder og derfor mennesker i et fotografi eller et videoovervågningsbillede. Det kan også bruges til at detektere aneurismer på et angiogram .
En ellipse er karakteriseret ved fem parametre, typisk:
Dette betyder, at den direkte implementering af Hough-transformationen sker i et femdimensionelt rum, der involverer en betydelig computertid og kræver en stor hukommelseskapacitet. Flere algoritmer er blevet foreslået for at reducere antallet af krævede parametre.
I 1978 foreslog Tsuji og Matsumoto at bruge kontrastgradienten til at bestemme vinkelret på tangenten. I betragtning af de punkter, der har parallelle tangenser, bestemmer de placeringen af ellipsernes centre. Derefter bruger de de geometriske egenskaber til at adskille ellipserne fra andre objekter med den samme egenskab, til sidst bestemmes ellipsernes parametre ved metoden med mindste kvadrater
I 1994 foreslog Yin og Chen at vælge grupper på fem punkter, et tilstrækkeligt antal til at bestemme en ellipse. Til dette klassificeres punkterne i underbilleder. Billedet af de opdagede konturpunkter kaldes F. Algoritmen scanner fra top til bund med en vandret linje og tager de punkter, der er placeret på denne linje. Han betragter midtpunkterne for de således definerede segmenter, disse midtpunkter af segmenter danner et billede kaldet G. For en given ellipse ligger segmenternes midtpunkter på den samme lige linje, den lige linje afhængigt af hældningen på hovedaksen; denne linje kaldes "symmetriakse", fordi punkterne ikke er symmetriske ved refleksion, men af en lighed mellem forholdet 1. Disse linjer bestemmes af den klassiske Hough-transformation af G. Derefter skaber algoritmen delbilleder af F dannet af punkter, der genererer en given linje af G; således klassificeres punkterne for F efter deres mulige tilhørsforhold til en ellipse med en given symmetriakse. Hvert underbillede behandles derefter separat. I et underbillede, for hvert par punkter (A, B), bestemmer algoritmen fem punkter:
Parameterne for ellipsen bestemmes ud fra disse fem punkter, og akkumuleringsmatricen opdateres for dette sæt af parametre. grænserne for denne metode er:
I 1995 skabte Ho og Chen to underrum på en måde svarende til Yin og Chen. Den første består i at overveje par konturpunkter placeret på den samme vandrette linje og tage midtpunkterne på de således dannede segmenter. Det andet underrum er konstrueret på samme måde, men ved at overveje de par af punkter, der er placeret på den samme lodrette. Algoritmen udfører derefter en detektion af de linjer, der dannes af disse midtpunkter med den klassiske Hough-transformation, hvor krydset mellem disse linjer giver centrum for ellipserne. De bestemmer derefter de tre resterende parametre (bestemmelse af hoved- og mindre akse).
En lignende metode består i at overveje par af punkter: gradienten giver adgang til tangenten, hvis tangenterne ikke er parallelle, krydser de hinanden ved et punkt T. Linjen, der forbinder dette punkt til midten af segmentet, passerer gennem midten af ellipsen .
I 2002 foreslog Xie og Ji en metode til at udføre en søgning på kun en parameter, længden af den semi-mindre akse. De tager et par punkterne A 1 ( x 1 , y 1 ) og A 2 ( x 2 , y 2 ) tilstrækkeligt langt fra hinanden, og antager, at de er placeret på hovedaksen af en ellipse. Med denne antagelse er centrum af ellipsen nødvendigvis i midten O af [A 1 A 2 ], længden af hovedaksen er 2 a = A 1 A 2 og hældningen af hovedaksen er θ = arctan (( y 2 - y 1 ) / ( x 2 - x 1 )). Derefter overvejer de hvert konturpunkt M: hvis det er tilstrækkeligt tæt på O til at være på en ellipse med en stor akse [A 1 A 2 ], så bruges punktet M til at beregne den semi-mindre akse b af ellipsen. Det er denne parameter b, der bruges til at opbygge akkumuleringsmatrixen. Hvis matrixen indeholder en top, der er stor nok til at karakterisere en ellipse, bevares ellipsen. Derefter algoritmen passerer til et andet par (A 1 , A 2 ). Algoritmen består derfor i at udføre en Hough-transformation for hvert af parene med tilstrækkeligt fjerne punkter, men denne transformation finder kun sted på en enkelt parameter. På den anden side skal billedet vise enderne af hovedaksen for at en ellipse kan detekteres.
Ansøgninger
En ellipse er projektionen af et cirkulært snit på et plan. Ellipsedetekteringen tillader derfor detektering af cylindriske eller toriske genstande såsom pupiller i øjnene, trafikskilte og køretøjshjul.