Tracking Filter voor het component Video Meten in Coach
Door Studentnummer Universiteit Datum Begeleiders
: : : : : :
Mark Smids <
[email protected]> 0102342 Universiteit van Amsterdam 11 juni 2004 Rein van den Boomgaard (UvA) Leendert van Gastel (Amstel Instituut)
Sleutelwoorden
: Object Tracking, DirectShow, OpenCV, : Educatie, Coach, Filters
Tracking Filter voor het component Video Meten in Coach
2
Tracking Filter voor het component Video Meten in Coach
Inhoudsopgave 1 Voorwoord ......................................................................................................................... 5 2 Samenvatting ...................................................................................................................... 7 3. Onderzoeksvoorstel ............................................................................................................ 9 3.1 Doelstellingen ................................................................................................................... 9 3.2 Plan van Aanpak ............................................................................................................... 9 3.3 Toepassingen................................................................................................................... 11 3.4 Risico’s............................................................................................................................ 11 4. Bedrijfsprofiel.................................................................................................................. 13 4.1 Over het instituut............................................................................................................. 13 4.2 Coach .............................................................................................................................. 13 4.3 Het component Video Meten .......................................................................................... 14 5. Literatuurstudie ................................................................................................................ 15 5.1.1 Matching ...................................................................................................................... 16 5.1.1.1 Som van het kwadratische verschil ........................................................................... 16 5.1.1.2 Hausdorff afstand en Transformaties ........................................................................ 16 5.1.1.3 Hough Transformatie ................................................................................................ 17 5.1.1.4 Mean Shift analyse.................................................................................................... 18 5.1.2 Tracking ....................................................................................................................... 19 5.1.2.1 Gemiddelde verplaatsing........................................................................................... 19 5.1.2.2 Adaptive Kalman filter.............................................................................................. 19 5.2 Samenvatting Matching en Tracking Methoden ............................................................. 21 6 Ontwerp van het Algoritme ................................................................................................ 23 6.1 Eigenschappen van Video’s ............................................................................................ 23 6.3 De gekozen video’s ......................................................................................................... 26 6.4 Keuze van het algoritme.................................................................................................. 27 6.5 Flow Chart (Stroomdiagram) .......................................................................................... 28 6.6 Functieprototypes............................................................................................................ 32 7 De Implementatie van de gekozen algoritmes...................................................................... 33 7.1 Tools................................................................................................................................ 33 7.1.1 Visual C++ ................................................................................................................... 33 7.1.2 DirectX/DirectShow..................................................................................................... 33 7.1.3 OpenCV bibliotheek .................................................................................................... 34 7.1.4 Compileren................................................................................................................... 34 7.2 Implementatie details ...................................................................................................... 36 7.3 Testresultaten .................................................................................................................. 37 8 De GUI voor de gebruiker ................................................................................................. 39 8.1 De opbouw van het Eigenschappenvenster..................................................................... 39 8.2 De didactische aspecten van het filter ............................................................................. 40 9 De Demonstratieapplicaties ............................................................................................... 43 9.1 Gebruik van het filter in GraphEdit ................................................................................ 43 9.2 Het verwerken van de Meetgegevens.............................................................................. 44 10 Conclusie........................................................................................................................ 47 11 Referenties...................................................................................................................... 49 – Appendix A – ................................................................................................................... 51 Voorbeelden Wiskundige Methoden..................................................................................... 51 A.1 Hausdorff afstand bepalen.............................................................................................. 51 A.2 Rechte lijnen vinden via een Hough Transformatie....................................................... 53
3
Tracking Filter voor het component Video Meten in Coach
4
Tracking Filter voor het component Video Meten in Coach
1 Voorwoord In deze scriptie, behorende bij mijn Bachelor afstudeeropdracht aan de Universiteit van Amsterdam (UvA), staat beschreven hoe ik mijn opdracht heb aangepakt, uitgewerkt en getest. Ook dient het ter documentatie voor de werking en bediening van het op te leveren product. Eerst zal ik mij even kort voorstellen. Ik ben Mark Smids, 21 jaar en 3e jaars informaticastudent aan de Universiteit van Amsterdam. In de drie jaar dat ik de opleiding informatica nu volg heb ik gemerkt dat ik vakken die te maken hebben met graphics, beeldverwerking en programmeervakken erg leuk vond om te volgen. Dit gaf mij dan ook de doorslag om voor een afstudeeropdracht te kiezen dat zich op dit terrein bevond. Kort geformuleerd is de opdracht in dit project het maken van een eenvoudige tracking filter, dat in staat is om één of meerdere objecten in een video real-time te kunnen volgen. Hierbij gaan de meetgegevens die zo ontstaan (2D-coördinaten van het te volgen object in elk frame) gebruikt worden in het educatieve softwarepakket Coach. De opbouw van deze scriptie is globaal als volgt: eerst zal de opdracht wat preciseer gedefinieerd worden en wordt er verteld wat van mij verwacht werd om af te leveren. Daarna volgt een stuk over het bedrijf waar ik stage heb gelopen. Voor dit bedrijf wordt het filter namelijk ontwikkeld. Dan volgt er een stuk literatuuronderzoek waarin verteld wordt welke wiskundige methoden er zoal gebruikt worden voor het tracken van objecten in video. Ondanks dat het onderwerp nog niet zo erg lang bestaat, zijn er al talloze verschillende methoden ontwikkeld om goed objecten te volgen in video. Vervolgens zijn de systeemeisen opgesteld met goedkeuring van mijn begeleiders. Deze eisen zullen ook in deze scriptie genoemd worden. Daarna zal het ontwerp en de implementatie van het gekozen algoritme besproken worden. Tot slot zal beschreven worden hoe een grafische schil gebruikt wordt om het algoritme te demonstreren. Hierbij heb ik ook gelet op de didactische aspecten van het filter. Voor vragen, opmerkingen of het doorgeven van (schrijf) fouten kunt u contact met mij opnemen. Mijn gegevens staan op het voorste blad van deze scriptie. Literatuurverwijzingen staan in de tekst aangegeven tussen vierkante haken, bijvoorbeeld: [A2]. In hoofdstuk 11 staat de referentielijst. De scriptie plus aanvullende bestanden die bij dit project horen zijn ook digitaal beschikbaar op: http://gene.science.uva.nl/~msmids/afstuderen Mark Smids (Juni 2004)
5
Tracking Filter voor het component Video Meten in Coach
6
Tracking Filter voor het component Video Meten in Coach
2 Samenvatting In deze scriptie wordt het ontwerpen, implementeren en testen van een geschikt tracking algoritme besproken, gebruikmakend van de DirectShow 9 SDK [S1] en de OpenCV beta 3.1 [S2] bibliotheek. Het algoritme is verwerkt in een DirectShow Transform filter en is afgestemd op de systeemeisen die afgesproken zijn met de opdrachtgever. Het filter is in staat real-time objecten te tracken in video bestanden of rechtstreeks via een webcam. Ook is een optie ingebouwd waardoor objecten die tijdelijk ziet zichtbaar zijn (door occlusie) toch goed gevolgd blijven worden, door gebruik te maken van een lineaire schatter. De gebruiker van het filter kan parameters van het filter aanpassen in de property page van het filter en direct toepassen. De doelgroep van de gebruikers van het filter zijn scholieren van het voorgezet onderwijs die het gaan gebruiken om metingen te verrichten in video. Het is de bedoeling dat het filter later geïntegreerd gaat worden in het educatieve softwarepakket Coach, ontwikkeld door het Amstel instituut.
7
Tracking Filter voor het component Video Meten in Coach
8
Tracking Filter voor het component Video Meten in Coach
3. Onderzoeksvoorstel 3.1 Doelstellingen Het af te leveren eindproduct is een Tracking Filter die gebruik maakt van de Microsoft DirectDraw bibliotheek en ga ik programmeren in Visual C++. Het filter kan vervolgens later geïmporteerd worden in het softwarepakket Coach (in het “Video-meten” component). Het filter is een transformatie filter die in gedachte geplaatst kan worden tussen een bron- en een render-filter. Zie figuur 1. Bron filter
Transformatie filter
video.avi / webcam
tracking filter
Render filter
monitor /
Meet gegevens voor verder gebruik in Coach. Figuur 1 – Schematisch overzicht van soorten filters. De gearceerde delen zijn van belang voor het project
Het transformatie filter heeft, zoals hierboven zichtbaar, ook als taak dat het de meetgegevens (coördinaten van het te volgen object per frame) kan doorgeven aan applicaties die het filter gebruiken, zoals Coach. Naast deze meetgegevens wordt uiteraard zichtbaar dat het object gevolgd wordt (door het render filter, wat een monitor of een file kan zijn). Opmerking: Het importeren van DirectShow filters in de nieuwe versie van Coach is nog in ontwikkeling. De mogelijkheid tot importeren valt dus buiten dit project.
3.2 Plan van Aanpak De nadruk van de opdracht ligt op de keuze van het ontwerp van het tracking algoritme. Maar ook de didactische kant van het filter is belangrijk omdat de doelgroep die het filter daadwerkelijk gaat gebruiken, leerlingen zijn van de bovenbouw van het middelbaar onderwijs. Kortom, bij het maken van een tracking filter voor Coach komt veel kijken. Door deze opdracht in te delen in een aantal subopdrachten zal een structuur ontstaan zodat de delen los van elkaar te lezen zijn. •
Literatuurstudie:. Het algoritme bestaat eigenlijk uit twee delen: Ten eerste het herkennen van een object in het opeenvolgende frame, gegeven het model (template) van een object. Er moet dus in het volgende frame gezocht worden
9
Tracking Filter voor het component Video Meten in Coach naar de beste match. Dit is op die plaats (gebied) dat het meest overeen komt met het gebied beschreven in het model. Ten tweede speelt het beperken van het zoekgebied een rol. Door te voorspellen waar het object in het volgende frame ongeveer terechtkomt is het mogelijk het zoekgebied, waarbinnen gematchd moet worden, te verkleinen waardoor het algoritme sneller werkt. Er zijn verschillende wiskundige methodes die toe te passen zijn in het algoritme. In deze deelopdracht zal moeten worden bepaald welke van deze technieken ik ga gebruiken in het project. Deze keuze hangt af van de eigenschappen van de video’s die gaan worden gebruikt in Coach. Dit deel van de opdracht zal veel tijd in beslag nemen en is een stap die eerst gedaan moet worden alvorens het werkelijke implementeren kan beginnen. •
Ontwerp en implementatie van het gekozen algoritme: Wanneer een keuze is gemaakt uit de bestaande algoritmen voor object tracking zal het algoritme worden ontworpen door onder andere de systeemeisen op te stellen en vervolgens zal het algoritme geïmplementeerd worden in Visual C++. Het algoritme moet op elk frame van de video worden toegepast. Dit subonderdeel van het project zal het meeste tijd in beslag gaan nemen omdat naast het implementeren ook onderzocht moet worden welke video’s geschikt zijn en welke minder geschikt. Het algoritme moet vervolgens verwerkt worden in een standaard transformatie filter in DirectShow. Het maken van een framework van zo’n filter kan worden gedaan met allerlei Wizards die te downloaden zijn van internet. Het maken van zo’n framework beschouw ik dus als bestaand en valt buiten het project.
•
Gebruikersvriendelijkheid van het filter: Een transformatie filter heeft vaak een Property Page. Dit is een dialoog (GUI) waar de gebruiker parameters kan instellen die effect hebben op het filter. Voorbeelden van parameters in het tracking filter zijn coördinaten van het geselecteerde object of de mate waarin kleur een rol speelt bij het matchen. Bij het ontwerp van dit dialoog is het belangrijk dat dit overzichtelijk is en ook aangepast is voor de doelgroep. Middelbare scholieren moeten eenvoudig de parameters van het filter kunnen aanpassen. Een belangrijk deel is de communicatie tussen het filter zelf en de Property Page, waar parameters door de gebruiker kunnen worden gewijzigd. Het werken hieraan gebeurt parallel aan het ontwerpen van het tracking algoritme.
•
Het maken van een demonstratie applicatie: Omdat het importeren van DirectX filters in Coach nog in ontwikkeling is, zal een stand-alone demonstratie gemaakt worden die rechtstreeks gebruikt maakt van het te ontwerpen filter. In real-time moet dan zichtbaar worden dat daadwerkelijk een object gevolgd wordt en dat de meetgegevens automatisch verwerkt worden. Deze demonstratie applicatie zal in Java geschreven worden omdat deze taal zich goed leent voor het parsen van files. Deze subopdracht zal in relatief korte tijd gemaakt worden nadat het filter voltooid is.
10
Tracking Filter voor het component Video Meten in Coach
3.3 Toepassingen Educatieve toepassing: Het te ontwerpen filter gaat gebruikt worden in het educatieve softwarepakket Coach. Dit pakket bevat een component dat Video Meten heet. Hierin kan de leerling bijvoorbeeld de snelheid van een object in een video meten door in elk frame van de video aan te klikken waar het object zich bevind. Wanneer de video erg veel frames bevat is dit tijdrovend werk. Met het tracking filter ingeschakeld moet het mogelijk worden dat de leerling maar één keer hoeft te klikken op een object in een willekeurig frame en dat het filter dan de positie van het object in elk frame vastlegt. Uit deze positiegegevens kunnen dan door de leerling allerlei grootheden als snelheid, versnelling, kracht, impuls, enz. bepaald worden. Overige toepassingen: Een tracking filter in het algemeen kan ook voor talloze andere doeleinden gebruikt worden. Hierbij kan gedacht worden aan bijvoorbeeld: beveiligingscamera’s die personen kunnen volgen, toepassingen in het verkeer (automatische kenteken registratie) en bijvoorbeeld in het veld van de Virtual Reality en spelontwikkeling.
3.4 Risico’s Problemen die kunnen optreden tijdens het ontwikkelproces zouden kunnen zijn: •
Het filter blijkt uiteindelijk niet real-time te werken op een gemiddelde consumenten PC. Wanneer dit het geval is zal het algoritme minder complex gemaakt moeten worden. Er moet dus een afweging worden gemaakt tussen snelheid en de mate van correctheid van het filter.
•
Bepaalde vastgelegde eisen kunnen niet worden gehaald door beperkingen van DirectShow. Wanneer dit zich voordoet zal in deze scriptie beschreven worden waar deze beperkingen precies zitten en waardoor dus een bepaalde eis niet haalbaar is.
•
Het filter blijkt achteraf niet makkelijk in Coach zijn te importeren. Omdat het importeren van filters in Coach nog in ontwikkeling is zal er overlegd moeten worden met de mensen die hier aan werken. Dan gaat het vooral over welke dingen het filter moet doen en welke dingen het programma Coach zelf voor zijn rekening neemt. (denk aan het verwerken van de meetgegevens)
11
Tracking Filter voor het component Video Meten in Coach
12
Tracking Filter voor het component Video Meten in Coach
4. Bedrijfsprofiel De gekozen opdacht voor het bachelor afstudeerproject heeft deels de vorm van een bedrijfsstage. Naast begeleiding van de docenten die verantwoordelijk zijn voor de Bachelor afstudeergroep, is er goede begeleiding van medewerkers die verbonden zijn aan het bedrijf waar stage gelopen wordt. Het instituut heet het AMSTEL instituut te Amsterdam (zie figuur 2). Het AMSTEL Instituut vormt een onderdeel van de Faculteit der Natuurwetenschappen, Wiskunde en Informatica (FNWI) van de Universiteit van Amsterdam (UvA). In paragraaf 4.1 zal wat meer verteld worden over het instituut. Het is de bedoeling dat het te ontwerpen tracking filter (deels) in een commercieel softwarepakket wordt gebruikt. Dit softwarepakket heet Coach en wordt voor educatieve toepassingen gebruikt. Figuur 2 – het Amstel instituut In paragraaf 4.2 wordt kort verteld wat Coach precies is (eigen foto) en wat de doelgroep van deze software is. In paragraaf 4.3 wordt beschreven welk deel van het programma van belang is bij het ontwikkelen van het filter.
4.1 Over het instituut Het AMSTEL Instituut is gespecialiseerd in onderzoek en ontwikkeling van ICTtoepassingen in het onderwijs. De staf van ongeveer 35 mensen vormt een team dat veel disciplines bestrijkt en bestaat uit experts op het gebied van hard- en software. Verder werken er onderwijsdeskundigen, mensen die nascholing verzorgen en onderzoekers. Bovendien is het mogelijk binnen het instituut als student een stage te lopen voor bijvoorbeeld, zoals in mijn geval, een afstudeeropdracht. Het doel van het Amstel Instituut is het verbeteren van het onderwijs in de wiskunde, natuurwetenschappen en de techniek in het algemeen. Ook verzorgt het Amstel Instituut de inhoudelijke relatie tussen de beta-faculteiten van de UvA en het voortgezet onderwijs (VO). Zo levert het AMSTEL Instituut hardware en software aan het voortgezet onderwijs die gebruikt wordt bij practica van onder andere wiskunde en natuurkunde. Door onder meer digitale interactieve video te gebruiken wordt een belangrijke stap gezet in de richting van realistischer onderwijs. Hierbij worden leerlingen van het voortgezet onderwijs geconfronteerd met meer tastbaar materiaal om te bestuderen.
4.2 Coach Coach is een veelzijdige leeromgeving waarin scholieren en studenten kunnen meten, regelen en sturen. Het softwarepakket kan bovendien samenwerken met allerlei hardware die onder andere ook op het AMSTEL Instituut vervaardigd wordt. Voorbeelden daarvan zijn sensoren, meetpanelen en speciale drivers om met behulp van Coach de LEGO RCX1 1
De RCX is een programmeerbare microcomputer waarop sensoren en (lego) motortjes kunnen worden aangesloten. Hiermee kan bijvoorbeeld een voertuig van lego aangestuurd worden die een bepaalde voorgeprogrammeerde opdracht moet vervullen.
13
Tracking Filter voor het component Video Meten in Coach te programmeren. Op 25 november 2003 heeft het AMSTEL Instituut uit handen van de Minister van Onderwijs en Wetenschappen van Zweden de European Academic Software Award ontvangen. Het pakket is dan ook in meer dan 15 talen vertaald en wordt in vele landen gebruikt. Uiteraard wordt hier in Nederland ook veel gebruik gemaakt van het programma, met name op scholen in het voortgezet onderwijs..
4.3 Het component Video Meten Het component in Coach dat betrekking heeft op dit project is het component “Video Meten”. Met dit component is de leerling in staat om metingen te verrichten in bewegende beelden. Grootheden die gemeten kunnen worden zijn bijvoorbeeld afstand, snelheid, versnelling en rotatie van objecten in de video’s. Hiervoor moet er in elk frame (of een selectie van frames) van een bepaalde video steeds geklikt worden op het voorwerp wat gevolgd dient te worden. (zie figuur 3) Wanneer we een video hebben met veel frames is dat vele klikken voor de leerling natuurlijk erg vervelend. Dit is precies waar dit project inspringt. Het proces van klikken moet geautomatiseerd worden zodat de leerling een stuk minder hoeft te klikken. Dit moet gedaan worden door een tracking filter te maken die dus per frame de coördinaten doorgeeft aan een verwerkingscomponent (van Coach). De eigenschappen van video’s die in coach aanwezig zijn zullen behandeld worden in paragraaf 6.1. Het component Video Meten is erg populair onder de leerlingen maar toch is steeds de ‘klacht’ van het vele klikken te horen. Een tracking filter gebruiken zou hier dus een ideale oplossing zijn.
Figuur 3 – Het Videometen component in Coach. Links boven is een filmpje te zien waar de leerling in elk frame op die plaats moet klikken waar het te volgen object is. Rechtsboven wordt dan real-time bij elke klik een grafiek bijgewerkt waarin langs de horizontale as de tijd is uitgezet en de verticale as de afstand in verticale richting. rechtsonder is de grafiek te zien waarin de verticale snelheid is uitgezet tegen de tijd.
14
Tracking Filter voor het component Video Meten in Coach
5. Literatuurstudie Voor het tracken van bewegende objecten in video beelden zijn vele methoden bekend. Vooral de laatste jaren worden er zeer veel wetenschappelijke artikelen en papers gemaakt die betrekking hebben op het herkennen en tracken van objecten in video. Het is opmerkelijk dat het vaak maatwerk is: een bepaald algoritme werkt alleen goed met video’s die bepaalde eigenschappen bezitten, of een bepaald algoritme werkt bijvoorbeeld alleen snel genoeg op een supercomputer. Omdat er dus niet een algemeen algoritme is die voor alle gevallen goed werkt zal in dit hoofdstuk een uiteenzetting gegeven worden waarin de meest voorkomende wiskundige methoden, die in tracking algoritmes gebruikt worden, besproken worden.
5.1 De Wiskundige Methoden Een tracking algoritme heeft tenminste twee taken. Ten eerste is een deel van het algoritme verantwoordelijk voor het vergelijken van een model met delen van de afbeelding waarin het te volgen object zich bevindt (Matching). Een dergelijk model noemt men in de gangbare literatuur ook wel een template. Het vergelijken vindt plaats in een bepaald zoekgebied. De tweede taak bepaalt waar dit zoekgebied in het volgende frame ongeveer moet liggen en hoe groot dit zoekgebied moet zijn (Tracking). Verder kan een tracking algoritme nog optionele taken hebben zoals het opslaan van meetgegevens of het doorsturen van meetgegevens naar een andere applicatie. Voor beide taken zullen nu een aantal wiskundige methoden beschreven worden die toegepast kunnen worden. Ook zal bij een aantal methoden vermeld worden in welke papers ze gebruikt zijn. In appendix A staan van een tweetal methoden ter verduidelijking een klein voorbeeld uitgewerkt. Hieronder in figuur 4 staan de methoden opgesomd die behandeld worden: Matching • Som van het kwadratische verschil • Hausdorff afstand • Hough transformatie • Mean Shift
Tracking • Gemiddelde verplaatsing • Kalman filter
Figuur 4 – Verschillende methoden voor Matching en Tracking die in de literatuur toegepast worden.
15
Tracking Filter voor het component Video Meten in Coach
5.1.1 Matching 5.1.1.1 Som van het kwadratische verschil
Dit is relatief een eenvoudige methode om de beste match te vinden in een zoekgebied. Deze methode vergelijkt pixel intensiteiten en werkt vaak op maar een kanaal van het kleuren type (bijvoorbeeld RGB), maar is uiteraard ook uit te voeren voor alle kanalen en dan het beste resultaat te kiezen. In elk frame gaat het matchen volgens deze regel: TH 1 TW 1
( I (i + x, j + y ) T ( x, y )) 2
res(i,j) = y =0
x =0
waarbij TH staat voor de hoogte van het template in pixels en TW voor de breedte van het template in pixels. x en y zijn de coördinaten met bereik gelijk aan TW en TH , T(x,y) geeft de pixelwaarde van het template in het punt (x,y) en I(x,y) geeft de pixelwaarde in het huidige frame in het punt (x,y). Hoe lager de waarde van res(i,j) is, hoe kleiner het totale kwadratische verschil is en dus hoe meer het template lijkt op het geselecteerde beeld in het frame. We laten vervolgens het template matchen met alle gebieden van formaat TWxTH in het zoekgebied en kiezen tenslotte die i en j die het kleinste kwadratische verschil oplevert. Dit zijn dan de berekende nieuwe coördinaten van het te volgen object. Het voordeel van deze methode is dat deze relatief eenvoudig te implementeren en begrijpen is. Het nadeel is dat wanneer de grootte van het zoekvenster verdubbeld wordt, de benodigde rekenkracht kwadratisch toeneemt. Dit venster mag dus niet te groot worden gekozen. Een ander nadeel is dat deze methode gevoelig is voor outliers2. 5.1.1.2 Hausdorff afstand en Transformaties
De Hausdorff afstand is als volgt gedefinieerd: Laat A en B een eindige verzameling punten zijn. Dan is de Hausdorff afstand: H(A,B) = max{h(A,B), h(B,A)} met h(A,B) = max min || a – b || (1) a A
b B
h(A,B), ook wel de directed Hausdorff genoemd, vindt het punt a in A, dat het verst weg ligt van elk punt in B en meet de afstand van a tot zijn dichtst bijgelegen buurpunt in B. H(A,B) meet dus de mate van gelijkheid van twee verzamelingen. Hoe kleiner deze uitkomst is, hoe meer de twee verzamelingen op elkaar lijken. Als de Hausdorff afstand d is, dan moet elk punt in A binnen de afstand d liggen van een willekeurig punt in B. In appendix A.1 staat een voorbeeld van een berekening van een Hausdorff afstand tussen twee verzameling punten. 2
Met een outlier wordt hier een pixel bedoeld die een grote afwijkende pixelwaarde heeft ten opzichte van zijn buurpixels.
16
Tracking Filter voor het component Video Meten in Coach De Hausdorff afstand bepaling heeft als nadeel dat deze methode ook erg gevoelig is voor outliers: Wanneer een punt a in A ver weg ligt van de rest van de punten in A heeft dit meteen grote gevolgen voor de Hausdorff afstand. Dit is bijvoorbeeld het geval bij gedeeltelijke occlusie of ruis in het beeld. Om de outliers een minder grote invloed te laten hebben kunnen we vergelijking (1) aanpassen door te zeggen: h(A,B) = k th min || a – b || (2) a A b B
We kiezen dus nu de k-de grootste afstand in plaats van de maximale afstand tussen twee verzamelingen. Nu de toepassing van deze methode met betrekking tot matching: Stel we nemen de verzamelingen A en B. Laat verzameling A de verzameling beeld punten van een geselecteerd gebied zijn en B een verzameling punten in het model (een template die bijvoorbeeld verkregen is uit het vorige frame van de video). De beide verzamelingen zijn verzamelingen binaire punten van randen en worden dus verkregen door een edge detection3 methode uit te voeren op het beeld. Verder is er een transformatie t van B naar de 2D ruimte A. Dan geldt dat voor die waarden van t waar h(t(B),A) klein is, de transformaties van het model het meest waarschijnlijk is. Dus voor een reeks waarden voor t moet h(A,t(B)) worden geëvalueerd om de minimum afstand in de transformatie zoekruimte te vinden. [A7] Een aantal artikelen [A6] [A7] [A10] maken gebruik van deze Hausdorff afstand (2) en transformaties. Deze algoritmes gebruiken deze afstand dus om aan te geven in hoeverre een geselecteerd gebied (vaak een verzameling randen) lijkt op het model. 5.1.1.3 Hough Transformatie
De Hough Transformatie (HT) werd in 1962 uitgevonden door P.V.C.Hough. Het is een methode die globale patronen in een afbeelding kan herkennen door middel van herkenning van locale patronen in een getransformeerde parameter ruimte. Deze methode is vooral goed te gebruiken wanneer de patronen veel ruis bevatten, onderbrekingen hebben of erg discreet zijn. Met deze methode kunnen objecten worden gevonden die geparametriseerd zijn in een passende parameter ruimte. Voorbeelden zijn rechte lijnen, polynomen en cirkels. De methode wordt vooral toegepast in 2D maar kan ook voor hogere dimensies gebruikt worden. Ter verduidelijking staat er in appendix A.2 hoe via een Hough transformatie rechte lijnen in een afbeelding herkend kunnen worden. Wanneer we nu bijvoorbeeld een vierkant object willen volgen zoeken we in het resultaat vier lijnen die samen een vierkant gebied omsluiten en kiezen hiervan het centrum coördinaat om door te geven als tracking resultaat.
3
Een van de bekendste edge detectors is de Canny Edge Detector. Deze detector geeft een verzameling punten terug die tot de rand van een geselecteerd object behoren.
17
Tracking Filter voor het component Video Meten in Coach De Hough transformatie wordt onder andere toegepast in [A12] in combinatie met een Kalman filter (zie paragraaf 5.1.2.2). In [A13] wordt een uitgebreidere Hough Transformatie besproken: de Fuzzy Generalized Hough Transformation, waarbij ook objecten redelijk goed gevolgd kunnen worden die bestaan uit combinaties van geparametriseerde componenten. Deze methode heeft als nadeel dat het maar voor een gering aantal doeleinden gebruikt kan worden. Het te volgen object moet zoals gezegd parametriseerbaar zijn. Verder mag de achtergrond niet te complex zijn [A13]. Het grote voordeel van deze methode is dat het zeer snel werkt, de berekening per frame is immers beperkt tot het vinden van punten die tot randen behoren en vervolgens hoeven alleen die punten getransformeerd worden. 5.1.1.4 Mean Shift analyse
Deze methode, de “gemiddelde verschuiving” methode, kan gebruikt worden om objecten te tracken terwijl de camera beweegt. De methode maakt sterk gebruik van de kleur van het te volgen object en kan dus daarom alleen toegepast worden wanneer de kleur van het object niet te snel veranderd. Gevolg is ook dat er niet teveel veranderingen mogen optreden in de belichting in de scène. Ook deze methode is weer een matching methode; een algoritme gebaseerd op de Mean Shift is in staat om te bepalen welk gedeelte in het frame het meest lijkt op een gegeven model (template). In [A15] wordt de Mean Shift toegepast voor het match gedeelte van het algoritme. Het verschil met andere matching methodes is dat deze methode niet uitputtent zoekt in het zoekgebied naar de beste match. Bij de drie eerder beschreven methoden is dit namelijk wel het geval. Bij de Mean Shift methode schuift het model als het ware bij elke iteratie steeds dichter naar het te vinden object toe. (zie figuur 5) Het algoritme doet dit door te kijken naar de spatiele gradient van elke meting. De gradiënt bepaalt namelijk de richting waarlangs een functie het snelst verandert.
Figuur 5 – De Mean Shift methode zorgt er voor dat er niet uitputtend in het zoekgebied gezocht hoeft te worden maar het model convergeert als het ware naar de locatie van het te volgen object.
Voor het schatten van de locatie van het object in opvolgende frames gebruiken de auteurs een Kalman filter (zie 5.1.2.2). De methode beschreven in [A15] heeft veel voordelen: het algoritme kan overweg met gedeeltelijke occlusie, veel ruis, herschaling 18
Tracking Filter voor het component Video Meten in Coach en rotaties van het te volgen object. Bovendien is het niet erg wanneer de camera beweegt. Het algoritme is ook nog eens real-time uit te voeren op een gemiddelde computer. Het nadeel is echter nog dat de kleur van het object sterk moet verschillen van de kleur van die van de achtergrond.
5.1.2 Tracking 5.1.2.1 Gemiddelde verplaatsing
De intuïtief eenvoudigste manier om te schatten waar het zoekvenster in het volgende frame komt te liggen is door bij te houden wat de verplaatsing van het zoekvenster in n eerdere frames was. Hieruit kan dan worden geschat met welke verplaatsing in de x en y richting het zoekvenster verder moet gaan. Zo kan dus een voorspelling maken waar het te volgen object in het volgende frame zich ongeveer zou moeten bevinden. Ook wanneer een object, dat we willen volgen, voor de camera tijdelijk niet zichtbaar is, omdat er andere objecten tussen de camera en het te volgen object staan, zouden we met deze methode toch kunnen schatten waar het te volgen object in het volgende frame zou moeten zijn. Wanneer we deze techniek gebruiken voor tracken moet de matching methode kunnen detecteren wanneer occlusie plaats vindt. Bovendien moet de matching methode kunnen waarnemen wanneer het object weer voldoende zichtbaar is zodat deze weer door kan gaan met zijn werk. Het grote voordeel van deze methode is dat het eenvoudig te implementeren is en de methode kan omgaan met (gedeeltelijke) occlusie. Het nadeel is echter dat wanneer het te volgen object plots van richting veranderd (denk bijvoorbeeld aan een honkbal die weggeslagen wordt) dat de locatie van het zoekvenster dan niet meer juist wordt geschat in het volgende frame. Het voorwerp moet dus in het gunstigste geval met constante snelheid bewegen. In [A5] gebruiken de auteurs deze methode en voor het matching deel van het algoritme wordt robust approximation gebruikt, een variant op de kwadratische verschil methode die ik beschreef in paragraaf 5.1.1.1. Om het schatten te optimaliseren wordt in paragraaf 5.1.2.2 een complexere methode besproken die vaak wordt toegepast in papers over tracking. 5.1.2.2 Adaptive Kalman filter
Wat een Kalman filter simpel gezegd moet doen is het leren van fouten die het gemaakt heeft in het verleden; De bedoeling is dat het filter de onvoorspelbaarheid moet minimaliseren. Een Kalman filter kan recursief de status van een bepaald object berekenen (schatten) op basis van een aantal metingen. Wanneer we kijken naar object tracking, wordt de status van een object gegeven door de locatie en beweging van het object. Een Kalman filter geeft ook de covariantie4 van deze status weer. Op deze manier 4
De covariantie is hier een maat voor de spreiding van twee variabelen x en y in n frames gegeven door n
cov( x, y ) = waar
i =1
( xi
µ x )( y i
µy )
n
µ x en µ y het gemiddelde is van alle x resp. alle y. cov(x,y) 19
geeft dus de correlatie weer tussen x en y.
Tracking Filter voor het component Video Meten in Coach kunnen we goed redeneren over de fout en onzekerheid van elke status. Het schatten van de status van het object (de locatie en beweging) door het Kalman filter resulteert in het efficiënter werken van een willekeurige matching methode omdat het zoekgebied drastisch verkleind wordt. Een Kalman filter heeft dus niet als doel om een object exact te volgen maar maakt een model van de beweging die het best past bij de eerder verkregen schattingen van het filter. Een Kalman filter is een optimale lineaire schatter en bovendien een recursief processing algoritme. • Optimaal wil hier zeggen: een Kalman filter verenigt alle mogelijke data dat aan het filter aangeboden kan worden en kan bovendien elke meting verwerken, ongeacht de precisie. Het filter komt zo tot een schatting van de huidige waarde van een bepaalde variabele, waar we in geïnteresseerd zijn. • Recursief wil hier zeggen: Niet alle voorgaande data gegenereerd door een Kalman filter hoeft worden opgeslagen en worden herberekend wanneer een nieuwe meting plaatsvindt, wat dus veel geheugen bespaart. Dit is uiteraard van groot belang bij het implementeren van een dergelijk filter. De schatting van de huidige waarde van een bepaalde variabele waarin we geïnteresseerd zijn is zodanig dat de fout, statistisch gezien, geminimaliseerd is. Ofwel, wanneer we een aantal soortgelijke filters veelvuldig zouden toepassen op het systeem, dan zou de Kalman filter gemiddeld een beter resultaat geven dan alle andere filters. Het nadeel van deze methode is dat het wederom niet goed werkt wanneer de achtergrond van het beeld erg complex is. Dit komt omdat een Kalman filter een Gaussische5 representatie van een kansverdeling gebruikt. Hierdoor blijven er meerdere locaties over die mogelijk in aanmerking komen waar het zoekgebied zou moeten komen, wegens de Bell-shape van de kansverdeling. Samples die volgens het model dicht bij de juiste positie liggen krijgen zo snel een hoge weging. Er zijn verscheidende artikelen die deze methode gebruiken zoals [A3]. In [A4] en [A5] laten de auteurs zien dat het Kalman filter niet alleen gebruikt kan worden voor het bepalen van de zoekruimte maar ook om veranderingen in oriëntatie en belichting van het te volgen object te detecteren. Deze artikelen zijn geschreven door mensen uit de MMIS groep in Amsterdam.
5
Een stochastische variabele x met een Gaussische kansverdeling, ook wel normale verdeling, met
gemiddelde
µ
en variantie
2
heeft een kansdichtheid die voldoet aan:
20
f ( x) =
1 2
e
1 x µ 2 ( ) 2
Tracking Filter voor het component Video Meten in Coach
5.2 Samenvatting Matching en Tracking Methoden Om een duidelijk overzicht te krijgen staan in de figuren 6 en 7 tabellen waarin staat of de methoden bepaalde eigenschappen wel of niet hebben. Matching Makkelijke implementatie? Voorbewerking nodig? Gevoelig voor verandering in belichting/kleur
Som van het kwadratische verschil Ja
Hausdorff afstand
Hough transformatie
Mean Shift
Nee
Ja
Nee
Nee
Ja, edge detection Nee
Ja
Ja, edge detection Nee
Ja
Ja
Ja
Nee, wanneer de generalized Hausdorff afstand (2) wordt gebruikt Ja
Gevoelig voor verandering in vorm object? Gevoelig voor outliers/ruis? Uitputtend zoekalgoritme? Toename rekentijd bij verdubbelen grootte zoekgebied? Te volgen objecten moeten parametriseerbaar zijn? Gevoelig voor herschaling van het object?
Ja
Nee
Ja
Nee, behalve als Nee de vorm van het object niet meer parametriseerbaar wordt. Nee Nee
Nee
Nee
Altijd kwadratisch
Afhankelijk van het aantal randgebieden in het zoekgebied
Afhankelijk van het aantal randgebieden in het zoekgebied
Nee
Nee
Nee
Altijd < kwadratisch, hang af van de grootte van het object. Ja
Ja
Nee
Nee
Ja
Figuur 6 –Samenvattend de eigenschappen van alle behandelde matching methoden. Deze methoden hebben dus te maken met de manier van vergelijken van samples met het model.
21
Tracking Filter voor het component Video Meten in Coach
Tracking
Gemiddelde verplaatsing
Makkelijke Ja implementatie? Bestand tegen Ja, zolang de occlusie? verplaatsing lineair is en de hoek constant Externe Ja, aantal frames die parameters gebruikt worden voor nodig? het model Recursieve Nee methode? Gevoelig voor Ja mismatches ? Rekentijd? Weinig
Kalman filter
Nee
Zoekvenster updaten door het centrum samen te laten vallen met het centrum van het template Ja
Ja
Nee
Ja, beginstatus
Nee
Ja
Nee
Nee
Ja
Weinig
Geen
Figuur 7 – Samenvattend de eigenschappen van de behandelde tracking methoden. Deze methoden hebben dus te maken met de bepaling van de positie van het zoekvenster
Gedurende de stage is er gesproken met Hieu Tat Nguyen, hij is postdoc bij de MMIS groep en hij heeft een aantal artikelen gepubliceerd over object tracking. In zijn artikelen gebruikt hij Kalman filters (zie paragraaf 5.1.2.2) voor het detecteren van veranderingen in oriëntatie en belichting van het te volgen object. Voor het schatten van de positie van het zoekvenster gebruikt hij in [A5] een methode gelijk aan wat beschreven is in paragraaf 5.1.2.1. Zijn methode kan dus goed omgaan met gedeeltelijke occlusie. Nguyen gaf als advies om zijn methode te gebruiken wanneer er (gedeeltelijke) occlusie plaatsvindt in de betreffende video’s. Wanneer er geen occlusie plaats vindt raadde hij aan om een eenvoudigere methode te gebruiken, namelijk de kwadratische verschil methode (paragraaf 5.1.1.1) of de robust approximation. Dit is een uitbreiding op de kwadratische verschil methode die niet het kwadraat van het verschil neemt maar het verschil is de input van een bepaalde functie f (I(x,y)-T(x,y)). Deze functie f kan dan zo gedefinieerd worden dat outliers minder zwaar meetellen voor het resultaat zodat uiteindelijk een beter resultaat verkregen wordt. Nadat de testvideo’s gekozen zijn (zie paragraaf 6.3) zal een beslissing worden genomen welke methoden gebruikt gaan worden voor het te ontwerpen tracking filter in dit project.
22
Tracking Filter voor het component Video Meten in Coach
6 Ontwerp van het Algoritme In dit hoofdstuk wordt het ontwerp van het tracking algoritme besproken. Bij dit ontwerp hoort de requirements analyse, een flow chart van de gemaakte algoritmes en de functieprototypes met een beschrijving van de werking van deze functies. Voordat deze delen beschreven worden, wordt er eerst bij 6.1 beschreven om wat voor soort video’s het gaat die in Coach standaard meegeleverd worden. Deze video’s worden als uitgangspunt genomen voor het te ontwerpen algoritme.
6.1 Eigenschappen van Video’s Met mijn begeleider (opdrachtgever) en andere mensen uit het Amstel Instituut is besproken wat voor soort voorbeeld filmpjes in het pakket Coach zitten. Hierop moet namelijk het te ontwerpen algoritme afgesteld worden. De belangrijkste eigenschappen van de sample video’s, die nu in de huidige versie van Coach zitten, en de video’s die mogelijk in een nieuwe versie worden toegevoegd, zijn: 1. De minimale resolutie van de sample video’s is 320x240 en de kleurdiepte is minimaal 24 bits6. 2. De frame-rate van de sample video’s is minimaal 25 fps. 3. De gebruikte codecs voor de sample video’s zijn Cinepak7 of Intel Indeo8 (IR32) 4. De sample video’s hoeven niet perspectief correct te zijn. Het te volgen object hoeft dus niet noodzakelijk in een vlak te liggen parallel aan het projectievlak van de camera. 5. In de sample video’s mogen camerabewegingen voorkomen. Hierdoor verandert mogelijk de grootte, detaillering, vorm en belichting van het te volgen object. 6. In de sample video’s mag worden in- en uitgezoomd. Hierdoor verandert de grootte en mogelijk de detaillering van het te volgen object. 7. Het te volgen object kan door occlusie tijdelijk niet zichtbaar zijn vanuit het camera oogpunt. Ook kan het te volgen object (tijdelijk) buiten de grenzen van het beeld vallen. 8. De meeste video samples komen uit sportverslagen die opgenomen zijn van tv. 9. Voorwerpen die gevolgd moeten worden zijn vaak lichaamsdelen (bijvoorbeeld hoofd van een sprinter of een heup van een turnster) of bolvormige voorwerpen zoals het geval is bij balsporten. 10. Op sommige sample video’s is een vertragingsfactor toegepast omdat het voorwerp ‘in het echt’ zeer snel beweegt. Denk hierbij aan een bal, die met een knuppel weggeslagen wordt door een honkballer. 11. Het is niet zo dat altijd slechts 1 object in een sample video beweegt. Er kunnen dus meerdere bewegende objecten aanwezig zijn. Denk hierbij bijvoorbeeld aan een video waarop twee auto’s te zien zijn die langs elkaar rijden. 12. De video samples hebben in principe niet veel last van ruis, alleen doordat de meeste video samples van erg lage resolutie zijn valt er wel veel detail weg. 6
Een kleurendiepte van 24 bits heeft als gevolg dat het bestand uit 3 kanalen bestaat van basiskleuren. In het RGB model is dit uiteraard rood, groen en blauw. Elk kleurcomponent kan een intensiteit hebben die varieert van 0 tot 255. 7 Informatie, voor- en nadelen van de CinePak codecs staan hier opgesomd: http://www.siggraph.org/education/materials/HyperGraph/video/codecs/Cinepak.html 8 Informtatie, voor- en nadelen zijn van de Intel Indeo codecs staan hier opgesomd: http://www.siggraph.org/education/materials/HyperGraph/video/codecs/Indeo.html
23
Tracking Filter voor het component Video Meten in Coach 13. De video samples die buiten opgenomen zijn terwijl de zon schijnt, of video samples die met kunstlicht binnen zijn opgenomen kunnen schaduwen bevatten. Dus ook kan er een schaduw zichtbaar worden van het te volgen object. Deze schaduw kan de zelfde vorm hebben als het object. Opmerking: De eigenschappen 4,5 en 6 gelden niet voor filmpjes die in de huidige versie van Coach beschikbaar zijn, echter in versie 6 is men van plan om filmpjes toe te voegen die de eigenschappen 4, 5 en 6 wel hebben. Bovendien hebben deze filmpjes een grotere resolutie.
6.2 Requirements Analyse Het te gebruiken algoritme moet voldoen aan een aantal systeemeisen. Deze eisen zijn vastgelegd in samenspel met de opdrachtgever. Vanwege de relatief korte duur van deze stage is er te weinig tijd om een algoritme te maken die om kan gaan met alle hier boven genoemde eigenschappen van de video’s. Er is dus een keuze gemaakt welke eigenschappen door het algoritme wel ondersteund gaan worden en welke niet. In deze paragraaf zullen de genoemde systeemeisen opgesomd worden in drie delen. Het eerste deel betreft de eisen van het algoritme zelf. Dit zijn de eisen die voor dit project van belang zijn, bij het ontwerpen en implementeren van het algoritme. In het tweede deel staan de eisen met betrekking tot de gebruikers interactie. Deze eisen zijn pas van belang wanneer een demonstratie applicatie gemaakt wordt of wanneer het filter uiteindelijk in Coach geïntegreerd is. Zie ook hoofdstuk 8 en 9 Tenslotte staan in het derde deel de eisen die betrekking hebben op transformaties die het algoritme zou kunnen uitvoeren. Dit is dus een uitbreiding op het basis algoritme beschreven door de eisen van deel 1. Vanwege de korte duur van de stage valt dit deel buiten dit project. 1. Tracking 1. Aan de hand van invoer van een aantal parameters voor een klein aantal (< 4) frames, door een gebruiker, moet het algoritme in staat zijn om 1 of meerdere objecten in de video sample te tracken. 2. Het algoritme moet in staat zijn om meetgegevens te genereren en deze door geven aan een externe applicatie. 3. Het algoritme moet een nieuwe video afleveren waarin de te volgen objecten gemarkeerd zijn door een punt of vierkant. 4. Het algoritme moet real-time werken voor video’s tot 30 frames per seconde, ook op de wat tragere computers van 1 tot 2 Ghz. 5. Het algoritme moet in staat zijn om te schatten waar het te volgen object is, wanneer deze door occlusie niet zichtbaar is. 6. Het algoritme moet in staat zijn op om de componenten van elk pixel in elk frame te kunnen uitlezen of veranderen 7. Het algoritme moet uit de binnenkomende video stream kunnen bepalen welk bestandsformaat wordt gebruikt. 8. Het algoritme moet ook een continue datastroom aan kunnen zoals bijvoorbeeld de stroom data afkomstig van een webcam.
24
Tracking Filter voor het component Video Meten in Coach 9. Het algoritme moet in staat zijn om informatie over reeds verwerkte frames te hergebruiken in de huidige en de nog te verwerken frames. 10. Het algoritme mag geen onvoorzien of willekeurig gedrag vertonen. 11. Een meting is fout als het te volgen object volledig buiten het gebied (met de grootte van het template) valt waar het object volgens het algoritme zou moeten liggen. 12. Het foutpercentage mag niet hoger liggen dan 5%. (in hoogstens 5% van het totaal aantal frames mag een fout zitten).
2. Interactie met de gebruiker 13. Het algoritme moet vertraagd gesimuleerd kunnen worden waarbij tussenresultaten meteen zichtbaar worden. 14. Indien er vertraagd gesimuleerd wordt: De gebruiker moet het tracking proces kunnen onderbreken en zonodig handmatig correcties kunnen aanbrengen in frames, wanneer het object op een bepaald traject niet juist gevolgd wordt. 15. De gebruiker moet snel kunnen zien welke meting bij welke frame van de video hoort. 16. Het instellen van de parameters moet gebruikersvriendelijk zijn: al de overbodige wiskundige details moeten niet zichtbaar worden en de user interface9 moet duidelijk zijn. 17. De gebruiker moet ook andere video’s kunnen openen en het algoritme hierop laten toepassen. In plaats van een video moet ook een webcam gebruikt kunnen worden als bron.
3. Uitbreiding: transformaties 18. Het algoritme moet in staat zijn om te zien wanneer een scène eindigt. Een scène eindigt wanneer er van camera gewisseld wordt. Het tracking proces dient dan automatisch te stoppen. 19. Het algoritme moet in staat zijn om te bepalen of de oorsprong10 gedurende de video sample van plaats is veranderd. 20. Het algoritme moet in staat zijn om te bepalen of er herschaling11 plaatsvindt in het video sample. 21. Het algoritme moet in staat zijn om nog steeds goed te tracken wanneer de camera van positie veranderd (18) en er bovendien in- of uitgezoomd (19) wordt.
Opmerking bij punt 18 en 19: deze transformaties kunnen het beste in een aparte filter geïmplementeerd worden.
9
Het betreft hier dus de grafische omgeving waarin parameters van het algoritme kunnen worden gewijzigd door de gebruiker. 10 De oorsprong is de plaats waar in gedachte de oorsprong van een assenstelsel wordt neergelegd. De meetgegevens die gegenereerd worden nemen dit assenstelsel als basis. De oorsprong verandert wanneer de camera beweegt 11 Er moet herschaling worden toegepast wanneer de camera in- of uitzoomd.
25
Tracking Filter voor het component Video Meten in Coach
6.3 De gekozen video’s De video’s die gebruikt gaan worden om het te ontwerpen algoritme te testen komen op één na uit Coach 5, de huidige versie die nu op middelbare scholen gebruikt wordt. De laatste video is rechtstreeks opgenomen van de tv. Deze video heeft een hogere resolutie maar is wel een stuk complexer vanwege de vele camera bewegingen en schakelen tussen camera’s. In figuur 8 op deze en de volgende bladzijde staan een tweetal frames van elke video. Ze staan geordend op moeilijkheid, waarbij het object in video 1 relatief eenvoudig te tracken is en het object in video 5 moeilijk te tracken is. 1
object: softbal
moeilijkheid: schaduw van de bal heeft dezelfde vorm.
object: Basketbal
moeilijkheid: deel achtergrond zelfde kleur als de basketbal (lijnen op de muur)
objecten: Beide auto’s
moeilijkheid: witte auto tijdelijk niet zichtbaar
2
3
26
Tracking Filter voor het component Video Meten in Coach 4
object: deel van een lichaam
moeilijkheid: object verandert van vorm
object: tennisbal
moeilijkheid: camerabewegingen, perspectief en vervormingen van het object
5
Figuur 8 – De gekozen test video’s geordend op moeilijkheid waarbij het object in video 1 relatief makkelijk te tracken is en het object in video 5 moeilijk te tracken is. Het is uiteraard niet zo dat het algoritme alleen deze video’s goed moet aankunnen, maar deze selectie wel een goed beeld geeft van de moeilijkheden die kunnen ontstaan wanneer tracking toegepast wordt. Zoals beschreven in de systeemeisen moet mijn ontworpen filter de objecten in de video’s 1,2,3 en 4 goed kunnen tracken. Voor de laatste video, waar ook camerabewegingen in voor komen, geldt dat het algoritme uitgebreid moet gaan worden en dus complexer wordt (zie de eisen bij het derde deel van de Requirements analyse).
6.4 Keuze van het algoritme Aan de hand van het literatuuronderzoek (hoofdstuk 5), de requirements analyse (paragraaf 6.2), en de gekozen video’s (paragraaf 6.3) is er een keuze gemaakt voor een bepaald type algoritme. Aangezien in alle testvideo’s (op video 3 na) geen gedeeltelijke occlusie plaatsvindt is ervoor gekozen om eerst de kwadratische verschil methode (paragraaf 5.1.1.1) te implementeren (voor alle drie de RGB kanalen) om te kijken hoe goed deze werkt op video’s 1,2,4 en 5. Deze keuze is gemaakt omdat uit de genoemde testvideo’s blijkt dat er 27
Tracking Filter voor het component Video Meten in Coach weinig ruis aanwezig is en de te volgen objecten niet van of nauwelijks van kleur en vorm veranderen. Uit de tabel in figuur 6 blijkt dan dat deze methode de eenvoudigste is om te kiezen. De locatie van het zoekvenster wordt steeds bijgwerkt door het midden van het zoekvenster mee te laten verplaatsen met het midden van het template. In paragraaf 7.3 rapporteer ik mijn testresultaten van deze methode. Deze beschreven methode gaat zeker fout wanneer deze toegepast wordt op video 3 vanwege de occlusie. Het is dan ook te zien dat het zoekvenster daar dan ook “wild weg springt” wanneer de witte auto achter de zwarte auto verdwijnt. De witte auto wordt ook als hij weer verschijnt niet opgepakt door de tracker omdat de witte auto zich dan buiten het zoekgebied bevindt. Om video 3 ook aan te kunnen is het nodig om te schatten waar het object is wanneer het verborgen is door occlusie. Hiervoor wordt de methode gebruikt die ik beschreef bij paragraaf 5.1.2.1. De afstandsverschillen van het object zullen dus worden bijgehouden uit een n-tal eerdere frames. Uit deze gegevens wordt dan bepaald waar het object zich moet bevinden als het object niet zichtbaar is. Deze manier komt overeen met de methode die Nguyen (zie paragraaf 5.2) gebruikt heeft om te voorspellen waar het zoekvenster terecht komt. De keuze voor deze methode is gemaakt op aanraden van Nguyen en het feit dat de implementatie eenvoudig is en weinig rekentijd in beslag neemt. In paragraaf 7.3 zullen ook de testresultaten van deze methode beschreven worden.
6.5 Flow Chart (Stroomdiagram) Voor de twee geïmplementeerde tracking algoritmen zal ik nu een flow chart geven waarin overzichtelijk staat hoe mijn implementaties van de algoritmes in elkaar zitten. •
Het eerste diagram geeft het verloop aan van het algemene deel dat onafhankelijk is van het gekozen algoritme. Het zijn dus de voorbereidingen, voorbewerkingen en nabewerkingen die op elk frame van de video uitgevoerd moeten worden. In figuur 9 staat dit diagram. Rode blokken zijn black-boxes. in de volgende twee diagrammen worden deze processen voor beide algoritmes gedetailleerd weergegeven. De groene blokken zijn optioneel en worden alleen uitgevoerd wanneer de gebruiker van het filter de bijbehorende optie heeft ingeschakeld.
•
Het tweede diagram laat zien hoe de “kwadratisch verschil” methode in zijn werk gaat. Het beschrijft dus de details van de twee black-boxes in het eerste diagram, wanneer gekozen worde voor deze methode. Dit diagram staat afgebeeld in figuur 10.
•
Het laatste diagram laat tenslotte zien hoe ik het algoritme heb geïmplementeerd dat er voor zorgt dat het filter ook (gedeeltelijke) occlusie aankan. Het is te zien dat er veel overeenkomsten zijn met het tweede diagram omdat het matching proces het zelfde blijft en alleen het updaten van het zoekvenster gedeeltelijk anders verloopt. In figuur 11 staat dit diagram afgebeeld.
28
Tracking Filter voor het component Video Meten in Coach START
Wacht totdat gebruiker in de video klikt
Sla x en y coördinaat op van het aangeklikte punt Verwijder oud coördinaatbestand (indien aanwezig) Reset alle arrays door geheugen op te schonen Set de locatie van het template met grootte TWxTH
Verplaats het template zo dat het binnen de video valt
nee
Template valt binnen de grenzen van de video?
Maak een zoekvenster met grootte WWxWH rondom het template Verplaats het zoekvenster zo dat het binnen de video valt
nee
zoekvenster valt binnen de grenzen van de video?
Pas een Matching methode toe om de beste match te vinden binnen het zoekgebied Update het zoekvenster met een bepaalde methode
Verplaats het zoekvenster zo dat het binnen de video valt
zoekvenster valt binnen de grenzen van de video?
Laat de positie van het template en zoekvenster zien in de video Schrijf gevonden coördinaten naar bestand
Maak al het gebruikte geheugen vrij
nee
volgend frame van de (video)stream beschikbaar om bewerkingen op uit te voeren?
EINDE
Figuur 9 – Flow Chart van het algemene deel van het tracking filter
29
Tracking Filter voor het component Video Meten in Coach
START
Set de positie van het template linksboven in het zoekvenster en stel i = 0 Bereken en sla op: (I(i+x,j+y)-T(x,y))2 voor elke xeTW en elke yeTH *
nee
nee
Valt het template bij 1 plaats naar onder opschuiven nog binnen de grenzen van het zoekvenster
Valt het template bij 1 plaats naar rechts opschuiven nog binnen de grenzen van het zoekvenster?
Schuif de positie van het template 1 pixel naar beneden en volledig naar links, verhoog j met 1 en set i terug op 0
Schuif de positie van het template 1 pixel op naar rechts en verhoog i met 1
* Zie hoofdstuk 5.1.1.1 voor verdere uitleg
Kies die x en y waarvoor geldt dat (I(x,y)-T(x,y))2 minimaal is. in dit coördinaat (x,y) was de match het best
Update het zoekvenster zodat het midden hiervan komt te liggen op coördinaat (x,y) waar de match het best was
EINDE
figuur 10 – Flow Chart van het “kwadratische verschil” algoritme 30
Tracking Filter voor het component Video Meten in Coach
Set x_old = x en y_old = y Set de positie van het template linksboven in het zoekvenster, stel i = 0 en stel n = 0 (statisch!) Bereken en sla op: (I(i+x,j+y)-T(x,y))2 voor elke xeTW en elke yeTH *
nee
nee
Valt het template bij 1 plaats naar onder opschuiven nog binnen de grenzen van het zoekvenster
Schuif de positie van het template 1 pixel naar beneden en volledig naar links, verhoog j met 1 en set i terug op 0
Valt het template bij 1 plaats naar rechts opschuiven nog binnen de grenzen van het zoekvenster?
Schuif de positie van het template 1 pixel op naar rechts en verhoog i met 1
* Zie hoofdstuk 5.1.1.1 voor verdere uitleg
Kies die x en y waarvoor geldt dat (I(x,y)-T(x,y))2 minimaal is. in dit coördinaat (x,y) was de match het best
nee N = MAX_DISTANCES ? (constante in te stellen door gebruiker) Bereken en sla op: dx en dy door x – x_old en y – y_old te berekenen. Verhoog verder n met 1 Update het zoekvenster zodat het midden hiervan komt te liggen op coördinaat (x,y) waar de match het beste was
EINDE
Bereken eenmalig de gemiddelden van de verzamelde dx’en en dy’en Update de locatie (x,y) van het midden van het zoekvenster door te stellen: nieuwe x = huidige x + gemiddelde dx’en nieuwe y = huidige y + gemiddelde dy’en
Figuur 11 – Flow Chart van het algoritme dat er voor zorgt dat ook objecten die tijdelijk niet zichtbaar zijn, toch goed gevolgd worden zolang de snelheid van het object nagenoeg constant is.
31
Tracking Filter voor het component Video Meten in Coach
6.6 Functieprototypes In deze paragraaf staat een opsomming van de functies (in pseudocode) die geïmplementeerd of aangepast zijn in dit project.. In paragraaf 7.2 volgen een aantal belangrijke implementatie details zodat de onderlinge relatie tussen deze functies duidelijk wordt. Veel functies hebben dezelfde namen als de processen die beschreven staan in de flow charts in de vorige paragraaf. // in deze functie vind het werkelijke tracking process plaats void Transform(video_frame); // wanneer de gebruiker op stop drukt worden alle globals gereset void Stop(); // Haal de huidige parameters op die ingesteld zijn door de gebruiker void GetParams(char *parameters); // Sla de huidige parameters op die ingesteld zijn door de gebruiker void SetParams(char *parameters); // iplPutText: print de string xTxt in de video op locatie (x,y) void iplPutText(bron, int x, int y, char *sTxt); // WriteCrdsToFile: schrijft de coördinaten van het te volgen object // naar een bestand voor elk frame van de videostream // voorbeeld: // // #399 Wed Apr 21 12:06:01 2004 // X=339 // Y=258 void WriteCrdsToFile(int number, int x, int y) // FileExists: controleer of een bestand met naam
bestaat. // Geeft –1 terug wanneer dit niet het geval is. int FileExist(FILE filename); // geheugen opschonen (ReleaseImages) void Cao_simpletrack_cv::FreeImages(); // NewDistance: vult de arrays dx and dy tot ze vol zitten. Wanneer // deze functie aangeroepen wordt als de arrays vol zitten, wordt –1 // terug gegeven. int Cao_simpletrack_cv::NewDistance(int x, int y); // CalculateAverage: berekent het gemiddelde van MAX_DISTANCE elementen // in het array ‘avg’ double Cao_simpletrack_cv::CalculateAverage(double *avg);
32
Tracking Filter voor het component Video Meten in Coach
7 De Implementatie van de gekozen algoritmes In dit hoofdstuk zal ten eerste bespreken worden welke tools gebruikt zijn om het filter te implementeren. Ook wordt hierin aangegeven hoe het filter te compileren is. Ten tweede zullen een aantal implementatie details volgen voor die functies waar wat extra documentatie nodig is. Ten derde staan er in dit hoofdstuk wat test resultaten, om zo de prestaties van het filter te kunnen meten.
7.1 Tools 7.1.1 Visual C++
Het implementeren van het filter is gedaan met Microsoft Visual C++ 6.0. Het filter maakt verder gebruik van 2 belangrijke SDK’s (Software Development Kits). Dit zijn de DirectX 9.0 SDK (zie 7.1.2) en de OpenCV SDK (zie 7.1.3). De klasse die het filter omvat is afgeleid van een DirectShow transformatie filter. Een dergelijk filter is vrij complex en tijdrovend om vanaf scratch op te bouwen. Daarom zijn er Wizards ontworpen die een skelet kunnen aanmaken waarin de creatie- en de communicatie taken met andere filters reeds geïmplementeerd zijn. De programmeur hoeft zich op deze manier alleen te richten op het transformatie algoritme – in dit project dus een tracking algoritme - zonder al te veel af te weten van de interne structuur van zo’n transformatie filter. De gebruikte wizard is de DirectShow ARGOS Filter Wizard [S3] die ik aangeleverd heb gekregen van Ton ten Kate12. Bovendien heeft hij in het filter een eenvoudig tracking algoritme geïmplementeerd op basis van de “kwadratische verschil” methode (zie paragraaf 5.1.1.1) die werkt op één kanaal van het RGB kleurmodel. Dit filter is als basis genomen voor dit project en daarmee had ik dan ook een uitstekend startpunt. 7.1.2 DirectX/DirectShow
De DirectX SDK bestaat uit een verzameling APIs (Application Program Interface) die er voor zorgen dat Microsoft Windows optimaal gebruik kan maken van de aanwezige multimedia hardware. Groot voordeel is dat deze APIs direct de hardware kunnen aanspreken zonder tussenkomst van het besturingssysteem. Hierdoor kunnen grote snelheidswinsten worden gehaald. DirectX is verder ingedeeld in bibliotheken met ieder een bepaalde functie. Één van deze bibliotheken is de DirectShow bibliotheek. Deze is speciaal gemaakt voor beeldverwerking in 2D en het maken van filters. DirectShow kent 3 soorten filters. Ten eerste zijn er bronfilters. Dit zijn filters die bijvoorbeeld een stream data van een videobestand of webcam kunnen doorgeven aan een volgend filter. Ten tweede zijn er transformatiefilters. Dit zijn filters die een bewerking doen op een binnenkomende stream en deze bewerkte stream dan vervolgens weer doorgeeft aan een volgend filter. Ten slotte zijn er renderfilters. Deze filters zorgen ervoor dat de gebruiker
12
Ton ten Kate is onderzoeker bij TPD/TNO met ervaring op gebied van video bewerking met DirectShow in combinatie met OpenCV. Hij is de bereiken op [email protected]
33
Tracking Filter voor het component Video Meten in Coach het transformatie resultaat kan zien. In paragraaf 9.1 wordt uitgelegd hoe deze verschillende filters aan elkaar geschakeld kunnen worden. 7.1.3 OpenCV bibliotheek
De OpenCV (Open Computer Vision) bibliotheek is speciaal door Intel gemaakt voor toepassingen in het veld van Computer Vision. Tot dit veld behoren bijvoorbeeld gezichtsherkenning, bewegingsherkenning, segmentatieproblemen en ook object tracking. OpenCV werkt met een eigen type van een afbeelding (iplimage). Nadat een beeldbestand geconverteerd is naar een iplimage kunnen er allerlei operaties worden uitgevoerd op deze afbeelding. Een voorbeeld is de functie cvMatchTemplate die als argumenten drie iplimages mee moet krijgen. Eén die het template bevat, één die een deel van de afbeelding bevat dat zich in het zoekvenster bevindt, en één waarin het resultaat wordt opgeslagen. Uiteraard maak ik in dit project gebruik van deze functie en ook talloze andere functies die veel werk uit handen nemen. OpenCV is daarom ook een onmisbaar pakket voor de Windows programmeur die zich bevindt op het terrein van Computer Vision. 7.1.4 Compileren
In deze paragraaf wordt bespreken hoe het door mij gemaakte filter te compileren is en hoe het filter vervolgens “geregistreerd” kan worden, zodat Windows het filter herkent. Alvorens het filter te compileren moeten bovendien een aantal handelingen binnen Visual C++ 6.0 uitgevoerd worden. Al de C++ source-code en Visual C++ projectfiles van het project zijn te downloaden van: http://gene.science.uva.nl/~msmids/afstuderen/
[S4]
Download en installeer zonodig eerst de benodigde SDK’s. • Download en installeer de DirectX SDK 9.0 of hoger [S1] • Download en installeer de OpenCV SDK beta 3.1 of hoger [S2] • Download de source [S4] van het tracking filter (.zip file) • Pak de source uit in een willekeurige directory Compileren: • Start Microsoft Visual C++ 6.0 of hoger en open de source van het tracking filter door ao_simpletrack_cv.dsp te openen. Ga in Visual C++ naar tools options en kies het tabblad directories. Voeg de include en library directories van de DirectX en OpenCV SDKs toe. Zie ook de afbeeldingen in figuur 12 en 13 op de volgende bladzijde. Het kan zijn dat directory namen afwijken wanneer de SDK’s niet in de standaard directories zijn geïnstalleerd. • Compileer door in het menu build rebuild all te kiezen. Het filter wordt nu gecompileerd en automatisch geregistreerd indien de gebruiker administrator rechten heeft. Alleen registeren • Om een gecompileerde DirectShow filter (extensie: ax of dll) te registreren, bijvoorbeeld op een ander systeem waar geen visual C++ aanwezig is, gaat u naar de directory waar het gecompileerde filter staat en voert u het volgende
34
Tracking Filter voor het component Video Meten in Coach commando in een dosbox uit: regsvr32 ao_simpletrack_cv.ax. Zorg er bovendien voor dat ook het bestand cv.dll in deze directory staat.
Figuur 12 – Include directories die horen bij de DirectX en OpenCV SDK’s (rode pijlen). Zorg dat deze goed ingesteld staan wanneer het filter gecompileerd moet worden.
Figuur 13 – Bibliotheek directories die horen bij de DirectX en OpenCV SDK’s (rode pijlen). Zorg dat deze ook goed ingesteld staan wanneer het filter gecompileerd moet worden.
In hoofdstuk 9 zal beschreven worden hoe het filter daadwerkelijk te gebruiken is met een programma als GraphEdit of met een andere externe applicatie. Dit filter werkt namelijk niet op zich zelf maar moet aaneengeschakeld worden met andere filters.
35
Tracking Filter voor het component Video Meten in Coach
7.2 Implementatie details In deze paragraaf komen een aantal zaken aan bod die in een DirectShow transformatie filter aanwezig zijn en wordt er uitgelegd wat deze onderdelen van een filter doen en welke functies daarvoor aangeroepen worden. Ten eerste valt het op dat de DirectShow functies een afwijkend return-type hebben, namelijk HRESULT. Wanneer een functie met succes is doorlopen zal deze een S_OK teruggeven. Wanneer een functie E_FAIL teruggeeft is er iets mis gegaan. Ook kunnen talloze andere meldingen worden teruggegeven, wat deze return-type flexibel maakt. Zo kan bijvoorbeeld VFW_S_NO_MORE_ITEMS teruggegeven worden wat er voor zorgt dat de betreffende functie niet meer uitgevoerd wordt. DirectShow filters hebben een hoge mate van objectgeoriënteerde structuur. Zo is het tracking filter onder andere “afgeleid” van een CTransformFilter klasse. Dit betekent dus dat mijn filter alle functies en variabelen overerft van deze klasse. Vervolgens hoeven alleen een aantal functies overschreven te worden, zodat het transformatiefilter daadwerkelijk iets gaat doen. De belangrijkste functie is daarbij de Transform functie. Deze functie wordt namelijk voor elk mediasample (wat vaak een frame van een video is) opnieuw aangeroepen. In deze functie moeten dus bewerkingen worden gedaan op het binnengekomen videoframe die zorgen voor de transformatie. In mijn geval is dat het tekenen van een zoekvenster, template en eventuele andere debug informatie op het videoframe. De gebruiker kan zo zien dat het filter daadwerkelijk het object volgt. Elk (transformatie) filter heeft ook een constructor en destructor in zijn klasse. Deze functies zijn goed te gebruiken om variabelen te initialiseren en geheugen toe te wijzen en weer vrij te geven. Dus ook deze functies zijn overschreven in mijn filter. De functienamen zijn Cao_simpletrack_cv en ~Cao_simpletrack_cv. Ook is er een functie Stop die aangeroepen wordt wanneer de gebruiker van het filter de gegevensstroom stopt. Deze functie is uiteraard goed te gebruiken om variabelen en tellers te resetten of gegevens weg te schrijven naar externe bestanden. Bij een transformatie filter hoort ook vaak een Property Page. Dit is een GUI waarin gebruikers van het filter allerlei parameters kunnen instellen die van belang zijn voor het transformatie algoritme (in mijn geval dus de tracking algoritmes). Hiervoor heb ik bij dit filter een apart source bestand (Cao_simpletrack_cv_prop.cpp) aangemaakt waar alle functies in staan die betrekking hebben op deze GUI. Belangrijke functies hierin zijn GetControlValues en SetControlValues. Deze twee functies zorgen ervoor dat de parameters die de gebruiker ingevoerd heeft, beschikbaar zijn voor het filter. De parameters worden door deze functies opgeslagen en gelezen uit een structure ao_simpletrack_cvParams welke gedefinieerd staat in het interface van het filter iao_simpletack_cv.h. Twee andere belangrijke functies die betrekking hebben op het Property Page zijn readConfig en saveConfig. Deze functies zorgen ervoor dat de parameters opgeslagen en gelezen kunnen worden in en uit het Windows Register. Bij het afsluiten van het filter blijven de instellingen dus bewaard op de huidige machine.
36
Tracking Filter voor het component Video Meten in Coach Tenslotte nog iets over pinnen. Een transformatie filter heeft input en output pinnen. Een standaard transformatie filter heeft één input en één output pin met een bepaald type (bijvoorbeeld videostream). Mijn filter heeft twee output pinnen nodig omdat ik ook de coördinaten van het te volgen object in elk frame wil doorgeven aan een volgend filter. Ik heb dus een nieuwe klasse moeten maken die ik heb afgeleid van een CTransformOutputPin klasse. Vervolgens heb ik de nodige functies overschreven om het type van de pin (TEXT) in te stellen. Filters kunnen met elkaar verbonden worden door middel van deze pinnen wanneer het type van de input pin van het ene filter en het type van de output pin van een ander filter gelijk zijn. In hoofdstuk 9 laat ik dit grafisch zien.
7.3 Testresultaten In de tabel in figuur 14 hieronder staan een aantal testresultaten van beide algoritmen. Het experiment betrof een template matching gebruik makende van de kwadratische verschil methode en zonodig is gebruik gemaakt van het algoritme die bestand is tegen occlusie. Dit is de uitbreiding op de kwadratische verschil methode waarbij de locatie van het zoekvenster wordt bepaald door een lineaire schatter (linear prediction). Kwadratische Verschil Methode
0% fout
<5% fout
Video 1 (softbal) Video 2 (basketbal) Video 3 (witte auto) Video 4 (turnster) Video 5 (speelsters)
Nee Nee Nee Ja Nee
Ja Ja Nee/Ja14 Ja Nee
Ideale grootte van het template 12x12 12x12 12x12 16x16 16x16
Ideale grootte van het zoekvenster 64x64 32x32 64x64 32x32 128x128
Ideaal aantal opgenomen frames 10 -13 15 -13 4015
Real-time
Ja Ja Ja Ja Nee
Figuur 14 – Testresultaten van de toepassing van de twee behandelde algoritmen in de testvideo’s. De “kwadratische verschil” methode wordt toegepast op alle drie RGB kanalen en zonodig wordt het zoekvenster geschat met een lineaire schatter wanneer occlusie plaatsvindt.
Bij het tracken van objecten in de testvideo’s zijn er drie van de vijf video’s waarvan het foutpercentage altijd lager ligt dan 5 procent. In video 4 leverden de testen helemaal een goed resultaat op, namelijk een foutpercentage van 0%. Dit komt vooral omdat de kleur van het te volgen object (broekje van een turnster) sterk verschilt met de kleur van de omgeving. Bovendien is het zo dat het broekje zwart van kleur is en daardoor minder last heeft van verkleuringen door meer of minder belichting. In de 3e en 4e kolom staan ideale groottes van het template en zoekvenster. Hiermee wordt de ideale grootte bedoeld waarbij het foutpercentage van een tracking proces zo laag mogelijk is. Wanneer het zoekvenster te groot wordt zal het zo zijn dat het proces 13
niet van toepassing omdat deze video totaal niet geschikt is voor de lineaire predictie methode. Het te volgen object verplaatst zich immers niet met een constante snelheid en hoek. 14 Wanneer de voorspelling optie ingeschakeld is (lineaire predictie) is de foutmarge wel < 15% 15 Deze video is alleen voor de lineaire predictie methode geschikt gedurende de tijd dat een speelster in beeld is en naar de bal toe rent wanneer de camera niet beweegt.
37
Tracking Filter voor het component Video Meten in Coach niet meer real-time verloopt op een gemiddelde desktop pc. Zo is het in video 5 niet mogelijk om real-time een speler te volgen omdat het zoekvenster te groot is. Wanneer een kleiner zoekvenster gekozen wordt is het foutpercentage te hoog. Er moet in dat geval dus een afweging worden gemaakt door de gebruiker van het filter. Wanneer de lineaire predictie wordt aan gezet bij het tracking proces in video 1 (softbal) is te zien dat het tracking proces goed gaat totdat de slagman de bal raakt. Het algoritme verwacht immers dat de bal zich met constante snelheid en hoek zal verplaatsen. Wanneer de bal plots de andere kant op schiet gaat het dus fout. Met het “ideaal aantal opgenomen frames” in de 4e kolom van figuur 14 wordt het aantal frames bedoeld waarvan informatie wordt verzameld (dx’en en dy’en). Deze gegevens worden dan als model gebruikt voor de voorspellingen van de locatie van het zoekvenster in de opvolgende frames. Dit aantal frames in de laatste kolom komt overigens overeen met de constante MAX_DISTANCES in het ontwerp (figuur 11). Op http://gene.science.uva.nl/~msmids/afstuderen/files staan een aantal filmpjes waarin het tracking proces zichtbaar wordt. Het template en zoekvenster worden over de video “heen geplakt” zodat de gebruiker meteen ziet of het object daadwerkelijk gevolgd wordt of niet. In figuur 15 hieronder staan voor de duidelijkheid de onderdelen benoemd.
Figuur 15 – De onderdelen die de gebruiker ziet wanneer het tracking proces plaatsvindt. De template geeft in elk frame de locatie aan waar, binnen het zoekgebied, de beste match plaatsvindt. De coördinaten linksboven in de hoek zijn de coördinaten van het midden van het groene kruis.
38
Tracking Filter voor het component Video Meten in Coach
8 De GUI voor de gebruiker DirectShow filters hebben vaak een eigenschappenvenster (ook wel “Property Page” genoemd). Dit is een paneel waarop de gebruiker van het filter allerlei parameters kan instellen die van belang zijn voor het resultaat dat het filter aflevert. Bij het tracking filter is een dergelijk paneel ook nodig om aan te geven welk tracking algoritme toegepast moet worden. In paragraaf 8.1 wordt de opbouw van het paneel besproken. Wanneer dit filter later geïntegreerd wordt in Coach zal de gebruiker dit venster niet meer te zien krijgen maar een interface die afgestemd is op de doelgroep. In paragraaf 8.2 wordt verteld welke details verborgen moeten blijven voor de gebruikers die deel uitmaken van de gegeven doelgroep (zie paragraaf 4.2).
8.1 De opbouw van het Eigenschappenvenster In figuur 16 hieronder staat een screenshot van het eigenschappenvenster.
Figuur 16 – Het eigenschappenvenster van het tracking filter
Aanvinken van de eerste checkbox “Show Debug info in Video Renderer” zorgt ervoor dat de gebruiker allerlei data die van belang is voor het debuggen te zien krijgt op de video. Deze gegevens worden dus op het uitkomende videoframes “geplakt”. Wanneer deze checkbox uitgevinkt wordt blijft alleen het zoekvenster en template (zie ook figuur 14) zichtbaar voor de gebruiker. Wanneer de tweede checkbox “Write Coordinates to file ‘crds.txt’” aangevinkt wordt, worden de coördinaten van het te volgen object in elk frame opgeslagen in het bestand
39
Tracking Filter voor het component Video Meten in Coach crds.txt.
Een externe applicatie kan deze coördinaten weer inlezen en verwerken. Zo kan er bijvoorbeeld een grafiek worden getekend uit deze verkregen meetgegevens. Vervolgens zijn er een aantal instellingen die te maken hebben met de manier van tracken. In de twee edit-boxen kan de grootte van zowel het template als het zoekvenster opgegeven worden. Deze grootte is in pixels en wanneer bijvoorbeeld een template van grootte 12 wordt gekozen, zal het template een totale grootte van 12x12 pixels hebben. Wanneer het zoekvenster groter wordt gekozen dan 64 werkt het filter in de meeste gevallen niet meer real-time zoals was te zien in de testresultaten in paragraaf 7.3. Het zelfde geldt voor het template: wanneer deze groter wordt gekozen dan 32 verloopt het tracking proces ook niet meer real-time. Dan zijn er nog een aantal keuzes: Ten eerste de checkbox “single [off] / all [on] RGB channels’. Wanneer deze aangevinkt wordt zal het matchen geschieden op al de 3 kanalen van het RGB-kleurenmodel. Vervolgens wordt het beste resultaat van deze drie (het laagste getal) gekozen. Wanneer bovendien de checkbox “Show Debug info in Video Renderer” aangevinkt staat zal de gebruiker een regel zien in de vorm: --r-- --g-- --b-x. Waarbij de r,g en b de resultaten zijn van matching, gebruik makend van de kwadratisch verschil methode. x geeft weer, welke van deze drie waarden het laagst is, en dus uiteindelijk gekozen wordt als beste match. Wanneer de checkbox “single [off] / all [on] RGB channels’ uitgevinkt wordt, zal slechts met behulp van één kanaal (het rode) van het RGB kleurenmodel worden gematched. Matchen met behulp van alle kanalen levert in het algemeen een beter resultaat op maar er moet wel drie keer zoveel gerekend worden. Echter is het extra rekenwerk nauwelijks te merken omdat de match functie in openCV (cvMatchTemplate) goed geoptimaliseerd is. Ten slotte is er nog een optie voor het inschakelen van het algoritme dat om kan gaan met (gedeeltelijke) occlusie. Door de checkbox “Predict Position of Search Window based on linear prediction” aan te vinken. In de bijbehorende edit-box kan worden opgegeven hoeveel frames gebruikt worden voor het opmaken van het model waarmee de locatie van het zoekvenster in volgende frames wordt geschat. Zie paragraaf 6.5.3 en 7.3 voor de werking van deze methode. Wanneer de checkbox “Show Debug info in Video Renderer” aangevinkt staat zal de gebruiker te zien krijgen wat de gemiddelde dx en dy is nadat het model is opgemaakt.
8.2 De didactische aspecten van het filter Wanneer dit filter later geïntegreerd wordt in het Coach pakket zal de grafische interface moeten worden afgestemd op de doelgroep. Het component Video Meten wordt namelijk op het voortgezet onderwijs veel gebruikt voor bewegingsanalyse. Een aantal punten waarop gelet moet worden bij het maken van deze interface zijn: •
Er moet eerst een korte uitleg gegeven worden over wat tracking precies is en hierbij moet uitgelegd worden hoe de “kwadratische verschil” methode globaal werkt.
40
Tracking Filter voor het component Video Meten in Coach •
•
•
De componenten die op de video verschijnen als resultaat (template en zoekgebied) moeten worden uitgelegd en de functie ervan moet worden besproken. Gevraagd kan bijvoorbeeld worden wat er gebeurt met het aantal rekenstappen wanneer het zoekgebied 2x zo groot wordt. Op deze manier kan worden getoetst of de leerlingen de “kwadratische verschil” methode snappen. Verberg de optie waar ingesteld kan worden hoeveel kanalen van het RGB kleuren model gebruikt worden om te matchen. De theorie achter deze optie heeft te weinig raakvlak met het onderwerp bewegingsanalyse en is daarom verder niet interessant. Wanneer het algoritme dat om kan gaan met occlusie gebruikt wordt, zal eerst uitgelegd moeten worden hoe dit algoritme werkt en aan de hand daarvan kan bijvoorbeeld worden gevraagd wat de beperkingen zijn van deze methode. Het in te stellen aantal frames dat gebruikt wordt voor het model (MAX_DISTANCES) kan het beste per filmpje vast gelegd worden in Coach zodat de leerlingen niet veel tijd kwijt zijn voor het kiezen van een ideaal aantal frames.
Coach kan na het tracking proces de doorgestuurde coördinaten van het te volgen object plotten in een grafiek met op de horizontale as framenummers (of beter nog: de tijd, het aantal frames per seconde en het aantal frames in de video zijn immers bekend) en op de verticale as de positie (x of y). De leerling kan hierna uit de grafiek andere eigenschappen afleiden van het gevolgde object. Zoals bij de testresultaten zichtbaar werd, kan het gebeuren dat in een aantal frames van de video de match verkeerd is verlopen en dus de verkeerde coördinaten doorgegeven worden. De leerling moet na het tracking proces dan ook de mogelijkheid hebben om handmatig de verkeerde metingen bij te stellen door de punten in de gemaakte grafiek te verslepen. Door gebruik te maken van het tracking filter is het bovendien zo dat de meetgegevens nauwkeuriger zijn dan op de huidige manier. Nu is het zo dat de leerlingen in elk frame moeten aanklikken waar het object zich bevind. Omdat de meeste video’s uit heel wat frames bestaan wordt er vaak maar een selectie gemaakt van de frames waarin de leerling moet klikken. Hierdoor ontbreken dus delen van de meetgegevens en zal het resultaat minder nauwkeurig zijn. Bovendien zullen veel leerlingen het fijn vinden dat al het “klikwerk” nu niet meer nodig is. Er hoeft slechts 1x geklikt te worden om het tracking proces te starten. Aan het einde van het proces hoeft de leerling alleen maar te kijken of er foute metingen zijn en deze zonodig te corrigeren.
41
Tracking Filter voor het component Video Meten in Coach
42
Tracking Filter voor het component Video Meten in Coach
9 De Demonstratieapplicaties Nadat het tracking filter gecompileerd is kan het gebruikt worden door het filter te schakelen in een keten van filters. Het filter werkt namelijk niet op zichzelf. Één manier om het filter te gebruiken is door een filter graph te bouwen in het programma GraphEdit.. Dit programma wordt geleverd bij de DirectX SDK. Een filter graph is een keten van geschakelde filters. In 9.1 wordt uitgelegd hoe GraphEdit te gebruiken is. In paragraaf 9.2 wordt besproken hoe de meetgegevens (coördinaten) visualiseerbaar gemaakt kunnen worden in een grafiek.
9.1 Gebruik van het filter in GraphEdit Wanneer we het gemaakte tracking filter invoegen in een lege filter graph [Graph insert Coach”] zien we
filters ”DirectShow
filters” ”Tracking
filter
for
een grafische representatie van het filter. In figuur 17 hieronder is te zien dat er drie pinnen aanwezig zijn. De pin aan de linkerkant van het filter is de inputpin en de twee rechter pinnen zijn output pinnen.
Figuur 17 – Grafische representatie van het tracking Figuur 18 – Grafische representatie van filter. een bronbestand, in dit geval een videobestand genaamd 1.avi
Het filter verwacht een stream van video als input. Deze gegevensstroom kan afkomstig zijn van een bronfilter, zoals een video bestand (.avi) of bijvoorbeeld een webcam. Wanneer we een avi bestand kiezen als bronfilter voegen we deze ook toe. [Graph insert filters ”DirectShow filters” ”File Source (Asynch)”] Na het kiezen van het bronbestand is het filter in figuur 18 toegevoegd aan het filter graph. Door nu de output pin van het filter in figuur 18 te verbinden met de Video In pin van het filter in figuur 17 worden de twee filters aan elkaar gekoppeld als de types van de twee pinnen overeenkomen. In figuur 19 is te zien wat GraphEdit doet wanneer de twee filters gekoppeld worden. GraphEdit voegt zelf de noodzakelijke filters toe die er voor zorgen dat de gegevensstroom compatibel wordt.
Figuur 19 – Wanneer de twee filters in figuur 16 en 17 gekoppeld worden zorgt GraphEdit ervoor dat de gegevensstroom in het juiste formaat het tracking filter binnen komt
43
Tracking Filter voor het component Video Meten in Coach Nu kan de outputpin Video Out van het tracking filter verbonden worden met een video renderer. Een dergelijk filter zorgt er voor dat het resultaat van het transformatiefilter (hier dus het tracking filter) zichtbaar wordt voor de gebruiker. We voegen dus nu een video renderer tot aan het filter graph. [Graph insert filters ”DirectShow filters” ”Video Renderer”’]We verbinden vervolgens de outputpin Video Out van het tracking filter met de inputpin van het Video Renderer. De filter graph is nu compleet. In figuur 20 staat deze ketening van filters weergegeven.
Figuur 20 – Het tracking filter is nu opgenomen in een filter graph en is klaar voor gebruik. Om het eigenschappenvenster te openen van het tracking filter (figuur 15) klikt te gebruiker met rechts op het filter en kiest dan “filter properties”. Na de gewenste opties te hebben ingesteld drukt de gebruiker op de Play knop in GraphEdit en de video verschijnt in een venster. Door nu in deze verschenen videovenster te klikken op een object wat gevolgd moet worden, begint het tracking proces. Zoals in figuur 19 en 20 te zien is, heeft het tracking filter ook nog een tweede outputpin. De bedoeling is dat hierdoor de coördinaten van het te volgen object in elk frame van de video gaan stromen. Aangezien deze optie nog niet volledig is geïmplementeerd wegens problemen met DirectShow werkt deze pin niet. Wanneer deze pin ergens op wordt aangesloten zal GraphEdit de verbinding niet accepteren. Om de coördinaten toch extern op te slaan moet de optie “write coordinates to file” worden ingeschakeld in het eigenschappenvenster.
9.2 Het verwerken van de Meetgegevens De coördinaten die opgeslagen zijn in een bestand willen we uiteraard visualiseerbaar maken. Door de coördinaten te plotten in een grafiek kunnen we een goed beeld krijgen van de beweging van het gevolgde object. Om de coördinaten te plotten in een grafiek heb ik in JAVA een programma gemaakt [S6] die de coördinaten inleest en vervolgens een grafiek laat zien van de meetgegevens. In figuur 20 op de volgende bladzijde is een screenshot van dit programma te zien. De grafiek hoort bij het tracking proces van de turnster (video 3). In de bovenste grafiek staan op de horizontale as de framenummers uitgezet en op de verticale as de X-posities van het gevolgde object. In de onderste grafiek staat op de verticale as de Y-posities uitgezet. Bij deze springende beweging van de turnster is vooral de onderste grafiek van belang omdat de springbeweging hoofdzakelijk verticaal verloopt. Wanneer we weten met hoeveel frames per seconde de video is opgenomen kunnen we de y-as ook zien als tijd as. Omdat we dan de afstand uitgezet hebben tegen de tijd
44
Tracking Filter voor het component Video Meten in Coach kunnen we allerlei andere informatie uit de grafiek halen zoals snelheid, versnelling en de periode. In figuur 21 is ook te zien dat er minstens één meetgegeven fout is. Het 5e coördinaat heeft een hogere X- en Y-waarde dan zou moeten. Dit is te zien doordat er in de grafiek een “hak” te zien is rond het 5e framenummer. Opmerking: Coach heeft al een goed ingebouwd grafiekencomponent maar omdat het tracking filter nog niet geïntegreerd kan worden in coach16, is dit een tijdelijke oplossing om toch de meetgegevens visualiseerbaar te maken.
Figuur 21 – De grafieken die ontstaan wanneer de coördinaten worden ingelezen uit het coördinaatbestand (video 3: turnster). De bovenste grafiek representeert de horizontale beweging en de onderste grafiek representeert de verticale beweging van het gevolgde object.
16
Het integreren van DirectShow filters in Coach is nog in ontwikkeling.
45
Tracking Filter voor het component Video Meten in Coach
46
Tracking Filter voor het component Video Meten in Coach
10 Conclusie Terugkijkend op de gestelde eisen waaraan het tracking filter moest voldoen is op te merken dat aan de meeste eisen voldaan is. De twee methodes die het tracking filter gebruikt, werken beide real-time op een gemiddelde desktop-pc. Het is gebleken dat een tracking filter die gebruik maakt van DirectShow en de OpenCV bibliotheek zeer efficiënt omgaat met de hardware van de computer. Ook gaat het tracking proces goed wanneer objecten tijdelijk niet zichtbaar zijn (door occlusie) zolang het object met constante snelheid en hoek verplaatst. Uit de testresultaten is ook te zien dat het tracking proces in alle testvideo’s een foutpercentage van < 5% heeft, zoals vastgesteld stond in de eisen. Ook kunnen er andere bronnen aangesloten worden aan het filter. Zo is het ook mogelijk real-time te tracken met een webcam als bron. Ook dit was een opgestelde eis. Ook de eis van het aantal keren klikken is ruimschoots gehaald. De gebruiker hoeft voor het initialiseren van het tracking proces slechts eenmalig te klikken op het te volgen object. De coördinaten worden geëxporteerd naar een bestand en er kan dus na het proces met de meetgegevens gewerkt worden door de gegevens bijvoorbeeld te plotten in een grafiek. Toch is er aan één eis niet voldaan. De geproduceerde meetgegevens (coördinaten) kunnen nu zoals gezegd pas na het tracking proces worden benaderd en niet tijdens het proces zelf. Het was de bedoeling de meetgegevens mee te laten “stromen” door een outputpin, maar de implementatie van deze pin is niet volledig gelukt wegens moeilijkheden met DirectShow. Een andere beperking van het filter is dat wanneer objecten die door occlusie tijdelijk niet zichtbaar zijn, zich niet met constante snelheid en hoek voortbewegen , de schatting niet correct is omdat een lineaire schatter gebruikt wordt. De nog niet volledige geïmplementeerde tweede output pin en de beperkte functie van de lineaire schatter zijn punten van aandacht voor een volgende deelnemer aan dit project, die moet voortbouwen op wat tot nu toe geproduceerd is.
47
Tracking Filter voor het component Video Meten in Coach
48
Tracking Filter voor het component Video Meten in Coach
11 Referenties [A1] H.T. Nguyen, A. W.M. Smeulders. Tracking aspects of the foreground against the background. In Proc. of the European. Conf. on Computer Vision, ECCV'04, Praha, 2004. [A2] H.T. Nguyen, M. Worring, R. van den Boomgaard. Watersnakes: energy-driven watershed segmentation. IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 25, No. 3, pp. 330-342, 2003.
[A6] Daniel P. Huttenlocher, Gregory A. Klanderman, and William J. Rucklidge Comparing Images Using the Hausdorff Distance (1993) IEEE Transactions on PAMI, 15(9), September 1993 [A7] David Vignon, Brian C. Lovell, Robert J. Andrews General Purpose Real-Time Object Tracking Using Hausdorff Transforms (2002) In Proc. of the IPMU2002, pages 1-6, Annency, France.
[A3] H.T. Nguyen, M. Worring, R. van den Boomgaard and A. W.M. Smeulders. Tracking non-parameterized object contours in video. IEEE Trans. on Image Processing, Vol. 11, No.9, pp. 1081-1091, 2002. [A4] H.T. Nguyen, and A. W.M. Smeulders. Template tracking using color invariant pixel features. In Proc. of the Inter. Conf. on Image Processing, ICIP'02, Vol 1, pp. 569 - 573, Rochester, 2002. [A5] H.T. Nguyen, M. Worring and R. van den Boomgaard. Occlusion robust adaptive template tracking. In Proc. of the IEEE Inter. Conf. on Computer Vision, ICCV'01,Vol.1, Vancouver, 2001.
49
[A8] D.M. Gavrila Multi-feature Hierarchical Template Matching Using Distance Transforms (1998) In Proc. IEEE International Conference on Pattern Recognition, Brisbane, Australia [A9] Michael Suleder, Dieter Heuer Automatische Videoanalyse + software (2002) In Didaktik der Physik, Fruhjahrstagung Leipzig 2002 [A10] Walter Bell, Dan Huttenlocher Model Based Tracking in Quasi real-time (1998) [not published] [A11] LIU Ya, AI Haizhou, XU Guangyou Moving Object Detection and Tracking Based on Background Substraction (2001) In Proceedings of SPIE Vol. #4554 [455411], October 2001
Tracking Filter voor het component Video Meten in Coach
[A12] Steven Mills, Tony Pridmore and Mark Hills Tracking in a Hough Space with the Extended Kalman Filter (2003) In Proceedings of the International Conference on Pattern Recognition (ICPR2004), August 2004
[A14] Dorin Comaniciu and Visvanathan Ramesh Mean Shift and Optimal Prediction for efficient object tracking IEEE Int. Conf. Image Processing (ICIP'00), Vancouver, Canada, Vol. 3, 7073, 2000
[A13] Renaud Seguier, Annick Le Glaunec, Bernard Loriferne Human Faces Detection and Tracking in Video Sequence (1995) Ecole Superieure d'Electricite, Electronic Department, Rennes, France
[B1] Programming Microsoft DirectShow for Digital Video and Television Mark D. Pesce, paperback, Bk&CD edition, Published April 2003, 448 pages, ISBN 0735618216 [B2] Managed DirectX 9 Kick Start: Graphics and Game Programming Tom Miller Sams, Paperback, Bk&CD edition, Published October 2003, 411 pages, ISBN 0672325969
[S1] DirectX Software Developer Kit 9.0 – Microsoft – Published: December 19. 2002 Downloaden: http://www.microsoft.com/downloads/details .aspx?FamilyId=124552FF-8363-47FD8F3B-36C226E04C85&displaylang=en [S2] OpenCV Software Developer Kit beta 3.1 – Intel – Published: February 26. 2003 Downloaden: http://prdownloads.sourceforge.net/opencvli brary/OpenCV_b3.1.exe?download [S3] DirectShow ARGOS Filter Wizard – TNO/TPD – Website: http://www.tpd.tno.nl/smartsite828.html [S4] Alle relevante documenten, source code, en andere bestanden behorende bij dit project zijn te vinden op: http://gene.science.uva.nl/~msmids/afstudere n/
50
Tracking Filter voor het component Video Meten in Coach
– Appendix A – Voorbeelden Wiskundige Methoden A.1 Hausdorff afstand bepalen Hieronder een voorbeeld waarbij de Hausdorff afstand wordt bepaald tussen 2 verzamelingen punten: {a1,a2} en {b1,b2,b3}. Op de volgende bladzijde staat de toelichting.
(a)
(b)
(c)
(d)
51
Tracking Filter voor het component Video Meten in Coach
(e)
(f)
(g)
(h)
Toelichting: In (a) zijn 2 verzamelingen punten A en B gegeven. Eerst bepalen we de afstand tussen a1 en alle punten in B (b), Vervolgens bewaren we de kortste afstand van de bepaalde afstanden (c). We herhalen hetzelfde voor het tweede punt in A (d)(e). Van de twee verkregen kortste afstanden, weergegeven in (f), kiezen we de langste. In dit geval is dat a1-b1. Dit is de Hausdorff afstand h(A,B) weergegeven in (g). Figuur (h) maakt duidelijk dat elk punt in A ten hoogste d(a1,b1) heeft tot een punt in B.
52
Tracking Filter voor het component Video Meten in Coach
A.2 Rechte lijnen vinden via een Hough Transformatie In dit voorbeeld zal ik uitleggen hoe rechte lijnen y = ax + b in een afbeelding herkend kunnen worden met een Hough transformatie. We kunnen een rechte lijn ook als geparametriseerde versie schrijven, p = x cos + y sin , waar p de loodrechte afstand is van de oorsprong tot de lijn en waar de hoek is tussen de x-as en de vector p. Dit staat hier onder in de linker figuur weergegeven.
Als we dit betrekken op beeld analyse en de coördinaten van de rand segmenten (xi, yi) veronderstellen we bekend, dan worden deze xi en yi dus als constanten gebruikt in de vergelijking p = x cos + y sin . De p en zijn de onbekende variabelen waar we naar op zoek zijn. Wanneer we een plot , en we doen dit voor alle (xi, yi), dan maken van alle mogelijke waarden van p en krijgen we de sinusoiden zoals hierboven in de rechter figuur is afgebeeld. Dit is nu dus in de (p, ) ruimte. Het is te zien dat de drie sinusoiden elkaar snijden in een gemeenschappelijk punt (p, ). Nu is het zo dat alle punten (x,y) in de linker figuur die op een rechte lijn liggen (onder andere dus de punten 1, 2 en 3) transformeren in de (p, ) ruimte naar sinusoiden die elkaar in een gemeenschappelijk punt snijden. Voor elke map (x,y) (p, ) houden we een histogram bij, in de (p, ) ruimte, zodat de staven van het histogram het hoogst zijn, daar waar twee of meer sinusoiden elkaar snijden. Elk zo’n snijpunt representeert een rechte lijn in de (x,y) ruimte. In de drie figuren op de volgende bladzijde geef ik nog een voorbeeld ter verduidelijking:
53
Tracking Filter voor het component Video Meten in Coach
(a)
(b)
(c)
Toelichting: In figuur17 (a) zijn de randen bepaald met een edge detector, in (b) is de Hough transformatie toegepast en is er een histogram opgemaakt. De gele punten representeren de lijnen in de (x,y) ruimte (hoogste staven in het histogram). In (c) worden vervolgens de gevonden lijnen geplot in de originele figuur. De rechte lijnen worden dus goed herkend, bovendien is te zien dat de Hough transformatie “een gat in een lijn” zoals bovenin figuur a, goed aankan.
Uit de gevonden lijnen kan de locatie van het te volgen object worden afgeleid omdat we eenvoudig de coördinaten van het gevonden gebied, ingesloten door de gevonden lijnen, kunnen vinden.
17
Bron foto’s: Ghassan Hamarneh, http://www.cs.toronto.edu/~ghassan/phd/illus/linehough/
54