Hough se transformă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 6 martie 2021; verificările necesită 2 modificări .

Transformarea Hough  este un  algoritm de calcul utilizat pentru identificarea parametrică a elementelor geometrice ale unei imagini raster (brevet din 1962 de Paul Hough). Folosit în analiza imaginilor, imagistica digitală și viziunea computerizată . Conceput pentru a căuta obiecte aparținând unei anumite clase de figuri folosind procedura de vot. Procedura de vot se aplică spațiului parametrilor, din care se obțin obiecte dintr-o anumită clasă de cifre în funcție de maximul local din așa-numitul spațiu de acumulare , care este construit la calcularea transformării Hough.

Algoritmul clasic de transformare Hough se ocupă de identificarea liniilor dintr-o imagine, dar mai târziu algoritmul a fost extins pentru a identifica poziția unei figuri arbitrare, cel mai frecvent elipse și cercuri . Transformarea Hough, așa cum este folosită astăzi, a fost inventată în 1981. Acest algoritm a fost numit „ transformată Hough generalizată ” și a fost propus de Dana Ballard .

Teorie

În analiza automatizată a imaginilor digitale, se pune adesea problema identificării formelor simple, precum linii, cercuri sau elipse. În multe cazuri, un algoritm de căutare a marginilor este utilizat ca pre-procesare pentru a obține puncte care se află pe o curbă dintr-o imagine. Cu toate acestea, fie din cauza zgomotului imaginii, fie din cauza unui algoritm imperfect de detectare a marginilor, pot apărea puncte „pierdute” pe curbă, precum și ușoare abateri de la forma ideală a unei linii drepte, cerc sau elipse. Din aceste motive, este adesea destul de dificil să atribuiți limitele găsite liniilor, cercurilor și elipselor corespunzătoare din imagine. Scopul transformării Hough este de a rezolva problema grupării punctelor limită prin aplicarea unei anumite proceduri de vot la un set de obiecte imagine parametrizate.

În cel mai simplu caz, transformarea Hough este o transformare liniară pentru detectarea liniei. Linia dreaptă poate fi dată de ecuația y = mx + b și poate fi calculată din orice pereche de puncte ( x, y ) din imagine. Ideea principală a transformării Hough este de a lua în considerare caracteristicile unei linii drepte nu ca o ecuație construită dintr-o pereche de puncte de imagine, ci în ceea ce privește parametrii săi, adică m  este panta și b  este punct de intersecție cu axa y. Pe baza acesteia, dreapta dată de ecuația y = mx + b poate fi reprezentată ca un punct cu coordonatele ( b, m ) în spațiul parametrilor.

Cu toate acestea, liniile paralele cu axa y au valori infinite pentru parametrul m [1] [2] . Prin urmare, este mai convenabil să reprezentați linia folosind alți parametri, cunoscuți ca și [ rho, theta ]. Parametrul  este lungimea vectorului rază a punctului de pe linia cel mai apropiat de origine (adică normala liniei trase de la origine) și  este unghiul dintre acest vector și axa x. Cu o astfel de descriere a liniilor drepte, nu apar parametri infiniti.

Astfel, ecuația unei linii drepte poate fi scrisă ca

,

sau după conversie

.

Prin urmare, este posibil să se asocieze fiecărei linii din imaginea originală (în planul XY) un punct cu coordonatele r, θ în planul parametrilor, care este unic cu condiția ca și , sau că și .

Planul ( r,θ ) este uneori numit spațiu Hough pentru un set de linii în cazul bidimensional. Transformarea Hough este conceptual foarte apropiată de transformarea Radon 2D și poate fi considerată ca reprezentarea sa discretă.

Prin fiecare punct al planului pot exista infinit de linii. Dacă acest punct are coordonatele , atunci toate liniile care trec prin el corespund ecuației:

.

Aceasta corespunde unei linii sinusoidale în spațiul Hough ( r, θ ), care, la rândul său, este unică pentru un punct dat și îl definește în mod unic. Dacă aceste linii (curbe) corespunzătoare la două puncte se suprapun, atunci punctul (în spațiul Hough ) unde se intersectează corespunde liniilor drepte (la locația originală a imaginii) care trec prin ambele puncte. În general, un set de puncte care formează o linie dreaptă definesc sinusoidele care se intersectează în punctul parametru al dreptei respective. Astfel, problema detectării punctelor coliniare poate fi redusă la problema detectării curbelor care se intersectează.

Implementare

Algoritmul de transformare Hough folosește o matrice numită acumulator pentru a determina prezența liniei y = mx + b . Dimensiunea acumulatorului este egală cu numărul de parametri necunoscuți ai spațiului Hough. De exemplu, pentru o transformare liniară, trebuie să utilizați o matrice bidimensională, deoarece există doi parametri necunoscuți: m și b . Cele două dimensiuni ale acumulatorului corespund valorilor cuantificate ale parametrilor m și b . Pentru fiecare punct și vecinii săi, algoritmul determină dacă greutatea limitei în acel punct este suficientă. Dacă da, atunci algoritmul calculează parametrii liniei și crește valoarea din celula acumulatorului corespunzătoare parametrilor dați.

Apoi, prin găsirea celulelor acumulatorului cu valori maxime, de obicei prin căutarea unui maxim local în spațiul acumulatorului, pot fi determinate liniile cele mai potrivite. Cel mai simplu mod este filtrarea pragului. Cu toate acestea, metode diferite pot da rezultate diferite în situații diferite. Deoarece liniile obținute nu conțin informații despre lungime, următorul pas este găsirea părților din imagine corespunzătoare liniilor găsite. Mai mult, din cauza erorilor la etapa de determinare a limitelor figurilor, spațiul acumulatorului va conține și erori. Acest lucru face ca găsirea liniilor potrivite să nu fie banală.

Exemplu

Luați în considerare imaginea de testare originală a trei puncte negre. Verificați dacă punctele sunt pe o linie dreaptă.

Coordonatele punctului de intersecție al sinusoidelor determină parametrii dreptei comuni punctelor care se verifică pe imaginea originală.

Următorul exemplu arată rezultatele transformării Hough pentru o imagine cu două linii care se intersectează.

Rezultatele acestei transformări sunt stocate în matrice. Valorile din celulele matricei reprezintă numărul de curbe care trec prin punct. Valorile maxime din celule corespund celor două puncte mai luminoase ale imaginii și parametrilor liniilor corespunzătoare. Cele două puncte luminoase sunt intersecțiile a două linii curbe. Din aceste puncte, puteți determina unghiul și distanța față de linia dreaptă din imaginea originală.

Restricții

Transformarea Hough este eficientă numai dacă există un număr semnificativ de „hituri” în elementul corespunzător al spațiului Hough, numai atunci este posibil să se determine cifra cu încredere, neglijând zgomotul de fond. Aceasta înseamnă că dimensiunea elementului nu trebuie să fie foarte mică, altfel unele valori vor cădea în elemente învecinate, reducând vizibilitatea elementului dorit.

De asemenea, atunci când numărul de parametri este mare (mai mare de trei), numărul mediu de accesări pe un element este mic și, prin urmare, elementul corect nu va fi foarte diferit de vecinii săi. Astfel, algoritmul trebuie folosit cu mare grijă pentru a nu defini altceva decât linii drepte și cercuri.

Eficiența algoritmului este determinată în mare măsură de calitatea datelor de intrare: limitele figurilor în etapa de preprocesare a imaginii trebuie clar definite. Utilizarea transformării Hough pe imagini zgomotoase este dificilă. Pentru imagini zgomotoase, este necesar un pas de preprocesare pentru a suprima zgomotul. În cazul în care imaginea este coruptă, pete , ca în cazul unei imagini cu indicator radar , transformarea Radon este de preferată pentru detectarea liniei, deoarece are un efect bun de dezgomot la stivuire.

Vezi și

Note

  1. ↑ Document PDF: Utilizarea transformării Hough pentru a detecta liniile și curbele în imagini (link nu este disponibil) . Preluat la 23 mai 2008. Arhivat din original la 13 martie 2012. 
  2. ↑ Transformarea Hough . Consultat la 2 noiembrie 2014. Arhivat din original pe 2 noiembrie 2014.

Link -uri