ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE Fakulta elektrotechnická Katedra kybernetiky
DIPLOMOVÁ PRÁCE Automatické vyhodnocování algoritmů počítačového vidění
2011
Vypracoval: Bc. Luboš Jirák Vedoucí práce: Ing. Karel Zimmermann, Ph.D.
i
ii
Poděkování Chtěl bych poděkovat především vedoucímu práce Ing. Karlovi Zimmermannovi, Ph.D. za cenné připomínky a rady k této diplomové práci. Dále bych chtěl poděkovat také rodičům a všem ostatním, kteří mě podporovali ve studiu.
iii
iv
Anotace Tato diplomová práce se zabývá způsoby vyhodnocování kvality algoritmů pro detekci a sledování, metrikami pro měření vzdálenosti, způsoby vhodného určování korespondencí a zkoumá různé metriky podle kterých můžeme algoritmy mezi sebou porovnávat. V programu Matlab jsou implementovány metriky MOTA a MOTP a také vizualizace výstupů pro rychlé odhalování problémových míst vyhodnocovaných algoritmů. V poslední části je implementováno několik metod pro automatické získávání ground truth s využitím již existujícího detektoru lidí.
Summary This thesis investigates methods for evaluating the quality of algorithms for detecting and tracking, metrics for measuring distances, appropriate ways of identifying correspondences, and examines various metrics by which we can compare algorithms for detecting and tracking. In Matlab, we implement metrics MOTA and MOTP and visualization of outputs for rapid detection of evaluated algorithms weaknesses. In the last section we implemented some methods for automatic acquisition of ground truth using the already existing human detector.
Obsah Seznam obrázků
viii
Seznam tabulek
ix
1 Úvod 1.1 Seznámení s problematikou . . . . . . . . . . . . . . 1.2 Základní pojmy . . . . . . . . . . . . . . . . . . . . 1.2.1 Ground truth . . . . . . . . . . . . . . . . . 1.2.2 Sekvence, snímek . . . . . . . . . . . . . . . 1.2.3 Objekty, hypotézy, detekční okno . . . . . . 1.2.4 Falešně pozitivní, minuté, skutečně pozitivní 1.2.5 Korespondence objektu a hypotézy . . . . . 1.2.6 Záměna . . . . . . . . . . . . . . . . . . . . 1.2.7 dodefinovat metriku . . . . . . . . . . . . . 1.3 Požadované vlastnosti sledovacích algoritmů . . . .
. . . . . a . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . skutečně . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . negativní . . . . . . . . . . . . . . . . . . . . . . . .
2 Metriky pro měření kvality algoritmů pro detekci a sledování 2.1 Základní jednoduché metriky . . . . . . . . . . . . . . . . . . . . 2.2 ETISEO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Metriky pro detekci objektů . . . . . . . . . . . . . . . . . 2.2.2 Metriky pro lokalizaci objektů . . . . . . . . . . . . . . . . 2.2.3 Metriky pro sledování objektů . . . . . . . . . . . . . . . . 2.2.4 Metriky pro klasifikaci objektu a rozpoznání události . . . 2.3 CLEAR MOT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Návrhová kritéria . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Vyhodnocovací procedura . . . . . . . . . . . . . . . . . . v
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
1 1 1 1 3 3 4 4 7 8 8
. . . . . . . . . .
10 10 11 11 12 13 14 14 14 14 15
OBSAH
2.4
2.5 2.6
vi
2.3.4 Přiřazovací procedura . . . . . . . . . . . . 2.3.5 MOTA . . . . . . . . . . . . . . . . . . . . . 2.3.6 MOTP . . . . . . . . . . . . . . . . . . . . . Metriky SFDA, ATA . . . . . . . . . . . . . . . . . 2.4.1 Sequence Frame Detection Accuracy(SFDA) 2.4.2 Averate Tracking Accuracy(ATA) . . . . . . Pixelové . . . . . . . . . . . . . . . . . . . . . . . . Vyhodnocení . . . . . . . . . . . . . . . . . . . . .
3 Implementace v matlabu 3.1 Vstupy . . . . . . . . . . . . . . . . . . . . 3.2 Funkce evaluate . . . . . . . . . . . . . . . 3.2.1 Funkce calculateDist . . . . . . . . 3.2.2 Mapování korespondencí do pole M 3.3 Vizualizace . . . . . . . . . . . . . . . . .
. . . . .
. . . . .
4 Automatické získávání ground truth 4.1 Detektor lidského těla . . . . . . . . . . . . . 4.2 Pokusy o vylepšení detekce . . . . . . . . . . . 4.2.1 Odstranění duplikovaných detekcí . . . 4.2.2 Odstranění detekčních oken na pozadí 4.2.3 Přidání nových snímků . . . . . . . . . 4.3 Experimenty . . . . . . . . . . . . . . . . . . .
. . . . .
. . . . . .
. . . . .
. . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
. . . . .
. . . . . .
. . . . . . . .
16 16 17 18 18 19 20 20
. . . . .
22 22 23 24 24 25
. . . . . .
28 28 28 29 30 32 33
5 Závěr
35
Literatura
36
A Obsah přiloženého cd
38
Seznam obrázků 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 2.1 2.2 2.3 3.1
3.2
Detekční okno, vyznačeno modře . . . . . . . . . . . . . . . . . . . . . . . Skutečně pozitivní, falešně pozitivní, falešně negativní, šedivě objekt, modře detekční okno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ukázky metrik, v (a) jsou modře a zeleně zobrazena detekční okna, v (b) jsou modře zobrazena detekční okna, zeleně jejich průnik . . . . . . . . . . Ukázka chování ρ1 při různém procentu překryvu . . . . . . . . . . . . . . Graf závislosti ρ(A, B) na procentu překrytí . . . . . . . . . . . . . . . . . Ukázka chování ρ1 při překryvu se čtvrtinovým oknem . . . . . . . . . . . Záměna, červeně a černě jsou vyznačené objekty, zeleně a modře, detekční okna. V čase t+2 došlo k záměně. . . . . . . . . . . . . . . . . . . . . . . . Diagram fugování metriky . . . . . . . . . . . . . . . . . . . . . . . . . . . Roztříštění při detekci objektu, modře je vyznačené detekční okno objektu, červeně, zeleně a šedivě detekční okna hypotéz . . . . . . . . . . . . . . . Sloučení více objektů pod jednu hypotézu, modře je vyznačené detekční okno hypotézy, zeleně detekční okna objektů . . . . . . . . . . . . . . . . Intuitivní určování korespondence . . . . . . . . . . . . . . . . . . . . . . . Ukázka z výstupu vizualizace, vlevo nahoře je černě zobrazené číslo snímku t, zelené číslo vlevo nahoře je počet objektů v ground truth, modré číslo vlevo nahoře je počet hypotéz, červeně je vlevo nahoře na jednom řádku zobrazeno identifikační číslo objektu a identifikační číslo hypotézy, které spolu v daném snímku korespondují . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Minutý a korespondující objekt. Zeleně vyznačené detekční okna jsou objektů, růžově je označená korespondence mezi hypotézou a objektem. Objekt č.2 je minutý, asi proto, že je částečně schovaný za keřem, objekt č.188 koresponduje s hypotézou č.3. . . . . . . . . . . . . . . . . . . . . . . . . . vii
4 5 6 7 8 8 9 9
12 13 15
26
27
SEZNAM OBRÁZKŮ
3.3
4.1 4.2 4.3 4.4 4.5 4.6
Falešně pozitivní a nalezený objekt. Zeleně vyznačené detekční okno je objekt(ground truth), růžově je označená korespondence mezi hypotézou a objektem, modře nepřiřazená(falešná) hypotéza. Hypotéza č.7250 je falešná, objekt č.7191 koresponduje s hypotézou č.24 . . . . . . . . . . . . . . . . . Detekční okna detektoru lidí, pro různá nastavení parametru THRESHOLD Odstranění duplikovaných detekčních oken, vlevo všechny, vpravo po odstranění duplikovaných . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Určení pozadí a popředí snímku, bílé plochy odhadnuté jako popředí, černé jako pozadí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Odstranění detekčních oken v pozadí, vlevo všechny, vpravo po odstranění oken v pozadí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pokus o detekování nových oken . . . . . . . . . . . . . . . . . . . . . . . . Křivky z výstupu použitých metod, 1) Výstup z detektoru, 2) Po odstranění duplikátů, 3) Po odstranění duplikátů a snímků v pozadí, 4) Po odstranění duplikátů, snímků v pozadí a pokusu o přidání oken . . . . . . . . . . . . .
viii
27 29 30 31 32 33
34
Seznam tabulek 1.1 1.2
Tabulka důležitých proměnných . . . . . . . . . . . . . . . . . . . . . . . . Kontingenční tabulka detekce . . . . . . . . . . . . . . . . . . . . . . . . .
3.1
Struktura vstupu, ke každému snímku jsou přiřazeny detekční obdélníky s parametry id, pos, rec, rem . . . . . . . . . . . . . . . . . . . . . . . . . . Výsledek Munkresova algoritmu, čísla v tabulce reprezentují vzdálenost, Inf značí ”nekonečné” vzdálenosti . . . . . . . . . . . . . . . . . . . . . . . . .
3.2
ix
2 5
23 24
Kapitola 1 Úvod 1.1
Seznámení s problematikou
Cílem této diplomové práce je shrnout metody pro vyhodnocování algoritmů pro počítačové vidění, zejména pro detekci a sledování lidských postav ve videosekvencích. Ohodnocení výkonnosti je velmi důležité, pro rozhodnutí zda je některý algoritmus lepší než jiný.V případě sledování jednoho objektu je vyhodnocení lepšího algoritmu jednodušší viz [6], v případě sledování více objektů by metrika měla srozumitelně ukazovat celkovou výkonost algoritmu a pokrývat několik různých kriterií. V dnešní době, kdy výkon počítačů umožňuje zpracování a vyhodnocování snímků z kamer v reálném čase a vzniká mnoho algoritmů pro detekci, je porovnávání a vyhledávání nejlepších algoritmů velmi aktuální téma. Algoritmy jsou využitelné v mnoha aplikacích, v automobilovém průmyslu, například upozorněním na chodce, při automatické indexování osob ve virtuálních systémech, v robotice, při koordicnaci člověka s robotem, pro zjednodušené vyhodnocování záznamů z bezpečnostních kamer.
1.2 1.2.1
Základní pojmy Ground truth
Většina vyhodnocování je založená na porovnávání výstupu z algoritmu s tzv. ground truth. Existují ale i pokusy o vyhodnocování bez použití ground truth, např. [10]. Ground truth jsou vyhodnocovaná obrazová data(obecně jakákoliv data), již obohacená o znalost pravdy, tj. informacemi o tom, co se v obrazech kde nachází, jaké to má vlastnosti, rozměry 1
1.2. ZÁKLADNÍ POJMY Tabulka 1.1: Tabulka důležitých proměnných t n oi hj oti htj A, B xA , yA xB , yB ρ(A, B) ρ1 (A, B) ρ1 (oi , hj ) ρ1n (A, B) PSP PF P PSN PF N ct mr pr fa F Score Mt M OT A M OT P zt mt f pt gt kt F DA kt No Nh SF DA ST DA AT A P za(t) d Pz (t) M p(t)
snímek s číslem t celkový počet snímků v sekvenci objekt číslo i hypotéza číslo j objekt oi ve snímku t hypotéza hj ve snímku t detekční okna A a B souřadnice středu detekčního okna A souřadnice středu detekčního okna B funkce euklidovské vzdálenosti mezi detekčními okny A a B, viz rovnice 1.1 vzdálenostní funkce překryvu detekčních oken A a B, viz rovnice 1.2 vzdálenostní funkce překryvu detekčních oken objektu oi a hypotézy hj . ρ1n (A, B) = 1 − ρ1 (A, B) počet skutečně pozitivních počet falešně pozitivních počet skutečně negativních počet falešně negativních míra skutečně pozitivních, nebo také citlivost, viz rovnice 2.1 míra minutých, viz rovnice 2.2 přesnost, viz rovnice 2.3 míra falešných alarmů(hypotéz), viz rovnice 2.4 kombinace pr a ct , viz rovnice 2.5 množina korespondencí (oi , hj ) ve snímku t Metrika multiple object tracking accuracy, viz 2.7 Metrika multiple object tracking precision, viz 2.11 Počet zaměněných ve snímku t Počet minutých ve snímku t Počet falešně pozitivních ve snímku t Počet objektů ve snímku t Počet korespondencí ve snímku t Frame Detection Accuracy viz rovnice 2.12 počet hypotéz ve snímku t počet unikátních objektů v celé sekvenci počet unikátních hypotéz v celé sekvenci Sequence Frame Detection Accuracy, viz rovnice 2.14 Sequence Track Detection Accuracy viz rovnice 2.17 Average Tracking Accuracy, viz rovnice 2.18 součet matic Hcˇ(t), Hz (t) a Hm (t) pro snímek t délka klouzavého průměru průměrná hodnota pozadí snímku t matice nul a jedniček, která znázorňuje strukturu pozadí pro snímek t
2
1.2. ZÁKLADNÍ POJMY
3
atd. Například informacemi o přítomnosti člověka, o velikosti 50 pixelů, na souřadnicích (x,y). Jednotná norma na to, co by ground truth měla obsahovat, není a tak je tomu často tak, že skoro každý používá jiný formát. Dá se říci, že ground truth je ten nejlepší možný výstup, který v ideálním případě požadujeme od algoritmu. Nepředpokládá se, že by algoritmus byl schopný podávat lepší výsledky než jsou v ground truth, ale může se to stát pokud budeme mít nekvalitní ground truth. Ground truth je obvykle získávána manuálně, např. kreslením detekčních oken okolo objektů nebo vyznačováním hranic objektů. Manuální získávání ground truth je ohromně časově náročná a pro člověka ubíjející práce.Různí lidé budou generovat různou ground truth, v závislosti nejen na svých schopnostech, ale i v závislosti na svých zkušenostech a na tom, jak každý pochopili zadané instrukce. Proto je dobré získat stejnou ground truth od více lidí a provést zprůměrování. Toto bylo ukázáno například v článku [11], zabývajícím se lidskou spolehlivostí při generování ground truh.
1.2.2
Sekvence, snímek
Běžná videokamera funguje na principu snímání obrázků. Snímkem se v této práci rozumíme jeden výstupní obrázek z běžné kamery, typicky v nějakém standardním počítačovém formátu. Sekvencí je myšlen záznam skládající se z po sobě následujících snímků, jehož rychlost je udávaná počtem snímků za sekundu. Písmeno t značí snímek číslo t v sekvenci, písmeno n značí celkový počet snímků v sekvenci.
1.2.3
Objekty, hypotézy, detekční okno
To co je uloženo v ground truth budeme pro účely této práce nazývat objekt. Značka oi znamená objekt číslo i, značka oti znamená objekt číslo i ve snímku t. Objekt má různé vlastnosti, typicky souřadnice a velikost detekčního okna, unikátní identifikační číslo. Detekční okno vypadá tak, jak je modře vyznačeno na obr. 1.1, v tomto obrázku hranice detekčního okna těsně obepínají objekt. Tato vlastnost by se očekávala, ale vzhledem k nepřesnostem to nebývá pravidlem. V naší implementaci má detekční okno čtyři parametry: souřadnici levého horního rohu v osách x a y, a jeho šířku podél os x a y. Výstup z algoritmu budeme nazývat hypotézou. Značka hj znamená hypotézu číslo j, značka htj znamená hypotézu číslo j ve snímku t. Hypotéza má stejné vlastnosti jako objekt, protože při vyhodnocování dochází k porovnávání objektu s hypotézou.
1.2. ZÁKLADNÍ POJMY
4
Obrázek 1.1: Detekční okno, vyznačeno modře
1.2.4
Falešně pozitivní, minuté, skutečně pozitivní a skutečně negativní
Skutečně pozitivní, skutečně negativní, falešně pozitivní, falešně negativní, jsou typické výrazy hojně využívané při jakékoliv úloze vyhodnocování hypotéz(zde myšleno obecně), ať už v umělé inteligenci, lékařství, či právě počítačovém vidění. Jaký mají význam v této práci vysvětlujeme v následujícím přehledu: • Skutečně pozitivní(True positive) - znamená že hypotéza hj koresponduje s objektem oi (co se tím myslí viz dále v 1.2.5, prozatím to znamená že se jejich detekční okna téměr úplně překrývají), viz obr. 1.2a. • Falešně pozitivní(False positive) - znamená že hypotéza hj nekoresponduje s žádným objektem(opět viz dále v 1.2.5), viz obr. 1.2b. • Minuté, neboli falešně negativní(False negative) - znamená že objekt oi nekoresponduje s žádnou hypotézou hj , viz obr. 1.2c. • Skutečně negativní(True negative) - má význam pokud vyhodnocujeme obraz po jednotlivých pixelech(viz později v 2.5), z našeho pohledu objektů a hypotéz jsou to v podstatě všechna místa v obraze kde se nevyskytuje ani objekt, ani hypotéza. Vzájemné vztahy jsou přehledně zobrazeny v tabulce 1.2.
1.2.5
Korespondence objektu a hypotézy
Přirozeně budeme za hypotézy korespondující s objektem považovat takové, které mají k objektu nejmenší vzdálenost. Objekty bez korespondence budeme považovat za minuté,
1.2. ZÁKLADNÍ POJMY
5
Tabulka 1.2: Kontingenční tabulka detekce Hypotézy (výstup z algoritmu) Hypotéza je Hypotéza není
Objekty z ground truth Objekt existuje Objekt neexistuje skutečně pozitivní(SP ) falešně pozitivní(FP ) falešně negativní(FN ) skutečně negativní(SN )
(a) Skutečně pozitivní
(b) Falešně pozitivní
(c) Falešně negativní
Obrázek 1.2: Skutečně pozitivní, falešně pozitivní, falešně negativní, šedivě objekt, modře detekční okno hypotézy bez korespondence budeme považovat za falešně pozitivní. Pro určení nejbližších hypotéz a objektů potřebujeme definovat vzdálenostní metriku, pomocí které budeme zjišťovat a porovnávat vzdálenost mezi hypotézou a objekty. Vzdálenost se dá měřit mnoha způsoby, rozlišujeme kde budeme vyhodnocovat, tj. ve 2D nebo 3D a jakou použijeme vzdálenostní metriku (L1 , L2 , . . .). V této práci je využíváno měření Euklidovské vzdálenosti, neboli L2 metrika. Měříme vzdálenost středů detekčních oken v pixelech, nebo vzdálenost mezi těžišti objektů a hypotéz. Viz obr. 1.3a, kde je euklidovská vzdálenost středů vyznačena oboustrannou šipkou. Euklidovská vzdálenost je počítána podle vzorce: ρ(A, B) =
√ (xA − xB )2 + (yA − yB )2 ,
(1.1)
kde (xA , yA ) a (xB , yB ) jsou souřadnice středů detekčních oken A a B. Stejným způsobem je vzdálenost počítána se souřadnicemi těžišť objektů a hypotéz. Problém ale je, že určení těžiště některých objektů může být obtížné a nemusí pro to existovat žádný postup.
1.2. ZÁKLADNÍ POJMY
6
Jako další využitá metrika je měření překryvu oken, dle vzorce ρ1 (A, B) =
|A ∩ B| , |A ∪ B|
(1.2)
kde A je plocha jednoho detekčního okna a B je plocha druhého detekčního okna. V obr. 1.3b je naznačen uvedený vzorec jako poměr mezi zelenou plochou a celkovým součtem modré a zelené plochy.
35
35
30
30
25
25
20
20
15
15
10
10
5
5
0
0
5
10
15
20
25
(a) Euklidovská vzdálenost
0
0
5
10
15
20
25
(b) Překrývání detekčních oken
Obrázek 1.3: Ukázky metrik, v (a) jsou modře a zeleně zobrazena detekční okna, v (b) jsou modře zobrazena detekční okna, zeleně jejich průnik Rozeberme ještě hlouběji chování metriky v rovnici 1.2, které není úplně intuitivní. Metrika nabývá hodnot od 0 do 1, přičemž úplný překryv má nejvyšší hodnotu, tj. maximálně 1 a žádný překryv má nejmenší hodnotu, tj 0. Při používání je dobré si uvědomit, že výsledná vzdálenost v závislosti na procentu překryvu dvou oken není lineární, viz obrázek 1.4 a graf obr. 1.5. Neboli okna co mají mezi sebou vzdálenost 0,5 až 1, se překrývají nikoliv více než 50% jak by bylo intuitivní, ale ve skutečnosti více než 66%. Zajímavé také je, že maximální hodnoty přiblížení lze dosáhnout pouze u stejně velkých oken, nestejně velká okna k sobě nikdy nebudou mít nejmenší vzdálenost, viz obrázek 1.6. Je důležité určit vzdálenostní práh, což je maximální vzdálenost pro kterou ještě hypotéza odpovídá objektu. Stanovení tohoto prahu není jednoduché a jeho nastavení ovlivňuje celkové výsledky. Hodnota prahu bude individuální pro různá prostředí a aplikace, je vhodné ji nastavovat vzhledem k požadované přesnosti. Jak bylo rozebráno výše, metrika překryvu se chová odlišně od více intuitivní, euklidovské a při nastavování prahu je nutné
1.2. ZÁKLADNÍ POJMY
7
30
30
30
25
25
25
20
20
20
15
15
15
10
10
10
5
5
5
0
0
5
10
15
20
25
30
35
0
0
5
(a) 0%, ρ1 = 0
10
15
20
25
30
35
0
(b) 0%, ρ1 = 0 30
30
25
25
25
20
20
20
15
15
15
10
10
10
5
5
5
0
0
5
10
15
20
25
30
. (d) 50%, ρ1 = 0, 3333
35
0
5
10
15
20
25
5
10
15
20
25
30
35
. (c) 25%, ρ1 = 0, 1429
30
0
0
30
(e) 75%, ρ1 = 0, 6
35
0
0
5
10
15
20
25
30
35
(f) 100%, ρ1 = 1
Obrázek 1.4: Ukázka chování ρ1 při různém procentu překryvu brát v potaz i chování pro rozdílné velikosti detekčních oken. Hypotéza a objekt tedy korespondují(jsou považovány za shodné), pokud je ρ(oi , hj ) < zvolený práh, respektive ρ1 (oi , hj ) > zvolený práh. V opačném případě nekorespondují(nejsou považovány za shodné). Značením ρ(oi , hj ), přeneseně myslíme vzdálenost detekčního okna objektu i a detekčního okna hypotézy j.
1.2.6
Záměna
Záměna nastává, pokud se sledovací algoritmus v některém snímku splete. Neboli hypotézou(identifikovanou v celé sekvenci unikátním číslem) začne detekovat jiný objekt než detekoval doposud. Demonstrace jak vypadá záměna v sekvenci je vidět na obrázku 1.7. Počet záměn ve snímku t značíme zt .
1.3. POŽADOVANÉ VLASTNOSTI SLEDOVACÍCH ALGORITMŮ
8
1 0.9 0.8
ρ1(A,B) [−]
0.7 0.6 0.5 0.4 0.3 0.2 0.1 0
0
20
40 60 Prekrytí A a B [%]
80
100
Obrázek 1.5: Graf závislosti ρ(A, B) na procentu překrytí
30
30
30
25
25
25
20
20
20
15
15
15
10
10
10
5
5
5
0
0
5
10
15
20
25
30
35
0
0
(a) ρ1 = 0
5
10
15
20
25
. (b) ρ1 = 0, 1111
30
35
0
0
5
10
15
20
25
30
35
(c) ρ1 = 0, 25
Obrázek 1.6: Ukázka chování ρ1 při překryvu se čtvrtinovým oknem
1.2.7
1.3
dodefinovat metriku
Požadované vlastnosti sledovacích algoritmů
Pokud chceme sledovací algoritmy hodnotit, je dobré si určit co od nich vlastně očekáváme. Jaké vlastnosti jsou podstatné a co by měl umět ideální sledovací algoritmus. Takže se pokusíme nadefinovat vlastnosti ideálního sledovacího algoritmu. Ideální sledovací algoritmus by měl umět dobře sledovat, čili vygenerovat hypotézy, které budou korespondovat s objekty z ground truth, pro každý snímek t, v celé sekvenci. Předpokládá se robustnost, neboli že si poradí s měnícím se prostředím, jako je změna světelných podmínek(slunečno, zataženo), déšť, atd. Měl by také umět dobře identifikovat, tím je myšleno, že k jednomu identifikačnímu číslu objektu v celé sekvenci, bude mít hypotéza také jenom jedno identifikační číslo.Dále by měl dobře určovat aplikačně specifické vlastnosti
1.3. POŽADOVANÉ VLASTNOSTI SLEDOVACÍCH ALGORITMŮ
9
2
1
t 1
2 t+1 1
2
t+2 1 2 t+3
Obrázek 1.7: Záměna, červeně a černě jsou vyznačené objekty, zeleně a modře, detekční okna. V čase t+2 došlo k záměně.
objektů, jako je například rychlost. A poslední důležitou vlastností je, že by měl být rychlý. Algoritmus pak budeme hodnotit jak je naznačeno v diagramu na obr. 1.8. Hypotézy
Vstup
Algoritmus
Ohodnocení Metrika
Objekty Ground truth
Obrázek 1.8: Diagram fugování metriky
Kapitola 2 Metriky pro měření kvality algoritmů pro detekci a sledování 2.1
Základní jednoduché metriky
Označme si PSP , jako počet skutečně pozitivních, PF P , jako počet falešně pozitivních, PSN , jako počet skutečně negativních a PF N , jako počet falešně negativních. Typické základní metriky jsou tyto: • Míra skutečně pozitivních, nebo také citlivost: PSP . PSP + PF N
ct =
(2.1)
Citlivost měří kolik bylo korespondencí mezi objektem a hypotézou v poměru ke všem objektům. Nejlepší výsledek je 1, tj. nejsou žádné nekorespondující objekty, nejhorší je 0. • Míra minutých mr =
PF N . PF N + PSP
(2.2)
Míra minutých, komplementární k ct , měří kolik bylo nekorespondujících objektů v poměru ke všem objektům. Nejlepší výsledek je 0, tj. nejsou žádné nekorespondující objekty, nejhorší je 1. • Přesnost pr =
PSP . PSP + PF P 10
(2.3)
2.2. ETISEO
11
Přesnost měří kolik bylo korespondencí mezi objektem a hypotézou v poměru ke všem hypotézám. Nejlepší výsledek je 1, tj. nejsou žádné nekorespondující hypotézy, nejhorší je 0. • Míra falešných alarmů(hypotéz): fa =
PF P . PSP + PF P
(2.4)
Míra falešných alarmů, komplementární k pr , měří kolik bylo nekorespondujících hypotéz v poměru ke všem hypotézám. Nejlepší výsledek je 0, tj. nejsou žádné nekorespondující hypotézy, nejhorší je 1. • F-Score, definovaná jako: F Score =
2 × pr × ct (pr + ct )
(2.5)
Dává do souvislosti přesnost a citlivost, výsledkem je jedno číslo v rozmezí 0-1, 1 je nejlepší výsledek, 0 je nejhorší.
2.2
ETISEO
Metriky z projektu ETISEO(Evaluation du Traitement et de Interpretacion de Sequences vidEO) [5]. Metriky projektu snaží pokrýt celou škálu aspektů sledovacích algoritmů, jejich nevýhodou je velké množství metrik, což činí vyhodnocování komplikovaným. ETISEO pro vyhodnocování svých metrik využívá přesnost, viz rovnice 2.3, citlivost, viz rovnice 2.1 a F-Score, viz rovnice 2.5.
2.2.1
Metriky pro detekci objektů
Celkem čtyři metriky porovnávající kvalitu detekce: • Metrika ”počet objektů” - Vypočítává kolik nalezených hypotéz koresponduje s objekty, neboli počítá skutečně pozitivní. • Metrika ”prostor objektu” - Funguje na úrovni pixelů, počítá kolik pixelů, příslušejících objektům, koresponduje s hypotézami. Nevýhodou je, že větší objekty mají větší roli, protože pokrývají více pixelů.
2.2. ETISEO
12
• Metrika roztříštění - Vypočítává roztříštěnost vygenerovaných hypotéz, nastává v případě několika hypotéz pro jeden objekt. Pro detekci takových hypotéz si zavádí jednoduchou metriku: |A ∩ B| ρ2 (A, B) = , (2.6) |B| kde A je plocha detekčního okna objektu, B detekčního okna hypotézy. Tato funkce má hodnotu 1, pokud se hypotéza nachází uvnitř detekčního okna objektu, viz obr. 2.1. Metrika roztříštění ve skutečnosti takto také odhaluje vícenásobnou detekci stejného objektu, takže je také možné jí využít k odstraňování vícenásobných detekčních chyb. • Metrika sloučení - Vypočítává kolikrát došlo k překrytí jednoho objektu více hypotézami. Většinou nastává v případech pokud se objekty z ground truth vyskytují blízko sebe, což může být způsobeno například nevhodným úhlem kamery, viz obr. 2.2.
30
25
20
15
10
5
0
0
5
10
15
20
25
Obrázek 2.1: Roztříštění při detekci objektu, modře je vyznačené detekční okno objektu, červeně, zeleně a šedivě detekční okna hypotéz
2.2.2
Metriky pro lokalizaci objektů
Jedna metrika hodnotící přesnost detekce polohy:
2.2. ETISEO
13
Obrázek 2.2: Sloučení více objektů pod jednu hypotézu, modře je vyznačené detekční okno hypotézy, zeleně detekční okna objektů
• Metrika ”2D/3D - vzdálenost” - Měří průměrnou vzdálenost mezi těžišti objektů a těžišti hypotéz. Určuje podobnou přesnost jako metrika ”prostor objektu” v 2.2.1, liší se od ní v tom, že redukuje i velké objekty na jeden bod, čili nepreferuje velké objekty.
2.2.3
Metriky pro sledování objektů
Jedna hlavní a tři pomocné metriky určené pro vyhodnocování jak dobře sledovaný algoritmus drží stopu objektu v čase: • Metrika ”sledovací čas” - Měří kolik procent času v sekvenci je hypotéza přiřazena objektu, neboli kvalitu sledování. • Metrika ”trvalost ID objektu” - Vypočítává kolikrát byl objekt v sekvenci korespondován s různými hypotézami. Ze své podstaty preferuje poddetekování, protože je lepší mít korespondenci objektu s hypotézu pouze v jednom snímku a v dalších nemít pro objekt žádnou korespondenci, než mít korespondenci ve více snímcích, ale s hypotézami s různým identifikačním číslem. • Metrika ”záměna ID objektu” - Vypočítává kolikrát byla hypotéza v sekvenci korespondována s různými objekty.
2.3. CLEAR MOT
14
Metriky ”trvalost ID objektu” ”záměna ID objektu”
2.2.4
Metriky pro klasifikaci objektu a rozpoznání události
Metrika pro klasifikaci objektu funguje velmi jednoduše tak, že spočte v každém snímku hypotézy, které jsou nejen přiřazené objektům, ale jsou i správně oklasifikované.
2.3 2.3.1
CLEAR MOT Úvod
Metriky CLEAR(Classification of Events, Activities and Relationships) MOT(Multiple Object Tracking)[8] jsou navržené pro měření výkonu algoritmů počítačového vidění při sledování více objektů. Zavádí objektivní a zároveň intuitivní metriky, s co nejmenším počtem parametrů, pokrývající všechny chyby při sledování více objektů a využitelné pro porovnávání výkonnosti algoritmů.
2.3.2
Návrhová kritéria
Metriky CLEAR MOT jsou navrženy tak aby splňovaly tyto vytyčená kriteria: 1. Umí posoudit nepřesnost v určení pozice v závislosti na přesné poloze objektu. 2. Umí vyhodnotit sledování trasy objektu v čase, posoudit správnost nalezených trajektorií 3. Mají co nejméně nastavitelných parametrů, aby se výsledky různých algoritmů daly snadno porovnávat. 4. Jsou intuitivní a snadno srozumitelné, mají jednoduché rozlišení různých druhů chyb při detekci. 5. Jsou obecné, aby se daly porovnávat všechny možné algoritmy, např. pro 2D, 3D. 6. Mají málo výstupních parametrů, ale přesto dobře ukazují schopnosti porovnávaných algoritmů, kvůli zjednodušenému porovnávání i velkého množství algoritmů.
2.3. CLEAR MOT
2.3.3
15
Vyhodnocovací procedura
Předpokladem pro vyhodnocovací proceduru je, že o každém snímku v záznamu máme sadu hypotéz {h1 , ..., hm }, získaných od sledovacího algoritmu, a sadu viditelných objektů {o1 , ..., on }, získaných z ground truth. Procedura funguje takto: Pro každý snímek t ze sekvence, 1. Najdi nejlepší korespondenci mezi hypotézou hj a objektem oi . 2. Pro každou nalezenou korespondenci spočítej chybu odhadu pozice. 3. Shromáždi všechny chyby v korespondenci následovně: (a) Počítej objekty pro které není korespondující hypotéza jako minuté. (b) Počítej hypotézy pro které neexistuje korespondující objekt, jako falešně pozitivní. (c) Jako zaměněné započítej ty, kde se korespondence mezi hypotézou a objektem změnila v porovnání s předchozím snímkem. Je dobré si uvědomit, že pokud sledujeme objekt v celé sekvenci, není nejlepším řešením vytvářet korespondence jen na základě nejmenší vzdálenosti z jednoho snímku. Protože je pravděpodobné, že sledovací algoritmus sleduje hypotézou stále stejný objekt, je lepší se podívat do korespondencí v předchozím snímku. Jak je vidět z obrázku 2.3, touto metodou docílíme, že nezvyšujeme počet zaměněných u algoritmu, který nechybuje. o1
h1
o2
(a) Korespondence podle předchozí
o1
h1
o2
t
t
t+1
t+1
t+2
t+2
t+3
t+3
(b) Korespondence nejbližší
Obrázek 2.3: Intuitivní určování korespondence
2.3. CLEAR MOT
2.3.4
16
Přiřazovací procedura
Procedura pro přiřazování korespondujících objektů oi k hypotézám hj , když Mt je množina korespondencí ve snímku t, vypadá následovně: Jelikož snímek t = 0 neexistuje, tak M0 je prázdná množina. Pro všechny snímky t, proveď: 1. Pro každou korespondenci (oi , hj ) v množině korespondencí Mt−1 ověříme zda ve snímku t stále korespondují, pokud ano, tak zda došlo k překročení vzdálenostního prahu mezi objektem a hypotézou, pokud nedošlo, přidáme tuto korespondenci do Mt . 2. Ostatní objekty, pro které ještě nebyla nalezena korespondence s hypotézou, budeme hledat korespondence tak, aby celková vzdálenost objektů od hypotéz byla co nejmenší(detailněji viz dále v 3.2.2). Pokud některá nově vytvořená korespondence je rozdílná od dříve vytvořené, započítej to jako záměnu, kterou přičti do proměnné počet záměn zt ve snímku t. 3. Pro všechny nalezené korespondující páry (oi , hj ), ve snímku t, uložené v množině Mt spočítáme vzdálenost mezi objektem a hypotézou a označíme jí dit . Jako kt označíme počet korespondujících párů pro snímek t. 4. Pokud zbyly nějaké nekorespondující hypotézy, jsou započítány jako falešně pozitivní do proměnné f pt . Všechny zbylé nekorespondující objekty jsou započítány jako minuté do proměnné mt . 5. Do proměnné gt ulož počet objektů ve snímku t. Opakuj předchozí body pro následující snímek.
2.3.5
MOTA
Metrika multiple object tracking accuracy (MOTA) je definována vzorcem: ∑ M OT A = 1 −
+ t (mt∑
f p t + zt ) , t gt
(2.7)
kde mt je počet minutých, f pt je počet falešně pozitivních, zt je počet zaměněných a gt je počet všech objektů ve snímku t.
2.3. CLEAR MOT
17
Čili rovnice 2.7 se vlastně skládá ze součtu tří poměrů: ∑ mt m = ∑t , t gt
(2.8)
což je poměr minutých v celé sekvenci ku všem objektům v sekvenci, ∑ f pt f p = ∑t , t gt
(2.9)
což je poměr falešně pozitivních v celé sekvenci ku všem objektům v sekvenci a ∑ zt z = ∑t , t gt
(2.10)
což je poměr zaměněných v celé sekvenci ku všem objektům v sekvenci. Metrika MOTA, tedy počítá přesnost přes celou sekvenci, pro všechny započítávané chyby typu, falešně pozitivní, minuté a zaměněné. Není ovlivněna přesným určením pozice, pokrytým v následující metrice MOTP. Nejlepší možný výsledek jakého může algoritmus v metrice MOTA dosáhnout, je 1(tj. 100%). Nejhorší možný výsledek, ačkoliv je MOTA počítána odečtením celkové sumy chyb od jedničky a vyjadřuje se v %, není 0, ale v určitých případech může nabývat i záporných hodnot. Toto je způsobeno tím, že celkový součet falešně pozitivních, minutých a záměn, může být z principu větší než je počet objektů v ground truth. A protože pak výsledný podíl vyjde větší než jedna, vyjde v takovém případě MOTA záporně.
2.3.6
MOTP
Metrika multiple object tracking precision (MOTP) je definována vzorcem: ∑ i i,t dt M OT P = ∑ , t kt
(2.11)
∑ kde i,t dit je suma všech rozdílů ve vzdálenostech, pro všechny korespondence ve všech ∑ snímcích. t kt je suma počtu všech vytvořených korespondencí ve všech snímcích. Metrika MOTP vyjadřuje chybu ve vzdálenosti mezi objektem a hypotézou přes všechny snímky, zprůměrovanou celkovým počtem vytvořených korespondencí, značí přesnost algoritmu v určování přesné pozice. Na základě tohoto údaje můžeme vyhodnotit jak přesně algoritmus vyhodnocuje pozici nezávisle na dalších schopnostech, například nalezení ob-
2.4. METRIKY SFDA, ATA
18
jektu. Výstupní hodnota vypadá podle použité metriky pro vzdálenost, např. v případě euklidovské bude výstupem hodnota v pixelech, a nejlepší hodnota výstupu bude 0. Výstupní hodnota bude 0 i v případě že nenastane žádná korespondence, proto tato metrika slouží pouze k doplnění předchozí metriky MOTA.
2.4
Metriky SFDA, ATA
Metriky SFDA a ATA prezentované v [9]. Jsou primárně založené na překryvech detekčních oken objektů a hypotéz, viz rovnice 1.2 a na tom že si vytvoříme korespondence mezi objekty a hypotézami, tak aby metriky dosáhly co nejlepšího výsledku. Mají normalizované výsledky, nejlepší výsledek dostane 1 a nejhorší výsledek dostane 0.
2.4.1
Sequence Frame Detection Accuracy(SFDA)
Pro každý snímek je nejprve spočítána Frame Detection Accuracy(FDA). Korespondence mezi objekty a hypotézami je v každém snímku vybrána tak, aby mezi sebou měly co největší překryv, tj. maximální ρ1 . Vzorec pro výpočet FDA pro snímek t vypadá takto: F DA(t) = kde η=
kt ∑
η
,
(2.12)
ρ1 (oti , htj )
(2.13)
gt +kt 2
i
η je suma překryvů(vycházející z rovnice 1.2) pro všechny korespondence ve snímku t, gt je počet objektů ve snímku t, kt je počet hypotéz ve snímku t. Vzorec zjednodušeně znamená, že sumu všech překryvů normalizujeme počtem objektů a hypotéz. Když sečteme FDA(t) pro každý snímek v sekvenci a provedeme normalizaci počtem snímků, ve kterých existuje alespoň jeden objekt nebo hypotéza, získáme Sequence Frame Detection Accuracy(SFDA), definované vzorcem: ∑n F DA(t) , SF DA = ∑n t=1 t t t=1 ∃(oi ∨ hj )
(2.14)
∑ kde n je celkový počet snímků v sekvenci a nt=1 ∃(oti ∨ htj ) je počet snímků v sekvenci, ve kterých existuje alespoň jeden objekt nebo hypotéza.
2.4. METRIKY SFDA, ATA
19
V případě kdy nás zajímá pouze kvalita detekce a nemáme zájem o určení prostorové přesnosti, lze SFDA modifikovat tak, že nastavíme hranici překryvu nad kterou budeme korespondence preferovat, tedy nastavíme jim nejvyšší překrytí, tj. 1. Nová funkce pro výpočet sumy překryvů pak vypadá takto:
η1 =
kt ∑ ρ3 (oti , htj ) i=1
kde,
(2.15)
|oti ∪ htj |
t t| j |ot ∪ ht |, když |oi ∩h ≥ zvolený práh i j |oti | t t ρ3 (oi , hj ) = |ot ∩ ht |, jinak i
,
(2.16)
j
kt je počet korespondencí ve snímku t.
2.4.2
Averate Tracking Accuracy(ATA)
Nejdříve je spočítána STDA(Sequence track Detection Accuracy), rozdíl mezi touto metrikou a předchozí SFDA je, že přiřazování hypotéz k objektům ve SFDA je optimalizováno vždy pro každý jeden snímek, zatímco ve STDA je optimalizováno přes všechny snímky v sekvenci. STDA je definována následovně: ST DA =
k∑ celk i=1
∑n t=1
ρ1 (oti , htj )
N(oi ∪hj ̸=0)
,
(2.17)
kde kcelk je celkový počet korespondencí v celé sekvenci a n je celkový počet snímků v sekvenci. Průměrná trasovací přesnost ATA(Average Tracking Accuracy), definována jako: AT A =
ST DA , h [ No +N ] 2
(2.18)
kde No je počet unikátních objektů v celé sekvenci a Nh je počet unikátních hypotéz v celé sekvenci. Kde unikátnost je znamená, že má unikátní identifikační číslo. ATA je v podstatě STDA přepočítaná na průměrný počet objektů a hypotéz. Pokud nás zajímá pouze trasovací schopnost a přesnost nepovažujeme za důležitou, zavá-
2.5. PIXELOVÉ
20
díme opět novou funkci pro výpočet sumy překryvů, podobnou rovnici 2.15. η2 =
n ∑ ρ3 (oti , htj ) t=1
2.5
oti ∪ htj
(2.19)
Pixelové
Přestože se v této práci primárně zabýváme metrikami založenými na ground truht s objekty, musíme se zmínit o metrikách založených na ground truth s pixely. V pixelově orientované ground truth je uloženo o každém pixelu ve snímku zda má být detekován, nebo ne. Výstup z algoritmu je ve stejném formátu, čili vychází z něj informace o všech pixelelech ve snímku a jestli byly oklasifikovány jako detekované či nedetekované. K vyhodnocení pak dochází pomocí dříve uvedené tabulky 1.2, podle které se dá o každém pixelu rozhodnout zda je skutečně(falešně) pozitivní nebo skutečně(falešně) negativní. Takto se vyhodnotí všechny snímky t v celé sekvenci, sečtou se informace o všech čtyřech kategoriích a dále se vyhodnocují například s užitím vzorců v sekci 2.1.
2.6
Vyhodnocení
Projekt ETISEO využívá velké množství metrik, rozdělených do skupin, které spolu velmi úzce souvisí a navzájem se doplňují a zpřesňují. Samostatně většinou nemají velkou výpovědní hodnotu, protože izolovaně hodnotí jeden aspekt algoritmu. Rozhodnout o nejlepším algoritmu na základě těchto metrik bude poměrně složité. V případě velkého rozdílu v pořadí algoritmů podle jednotlivých skupin metrik ETISEO, museli bychom ještě vytvořit nějakou hodnotící funkci, která metriky sjednotí a umožní nám sestavit jednotné pořadí. Metriky ETISEO se proto špatně porovnávají s dalšími uvedenými. Rozdíl mezi metrikami MOTA, MOTP a SFDA, ATA je v tom, že zatímco metrika MOTA a snaží se vytvářet korespondence intuitivně, metriky SFDA a ATA, vytvářejí korespondence tak, aby maximalizovaly svůj výsledek. Metrika SFDA pro každý snímek zvlášť, metrika ATA pro celou sekvenci. Metrika MOTA přesně počítá záměny, falešně pozitivní a minuté. Záměny se v SFDA nepočítají vůbec, každý snímek je brán zvlášť. V ATA záměny také neexistují, protože každý objekt může v celé sekvenci korespondovat pouze s jednou hypotézou a to s tou, pro kterou bude metrika dávat nejvyšší výsledek. Falešně pozitivní a minuté jsou do metrik SFDA a ATA započítávány nepřímo, skrze normalizování. Například u metriky SFDA, pokud ve snímku není žádný překryv mezi objektem a hypotézou,
2.6. VYHODNOCENÍ
21
tj. žádná korespondence, tak se nebere ohled nato kolik je v něm objektů či hypotéz. Tento snímek bude pouze jednou započten do celkového počtu snímků ve kterých se vyskytuje hypotéza nebo objekt. Výhodou metrik SFDA a ATA je že jsou normalizované a nabývají hodnot od 0 pro nejhorší po 1 pro nejlepší.
Kapitola 3 Implementace v matlabu Jako nejvhodnější pro implementaci byly zvolené metriky CLEAR MOT, protože při jejich počítání se dají průběžně zjišťovat statistiky falešně pozitivních, negativních a minutých, využitelné pro další zpracování. Jako vstupní data pro ground truth, videosekvence a přiřazované objekty byla použita data z projektu NIFTi [7].
3.1
Vstupy
Vstupní data, než mohou být použita, je nutné převést do vhodného formátu. V Matlabu by neměl být problém jednoduše vytvářet konvertory pro jakákoliv vstupní data a tím zaručit použitelnost pro různé vstupní algoritmy. Výchozí formát pro vstup je tvořen tak, že kolik je snímků, tolik existuje buněk (cell) a každá buňka svým číslem odpovídá číslu snímku. V každé buňce je potom právě tolik struktur kolik obsahuje detekčních oken. Každá struktura má pole viz tabulka 3.1: • id - identifikátor detekčního okna • pos - pozice, pole o dvou hodnotách, jsou v něm uloženy x,y souřadnice levého horního rohu detekčního okna • rec - parametry detekčního okna, zde je v poli o dvou hodnotách uložena jeho výška a šířka • removed - nepovinné pole, číselná hodnota použitá pro rozlišení vyřazených oken při pozdější zpracování
22
3.2. FUNKCE EVALUATE
23
V tomto formátu musí být jak vstup od algoritmu, tak ground truth. Je důležité zmínit, že počátek souřadného systému je v levém horním rohu. Tabulka 3.1: Struktura vstupu, ke každému snímku jsou přiřazeny detekční obdélníky s parametry id, pos, rec, rem snímek id id pos pos rec rec rem rem
3.2
1 id pos rec rem
snímek 2 id pos rec rem
snímek 3 id id pos pos rec rec rem rem
... ... ... ... ...
snímek n id ... pos . . . rec . . . rem . . .
Funkce evaluate
Hlavní funkce jejímž vstupem je vstup od algoritmu, ground truth, prahová vzdálenost a volba metody pro určování vzdálenosti. Volání funkce z Matlabu vypadá takto: [M OT A, M OT P, M, ST AT ] = evaluate(input, gtruth, maxDist, method) Výstupem je tedy: • MOTA - multiple object tracking accuracy(2.3.5) • MOTP - multiple object tracking precision(2.3.6) • M - množina korespondencí která má v každé buňce odpovídající číslu snímku v sekvenci uloženou korespondenci mezi objektem a hypotézou • STAT - 4 × n, rozměrná matice, kde n je počet snímků v sekvenci a na pozicích po řadě 1-4, je uložen počet minutých, falešně pozitivních, zaměněných a počet objektů v ground truth, pro snímek n. Proměnná STAT má využití při odhalování chyb algoritmů, například se z ní dá základními příkazy matlabu zjistit ve kterých snímcích je velké množství falešně pozitivních.
3.2. FUNKCE EVALUATE
3.2.1
24
Funkce calculateDist
Má tři vstupní parametry, dva jsou pro vložení objektu a hypotézy, a třetí určuje metodu kterou pro určení vzdálenosti použijeme. Implementovány jsou dvě metody, euklidovská a překryv oken, viz výše ve 1.2.5. Původní metrika překrývání oken byla mírně upravena, protože pro nejlepší výsledek dávala největší vzdálenost, což vzhledem k významu vzdálenosti nedává smysl. Převrácením hodnoty došlo k vytvoření nového vzorce: ρ1n (A, B) = 1 −
A∩B , A∪B
(3.1)
takto totiž dostáváme vzdálenost v přijatelnější formě, tedy 0 nastává v případě nejmenší vzdálenosti(okna jsou přesně na sobě) a 1 pokud nemají žádný překryv.
3.2.2
Mapování korespondencí do pole M
Mapování korespondujících hypotéz s objekty probíhá dle procedury v 2.3.4. Aby se dosáhlo co nejlepšího přiřazení hypotéz objektům, vygeneruje se pomocí funkce calculateDist matice i×j, obsahující všechny vzdálenosti mezi objekty a hypotézami. Ta se poté zpracuje Munkresovým algoritmem [3], který vybere nejlepší možné korespondence hypotéz k objektům. Viz příklad v tabulce 3.2, jako Inf jsou označeny vzdálenosti větší než práh. Munkresův algoritmus vybral jako nejlépe korespondující páry (o1 , h3 ), (o2 , h1 ), (o3 , h5 ), (o4 , h2 ). Za povšimnutí stojí, že hypotéza h4 nebyla přiřazena žádnému objektu, byla by tedy vyhodnocena jako falešně pozitivní. Tabulka 3.2: Výsledek Munkresova algoritmu, čísla v tabulce reprezentují vzdálenost, Inf značí ”nekonečné” vzdálenosti
h1 h2 h3 h4 h5
o1 Inf 5 1 5 Inf
o2 2 Inf Inf Inf 2
o3 3 3 1 Inf 1
o4 4 2 Inf 2 5
3.3. VIZUALIZACE
3.3
Vizualizace
K vizualizování výsledků slouží funkce drawData. Její volání z Matlabu vypadá takto: drawData(input, gtruth, M, images, f rames, maxT rajectory, step, f rameT ime) Vstupní proměnné jsou: • input - vstupní data z algoritmu ve formátu uvedeném výše v 3.1 • gtruth - ground truth • M - množina korespondencí spočtená ve funkci evaluate • images - proměnná ve které je uložená cesta ke snímkům • frames - do této proměnné zadáme čísla snímků, které chceme vizualizovat • maxTrajectory - jak dlouhá má být maximální trajektorie • step - délka kroku v trajektorii • frameTime - čas jak dlouho má být každý snímek zobrazen v sekundách
25
3.3. VIZUALIZACE
26
Obrázek 3.1: Ukázka z výstupu vizualizace, vlevo nahoře je černě zobrazené číslo snímku t, zelené číslo vlevo nahoře je počet objektů v ground truth, modré číslo vlevo nahoře je počet hypotéz, červeně je vlevo nahoře na jednom řádku zobrazeno identifikační číslo objektu a identifikační číslo hypotézy, které spolu v daném snímku korespondují
3.3. VIZUALIZACE
27
Obrázek 3.2: Minutý a korespondující objekt. Zeleně vyznačené detekční okna jsou objektů, růžově je označená korespondence mezi hypotézou a objektem. Objekt č.2 je minutý, asi proto, že je částečně schovaný za keřem, objekt č.188 koresponduje s hypotézou č.3.
Obrázek 3.3: Falešně pozitivní a nalezený objekt. Zeleně vyznačené detekční okno je objekt(ground truth), růžově je označená korespondence mezi hypotézou a objektem, modře nepřiřazená(falešná) hypotéza. Hypotéza č.7250 je falešná, objekt č.7191 koresponduje s hypotézou č.24
Kapitola 4 Automatické získávání ground truth Získávání ground truth je časově náročné, proto je implementace nějaké metody která jí automaticky zjistí velmi užitečné. Bylo rozhodnuto, že pro automatické získávání ground truth využijeme již existující algoritmus pro vyhledávání osob z diplomové práce [1], který má jako výstup detekční okna. Jelikož tento detektor pro tuto úlohu nepracoval příliš dobře, pokoušeli jsme aplikovat některé metody pro jeho vylepšení.
4.1
Detektor lidského těla
Snahou detektoru z [1] je rozpoznat člověka a vygenerovat okolo něj detekční okno. Detekce je založená na vlastnostech obrazových gradientů (HOGs) a pro urychlení používá kaskádový klasifikátor. K testování docházelo na stejných datech jako v případě implementace metriky viz kapitola 3. V detektoru bylo ponecháno původní nastavení a natrénování, docházelo pouze k manipulaci s parametrem threshold, tj. prahu. Ukázky detekčních oken pro různá nastavení parametru threshold jsou vidět na obrázku 4.1. Z této skupiny obrázků je vidět, že v případě využití detektoru pro získání ground truth, má smysl spíše menší nastavení prahu, aby byly detekovány všechny osoby, i za cenu většího množství oken.
4.2
Pokusy o vylepšení detekce
Cílem těchto pokusů nebylo vytvářet nový detektor, spíše prozkoušet některé metody pro zlepšení detekce.
28
4.2. POKUSY O VYLEPŠENÍ DETEKCE
29
Obrázek 4.1: Detekční okna detektoru lidí, pro různá nastavení parametru THRESHOLD
4.2.1
Odstranění duplikovaných detekcí
Algoritmus ke každé hypotéze přidává údaj o tom, jak moc je dané okno pravděpodobné, neboli nakolik se mu dá důvěřovat. Tuto výstupní proměnnou z algoritmu budeme dále nazývat důvěra. Na základě této důvěry jsme se snažili odstranit duplikované detekce. Tj. vícenásobnou detekci jednoho objektu. Postupovali jsme následujícím algoritmem: 1. Ve snímku t vyber hypotézu s největší důvěrou, nazveme ji například h1 . 2. Vyber všechny hypotézy které jsou od h1 vzdáleny méně než je zvolený práh, tj. kde ρ(h1 , hj ) < zvolený práh . 3. Hypotézy vybrané v předchozím bodě považujeme za duplikáty, proto je odstraň 4. Opakuj pro všechny snímky t
4.2. POKUSY O VYLEPŠENÍ DETEKCE
30
Při použití metriky pro překryv ρ1 se ukázalo omezení této metriky. Malá detekční okna, i když jsou úplně celá uvnitř větších, nikdy nepřekročí vzdálenostní práh. Tato okna jsou určitě vícenásobnou detekcí, ale ve snímku bohužel zůstanou. Pokud by se předem omezilo jak velká okna může detektor generovat, dal by se výskyt této chyby omezit. Okna která se podařilo tímto postupem odstranit je vidět na obrázku 4.2.
Obrázek 4.2: Odstranění duplikovaných detekčních oken, vlevo všechny, vpravo po odstranění duplikovaných
4.2.2
Odstranění detekčních oken na pozadí
Z levého obrázku 4.2 je patrné množství chybných oken v levém horním rohu. Jako metoda pro jejich odstranění bylo navrhnuto implementovat odstraňování detekčních oken v místech, kde dochází pouze k malým změnám. Vycházíme z předpokladu, že pohybující se člověk vytváří relativně velkou změnu mezi jednotlivými snímky obrazu. Problémem by mohlo být, že další pohybující se objekty v obraze, např. zvířata, automobily, ale také vlnící se listí na stromech, případně prudká změna osvětlení, vytváří podobné změny v obraze jako pohybující se člověk. Další menší nepřesnosti mohou přinášet stíny pohybujících se lidí. Místa s malou změnou se dají identifikovat několika způsoby, viz např. v [13]. My jsme pro průběžné počítání průměrné hodnoty pozadí použili klouzavý průměr s exponenciálním zapomínáním. Jelikož snímek je ve formátu červená, zelená, modrá, byly nejprve sečteny hodnoty červené, zelené a modré barvy v obraze: P za(t) = Hcˇ(t) + Hz (t) + Hm (t),
(4.1)
4.2. POKUSY O VYLEPŠENÍ DETEKCE
31
kde P za, Hcˇ, Hz a Hm , jsou matice o rozměru snímku, kde na pozicích x, y je uloženo číslo odpovídající hodnotě barvy ve snímku je má každý pixel na pozici (x, y) uložené číslo. V maticích Hcˇ, Hz a Hm , je po řadě uložena hodnota červené, zelené a modré barvy ve snímku t v rozmezí 0-1 a v P za je součet těchto tří. Dále byl aplikován následují vzorec pro výpočet klouzavého průměru: P z(t) =
P z(t − 1) ∗ (d − 1) + P za , d
(4.2)
kde d je délka klouzavého průměru, P z(t) a P z(t − 1) jsou hodnoty pozadí pro současný a předchozí snímek. Aplikací rovnice 4.2 získáváme průměrnou hodnotu pozadí P z(t) pro každý snímek t v sekvenci. Matici P z(t) pak odečteme od matice P za a každý prvek porovnáme s prahem pozadí p, což je hodnota pro kterou budeme považovat, že došlo ke změně v pozadí, viz následující rovnice: 1, když |P z (t) − P za (t)| > p xy xy M pxy (t) = 0, když |P z (t) − P za (t)| ≤ p xy xy
(4.3)
Výsledná vizualizace matice M p(t) pro pozadí a popředí je vidět na obr. 4.3.
Obrázek 4.3: Určení pozadí a popředí snímku, bílé plochy odhadnuté jako popředí, černé jako pozadí
V matici M p(t) odpovídá každému pixelu ve snímku t jedno číslo 1 nebo 0. Podle této
4.2. POKUSY O VYLEPŠENÍ DETEKCE
32
matice se tedy dá rozhodnout, zda se daný pixel nachází v pozadí. Pro každé detekční okno se pak lze spočítat kolik procent jeho pixelů se nachází v pozadí. Tato metoda nám umožnila odstranit ta okna která měla v pozadí velké procento pixelů(bylo nastavováno přes 50%). Zobrazení snímku před a po odstranění oken je vidět na obrázku 4.4.
Obrázek 4.4: Odstranění detekčních oken v pozadí, vlevo všechny, vpravo po odstranění oken v pozadí
4.2.3
Přidání nových snímků
V několika místech sekvence se stávalo, že v následujícím snímku nebyla k objektu hypotéza a byla až v nějakém dalším. Neboli že docházelo k výpadkům detekčních oken pro jeden či více snímků. Bylo diskutováno, zda by nebylo možné vyžít informaci z předchozích snímků pro doplnění dočasně zmizelých detekčních oken do snímků následujících, a tím vylepšit celkovou detekci. Jako metoda pro přidávání oken byla použita normalizovaná křížová korelace(Normalized cross-correlation). Zjednodušený postup vypadal následovně: • Ve snímku t − 1 vezmi detekční okno. • Umísti ho na stejné místo ve snímku t. • Toto nové okno ve snímku t posouvej v osách x, y. Posouvání slouží k identifikaci rozdílu pozice mezi snímky při pohybujícím se objektu. • Pro všechna posunutí spočítej normalizovanou křížovou korelaci.
4.3. EXPERIMENTY
33
• Ze spočtených korelací vyber tu nejlepší, tj. v nejlepším případě je korelace 1. • U nového detekčního okna s nejlepší korelací prozkoumej vzdálenost od ostatních, již existujících detekčních oken ve snímku t. • Pokud nové okno nekoresponduje s žádným stávajícím, takže se dá předpokládat že se jedná o unikátní detekci, přidej do snímku toto detekční okno. Tímto postupem přibyla do sekvence nová detekční okna, ale jak se ukázalo, ne tak jak bylo původně zamýšleno. Uvedená korelace fungovala spíše na menší okna, a tak více přibývala menší okna než aby se skutečně doplňovala dočasně zmizelá okna. Jelikož menší okna uvnitř větších jsou většinou vícenásobná detekce, kterou neodstranila metoda v sekci 4.2.1, zvyšovalo se tak množství falešně pozitivních. Na obr. 4.5 je vpravo vidět objevení dvou menších detekčních oken uvnitř větších.
Obrázek 4.5: Pokus o detekování nových oken
4.3
Experimenty
Při pokusech o vylepšování detekce jsme potřebovali nějak vyhodnocovat úspěšnost našich vylepšení. Naimplementované metriky se pro to nehodí, ale bylo využito, že při jejich výpočtu dochází i ke spočtení doplňkových statistik, o minutých, falešně pozitivních a tak byly vykreslovány DET křivky. Výsledky experimentů jsou vidět na obrázku 4.6. Na ose x je vynesen průměrný počet falešně pozitivních na jeden snímek v sekvenci, tj. ∑n t=1 f pt . Na ose y je vynesena míra minutých v celé sekvenci. Jednotlivé body křivky jsou n
4.3. EXPERIMENTY
34
pak sestrojeny nastavováním parametru threshold(v rozmezí -2 až -1) v detektoru lidského těla, viz. 4.1. V tomto grafu je vidět, že každou úpravou došlo ke zlepšení detekce, po aplikaci prvních třech metod ubyly falešně pozitivní, po aplikaci čtvrté metody se zmenšil počet minutých. I když zlepšení u čtvrté metody je diskutabilní, protože jak bylo uvedeno výše, přidávaná okna vznikla z nedostatečně odstraněné vícenásobné detekce. 1 viz.
1)
viz. 2)
0.95
viz. 3) viz. 4)
Míra minutých [−]
0.9
0.85
0.8
0.75
0.7
0.65
0
1
2 3 4 5 6 Pocet falešne pozitivních na jeden snímek [−]
7
8
Obrázek 4.6: Křivky z výstupu použitých metod, 1) Výstup z detektoru, 2) Po odstranění duplikátů, 3) Po odstranění duplikátů a snímků v pozadí, 4) Po odstranění duplikátů, snímků v pozadí a pokusu o přidání oken
Kapitola 5 Závěr V této práci byly prozkoumány a nastudovány metody automatického vyhodnocování algoritmů počítačového vidění, metriky pro měření vzdálenosti, způsoby určování korespondencí, zkombinované do metrik pro celkové vyhodnocování algoritmů pro detekci a sledování. Jako nejvhodnější byly vybrány a naimplementovány metriky MOTA a MOTP, obohacené o metriku překryvu. Byla vytvořena vizualizace pro výstupní statistiky vzniklé při počítání těchto metrik. Naimplementované metriky se dají využít k vyhodnocování sledovacích algoritmů a v kombinaci s jejich vizualizací dokážou odhalovat slabá místa a problémy vyhodnocovaných algoritmů. V poslední části bylo experimentováno s automatickým získáváním ground truth, přitom bylo naimplementováno a vyzkoušeno několik metod pro zpřesnění detekcí lidí v obrazech, které se dají využít k získávání ground truth. Jako pokračování této práce by bylo vhodné rozšířit metodu automatického získávání ground truth, aby dokázala mapovat objekty skrz celou sekvenci. Případně vyzkoušet použití nějakého lepšího detektoru lidí.
35
Literatura [1] PRIKNER, Rostislav. Pictorial Structural Models for Human Detection in Videos. Praha, 2008. 63 s. Diplomová práce. ČVUT, FEL. [2] DOLLÁR, Piotr, Caltech Pedestrian Dataset homepage [online]. 2010 [cit. 2011-03-30]. Dostupné z WWW:
[3] MUNKRES, James. Algorithms for the assignment and transportation problems, Journal of the Society of Industrial and Applied Mathematics, 1957, 5, s. 32-38. [4] CAO, Yi. Munkres Algorithm for Linear Assignment Problem, m-file, Cranfield University, July 2008 [5] NGHIEM, Anh T., et al. ETISEO, Performance evaluation for video surveillance systems. Advanced Video and Signal Based Surveillance. 2007, s. 476-481. [6] COLLINS, Robert; ZHOU, Xuhui; TEH, Seng. An Open Source Tracking Testbed and Evaluation Web Site. In Proc. IEEE PETS Workshop. 2005. s. 5. [7] NIFTi
, 2011 [8] BERNARDIN, Keni; STIEFELHAGEN, Rainer. Evaluating Multiple Object Tracking Performance: The CLEAR MOT Metrics. EURASIP Journal on Image and Video Processing. 2008 [9] MANOHAR, Vasant, et al. Performance Evaluation of Object Detection and Tracking in Video. In Proceedings of the Seventh Asian Conference on Computer Vision. 2006. s. 151-161. [10] ERDEM, C ¸ i˘gdem Ero˘glu; MURAT TEKALP, A.; SANKUR, Bülent. Metrics for performance evaluation of video object segmentation and tracking without ground-truth. 36
LITERATURA
37
In 2001 International Conference on Image Processing, 2001. Proceedings. . Thessaloniki, Greece, 2001. s. 69 - 72. ISBN 0-7803-6725-1. [11] LIST, Thor, et al. Performance evaluating the evaluator. IEEE Joint International Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance. 2005, s. 129 - 136. [12] RENNO, John-Paul, et al. Evaluating motion detection algorithms: issues and results. In IEEE International Workshop on Visual Surveillance. Graz, Austria, 2006. s. 97104. [13] LI, Li; JINING, Xu. Moving human detection algorithm based on Gaussian mixture model. In Control Conference (CCC), 2010 29th Chinese . Beijing, 2010. s. 2853 2856 . ISBN 978-1-4244-6263-6.
Příloha A Obsah přiloženého cd K této práci je přiloženo CD na kterém jsou uloženy zdrojové kódy v Matlabu a tato práce ve formátu pdf. • \Dokumentace\: Diplomová práce ve formátu pdf. • \Matlab\: Zdrojové kódy z Matlabu.
