Un Doi și Trei: Istoria unei Margarete

Introducere

Articolul iși propune să pună în lumină intr-un desfașurator istoric o ramură intens studiată în domeniul recunoașterii formelor sau computer vision numită: Structuri din Mișcare.

Aceasta ramură aparte, Structuri din Mișcare, studiază procesele de extragere a informației spațiale dintr-un șir de inregistrări bidimensionale a unei realitații fizice. Ca și model de referință studiază cum anume ochiul sau viziunea umană poate percepe și procesa conceptul “spațiu”, iar prin analogie încearcă sa găsească metodele numerice fezabile pe un sistem de calcul.

Deoarece o imagine nu este nimic altceva decât o inșiruiure numerică a unor intensități luminoase, care pot fi captate cu un senzor (un CCD spre exemplu), este foarte dificil de însușit o corelare între aceste masurători numerice și concepte umane ințelese ca fiind geometrii. Acele concepte pe care orice ființă umană (și nu numai) le ințelege cu ușurință, sunt pe cât de simple pe atât de imposibil de mimat sau descifrat numeric, cum ar fi câteva de bază: distanță, adâncime, margine, contur, etc.

Metode Numerice.

Foarte important de notat în metodele descrise în acest articol este noțiunea de fezabilitate a unei metode numerice. Nu orice metodă este fezabilă și aplicabilă oricât ar parea ea de logică sau plină de sens matematic absolut. Este mai mult decât dificil de găsit o metodă fezabilă, de multe ori ea nu are logică, ori este inspirată din pură intuiție, și dacă nici intuiție atunci mai sunt șanse de căutare în modelele banale ale naturii. Fezabilitatea algoritmică definește ce se poate și ce nu pe un sistem de calcul, care este de altfel o creație inginerească limitată. Ideea de fezabilitate numerică a fost introdusă și la preocupat pe însăși Alan Turing, părintele științei moderne numită astăzi Informatică, devenit celebru după descifrarea codului ENIGMA, utilizat de nemți în comunicațiile radio din al doilea război mondial, descifrare care a influențat decisiv soarta războiului.

Începutul

1988: Chris Harris și Mike Stephens, doi cercetători la compania The Plessey Company PLC din Marea Britanie, publică lucrarea intitulată A combined corner and edge detector, considerată a fi un pas foarte important în a defini niște repere cheie solide din punct de vedere numeric. Practic, ei reușesc în mod fezabil translatarea concepului uman ‘punct de reper’ în ceva exprimabil numeric, având proprietați clar definibile și determinabile cu un aparat matematic. Se enunță astfel pentru prima oară necesitatea de a introduce conceptul numit descriptor local, mai exact, în lucrare, se consideră ca fiind practic un punct luat după o regulă numerică de-a dreptul banală: colțurile !

Figura 1: Detecția colțurilor Harris pe un raster reprezentând geometrii compuse.

În Figura 1. se pot observa colțurile determinate cu metoda Harris. Metoda numerică pentru a găsi aceste colțuri este una simplă, o posibilă formulă logică enunțată schematic ar fi:

• Pentru fiecare pixel se ia în considerare adiacențele și se observă stările acestora.
• Dacă adiacențele sunt doar parțiale, se poate afla dacă pixelul poate fi clasificat colț sau nu.

Logica descrisă mai sus nu este suficientă, deoarece un singur pixel în multe cazuri nu poate neapărat defini dacă este sau nu un colț vizual al unui grup mult mai mare de pixeli. Harris a dezvoltat această idee (mai veche de altfel) și a utilizat blocuri mai mari de pixeli (patch-uri) observând diferențele în scorul unei sume calculate către toate adiacențele carteziene posibile. Diferențele obținute înspre vecinătațile permise reflectă de fapt cu adevărat lipsa sau prezența conectivităților adiacente, la un nivel de macro-pixeli, respectiv diferențele numerice indică dacă există un gol geometric, iar în acest caz se poate clasifica drept un colț. Metoda obținută de Harris este astăzi consacrată în literatura de specialitate ca Harris corners sau colțuri Harris.

Colțurile Harris în primul rând reprezintă o metodă fezabilă numeric pe un sistem de calcul, chiar și pentru sistemele anilor 1988, acesta detectează precis cu un număr redus de puncte false ‘outliers’ colțurile într-un raster dat, fapt ce a făcut metoda să fie extrem de populară și longeviva până în zilele noastre.

Doar Colțuri.

O intrebare firească ar fi la ce sunt bune colțurile ? Și care ar fi valoarea lor numerică ? Raspunsul se află în Figura 2. ilustrată mai jos:

Figura 2: Invarianța colțurilor detectate cu Harris.

În perechile din Figura 2. se observă un lucru important, și anume: colțurile sunt aceleași și neschimbate în ambele imagini chiar dacă imaginea din dreapta este luată vizual din alt unghi sau este mai deformată fața de prima. După această observație se poate afirma un lucru important: colțurile detectate de Harris sunt invariante la rotire, scalare și translație !

Colțurile practic leagă cu o informatie numerică două imagini raster și ne pot spune ce anume este comun între două imagini distincte deci ele pot fi numite: descriptori locali.

Figura 3: Colțuri Harris în două imagini luate în perspective diferite.

Figura 4: Imaginile coregistrate după punctele Harris.

Figura 3 și Figura 4 exemplifică un proces de coregistrare a două imagini, în prima imagine sunt determinate colțurile de tip Harris, iar în a doua imagine, pe baza colțurilor, o imagine este proiectată în cealaltă imagine, adică este coregistrată.

O implementare numerică a colțurilor Harris poate fi gasită cu usurintă pe internet, ea fiind foarte raspandită pe site-urile laboratoarelor din cadrul universitaților preocupate de recunoașterea formelor.

În timp, metoda numerică Herris, a fost rafinată și îmbunatățită, două optimizări majore sunt reprezentate prin colțurile Susan, respectiv mai recent FAST, a căror proprietăți constă într-o detecție mai sofisticată a inflexiunilor raster cu o modalitate relativ rapidă. Utilizând grafuri și arbori de decizie, în a defini dacă un pixel este sau nu colț, se obține metoda AGAST, alintată și “faster than FAST and even FAST-ER”. AGAST a apărut public în 2010 și a fost gândit din raționamente pure de sistem de calcul, fiind conceput strict pentru a satisface o singură condiție: viteză de execuție. Se consideră că viteza este mai importantă decât corectitudinea absolută, în ideea că în pașii următori, unde vor fi folosite aceste colțuri, acestea pot fi triate după diverse necesități.

Vectori Multidimensionali.

Dacă detectoarele de colțuri, care produc descriptori locali, se plasează în domeniul cartezian și sunt exprimate în coordonate bidimensione X și Y, ca fiind insăși poziția lor în poza de proveniență, atunci se ridică problema acurateții acestor descriptori în scene complexe, unde simplul element geometric colț nu este îndeajuns, sau atunci când densitatea și multitudinea colțurilor poate perturba, sau cazul în care imaginea este saracă în colțuri geometrice. În acest caz, puteți să vă imaginați o scenă color, cu niște nori, unde cu siguranță simple colțuri vor produce rezultate false.

Figura 5: Descriptori SIFT într-un proces de coregistrare.

1999: David G. Lowe profesor la Universitatea British Columbia din Vancouver, Canada, introduce un nou descriptor și un proces însoțit de acesta SIFT, prescurtarea definiției fiind: “Scale-invariant feature transform”.

Ce este SIFT ? SIFT este un descriptor al cărui rezultat este exprimat ca un vector multidimensional în spațiul R, el fiind conceput cu 128 de dimensiuni. Într-un limbaj pur laic, poate fi considerat o înșiruire de numere atribuite unui pixel, care reflectă influența adiacențelor asupra pixelului din imagine. Acesta ar putea reprezenta “horoscopul” personal: Cine este pixelul din raster ? Ce îl face pe el unic într-o imagine ? Poate că pixelul observat mai atent, luând în considerare vecinii lui, prezintă nuanțe violet spre rosu s.a.m.d., care îi confirma o identitate complet unică. De altfel, afirmația laică enunțată, este doar o analogie ilustrativă, SIFT operând doar pe intensitățile imaginilor gri, nu color.

Figura 6: Schema de calcul SIFT.

Un vector SIFT este calculat ca și suma ponderată a valorilor normale (intensități), peste un gradient (grupuri de pixeli), luați adiacenți fată de pixelul analizat, unde factorul de pondere a sumelor depinde de distanța față de pixelul central analizat. Adiacența este lconsiderată a fi una carteziană.

SIFT devine brusc metoda de reper absolut în domeniu, rezultatele obținute fiind net superioare colturilor Harris, reprezintă calitați de invarianță foarte ridicată la aproape orice: rotire, scalare, translație. Totuși se ridică o nouă problemă: cum se pot corela acești vectori între două imagini?

Dacă colțurile Harris erau simple perechi de valori X și Y, SIFT este un vector multidimensional, o comparație între doi vectori în scopul de a vedea, între două imagini, care perechi se potrivesc. Se ajunge astfel la o preocupare intensă către metodele eficiente de “key matching”, sau corelare de puncte în spații multidimensionale.

Corelări Multidimensionale.

Pornind de la ideea, că pașii de corelare sau “key matching” ai vectorilor nu sunt altceva decât o problemă de segmentare sau partiționare valorică a elementelor vectoriale, apar și primele abordări cum ar fi Best Bin First sau K-D Tree, culminând cu implementarea numerică botezată ANN.

Figura 7: ANN, segmentare ilustrativă în spațiu multidimensional.

Metoda ANN presupune o aliniere ierarhică a membrilor vectoriali într-un hiperplan multidimensional, unde se întâmplă o segmentare spațială, rezultatul fiind doar unul “aproximativ”. Această aproximare se dovedește în practică a fi suficientă dacă se folosește o mulțime mare de vectori, ca de exemplu descriptori SIFT generați din imagini.

În căutarea unei metode mai rapide și fezabile pe un sistem de calcul, apare FLANN, o suita soft compusă din două metode (amintite anterior) care alternează în funcție de caz, pentru a obține rezultate rapide, respectiv este adecvată și pe sisteme de calcul masiv, în paralel utilizând standardul MPI.

O margaretă nouă: DAISY

Figura 8: Schematizarea metodei DAISY, comparată cu modelul petalelor unei flori.

2008: Engin Tola, Pascal Fua și Vincent Lepetit de la EPFL CVLab din Lausanne, Elveția, publică in cadrul CVPR ediția 2009 lucrarea intitulată A fast local descriptor for dense matching. Articolul prezintă un descriptor cu totul nou, similar cu SIFT, având ca rezultat tot vectori multidimensionali, concepuți cu 192 de elemente. DAISY prezintă ceva unic fată de SIFT, se calculează mult mai ușor, iar anumiți pași de calcul ai gradienților din jurul pixelului sunt simplificați dramatic. În schimb, modalitatea de eșantiontiare a adiacențelor, este ingenios inspirată din natură, conform dispunerii radiale a petalelor unei flori, ilustrat în Figura 8. Tocmai această dispunere garantează superioritatea noului descriptor local, și il scutește de calcule expensive.

DAISY permite calculul descriptorilor pentru absolut toți pixelii dintr-o imagine, iar vectorii rezultați garantează o invarianță superioară. Pentru prima oară se merge dincolo de a corela doar două poze intre ele, și se incearcă cu rezultate foarte bune, ceva ce părea imposibil înainte: calculul eficient a unui “depth-map” sau harți de adâncime chiar și din două poze complet mono oculare, sau ne-aliniate optic într-un format “stereo” restituibil. Rezultatul calculului este un pas important spre a reflecta realitatea 3D a pozelor oarecare. În 2009 se publică un studiu care evidențiează calitățile DAISY în calcule “depth-map”, întitulat DAISY: An Efficient Dense Descriptor Applied to Wide Baseline Stereo.

Ambiții 3D. Fezabil ?

Atât DAISY cât și SIFT sunt descriptori multidimensionali exprimați ca numere reale, mai exact cu valori numerice de la 0…255, de tip unsigned char. Fiind exprimat ca unsigned char, practic un membru al vectorului, ocupa exact un octet din memorie. O imagine modestă de 5 Mpix, descrisă pentru toți pixelii cu un descriptor DAISY, va însuma 5.000.000 pixeli x 192 octeți = 960 Mocteți, adică pentru o singură imagine reprezintă limita unui sistem de calcul decent. Pentru determinări “depth-map” peste mai multe imagini este nevoie de un sistem dotat în primul rând cu memorie RAM.

Două abordări:

“Rarefiat“ (Sparse): Având în vedere resursele de memorie limitate, o abordare care urmărește obținerea de modele 3D, fară calcul “depth-map” din rasteri, ar consta în a ne limita doar la determinarea elementelor comune între poze și nu a merge până la un “depth-map” cu toți pixelii. Asta de ce nu chiar cu Harris, sau cel mai potrivit DAISY sau SIFT, poate chiar o combinație succesivă între ele. Se poate observa relația între poze cu metode și măsurători sugerate de Thales sau Pitagora, însemnând operații cu unghiuri și determinări de poziții, adică elemente clasice de geometrie. Nu este nevoie de un calcul complet al descriptorilor locali pe toată imaginea. Se poate merge pe ideea de a colecta colțuri Harris în mod nepretențios cu FAST sau AGAST, respectiv pentru fiecare dintre aceste colțuri găsite se poate efectua un calcul mult mai precis DAISY sau SIFT. Astfel, găsim o reprezentare rarefiată dar suficientă pentru a corela corect și precis, două sau mai multe imagini. Deoarece punctele multidimensionale găsite reprezintă un procent mic din imagine nu se ridică probleme de memorie a sistemului.

Figura 9: Starea scenei optice cu puncte “rarefiate” comune din imagini.

În Figura 9 se pot observa punctele P1…Pn determinate ca fiind cele comune imaginilor. Utilizarea simplă a teoremelor Thales și Pitagora nu este neapărat suficientă pentru a determina pozițiile exacte a camerelor în spațiu, deoarece necunoscutele sunt matricile R,T (rotație, translație) particulare fiecărei camere în parte. Avem un sistem de ecuații complex f(R,T,P) în care doar P1…Pn sunt cunoscute relativ la imaginile de proveniență, eventual și distanțele focale ale lentilelor (din informația EXIF), care poate fi un ajutor minor. Metoda Levenberg-Marquardt poate minimiza și oferi soluția fiecărui set R și T din multitudinea de puncte P cunoscute. LMA (Levenberg-Marquardt) este utilizată în această metodă numerică cunoscută și ca SBA (Sparse Bundle Adjustment). Rezultatul conduce la obținerea realității 3D vectoriale a intregii scene la modul “rarefiat”, iar punctele P1…Pn sunt realiniate corect in spațiu, din moment ce R,T-urile specifice camerelor sunt determinate exact.

Odată ce modelul “rarefiat” este determinat, acesta poate fi densificat în pașii următori. Yasutaka Furukawa, în proiectul public PMVS, prezintă o soluție simplă de post-densificare, utilizând ideea de a proiecta din imaginile raster înspre scena determinată, niște grupuri de pixeli (patchuri), împreună cu informația de culoare. Implementarea se numește: “Patch based multi-view stereo”. Cu ajutorul PMVS s-au obținut rezultate impresionante în reconstrucția întreagă a unui oraș: “Building Rome in a day”, doar din imagini luate de către turiști și postate pe servicii publice: Picasa, Flickr, Panoramio.
Metoda “rarefiată” este adecvată chiar și pentru zeci de mii de poze și fezabilă pe un sistem de calcul decent. Precizia scenei poate umili chiar și un LIDAR, dealtfel foarte costisitor, în plus modelul final este unul color.

“Profund“ (Dense): Este abordarea densă de a calcula “depth-map” integral chiar dacă ridică probleme de memorie. În acest scop, se încearcă reducerea dimensională a vectorilor DAISY sau SIFT având impact final intr-un spațiu mai mic necesar stocării. S-au încercat diverse metode de a reduce cei 128 sau 192 de membrii ai vectorilor. O asemenea încercare, mai veche de altfel, este SIFT-PCA, încercare de a reduce dimensionalitatea cu Principal Component Analisys. S-a mai încercat un calcul SIFT la doar jumatate din proces cu 64 de elemente ai vectorilor, fară a afecta foarte mult calitatea de invarianță, dar insuficient pentru a reduce consumul de memorie.

În anul 2007 Yair Weiss studiează modalități de a reduce dimensionalitatea vectorilor și aduce la lumină o metodă și un mecanism extrem de ingenios, numit Spectral Hashing. Preocupat profund de procese neuronale, publică lucrarea sa împreună cu Antonio Torralba si Rob Fergus, intitulată “Spectral Hashing”, în cadrul NIPS ediția 2008. Aceasta este o lucrare foarte elegantă și cu o idee complet originală. Ei demonstrează, în mod mai mult decât fezabil, reducerea în dimensionalitate a unei baze de date cu 80 milioane de vectori, a câte 512 dimensiuni, fără probleme (proiectul LabelMe), proiect ce uimește motoare de căutare populare consacrate pentru imagini: Google sau Yahoo!. Marele secret a lucrării este translatarea metricii vectorilor din spațiu Euclidian în metrici ale spațiului Hamming, care se dovedește a fi un pas extrem de important pentru digestia vectorilor, cu o viteză fără precedent pe un sistem de calcul obișnuit, și de data aceasta cu un consum de memorie care a scăzut dramatic. Practic, problema esențială se rezumă la ce înțelegem la prima vedere prin metrică așa cum o știm de la Euclid și ce este capabil un sistem de calcul sa înțeleagă prin metrică, dar în mod eficient! Autorii iși permit în mod entuziast să afirme în lucrarea lor oficială, chiar în prefață: “Our experiments show that our codes outperform the state-of-the art“.

Experimente anterioare au mai existat ca de altfel și LSH, sau chiar ANN și FLANN menționate anterior sunt neperformante, deoarece sunt concepute să opereze doar în metrică Euclidiană dovedită acum a fi costisitoare pe un sistem de calcul.

Cristoph Strecha, Laussane, Elveția, în lucrarea întitulată LDAHash: Improved matching with smaller descriptors reușește sa reducă dimensionalitatea vectorilor SIFT și DAISY foarte elegant în spațiul Hamming, inspirat de Y. Weiss și ajustează astfel performanțele metodei dense ce utilizează “depth-map”, mergând doar pe linia “Profundă“. El reușește să facă complet utilizabilă ideea de a calcula descriptori locali pentru absolut toți pixelii și demonstrează fezabilitatea “depth-map” chiar și pentru imagini de rezoluție foarte înalta de 80Mpix, în scopuri dedicate special fotogrametriei și teledetecției. Lucrarea este întitulată “Efficient Large Scale Multi-View Stereo for Ultra High Resolution Image Sets” în care cei de la Laussane incluzând Engin Tola și Pascal Fua descriu întregul proces.

Distanța Hamming

Figura 10. Distanțe în spațiul Hamming.

Spațiul Hamming (Figura 10) este compus din două posibile valori: 1 și 0. Este un spațiu al valorilor binare unde distanța dintre două numere se calculeză cu o operatie logică XOR (sau exclusiv) între cele două valori binare, urmată de o numărătoare a populației de 1 în rezultatul obținut, numit POPCNT “population count”. Valoarea populației stărilor 1 reflectă logic distanța dintre cele două valori inițiale. Spre exemplu, dacă populația nu conține nici un 1 binar, atunci valorile inițiale coincid, deoarece XOR anulează valorile identice între ele. Un CPU oarecare de pe sistemele moderne de calcul poate digera aceste două operații în mod nativ, la o viteză numită “full pipeline speed” (direct pe linia de asamblare internă). Este evident că operațiile Euclidiene obișnuite de adunare, multiplicare sau diviziune, reprezintă o povară imensă pentru un CPU în față cu operațiile logice din spațiul Hamming. În plus, imaginați-vă că acești vectori exprimați în spațiul Hamming necesită considerabil mult mai puțină memorie de sistem.

Un nou orizont: BRISK

BRISK sau “Binary Robust Invariant Scalable Keypoints” este un nou descriptor conceput direct în spațiul Hamming. Prezentat de către Stefan Leutenegger, Margarita Chli și Roland Siegwart de la ETHZ Zuerich, Elveția, în cadrul ICCV ediția 2011, reprezintă “descriptorul“ care evoluează natural din performanțele și aspectele DAISY, respectiv cunoștințele și avantajele spațiului Hamming. Superioritatea acestui descriptor este evidentă, el corectează neajunsurile toturor descriptorilor din care a evoluat. Greu de imaginat dacă este posibilă o îmbunătățire a acestui prototip avansat, dar cu siguranță deține potențialul să redefinească sau să simplifice toate aplicațiile enumerate în acest articol. BRISK este și el public iar implementarea este licențiată GPLv3. Librăria înglobează în plus pașii de “key matching” sau corelare a vectorilor în spațiul Hamming, respectiv oferă niște subvariante optimizate pentru arhitecturile moderne de calcul, profită din plin de instrucțiunile vector disponibile pe arhitecturile Intel SSE2, SSE3 și SSE4.