Aplicarea metodelor de flux optic pentru estimarea deplasării imaginilor. Construcția fluxului optic Articolul fluxuri turbionare metode optice

Imaginile cu luminozitate se deplasează împreună cu obiectele observate. Fluxul optic este mișcarea aparentă a unei imagini cu luminozitate. În mod ideal, fluxul optic corespunde câmpului de mișcare, dar vom arăta mai jos că nu este întotdeauna cazul.

Orez. 12.2. Fluxul optic care nu coincide întotdeauna cu câmpul de mișcare. a - o sferă netedă se rotește sub iluminare constantă - imaginea nu se schimbă, deși câmpul de mișcare este diferit de zero; b - o sferă staționară este iluminată de o sursă în mișcare - distribuția de iluminare a imaginii se modifică, deși câmpul de mișcare este zero.

Să considerăm o sferă ideal omogenă care se rotește în fața lentilei sistemului vizual (Fig. 12.2, a). Deoarece suprafața este curbată, în imaginea sferei se vor observa variații spațiale ale luminozității. Cu toate acestea, acest model de luminozitate nu se mișcă cu suprafața și imaginea nu se modifică în timp. În acest caz, fluxul optic este zero peste tot, deși câmpul de mișcare este diferit de zero. Acum luați în considerare o sferă staționară iluminată de o sursă de lumină în mișcare (Fig. 12.2, b). Luminozitatea imaginii se modifică odată cu mișcarea sursei. În acest caz, fluxul optic este în mod evident diferit de zero, deși câmpul de mișcare este zero peste tot. Reflexiile speculare și umbrele oferă alte exemple în care fluxul optic nu coincide cu câmpul de mișcare.

Avem acces doar la fluxul optic și vom presupune că, în cazul normal, fluxul optic nu este foarte diferit de câmpul de mișcare. Acest lucru ne permite să estimăm mișcarea relativă pe baza modului în care imaginea se schimbă în timp.

Ce înțelegem prin mișcarea aparentă a unui model de luminozitate? Să considerăm un punct P pe imagine care are luminozitatea E în acest moment (Fig. 12.3). Care punct P al imaginii îi va corespunde în acest moment, cu alte cuvinte, cum se mișcă imaginea de luminozitate în acest interval de timp? De obicei, în vecinătatea punctului P sunt multe

puncte cu aceeași luminozitate E. Dacă în partea din imagine ne interesează luminozitatea se modifică continuu, atunci punctul P se va așeza pe o linie de luminozitate egală C. În momentul de față va corespunde unei linii de luminozitate egală C cu aceeași valoare E. Care este însă corespondența dintre punctele dreptelor C și CU? La această întrebare nu este ușor de răspuns, deoarece forma acestei linii se schimbă de obicei atunci când se mișcă.

Astfel, observăm că fluxul optic într-o imagine în schimbare este determinat în mod ambiguu de informațiile locale. Să ilustrăm acest lucru cu un alt exemplu. Să luăm în considerare o regiune de luminozitate uniformă din imagine care nu se schimbă în timp. „Cel mai plauzibil” în acest caz ar fi fluxul optic zero. De fapt, în interiorul unui punct omogen putem atribui punctelor orice viteză dorim. Deși, aparent, am prefera cea mai simplă explicație pentru modificările de imagine observate (în acest caz, absența unor astfel de modificări).

Să fie iluminarea într-un punct al imaginii la timp. Atunci, dacă și componentele y ale vectorului de flux optic în acest punct, ne putem aștepta ca iluminarea să fie aceeași în momentul în care, cu alte cuvinte, pentru un interval de timp mic. Această limitare unică nu este suficientă pentru determinați cele două necunoscute și și V. De asemenea, este clar că am dori să profităm de faptul că câmpul de mișcare este aproape peste tot continuu.

Dacă luminozitatea variază ușor și atunci putem extinde partea stângă a ecuației într-o serie Taylor și de aici obținem

unde în conţine termeni de ordine superioare de micime pornind de la

Orez. 12.3. Mișcarea aparentă a modelului de luminozitate.

Nu este ușor să decideți care punct P de pe linia de nivel de luminozitate C a celei de-a doua imagini corespunde unui punct dat P pe linia de nivel de luminozitate C a primei imagini.

Orez. 12.4. Informații locale despre gradientul de luminozitate și viteza de schimbare a acestuia în timp, impunând o singură limitare componentelor vectorului de flux optic. Este necesar ca viteza curgerii să fie direcționată de-a lungul unei linii drepte perpendiculară pe direcția gradientului de luminozitate. Putem determina doar componenta direcționată de-a lungul gradientului de luminozitate.Nu se știe nimic despre componenta vitezei curgerii în direcția perpendiculară.

din a doua. Să reducem, să împărțim cu și să mergem la limită la Apoi obținem

Fluxul optic este o tehnologie utilizată în diferite domenii ale vederii computerizate pentru a determina schimbările, segmentarea, selecția obiectelor și compresia video. Cu toate acestea, dacă dorim să o implementăm rapid în proiectul nostru, după ce am citit despre el pe Wikipedia sau în altă parte, atunci, cel mai probabil, ne vom împiedica foarte repede de faptul că funcționează foarte prost și nu reușește la determinarea schimbărilor de ordinul 1-2 pixeli (cel puțin așa a fost cazul pentru mine). Apoi să ne întoarcem la implementări gata făcute, de exemplu, în OpenCV. Acolo este implementat folosind diverse metode și este complet neclar de ce abrevierea PyrLK este mai bună sau mai proastă decât denumirea Farneback sau ceva de genul acesta și va trebui să vă dați seama de semnificația parametrilor, dintre care există o mulțime în unele. implementari. Mai mult, ceea ce este interesant este că acești algoritmi funcționează cumva, spre deosebire de ceea ce am scris noi înșine. Care este secretul?

Ce este fluxul optic

Fluxul optic (OP) este o imagine a mișcării aparente care reprezintă deplasarea fiecărui punct între două imagini. În esență, reprezintă un câmp de viteză (deoarece deplasarea, până la scară, este echivalentă cu viteza instantanee). Esența OP este că pentru fiecare punct din imagine se găsește o deplasare (dx, dy) astfel încât punctul de pe a doua imagine să corespundă punctului original. Cum se determină corespondența punctelor este o întrebare separată. Pentru a face acest lucru, trebuie să luați un fel de funcție punct care nu se schimbă ca urmare a deplasării. De obicei se consideră că un punct își păstrează intensitatea (adică luminozitatea sau culoarea pentru imagini color), dar punctele care păstrează magnitudinea gradientului, Hessianul, mărimea sau determinantul său, Laplacianul și alte caracteristici pot fi considerate identice. . Evident, menținerea intensității eșuează dacă se modifică iluminarea sau unghiul de incidență al luminii. Totuși, dacă vorbim de un stream video, atunci, cel mai probabil, iluminarea nu se va schimba prea mult între două cadre, fie doar pentru că între ele trece o scurtă perioadă de timp. Prin urmare, intensitatea este adesea folosită ca o funcție care este conservată într-un punct.

Pe baza acestei descrieri, se poate confunda OP cu căutarea și compararea punctelor caracteristice. Dar acestea sunt lucruri diferite, esența fluxului optic este că nu caută puncte speciale, ci, pe baza parametrilor imaginii, încearcă să determine unde s-a deplasat un punct arbitrar.

Există două opțiuni pentru calcularea fluxului optic: dens (dens) și selectiv (rar). Fluxul Sparse calculează deplasarea punctelor individuale date (de exemplu, punctele selectate de un detector de caracteristici), fluxul dens calculează deplasarea tuturor punctelor de imagine. Desigur, fluxul selectiv este calculat mai rapid, dar pentru unii algoritmi diferența nu este atât de mare, iar pentru unele sarcini este necesar să găsiți fluxul în toate punctele imaginii.

Pentru cazurile degenerate, se pot folosi metode mai simple de determinare a deplasării. În special, dacă toate punctele imaginii au aceeași deplasare (întreaga imagine este deplasată), atunci se poate aplica metoda corelației de fază: calculați transformata Fourier pentru ambele imagini, găsiți convoluția fazelor lor și utilizați-o pentru a determina deplasarea ( vezi en.wikipedia.org /wiki/Phase_corelation). De asemenea, puteți utiliza potrivirea blocurilor: găsiți deplasarea care minimizează norma diferenței dintre imagini din fereastră. În forma sa pură, un astfel de algoritm va funcționa mult timp și este instabil la rotații și alte distorsiuni. Wikipedia în limba engleză listează algoritmii enumerați ca diverse opțiuni pentru calcularea fluxului optic, dar acest lucru nu mi se pare foarte corect, deoarece acești algoritmi pot fi utilizați în alte scopuri și nu rezolvă complet această problemă. Vom numi metode bazate pe caracteristicile locale ale fluxului optic de imagini (ceea ce se numește metode diferențiale în Wikipedia în engleză).

Abordare standard (metoda Lucas-Kanade)

O descriere matematică a algoritmului este oferită suficient de detaliat în acest articol, dar atinge doar aspecte teoretice.

Să luăm în considerare un model matematic al fluxului optic, presupunând că intensitatea punctului nu s-a modificat ca urmare a deplasării.

Lăsa – intensitatea la un moment dat (x, y) în prima imagine (adică la momentul t). În a doua imagine, acest punct s-a deplasat cu (dx, dy), în timp ce timpul dt a trecut, apoi avem Taylor extins funcția de intensitate la primul termen (mai târziu se va menționa de ce numai la primul), aici sunt derivate parțiale în ceea ce privește coordonatele și timpul, adică, în esență, o schimbare a luminozității în punctul (x, y) între două cadre.

Credem că punctul și-a păstrat intensitatea, ceea ce înseamnă
Obținem o ecuație cu două necunoscute (dx și dy), ceea ce înseamnă că nu este suficient de rezolvat, adică nu vei ajunge departe doar cu această ecuație.

Cea mai simplă soluție la problemă este algoritmul Lucas-Kanade. În imaginea noastră, avem obiecte mai mari de 1 pixel, ceea ce înseamnă că, cel mai probabil, în vecinătatea punctului curent, alte puncte vor avea aproximativ aceleași deplasări. Prin urmare, luăm o fereastră în jurul acestui punct și minimizăm (prin metoda celor mai mici pătrate) eroarea totală din acesta cu coeficienți de ponderare distribuiți conform gaussian, adică astfel încât pixelii cei mai apropiați de cel studiat să aibă cea mai mare greutate. După cele mai simple transformări, obținem un sistem de 2 ecuații cu 2 necunoscute:

După cum se știe, acest sistem nu are întotdeauna o soluție unică (deși foarte des): dacă determinantul sistemului este egal cu zero, atunci fie nu există soluții, fie un număr infinit. Această problemă este cunoscută ca problema Aperture - ambiguitatea deplasării cu un câmp vizual limitat pentru imagini periodice. Ea corespunde cazului în care iese la vedere un fragment dintr-o imagine, în care există o oarecare ciclicitate; aici nici măcar o persoană nu va putea determina fără ambiguitate unde s-a deplasat imaginea. Problema este că, din cauza zgomotului în astfel de situații ambigue, nu vom obține un determinant zero, ci unul foarte mic, ceea ce va duce cel mai probabil la valori de schimbare foarte mari care nu sunt corelate în mod deosebit cu realitatea. Deci, la o anumită etapă, trebuie doar să verificați dacă determinantul sistemului este suficient de mic și, dacă da, să nu luați în considerare astfel de puncte sau să le marcați ca eronate.

De ce nu merge?

Dacă ne oprim în această etapă și implementăm acest algoritm, acesta va funcționa cu succes. Dar numai dacă deplasarea între imaginile adiacente este foarte mică, de ordinul a 1 pixel, și chiar și atunci nu întotdeauna. (Pentru a analiza calitatea, s-au generat secvențe sintetice cu diferite deplasări relative, iar această deplasare poate fi exprimată printr-un număr neîntreg de pixeli, apoi imaginea rezultată este interpolată corespunzător) Deja la o deplasare de 2 pixeli eroarea va fi mare , iar dacă 3 sau mai multe, atunci rezultatul va fi în general inadecvat. Ce s-a întâmplat?

Aici matematica ne-a pus la punct. Ea ne-a insuflat sentimentul că toate funcțiile din jurul nostru sunt continue și de multe ori diferențiabile. Și, în general, la institut am fost învățați să scriem aproximarea unei funcții în vecinătatea unui punct folosind formula Taylor și o folosim fără gânduri și bucurie peste tot. Acum să ne gândim la semnificația fizică a derivatelor în acest loc? Vrem să le folosim pentru a determina modificarea valorii unei funcții într-o vecinătate finită a unui punct, iar derivata dă o idee despre o vecinătate infinitezimală. Pentru a extinde această vecinătate, ar fi posibil să se adauge un ordin superior al derivatelor expansiunii Taylor, dar acest lucru va duce la neliniarități în sistem, ceea ce va face mult mai dificil de rezolvat, iar avantajele vor fi discutabile, mai ales că în practică, nu avem de-a face cu funcții diferențiabile multiple continue, ci cu funcții discrete în general neclare. Prin urmare, ar fi mai logic să căutăm o funcție g(x), pentru care în cazul nostru discret f(x) + g(x) = f(x+1), f(x) + 2g(x) = f(x) este satisfăcută cât mai precis posibil +2), f(x) - g(x) = f(x-1), etc. Astfel, în acest caz nu avem nevoie de o derivată, ci de o funcție liniară care este cel mai apropiat de punctele funcției inițiale. Calculele matematice simple duc la o soluție , Unde . Dacă am construit derivata folosind câte un punct adiacent de fiecare parte, atunci am avut noroc: în acest caz formula coincide cu formula de calcul aproximativ al derivatelor: g(x) = (f(x+1) – f(x-). 1)) / 2. De obicei, în OpenCV, când se calculează fluxul optic Lucas-Kanade, se folosește exact această formulă, vom reveni la aceasta mai târziu. Dar dacă luați mai multe puncte, atunci formula devine complet diferită de schemele clasice de diferență pentru prima derivată.

Evident, dacă construim această funcție, de exemplu, folosind trei puncte învecinate la stânga și la dreapta celui original, atunci nu depinde în niciun fel de punctele situate mai departe și, în consecință, dacă deplasăm mai mult de trei puncte, vom obține în continuare rezultate inadecvate. Și, de asemenea, cu cât este mai mare numărul de puncte din care construim această funcție, cu atât este mai mare abaterea medie a dreptei rezultate de la punctele folosite - din nou datorită faptului că nu avem imagini care variază liniar, dar cine știe ce fel. În practică, deplasările de peste 2 pixeli produc deja o eroare necorespunzător de mare, indiferent de câte puncte luăm.

Un alt punct slab al algoritmului este că, din nou, nu avem de-a face cu funcții continue netede, ci cu unele arbitrare și chiar discrete. Prin urmare, în unele fragmente de imagine, intensitatea poate „sări” fără niciun model evident, de exemplu la granițele obiectelor sau din cauza zgomotului. În acest caz, nicio funcție g(x) nu poate descrie suficient de precis modificările imaginii din vecinătatea punctului. Pentru a combate acest lucru (cel puțin parțial), se propune să se undă imaginea originală și va fi util să o întindă destul de puternic, adică este mai bine să se folosească nici măcar neclaritatea gaussiană preferată a tuturor (medie cu coeficienți de ponderare), ci doar un filtru cutie (medie uniformă peste fereastră) și de mai multe ori la rând. Netezimea imaginii este acum mai importantă pentru noi decât detaliile.

Cu toate acestea, aceste măsuri nu ne vor scuti de limitarea deplasării detectate la 2-3 pixeli. Și apropo, în OpenCV 1.0 a existat o astfel de implementare a fluxului optic și a funcționat doar în condiții ideale și la ture foarte mici.

Ce să fac?

În rezumat, Lucas-Kanade obișnuit este bun la identificarea micilor deplasări, astfel încât imaginea să fie similară cu aproximarea sa liniară. Pentru a combate acest lucru, vom folosi tehnica standard CV - multi-scalare: vom construi o „piramidă” de imagini de diferite scări (aproape întotdeauna scala de 2 ori de-a lungul fiecărei axe, este mai ușor de calculat) și le vom parcurge. cu un flux optic de la o imagine mai mică la una mai mare, atunci micul deplasare detectată într-o imagine mică va corespunde unei deplasări mari într-o imagine mare. Pe cea mai mică imagine detectăm o deplasare de cel mult 1-2 pixeli, iar trecând de la o scară mai mică la una mai mare, folosim rezultatul de la pasul anterior și rafinăm valorile deplasării.De fapt, în OpenCV este implementat de funcția calcOptFlowPyrLK.Folosirea acestui algoritm piramidal ne permite să nu ne deranjam cu calcularea unui liniar aproximare pe mai multe puncte: este mai ușor să luăm mai multe niveluri ale piramidei, iar la fiecare nivel să luăm o aproximare destul de grosieră a acestei funcție.De aceea, în OpenCV calculăm folosind doar două puncte învecinate.Și, prin urmare, în raport cu această implementare a la algoritm, concluziile noastre despre avantajul funcției de aproximare față de derivată s-au dovedit a fi inutile: pentru un astfel de număr de puncte de referință, derivata este cea mai bună funcție de aproximare.

Ce altele mai sunt?

Acest algoritm nu este singura opțiune pentru calcularea fluxului optic. În OpenCV, pe lângă fluxul Lucas-Kanade, există și un flux Farneback și SimpleFlow, iar algoritmul Horn-Schunck este adesea menționat.

Metodă Horn–Schunck este ceva mai globală ca natură decât metoda Lucas-Kanade. Se bazează pe presupunerea că fluxul optic va fi destul de neted pe întreaga imagine. Din aceeași ecuație se propune trecerea la cea funcțională, adică adăugarea cerinței pentru absența unei schimbări bruște a deplasărilor cu un coeficient de ponderare α. Minimizarea acestei funcționale ne conduce la un sistem de două ecuații:

În aceste ecuaţii, laplacianul se propune să fie calculat aproximativ: – diferenţă cu valoarea medie. Obținem un sistem de ecuații, pe care îl scriem pentru fiecare pixel și rezolvăm întregul sistem în mod iterativ:

În acest algoritm, ei sugerează, de asemenea, utilizarea multi-scalării și recomandă scalarea imaginilor nu de 2 ori, ci cu un factor de 0,65

Acest algoritm a fost implementat în primele versiuni ale OpenCV, dar ulterior a fost abandonat.

Farneback a propus aproximarea variației de intensitate în vecinătate folosind o formă pătratică: I = xAx + bx + c cu o matrice simetrică A (de fapt, luând în considerare expansiunea Taylor la primul termen, am luat aproximarea liniară I = bx + c , adică acum ne-am hotărât să creștem acuratețea aproximării) Dacă imaginea s-a mutat în această vecinătate, atunci, înlocuim în expansiunea pătratică, deschidem parantezele, obținem


.

Acum putem calcula valorile lui A, b, c în ambele imagini, iar apoi acest sistem va deveni redundant în raport cu d (prima ecuație este deosebit de confuză) și, în general, d poate fi obținut din a doua ecuație: . Trebuie să recurgem la următoarea aproximare: . Să notăm și pentru simplitate , Atunci obținem pur și simplu.

Pentru a compensa zgomotul în timpul calculelor, ne întoarcem din nou la ipoteza că în vecinătatea punctului studiat, toate punctele au mai mult sau mai puțin aceeași deplasare. Prin urmare, integrăm din nou eroarea peste fereastră cu coeficienți de ponderare gaussieni w, și găsiți vectorul d care minimizează această eroare totală. Apoi vom obține valoarea optimă și eroarea minimă corespunzătoare. Adică, trebuie să calculăm pentru fiecare punct, media peste fereastră, să inversăm matricea și să obținem rezultatul. În consecință, aceste produse pot fi calculate pentru întreaga imagine și pot fi utilizate valori precalculate pentru diferite puncte, adică acesta este exact cazul când are sens să se calculeze un flux dens.

Ca de obicei, acest algoritm are o serie de modificări și îmbunătățiri, permițând în primul rând utilizarea informațiilor cunoscute a priori - o aproximare inițială dată a fluxului - și, din nou, multi-scalare.

Baza metodei SimpleFlow constă următoarea idee: dacă încă nu știm cum să determinăm o deplasare mai mare decât dimensiunea ferestrei peste care am căutat derivate, atunci de ce să ne deranjez măcar cu calcularea derivatelor? Să găsim doar punctul cel mai asemănător din fereastră! Iar pentru a rezolva ambiguitățile și a compensa zgomotul, luăm în considerare faptul că fluxul este continuu și în vecinătatea unui punct dat toate punctele au aproape aceeași deplasare. Și vom rezolva din nou problema cu dimensiunea ferestrei prin scalare multiplă.

Mai strict, algoritmul sună astfel: pentru toate punctele din fereastră există o funcție „energie” care este responsabilă (cu o dependență logaritmică inversă) pentru probabilitatea ca punctul inițial să treacă în acest punct: . În continuare, se ia în considerare convoluția acestei energii cu o fereastră Gaussiană și se găsesc valorile (dx,dy) care minimizează această funcție. Pentru a obține acuratețea sub-pixelului, se ia în considerare o mică vecinătate a punctului optim găsit (dx,dy) și se caută vârful funcției de energie în el ca vârful unui paraboloid. Și, după cum am menționat mai sus, această procedură este efectuată pe o piramidă de imagini la scară. Algoritmul lor oferă și metode inteligente pentru accelerarea calculelor, dar cei interesați își vor da seama singuri. Ceea ce este important pentru noi este că datorită acestui lucru, acest algoritm este (teoretic) destul de rapid și cu o precizie bună. Și nu are aceeași problemă ca cele anterioare, că cu cât este mai mare schimbarea, cu atât este mai rău detectat.

Dacă nu luăm intensitate?

S-a spus mai sus că corespondența dintre puncte poate fi determinată de cantități diferite, deci de ce luăm în considerare doar intensitatea? Dar pentru că orice altă valoare poate fi redusă la ea: pur și simplu filtrăm imaginile cu filtrul corespunzător și alimentăm imaginile filtrate la intrarea algoritmilor descriși mai sus. În consecință, dacă doriți să utilizați fluxul optic, atunci gândiți-vă mai întâi la ce caracteristică a imaginii va fi cea mai stabilă în condițiile dvs. și efectuați o filtrare adecvată, astfel încât intrarea algoritmului să nu fie intensitatea, ci această caracteristică.

Practică

Să încercăm în practică algoritmii pe care ni-i oferă OpenCV.

Aici puteți efectua multe studii diferite ale fiecărui algoritm, variați parametrii, schimbați secvențele de intrare - cu diferite deplasări, rotații, transformări proiective, segmente, cu zgomot diferit etc. Toate acestea ar dura mult timp și dimensiunea raportului. ar depăși acest articol, Prin urmare, aici îmi propun să ne limităm la cazul simplu de deplasare paralelă a imaginii cu o distanță fixă ​​și impunerea unui zgomot mic. Acest lucru vă va permite să înțelegeți în termeni generali cum să rulați algoritmi și care dintre ei este mai tare.

Sintaxa procedurilor este descrisă în detaliu pe pagina cu manualul; aici voi oferi o traducere sumar cu comentariile mele.

Clasicul Lucas-Kanade este implementat cu o piramidă în procedura calcOpticalFlowPyrLK. Algoritmul calculează fluxul rar, adică pentru un set dat de puncte din prima imagine, estimează poziția acestora în a doua. Parametrii de intrare sunt destul de evidenti: două imagini de intrare, un set de puncte de intrare și un set de ieșire, stare - un vector de ieșire care indică dacă punctul corespunzător a fost găsit cu succes, err - un vector de ieșire al erorilor estimate ale punctelor corespunzătoare, WinSize - dimensiunea ferestrei peste care are loc media gaussiană, am luat 21x21 și a funcționat bine, maxLevel – numărul de straturi din piramidă minus unu, adică numărul ultimului strat, am luat 5, criterii – condiția de ieșire procesul iterativ de determinare a deplasării (minimizarea erorii se face iterativ) – am lăsat acest parametru în mod implicit, steaguri – steaguri suplimentare, de exemplu, puteți utiliza aproximarea inițială a fluxului sau selectați metoda de estimare a erorii, minEigThreshold – pragul gradientului valoare sub care matricea este considerată singulară, am lăsat-o implicit. Începând cu OpenCV 2.4.1, la calcularea fluxului poate fi utilizată o piramidă precalculată de imagini la scară.

Rezultatul muncii este că atât schimburile mici, cât și cele mari sunt detectate cu succes și stabil, este rezistent la zgomote destul de mari, timpul de funcționare este de aproximativ 10 ms pentru 400 de puncte cu o piramidă cu 5 straturi (pe un nucleu i7 950).

Apropo, acest algoritm este implementat și pe GPU (CUDA), atât versiuni dense, cât și rare.

Fluxul Farneback este implementat prin procedura calcOpticalFlowFarneback, se calculează debitul dens, adică deplasarea fiecărui punct. Parametri: imagini de intrare, flux de ieșire în formatul unei matrice float cu două canale, pyr_scale determină raportul de scară dintre straturile piramidei, niveluri – numărul de niveluri din piramidă, winsize – dimensiunea ferestrei peste care se face media se efectuează, iterații – numărul de iterații la fiecare nivel, poly_n – dimensiunea polinomului prin care sunt estimate valorile lui A și b, poly_sigma – sigma estomparii gaussiene la netezirea derivatelor, valorile parametrilor recomandate sunt indicate în manual, steaguri – steaguri suplimentare, de exemplu, puteți utiliza aproximarea inițială a debitului sau, altfel, media peste fereastră.

Acest algoritm este mult mai puțin stabil (conform observațiilor mele), ratează mai ușor imaginile destul de uniforme (se pare că problema este lipsa de filtrare a punctelor nereușite) și nu detectează bine deplasările mari. La mine a funcționat în 600 ms pe o imagine de 512x512.

Fluxul SimpleFlow implementează procedura calcOpticalFlowSF (din nou, se calculează fluxul dens), și are mulți parametri misterioși fără valori implicite, iar în general, în acest moment informațiile de pe pagină sunt furnizate foarte succint. Să încercăm să ne dăm seama. Primele 3 sunt imagini de intrare și de ieșire pe două canale; straturi – numărul de straturi din piramidă, adică de câte ori scalam imaginea originală; averaging_block_size – dimensiunea ferestrei în care am calculat funcția de energie a pixelilor; max_flow – deplasarea maximă pe care dorim să o putem determina la fiecare pas, în esență este determinată de dimensiunea ferestrei (deși nu este complet clar de ce este int). Te poți opri aici, sau mai poți seta câțiva parametri, sensul unora dintre ei mă scapă.

Site-ul oferă un exemplu de utilizare a acestuia, în care este lansat cu următorii parametri: calcOpticalFlowSF(frame1, frame2, flow, 3, 2, 4, 4.1, 25.5, 18, 55.0, 25.5, 0.35, 18, 55.0, 25.5 , 10);

Algoritmul meu funcționează mult mai lent decât alții, aproximativ 9-12 secunde pe imagine de 512x512. Rezultatul lucrării pare mai plauzibil decât Farneback, cel puțin schimbarea imaginilor uniforme este mai bine determinată și funcționează considerabil mai bine cu schimbări mari.

concluzii

Dacă doriți să utilizați fluxul optic undeva, mai întâi gândiți-vă dacă aveți nevoie de el: adesea vă puteți descurca cu metode mai simple. Angajamentul de a implementa singur un flux merită să te gândești doar de câteva ori: fiecare algoritm are multe trucuri, subtilități și optimizări; Orice ai face, probabil că va funcționa mai bine în OpenCV (presupunând că este acolo, desigur). Mai mult, ele folosesc pe deplin optimizările logice și hardware, cum ar fi utilizarea instrucțiunilor SSE, multithreading, capabilități de calcul cu CUDA sau OpenCL etc. Dacă trebuie doar să calculați deplasarea unui anumit set de puncte (adică flux rar), atunci trebuie să poate utiliza în siguranță funcția calcOpticalFlowPyrLK, funcționează bine, fiabil și destul de rapid. Pentru a calcula debitul dens, este bine să folosiți funcția calcOpticalFlowSF, dar este foarte lent. Dacă performanța este critică, atunci calcOpticalFlowFarneback, dar trebuie totuși să vă asigurați că rezultatele muncii sale vi se potrivesc. Adaugă etichete

Agafonov V.Yu. 1

1 Agafonov Vladislav Yurievich - student absolvent al departamentului de „proiectare asistată de computer și sisteme de proiectare de căutare”, Universitatea Tehnică de Stat din Volgograd,

Volgograd

Adnotare: V Acest articol discută două abordări pentru a găsi decalaje între imagini dintr-un flux video. Prima abordare se bazează pe minimizarea erorii folosind metoda celor mai mici pătrate atunci când se caută deplasarea punctelor cheie din imagine. A doua abordare se bazează pe aproximarea unei regiuni a fiecărui pixel printr-un polinom pătratic, care poate fi bine utilizat în estimarea mișcării. Sunt descrise principalele etape de implementare a metodelor. Au fost pregătite seturi de testare de imagini ținând cont de specificul sarcinii. Sunt prezentate rezultatele acestor teste.

Cuvinte cheie: prelucrarea imaginilor, căutarea deplasării imaginii

APLICAREA METODELOR DE FLUJ OPTICE PENTRU ESTIMAREA DEPOZITĂRII IMAGINII

Agafonov V.U. 1

1 Agafonov Vladislav Urevich - student postuniversitar la departamentul „sisteme de proiectare asistată de computer și proiectare de căutare”,

Universitatea Tehnică de Stat din Volgograd, Volgograd

Abstract: în acest articol sunt descrise metode de estimare a deplasării imaginii. Prima abordare se bazează pe minimizarea erorii pătratice medii la căutarea deplasării punctelor cheie ale imaginii. A doua abordare se bazează pe aproximarea fiecărei vecinătăți a ambelor cadre prin polinoame pătratice, ceea ce poate fi realizat eficient folosind transformarea de expansiune polinomială. Sunt descrise principalele etape ale implementării acestor metode. Seturile de testare de imagini sunt pregătite ținând cont de natura specifică a problemei. Sunt prezentate rezultatele lucrării.

Cuvinte cheie: procesarea imaginilor, estimarea deplasării imaginii

UDC 004.932.2

Introducere

La rezolvarea problemelor de viziune computerizată apare adesea problema estimării mișcării unui obiect în cadre sau a deplasării a două cadre consecutive într-un flux video. Estimarea precisă a parametrilor de mișcare a scenei în cadre este un factor important pentru mulți algoritmi, așa că metodele de detectare a mișcării trebuie să ofere acuratețe sub-pixel.

Există mai multe abordări pentru estimarea deplasării imaginii. Principalele sunt: ​​identificarea caracteristicilor cheie din imagine, urmată de compararea punctelor cheie, determinarea corelației de fază a reprezentării în frecvență a semnalului imaginii și a fluxului optic. Acesta din urmă, în forma sa principală, nu este folosit pentru a căuta deplasări de imagine; este folosit pentru a determina prezența mișcării în imagine. Astfel, fluxul optic este utilizat în sistemele de detectare și urmărire a obiectelor.

Fluxul optic este modelul de mișcare aparentă a obiectelor, suprafețelor sau marginilor unei scene, cauzat de mișcarea relativă a unui observator (ochi sau cameră) față de scenă. Algoritmii bazați pe flux optic, cum ar fi detectarea mișcării, segmentarea obiectelor și codificarea mișcării, utilizează această mișcare a obiectelor, suprafețelor și marginilor.

În această lucrare, sunt luate în considerare două abordări, dintre care una vă permite să obțineți decalaje pentru puncte cheie individuale, iar a doua - pentru fiecare pixel individual.

Flux optic prin metoda Lucas-Kanade

Conceptul de bază al metodei este să presupunem că valorile pixelilor se mișcă de la un cadru la altul fără a se schimba:

Unde. Ignorând termenul rămas, obținem formula pentru aproximarea ????:

unde determină decalajul. În conformitate cu ipoteza făcută, obținem că. Apoi scriem ecuația (4) ca

Se dovedește că suma derivatelor parțiale este zero. Totuși, deoarece avem o singură ecuație și două necunoscute, trebuie să impunem condiții suplimentare. O modalitate obișnuită este de a impune restricții asupra pixelilor din apropiere. Să presupunem că pixelii vecini se mișcă în mod egal. Evident, nu poate exista un offset care să satisfacă toți pixelii, așa că minimizăm eroarea folosind metoda celor mai mici pătrate.

unde este o matrice simetrică, este un vector și este un scalar. Coeficienții sunt calculați folosind cele mai mici pătrate ponderate pentru valorile semnalului dintr-o zonă dată. Funcția de ponderare constă din două componente numite certitudine și aplicabilitate. Certitudinea raportează valoarea unui semnal în funcție de valorile din vecinătate. Aplicabilitatea determină contribuția relativă a punctelor în funcție de poziția lor în cartier. De obicei punctul central are cea mai mare greutate, greutatea punctelor rămase scade pe direcția radială. Deoarece imaginea este extinsă ca un polinom pătratic într-o anumită vecinătate, este necesar să înțelegem cum se comportă polinomul cu o deplasare ideală. Fie un polinom patratic de forma:

Echivalând coeficienții corespunzători ai polinoamelor pătratice avem:

Acest lucru este valabil pentru orice semnal.

Evident, presupunerea că semnalul poate fi reprezentat printr-un singur polinom este destul de nerealistă. Totuși, relația (10) poate fi utilizată pentru semnale reale, chiar dacă apar erori. Întrebarea principală este dacă erorile sunt suficient de mici pentru ca algoritmul să fie util.

Să înlocuim reprezentarea polinomială globală cu una locală. Să calculăm coeficienții polinomii pentru prima imagine și pentru a doua imagine. În conformitate cu (9), ar trebui să fie, dar în practică se utilizează aproximarea:

unde reflectă înlocuirea deplasării globale cu o deplasare variabilă spațial.

În practică, ecuația (11) poate fi rezolvată element cu element, dar rezultatele se dovedesc a fi prea zgomotoase. În schimb, se presupune că regiunea de deplasare se modifică lent, astfel încât să putem integra informații folosind pixeli vecini. Astfel încercăm să găsim, satisfăcător (11) în vecinătate, sau mai formal:

Principala problemă a metodei este presupunerea că polinoamele sunt aceleași, cu excepția offset-ului. Deoarece expansiunea polinomului local a polinomului se va modifica în funcție de mediu, aceasta va introduce o eroare în (11). Pentru deplasări mici acest lucru nu este important, dar pe măsură ce deplasarea crește, eroarea crește. Dacă avem cunoștințe a priori despre părtinire, putem compara două polinoame: primul în, al doilea în, unde aceasta este părtinirea anterioară, rotunjită la o valoare întreagă. Astfel putem executa metoda iterativ. O părtinire anterioară mai bună înseamnă o părtinire relativ mai mică, care, la rândul său, crește șansele unei estimări bune a părtinirii reale.

Aplicarea metodelor de flux optic la problema căutării deplasărilor de imagine

Pentru a testa aceste metode, testarea a fost efectuată pe un set de date artificiale, adică. obţinute folosind un generator de imagini părtinitoare. Pentru a obține o deplasare de subpixeli, zonele cu o ușoară deplasare una față de alta au fost decupate din imaginea originală. După aceasta, imaginile de test rezultate au fost comprimate de mai multe ori; în consecință, unele dintre informațiile de pe ele au dispărut, iar deplasarea a fost redusă la subpixel.

Pentru metoda Lucas-Kanade, este necesar să se selecteze multe puncte cheie a căror deplasare trebuie găsită. În acest scop, se folosește metoda clasică de căutare a limitelor și a colțurilor. După obținerea deplasării fiecăruia dintre aceste puncte, este necesară medierea rezultatului rezultat.

Pentru metoda Farneback, este suficient să mediați valorile deplasării în fiecare pixel.

Experimentul a fost efectuat pe un eșantion de 20 de perechi de teste și a fost calculată abaterea standard pentru fiecare metodă.

OP Lucas-Canada
OP Farnebaca

Tabelul 1 - Abaterea standard a deplasărilor

Din rezultatele experimentale se poate observa că ambele metode estimează deplasarea imaginilor cu o precizie ridicată. Rezultatul metodei lui Farneback arată un rezultat mai slab datorită faptului că metoda estimează deplasarea pentru toți pixelii și poate face erori pe părțile monocromatice ale imaginii.

Fiecare metodă are propriile sale avantaje și dezavantaje, precum și domeniul de aplicare și limitări. Metoda Lucas-Kanade implementează un flux optic rar și

poate atinge o precizie sub-pixel. Dar cu mișcarea non-plan-paralelă, apare o altă problemă, cum se estimează deplasarea punctelor care nu sunt cheie. Prima soluție este de a construi o diagramă Voronoi pentru planul imaginii cu puncte cheie date. Această abordare se bazează pe presupunerea că zonele situate în apropierea punctelor cheie se deplasează în același mod ca punctele cheie. În general, acest lucru nu este întotdeauna adevărat. În practică, punctele cheie sunt în mare parte zone cu schimbări bruște de gradient, ceea ce înseamnă că punctele cheie vor fi concentrate în mare parte pe obiecte detaliate. Prin urmare, deplasarea zonelor de culoare solidă va avea o eroare mare. A doua soluție este găsirea omografiei a două imagini. Această soluție suferă și de estimarea inexactă a deplasării la marginile imaginii.

Avantajul metodei de flux optic Farneback este că deplasarea se găsește pentru fiecare pixel. Cu toate acestea, această metodă face greșeli și asupra obiectelor periodice și slab texturate, dar ne permite să evaluăm mișcarea non-plan-paralelă.

Concluzie

Acest articol a discutat despre o abordare pentru estimarea deplasării imaginii bazată pe metode de flux optic. Aplicabilitatea metodelor este dovedită și sunt prezentate rezultatele unei analize comparative. Studiile experimentale ale metodelor au arătat că această abordare este foarte precisă și poate fi utilizată pentru a estima parametrii de mișcare a scenei.

Bibliografie/ Referințe

1. Fleet D., Weiss Y. Optical flow estimation //Handbook of mathematical models in computer vision. - Springer US, 2006. - p. 237-257.
2. Farnebäck G. Estimarea mișcării în două cadre bazată pe expansiunea polinomială //Analiza imaginii. - 2003. - P. 363-370.

Aceasta este reprezentarea urmei vizibile de mișcare a obiectelor, suprafețelor și marginilor unei scene vizuale, observată atunci când există o mișcare relativă între observator (cum ar fi un ochi uman sau o cameră) și scenă.

Conceptul de flux optic a fost propus de psihologul american James J. Gibson în anii 1940 pentru a descrie stimulul vizual (semnalul) care apare la animalele care se mișcă în spațiu în raport cu mediul lor.

James Gibson a subliniat importanța fluxului optic pentru capacitatea de a percepe, capacitatea de a discerne constrângerile și oportunitățile de acțiune în mediu. Adepții robotului lui Gibson și abordarea sa ecologică a psihologiei au putut, ulterior, să arate rolul stimulului fluxului optic în percepția mișcării observatorului în raport cu lumea înconjurătoare; percepția formei, distanței și mișcării obiectelor din jur; și controlul mișcării.

Recent, termenul de flux optic a fost cooptat de robotică pentru a include tehnici relevante pentru procesarea imaginilor și controlul navigației, cum ar fi detectarea mișcării, segmentarea obiectelor, informații de contact în timp, calcule de extindere a focalizării, luminanță, codare compensată cu mișcare și stereo. măsurători de disparitate.

Recent, termenul de flux optic a fost cooptat de robotiști pentru a include tehnici relevante pentru procesarea imaginilor și controlul navigației, cum ar fi detectarea mișcării, segmentarea obiectelor, informații despre timpul până la contact, concentrarea calculului expansiunii, luminanța, codarea compensată cu mișcare și măsurători ale disparității stereo.

Calcul

O secvență de imagini ordonate permite estimarea mișcării, fie ca viteze instantanee ale imaginii, fie ca valori discrete ale deplasării imaginii. Există materiale sub forma unei lecții despre metoda fluxului optic bazată pe gradienți. Cercetătorii au efectuat, de asemenea, o analiză comparativă a diferitelor tehnici de flux optic, analizând acuratețea și frecvența măsurătorilor.

Metodele optice de calcul al mișcării încearcă să estimeze mișcarea dintre două cadre de imagine văzute la momente în timp t iar la fiecare pozitie voxel. Astfel de metode sunt numite diferențiale deoarece se bazează pe estimări locale ale seriei Taylor pentru semnalul imaginii, adică folosesc derivate parțiale în raport cu coordonatele spațiale și temporale.

Pentru cazul dimensiunii 2D+ t(la fel pentru 3D sau n-D cazuri) locația unui voxel cu intensitate care se va deplasa mai departe și între două cadre de imagine și cu constrângere ulterioară constanța luminozității constrângere de constanță) se poate scrie:

Presupunând că mișcarea a fost nesemnificativă, calculând aproximarea imaginii folosind seria Taylor, se poate obține:

… (Membri de ordin superior)

Din aceste ecuații rezultă că:

rezultând

unde acestea sunt componentele și viteza sau fluxul optic și, și sunt derivate pentru imagine în direcțiile corespunzătoare. Și mai departe poate fi scris pentru derivate.

Prin urmare:

Această ecuație cu două necunoscute nu poate fi rezolvată ca atare. Aceasta este cunoscută ca problema de deschidere (diafragmă). algoritm de flux optic. Pentru a calcula fluxul optic, este necesar un set diferit de ecuații, specificat de unele condiții suplimentare. Toate metodele de calcul al fluxului optic introduc condiții suplimentare pentru estimarea debitului real.

Senzor optic de debit

Un senzor de flux optic este un senzor de viziune capabil să măsoare fluxul optic sau mișcarea vizuală și să producă un rezultat de măsurare bazat pe fluxul optic. Există multe configurații diferite ale unor astfel de senzori. Acesta poate fi un senzor de imagine conectat la un procesor pe care este programat algoritmul de flux optic. O altă configurație folosește un cip de viziune proiectat ca un circuit integrat care conține atât senzorul, cât și procesorul pe un singur cip într-un dispozitiv compact. Un exemplu în acest sens este senzorul de mouse optic convențional utilizat la șoarecii optici. În unele cazuri, circuitele de calcul care utilizează circuite analogice cu semnal mixt pot fi utilizate pentru a calcula rapid fluxul optic cu un consum minim de curent.

Un domeniu al cercetării actuale este utilizarea tehnicilor de inginerie neuromorfă pentru a implementa circuite care simt fluxul optic și, astfel, pot fi utilizate ca senzor optic. Astfel de circuite preiau idei din rețelele neuronale biologice și detectează fluxul optic folosind un principiu similar.

Imagini înrudite

Fluxul optic este o imagine a mișcării aparente a obiectelor, suprafețelor sau marginilor unei scene care rezultă din mișcarea observatorului (ochiul sau camera) în raport cu scena. Algoritmii bazați pe flux optic, cum ar fi detectarea mișcării, segmentarea obiectelor, codificarea mișcării și calculul disparităților stereo, exploatează această mișcare a obiectelor, suprafețelor și marginilor.

Estimarea fluxului optic

Metodele bazate pe flux optic calculează mișcarea dintre două cadre luate la un moment dat în timp și la fiecare pixel. Aceste metode se numesc diferențiale deoarece se bazează pe aproximarea semnalului segmentului din seria Taylor; astfel, folosesc derivate parțiale în ceea ce privește timpul și coordonatele spațiale.

În cazul dimensiunii 2D+ t(cazurile de dimensiuni mai mari sunt similare) un pixel într-o poziție cu intensitate într-un cadru va fi mutat în și, și se poate scrie următoarea ecuație:

Presupunând că deplasarea este mică și folosind seria Taylor, obținem:

Din aceste egalități rezultă:

de aici rezultă că

Componentele vitezei de curgere optice în ,

Imagini derivate în direcțiile corespunzătoare.

Prin urmare:

Ecuația rezultată conține două necunoscute și nu poate fi rezolvată în mod unic. Aceasta este cunoscută sub numele de problema deschiderii. Problema se rezolvă prin impunerea unor restricții suplimentare – regularizarea.

Metode de determinare a fluxului optic:

Corelația de fază este inversarea spectrului încrucișat normalizat.

Metode bloc - minimizarea sumei pătratelor sau a sumei modulelor diferențelor

Metode diferențiale pentru estimarea fluxului optic pe baza derivatelor parțiale ale semnalului:

Algoritmul lui Lucas - Kanade - sunt luate în considerare părți ale imaginii și modelul afin de mișcare

Horn–Schunck - minimizarea unei funcționale care descrie abaterea de la presupunerea de luminozitate constantă și netezimea câmpului vectorial rezultat.

Buxton–Buxton - bazat pe un model al mișcării granițelor obiectelor într-o secvență de imagini

Metodele variaționale generale sunt modificări ale metodei Horn-Schunck care utilizează diferite constrângeri de date și diferite constrângeri de netezime.

Metode de optimizare discrete - spațiul de căutare este cuantificat, apoi fiecărui pixel al imaginii i se atribuie o etichetă astfel încât distanța dintre cadrele succesive să fie minimă. Soluția optimă este adesea găsită folosind algoritmi pentru găsirea tăieturii minime și a debitului maxim într-un grafic, programare liniară sau propagare a credinței.

Urmărirea fluxului optic este adesea folosită cu camere fixe, cum ar fi camerele din aeroporturi sau clădiri, sau camerele de bord fixe.

În această lucrare, a fost utilizată o metodă folosind algoritmul Lucas-Kanade (Fig. 4-6)

Orez. 4 Fereastra principală a modelului

Orez. 5 blocuri model

Orez. 6 Rezultatul modelului

Acest model folosește o metodă de estimare a fluxului optic pentru a determina vectorii de mișcare din fiecare cadru al unui fișier video. Prin constrângerea și aproximarea morfologică a vectorilor de mișcare, modelul creează imagini de caracteristici binare. Modelul găsește o mașină în fiecare imagine binară prin blocul „Analiza blob”. Blocul Draw Shapes desenează apoi un dreptunghi verde în jurul mașinilor care trec prin linia albă.

Dezavantajul acestei metode este că camera trebuie să fie staționară, altfel rezultatul recunoașterii și urmăririi devine imprevizibil.