Transformata Hough

Utilizarea direcției gradientului pentru a reduce numărul de voturiEdit

O îmbunătățire sugerată de O’Gorman și Clowes poate fi utilizată pentru a detecta liniile dacă se ia în considerare faptul că gradientul local al intensității imaginii va fi în mod necesar ortogonal la margine. Deoarece detectarea marginilor implică, în general, calcularea magnitudinii gradientului de intensitate, direcția gradientului este adesea găsită ca un efect secundar. Dacă se întâmplă ca un anumit punct de coordonate (x,y) să se afle într-adevăr pe o linie, atunci direcția locală a gradientului dă parametrul θ corespunzător liniei respective, iar parametrul r se obține imediat. (Shapiro și Stockman, 305) Direcția gradientului poate fi estimată cu o precizie de 20°, ceea ce scurtează urma sinusoidală de la 180° la aproximativ 45°. Acest lucru reduce timpul de calcul și are efectul interesant de a reduce numărul de voturi inutile, sporind astfel vizibilitatea vârfurilor care corespund liniilor reale din imagine.

Kernel-based Hough transform (KHT)Edit

Fernandes și Oliveira au sugerat o schemă de vot îmbunătățită pentru transformarea Hough care permite ca o implementare software să atingă performanțe în timp real chiar și pe imagini relativ mari (de exemplu, 1280×960). Transformarea Hough bazată pe Kernel utilizează aceeași ( r , θ ) {\displaystyle (r,\theta )}

parametrizarea propusă de Duda și Hart, dar operează pe clustere de pixeli aproximativ coliniari. Pentru fiecare cluster, voturile sunt exprimate cu ajutorul unui nucleu eliptico-gaussian orientat care modelează incertitudinea asociată cu linia care se potrivește cel mai bine în raport cu clusterul corespunzător. Abordarea nu numai că îmbunătățește în mod semnificativ performanța sistemului de vot, dar produce, de asemenea, un acumulator mult mai curat și face ca transformarea să fie mai rezistentă la detectarea liniilor false.

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

Limberger și Oliveira au sugerat o tehnică deterministă pentru detectarea planurilor în norii de puncte neorganizate al cărei cost este n log ( n ) {\displaystyle n\log(n)}.

în numărul de eșantioane, obținând performanțe în timp real pentru seturi de date relativ mari (până la 10 5 {\displaystyle 10^{5}}

puncte pe un procesor de 3,4 GHz). Se bazează pe o strategie de votare rapidă a transformării Hough pentru regiuni plane, inspirată de transformarea Hough bazată pe Kernel (KHT). Această transformare Hough 3D bazată pe Kernel (3DKHT) utilizează un algoritm rapid și robust pentru a segmenta grupuri de eșantioane aproximativ coplanare și votează pentru grupuri individuale (în loc să voteze pentru eșantioane individuale) pe un ( θ , ϕ , ρ {\displaystyle \theta ,\phi ,\rho }

) acumulator sferic folosind un nucleu gaussian trivariat. Abordarea este cu câteva ordine de mărime mai rapidă decât tehnicile existente (nedeterministe) pentru detectarea planurilor în norii de puncte, cum ar fi RHT și RANSAC, și se adaptează mai bine la dimensiunea seturilor de date. Aceasta poate fi utilizată în orice aplicație care necesită detectarea rapidă a caracteristicilor plane pe seturi mari de date.

Transformarea Hough a curbelor și generalizarea sa pentru forme analitice și non-analiticeEdit

Deși versiunea transformării descrisă mai sus se aplică numai pentru găsirea liniilor drepte, o transformare similară poate fi utilizată pentru găsirea oricărei forme care poate fi reprezentată printr-un set de parametri. Un cerc, de exemplu, poate fi transformat într-un set de trei parametri, reprezentând centrul și raza sa, astfel încât spațiul Hough devine tridimensional. Elipsele și curbele arbitrare pot fi, de asemenea, găsite în acest mod, la fel ca orice formă ușor de exprimat ca un set de parametri.

Generalizarea transformării Hough pentru detectarea formelor analitice în spații având orice dimensionalitate a fost propusă de Fernandes și Oliveira. Spre deosebire de alte abordări bazate pe transformata Hough pentru forme analitice, tehnica lui Fernandes nu depinde de forma pe care se dorește a fi detectată și nici de tipul de date de intrare. Detecția poate fi direcționată către un tip de formă analitică prin schimbarea modelului presupus de geometrie în care au fost codificate datele (de exemplu, spațiu euclidian, spațiu proiectiv, geometrie conformă etc.), în timp ce formularea propusă rămâne neschimbată. De asemenea, garantează că formele vizate sunt reprezentate cu cel mai mic număr posibil de parametri și permite detectarea concomitentă a diferitelor tipuri de forme care se potrivesc cel mai bine unui set de intrări de intrare cu dimensiuni diferite și definiții geometrice diferite (de exemplu, detectarea concomitentă a planurilor și sferelor care se potrivesc cel mai bine unui set de puncte, linii drepte și cercuri).

Pentru forme mai complicate în plan (de ex, forme care nu pot fi reprezentate analitic într-un spațiu 2D oarecare), se utilizează transformarea Hough generalizată, care permite ca o caracteristică să voteze pentru o anumită poziție, orientare și/sau scalare a formei folosind un tabel de căutare predefinit.Transformarea Hough acumulează contribuții de la toți pixelii din marginea detectată.

Procesul de detectare a cercurilorEdit

Alterarea algoritmului pentru a detecta formele circulare în loc de linii este relativ simplă.

• În primul rând, creăm spațiul de acumulare, care este alcătuit dintr-o celulă pentru fiecare pixel. Inițial, fiecare celulă este setată la 0.
• Pentru fiecare punct de margine (i, j) din imagine, se incrementează toate celulele care, în conformitate cu ecuația unui cerc ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}}.
  

  ar putea fi centrul unui cerc. Aceste celule sunt reprezentate de litera a {\displaystyle a}

  

  în ecuație.

• Pentru fiecare valoare posibilă a {\displaystyle a}
  

  găsită în etapa anterioară, găsiți toate valorile posibile ale lui b {\displaystyle b}

  

  care satisfac ecuația.

• Căutați maximele locale în spațiul acumulatorului. Aceste celule reprezintă cercuri care au fost detectate de algoritm.

Dacă nu cunoaștem în prealabil raza cercului pe care încercăm să-l localizăm, putem folosi un spațiu acumulator tridimensional pentru a căuta cercuri cu o rază arbitrară. Bineînțeles, acest lucru este mai costisitor din punct de vedere computațional.

Această metodă poate detecta, de asemenea, cercuri care se află parțial în afara spațiului de acumulare, atâta timp cât o cantitate suficientă din aria cercului este încă prezentă în interiorul acestuia.

Detectarea obiectelor 3D (Planuri și cilindri)Edit

Transformarea Hough poate fi utilizată, de asemenea, pentru detectarea obiectelor 3D în datele de distanță sau în norii de puncte 3D. Extinderea transformării Hough clasice pentru detectarea planurilor este destul de simplă. Un plan este reprezentat prin ecuația sa explicită z = a x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d}.

pentru care putem folosi un spațiu Hough 3D corespunzător lui a x {\displaystyle a_{x}}.

, a y {\displaystyle a_{y}}

și d {\displaystyle d}

. Această extensie suferă de aceleași probleme ca și omologul său 2D, și anume, planurile aproape orizontale pot fi detectate în mod fiabil, în timp ce performanța se deteriorează pe măsură ce direcția plană devine verticală (valori mari ale lui a x {\displaystyle a_{x}}

și a y {\displaystyle a_{y}}

amplifică zgomotul din date). Această formulare a planului a fost utilizată pentru detectarea planurilor în norii de puncte achiziționați prin scanare laser aeropurtată și funcționează foarte bine, deoarece în acest domeniu toate planurile sunt aproape orizontale.

Pentru detectarea generalizată a planurilor cu ajutorul transformării Hough, planul poate fi parametrizat prin vectorul său normal n {\displaystyle n}

(folosind coordonate sferice) și distanța sa față de origine ρ {\displaystyle \rho }

rezultând un spațiu Hough tridimensional. Astfel, fiecare punct din datele de intrare votează pentru o suprafață sinusoidală în spațiul Hough. Intersecția acestor suprafețe sinusoidale indică prezența unui plan. O abordare mai generală pentru mai mult de 3 dimensiuni necesită o euristică de căutare pentru a rămâne fezabilă.

Transformarea Hough a fost, de asemenea, utilizată pentru a găsi obiecte cilindrice în norii de puncte folosind o abordare în două etape. Prima etapă găsește orientarea cilindrului, iar a doua etapă găsește poziția și raza.

Utilizarea caracteristicilor ponderateEdit

Un detaliu de variație comun. Adică, găsirea binișoarelor cu cel mai mare număr într-o etapă poate fi folosită pentru a constrânge intervalul de valori căutate în etapa următoare.

Spațiu de parametri ales cu grijăEdit

Un spațiu de parametri cu dimensiuni mari pentru transformata Hough nu numai că este lent, dar dacă este implementat fără o gândire prealabilă poate depăși cu ușurință memoria disponibilă. Chiar dacă mediul de programare permite alocarea unui array mai mare decât spațiul de memorie disponibil prin intermediul memoriei virtuale, numărul de schimburi de pagini necesare pentru aceasta va fi foarte solicitant, deoarece array-ul de acumulatori este utilizat într-un mod accesat aleatoriu, oprindu-se rareori în memorie contiguă pe măsură ce sare de la un index la altul.

Considerați sarcina de a găsi elipse într-o imagine de 800×600. Presupunând că razele elipsei sunt orientate de-a lungul axelor principale, spațiul parametrilor este cvadridimensional. (x,y) definește centrul elipsei, iar a și b desemnează cele două raze. Dacă se permite ca centrul să fie oriunde în imagine, se adaugă constrângerea 0<x<800 și 0<y<600. Dacă razele primesc aceleași valori ca și constrângeri, ceea ce rămâne este o matrice de acumulatori slab umplută cu peste 230 de miliarde de valori.

Este puțin probabil ca un program astfel conceput să fie lăsat să aloce suficientă memorie. Acest lucru nu înseamnă că problema nu poate fi rezolvată, ci doar că trebuie găsite noi modalități de a constrânge dimensiunea tabloului de acumulatori, ceea ce o face fezabilă. De exemplu:

1. Dacă este rezonabil să se presupună că elipsele sunt fiecare conținute în întregime în interiorul imaginii, intervalul razei poate fi redus. Cele mai mari raze pot fi dacă centrul elipsei se află în centrul imaginii, permițând ca marginile elipsei să se întindă până la margini. În acest caz extrem, fiecare dintre raze poate fi doar jumătate din mărimea imaginii orientate în aceeași direcție. Reducerea intervalului lui a și b în acest mod reduce matricea de acumulatori la 57 de miliarde de valori.
2. Trade precizia pentru spațiu în estimarea transformării Hough acumulează contribuții de la toți pixelii din marginea detectată. Transformarea Hough acumulează contribuții de la toți pixelii din marginea detectată. el centru: Dacă se prezice că centrul este deplasat cu 3 atât pe axa x, cât și pe axa y, acest lucru reduce dimensiunea matricei de acumulatori la aproximativ 6 miliarde de valori.
3. Precizia schimbului pentru spațiu în estimarea razei: În cazul în care se estimează că fiecare dintre raze este diferită de 5, are loc o reducere suplimentară a dimensiunii matricei de acumulatori, cu aproximativ 256 de milioane de valori.
4. Cuplați imaginea în zonele de interes. Acest lucru depinde de imagine și, prin urmare, este imprevizibil, dar imaginați-vă un caz în care toate marginile de interes dintr-o imagine se află în cadranul din stânga sus al imaginii respective. Matricea de acumulatori poate fi redusă și mai mult în acest caz prin constrângerea tuturor celor 4 parametri cu un factor de 2, pentru un factor de reducere total de 16.

Prin aplicarea doar a primelor trei dintre aceste constrângeri la exemplul menționat mai sus, dimensiunea matricei de acumulatori este redusă cu aproape un factor de 1000, aducând-o la o dimensiune care este mult mai probabil să încapă în memoria unui calculator modern.

Algoritm eficient de detectare a elipseiEdit

Yonghong Xie și Qiang Ji oferă o modalitate eficientă de implementare a transformării Hough pentru detectarea elipsei prin depășirea problemelor de memorie. După cum se discută în algoritm (la pagina 2 a lucrării), această abordare utilizează doar un acumulator unidimensional (pentru axa minoră) pentru a detecta elipsele din imagine. Complexitatea este O(N3) în numărul de puncte non-zero din imagine.

.