Hough-muunnos

Gradientin suunnan käyttäminen äänimäärän vähentämiseksiEdit

O’Gormanin ja Clowesin ehdottamaa parannusta voidaan käyttää viivojen havaitsemiseen, jos otetaan huomioon, että kuvan intensiteetin paikallinen gradientti on välttämättä kohtisuorassa reunaan nähden. Koska reunan havaitseminen edellyttää yleensä intensiteettigradientin suuruuden laskemista, gradientin suunta löydetään usein sivutuotteena. Jos tietty piste, jonka koordinaatit ovat (x,y), sattuu todellakin olemaan viivan päällä, gradientin paikallinen suunta antaa θ-parametrin, joka vastaa kyseistä viivaa, ja r-parametri saadaan välittömästi. (Shapiro ja Stockman, 305) Gradientin suunta voidaan arvioida 20°:n tarkkuudella, mikä lyhentää sinimuotoista jälkeä täydestä 180°:sta noin 45°:een. Tämä lyhentää laskenta-aikaa ja sillä on mielenkiintoinen vaikutus, että hyödyttömien äänten määrä vähenee, mikä parantaa kuvan todellisia viivoja vastaavien piikkien näkyvyyttä.

Kernel-pohjainen Hough-muunnos (KHT)Edit

Fernandes ja Oliveira ehdottivat Hough-muunnokselle paranneltua äänestysjärjestelmää, jonka avulla ohjelmistototeutus voi saavuttaa reaaliaikaisen suorituskyvyn jopa suhteellisen suurissa kuvissa (esim. 1280×960). Kernel-pohjainen Hough-muunnos käyttää samaa ( r , θ ) {\displaystyle (r,\theta )}

Dudan ja Hartin ehdottamaa parametrointia, mutta se toimii suunnilleen kollineaaristen pikseleiden klustereilla. Kullekin klusterille annetaan ääniä käyttämällä orientoitua elliptis-gaussilaista ydintä, joka mallintaa epävarmuutta, joka liittyy parhaiten sopivaan viivaan suhteessa vastaavaan klusteriin. Lähestymistapa ei ainoastaan paranna merkittävästi äänestysjärjestelmän suorituskykyä, vaan tuottaa myös paljon puhtaamman akkumulaattorin ja tekee muunnoksesta kestävämmän vääränlaisten viivojen havaitsemisen suhteen.

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

Limberger ja Oliveira ehdottivat determinististä tekniikkaa tasojen havaitsemiseen organisoimattomissa pistepilvissä, jonka kustannukset ovat n log ( n ) {\displaystyle n\log(n)}.

näytteiden määrässä, jolloin saavutetaan reaaliaikainen suorituskyky suhteellisen suurille aineistoille (jopa 10 5 {\displaystyle 10^{5}}).

pistettä 3,4 GHz:n suorittimella). Se perustuu nopeaan Hough-muunnoksen äänestysstrategiaan tasomaisille alueille, joka on saanut vaikutteita Kernel-pohjaisesta Hough-muunnoksesta (KHT). Tässä 3D Kernel-pohjaisessa Hough-muunnoksessa (3DKHT) käytetään nopeaa ja vankkaa algoritmia suunnilleen samansuuntaisten näytteiden klustereiden segmentoimiseksi ja äänestetään yksittäisiä klustereita (yksittäisten näytteiden sijaan) ( θ , ϕ , ρ {\displaystyle \theta ,\phi ,\rho }).

) sfäärinen akkumulaattori käyttäen kolmimuuttujaista Gaussin ydintä. Lähestymistapa on useita kertaluokkia nopeampi kuin nykyiset (ei-deterministiset) tekniikat tasojen havaitsemiseksi pistepilvissä, kuten RHT ja RANSAC, ja se skaalautuu paremmin tietokokonaisuuksien koon kasvaessa. Sitä voidaan käyttää missä tahansa sovelluksessa, jossa tarvitaan nopeaa tasopiirteiden havaitsemista suurissa tietokokonaisuuksissa.

Käyrien Hough-muunnos ja sen yleistäminen analyyttisille ja ei-analyyttisille muodoilleEdit

Vaikka edellä kuvattua muunnoksen versiota sovelletaan vain suorien viivojen löytämiseen, samanlaista muunnosta voidaan käyttää minkä tahansa sellaisen muodon löytämiseen, joka voidaan esittää parametrien avulla. Esimerkiksi ympyrä voidaan muuntaa kolmen parametrin joukoksi, jotka edustavat sen keskipistettä ja sädettä, jolloin Hough-avaruudesta tulee kolmiulotteinen. Myös mielivaltaiset ellipsit ja käyrät voidaan löytää tällä tavoin, samoin kuin mikä tahansa muoto, joka voidaan helposti ilmaista parametrisarjana.

Hough-muunnoksen yleistämistä analyyttisten muotojen havaitsemiseen tiloissa, joilla on mikä tahansa ulottuvuus, ehdottivat Fernandes ja Oliveira. Toisin kuin muut Hough-muunnokseen perustuvat lähestymistavat analyyttisten muotojen havaitsemiseen, Fernandesin tekniikka ei ole riippuvainen muodosta, joka halutaan havaita, eikä syöttötietojen tyypistä. Havaitseminen voidaan ohjata analyyttisen muodon tyyppiin muuttamalla oletettua geometriamallia, johon tiedot on koodattu (esim. euklidinen avaruus, projektiivinen avaruus, konforminen geometria ja niin edelleen), kun taas ehdotettu muotoilu pysyy muuttumattomana. Lisäksi se takaa, että halutut muodot esitetään mahdollisimman pienellä parametrimäärällä, ja se mahdollistaa sellaisten erityyppisten muotojen samanaikaisen havaitsemisen, jotka sopivat parhaiten syöttötietojoukkoon, jolla on eri dimensiot ja erilaiset geometriset määritelmät (esim. sellaisten tasojen ja pallojen samanaikainen havaitseminen, jotka sopivat parhaiten pistejoukkoon, suoriin viivoihin ja ympyröihin).

Tasossa oleville monimutkaisemmille muodoille (esim, muodot, joita ei voida esittää analyyttisesti jossakin 2D-avaruudessa), käytetään yleistettyä Hough-muunnosta, jonka avulla piirre voi äänestää muodon tiettyä sijaintia, orientaatiota ja/tai skaalausta käyttäen ennalta määriteltyä hakutaulukkoa.Hough-muunnos kerryttää kaikkien havaitun reunan pikseleiden kontribuutiot.

Ympyrän havaitsemisprosessiTiedostoa muokkaa

Algoritmin muuttaminen havaitsemaan ympyränmuotoisia muotoja viivojen sijaan on suhteellisen suoraviivaista.

• Aluksi luodaan akkumulaattoriavaruus, joka koostuu solusta jokaiselle pikselille. Aluksi jokainen solu asetetaan arvoon 0.
• Kunkin kuvan reunapisteen (i, j) kohdalla kasvatetaan kaikki solut, jotka ympyrän yhtälön ( i – a ) 2 + ( j – b ) 2 = r 2 {\displaystyle (i-a)^{2}+(j-b)^{2}=r^{2}}}
  

  voisi olla ympyrän keskipiste. Näitä soluja edustaa yhtälössä kirjain a {\displaystyle a}

  

  .

• Etsi jokaiselle edellisessä vaiheessa löydetylle mahdolliselle a:n arvolle {\displaystyle a}
  

  kaikki mahdolliset b:n arvot {\displaystyle b}

  

  , jotka tyydyttävät yhtälön.

• Etsitään paikallisia maksimeja akkumulaattoriavaruudesta. Nämä solut edustavat algoritmin havaitsemia ympyröitä.

Jos emme etukäteen tiedä etsittävän ympyrän sädettä, voimme käyttää kolmiulotteista akkumulaattoriavaruutta etsiessämme ympyröitä, joiden säde on mielivaltainen. Tämä on luonnollisesti laskennallisesti kalliimpaa.

Menetelmällä voidaan havaita myös ympyrät, jotka ovat osittain akumulaattoriavaruuden ulkopuolella, kunhan ympyrän pinta-alasta on vielä riittävästi sen sisällä.

3D-objektien havaitseminen (tasot ja sylinterit)Muokkaa

Hough-muunnosta voidaan käyttää myös 3D-objektien havaitsemiseen etäisyysdatasta tai kolmiulotteisista pistepilvistä. Klassisen Hough-muunnoksen laajentaminen tasojen havaitsemiseen on melko suoraviivaista. Taso esitetään sen eksplisiittisellä yhtälöllä z = a x x + a y y + d {\displaystyle z=a_{x}x+a_{y}y+d}}

, johon voimme käyttää 3D-Hough-avaruutta, joka vastaa a x {\displaystyle a_{x}}

, a y {\displaystyle a_{y}}

ja d {\displaystyle d}

. Tämä laajennus kärsii samoista ongelmista kuin sen 2D-vastine eli lähellä vaakatasoa olevat tasot voidaan havaita luotettavasti, kun taas suorituskyky heikkenee, kun tason suunta muuttuu pystysuoraksi (suuret arvot a x {\displaystyle a_{x}}

ja a y {\displaystyle a_{y}}

vahvistavat datan kohinaa). Tätä tason muotoilua on käytetty tasojen havaitsemiseen ilmalaserkeilauksesta saaduissa pistepilvissä, ja se toimii erittäin hyvin, koska kyseisellä alueella kaikki tasot ovat lähes vaakasuoria.

Hough-muunnosta käyttävää yleistettyä tason havaitsemista varten taso voidaan parametrisoida sen normaalivektorilla n {\displaystyle n}

(pallokoordinaatistoa käyttäen) ja sen etäisyys origosta ρ {\displaystyle \rho }

, jolloin saadaan kolmiulotteinen Hough-avaruus. Tämä johtaa siihen, että jokainen syöttötietojen piste äänestää sinimuotoista pintaa Hough-avaruudessa. Näiden sinimuotoisten pintojen leikkauspiste osoittaa tason olemassaolon. Yleisempi lähestymistapa yli kolmeen ulottuvuuteen edellyttää hakuheuristiikkaa, jotta se pysyisi toteuttamiskelpoisena.

Hough-muunnosta on käytetty myös sylinterimäisten kohteiden löytämiseen pistepilvistä kaksivaiheisella lähestymistavalla. Ensimmäisessä vaiheessa etsitään sylinterin orientaatio ja toisessa vaiheessa sijainti ja säde.

Painotettujen piirteiden käyttäminenMuutos

Yksi yleinen variaation yksityiskohta. Eli löytämällä yhdessä vaiheessa suurimman lukumäärän omaavat binit voidaan rajoittaa seuraavassa vaiheessa etsittävää arvoaluetta.

Huolellisesti valittu parametriavaruusMuokkaa

Hough-muunnoksen korkea-ulotteinen parametriavaruus ei ole ainoastaan hidas, vaan jos se toteutetaan ennakoimatta, se voi helposti ylittää käytettävissä olevan muistin. Vaikka ohjelmointiympäristö sallisi käytettävissä olevaa muistitilaa suuremman joukon varaamisen virtuaalimuistin avulla, siihen tarvittavien sivunvaihtojen määrä on hyvin vaativa, koska akkumulaattorijoukkoa käytetään satunnaisesti ja se pysähtyy harvoin yhtenäiseen muistiin hypätessään indeksistä toiseen.

Harkitaan tehtävää löytää ellipsejä 800×600-kokoisesta kuvasta. Jos oletetaan, että ellipsin säteet ovat pääakselien suuntaisia, parametriavaruus on neliulotteinen. (x,y) määrittelee ellipsin keskipisteen, ja a ja b kuvaavat kahta sädettä. Jos keskipisteen annetaan olla missä tahansa kuvassa, lisätään rajoitus 0<x<800 ja 0<y<600. Jos säteille annetaan samat arvot kuin rajoitteille, jäljelle jää yli 230 miljardin arvon harvaan täytetty akkumulaattoriryhmä.

Tällaiseksi suunniteltu ohjelma ei todennäköisesti saa varattua riittävästi muistia. Tämä ei tarkoita, että ongelmaa ei voisi ratkaista, vaan ainoastaan sitä, että on löydettävä uusia tapoja rajoittaa akkumulaattorimassan kokoa, mikä tekee siitä toteuttamiskelpoisen. Esimerkiksi:

1. Jos on järkevää olettaa, että ellipsit ovat kukin kokonaan kuvan sisällä, voidaan säteiden kantamaa pienentää. Suurimmat säteet voivat olla, jos ellipsin keskipiste on kuvan keskellä, jolloin ellipsin reunat voivat ulottua reunoille. Tässä ääritapauksessa säteet voivat kukin olla vain puolet samaan suuntaan suunnatun kuvan koon suuruudesta. Kun a:n ja b:n vaihteluväliä pienennetään tällä tavoin, kertymäjoukko pienenee 57 miljardiin arvoon.
2. Tarkkuuden vaihtaminen tilaan Hough-muunnoksen estimoinnissa kertyy kaikkien havaitun reunan pikseleiden osuudet. Hough-muunnos kerryttää osuudet kaikista havaitun reunan pikseleistä. he keskellä: Jos keskipisteen ennustetaan poikkeavan 3:lla sekä x- että y-akselilla, tämä pienentää akkumulaattoriryhmän kokoa noin 6 miljardiin arvoon.
3. Trade accuracy for space in the estimation of the radii: Jos säteiden arvioidaan poikkeavan kumpikin 5:llä, akkumulaattorimassan koko pienenee edelleen, noin 256 miljoonalla arvolla.
4. Kuvan rajaaminen kiinnostaville alueille. Tämä on kuvasta riippuvaista ja siksi arvaamatonta, mutta kuvittele tapaus, jossa kaikki kuvan kiinnostavat reunat ovat kuvan vasemmassa yläneljänneksessä. Tässä tapauksessa akkumulaattoriryhmää voidaan pienentää entisestään rajoittamalla kaikkia neljää parametria kertoimella 2, jolloin kokonaispienennyskerroin on 16.

Soveltamalla vain kolmea ensimmäistä näistä rajoituksista edellä mainittuun esimerkkiin, akkumulaattoriryhmän koko pienenee melkein 1000-kertaiseksi, jolloin se pienenee kokoon, joka mahtuu paljon todennäköisemmin nykyaikaisen tietokoneen muistiin.

Tehokas ellipsin havaitsemisalgoritmiEdit

Yonghong Xie ja Qiang Ji esittävät tehokkaan tavan toteuttaa Hough-muunnos ellipsin havaitsemiseen voittamalla muistiongelmat. Kuten algoritmissa (paperin sivulla 2) käsitellään, tämä lähestymistapa käyttää vain yksiulotteista akkumulaattoria (sivuakselille) havaitakseen ellipsit kuvassa. Monimutkaisuus on O(N3) kuvan nollasta poikkeavien pisteiden määrässä.