Epipolaarinen geometria

Etsiä vastaavia kuvapisteitä stereokuvista geometria on malli matematiikka on geometrian , joka kuvaa geometriset suhteet eri kuvia saman kohteen otettu eri näkökulmista. Sen avulla voidaan kuvata vastaavien pikselien väliset riippuvuudet - toisin sanoen ne, jotka muodostavat kussakin kuvassa havaitun kohteen yksi piste. Vaikka Guido Hauck loi perustan vuonna 1883 ja Horst von Sanden  (de) tutki sitä vuonna 1908 , epipolaarinen geometria otti vain jonkin verran merkitystä digitaalisten kuvien hyödyntämisellä , ennen kaikkea keinotekoisen näön alalla .

Etualalla epipolaarista geometriaa käytetään kolmiulotteisen tiedon palauttamiseen kuvista. Se toimii tässä tukena vastaavuuksien analysoinnille, nimittäin pikselien havaitsemiselle kirjeenvaihdossa, ja se mahdollistaa hakuaikojen huomattavan lyhentämisen.

Periaate

Kamera tai kamera, voidaan geometrisesti mallintaa jonka neulanreikäkamerassa . Siinä aikana ammunta , keskellä reikä, kunkin pisteen kohdeobjektin ja vastaavan kuvan kohtaa ovat kohdakkain . Jos objektikohta on nähty kahdella eri kameralla, voimme avaruusreikien sijainnista riippuen ja kuvien suhteen muodostaa uudelleen nämä kaksi viivaa ja niiden leikkauspisteen, joka on kohdepiste. laskekaa siis myöhemmin. Meillä on siis kolmiulotteinen kohdepisteen rekonstruktio, jonka pisteet voidaan tunnistaa kahden kuvan kirjeenvaihdossa. Epipolaarista geometriaa käytetään tämän rekonstruoinnin helpottamiseen: jos piste annetaan kuvalle, epipolaarisen geometrian tilanteen tuntemus rajoittaa toisen kuvan vastaavuuden pisteen etsimistä yhdelle riville.

Vasemmassa reunassa olevassa kaaviossa esitetään seuraavat geometriset olennot: objektipisteet ja kuvapisteet, kahden kameran projektiokeskukset O G ja O D sekä niiden kuvatasot, jotka on sijoitettu projektiokeskusten eteen symmetrisesti ( mikä ei muuta kohdistusta, mutta helpottaa esitystä). Kohdepistettä X projisoidaan vasemman kuvan X- G . Tästä kuvapisteestä kohdepiste löytyy vain suoraviivaisesta säteestä O G X G  : kohdassa X 3 , X 2 , X 1 tai X , joilla kaikilla on sama kuva X G vasemmalla. Kaikki nämä seikat ovat ennustetaan aivan samalla rivillä ( "suora etsiä vastaavia kuvapisteitä stereokuvista" punaisella), johon voidaan rajoittaa varmistukseen kohtaan X D vastaten X G .

Epipolaarinen geometria antaa mahdollisuuden löytää yksinkertainen suhde kirjeenvaihdon pisteiden välillä tietämättä kameroiden sijaintia. Tietysti tietylle epipolaariselle geometrialle löytyy tietoa kameroiden suhteellisista sijainneista, mutta kameran sijaintia ei tarvitse tietää nimenomaisesti tätä varten. Epipolaarinen geometria riippuu vain kameroiden parametreista ja on riippumaton kuvatun kohtauksen rakenteesta.

Epipolaarisen geometrian ja sen elementtien kuvaamiseen käytetään tiettyä terminologiaa . Tasoa, joka sisältää kaksi projektiokeskusta ja kohdepisteen, kutsutaan epipolaariseksi tasoksi (kaaviossa vihreänä). Tämä leikkaa molemmat kuvat viivaa pitkin, epipolaarista viivaa . Annettua kuvan kohtaa vastaava kohta on toisen kuvan epipolaarisella viivalla. Kahden heijastuskeskuksen yhdistävä viiva leikkaa jokaisen kuvatason pisteessä, epipolissa . Epipolit pysyvät kiinteinä niin kauan kuin kameroiden suhteellinen sijainti pysyy kiinteänä. Kuvan epipoli on samalla toisen kameran projisointikeskuksen kuva. Kaikki kuvan epipolaariset viivat kulkevat epipolin läpi, mikä voi lisäksi olla kameran suhteellisen sijainnin mukaan kuvan kentän ulkopuolella.

Sovellukset

Etsiä vastaavia kuvapisteitä stereokuvista geometriaa käytetään pääasiassa projektiivinen geometria , fotogrammetrian ja keinotekoinen visio . Sen päätavoitteena on vastaavuusanalyysi: jos halutaan saada kuvan merkittävä piste, toisen kuvan vastaavuuspiste, on tutkittava koko toinen kuva, ellei epipolaarisesta geometriasta ole tietoa. . Jos tiedetään epipolaarinen geometria, riittää etsiä sitä epipolaarisesta viivasta. Tämä johtaa tutkimustilan merkittävään vähenemiseen. Tätä varten käytämme epipolaarista geometriaa ennen kaikkea, kun on tarpeen analysoida kohtaus tai esine kameroilla kolmella ulottuvuudella. Tärkeitä aloja ovat osien mittaus laadunvalvontaa varten, rakennusten kartoittaminen arkkitehtonisen fotogrammetrian avulla, ilmavalokuvametria maantieteellisten karttojen luomiseksi tai jopa visio avaruudessa itsenäisille automaateille.

Keinotekoinen visio

Epipolaarinen geometria rajoittaa esineiden tunnistamisen epipolaarisiin viivoihin vastaavien pisteiden etsintäkenttää ja mahdollistaa siten laskennallisen ajan valtavan säästämisen. Samalla se vähentää väärien vastaavuuksien määrää johtuen hakuverkkotunnuksen vähenemisestä. Molemmat ovat erittäin kiinnostuneita konenäköstä. Erityisesti autonomisten robottien alalla on tarpeen yksinkertaistaa laskutoimituksia korkean suorituskyvyn saavuttamiseksi, toisaalta piirien tilavuuden rajoitusten vuoksi, ja toisaalta nopean toiminnan saavuttamiseksi välttää törmäyksiä. Esimerkiksi yksi autonomisten ajoneuvojen välisen kilpailun DARPA Grand Challengen osallistujista käytti OpenCV- ohjelmakirjastoa , joka sisältää rutiinit epipolaarisen geometrian nopeaan laskemiseen ja kirjeenvaihtoanalyysiin.

Kohtauksen reliefikuvaus (3D) valokuville voidaan tehdä, jos kalibrointi ja kameroiden sijainti ovat tiedossa. Koska epipolaarinen geometria kuvaa kahden kuvan välistä projektiivista suhdetta, se altistetaan autokalibroinnille, toisin sanoen kameroiden parametrien automaattiselle laskemiselle. Tässä tapauksessa epipolaarista geometriaa ei käytetä osumien löytämiseen, mutta se tekee päinvastoin: tunnetuista vastaavuuksista se rekonstruoi suuren osan kalibroinnista ja kameroiden sijainnista.

Historia

Historia etsiä vastaavia kuvapisteitä stereokuvista geometria liittyy läheisesti että fotogrammetriaa . Ensimmäinen analysoi geometriset suhteet sen pohjalla oli matemaatikko Guido Hauck. Vuonna 1883 hän julkaisi artikkelin Journal für die reine und angewandte Mathematik -lehdessä , jossa "keskipisteen" käsitettä käytettiin ensimmäistä kertaa. Huolimatta anakronismeista ja yhtenäisen terminologian säilyttämiseksi käytämme epipolaarisen geometrian nimikkeistöä, jossa keskipiste on selvästi epipoli.

"Olkoon (kuva 1a) S ' ja S' kaksi projektiotasoa, O 1 ja O 2 vastaavat projektiokeskukset. Ristin viiva g 12 on peruskappale . Suora O 1 O 2 leikkaa o ' 1: n ja o ' 2: n projektiotasoja , joita kutsumme kahden tason epipoleiksi. "

Horst von Sanden piti laajemman esityksen vuonna 1908 osana opinnäytetään ”Epipolien määritys fotogrammetriassa. Hän kuvaa menetelmiä epipolien määrittämiseksi yksinkertaisemmalla ja tarkemmalla tavalla.

Ennen digitaalisen tekniikan käyttöönottoa analyysiksi kutsutulle vallitsevalle fotogrammetrialle, joka perustuu valokuvaan ja sen mekaaniseen-optiseen käyttöön, vastaavuusanalyysi tehtiin manuaalisesti. Koska ihmisen toimija voi helposti suorittaa vastaavuuden riittävän jäsennetyn kohtauksen kohtausten välillä, nämä löydöt jäivät ilman monia sovelluksia. Se oli vasta 1980-luvulta tullut digitaalinen fotogrammetria, digitaalivalokuvat ja tietokoneiden offline-hyödyntäminen, samoin kuin kasvava tarve kuvien automaattiselle hyödyntämiselle näkökentässä. Keinotekoinen, joka elvytti entistä voimakkaammin epipolaarisen geometrian tutkimuksen ja sen sovellukset. Ensimmäinen työ, joka todistaa tämän teeman löytämisen uudelleen, oli Hugh Christopher Longuet-Higginsin julkaisu Nature- lehdessä . Siitä lähtien monet tutkijat ovat olleet kiinnostuneita epipolaarisesta geometriasta, mukaan lukien Huang ja Olivier Faugeras , Horn tai Vieville ja Lingrand.

Matemaattinen kuvaus

Epipolaarinen geometria muodostaa suhteen kuvatasojen vastaavien pisteiden koordinaattien välillä. Nämä koordinaatit ovat usein ortonormaalisia suorakulmaisia ​​koordinaatteja , mutta ne voivat olla mitä tahansa affinikoordinaatteja . Kuvan koordinaattijärjestelmän alkuperä on usein kuvan keskellä tai kulmassa. Esimerkiksi digitaalikuville (CCD tai skannatut kuvat) pikselirivi ja sarake voidaan pitää koordinaateina. Kun rivi- ja sarakemääritykset ovat erilaiset tai akselit eivät ole kohtisuorassa, meillä on affiniinikoordinaatit.

Vastaavien pisteiden kuvakoordinaattien väliset suhteet kuvataan perusmatriisilla . Sen avulla voidaan määrittää ensimmäisen kuvan jokaiselle pisteelle vastaava epipolaarinen viiva toisella linjalla, jolla vastaava piste sijaitsee.

Homogeeniset koordinaatit ja projektiomatriisi

Kohdepisteiden soveltaminen kuvatasoon voidaan kuvata projektiivigeometriassa käytetyillä homogeenisilla koordinaateilla . Homogeeniset koordinaatit ovat suorakulmaisia ​​tai affiinisia koordinaatteja, korotettuna yhdellä koordinaatilla, mutta ne on määritelty vain asteikkokertoimeksi. Niiden avulla on mahdollista esittää johdonmukaisella tavalla näkökulman amatöörien pisteet äärettömyyteen tai katoavat pisteet .

Homogeenisissa koordinaateissa kolmiulotteisen avaruuden kohdepisteen soveltaminen kuvatason kaksiulotteiseen tasoon voidaan kuvata lineaarisella kartalla:

Tason pisteen homogeeniset koordinaatit muodostavat 3 × 1 -taulukon, joka voidaan käsitellä matriisilaskennan sääntöjen avulla. Nimeämme pisteet matriiseina.

Saamme suorakulmaiset koordinaatit x  =  u / w ja y  =  v / w . 3 x 4 P projektio matriisi kuvaa näkökulmasta projektio kohteen pistettä kuvatasoon. Se sisältää kameran suunnan ja sijaintitiedot. Kuten tässä projektiossa, ulottuvuus menetetään (etäisyys esineestä kameraan), se ei ole yksiselitteisesti käännettävä.

Kirjeenvaihdon pisteiden suhde

Laskennassa perus- matriisi perustuu ajatukseen valitsemalla piste x 1 ensimmäistä kuvaa, sitten määritetään kohdepisteeseen X ulkoneva tämän kuvan kohdassa, ja lopuksi laskemalla kuvan x 2 ja X on toinen kuva. Tämä piste x 2 ja toisen kuvan epipoli e 2 ovat epipolaarisella viivalla ja määrittävät sen sen vuoksi ainutlaatuisella tavalla.

Annetaan piste x 1 ensimmäistä kuvaa, säde, johon vastaava kohde piste sijaitsee määritellään projektio matriisin P 1 . Pistettä itse ei voida määrittää, koska sen etäisyyttä kameraan ei tunneta. Säteen piste voidaan laskea pseudo-käänteisen P 1 +  : n avulla:

X = P 1 + x 1

Tätä pistettä voidaan soveltaa toisen kameran projisointimatriisilla P 2 toisella kuvalla:

X 2  =  P 2 P 1 +  x 1

Tämä tekee mahdolliseksi tietää pisteeseen X 2 on etsiä vastaavia kuvapisteitä stereokuvista linjan toisen kuvan vastaten x 1 . Toinen kohta on epipole e 2 , kuva ulokkeen keskelle O 1 kameran 1:

e 2  =  P 2   O 1

Homogeenisissa koordinaateissa pisteiden ( u, v, w ) yhtälö, joka kulkee kahden annetun koordinaattipisteen ( u 1 ,  v 1 ,  w 1 ) ja ( u 2 ,  v 2 ,  w 2 ) läpi, koostuu siitä, että tekijä on 3 x 3 Koordinaattitaulukkoon katoaa.

Epipolaarista viivaa kuvataan homogeenisissa koordinaateissa yhtälöllä:

Det ( P 2 P 1 +  x 1 ,  P 2   O 1 ,  x 2 ) = 0

Determinantin kehittäminen sekoitetun tuotteen muodossa:

( P 2 P 1 +  x 1  ×  P 2  O 1 ) T  x 2  = 0

Kerroin x 2  on l 2 T , ja:

l 2  = ( P 2 P 1 +  x 1  ×  P 2  O 1 )

Koska l 2  on homogeeninen lineaarinen funktio x 1 , on olemassa matriisi F siten, että l 2  = F  x 1 , ja jota kutsumme perus- matriisi . Kirjeenvaihtopisteiden välinen suhde voidaan kirjoittaa:

l 2 T x 2  =  x 2 T l 2  =  x 2 T F x 1  = 0

tai:

Tätä yhtälöä kutsutaan epipolaariseksi yhtälöksi . Se voidaan tulkita hyvin kuvan 1 viivan yhtälöksi, annettu piste kuvassa 2, tai päinvastoin.

Perusmatriisin erityistapaus on olennainen matriisi . Tämä ilmestyy, kun käytetään ortonormaalia kuvan koordinaatteja , joiden alkuperä on projisointikeskipisteen kohtisuora projektio kuvatasossa. Koska tämä ehto ei ole välttämätön perusmatriisille, jälkimmäisen määritelmä on yleisempi kuin oleellisen matriisin määritelmä.

Perusmatriisin ominaisuudet

Perustavanlaatuinen matriisi F (kutsutaan myös ”kaksiteholinssejä tensor”) sisältää kaikki tarvittavat tiedot on etsiä vastaavia kuvapisteitä stereokuvista geometria. Se voidaan myös määrittää ilman tietoa heijastusmatriiseista P 1 ja P 2 eikä projektiokeskuksista O 1 ja O 2 vastaavien pisteiden kuvakoordinaateista.

Voimme määrittää perustasoisen 3 × 3 -matriisin vain kerrottavalla tekijällä, koska perusmatriisin tulo millä tahansa muulla luvulla kuin 0 ei muuta epipolaarisen yhtälön pätevyyttä x 1 T  F  x 2  = 0 . Joten vain 8 matriisin elementtiä ovat riippumattomia. Koska 3 x 3 antisymmetrinen matriisi: x  P 2  O 1 , kuten mikä tahansa antisymmetrinen n x n matriisi on singulaarinen varten pariton n , F on yksikkö, ja sen determinantti on siis nolla. Tämä lisäedellytys pienentää perusmatriisin vapausasteiden lukumäärää 7: een.

Perusmatriisia käyttämällä voimme laskea mihin tahansa pisteeseen x 1 vastaavan epipolaarisen viivan l 2 toisessa kuvassa:

l 2  =  F  x 1,

ja ilmeisesti päinvastoin toisen kuvan pisteessä x 2 , epipolaarinen viiva l 1  :

l 1  =  F T  x 2 .

Yhden kuvan epipolaarisesta viivasta emme voi laskea toisen kuvan vastaavaa pistettä. Tätä varten olisi välttämätöntä pystyä kääntämään perusmatriisi, mikä on mahdotonta, koska se on yksikkö. Kuten epipole e 2 on kaikista etsiä vastaavia kuvapisteitä stereokuvista linjat l 2 , on tarpeen, että

l 2 T e 2  = ( F  x 1 ) T  e 2  =  x 1 T F T  e 2  = 0

kaikille x 1 , niin että epipoli e 2 ja samalla tavalla e 1 täyttävät yhtälöt:

F T  e 2  = 0 ja F  e 1  = 0

Näistä yhtälöistä näemme, että perusmatriisin determinantin on oltava nolla, muuten yhtälöillä olisi vain ratkaisut e 1  =  e 2  = 0 , mikä on kielletty homogeenisissa koordinaateissa.

Perusmatriisin laskeminen voidaan suorittaa olettaen, että kamerat on kalibroitu , kahdesta projektiomatriisista ja projektiokeskuksesta ( katso yllä ). Mutta koska perusmatriisin laskemisen on yleensä puututtava ennen projektiomatriisien laskemista, tämä tapaus on suhteellisen harvinainen. Seuraavassa näytetään, kuinka F voidaan laskea vain kirjeenvaihdon pisteiden perusteella.

Laskeaksesi vastaavien pisteiden joukon perusmatriisin, kehitä epipolaarinen yhtälö x 2 T  F  x 1  = 0  :

x 2  x 1  f 11  +  x 2  y 1  f 12  +  x 2  f 13  +  y 2  x 1  f 21  +  y 2  y 1  f 22  +  y  2  f 23  +  x 1  f 31  +  y 1  f 32  +  f 33  = 0

tai vektori:

( x 2  x 1 ,   x 2  y 1 ,   x 2 ,   y 2  x 1 ,   y 2  y 1 ,   y 2 ,   x 1 ,  y 1 , 1) ∙  f  = 0 ,

kanssa:

f  = ( f 11   f 12   f 13   f 21   f 22   f 23   f 31   f 32   f 33 ) T

Alkaen n pistettä, asetamme järjestelmän homogeeninen lineaarinen yhtälöryhmä (ylempi indeksi tarkoittaa tarkasteltavan kohdan):

Koska vastaavien pisteiden koordinaatit tyydyttävät epipolaarisen yhtälön, A: n sarakkeet ovat lineaarisesti riippuvaisia . Matriisilla A on siten korkeintaan sijoitus 8. Yli kahdeksan rivin kohdalla tämä pätee, jos koordinaateissa ei ole mittausvirhettä eikä yksikään pistepari vastaa väärin. Jos ei ole listalla yhtä suuri kuin sen määrä sarakkeita, se jää f   (lukuun ottamatta triviaali tapaus f  = 0 ) joukko ratkaisuja, jotka muodostavat ytimen ja .

Yleensä pieniä mittausvirheitä esiintyy määritettäessä otteluja, koska kuvapisteitä voidaan luonnehtia vain äärellisellä tarkkuudella. Vektorilla f ilmaistulla perusmatriisilla F ei siis ole sijaa 2 eikä se ole yksikkö. Tämä johtaa siihen, että kuvan epipolaariset viivat eivät leikkaa kaikkia samassa pisteessä.

Käytännössä perusmatriisin laskemiseen käytetään kahta menetelmää, jotka johtavat singulariteettitilaan: 7-pisteen algoritmi ja 8-pisteen algoritmi. Molemmissa menetelmissä kuvapisteiden mitattuja koordinaatteja ei yleensä käytetä suoraan, vaan aiemmin normalisoidut koordinaatit: koordinaattien alkuperä siirretään kohti kuvapisteiden painopistettä ja koordinaatit normalisoidaan siten, että ne ovat suuruusluokassa 1. Tämän normalisoinnin avulla saavutetaan merkittävä parannus tuloksissa.

7 pisteen algoritmi

Tämä menetelmä käyttää seitsemän pistevastaavuutta matriisin F laskemiseen . Koska F määritetään tekijänä, 7 pistettä samoin kuin ehto Det (F)  = 0 ovat riittäviä elementtien 9 F määrittämiseksi . Seitsemän pisteiden vastaavuutta varten yhtälöjärjestelmä A F  = 0 sisältää vain 7 yhtälöä. Se on näin ollen kaksi lineaarisesti riippumattomia ratkaisuja f 1 ja f 2 ytimen . Perustavanlaatuinen matriisi F on rakennettu lineaarisena yhdistelmänä matriisien F 1 ja F- 2 rakennettu f 1 ja f 2  :

F  =  α   F 1  + (1 -  α )  F 2, jossatodellinen α .

Valitaksemme joukosta ratkaisuja, joilla on sijoitus 2, käytämme tosiasiaa, että Det (F)  = 0  :

Det (a F 1  + (1- a ) F 2 )  = 0 .

Tämä kuutiometriä yhtälö on α on ainakin yksi oikea ratkaisu, ja korkeintaan kolme, jos kerroin α 3 , joka on Det (F 1  -  F 2 )  on ei-nolla. Muussa tapauksessa rajalliselle α: lle ei voi olla ratkaisua . Kuitenkin, koska F 1  -  F 2  on determinantti, tämä on hyvä ratkaisu ongelmaan.

Voimme laskea perusmatriisin jokaisella kolmella. Jos ratkaisuja on useampi kuin yksi, otetaan huomioon muut pisteet sen selvittämiseksi, mikä on oikea ratkaisu. Valitaan se, joka täyttää epipolaarisen yhtälön näille lisäpisteille, lukuun ottamatta mittausvirheitä.

8 pisteen algoritmi

Yleensä otteluja on yli 7 pistettä. Alla kuvattu algoritmi vaatii vähintään 8 hakua, joten sen nimi, mutta voi käyttää enemmän. Tämän algoritmin idea johtuu Longuet-Higginsistä.

Ensimmäisessä vaiheessa tarkastellaan vain järjestelmää A f  = 0 huolimatta ehdosta Det (F)  = 0 . Ihannetapauksessa matriisilla A on aste 8; käytännössä, koska pisteitä on enemmän kuin 8, näin ei ole, joten ratkaisu f pienennetään arvoon 0. Sen sijaan määritämme ratkaisun pienimmän neliösumman menetelmällä tai etsimällä oikeita arvoja .

Pienimmän neliösumman menetelmällä määritetään f niin, että || A f  || on minimaalinen. Koska f on määritelty vain tekijään asti, on tarpeen ottaa käyttöön normalisointiehto, esimerkiksi, että jokin f: n elementti on yhtä suuri kuin yhtenäisyys. Ongelma tässä on elementin valinta: sen ei pitäisi olla suuruusluokaltaan paljon pienempi kuin muut, mitä emme tiedä etukäteen . Voit kokeilla erilaisia ​​mahdollisuuksia.

Toinen menetelmä on nimenomaan minimointi || A f  || , samalla kun ehto täyttyy f  || = 1 . Tämä johtaa siihen tulokseen, että ratkaisu f on ominaisvektori matriisin T  pienin ominaisarvo.

Mutta näin saatu ratkaisu f ei yleensä johda yksikkömatriisiin F. Tämän ehdon on täytyttävä toisessa vaiheessa. Tätä varten matriisi F diagonalisoidaan muodossa:

F = U S V

missä S on lävistäjämatriisi, jonka lävistäjät ovat F: n ominaisarvoja . Tuodaan 0 pienin ominaisarvot, ja laskee F matriiseista U , S ja valmistettu ainutlaatuinen, ja V . Siksi tuote on itsessään ainutlaatuinen.

8-pisteinen algoritmi on yksinkertainen prosessi perusmatriisin määrittämiseksi, mutta se on epävakaa mittausvirheiden suhteen. Tämä johtuu siitä, että perusmatriisin singulariteettiehto otetaan käyttöön jälkikäteen ja että minimoitu määrä || A f  || ei ole fyysistä merkitystä. On muitakin prosesseja, joilla ei ole mitään näistä haitoista. Nämä menetelmät ovat kuitenkin raskaampia ja niitä käytetään harvoin käytännössä.

Automaattinen laskenta

Keinonäkymässä on välttämätöntä, että epipolaarinen geometria lasketaan automaattisesti, koska esimerkiksi robottien on kyettävä toimimaan ilman ihmisen väliintuloa. Joten ensimmäinen askel on saada joukko vastaavia pisteitä. Tämä saavutetaan ohjelmistotyökalulla kirjeenvaihdon pisteiden löytämiseksi, joiden avulla kuvan merkittävimmät kohdat voidaan sijoittaa. Kun ne löydetään, heidät sovitetaan heidän samankaltaisuuteensa: kirjeenvaihtoanalyysi antaa mitan heidän samankaltaisuudelleen. Täten kirjeenvaihdossa saatu pistejoukko sisältää kuvakohinan ja molempien kameroiden saamien erilaisten perspektiivien vuoksi suuren määrän vääriä vastaavuuksia, eikä sitä siksi voida käyttää suoraan perusmatriisin laskemiseen.

Seuraavissa esityksissä näytämme joitain merkittäviä kohtia sekä kirjeenvaihdon analyysin tuloksia. In kuva 8 , on selvästi tunnustettu, että kaikkia otteluita ei ole määritetty asianmukaisesti. Kun kameraa on siirretty suunnilleen vaakatasossa kuvion 2 kahden näkymän välillä 6 ja kuva. Kuvion 7 mukaisesti vihreiden viivojen, jotka edustavat vastaavien pisteiden välisiä aukkoja, tulisi olla karkeasti vaakasuoria. Puun alueella tämä on kaukana tapauksesta, koska kaikilla lehdillä on samanlainen muoto ja valonvoimakkuus , mikä johtaa vastaavuusanalyysin vääriin tuloksiin.

Väärät vastaavuudet on poistettava ennen laskemista erottamis- ja poisto-ohjeilla. Tätä varten käytetään laajasti ns. RANSAC- algoritmia . Tämä algoritmi pystyy havaitsemaan pisteparien yhteensopivuusvirheet. F: n laskemiseksi se käsittää seuraavat vaiheet:

  1. Valitse tiedoista satunnaisesti 7 osumaa. On kohtuullisen todennäköistä, että nämä 7 ottelua ovat oikein.
  2. Laske F käyttämällä 7 pisteen algoritmin valitsemia 7 vastaavuutta.
  3. Etsi kaikki kirjeenvaihdon pisteet, joille x 2 T  F x 1  ≤  ε, ja kirjoita ne muistiin. Mitä enemmän pisteitä, jotka tyydyttävät tämän yhtälön, on todennäköisempää, että alun perin valitut pisteet ovat ilman kirjeenvaihtovirhettä. Kynnysarvo e on välttämätön, koska mittaus- ja laskuvirheiden vuoksi suhde x 2 T F x 1  = 0 ei käytännössä koskaan täyty.
  4. Toista vaiheet 1–3, kunnes on todennäköistä, että 7 ensimmäisessä pisteessä ei ole virheitä.

Perusmatriisi F lasketaan sitten 8-pisteisen algoritmin avulla vaiheessa 2 havaitun suurimman joukon perusteella.

Sitten voidaan tehdä uudelleen kirjeenvaihtotutkimus, ottaen huomioon laskettu perusmatriisi (kuten aiemmin selitettiin, pisteiden vastaavuuksien hakualue kaventuu epipolaariseen viivaan), ja vastaavuuksien hyväksymiseen käytetään tiukempaa arvoa . Nämä kaksi viimeistä vaihetta voidaan toistaa toistuvasti, kunnes otteluiden määrä vakiintuu.

Kaksi viimeistä kuvaa havainnollistavat prosessin vaiheita: RANSAC-suodatus on enemmän tai vähemmän riittävää. Sen avulla voidaan nähdä, että oikean näkymän epipoli on käytännöllisesti katsoen äärettömässä, horisonttiviivan alapuolella vasemmalla. Etsiä vastaavia kuvapisteitä stereokuvista linjat laskettu päässä lopullinen F osoittavat, että epipole vasemman näkymä on oikealla, on rajallinen etäisyyden, suunnilleen näköpiirissä. Tämä kuvaa sitä tosiasiaa, että näiden kahden epipolin välillä ei yleensä ole a priori -suhdetta. Emme ole täällä normaalissa stereotapauksessa , koska kameraa ei ole vain siirretty, vaan sitä on myös hieman käännetty: vasemman näkymän taso ei ole yhdensuuntainen liikkeen suunnan kanssa. Tämä toiminto lisää vastaavien pisteiden välistä etäisyyttä.

Erikoistapaukset

Kameran tietyissä asennoissa toistensa suhteen voidaan saavuttaa tiettyjä tapauksia. Näiden joukossa kaksi kokoonpanoa kiinnostaa jonkin verran konenäköä.

  1. Kun kahden kameran kuvatasot ovat yhdensuuntaiset projisointikeskuksia yhdistävän viivan kanssa, epipolaariset viivat ovat kaikki yhdensuuntaisia ​​tämän linjan kanssa, epipolit menevät äärettömään. Tämä kokoonpano - nimeltään "normaali stereotapaus" - esiintyy usein ainakin suunnilleen stereoskooppisessa näyssä, ja vastaavuuksien etsinnän etuna on, että epipolaarinen geometria pienenee siihen tosiseikkaan, että epipolaariset viivat ovat useimmiten vaakasuoria. Täsmähaku etsitään sitten vain vaakasuorista viivoista. Saat digitaalikamerat , on tarpeen etsiä otteluiden pikselijuovajoukon joissa sama numero.
  2. Jos nämä kaksi kameraa ovat toistensa edessä, ts. Ne ovat siirtyneet näköyhteyttä pitkin, epipolit sijoitetaan kuvan keskelle ja epipolaariset viivat säteilevät ulos kuvan keskiosasta alkaen. Tämä kokoonpano esiintyy yleisesti mobiiliroboteissa, jotka käsittävät yhden kameran, joka on suunnattu liikkeen etuosaan, ja jotka vertaavat eri aikoina otettuja kuvia. Pisteiden vastaavuuksia etsitään peräkkäisten kuvien välillä.

Näissä erityistapauksissa vastaavuuksien etsiminen yksinkertaistuu, koska epipolaarinen geometria tunnetaan etukäteen. Konfiguraatioissa, jotka lähestyvät sitä, siitä voi saada inspiraation myöhempien korjausten avulla.

Yleistäminen useammalle kuin kahdelle kuvalle

Trifokaalinen geometria on yleistys etsiä vastaavia kuvapisteitä stereokuvista geometrian tapauksessa kolme kuvaa. Jos tiedämme pisteen sijainnin kahdessa kuvassa, kaksi epipolaarista viivaa tunnetaan leikkaamalla kuvataso epipolaaristen tasojen kanssa, ja niiden leikkaus antaa pisteen sijainnin kolmannessa kuvassa. Siten, toisin kuin kahden kuvan tapauksessa, yksi saa yksiselitteisen tuloksen, sikäli kuin kohdepiste ei ole trifokaalisella tasolla (kolmen projisointikeskuksen taso), jolloin kaikki tasot yhdistetään tai muuten on trifokaalitaso, toisin sanoen projektiokeskukset eivät ole kohdakkain. Konfiguraatio, jossa kohdepiste on trifokaalisella tasolla, on myös nimetty erityistapaukseksi .

Voimme yleistää tällaiset näkökohdat yli kolmeen kuvaan. Käytännössä tämä kiinnostaa vain neljää näkemystä, joissa voidaan välttää objektipisteen aiheuttamat haitat trifokaalisella tasolla, koska se on tällä hetkellä muiden trifokaalisten tasojen ulkopuolella. Voimme määritellä kvadrifokaalisen tensorin , joka kuvaa näiden kuvien välisiä suhteita kuvapisteiden ja polttoväleiden välillä. Mutta yli neljän näkymän osalta emme ole tutkineet matemaattisia suhteita, koska mallinnuksesta ja laskemisesta tulee huomattavasti monimutkaisempia, ja useimmissa sovelluksissa viidennen kameran tarjoama lisätieto on hyvin vähäistä.

Reiänreiän mallipoikkeamat

Aikaisemmin kuvattujen vastaavien kuvapisteiden välinen suhde, jonka perusmatriisi muodostaa täysin, pätee vain valokuviin, jotka voidaan mallintaa reiällä. Mutta jos kuvatason projektiossa esiintyy geometrisia poikkeamia ( vääristymiä ) tai jos kuvan pinta ei ole tasainen, nämä poikkeamat epipolaarisesta geometriasta on otettava huomioon. Erityisesti epipolaariset viivat, joilta on tarpeen etsiä pisteitä vastaamaan kuvan pistettä, eivät enää ole viivoja.

Vääristymät

Vain korkealaatuisilla linsseillä vääristymät voidaan jättää huomiotta. Huonolaatuisempien tavoitteiden saavuttamiseksi on välttämätöntä ottaa huomioon vääristymät rekonstruoinnin hyvän tarkkuuden saavuttamiseksi. Vääristymä voidaan usein mallintaa radiaaliseksi vääristymäksi, toisin sanoen pisteeksi, joka olisi polaarikoordinaateille kuvan keskipisteen (r, θ) suhteen ilman vääristymää a, koska vääristymät, napakoordinaatit (rf (r), θ) , missä f (r) = 1 ja r pieni, mutta vähitellen poikkeaa sen muutaman prosentin reunoja kohti kuvan erittäin mielivaltainen tavoitteet.

Jos kamera on kalibroitu huolellisesti ja vääristymä tunnetaan, kuvia voidaan korjata. Sitten voimme työskennellä korjattujen kuvien kanssa kuten kuvissa ilman vääristymiä.

Tietyissä olosuhteissa vääristymä voidaan ottaa huomioon yleistetyllä perusmatriisilla. Oletetaan jokaiselle kuvalle vääristymä, jolle on tunnusomaista tuntematon parametri, ja joka vastaa kuvatason korvaamista asteikolla olevalla pinnalla kolmiulotteisessa projektiivisessa tilassa (4 homogeenisella koordinaatilla). Kahden vastaavuuspisteen välinen suhde ilmaistaan ​​sitten 4 × 4 -matriisilla, jolla on 9 vapausastetta.

Laajakulmaiset kamerat

For laajakulmainen kamerat , joiden avulla laaja kenttä laukausta , emme voi enää mallintaa ammunta geometrian pinhole jossa on tasainen kuva. Epipolaarisen geometrian kuvaus riippuu kameran tyypistä. Esimerkiksi kameran, joka koostuu neulareikiä, jossa on hyperbolinen peili , etsiä vastaavia kuvapisteitä stereokuvista linjat ovat kartioleikkauksille .

Bibliografia

Viitteet

  1. (lähettäjä) Guido Hauck , "  Neue Constructionen der Perspective und Photogrammetrie  " , Journal für reine und angewandte Mathematik , voi.  95,1883, s.  1–35
  2. (de) Horst von Sanden , Die Bestimmung der Kernpunkte in der Photogrammetrie: Opinnäytetyö Göttingenin yliopistossa , Göttingen,1908
  3. (en) HC Longuet-Higgins , "  Tietokonealgoritmi kohtauksen rekonstruoimiseksi kahdesta projektiosta  " , Nature , voi.  293,yhdeksäntoista kahdeksankymmentäyksi, s.  133-135
  4. (sisään) TS Huang ja OD Faugeras , "  S-matriisin joitain ominaisuuksia kahden näkymän liikearvioinnissa  " , IEEE-transaktiot kuvioanalyysissä ja koneen älykkyydessä , voi.  11,1989, s.  1310–1312
  5. (in) BKP Horn , "  keskinäinen orientaatio  " , International Journal of Computer Vision , Vol.  4,1990, s.  59-78
  6. (in) T. Viéville ja D. Lingrand , käyttäminen yksikössä siirtymät sRGB päällekkäin konenäköjärjestelmät: Technical Report 2678 , INRIA ,1995
  7. (sisään) Zhengyou Zhang, "  Epipolaarisen geometrian ja sen epävarmuuden määrittäminen: katsaus  " ,1996(käytetty 4. helmikuuta 2011 ) Revue (1996).
  8. (vuonna) Joao P. Barreto ja Kostas Daniilidis , "  Perusmatriisi radiaalisesti vääristyneille kameroille  " , kymmenennen IEEE: n kansainvälisen tietokonenäkökonferenssin (ICCV'05) toimet ,2005, s.  625-632 ( lue verkossa [ arkisto29. kesäkuuta 2010] [PDF] )

Huomautuksia

  1. Epipoli voi olla äärettömässä, jolloin epipolaariset viivat ovat yhdensuuntaiset. Tästä syystä on kiinnostus työskennellä homogeenisten koordinaattien kanssa, kun äärettömän pisteet eivät vaadi erityiskäsittelyä muihin verrattuna.
  2. alalla fotogrammetrian termit pyhitetty aiemmin, ja vielä osittain käytetään nykyään, oli hieman erilainen; katso ( Kraus ja Waldhäusl 1997 ).
  3. Kaksiulotteiset koordinaatit ( x, y ) vastaavat homogeenisia koordinaatteja ( u, v, w ) = ( wx, wy, w ) . Homogeeniset koordinaatit ( u, v, w ) ja ( u / w, v / w , 1) = ( x, y , 1) edustavat samaa pistettä, kun w  ≠ 0 . Tapaukset w  = 0 edustavat pisteitä äärettömissä , joilla ei ole suorakulmaisia ​​koordinaatteja. Koska homogeeniset koordinaatit on määritelty kerrannaiskertoimeen saakka, niiden nollaaminen on kielletty. Kolmiulotteisen avaruuden yleistäminen on ilmeistä. On mahdollista ja toisinaan kätevää edustaa näitä numerosarjoja matriiseilla, siirrettyjen ulottuvuuksien 3 × 1 (sarake) tai 1 × 3 (rivi) tasolle avaruudelle 4 × 1 tai 1 × 4.
  4. Olkoon M 1 ( x 1 , y 1 ) ja M 2 ( x 2 , y 2 ) kaksi suorakulmaisessa koordinaatistossa annettua pistettä ja M ( x , y ) suoran nykyinen piste. Linjan yhtälö kirjoitetaan: ( x - x 1 ) ( y - y 2 ) = ( x - x 2 ) ( y - y 1 ) Korvaamalla lauseke x = u / w  ; y = v / w suorakulmaisia ​​koordinaatteja homogeenisten koordinaattien funktiona, ja kertomalla kaksi jäsentä ( ww 1 w 2 ) saadaan täysin antisymmetrinen yhtälö: + uv 1 w 2 - uv 2 w 1 + vw 1 u 2 - vw 2 u 1 + wu 1 v 2 - wu 2 v 1 = 0
  5. Tämän matriisin laskeminen on helppoa asettamalla peräkkäin vain yksi x 1: n elementeistä yhtä suuri kuin 1, muut nolla. Tämä puolestaan ​​antaa F: n sarakkeet .
  6. Suora määritetään homogeenisissa koordinaateissa nollasta poikkeavalla matriisilla d siten, että suoran nykyinen piste x tyydyttää d T  x  = 0
  7. Tämä vastaa yleensä kahta identtistä kameraa, jotka ovat kohtisuorassa näkölinjaan nähden, enimmäkseen vaakasuorassa.
  8. Objektin peräkkäiset kuvat suurenevat sitä nopeammin, mitä lähempänä kamera sitä on. Näin on kuviossa 11 (kokoonpano 2) olevan vihreän pallon kuvasta , joka on lähempänä oranssia palloa ja joka sen vuoksi kasvaa nopeammin kameran B- ja A-asemien välillä. Ongelma vaikeutuu, kun robotti tekee käännöksen.

Katso myös