Hough-transzformáció

A gradiens irányának használata a szavazatok számának csökkentéséreSzerkesztés

Az O’Gorman és Clowes által javasolt fejlesztés használható a vonalak detektálására, ha figyelembe vesszük, hogy a kép intenzitásának helyi gradiense szükségszerűen ortogonális lesz az élre. Mivel az élek detektálása általában az intenzitásgradiens nagyságának kiszámításával jár, a gradiens irányát gyakran mellékesen találjuk meg. Ha egy adott (x,y) koordinátájú pont valóban egy egyenesre esik, akkor a gradiens helyi iránya adja az említett egyenesnek megfelelő θ paramétert, és azonnal megkapjuk az r paramétert. (Shapiro és Stockman, 305) A gradiens iránya 20°-os pontossággal becsülhető, ami a szinuszvonal nyomvonalát a teljes 180°-ról nagyjából 45°-ra rövidíti. Ez csökkenti a számítási időt, és érdekes hatása, hogy csökken a haszontalan szavazatok száma, így javul a képen a valós vonalaknak megfelelő tüskék láthatósága.

Kernel-based Hough transform (KHT)Edit

Fernandes és Oliveira egy továbbfejlesztett szavazási sémát javasolt a Hough-transzformációhoz, amely lehetővé teszi egy szoftveres megvalósítással a valós idejű teljesítmény elérését még viszonylag nagy képeken (pl. 1280×960) is. A Kernel-alapú Hough-transzformáció ugyanazt a ( r , θ ) {\displaystyle (r,\theta )}

paraméterezést, amelyet Duda és Hart javasolt, de megközelítőleg kollineáris pixelekből álló klasztereken dolgozik. Minden egyes klaszter esetében a szavazatokat egy orientált elliptikus-Gauss kernel segítségével adjuk le, amely a megfelelő klaszterhez legjobban illeszkedő vonalhoz kapcsolódó bizonytalanságot modellezi. Ez a megközelítés nemcsak a szavazási séma teljesítményét javítja jelentősen, hanem sokkal tisztább akkumulátort eredményez, és a transzformációt robusztusabbá teszi a hamis vonalak észlelésével szemben.

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

Limberger és Oliveira egy determinisztikus technikát javasolt síkok detektálására rendezetlen pontfelhőkben, amelynek költsége n log ( n ) {\displaystyle n\log(n)}.

a minták számában, valós idejű teljesítményt elérve viszonylag nagy adathalmazok esetén (akár 10 5 {\displaystyle 10^{5}}}

pontot egy 3,4 GHz-es CPU-n). Alapja egy gyors Hough-transzformációs szavazási stratégia síkbeli régiókra, amelyet a Kernel-alapú Hough-transzformáció (KHT) ihletett. Ez a 3D Kernel-alapú Hough-transzformáció (3DKHT) gyors és robusztus algoritmust használ a megközelítőleg egysíkú minták klasztereinek szegmentálására, és az egyes klaszterekre (az egyes minták helyett) szavazatokat ad le egy ( θ , ϕ , ρ {\displaystyle \theta ,\phi ,\rho }

) gömbhalmazon egy háromváltozós Gauss-kernel segítségével. A megközelítés több nagyságrenddel gyorsabb, mint a pontfelhőkben a síkok felismerésére szolgáló meglévő (nem determinisztikus) technikák, például az RHT és a RANSAC, és jobban skálázódik az adathalmazok méretével. Bármilyen olyan alkalmazással használható, amely nagy adathalmazokon a síkbeli jellemzők gyors detektálását igényli.

Görbék Hough-transzformációja és annak általánosítása analitikus és nem analitikus alakzatokraSzerkesztés

Bár a transzformáció fent leírt változata csak egyenes vonalak megtalálására alkalmazható, egy hasonló transzformáció bármely olyan alakzat megtalálására használható, amely paraméterek halmazával reprezentálható. Egy kör például átalakítható a középpontját és sugarát reprezentáló három paraméterből álló halmazzá, így a Hough-tér háromdimenziós lesz. Tetszőleges ellipszisek és görbék szintén megtalálhatók ily módon, akárcsak bármilyen, paraméterek halmazaként könnyen kifejezhető alakzat.

A Hough-transzformáció általánosítását analitikus alakzatok felismerésére bármilyen dimenziójú terekben Fernandes és Oliveira javasolta. Az analitikus alakzatok más Hough-transzformáción alapuló megközelítéseivel ellentétben Fernandes technikája nem függ sem a detektálni kívánt alakzattól, sem a bemeneti adatok típusától. A detektálás az analitikus alakzat típusához vezethető a geometria feltételezett modelljének megváltoztatásával, ahol az adatokat kódolták (pl. euklideszi tér, projektív tér, konformális geometria stb.), miközben a javasolt megfogalmazás változatlan marad. Emellett garantálja, hogy a kívánt alakzatokat a lehető legkisebb számú paraméterrel reprezentálja, és lehetővé teszi a különböző típusú alakzatok egyidejű felismerését, amelyek a legjobban illeszkednek egy különböző dimenziójú és különböző geometriai definíciójú bemeneti adathalmazhoz (pl. a pontok, egyenesek és körök halmazához legjobban illeszkedő síkok és gömbök egyidejű felismerése).

A bonyolultabb síkbeli alakzatok (pl, alakzatok, amelyek nem ábrázolhatók analitikusan valamilyen 2D-s térben), az általánosított Hough-transzformációt használják, amely lehetővé teszi, hogy egy jellemző egy előre meghatározott keresőtáblázat segítségével szavazzon az alakzat egy adott pozíciójára, orientációjára és/vagy méretezésére.A Hough-transzformáció az észlelt él összes pixelének hozzájárulásait felhalmozza.

Körfelismerési eljárásSzerkesztés

Az algoritmus módosítása úgy, hogy vonalak helyett kör alakzatokat észleljen, viszonylag egyszerű.

• Először létrehozzuk a felhalmozási teret, amely minden egyes pixelhez tartozó cellából áll. Kezdetben minden egyes cellát 0-ra állítunk.
• A kép minden egyes (i, j) élpontja esetében növeljük az összes cellát, amelyek a kör ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}}
  

  lehet a kör középpontja. Ezeket a cellákat az egyenletben az a {\displaystyle a}

  

  betű jelöli.

• Az előző lépésben talált a {\displaystyle a}
  

  minden lehetséges értékére keressük meg a b {\displaystyle b}

  

  minden lehetséges értékét, amely kielégíti az egyenletet.

• Keresünk helyi maximumokat a halmazterében. Ezek a cellák az algoritmus által felismert köröket jelölik.

Ha nem tudjuk előre a keresett kör sugarát, akkor egy háromdimenziós akkumulátortérben tetszőleges sugarú köröket kereshetünk. Ez természetesen számításigényesebb.

Ez a módszer képes olyan köröket is felismerni, amelyek részben kívül esnek a felhalmozási téren, amennyiben a kör területéből még elegendő van benne.

3D objektumok felismerése (Síkok és hengerek)Edit

A Hough-transzformáció 3D objektumok felismerésére is használható távolsági adatokban vagy 3D pontfelhőkben. A klasszikus Hough-transzformáció kiterjesztése síkok detektálására meglehetősen egyszerű. Egy síkot a z = a x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d} explicit egyenletével ábrázolunk.

, amelyhez használhatjuk az a x {\displaystyle a_{x}}} megfelelő 3D Hough teret.

, a y {\displaystyle a_{y}}

és d {\displaystyle d}

. Ez a kiterjesztés ugyanazokkal a problémákkal küzd, mint 2D-s megfelelője, azaz a közel vízszintes síkok megbízhatóan detektálhatók, míg a teljesítmény romlik, ahogy a sík iránya függőlegessé válik (nagy értékek a x {\displaystyle a_{x}}

és a y {\displaystyle a_{y}}

felerősítik a zajt az adatokban). A síknak ezt a megfogalmazását használták a síkok detektálására a légi lézerszkenneléssel szerzett pontfelhőkben, és nagyon jól működik, mivel ebben a tartományban minden sík közel vízszintes.

A Hough-transzformációval történő általános síkdetektáláshoz a sík paraméterezhető az n {\displaystyle n} normálvektorával.

(gömbi koordinátákat használva) és az origótól való távolságával ρ {\displaystyle \rho }

, ami egy háromdimenziós Hough teret eredményez. Ez azt eredményezi, hogy a bemeneti adatok minden egyes pontja egy szinuszos felületre szavaz a Hough-térben. E szinuszos felületek metszéspontja jelzi egy sík jelenlétét. A 3 dimenziónál több dimenzióra vonatkozó általánosabb megközelítés megvalósíthatóságához keresési heurisztikára van szükség.

A Hough-transzformációt kétlépéses megközelítéssel hengeres objektumok megtalálására is használták pontfelhőkben. Az első lépés a henger orientációját, a második lépés pedig a helyzetét és sugarát találja meg.

Súlyozott jellemzők használataSzerkesztés

Egy gyakori variációs részlet. Ez azt jelenti, hogy az egyik lépésben a legnagyobb számmal rendelkező tárolók megtalálása felhasználható a következő lépésben keresett értékek tartományának korlátozására.

Gondosan megválasztott paramétertérSzerkesztés

A Hough-transzformáció nagydimenziós paramétertere nemcsak lassú, de átgondolatlanul megvalósítva könnyen túlterhelheti a rendelkezésre álló memóriát. Még ha a programozási környezet lehetővé is teszi a rendelkezésre álló memóriaterületnél nagyobb tömb kiosztását a virtuális memórián keresztül, az ehhez szükséges lapcserék száma nagyon megterhelő lesz, mivel a felhalmozási tömböt véletlenszerű eléréssel használjuk, ritkán áll meg egybefüggő memóriában, mivel indexről indexre ugrál.

Gondoljunk arra a feladatra, hogy egy 800×600-as képen ellipsziseket keressünk. Feltételezve, hogy az ellipszisek sugarai a főtengelyek mentén helyezkednek el, a paramétertér négydimenziós. (x,y) határozza meg az ellipszis középpontját, a és b pedig a két sugarat jelöli. Ha megengedjük, hogy a középpont bárhol legyen a képen, hozzáadjuk a 0<x<800 és 0<y<600 korlátot. Ha a sugaraknak ugyanazokat az értékeket adjuk meg, mint a kényszerek, akkor egy több mint 230 milliárd értéket tartalmazó, ritkán töltött akkumulátortömb marad.

Egy így elképzelt programnak valószínűleg nem engedjük, hogy elegendő memóriát rendeljen ki. Ez nem azt jelenti, hogy a probléma nem megoldható, hanem csak azt, hogy az akkumulátor tömb méretének korlátozására új módokat kell találni, ami megvalósíthatóvá teszi. Például:

1. Ha ésszerű feltételezni, hogy az ellipszisek mindegyike teljes egészében a képen belül van, akkor a sugarak tartománya csökkenthető. A sugarak akkor lehetnek a legnagyobbak, ha az ellipszis középpontja a kép közepén van, lehetővé téve, hogy az ellipszis szélei a szélek felé nyúljanak. Ebben a szélsőséges esetben a sugarak egyenként csak az azonos irányba orientált képméret nagyságának fele lehetnek. Az a és b tartomány ilyen módon történő csökkentése 57 milliárd értékre csökkenti a felhalmozási tömböt.
2. A Hough-transzformáció becslésénél a pontosságot a helyért cserébe a Hough-transzformáció az észlelt él összes pixelének hozzájárulását felhalmozza. A Hough-transzformáció a detektált élben lévő összes pixel hozzájárulását felhalmozza. he központ: Ha a középpontot mind az x-, mind az y-tengelyen 3-mal tévesztjük meg, ez a felhalmozási tömb méretét körülbelül 6 milliárd értékre csökkenti.
3. Trade accuracy for space in the estimation of the radii:
4. A képet az érdeklődésre számot tartó területekre vágjuk. Ez képfüggő, és ezért megjósolhatatlan, de képzeljünk el egy olyan esetet, amikor egy kép összes érdekes éle a kép bal felső kvadránsában van. Az akkumulátortömb ebben az esetben még tovább csökkenthető, ha mind a 4 paramétert 2-szeres szorzóval korlátozzuk, így a teljes csökkentési tényező 16.

Ezek közül csak az első három korlátozást alkalmazva a fenti példára, az akkumulátortömb mérete közel 1000-szeresére csökken, így olyan méretűvé válik, amely sokkal inkább elfér egy modern számítógép memóriájában.

Hatékony ellipszisfelismerő algoritmusSzerkesztés

Yonghong Xie és Qiang Ji a memóriaproblémák leküzdésével hatékony módját adja a Hough-transzformáció megvalósításának az ellipszisfelismeréshez. Az algoritmusban (a cikk 2. oldalán) tárgyaltak szerint ez a megközelítés csak egy egydimenziós akkumulátort használ (a kis tengelyhez) az ellipszisek detektálásához a képen. A komplexitás O(N3) a képen található nem nulla pontok számában.