Identificarea Obiectivelor Circulare Intr O Captura Video Live Si Prelucrarea Datelor Obtinute

Capitolul 1 Introducere

1.1 Motivație

Identificarea traiectoriei obiectelor circulare în imagini video are o puternică influență asupra variație aplicațiilor în domeniul analizei de imagini video: supraveghere video, industrie mecanică, industrie medicală și multe altele.

Pentru identificarea traiectoriei în imagini video avem nevoie inițial de indentificarea în cadru a obiectului țintă după care compararea acestuia cu cadrele anterioare astfel încât să distingem la final traiectoria pe care a avut-o obiectul țintă. Pentru acest lucru trebuie aplicată fiecărui cadru de imagine, o procesare amănunțită în felul acesta indentificandu-se cu o precizie crescută obiectele țintă și prelucrându-se cu o oarecare ușurință datele despre acestea.

Aplicațiile practice care implică detecția și procesarea de imagini, respectiv cadre video au fost o bună motivație pentru mine să pun în aplicare o aplicație care poate fi folosită nu doar ca un instrument pentru un anumit domeniu, ci se poate generaliza și folosi ca un instrument didactic pentru înțelegerea cât mai ușoară a teoriei matematice care se află în spatele acestori algoritmi de detecție.

1.2 Scurtă descriere a lucrării

Această lucrare începe cu o scurtă descriere de bază despre detecția video și scopul acesteia. După ce cititorul înțelege scopul detecției și elementele de bază ale acesteia i se prezintă elementele implementării unui algoritm de detecție și problemele care pot să apăra la implementarea unui algoritm.

În următorul capitol se prezintă metodele folosite în localizarea video care pot porni de la o singură ipoteză sau de la ipoteze multiple. Sunt prezentate părțile matematice ale celor două metode de localizare și modelele matematice ale celor 3 algoritmi universali de detecție Kanade-Lucas-Tomasi (KLT), algotimul cu translație a mediei (mean shift – MS) și detecția bazată pe Bayes și fitru Kalman.

În capitolul următor trecem prin a exemplifica cum se aplia transformată Hough asupra obiectelor circulare, probleme care influențează detecția obiectelor circulare, pașii pe care îi parcurge algortimul Hough și descrierea acestora.

În ultimul capitol mă ocup de prezentarea aplicației pentru identificarea obiectelor circulare într-o captură video live și prelucrarea datelor obținute. Se face o prezentare succintă a toolurilor folosite în implementarea aplicatiei, stabilirea conexiunii între acestea, scopul fiind acela de a obține o peformanță ridicată prin folosirea redusă a resurselor care pot fi alocate pentru diverse proiecte.

Capitolul 2 Procesare video în localizarea și detectarea imaginilor

2.1 Introducere

În prezent, a face captură video devine o operațiune din ce în ce mai ușoară. Putem spune că planul mașinilor capabile să înțeleagă și să vizualizeze există deja, și dezvoltarea acestora este accelerată atât de progresele în domeniul microelectroinicii cât și de algoritmii de analiză video. Există oportunități variate în ceea ce privește dezvoltarea aplicațiilor în diferite domenii, cum ar fi supravegherea video, crearea și editarea de conținut video, transmiterea video folosită pentru comunicații personale, robotică și interacțiunea naturală om-mașină.

O caracteristică fundamentală și esențială pentru ca mașinile "să vadă",| să înțeleagă" și "să reacționeze" la mediu este ca aceste mașini să aibă capacitatea lor de a detecta și a urmări obiecte de interes. Procesul de estimare și localizare a unuia sau mai multe obiecte de-a lungul timpului folosind o cameră video se numește urmărire în secvențe video. Îmbunătățirea rapidă atât a calității cât și a rezoluției senzorilor de imagine, respectiv creșterea dramatică a puterii de calcul din ultimul deceniu au favorizat crearea de noi algoritmi care folosesc detecțiea în imagini video.

Definiția obiectului de interes depinde de necesitatea de a detecta într-o anumită secvență video a unui anumit obiectiv, acest lucru făcându-se printr-o anumită aplicație.

De exemplu, pentru supravegherea unei clădiri printr-o aplicație, obiectivele pot fi oameni(figura de mai jos, stânga), în timp ce într-o aplicație gen joc interactiv, obiectivele pot fi mâinile sau fața unei persoane.

În acest capitol voi acoperi pașii fundamentali pentru proiectarea unui algoritm de detecție cât și formularea matematică pentru problema de urmărire video.

Figura 2.1: Exemple de ținte pentru urmărire în video: stânga-oameni, dreapta-fețe

2.2 Implementarea unui algoritm de detecție video

Camerele video captează informații despre obiectele de interes sub forma unor seturi de pixeli ai imaginii. Modelând relația dintre aspectul țintei și valorile corespunzătoare pixelilor, un tracker video estimează locația obiectului în timp.

Relația dintre un obiect și imaginea sa proiectată este foarte complexă și poate depinde de mai mulți factori decât de poziția obiectului în sine, făcând astfel urmărirea video de o sarcină dificilă. În această secțiune, voi discuta mai întâi principalele provocări în urmărirea video și apoi voi analiza principalele componente în care urmărirea într-o secvență video poate fi descompusă.

2.2.1 Provocări în detecția video

Principalele provocări care trebuie să fie luate în considerare la proiectarea și funcționarea unui algoritm de detecție sunt legate de similitudinile de aspect între țintă și alte obiecte din scenă, și variațiile țintei în sine.

Aspectul unor obiecte și ale fundalului pot fi similare cu aspectul țintei și prin urmare, poate interfera cu observarea ei. Într-un astfel de cazuri, caracteristicile imaginii sunt extrase din zone ale imaginii care nu doresc sa fie urmărite putând fi dificil de discriminat din caracteristicile pe care se așteaptă ca obiectivul să le detină. Acest fenomen poartă numele de aglomerare. Figura 2.2 prezintă un exemplu de ambiguitate de culoare care poate distrage atenția trackerului de la adevărata țintă. Rezolvarea acestei provocări se poate obține prin utilizarea mai multor caracteristici de pondere cu fiabilitate crescută.

În plus față de urmăriea în caz de aglomerare a imaginii, urmărirea video este ingreunată de modificări ale aspectului țintei în planul imaginii, care apar din cauza unuia sau mai multora din factorii următori:

Modificări ale obiectului țintă O țintă în mișcare variază în aspect atunci când este proiectată pe planul imaginii, de exemplu prin rotire (figura 2.3 (a)-(b)).

Figura 2.2: Exemple de aglomerare în urmărire video. Obiectele din fundal (cutiile roșii) pot avea culoare asemănătoare (stânga) sau formă și proprietăți asemănătoare cu ale țintei (dreapta) și prin urmare de a distrage atenția de la obiectele asemănătoare accentual punându-se pe culoarea obiectului (verde). În stânga avem un scenariu de detecție a trasăturilor feței, iar în partea dreaptă avem un scenariu de supraveghere a unei parcări.

Iluminarea ambientală. Direcția, intensitatea și culoarea luminii pot influența aspectul țintei. Mai mult decât atât, modificările iluminării globale a cadrelor sunt de cele mai multe ori o provocare mai ales pentru scenele în aer liber.

De exemplu, schimbările de lumină ambientală atunci când norii ascund soarele. De asemenea, unghiurile dintre direcția de lumină și normalele la suprafața obiectivului, afectează modul în care vedem obiectul prin lentilele camerei.

Zgomotul. Procesul de achiziție de imagine introduce în semnalul imaginii un anumite grad de zgomot, care depinde de calitatea senzorului camerei video. Observațiile prinind ținta pot fi corupte și prin urmare pot afecta performanța detectorului.

Ocluziile. O țintă poate să nu fie observată parțial sau în totalitate deoarece în cadru apar și alte obiecte în scenă. Ocluziile sunt de obicei cauzate de:

O țintă în mișcare în spatele unui obiect static, cum ar fi o coloană, un perete, sau un birou (figura 2.3 (c)), sau

alte obiecte aflate în mișcare care ascund obiectul țintă (figura 2.3(d)).

Pentru a aborda această provocare, pot fi aplicate diferite metode, care depind de nivelul așteptat de ocluzie:

Ocluzii parțiale care afectează doar o mică parte a zonei țintă pot fi tratate de către modelul aspectului țintei sau de algoritmul de detecție în sine. Proprietățile

Figura 2.3: Exemple de modificări ale aspectului țintei care fac urmărirea dificilă (a)- (b) ținta iși schimbă capul acest lucru facând imposibilă detectarea de către aparatul video. In partea a doua a pozei, figura (c)-(d) avem două exemple de ocluzii. În figura (c) vederea directă a țintei este obstrucționată de către obiectele statice din scenă. (d) vederea directă a țintei este obstrucționată de către alte obiecte aflate în mișcare în scenă.

invarianței unor metode de reprezentare la nivel global ale caracteristicilor(de exemplu histograma) sunt adecvate pentru a face față ocluziilor. De asemenea înlocuirea unei reprezentări globale cu mai multe caracteristici limitate pe o mică regiune a țintei pot crește robustețea unui detector în imagini video.

Informații cu privire la caracteristicile aspectului țintei nu sunt suficiente pentru

a face față unei ocluzii totale. Pentru a face față acestei provocări este necesar să pornim de la un raționament de nivel ridicat sau prin intermediul metodei ipotezelor multiple de urmărire de-a lungul timpului (problemă tratată în capitolul următor). Informațiile despre comportamentele tipice ale mișcării și metodele preexistente de ocluzie pot fi de asemenea folosite pentru a propaga traiectoria țintei, în lipsa de măsurători valabile. Când reapare ocluzie la detectarea vizată, propagarea metodei ipotezelor multiple și de modelare a aspectului poate oferi indicii necesare pentru a reinițializa o cale.

O descriere sumară a principalelor provocări întâlnite în detecția video este prezentată în figura de mai jos:

Figura 2.4: Principalele provocări în urmărirea video apar ca urmare a variațiilor temporale ale aspectului obiectului urmărit și a similitudinii cu alte obiecte din scenă.

2.2.2 Principalele componente ale detecției

În scopul de a aborda provocările discutate în secțiunea anterioară, am identificat cinci componente logice ale unui algoritm de urmărire în video

Definiția metodei de extrage a informațiilor relevante dintr-o zona de imagine ocupată de către obiectiv. Această metodă se poate baza pe clasificarea mișcării, pe detectarea schimbului, pe clasificarea obiectelor sau pur și simplu pe extragerea de rang inferior a caracteristicilor, cum ar fi culoarea sau panta, sau de nivel mediu, cum ar fi marginile sau punctele de interes.

Figura 2.5: Procesul de urmărire video. Diagrama prezintă principalele component logice ale unui algoritm de urmărire

Definiția de reprezentare pentru codificarea aspectului și a formei unui obiect țintă (a stării). Această reprezentare definește caracteristicile unui obiectiv țintă care urmează să fie utilizate ca șablon pentru detecție. În general, reprezentarea este un compromis între acuratețea descrierii și invarianță: un șablon ar trebui să fie descris amănuțit pentru a face față aglomerării sau a țintelor false, permițând în același timp un anumit grad de exibilitate, pentru a face față cu schimbările de scară ale unui obiectiv, sau iluminare și ocluzii parțiale.

Definiția unei metode care propagă starea unei ținte de-a lungul timpului. Acest pas recursiv folosește informații de la etapa de extracție sau de la caracterizarea stării estimate deja disponibilă pentru a forma traiectoria. Această sarcină leagă instanțe diferite ale aceluiași obiect în timp și trebuie compensate ocluziile, încărcarea, și schimbarea iluminării locale și globale.

Definirea unei strategii care gestionează obiectele care apar și dispar din cadru. Acest pas se referă de asemenea la managementul țintelor, inițializarea căii pentru un obiect de interes și se termină cu traiectoria unui obiect de interes dispărut. Când un nou obiect de interes apare în cadru (se reinițializează urmărirea) se inițializeazăvo nouă traiectorie.

Extracția meta-datelor într-o stare compactă a țintei și lipsită de ambiguitate pentru a fi utilizate de către o aplicație specifică, cum ar fi încadrarea țintei în video, înțelegerea și recunoașterea comportamentului șablonului într-o scenă.

Capitolul 3 Modelul matematic de detectarea a obiectelor în imagini video

3.1 Introducere

In acest capitol o să discut despre cum pot localiza un segment al imaginii de-a lungul timpului, având o poziție inițială. După inițializare, etapa de localizare într-un frame se bazează pe recursivitatea estimată a stării xy dată de caracteristicile extrase din frameurile video, bazându-se pe stările anterioare estimate: x1:k-1.

Putem clasifica metodele de localizare în două clase majore:

Metoda de localizare pornind de la o singură ipoteză (SHL), unde un singur cadru poate fi estimat și evaluat la un moment dat;

Metoda de localizare pornind de la ipoteze multiple (MHL), unde mai multe cadre sunt evaluate simultan: abilitatea de a propaga ipoteze multiple pot îmbunătăți performanța detecției;

Estimarea stării se bazează presupunând că poziția, forma și opțional aspectul unei ținte într-o succesiune de cadre se schimbă lin de-a lungul timpului. În altă ordine de idei, coerența detecției se bazează pe obiectele detectate anterior și variază de la o situație la alta. În următoarele secțiuni voi discuta despre strategiile de localizare si de urmărire a detaliilor într-un cadru video.

3.2 Metoda de localizare pornind de la o singură ipoteză

Estimările optime ale obiectului de detectat (în sensul în care avem un obiect de formă pătratică) pot fi obinute algebric sub ipoteze foarte stricte pentru relația între caracteristica spațiului E0 și starea spațiului Es. Adesea, atunci când algoritmul de localizare urmărește o țintă în spațiul de detecție (de exemplu viitorul spațiu în care dorim să facem detecția face parte din spațiul de detecție), estimarea optimă prin metoda celor mai mici pătrate poate fi aplicată folosind un filtru Kalman. Cu toate acestea la majoritatea cazurilor relația intre caracteristicile si stările care nu îndeplinesc condițiile optime, poate fi aproximată ca și o soluție necesară. Un exemplu sunt metodele bazate pe variația gradientului despre care o să discutăm în subcapitolul următor.

3.2.1 Detecția bazată pe gradient

Detecția bazată pe gradient utilizează caracteristicile imaginii care conduc la aflarea stării obiectului de detectat (bazat pe ipoteza de detecție) ca și o soluție la problema de detectare în imagini video. Având în vedere caracteristicile extrase din cadrul curent și o funcție de scor care definește calitatea stării candidatului, metode bazate pe gradientul iterativ înmbunătățește estimarea ți convergența la un maxim local al scorului.

Figura 3.1: Strategia de localizare bazată pe gradient folosind informațiile din imagine pentru a îmbunătății starea predicției estimată

Algoritmi frecvenți pentru a rezolva aceste iterații în problemele de optimizare sunt bazați pe gradientul original sau pe maximizarea așteptată. Un punct convenabil de pornire (inițial) în fiecare cadru este starea anterioară estimată. Acest lucru impune în mod natural o constrângere temporală cu privire la mișcarea pe care o efectuează obiectul de detectat față de cadrul anterior.

Detectarea în cadre folosind Kanade-Lucas-Tomasi (KLT)

Putem spune că un simplu model al obiectului pe care dorim să îl detectăm este un șablon. Detectarea folosind algoritmul Kanade-Lucas-Tomasi (KLT) poate fi folosită pentru a estima stările unui obiect pe care dorim sa îl detectăm folosind un șablon.

Fără pierderi de generalitate, zona în care obiectul de detectat se va afla va fi un pătrat de dimensiune fixă N = (2W – 1) x (2W – 1). Problema de urmărire a țintei poate fi redusă la estimarea mișcării de translație pură, unde starea inițială se poate defini ca:

xk = (uk , vk).

Putem permite sistemului de coordonate ale șablonului, IT (.) , să fie aliniat cu sistemul de coordonate ale imaginii Ik; ∀k. Dată fiind starea inițială a țintei pe care dorim să o detectăm, la timpul ințial k poate fi estimată ca și deplasare xk-1, la timpul k – 1, starea la timpul xk, la timpul k poate fi descompusă ca:

xk = xk,

(3.1) [11]

unde xk , este o mică deplasare adăugată la deplasarea anterioară. De asemenea, prin impunerea unor constrângeri spre exemplu constanta de iluminare, se pot considera discrepanțe ale aspectului între șablon și fereastra centrată în jurul stării xk ca și zgomot, aceasta fiind

(3.2) [11]

cu care indică norma lui L1; w este locația unui pixel in imagine și nk (w) modelele zgomotului aditiv peste valorile pixelilor.

În consecință, problema de detecție se reduce la a căutapentru o deplasare mică care minimizează erorile dintre zona imaginii implicite de cea mai bună estimare pentru și șablon, aceasta fiind

(3.3) [11]

Pentru valori mici ale lui putem aproxima funcția șablonului (.) cu seria sa Taylor care este centrată în jurul valorii de , trunchiată în termeni liniari la:

, (3.4) [11]

unde este transpunerea gradientului șablon

și matricea șablonului este reorganizată ca un vector pe o singură coloană. Apoi prin înlocuirea în ecuația (3.3), se pot obține:

.

(3.5) [11]

Acum este o funcție pătratică și prin urmare ecuația anterioară poate fi minimizată în formă închisă prin soluționarea următoarei ecuații:

Aceasta duce la:

(3.6) [11]

Având în vedere aproximarea Taylor, estimat nu poate corespunde la o minimă locală a erorii. Prin urmare, este necesar să se înlocuiască cu și de a itera ecuația de mai sus (3.6) până la convergență.

Trebuie reținut faptul că formularea de mai sus poate fi extinsă la mai multe tranformări complexe decât translații pure. Atunci când starea x reprezintă o transformare lineară arbitrară a regiunii șablon, se poate calcula o aproximare lineară ca și în ecuația (3.4) putând fi opținută printr-o procedură similară.

Pentru a rezuma cele spuse mai sus, în figura 3.2 se ilustrează o procedură de urmărire a unui șablon bazată pe KLT. Dacă este cunoscută starea inițială a țintei și modelul șablonului, pentru fiecare cadru pe care îl primim, algoritmul KLT compară template-ul cu imaginea și se efectuează un pas de optimizare a ecuației (3.6).

În cazul în care condițiile de convergență (de obicei bazate pe erori și a parametrului care definește dimensiunea pasului, care este un compromis între starea de așteptare și viteza de adaptare a algoritmului) nu sunt îndeplinite, actualizările KLT ale stărilor estimate duc la un alt pas de optimizare; în sens contrar ieșirile KLT ale stări estimate continuă să proceseze următorul cadru.

Este important de notat că proprietățile locale de convergență ale metodei impun o constrângere în mișcarea țintei care poate fi satisfăcută. De fapt, pentru translațiile care sunt mai mari decât mărimea șablonului, diferența între șablon și imagine, al numitorului comun din ecuația (3.6) se calculează pe o regiune care nu conține nici o țintă. Astfel, acest pas este necorelat cu mișcarea reala a țintei. În practică estimarea tinde să se degradeze mult mai devreme. Acest lucru depinde de metoda utilizată pentru a calcula gradientul imaginii (de exemplu, mărimea kernelului ), și aproximarea ecuației lineare (5.4) devine din ce în ce mai puțin precisă când crește mișcarea.

Algoritmul de translație la medie-mean shift(MS)

Când reprezentarea țintei se bazează pe histograme de culoare, algoritmul de translație la medie poate fi folosit pentru a reduce iterativ distanța ân ecuația (- distribuția normalizată și ponderată de culoare, – distanța dintre modelul de histogramă), folosind informațiile despre gradient. Minimul ecuației anterioare corespunde la un maxim al ecuației

Figura 3.2: Strategia de localizare bazată pe Kanade-Lucas-Tomasi(KLT). Starea inițială este redefinită folosind informații ca și modelul șablonului și cadrul curent.

, Similar lui KLT, MS utilizează procedura anterioară de estimare a stării inițială , aceasta fiind:

Folosind ecuația ; și calculul Taylor de extindere a coeficientului Bhattcharyya aproximativ si doar cu respectarea centroidului yk o să obținem:

,

(3.7) [11]

unde

(3.8)

Ca primul termen din ecuația (3.7) din partea dreaptă să nu depindă de yk, doa al doilea termen trebuie să fie redus la minim. Acest lucru se poate realiza prin rezolvarea gradientului și cu respectarea lui yk să fie zero. La fiecare iterație, ținta estimată se schimbă de la la , noua locație definindu-se ca:

(3.9) [11]

Dacă , atunci este in direcția gradientului.

Procesul iterativ continuă substituind cu și oprindu-ne în momentul în care este îndeplinită ecuația [11]

În mod uzual pixel. Trebuie reținut faptul că suprafața unde ținta poate fi cautată este definită de mărimea kernel-ului(de vizualizat ecuația 3.9).

Pentru acest motiv, în cazul în care schimbarea țintei este mai mare decât mărimea kernel-ului, este bine ca subiectul urmărit să fie pierdut. Această observație este aceeași cum am precizat la recunoașterea pe bază de șablon.

Diagrama bloc care o să urmeze în continuare sumarizează procedurile de localizare bazate pe MS.

Se pot vedea diferențe intre procedurile MS (figura 3.3) si KLT (figura 3.2) unde este un bloc suplimentar care calculează histograma de culoare. Procedura celor mai mulți algoritmi de detecție este bazată pe optimizarea recursivă fiind similară cu cea de la MS, având caracteristici de extragere și pași de optimizare apropiați.

Figura 3.3: Algoritmul de translație la medie-Mean Shift(MS) procedura de localizare, starea inițială estimată este rafinată folosind informații din modelul histogramei și histograma regiunii pretendente calculate peste cadrul curent

În general, cum sunt algoritmii de optimizare bine concepuți , converg la un număr mic de iterații, cu o metodă bazată pe o singură ipoteză și metode de calcul ieftine. Cu toate acestea, starea estimată depinde foarte mult de inițializare, localizarea unei singure ipoteze se comportă slab în cazul unei ocluzii. În plus, atunci când funcția de detectare a modelului este multi-modală peste zona de calibrare a kerner-ului , algoritmul unei singure ipoteze poate converge la nelocalizarea în imagine. În cele din urmă în cazul de convergență al unei estimări incorecte, o recuperare a detecției într-o imagine este puțin probabil să se realizeze, așa cum se vede în figura de mai jos.

Figura 3.4: Mean shift

3.2.2 Detecția bazată pe Bayes si filtrul Kalman

Trackerele Bayes abordează problema incertitudinii prin modelarea stării lui xk și observarea lui zk ca două procese sohastice.

În conformitate cu ipotezele Markoviene (de exemplu, date fiind observațiile , starea curentă a lui xk depinde doar de predecesorul său xk-1 și zk depinde doar de starea curentă xk așa cum se vede în figura de mai jos, recursivitatea fiind complet determinată de ecuația care se ocupă de observarea stărilor:

(3.10) [11]

și ca dinamica lui xk, este definită starea ecuației fk, ca și

(3.11) [11]

unde și sunt independente și identic distribuite secvențele procesului de zgomot.

Scopul unui proces Bayes este de a estima , pdf-ul obiectului este în starea xk , având în vedere toate observațiile zk până la momentul k. Estimarea se face recursiv, în două etape, adică de predicție și de actualizare:

Pasul de predicție utilizează modelul dinamic definit în ecuația (3.11) pentru a obține un pdf important prin intermediul ecuației Chapman-Kolomogorov:

,

(3.12) [11]

cu cunoscută de la iterația anterioară și densitatea de tranziție determinată de ecuația (3.11) cunoscând statisticile lui nk.

Figura 3.5: Modelul grafic al dependențelor de urmărire a ipotezelor Markoviene. Fiecare cerc reprezintă un vector aleator; săgețile arată dependențele dintre vectorii aleatori; cercurile umplute reprezintă interferența sesizabilă. Observația curentă zk depinde doar de starea curentă xk. Starea curentă xk depinde la rândul ei doar de starea precedentă xk-1 .

Pasul de actualizare folosește regula Bayes' atunci când zk este observată este disponibilă, astfel încât:

, (3.13) [11]

unde este determinat de ecuația (3.10) și de a cunoaște statisticile lui .

3.2.3 Filtrul Kalman

În general, ecuația (3.12) și ecuația (3.13) nu pot fi determinate analitic. O soluție binecunoscută, filtru Kalman, se bazează pe presupunerea liniarității ecuației (3.11) și a ecuației (3.10), a ausianității în prealabil cu , și pentru cele două procese de zgomot, și .

În acest caz, ecuația (3.10) și ecuația (3.11) se poate rescrie ca :

(3.14) [11]

și

(3.15) [11]

unde și sunt matrici furnizate de către utilizator care definesc relația lineară între stări consecutive și între stări și observații, și două procese de zgomot și având media zero covarianțele și respectiv .

Având în vedere statisticile de ordin primar și secundar, și media dată și covarianța înainte de din relația lineară a ecuației (3.15) și pasul de predicție din ecuația (3.12), vom obține statistica densității de predicție sub forma predicției medii:

; (3.16) [11]

și predicția covarianței

(3.17) [11]

unde cea din urmă se propagă înainte nesigur prin starea de tranziție a ecuației (3.14) și se adaugă la o incertitudine dată de acest pas (de exemplu ). De asemenea, din ecuația (3.14) putem calcula măsurarea anticipată ca

, [11]

Când noua măsurare devine disponibilă, din ecuația (3.13) putem deriva media reziduală

[11]

covarianța reziduală devine

[11]

și , câștigul Kalman, este

[11]

În final, pentru a completa recursivitatea, statisticile de ordin primar și secundar ale statisticii posterioare este media estimată

(3.18) [11]

și convarianța posterioară

(3.19) [11]

Rezumat

În cazul în care ipotezele sunt valide (linearitate pentru ecuația (3.11) și (3.10) și sunt în prealabil gausiane și au două procese de zgomot), filtrul Kalman este optim în ceea ce înseamnă media erorii pătratice a stării estimate.

În cazul în care ipotezele nu sunt valide, filtrul Kalman produce o soluție rezonabilă în cazul în care distribuția de bază este bine descrisă de către primele două momente ale sale (de exemplu medie și covarianță).{acesta fiind cazul uzual în care distribuția este uninomială}

În cazul în care ipotezele nu sunt valide, soluțiile sub-optimale sunt posibile. Dacă ți sunt diferențiabile, un prim ordin al expansiunii Taylor poate lineariza funcțiile de stare și observare (de exemplu și ) rezultatul fiind un
filtru suboptimal cunoscut ca Filtru Kalman Extins (EKF).

Cu toate acestea funcțiile de stare și de observare și nu pot fi diferențiabile. De asemenea, ca urmare a aproximării Taylor filtrul se poate abate repede de la cel optim. În cele din urmă așa cum este cazul în filtrele de urmărire, posteriorul este unimodal, prin urmare ipoteza Kalman simplifică problema de recunoaștere si subestimează valoarea de claritate a datelor. Pentru a face față acestor probleme, o să putem utiliza ipoteze multiple, pe care o să le descriu în secțiunea următoare.

3.3 Metoda ipotezelor multiple

Metoda ipotezelor multiple de localizare (MHL) generează mai multe ipoteze de detecție pentru fiecare frame așa cum arată figura de mai jos. Aceste metode sunt apoi validate față de măsurătorile de imagine și de un model al obiectului aflat în mișcare. Ipotezele improbabile sunt înlăturate de la cadru la cadru, în timp ce ipotezele cele mai probabile sunt propagate.

Gama multiplelor ipoteze ale abordărilor care selectează ipotezele bazate pe metode euristice simple la soluții complexe, propagă ipoteze bazate pe cadre probabilistice.

Cele mai populare ipoteze multiple probabilistice ale algoritmilor de localizare sunt filtrul de particule, o aproximare Monte Carlo a recursivității de detecție Bayes. Utilizarea ipotezelor multiple permite algoritmilor, cum ar fi filtru de particule, pentru a face față mai bine la funcții de scor multimodale, precum cele generate de ocluzii sau prin prezența unei dezordini astfel încât ținta să nu poată fi distinsă.

Figura 3.6: Ipoteze multiple de localizare(MHL) aceste metode elaborează ipoteze multiple și apoi imaginile sunt folosite pentru a evalua calitatea fiecărui eșantion. [11]

Figura 3.7: Eșantionarea mult-dimensională a spațiilor. Numărul de ipoteze necesare pentru explorarea spațiului crește exponențial cu numărul de dimesiuni. Stânga: spațiu 1D (4 eșantioane), în centru: spațiu 2D (16 eșantioane); dreapta: spațiu 3D (64 eșantioane).

Comparativ cu metoda unei singure ipoteze de localizare, localizarea cu ipoteze multiple (MHL) au metode de calcul mai scumpe și impun limitări puternice aspupra dimensionării stării spațiului. De fapt, numărul de ipoteze care sunt necesare pentru a explora spații multi dimensionale creste exponential cu numărul de dimensiuni ale spatiului respectiv. În exemplul din figura de mai sus, dacă presupunem că toți parametrii spațiului sunt la fel de importanți, 41 = 4 ipoteze folosite pentru a eșantiona un spațiu 1D, devine 42 = 16 ipoteze pentru două dimensiuni și 43 = 64 ipoteze pentru un spațiu 3D.

Diferența majoră între diferitele metode de localizare multi-ipoteză este strategia ultilizată pentru a selecta ipotezele de urmărire.

3.3.1 Grila de eșantionare

Atunci când activitatea de urmărire și de calcul a resurselor este disponibilă, o simplă abordare grosieră poate fi suficientă pentru a rezolva problemele de urmărire în video. Grila de metode bazate pe localizare selectează ipotezele într-un mod determinist cu ipotezele poziționate într-o rețea regulată așa cum se arată în figura de mai jos pentru un spațiu 2D.

O procedură pentru a construi un tracker simplu, recursiv bazat pe rețeaua de eșantionare este descris în pașii următori:

Definirea unei ferestre de căutare W centrată pe estimarea anterioară cea mai bună

Împărțirea ferestrei de căutare folosind o rețea regulată.

Evaluarea ipotezelor țintei sunt prezente în fiecare stare folosite pentru a defini rețeaua, de exemplu pentru unul din scorurile potrivite.

Selectarea celor mai bune ipoteze pentru starea actuală .

Figura 3.8: Exemplu de mai multe ipoteze de urmărire, care sunt desenate folosind o rețea de eșantionare regulată.

Trebuie reținut faptul că proceduri similare în compresia video apar atunci când folosind blocuri de detecție pentru estimarea mișcării. Pentru a exploata resundanța temporală între cadre ulterioare, inițial imaginea este împărțită în blocuri rectangulare (de exemplu compus din 16 X 16 pixeli). Apoi poziția fiecărui bloc (acestea având coordonate verticale și orizontale), este urmărit în cadrul anterior sau următor. Căutarea completă exhausitivă a algoritmilor de potrivire a blocurilor folosește o rețea de eșantionare cu spațiul de un pixel. În continuare în ambele regiuni candidate și șablonul bloc au același număr de pixeli, evaluarea unei ipoteze de detecție se poate face prin calcularea normei L1 dintre vectorii de concatenare a valorilor pixelilor. L1 este de obicei aleasă deoarece este mai puțin costisitoare ca și cost decât normele de ordin mai mare(de exemplu L2).

Precizia algoritmilor este bazată pe grila de eșantionare și selecție a celui mai potrivit ce depinde de distanța de grid. Urmăririle mai exacte pot fi realizate cu o grilă mai densă obținută prin creșterea rezoluției pentru fiecare cadru de imagine folosind interpolarea și apoi apelând grila de eșantionare pentru imagini mai mari.

Deși o căutare completă în întreaga rețea este garantată pentru a returna rezultatul optim, este practic doar atunci când evaluarea unu singur candidat este ieftină. De fapt, evaluarea tuturor ipotezelor definite de către grid pentru a găsi cea mai bună soluție de calcul poate fi prea scumpă. Atunci când resursele de calcul sunt insuficiente, există soluții sub-optimale. De exemplu, o abordare populară este eșantionată ierarhic unde mai întâi grila de eșantioane este grosier evaluată și apoi recursiv, fin, grilele ale ipotezelor centrate pe cea mai bună ipoteză curentă este evaluată la momentul respectiv. Un exemplu de structură ierarhică în trei etape de eșantionare este dat în exemplul din figura de mai jos.

În această figură, punctul roșu indică cea mai bună ipoteză la fiecare pas.

Figura 3.9: Procedura de eșantionare ierarhică a grilei. De la stânga la dreapta: o grilă fină este utilizată pentru a îmbunătăți starea curentă a celei mai bune ipoteze(de exemplu punctul roșu).

3.3.2 Filtrul de particule

Când și (ecuația 3.11 și ecuația) sunt neliniare, care variază în funcție de timp, putem considera o soluție bazată pe integrarea Monte Carlo.

Densitățile sunt aproximate cu suma funcțiile Dirac (particulele) fiind centrate în

ca

(3.20) [3]

unde

sunt ponderile asociate cu particulele și definite ca

(3.21) [3]

este o importantă funcție de densitate definită ca și densitatea care generează setul curent de particule.

Să presupunem că este aproximat prin setul de particule și ponderile asociate

,

ca în ecuația (3.20). Prin substituirea aceste aproximări în ecuația (3.12) o să obținem:

(3.22) [3]

Apoi din ecuația (3.13) și ecuația (3.21) urmează formularea recursivă de propagare a particulelor și ponderilor acestora cum ar fi

, (3.23) [3]

În algoritmul de condensare al lui Isard și Blake praticulele sunt desenate printr-o prezicere anterioară, adică

, (3.24) [3]

Acest lucru reduce ponderea ecuației (3.23) la

, (3.25) [3]

unde ponderile sunt proporționale cu riscul.

O formulare alternativă a actualizării ponderi este posibilă prin aplicarea aproximării Monte Carlo la egalitatea din partea dreptă

(3.26) [3]

unde ponderea este definită ca

(3.27) [3]

Apoi, pe baza unor procese Markoviene, prin descompunerea funcției de eșantionare importantă ca

(3.28) [3]

și presupunând

,

rezultă că

(3.29) [3]

Pentru a elimina particulele cu ponderi mici, putem aplica un pas de eșantionare înainte de propagare. Pasul de eșantionare se bazează pe

din seria

în conformitate cu funcția de re-eșantionare

Funcția de re-eșantionare definește probabilitatea ca fiecare particulă să genereze un nou eșantion la momentul k. Ponderile estimate ale filtrului posterior este obținut prin marginalizarea lui sin ecuația (3.26).

Ponderile sunt constante în marginalizare ca aceștia să nu depindă de , dar depind doar de pozițiile particulelor și . În consecință aproximarea filtrată posterioară a ecuației (3.20) moștenește aceleasi ponderi ca și egalitatea din partea dreptă a ecuației (3.26).

Cele două ecuații recursive actualizate (ecuația 3.23 și ecuația 3.29) diferă în pricipal de importanța funcției de eșantionare. Prin contabilizarea dependenței de cu starea anterioară actualizarea ponderii devine dependentă doar de și nu de setul de eșantioane globale, ca și în ecuația (3.23). Deși calculul ecuației (3.29) necesită mai puține înmulțiri decât ecuația (3.23), calculul lui necesită o atenție suplimentară pentru dependențele între factorizarea funcției de eșantionare importantă și pasul anterior (de timp).

Filtrele, bazate pe eșantionarea Monte Carlo și recursivitatea ecuațiilor Bayes, sunt cunoscute ca filtru de particule (PFs). Estimarea stării este de obicei calculată fie prin luarea unui maxim posteriori estimat, aceasta fiind particulele cu cea mai mare pondere, sau prin calcularea așteptării asupra ponderii particulelor ca

. (3.30) [3]

Figura de mai jos arată un exemplu al unui filtru de particule cu re-eșantionare. Reeșantionarea este un pas opțional care se aplică pentru a curăța ipotezele improbalile de la seria particulelor, și pentru a evita ca după câteva iterații aproape o singură particulă să aibă pondere neglijabilă. Acest fenomen este cunoscut ca particula scăpată.

Spre deosebire de filrul Kalman se poate ocupa și cu multi-modalitatea pdf-urilor și astfel se pot recupera pentru un termen scurt ocluzii. Cu toate acestea, rezultatul de urmărire depinde foarte mult de setarea parametriilor, care în schimb depind de conținutul cadrului. Mai mult decât atât numărul de particule necesare pentru a modela pdf-urile care stau la baza creșterea exponențială cu dimensiune stării spațiului, astfel sporind în mod semnificativ sarcinile de calcul. Eficiența acestui PF depinde de fapt de distribuția eșantioanelor în spațiu.

[11]

Figura 3.10: reprezentarea schematică a unui filtru de particule , cu re-eșantionare sistematică. De jos in sus: filtrarea re-eșantionează particulele și schimbă locul acestora în spațiu în acord cu importanța funcției de eșantionare sau apoi utilizând observații, actualizările ponderilor fiind în conformitate cu ecuația (3.23) sau ecuația (3.29).

Capitolul 4 Operatori folosiți în identificarea obiectelor circulare în imagini video – transformata Hough

4.1 Introducere

Un număr mare de metode de detectare a cercurilor au fost studiate pentru mai multe aplicații de procesare a imaginii. În această lucrare o să îmi propun să realizez identificarea obiectelor circulare (mai precis a mingilor de fotbal dintr-un meci, poziție, traiectorie, etc.) cu ajutorul transformatei Hough, folosind detecția cercurilor în imagini statice. În secvențele de imagini video se vor transforma în imagini statice (24 frame-uri pe secundă) pentru a reuși să dentificăm mingea, traiectoria acesteia, respectiv de a observa dacă mingea a intrat în poarta și s-a înscris un gol.

Acest domeniu este unul dificil având un număr mare de probleme cu care se confruntă, cum ar fi ocluzii, umbre, obiecte similare cu mingea, prelucrare in timp real si așa mai departe. Algoritmul de detecție a mingii ar trebui să fie foarte simplu din punct de vedere al timpilor de procesare și eficient în ceea ce privește rata de eșecuri. Planul nostru de lucru conține un pas secvențial esențial pentru a rezolva problema detecției mingii: utilizează o versiune modificată a transformatei Hough pentru cercuri direcționale unde se detectează care este regiunea imaginii unde se află mingea. Unele trucuri cum ar fi scăderea de fond și de urmărire a imaginii vor fi aplicate în scopul de a menține o căutare a mingii doar în zonele limitate ale imaginii. Diferite condiții de iluminare au fost considerate că introduc modificări puternice cu privire la aspectul mingii în imaginea respectivă: când secvențele de imagine sunt capturate la lumină naturală, adică sursa de lumină este strict direcțională, mingea, ca urmare a auto-nuanțării, apare ca un capac sferic, in acest caz fiind luate în considerare și situațiile anterioare pentru a avea o gestiune cât mai bună a poziiilor mingii. O să efectuez un număr mare de experimente care să ne arate cea mai bună metodă de detecție pentru a avea o rată de detecție cât mai mare.

Caracteristicilei transformatei Hough au rolul de a transforma o imagine într-un parametru spațiu, numit spațiu Hough. Se știe că transformata Hough standard (SHT) este o tehnică robustă pentru detecție și forme analitic definite, dar este necesară o memorie considerabilă a sistemului si un cost de calcul ridicat. SHT este necesar un acumulator tridimensional pentru detecția parametrilor cercului (x0; y0; r) În adunare, este dificil sa găsești un maxim într-un spațiu Hough datorită numărului necunoscut de vârfuri. În ceea ce privește acest lucru, mai multe versiuni ale SHT au fost introduse.

O modificare a SHT pentru detecția cercurilor folosind o matrice bidimensionala. Acest algoritm are scopul de a îmbunătăți eficiența și de a reduce mărimea (dimensiunea) spațiului Hough. Din păcate această metodă tinde să eșueze dacă mai mult de jumătate dintr-un arc de cerc este vizibil, deoarece această metodă este bazată pe localizarea tangentelor paralele.

O altă metodă este noua transformare Hough paralelă pentru cercuri. Acest algoritm folosește o pereche de acumulatori bidimensionali pentru a reduce memoria și costul de calcul. Este capabil de discriminări multiple pentru cercuiri (incluzând si pe cele concentrice) într-un complex de imagini din viața reala cu o rată a detecției de 95-100%. În Transformarea Inversei(TOI)[2] pentru detecția cercurilor, cercul detectat este întâi transformat într-o linie dreaptă, deci problema de detecție se va reduce la detecția liniilor. Aceasta reduce dimensiunea spațiului Hough la un plan și în acelați timp îmbunătățește costul de calcul. În adunare, interpretarea maximei locale în spațiul Hough este simplificată.

Metodele prezentate mai sus au toate ceva în comun. Calea în care algoritmul procesează o imagine nu se schimbă de la imagine la imagine, și acest lucru îl face să fie un algoritm static. O nouă familie a transformatei Hough a fost introdusă, transformata Hough probabilistică(PHT). Transformata Hough generalizată dinamic(DGHT) aparține și ea acestei familii. Algoritmul DGHT este preferat in situațiile in care împrejurimile se schimbă, deoarece este adaptat la atribuirea care i se dă. Acesta împarte regiunea de interes de câte ori este nevoie pentru a localiza cercurile. Aceasta proprietate dinamica duce la o reducere semnificativă in calculul numeric fata de SHT. Transformarea Hough generalizată dinamic, în aceasta seciune o să tratez o descriere a algoritmului DGHT. Acest algoritm se bazează pe diagrama de mai jos:

Primul pas este sa procesăm imaginea de intrare astfel încât să conțină numai margini fără concavitățile din cercurile suprapuse. Imaginea este apoi scanată pentru a conecta marginele pixelilor. O dată conectate aceaste margini, sunt determinate, localizate și folosite pentru a segmenta în părți imaginea (regiunea de interes). Toate marginile pixelilor relativ conectate la marginea pixelului si apoi sunt stocate într-o listă. Această listă este eșantionată de un număr de ori, de fiecare dată fiind aleși aleatoriu doi pixeli. Acești doi pixeli împreună cu pixelul conectat sunt folosiți pentru a calcula parametrii cercului care sunt stocați in trei acumulatori separați , de o dimensiune. Eșantionarea și calcularea este continuă până când statisticile acumulatorilor îndeplinesc o condiție predefinită.

Când acesta apare cercul este detectat, maximul în acumulatori fiind îndeplinit. Acest maxim corespunde parametrilor cercului detectat este ulterior înlăturat din imagine, si algoritmul începe să scaneze din nou pentru un pixel nou conectat. Acest algoritm continuă să scaneze pînă când imaginea este complet procesată.

Figura 4.1: Diagrama pentru algoritmul DGHT [4]

4.2 Metodele folosite algoritmul Hough pentru ex-tragerea obiectelor circulare

a) Procesarea

În acest pas al algoritmului DGHT imaginea este procesată, care constă în, detectarea marginilor și înlăturarea concavităților din cercurile suprapuse.

Pentru a executa și procesa doua imagini sunt folosite, una de intrare și o alta de ieșire. Primul prag este aplicat la imaginea de intrare în scopul de a o face binară. Făcând acest lucru, obiectele sunt separate de fundal. Găsirea pragurilor este efectuată ca o comparative intre nivelul de gri luând în considerare daca este mai mic decât th atunci pixelul este făcut negru, în sens contrar fiind făcut alb.

Pragul valorii th este determinat de nivelul de gri din imaginea de mai jos (figura 2 ) unde putem vedea două maxime locale. Valoarea th este aleasă ca fiind minimul valorii dintre doua maxime. În anumite cazuri această histogramă nu arată ca în figurii 2, fiind mult mai dificil de găsit pragul valorii th astfel că, în aceste cazuri diferite este necesară o altă abordare a problemei.

Figura 4.2: Histograma de nivel de gri [2]

După ce pragurile s-au găsit, imaginea de intrare este mărginit detectată. Detecția marginii este făcută diferit pentru toți pixelii la găsirea pragului unei imagini. Acesta este făcut calculând valoarea absolută a gradientului, ca o aproximare a acestuia este arătată mai jos (1):

(4.1) [4]

Funcția F indica nivelul de gri al pixelului, în acest caz 0(negru) sau pentru 255 (alb). Daca al pixelului (x,y) în imaginea de intrare este mai mare decât 0, pixelul(x,y) în imaginea de ieșire este un corespondent al marginii la valoarea 255, în caz contrar o să aibă valoarea 0. După acest calcul imaginea de intrare are acel prag de imagine întrucât imaginea de ieșire marginea este deja detectată.

În final concavitățile din cercurile suprapuse sunt înlăturate in imaginea de ieșire. Acest lucru este făcut prin impunerea unei măști 9×9 arătată in figura 3, pixelilor(x,y) în găsirea pragului din imaginea de intrare a mărginii pixelilor(x,y) din imaginea de ieșire.

Pixeli luați în considerare sunt în centrul măștii aplicate.

Figura 4.3: 9×9 mască pentru detecția concavității

O concavitate este detectată atunci când masca deține mai mult de 38 de pixeli albi, care corespund unui unghi mai mic de 180 de grade. În figura 4 o să vedem unghiul de concavitate. Numărul pixelilor albi urmează să fie numarați corespunzători zonei hașurate. Masca este circulară în sensul de a face ca numărul pixelilor in zona hașurată să fie independent de măsura gradului de concavitate.

O concavitate detectată este înlăturată făcând ca fiecare margine a unui pixel în imaginea de ieșire negru. După detecția marginilor precum și după au fost eliminate concavitățile imaginile preprocesate vor conține doar segmente de linie izolate, fiecare aparținând unui cerc.

b) Selectează pixelii conectați (X,Y)

Când procesarea este completă algoritmul DGHT urmărește în imagine primii pixeli conectați (x,y), deoarece este nevoie de o segmentare următoare. Un pixel este considerat să fie conectat dacă deține cel puțin 3 margini ale pixelilor în o mască de 3×3, cum se vede în figura de mai jos:

Conectivitatea este verificată de masca de 3×3 impuse totodată fiecărui pixel în imagine.

Acest lucru se realizează de la stânga la dreapta si de sus în jos.

c) În raport cu segmentul (X,Y)

Figura 4.4: Principiile detecției concavității

Figura 4.5: Masca 3×3 pentru detectarea conectivității

Pasul următor in algoritmul DGHT este segmentarea relativă a pixelului conectat. Aceasta se face creând o lista cu toate marginile care sunt relativ conectate la pixelul respectiv. Marginea pixelilor este înlăturată din imagine ca aceasta să fie stocată in listă. Motivația pentru a folosi segmentarea este că asigură că doar un cerc este în curs de detectare la un moment dat.

d) Eșantion de 2 pixeli

Ulterior pentru segmentare algoritmul selectează trei margini ale pixelilor p1; p2 și p3

pentru a calcula parametrii cercului. Prima margine a pixelului este aleasă pentru a fi pixelul conectat având în timp ce marginile celor doi pixeli rămași sunt eșantionați de către segmentul de listă. Eșantionarea se face ca un proces aleator (uniform distribuit) si este verificat ca cei doi pixeli sunt diferiți.

e) Calcularea parametrilor

Date cele trei margini ale pixelilor este posibil să calculăm parametrii cercului. Parametrii pe care o să îi calculăm au centrul (x0; y0) și raza r raza cercului. Calculul va fi bazat pe cunoștințe ale ecuației cercului (2), si pe cele trei margini ale pixelilor și .

(4.2) [4]

Combinând (2) cu p1; p2 și p3 trei ecuații cu trei necunoscute x0; y0 și r. Aceste ecuații sunt dificil de rezolvat deoarece (2) conține termeni neliniari, așa că îi vom rescrie:

(4.3) [4]

unde

Ecuația cercului in relația (2) a fost transformată într-o ecuație liniară în relația (3) in A, B si C. Rezolvând aceste ecuații pentru A, B si C este același lucru ca și aflarea lui x0; y0 și r, deoarece parametrii cercului pot fi calculați pe bazându-se pe A, B si C.

Pentru a rezolva sistemul de ecuații format din A, B si C ne folosim de formula (3) și p1; p2 și p3.

(4.4) [4]

Această ecuație poate fi simplu rezolvată de înmulțirea cu o matrice de 3 x 3. Inversa unei matrice de 3 x 3 poate fi calculată bazându-se pe minorii asociați ai matricei.

O condiție de folosire a acestor metode este ca determinantul să fie diferit de zero, având această valoare în majoritatea cazurilor mai puțin în cazul în care pixeli sunt plasați pe aceeași linie. Dacă determinantul este zero două noi margini ale pixelilor sunt eșantionate din listă.

f) Parametrii adunării

După ce parametrii x0; y0 și r au fost calculați ei sunt trasați în spațiul Hough. DGHT reduce spațiul Hough de la un acumulator tridimensional, folosit in SHT, la trei acumulatori unidimensionali. Aceasta este realizat prin proiectarea pixelilor in spatial Hough tridimensional pe cele trei axe. Rezultatul duce la o reducere semnificativă a cerințelor de memorie. Dacă soluția în x0 și y0 este notată cu și soluția lui r este notată cu , atunci memoria necesara este redusă la la 2. Deoarece este in sute, o semnificată reducere este obținută. În adunare, reducerea spațiului Hough face să fie mult mai rapidă detectarea maximei in spațiul Hough, corespunzând parametrilor unui cerc care trebuie detectat. Este important ca acumulatorii să fie capabili să stocheze toți parametrii deci informația nu este trunchiată. Acest lucru înseamnă că dacă imaginea conține segmente de cercuri care corespund la cercuri cu centrul ieșit din imagine, atunci acumulatorul x si acumulatorul trebuie să fie capabil să stocheze valori în afara ariei imaginii. Nu este necesar sa evaluăm statistic (g) acumulatorii după fiecare eșantion, deoarece ei nu se schimba atât de mult după un eșantion. Pașii e, f si g sunt prin urmare rulați de un număr de ori înainte de a executa pasul g. înainte de a trece la pasul următor variația fiecărui acumulator este estimată folosind ecuația (5).

(4.5) [4]

Variațiile sunt calculate deoarece sunt necesare pentru a decide când putem opri eșantionarea.

g) Evaluarea statistică

Următorul pas in acest algoritm este sa evaluăm statistic informațiile asociate cu parametrii de detecție. Informațiile statistice sunt folosite pentru a decide când oprim eșantionarea listei cu marginile pixelilor.

Lista de eșantionare este oprită când varianța fiecărui acumulator devine stabila, ca și în figura de mai jos (6):

Figura 4.6: Principiile criteriului de oprire

Dacă eșantionarea este continuată după ce am atins stabilitatea, acest lucru nu ne va da nici o informație. Măsura de stabilitate poate fi estimată examinând abaterea între variația actuală si media variațiilor ale celor n exemple. Media variațiilor ultimului eșantion este cel mai bun estimator al valorii la care converge variația. Acest lucru înseamnă că variația este calculată folosind (6):

(4.6) [4]

Suma de abatere de la variația medie pentru n eșantioane este calculată eroarea reziduală și rezultă e. Aceasta este calculată folosind expresia (7)

(4.7) [4]

Eroarea reziduală este o expresie de stabilitate unde o eroare mica corespunde la un grad mare de stabilitate. Bazat pe asta eșantioanele pot fi oprite când (8) este valabil pentru toți acumulatori.

(4.8) [4]

Factorul K este introdus pentru ca precizia criteriului de oprire sa fie setată individual la o aplicaie dată.

Este un criteriu static de stop care face ca DGHT să fie dinamic. Aceasta înseamnă că pentru datele cercului perfect este necesar să eșantionăm mai puțin timp decât în cazul unui cerc mai puțin perfect. Acest rezultat este un algoritm rapid de comparare al SHT.

Pentru a accepta obiectivele ca un cerc cu o abatere standard , , a acumulatorilor după ce s-au stabilizat ar trebui să fie sub un nivel predefinit. Acesta corespunde la un vârf bine definit îngust al acumulatorilor deoarece se apropie de o distribuție normală (De văzut figura 7). Când eșantionarea s-a oprit algoritmul își continuă pasul 8.

Figura 4.7: Nivelul acumulatorilor

h) Eliminarea caracteristicii

Dacă un obiect este acceptat ca un cerc atunci parametrii sunt calculați si cercul este scos din imagine, în caz contrar algoritmul resetează acumulatorii și se întoarce la pasul b. După ce cercul este înlăturat algoritmul se întoarce la pasul b numai după ce imaginea a fost procesată.

Din momentul în care obiectele rare sunt cercuri perfecte, este necesar sa înlături banda din jurul cercurilor detectate cu scopul de a elimina toți pixeli care aparțin acesteia. Banda cercului care este eliminată din poză o putem vedea in figura 8 de mai jos:

Lățimea benzii cercului este determinata de abaterea standard a parametrilor estimați. În cazul în care avem o distribuție normală lățimea cercului se poate calcula aproximativ

Figura 4.8: Eliminarea cercului detectat

ca și în formula (9).

(4.9)

, și sunt abateri standard ale acumulatorilor x, y si r. Folosirea formulei garantează mai mult de 95% din voturi în acumulatori care includ benzi circulare date de .

Capitolul 5 Partea practică: Identificarea obiectelor circulare într-o captură video live și prelucrarea datelor obținute

5.1 Descrierea aplicației

Aplicația îsi propune să studieze identificarea obiectelor circulare într-o captură video live și prelucrarea datelor obținute. Într-o fabrică producătoare de componete de mașini, pe o linie de producție a unor obiecte circulare ne interesează ca obiectele ieșite din turnătorie să îndeplinească prima calitate, adică să fie circulare, după care să nu fie afectată producția, în sensul că obiectele detectate trebuie să se miște cu o anumită viteză. Softul implementat își propune ca o cameră video să rețină traiectoria acestor piese circulare, să le arate modul în care acestea se îndreaptă spre împachetarea produsului și trimiterea acestuia spre expediere, făcând astfel posibilă reducerea costului cu personalul, o singură persoană putând monitoriza mai multe linii de producție

5.2 Tooluri folosite pentru implementarea aplicației

Pentru implementarea aplicației am folosit C++ ca și limbaj de programare, QT full package (librăriile și IDE), și librăriile OpenCV. În capitolul 5.4 vă voi prezenta detaliile despre implementarea aplicatiei, această descriere prezentată în acest subcapitol făcând mai ușoară întelegerea implementării aplicației.

5.2.1 Limbajul de programare C++

C++ este un limbaj de programare general, care este compilat,un limbaj multi-paradigmă, cu verificarea statică a tipului variabilelor ce suportă programarea procedurală, abstractizarea datelor, programare orientată pe obiecte. Este privit ca un limbaj de nivel mediu, fiind o combinație între un limbaj superior și unul de nivel scăzut. Acest limbaj a fost dezvoltat de către Bjarne Strustrup începând cu 1979 în Bell Labs sub forma inițială de limbajul de programare C facilitatea principală fiind că putea folosi clase. A fost redenumit în 1983 sub numele de C++.

C++ este un limbaj de programare strongly-typed, adică unul în care fiecare tip de date (cum ar fi întreg, caracter, zecimal , și așa mai departe) este predefinit ca parte a limbajului de programare, precum și toate constantele sau variabilele definite pentru un anumit program trebuie să fie descrise cu unul dintre tipurile de date, având o gamă mult mai mare de programare decât C. C++ este un "C mai bun" în sensul că suportă mai multe stiluri de programare aplicând limbajul C cu o mai bună verificare a tipurilor de date și un suport al notațiilor mult mai dezvoltat (fară pierderi de eficiență). În plus, C++ suportă abstractizări ale datelor, programare orientată pe obiecte și programare generică.

În "The Design and Evolution of C++" (1994), Bjarne Stroustrup descrie anumite reguli folosite de către implementarea în C++:

C++ este conceput pentru a lucra cu tipuri de date statice (statically typed), scopul general fiind ca acest limbaj să fie la fel de eficient ca și C;

C++ este conceput pentru a sprijini în mod direct și cuprinzător mai multe stiluri de programare (programare procedurală, abstractizare a datelor, programare orientată pe obiecte și programare generică);

C++ este proiectat pentru a oferi programatorului posibilitatea de a alege, chiar dacă programatorul alege calea nu tocmai corectă;

C++ este proiectat astfel încât să fie compatibil cu C, astfel facându-se o tranzitie lină de la C;

C++ evită caracteristicile specifice platformei de programare sau care nu au un scop general;

C++ este proiectat pentru a funcționa fără a folosi un limbaj de programare sofisticat.

5.2.2 Qt

Qt este o aplicație inter-platformă și un framework care folosește o interfață utilizator. Folosind Qt , putem scrie aplicații web-embeded o sigură dată și să le putem implementa atăât pentru desktop, tablete, mobile, sisteme de operare încorporate, cu facilitatea de a nu rescrie codul sursă. Caracteristicile acestei platforme:

Clase de biblioteci C++ intuitive – modulele Qt pentru librăriile de clasă C++ oferă un set bogat de aplicații building blocks, având toate funcționalitățile necesare de a programa avansat, folosindu-se de aplicațiile cross-platform (a se vizualiza figura de mai jos).

Figura 5.1: Sistemul cross-platform Qt

Interoperabilitatea între diferite sisteme de operare – folosind Qt, putem implementa și dezvolta aplicații în spațiul de lucru și pe sisteme de operare diferite, fără a rescrie codul.

Figura 5.2: Sisteme compatibile pentru platforma Qt

Instrumentele integrate de dezvoltare cu cross-platform IDE- Qt Creater este un cross-platform cu mediu integrat de dezvoltare (IDE), adaptate nevoilor de dezvoltare ale Qt. Acesta include: un sistem avansat de editor de cod C++, o interfață GUI (Graphical User Interface) integrată pentru layout-uri și designer de forme, oferă tool-uri de managementul proiectului și compilarea acestuia, integrare, help-system senzitiv în funcție de context, debbuger vizual, suport pe platforme multiple.

Performanță înaltă la rulare cu un consum minor de resurse RAM.

Distribuit sub termenii licenței GNU Lesser General Public License (printre altele), Qt este un software gratuit și open source. Toate edițiile suportă o arie largă de compulatori, incluzând compliler-ul GCC pentru C + + cât și suita de la Visual Studio.

5.2.3 OpenCV

OpenCV (Open Source Computer Vision) este o bibliotecă de funcții de programare în timp real a "vederii automate" (computer vision – CV). OpenCV este lansat sub licență BSD (Berkeley Software Distribution), și este gratuit atât pentru utilizare didactică cât și pentru scop comercial.

Scris în C și C++ rulează sub Windows, Linux și Mac OS X. Este dezvoltat pe interfețele Python, Ruby, Matlab și alte limbaje. Unul din obiectivele lui OpenCV este acela de a oferi o utilizare simplă a infrasctructurii computer vision, ajutând în acest fel la dezvoltarea destul de rapidă de aplicații sofisticate destul de rapid. Biblioteca OpenCV conține peste 500 de algoritmi, care se întind pe mai multe domenii , inclusiv inspecția produselor unei fabrici, imagistică medicală, securitate, interfață utilizator și robotică.

OpenCV a fost proiectat pentru a avea o eficiență de calcul crescută, un accent puternic punându-se pe aplicațiile în timp real. OpenCV este scris C, și optimizat pentru a putea folosi procesoarele multicore. Dacă se dorește optimizarea automată bazată pe arhitecturi Intel, se pot cumpăra bibliotecile Intel's Integrated Performance Primitives (IPP), care constau în rutine de nivel scăzut optimizate pentru o anumită arie de activitate. OpenCV utilizează automat biblioteca IPP în momentul rulării în cazul în care aceasta a fost instalată.

Computer Vision este transformarea de date de la o cameră foto sau o cameră video, fie intr-o decizie sau o nouă reprezentare. Toate aceste transformări sunt făcute cu scopul de a atinge unei ținte setate inițial. O noua reprezentare ar putea însemna captarea unei imagini cu ajutorul camerei video, și identificarea obiectelor circulare care se mișcă în fața camerei de luat vederi.

OpenCV este menit să ofere instrumentele de bază pentru rezolvarea problemelor de Computer Vision. În unele cazuri, funcțiile bibliotecă de nivel înalt vor fi suficiente pentru a rezolva probleme complexe ale Computer Vision. Chiar și atunci când nu este cazul, componentele de bază din bibliotecă sunt destul de complete pentru a permite crearea unei soluții complete pentru orice problemă individuală de Computer Vision. OpenCV are următoarele biblioteci:

CXCORE- Conține structuri de date, matrice algebrică, transformare de date, obiecte persistente, management al memoriei, tratarea erorilor, și încărcare dinamică de cod, precum și text, desen și matematică de bază.[13]

CV- Conține procesare de imagini, analiză structurată de imagini, mișcare și urmărire, recunoașterea formelor și calibrarea aparatului de fotografiat.

Machine Learning (ML)-mașini de învățare – Conține mai multe clustere, clasificarea și analiza funcțiilor de analiză de date.

HighGUI -Conține interfață grafică a utilizatorului GUI și stocare de imagine/video și recall.

CVCAM – Interfața cu aparatul foto/video

Haartraining – Cum să instruim un detector în cascadă, de obiecte.

5.3 Detalii despre implementarea aplicației

Ca și mediu integrat de elaborare pentru dezvoltarea aplicației am folosit Qt Creator IDE, împreună cu bibliotecile Qt și OpenCV. Cu ajutorul acestor instrumente, aplicația este foarte bine organizată, cross-platform, ușor de îmbunătățit. Aplicația este construită pe un cadru simplu, care captează imaginea video de la o cameră conectată prin usb la laptop, cu ajutorul transformatei Hough se face detecția obiectelor circulare în imagine, după care se afișează centrul cercului sub forma unui punct, folosindu-ne de Qtdesigner.

Qt Creator ne permite să vizualizăm aplicațiile proiectului foarte bine organizate, pe foldere și ne permite să găsim și să implementăm funcții noi. Figura 5.3 ne prezintă structura proiectului: forme (ecranul principal unde se listează detecția cercurilor de rază (x,y)), anteturi, fișiere sursă precum și un fișier numit traiectorie disertatie.pro , unde putem găsi toate informațiile despre surse, anteturi, bilioteci și resurse fiind incluse în proiectul numit "taiectorie disertatie".

În fișierele header și sursă vom găsi comentată fiecare funcție asrtfel încât să înțelegem cum funcționează aplicația și pentru a face o muncă mai ușoară dacă pe viitor se dorește extinderea acestei aplicații.

Figura 5.3: Structura aplicației

Pentru captura video am folosit de funția QApplication care se ocupă de captura de la camera video conectată la USB. Structura IplImage a fost moștenită de la biblioteca pe procesare a imaginii Intel, în care formatul este nativ. Open CV acceptă doar un subset de formate IplImage posibile, având anumite restricții, de care se ocupă un ROI[13] (region of interes) diferit. Funcțiile Open CV solicită ca dimensiunea imaginii sau dimensiunea ROI de la toate imaginile sursă și destinație să se portrivească exact. Pe de altă parte , biblioteca Intel de procesare a imaginii, prelucrează zona de intersecție dintre sursă și destinație, permițându-le să varieze independent.

Figura 5.4: main.cpp

Funcția cvGrabF rame[13] preia cadrul video de la camera video externă, fiind stocat intern. Scopul acestei funcții este acela de a prelua cadre rapid, astfel încât sincronizarea poate să apară dacă este necesar ca imaginile preluate să se citească simultan. Cadrele preluate nu sunt expuse, deoarece acestea sunt stocate într-un format comprimat.Această funcție returnează 1 pentru un cadru preluat și 0 în caz contrar. Pentru preluarea cadrului se folosește biblioteca cvRetrieveF rame. Funcția cvReleaseCapture eliberează structura cvcapture alocată de către CaptureFromCAM. In figura 5.4 putem vedea modul de folosire al acestor funcții.

Pentru calcularea distanței dintre două obiecte detectate, în vederea estimării rapidității obiectului, am folosit ecuația dreptei

Figura 5.5: Calculul distanței dintre puncte

Pentru detecția obiectelor circulare am contruit funcția detectCicles. Stocarea memoriei este o structură de nivel scăzut folosită pentru a stoca dinamic structurile de date, cum ar fi secvențele, contururi cum este și cazul nostru, în care se stochează contururi de cercuri. Practic, după cum se observă și în cod se creează un nou spațiu de stocare. Funcția cvCvtColor convertește matricea de pixeli de intrare dintr-un spațiu de culoare la altul. Cu ajutorului cvSmooth putem elimina zgomotul din imagine. Ne folosim de funcția cvHoughCircles și funcția CV HOUGH GRADIENT pentru a detecta și a afla coordonatele cercului {in imagine.

Figura 5.6: Detectarea de cercuri Hough

După detecția cercurilor ne interesează prelucrarea datelor primite, pentru aceasta am implementat algoritmul de mai jos (figura 5.7). Pentru fiecare cerc gasit s-a trasat un punct pe grafic urmând să se unească aceste puncte astfel stabilindu-se traiectoria obiectului detectat. În cazul în care acest obiect a părăsit cadrul, am calculat ultimul lui punct de pe grafic și noul punct astef să se poată stabili ușor dacă pe linia de producție sunt ceva probleme, astfel putânduse acționa imediat în cazul unei defecțiuni, la următorul obiect detectat schimbându-se culoare astfel încât traicetoriile să se poată distinge cu ușurință. În cazul în care se observă o creștere a vitezei între cele doua stări ale obiectului circular , înseamnă că avem o problemă pe linia de producție având în vedere ca timpul de producție e stabilit anterior si durata de încărcare a benzii nu poate depăși o diferență de timp mai mare de 30 de pixeli între obiecte , atunci acest fault este marcat prin culoarea portocaliu.

Figura 5.7: Algoritmul de listare a punctelor detectate

5.4 Partea practică a aplicației

După cum spuneam și în capitolele anterioare, subiectul pe care aș dori să îl dezbat la partea practică ar fi problemele cu care se confruntă o linie de producție care trebuie să fabrice obiecte circulare, de exemplu o fabrica de cauciucuri, anvelope sau producătoare de medicamente.

În oricare din cazurile prezentate mai sus ne interesează ca aceste obiecte să fie rotunde, deoarece nu s-ar încadra standardelor. Dacă un obiect nu a fost detectat înseamna că sunt ceva probleme la fabricarea acestuia și întreaga linie de producție trebuie oprită deoarece costurile ar depășii profitul.

În figura de mai jos se poate vizualiza detecția unui cerc/obiect circular, cât și orientarea acestuia.

Figura 5.8: Detecția obiectului circular

Aplicația este gândită în așa fel încât tehnicianul să poată observa în procesul de producție o problemă astfel putând reduce pagubele unei producții cu defecte.

Fiecare obiect este evidențiat printr-un cerc de culoare galbenă și se arată și direcția acestuia față de centru printr-o linie de culoare neagră. Parametrii obiectelor detectate sunt listate în debug, astfel putându-se vizualiza numărul de obiecte detectate și poziția acestora în imagine.

Figura 5.9: Listarea coordonatelor cercului și a numărului cercului detectat

Figura 5.10: Traiectoria cercului obiectelor detectate

Stabilirea traiectoriei se face prin unirea punctelor detectate ale cercului, inițializarea unei noi traiectorii făcându-se doar în cazul în care centrul cercului părăsște cadrul, urmând să fie initțializat cu noile coordonate la reintrarea în cadru.

Dupa cum se observă dacă distanța dintre două puncte este mare, atunci se pare că o anumită problemă a apărut și trebuie remediată, fiind senmalizată prin culoarea portocaliu. Se observă că după ce obiectul curent a părăsit spațiul, o nouă traiectorie este creată pentru cel de-al doilea obiect detectat, fiind diferențiate prin culori diferite.

Capitolul 6 Concluzii

In timp ce dezvoltam această aplicație am realizat că acest lucru poate fi doar un început în domeniul vast al procesării de imagini, care este un domeniu unde evoluția și înbunătățirile aduse se pot observa de la o zi la alta. A fost un început bun doarece partea de matematică m-a făcut să înteleg mai bine partea de decție din informatică, atât pe partea de procesare a imaginii video cât și partea de detecție în imagini.

Cu softul creat am încercat să realizez o aplicație care necesită resurse destul de reduse, chiar daca folosește prelucrarea de imagini video, și care poate fi cu succes folosită de către tehnicienii care se ocupă de monitorizarea anumitor obiecte circulare într-o fabrică. Această aplicație pot spune că este o punte între funcțiile bibliotecii OpenCV-ului și interfața grafică a Qt-ului (biblioteci și IDE). Pot spune că rezultatul este o aplicație care se va putea folosi într-o varietate de domenii.

Pot spune ca am întâmpinat mici probleme la detecție , apariția ocluziilor, dar acest lucru nu m-a împiedicat să îmi dedic mai mult timp studiului pentru a avea o aplicație software care să se poată folosi cu success de către utilizatori cu cerințe minime ale părții hardware a sistemului.

Studiul mai multor metode de detecție pot spune că m-a ajutat să pot face o comparație între metodele de detecție existente și să pot alege pe cea care am considerat-o că ar fi cea mai bună de implementat pentru cazul meu de detecție a obiectelor circulare.

Diferențele dintre algoritmii de detecție sunt destul de variate, de la detecția obiectului țintă pe care îl detectăm cu ajutorul șabloanelor folosind algoritmul Kanade- Lucas-Tomasi (KLT), detectarea țintei pe baza histogramelor de culoare, bazându-se foarte mult pe optimizarea recursivității, mean shift, toți bazându-se pe aceleași metode de calcul reduse ca și cost.

Bibliografie

[1] Henrik Brik, Lise Grevekop-Castenskiold, Jakob Lind. Cicle detection image analysis using the Dynamic Generalized Hough Transform .Institute of Electronic System, Aalborg University, Denmark, January 17, 1995.

[2] T. DOrazioa, C. Guaragnella, M. Leo, A. Distante. A new algorithm for ball recognition using circle Hough transform and neural classifier. ISSIACNR, Institute of Intelligent Systems for Automation, National Research Council, 166/5, Amendola, Bari 70126, Italy, 19 June 2003, Pattern Recognition 37 (2004),393-408

[3] Mohamed Rizon, Haniza Yazid, Puteh Saad, Ali Yeon Md Shakaff. Object Detection using Circular Hough Transform, American Journal of Applied Sciences 2 (12): 1606-1609, 2005.

[4] Hafizal Yazid, Haniza Yazid, Mohd Harun, Shukri Mohd, A. Aziz Mohamed. Circular discontinuities detection in welded joints using Circular Hough Transform.ScienceDirect,NDT&E International 40 (2007) 594-601

[5] Svein OlavKrogli , Henning Dypvik. Automatic detection of circular outlines inregional gravity and aeromagnetic data in the search for impact structure candidates. Computers & Geosciences, 36 (2010) 477-488.

[6] Chih-Jen Wu, Wen-Hsiang Tsai.Location estimation for indoor autonomous vehicle navigation by omni-directional vision using circular landmarks on ceilings, Robotics and Autonomous Systems 57 (2009) 546-555.

[7] T. Garlipp, C.H. Mueller. Detection of linear and circular shapes in image analysis, Computational Statistics & Data Analysis 51 (2006) 1479-1490 .

[8] E. R. DAVIES . MACHINE VISION Theory.Algorithms.Practicalities.Elsevier Third Edition,Royal Holloway, University of London 2003

[9] ary Bradski and Adrian Kaehler. Learning OpenCV, Published by OReilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 95472, 2008

[10] Robert Laganiere.OpenCV 2 Computer Vision Application Programming Cookbook, Packt Publishing,32 Lincoln Road,Olton,Birmingham, B27 6PA, UK.May 2011.

[11] Andrea Cavallaro, and Emilio Maggio.VIDEO TRACKING.Theory and Practice, Wiley, John Wiley & Sons, Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom, 2011

[12] Oliver Faugeras and Quang-Tuan Luong .The Geometry of Multiple Images. London: MIT press, 2001

[13] Open Source, Computer Vision,Library,Reference Manual,Intel Corporation, December 8,2000

[14] Rafael C. Gonzalez and Richard E Woods. Digital Image Processing-Third Edition, Pearson Education, Inc.2008