Algoritm în opt puncte - Eight-point algorithm

Algoritmul de opt puncte este un algoritm folosit în viziune de calculator pentru a estima matricea esențială sau matricea fundamentală legată de o pereche stereo camera dintr - un set de puncte de imagine corespunzătoare. A fost introdus de Christopher Longuet-Higgins în 1981 pentru cazul matricei esențiale. În teorie, acest algoritm poate fi utilizat și pentru matricea fundamentală, dar în practică algoritmul normalizat în opt puncte , descris de Richard Hartley în 1997, este mai potrivit pentru acest caz.

Numele algoritmului derivă din faptul că estimează matricea esențială sau matricea fundamentală dintr-un set de opt (sau mai multe) puncte de imagine corespunzătoare. Cu toate acestea, variațiile algoritmului pot fi utilizate pentru mai puțin de opt puncte.

Constrângerea de coplanaritate

Exemplu de geometrie epipolară. Două camere, cu centrele lor de puncte de proiecție O _L și O _R , observă un punct P . Proiecția P pe fiecare plan de imagine este notat p _L și p _R . Punctele E _L și E _R sunt epipolii.

Se poate exprima geometria epipolară a două camere și un punct din spațiu cu o ecuație algebrică. Observați că, indiferent în cazul în care punctul este în spațiu, vectorii , și aparțin aceluiași plan. Apelați coordonatele punctului din cadrul de referință al ochiului stâng și apelați coordonatele din cadrul de referință al ochiului drept și apelați rotația și translația dintre cele două cadre de referință st este relația dintre coordonatele din cele două cadre de referință. Următoarea ecuație se menține întotdeauna deoarece vectorul generat este ortogonal pentru ambele și  : ${\ displaystyle P}$${\ displaystyle {\ overline {O_ {L} P}}}$${\ displaystyle {\ overline {O_ {R} P}}}$${\ displaystyle {\ overline {O_ {R} O_ {L}}}}$${\ displaystyle X_ {L}}$${\ displaystyle P}$${\ displaystyle X_ {R}}$${\ displaystyle P}$${\ displaystyle R, T}$${\ displaystyle X_ {R} = R (X_ {L} -T)}$${\ displaystyle P}$${\ displaystyle T \ wedge X_ {L}}$${\ displaystyle T}$${\ displaystyle X_ {L}}$

${\ displaystyle X_ {L} ^ {T} T \ wedge X_ {L} -T ^ {T} T \ wedge X_ {L} = (X_ {L} -T) ^ {T} T \ wedge X_ {L } = 0}$

Pentru că , obținem ${\ displaystyle I = R ^ {T} R}$

${\ displaystyle (X_ {L} -T) ^ {T} R ^ {T} RT \ wedge X_ {L} = 0}$.

Înlocuind cu , obținem ${\ displaystyle (X_ {L} -T) ^ {T} R ^ {T}}$${\ displaystyle X_ {R} ^ {T}}$

${\ displaystyle X_ {R} ^ {T} RT \ wedge X_ {L} = X_ {R} ^ {T} RSX_ {L} = X_ {R} ^ {T} EX_ {L} = 0}$

Observați că se poate considera că este o matrice; Longuet-Higgins a folosit simbolul pentru a-l indica. Produsul este adesea numit matrice esențială și notat cu . ${\ displaystyle T \ wedge}$${\ displaystyle S}$${\ displaystyle RT \ wedge = RS}$${\ displaystyle E}$

Vectorii sunt paraleli cu vectorii și, prin urmare, constrângerea de coplanaritate se menține dacă substituim acești vectori. Dacă apelăm coordonatele proiecțiilor pe planurile de imagine stânga și dreapta, atunci constrângerea de coplanaritate poate fi scrisă ca ${\ displaystyle {\ overline {O_ {L} p_ {L}}}, {\ overline {O_ {R} p_ {R}}}}$${\ displaystyle {\ overline {O_ {L} P}}, {\ overline {O_ {R} P}}}$${\ displaystyle y, y '}$${\ displaystyle P}$

${\ displaystyle y '^ {T} \ mathbf {E} y = 0}$

Algoritm de bază

Algoritmul de bază în opt puncte este descris aici pentru cazul estimării matricei esențiale . Se compune din trei pași. În primul rând, formulează o ecuație liniară omogenă , în care soluția este direct legată și apoi rezolvă ecuația, luând în considerare faptul că este posibil să nu aibă o soluție exactă. În cele din urmă, constrângerile interne ale matricei rezultate sunt gestionate. Primul pas este descris în lucrarea lui Longuet-Higgins, al doilea și al treilea pas sunt abordări standard în teoria estimării. ${\ displaystyle \ mathbf {E}}$${\ displaystyle \ mathbf {E}}$

Constrângerea definită de matricea esențială este ${\ displaystyle \ mathbf {E}}$

${\ displaystyle (\ mathbf {y} ') ^ {T} \, \ mathbf {E} \, \ mathbf {y} = 0}$

pentru punctele de imagine corespunzătoare reprezentate în coordonate de imagine normalizate . Problema rezolvată de algoritm este de a determina pentru un set de puncte de imagine potrivite. În practică, coordonatele imaginii punctelor de imagine sunt afectate de zgomot și soluția poate fi, de asemenea, supra-determinată, ceea ce înseamnă că este posibil să nu fie posibil să se găsească care satisface constrângerea de mai sus exact pentru toate punctele. Această problemă este abordată în al doilea pas al algoritmului. ${\ displaystyle \ mathbf {y}, \ mathbf {y} '}$${\ displaystyle \ mathbf {E}}$${\ displaystyle \ mathbf {E}}$

Pasul 1: Formularea unei ecuații liniare omogene

Cu

${\ displaystyle \ mathbf {y} = {\ begin {pmatrix} y_ {1} \\ y_ {2} \\ 1 \ end {pmatrix}}}$   și     și   ${\ displaystyle \ mathbf {y} '= {\ begin {pmatrix} y' _ {1} \\ y '_ {2} \\ 1 \ end {pmatrix}}}$${\ displaystyle \ mathbf {E} = {\ begin {pmatrix} e_ {11} & e_ {12} & e_ {13} \\ e_ {21} & e_ {22} & e_ {23} \\ e_ {31} & e_ {32 } & e_ {33} \ end {pmatrix}}}$

constrângerea poate fi rescrisă și ca

${\ displaystyle y '_ {1} y_ {1} e_ {11} + y' _ {1} y_ {2} e_ {12} + y '_ {1} e_ {13} + y' _ {2} y_ {1} e_ {21} + y '_ {2} y_ {2} e_ {22} + y' _ {2} e_ {23} + y_ {1} e_ {31} + y_ {2} e_ { 32} + e_ {33} = 0 \,}$

sau

${\ displaystyle \ mathbf {e} \ cdot {\ tilde {\ mathbf {y}}} = 0}$

Unde

${\ displaystyle {\ tilde {\ mathbf {y}}} = {\ begin {pmatrix} y '_ {1} y_ {1} \\ y' _ {1} y_ {2} \\ y '_ {1 } \\ y '_ {2} y_ {1} \\ y' _ {2} y_ {2} \\ y '_ {2} \\ y_ {1} \\ y_ {2} \\ 1 \ end {pmatrix}}}$   și   ${\ displaystyle \ mathbf {e} = {\ begin {pmatrix} e_ {11} \\ e_ {12} \\ e_ {13} \\ e_ {21} \\ e_ {22} \\ e_ {23} \ \ e_ {31} \\ e_ {32} \\ e_ {33} \ end {pmatrix}}}$

adică reprezintă matricea esențială sub forma unui vector cu 9 dimensiuni și acest vector trebuie să fie ortogonal cu vectorul care poate fi văzut ca o reprezentare vectorială a matricei . ${\ displaystyle \ mathbf {e}}$${\ displaystyle {\ tilde {\ mathbf {y}}}}$${\ displaystyle 3 \ times 3}$${\ displaystyle \ mathbf {y} '\, \ mathbf {y} ^ {T}}$

Fiecare pereche de puncte de imagine corespunzătoare produce un vector . Având în vedere un set de puncte 3D, acesta corespunde unui set de vectori și toți trebuie să se satisfacă ${\ displaystyle {\ tilde {\ mathbf {y}}}}$${\ displaystyle \ mathbf {P} _ {k}}$${\ displaystyle {\ tilde {\ mathbf {y}}} _ {k}}$

${\ displaystyle \ mathbf {e} \ cdot {\ tilde {\ mathbf {y}}} _ {k} = 0}$

pentru vector . Având în vedere suficient de mulți (cel puțin opt) vectori liniar independenți , este posibil să se determine într-un mod direct. Colectați toți vectorii ca coloane ale unei matrice și atunci trebuie să fie cazul ${\ displaystyle \ mathbf {e}}$${\ displaystyle {\ tilde {\ mathbf {y}}} _ {k}}$${\ displaystyle \ mathbf {e}}$${\ displaystyle {\ tilde {\ mathbf {y}}} _ {k}}$${\ displaystyle \ mathbf {Y}}$

${\ displaystyle \ mathbf {e} ^ {T} \, \ mathbf {Y} = \ mathbf {0}}$

Aceasta înseamnă că este soluția la o ecuație liniară omogenă . ${\ displaystyle \ mathbf {e}}$

Pasul 2: Rezolvarea ecuației

O abordare standard pentru rezolvarea acestei ecuații implică faptul că este un vector singular stânga al care corespunde unei valori singulare , care este egal cu zero. Cu condiția să se utilizeze cel puțin opt vectori liniar independenți pentru a construi , rezultă că acest vector singular este unic (fără a lua în considerare multiplicarea scalară) și, în consecință, și apoi poate fi determinat. ${\ displaystyle \ mathbf {e}}$${\ displaystyle \ mathbf {Y}}$${\ displaystyle {\ tilde {\ mathbf {y}}} _ {k}}$${\ displaystyle \ mathbf {Y}}$${\ displaystyle \ mathbf {e}}$${\ displaystyle \ mathbf {E}}$

În cazul în care sunt utilizate mai mult de opt puncte corespunzătoare pentru a construi , este posibil să nu aibă nicio valoare singulară egală cu zero. Acest caz apare în practică atunci când coordonatele imaginii sunt afectate de diferite tipuri de zgomot. O abordare comună pentru a face față acestei situații este de a o descrie ca o problemă totală a celor mai mici pătrate ; găsi care minimizează ${\ displaystyle \ mathbf {Y}}$${\ displaystyle \ mathbf {e}}$

${\ displaystyle \ | \ mathbf {e} ^ {T} \, \ mathbf {Y} \ |}$

când . Soluția este de a alege ca vector singular la stânga corespunzător celei mai mici valori singular a . O reordonare a acestuia înapoi într-o matrice dă rezultatul acestui pas, denumit aici . ${\ displaystyle \ | \ mathbf {e} \ | = 1}$${\ displaystyle \ mathbf {e}}$${\ displaystyle \ mathbf {Y}}$${\ displaystyle \ mathbf {e}}$${\ displaystyle 3 \ times 3}$${\ displaystyle \ mathbf {E} _ {\ rm {est}}}$

Pasul 3: Aplicarea constrângerii interne

O altă consecință a gestionării coordonatelor de imagine zgomotoase este că matricea rezultată poate să nu satisfacă constrângerea internă a matricei esențiale, adică două dintre valorile sale singulare sunt egale și diferite de zero, iar cealaltă este zero. În funcție de aplicație, abaterile mai mici sau mai mari de la constrângerea internă pot fi sau nu o problemă. Dacă este esențial ca matricea estimată să satisfacă constrângerile interne, acest lucru poate fi realizat găsind matricea de rangul 2 care minimizează ${\ displaystyle \ mathbf {E} '}$

${\ displaystyle \ | \ mathbf {E} '- \ mathbf {E} _ {\ rm {est}} \ |}$

unde este matricea rezultată din Pasul 2 și se utilizează norma matricială Frobenius . Soluția problemei este dată de primul calcul al unei descompuneri a valorii singulare a : ${\ displaystyle \ mathbf {E} _ {\ rm {est}}}$${\ displaystyle \ mathbf {E} _ {\ rm {est}}}$

${\ displaystyle \ mathbf {E} _ {\ rm {est}} = \ mathbf {U} \, \ mathbf {S} \, \ mathbf {V} ^ {T}}$

unde sunt matrici ortogonale și este o matrice diagonală care conține valorile singulare ale . În cazul ideal, unul dintre elementele diagonale ar trebui să fie zero sau cel puțin mic în comparație cu celelalte două care ar trebui să fie egale. În orice caz, setați ${\ displaystyle \ mathbf {U}, \ mathbf {V}}$${\ displaystyle \ mathbf {S}}$${\ displaystyle \ mathbf {E} _ {\ rm {est}}}$${\ displaystyle \ mathbf {S}}$

${\ displaystyle \ mathbf {S} '= {\ begin {pmatrix} s_ {1} & 0 & 0 \\ 0 & s_ {2} & 0 \\ 0 & 0 & 0 \ end {pmatrix}},}$

unde sunt cele mai mari și a doua valori mari la singular, respectiv. În cele din urmă, este dat de ${\ displaystyle s_ {1}, s_ {2}}$${\ displaystyle \ mathbf {S}}$${\ displaystyle \ mathbf {E} '}$

${\ displaystyle \ mathbf {E} '= \ mathbf {U} \, \ mathbf {S}' \, \ mathbf {V} ^ {T}}$

Matricea este estimarea rezultată a matricei esențiale furnizate de algoritm. ${\ displaystyle \ mathbf {E} '}$

Algoritm normalizat

Algoritmul de bază în opt puncte poate fi utilizat în principiu și pentru estimarea matricei fundamentale . Constrângerea definitorie pentru este ${\ displaystyle \ mathbf {F}}$${\ displaystyle \ mathbf {F}}$

${\ displaystyle (\ mathbf {y} ') ^ {T} \, \ mathbf {F} \, \ mathbf {y} = 0}$

unde sunt reprezentările omogene ale coordonatelor corespunzătoare ale imaginii (nu sunt necesare normalizate). Aceasta înseamnă că este posibil să se formeze o matrice într-un mod similar cu cel pentru matricea esențială și să se rezolve ecuația ${\ displaystyle \ mathbf {y}, \ mathbf {y} '}$${\ displaystyle \ mathbf {Y}}$

${\ displaystyle \ mathbf {f} ^ {T} \, \ mathbf {Y} = \ mathbf {0}}$

pentru care este o versiune remodelată a . Urmând procedura descrisă mai sus, este apoi posibil să se determine dintr-un set de opt puncte potrivite. În practică, totuși, matricea fundamentală rezultată poate să nu fie utilă pentru determinarea constrângerilor epipolare. ${\ displaystyle \ mathbf {f}}$${\ displaystyle \ mathbf {F}}$${\ displaystyle \ mathbf {F}}$

Dificultate

Problema este că rezultatul este adesea prost condiționat . În teorie, ar trebui să aibă o valoare singulară egală cu zero, iar restul sunt nenule. Cu toate acestea, în practică, unele dintre valorile singularului non-zero pot deveni mici în raport cu cele mai mari. Dacă sunt utilizate mai mult de opt puncte corespunzătoare pentru a construi , în cazul în care coordonatele sunt doar aproximativ corecte, este posibil să nu existe o valoare singulară bine definită care poate fi identificată ca fiind aproximativ zero. În consecință, soluția sistemului liniar omogen de ecuații poate să nu fie suficient de precisă pentru a fi utilă. ${\ displaystyle \ mathbf {Y}}$${\ displaystyle \ mathbf {Y}}$${\ displaystyle \ mathbf {Y}}$

Cauză

Hartley a abordat această problemă de estimare în articolul său din 1997. Analiza sa asupra problemei arată că problema este cauzată de distribuția slabă a coordonatelor omogene ale imaginii în spațiul lor ,. O reprezentare omogenă tipică a coordonatei imaginii 2D este ${\ displaystyle \ mathbb {R} ^ {3}}$${\ displaystyle (y_ {1}, y_ {2}) \,}$

${\ displaystyle \ mathbf {y} = {\ begin {pmatrix} y_ {1} \\ y_ {2} \\ 1 \ end {pmatrix}}}$

unde ambele se situează între 0 și 1000–2000 pentru o cameră digitală modernă. Aceasta înseamnă că primele două coordonate variază într-un interval mult mai mare decât a treia coordonată. Mai mult, dacă punctele de imagine care sunt utilizate pentru a construi se află într-o regiune relativ mică a imaginii, de exemplu la , din nou vectorul indică mai mult sau mai puțin aceeași direcție pentru toate punctele. În consecință, va avea o valoare singulară mare, iar restul sunt mici. ${\ displaystyle y_ {1}, y_ {2} \,}$${\ displaystyle \ mathbf {y}}$${\ displaystyle \ mathbf {Y}}$${\ displaystyle (700.700) \ pm (100.100) \,}$${\ displaystyle \ mathbf {y}}$${\ displaystyle \ mathbf {Y}}$

Soluţie

Ca soluție la această problemă, Hartley a propus ca sistemul de coordonate al fiecăreia dintre cele două imagini să fie transformat, independent, într-un nou sistem de coordonate conform următorului principiu.

• Originea noului sistem de coordonate ar trebui să fie centrat (să aibă originea) la centroul (centrul de greutate) al punctelor imaginii. Acest lucru se realizează printr-o traducere a originii originale în cea nouă.
• După traducere, coordonatele sunt scalate uniform, astfel încât distanța medie de la origine la un punct să fie egală .${\ displaystyle {\ sqrt {2}}}$

Acest principiu are ca rezultat, în mod normal, o transformare distinctă a coordonatelor pentru fiecare dintre cele două imagini. Ca rezultat, noile coordonate omogene ale imaginii sunt date de ${\ displaystyle \ mathbf {\ bar {y}}, \ mathbf {\ bar {y}} '}$

${\ displaystyle \ mathbf {\ bar {y}} = \ mathbf {T} \, \ mathbf {y}}$

${\ displaystyle \ mathbf {\ bar {y}} '= \ mathbf {T}' \, \ mathbf {y} '}$

unde sunt transformările (traducerea și scalarea) de la vechea la noua coordonată normalizată a imaginii . Această normalizare depinde doar de punctele de imagine care sunt utilizate într-o singură imagine și este, în general, distinctă de coordonatele de imagine normalizate produse de o cameră normalizată. ${\ displaystyle \ mathbf {T}, \ mathbf {T} '}$

Constrângerea epipolară bazată pe matricea fundamentală poate fi acum rescrisă ca

${\ displaystyle 0 = (\ mathbf {\ bar {y}} ') ^ {T} \, ((\ mathbf {T}') ^ {T}) ^ {- 1} \, \ mathbf {F} \ , \ mathbf {T} ^ {- 1} \, \ mathbf {\ bar {y}} = (\ mathbf {\ bar {y}} ') ^ {T} \, \ mathbf {\ bar {F}} \, \ mathbf {\ bar {y}}}$

unde . Aceasta înseamnă că este posibil să se utilizeze coordonatele de imagine omogene normalizate pentru a estima matricea fundamentală transformată utilizând algoritmul de bază în opt puncte descris mai sus. ${\ displaystyle \ mathbf {\ bar {F}} = ((\ mathbf {T} ') ^ {T}) ^ {- 1} \, \ mathbf {F} \, \ mathbf {T} ^ {- 1 }}$${\ displaystyle \ mathbf {\ bar {y}}, \ mathbf {\ bar {y}} '}$${\ displaystyle \ mathbf {\ bar {F}}}$

Scopul transformărilor de normalizare este acela că matricea , construită din coordonatele imaginii normalizate, are, în general, un număr de condiție mai bun decât are. Aceasta înseamnă că soluția este mai bine definită ca soluție a ecuației omogene decât este relativă la . Odată ce a fost determinat și remodelat în acesta din urmă poate fi de-normalizat pentru a da în conformitate cu ${\ displaystyle \ mathbf {\ bar {Y}}}$${\ displaystyle \ mathbf {Y}}$${\ displaystyle \ mathbf {\ bar {f}}}$${\ displaystyle \ mathbf {\ bar {Y}} \, \ mathbf {\ bar {f}}}$${\ displaystyle \ mathbf {f}}$${\ displaystyle \ mathbf {Y}}$${\ displaystyle \ mathbf {\ bar {f}}}$${\ displaystyle \ mathbf {\ bar {F}}}$${\ displaystyle \ mathbf {F}}$

${\ displaystyle \ mathbf {F} = (\ mathbf {T} ') ^ {T} \, \ mathbf {\ bar {F}} \, \ mathbf {T}}$

În general, această estimare a matricei fundamentale este mai bună decât ar fi fost obținută prin estimarea din coordonatele ne-normalizate.

Folosind mai puțin de opt puncte

Fiecare pereche de puncte contribuie cu o ecuație de constrângere a elementului din . Deoarece are cinci grade de libertate, ar trebui, prin urmare, să fie suficient cu doar cinci perechi de puncte pentru a determina . Deși este posibilă din punct de vedere teoretic, implementarea practică a acestui lucru nu este simplă și se bazează pe rezolvarea diferitelor ecuații neliniare. ${\ displaystyle \ mathbf {E}}$${\ displaystyle \ mathbf {E}}$${\ displaystyle \ mathbf {E}}$

Kaveh Fathian și colab. au propus algoritmi pentru cinci, șase și șapte puncte care ocolesc calculul matricei esențiale prin calcularea cuaternionului de rotație direct.

Vezi si

• Matrice esențială
  • Matrice esențială # Extragerea rotației și translației
• Matrice fundamentală
• Tensor trifocal

Referințe

Lecturi suplimentare

• Richard I. Hartley (iunie 1997). „În apărarea algoritmului de opt puncte”. Tranzacții IEEE privind recunoașterea modelelor și inteligența mașinilor . 19 (6): 580-593. doi : 10.1109 / 34.601246 .

• Richard Hartley și Andrew Zisserman (2003). Geometrie cu vizualizare multiplă în viziunea computerizată . Cambridge University Press. ISBN 978-0-521-54051-3.

• H. Christopher Longuet-Higgins (septembrie 1981). „Un algoritm computerizat pentru reconstituirea unei scene din două proiecții”. Natura . 293 (5828): 133-135. doi : 10.1038 / 293133a0 .