Hand detectie op beelden afkomstig van een mobiele eye-tracker

FACULTEIT INDUSTRIELE INGENIEURSWETENSCHAPPEN CAMPUS DE NAYER

Hand detectie op beelden afkomstig van een mobiele eye-tracker

¨ DEN DOOVEN Raphael

Promotor:

Stijn De Beugher

ˆ Co-promotoren: Geert Brone

Masterproef ingediend tot het behalen van de graad van master of Science in de ¨ wetenschappen: Elektronica-ICT industriele Afstudeerrichting informatie- en communicatietechnieken

Academiejaar 2013 - 2014

c Copyright KU Leuven

Zonder voorafgaande schriftelijke toestemming van zowel de promotor(en) als de auteur(s) is over¨ nemen, kopieren, gebruiken of realiseren van deze uitgave of gedeelten ervan verboden. Voor aanvragen tot of informatie i.v.m. het overnemen en/of gebruik en/of realisatie van gedeelten uit deze publicatie, wendt u tot KU Leuven campus De Nayer, Jan De Nayerlaan 5, B-2860 SintKatelijne-Waver, +32-15-316944 of via e-mail [email protected]. Voorafgaande schriftelijke toestemming van de promotor(en) is eveneens vereist voor het aanwenden van de in deze masterproef beschreven (originele) methoden, producten, schakelingen en programma’s voor industrieel of commercieel nut en voor de inzending van deze publicatie ter deelname aan wetenschappelijke prijzen of wedstrijden.

Dankwoord Het voorbije jaar dat ik heb mogen werken aan deze thesis en van alles heb mogen bijleren, heb ik te danken aan verschillende mensen. Eerst en vooral aan mijn familie die mij de kans heeft gegeven om verder te mogen studeren. Dit is niet iets wat iedereen kan zeggen. Vervolgens alle docenten van De Nayer. Zij hebben mij begeleid tot en met nu, door mij nieuwe informatie aan te bieden. De onderzoeksgroep EAVISE die de thesis mogelijk heeft gemaakt. Een speciale dank aan Stijn De Beugher, mijn interne promotor. Hij heeft mij doorheen het jaar zeer goed beleid, het was een aanˆ gename samenwerking. Ook Geert Brone (externe promotor) en Bert Oben van onderzoeksgroep MIDI. Zij maakten de thesis samen met EAVISE mogelijk. Als laatste dank aan Carmen Van Maercke, mijn vriendin. Zij heeft voor literaire en mentale steun gezorgd in dit voorbije jaar.

v

Abstract Het doel van deze masterthesis was het ontwerpen van een algoritme om handen detecteren in beelden afkomstig van een mobiele eye-tracker. Manuele annotatie wordt hier door overbodig. Na het verwerken van deze beelden zou de data toegankelijk gemaakt moeten worden voor verdere verwerking door andere toepassingen. Het ontworpen algoritme werkt op een sequentie van beelden en maakt hier gebruik van om de resultaten te verbeteren. Het algoritme gaat in een detectie vlak, gegenereerd door een bovenlichaamsdetector, zoeken naar handen door middel van drie detectoren. Elke detector gebruikt een andere methode om handen te detecteren. Dit zorgt voor een goede betrouwbaarheid dat elk hand gedetecteerd is. we gebruiken een hand, een pols en een arm detector om handen te vinden. De laatste wordt gebruikt om handen te detecteren in motion-blur. Het evalueren van deze data verhoogt de betrouwbaarheid hier van. De evaluatie wordt gedaan op basis van de grootte, aantal huid pixels en de locatie van de detecties. In deze data wordt nadien gezocht naar een links en een rechts hand op basis van de geschatte waarde door een Kalman filter. Die op basis van de vorige locaties een voorspelling maakt. Dit zorgt voor een stabiele detectie van een linkse en rechtse handen. Trefwoorden: thesis, handdetectie, mobiele eye-tracker, video beelden

vii

Abstract The goal of this master thesis was to develop an algorithm that detects hands in images coming from a mobile eye-tracker. After the images are processed, the data most be retrievable. This creates the possibility to use the data afterwards in an other application. Consequently is manual annotation becoming invalid. The algorithm is designed to work on a sequence of images. This makes that the algorithm can take advantage of this feature to increase the correctness of the results. The algorithm search in a detection area (generated by an upper-body detector) for hands, using three different detectors. This makes the probability higher that no hands are missed. They use a hand, wrist and an arm detector to find hands. The first two are sensitive for motion-blur, that’s why the third detector is used. Through evaluating the detectors generated data based on side, skin pixels and location, it’s easier to find the left and the right hand. To find the location of the left and the right hand is assisted by a Kalman filter. A Kalman filters tries to find a new predicted location based on the previous locations. This makes for a stable estimations of right and left hands. Trefwoorden: thesis, hand detection, mobile eye-tracker, video images

ix

Short summary Goal The goal of this thesis was to create an algorithm for detecting hands in the images coming from a mobile eye-tracker. The results of the detector must be accessible for further processing in other applications, for example to investigate the relation between the viewing behavior and the hand movement of a person in a conversation.

Research A mobile eye-tracker is a device that detects the location the user is looking at. This is done by mounting two small cameras on a kind of spectacles. One camera looks at the eye and the other to the world. By tracking the location of the iris and with some calibration, the eye-tracker can calculate the location the user is looking at on the images taken by the world camera. For detecting hands, a few methodes have already been in existence. All based on a different detection technique. There are ones that use human pose estimators, so that afterwards they can guess the location based on the arm position. They are good for lower resolution images, but the hand detections are not very accurate. Other ones use hand model based detectors, specifically searching for hands in images. Mostly is even the rotation of the hand retrievable. It’s more computing intensive, but it is more accurate and gives more information about the hand.

Implementation Figure 1 shows an overview of the algorithm presented in the thesis. The first step in the algorithm is designed to find a human. This is done by using a upper-body detector. Then the results of this detection become the search area for the following detectors. The search area is stretched to a bigger area to overcome missing hand detections on, for example stretched arms. Next hand detectors will search for hands in this area. There are three different independent hand detectros used. The first two use DPM models of a hand and the wrist for the detecting of hand. Because the models are trained with hands all in one direction, however a person could hold his hand in any direction. Therefore must the detection area be rotated over 360 degrees. In further steps a face information is necessary. Therefore is a face detection used and made available for all steps. xi

xii

The third detector is based on a totally different concept. This one uses the arm to predict hands. It tries to search the arms by segmenting the skin of the image. On this segmentations a skeletonization is used to find the center line of a blob. To find useful lines on this skeletonized image a Hough line detector is used. The decision for a valid arm is based on the ratio between the size of the line and the size of the head, if an arm was detected, we add a fictive hand detection to each end of the line. In the other case when the hand is smaller the line is considered as one hand. The next step will decide if a detection is a true or a false positive. There are two eliminators that filters the false positives. They eliminate false detections based on the size of the detection and the percentage of the skin pixels present in a detection. Subsequently the remaining detections will be clustered together based on their size and mutual distance. To avoid false hand detections in the face, their score is lowered if they occur in the face region. The last step in this section is going to find the right and the left hand. This one is based on the prediction the next step is going to make. Based on that prediction, this step is trying to find the closest detected hand for each side. If there is no prediction (because for example the application was just started) this step searches for the hand with the highest score on the corresponding side of the left and the right hand. The last step of the algorithm tries to track the hands in time. This is realized by tracking the hands based on the relative position towards the head. This makes the localization of the hands more stable and consequently easier to track.

Figuur 1: Working diagram for the detection of hand in images coming from a mobile eye-tracker.

conclusion The algorithm is capable of detecting left and right hands in the images captured by a mobile eyetracker. This information is then properly stored in a good readable data format. Blur still keeps detecting hands difficult. But overall the algorithm is robust for shaking and nodding of the head of the wearer of the glasses.

Inhoudsopgave 1 Doelstellingen

3

2 Literatuurstudie

5

2.1 Eye-tracker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.1.1 Wat is een eye-tracker . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.1.2 Algoritmes eye-tracker . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.2.1

Zichtbaar spectrum t.o.v. Infrarood spectrum: . . . . . . . . . . . .

7

2.1.2.2

Feature-based t.o.v. Model-based:

. . . . . . . . . . . . . . . . .

8

2.1.2.3

¨ ` ¨ Coordinaten iris omzetten naar scene coordinaten: . . . . . . . . .

8

2.1.2.4

Besluit: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.2 Hand detectie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.2.1 Hand model gebaseerde detectie 2.2.1.1

9

Haar filter gebaseerde detectie . . . . . . . . . . . . . . . . . . . . 10

2.2.1.1.1 2.2.1.2

. . . . . . . . . . . . . . . . . . . . . . .

Toepassing

. . . . . . . . . . . . . . . . . . . . . . . . . 11

Histograms of Oriented Gradients gebaseerde detectie . . . . . . . 11

2.2.1.2.1

Deformable Parts Models . . . . . . . . . . . . . . . . . . 12

2.2.1.2.2

Toepassing

. . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2.2 Pose estimation gebaseerde detectie: . . . . . . . . . . . . . . . . . . . . . 14 2.2.3 3D gebaseerde algoritmes:

. . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.4 Fast Fourier Linear Detector . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2.4.1

Patchwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2.4.2

profiteren van het cache geheugen . . . . . . . . . . . . . . . . . . 16

2.2.4.3

resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Uitwerking

21

3.1 Bovenlichaam detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.1.1 Implementatie van bovenlichaamsdetector . . . . . . . . . . . . . . . . . . . 22 3.2 Gezichtsdetectie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.1 Implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 Hand detecties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.3.1 Hand en context detector implementatie . . . . . . . . . . . . . . . . . . . . 24 xiii

xiv

INHOUDSOPGAVE

3.3.2 Hand-aan-arm implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3.2.1

Huid segmentatie . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.3.2.2

Skeletteren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.3.2.3

Arm detectie

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.4 Hoogste waarschijnlijkheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.4.1 Eliminaties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4.2.1

Find-union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.4.2.2

Samenvoeging resultaten . . . . . . . . . . . . . . . . . . . . . . . 31

3.4.3 Verlagen van hansdetecties in het gezicht . . . . . . . . . . . . . . . . . . . 32 3.4.4 Vinden van het linkse en het rechtse hand . . . . . . . . . . . . . . . . . . . 33 3.5 Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.5.1 Kalman filter

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.5.2 Tracking van hoofd en handen . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.6 Data opslag . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.6.1 Structuur opbouw . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4 Conclusie

39

4.1 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

Lijst van figuren 1

Working diagram for the detection of hand in images coming from a mobile eye-tracker. xii

2.1 (a) remote eye-tracker en (b) mobile eye-tracker

. . . . . . . . . . . . . . . . . . .

6

2.2 Ilya Repin, An Unexpected Visitor, 1884 + eye-track data . . . . . . . . . . . . . . .

6

2.3 (a) Bright-pupil methode, (b) Dark-pupil methode en (c) Anatomie van het menselijk oog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4 Kalibratie van mobile eye-tracker met 9 kalibratie punten . . . . . . . . . . . . . . .

8

2.5 (a) cascade classifier en (b) haar-like feature + uitbreiding Lienhart and Maydt (2002) 10 2.6 (a) Toont aan hoe dat de summed area table berekent wordt en (b) geeft weer hoe dat er een deel van een feature berekent wordt met behulp van intergral image . . . 10 2.7 Hand detection system architecture, Nyan Bo Bo . . . . . . . . . . . . . . . . . . . 11 2.8 Visuele voorstelling van berekening Histogram oriented gradient van een bin

. . . . 12

2.9 Werking diagram van het algemeen DPM algoritme . . . . . . . . . . . . . . . . . . 12 2.10 Histograms of Oriented Gradients modellen van handen. Op de twee links afbeeldingen zijn de rug en de palm modellen te zien. De rechtse afbeelding toont het profiel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.11 (a) Originele afbeelding (b) Hand en context detectie (c) skin en hypothese detector (d) Superpixel segmentatie (e) uiteindelijk resultaat . . . . . . . . . . . . . . . . . . 14 2.12 (a) Buffy stickmen voorbeeld (b) Distributie data . . . . . . . . . . . . . . . . . . . . 14 2.13 (a) normale vlakke afbeelding en (b) is een dept map van (a) . . . . . . . . . . . . . 15 2.14 Fourier Transformatie ten opzichte van convolutie . . . . . . . . . . . . . . . . . . . 16 2.15 (a) conventionele image pyramid met model, (b) Image pyramid in het Fourier domein met model en (c) Patchwork . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.16 Strategie om cache beter te benutten. R = te verwerken patchworks, L = aantal filters en K = aantal features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 ¨ meting tijd ten opzichte van fractie grootte . . . . . . . . . . . . . . . . . . . 18 2.17 Reele 3.1 Werkingsdiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 (a) functie illustratie partition() en (b) illustratie functie groupRectangles() . . . . . . . 22 3.3 De rode kaders tonen de boundig box aan in beide afbeeldingen. De bovenste boundig box is verkregen van uit de bovenlichaamsdetector. Deze wordt vergroot in verschillende richtingen. Dit zorgt er voor dat de handen zeker aanwezig zijn in de bounding box. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 xv

xvi

LIJST VAN FIGUREN

3.4 Deze figuur toont aan dat een arm van hand tot schouder groter is dan 3,5 keer het hoofd. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.5 Op deze figuur is een hand detectie te zien (blauwe kader) en een context detectie (rode kader) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.6 De drie root modellen met van links naar rechts de palm, rug en profiel van een hand. 25 3.7 De afbeelding toont aan hoe een frame er uit ziet dat 360 graden gedraaid wordt met stappen van elke keer 10 graden ten opzichte van de vorige rotatie. De rotatie wordt telkens gedaan met de originele afbeelding om verlies aan data te vermijden. . . . . 26 3.8 De bovenste rij symboliseert een afbeelding zonder toevoeging van zwarte band en de tweede rij met zwarte band. In de eerst kolom is de originele afbeelding te zien, gevolgd door een afbeelding die 90 graden gedraaid is. De laatste kolom toont aan welke delen zeker zijn verwerkt en de rode cirkels tonen aan dat door geen zwarte band toe te voegen informatie verloren kan gaan. . . . . . . . . . . . . . . . . . . . 26 3.9 Omzetting van een detectie naar de juiste geroteerde detectie . . . . . . . . . . . . 27 3.10 (a) Toont de distributie van huidskleur met Saturation en Value ten opzichte van Hue en (b) toont de distributie van Cr ten opzichte van Cb . . . . . . . . . . . . . . . . . 28 3.11 (a) toont een gesegmenteerd beeld op basis van huid pixels. Wanneer deze wordt wordt verwerkt door de skelet bewerking bekomt men (b) . . . . . . . . . . . . . . . 29 3.12 Deze figuur illustreert de twee mogelijkheden van de armdetectie. Rechts bovenaan is een arm gedetecteerd en links onderaan is er een hand gedetecteerd op basis van de lijnlengte. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.13 Werking diagamma van de klasse Hoogste waarschijnlijkheid . . . . . . . . . . . . . 30 3.14 Illustratie van de menselijke maten van een hand ten opzichte van het gezicht . . . . 30 3.15 Deze figuur illustreert een lijst van data. De bovenste rij toont de niet verwerkte data, elk resultaat heeft dus een eigen groep. Volgende rij toont de gegroepeerde lijst (union functie), deze bestaat uit drie onafhankelijke. Dit wordt nog eens getoond in de laatste rij door middel van een lijst van de verzameling indicatoren. . . . . . . . . 31 ¨ som gemaakt. . 32 3.16 Links zijn alle hoeken hoeken te zien, rechts daarvan is de vectoriele 3.17 Op deze figuur zijn er enkele handen gedetecteerd op het gezicht. . . . . . . . . . . 32 ´ binnen het gezichtsveld ligt en met 3.18 De figuur illustreert twee detecties waarvan e´ en gevolg de score zou verlaagd worden. De andere detectie ligt ver genoeg buiten de het gezicht, zelfs met de marge (oranje boord) ronde het gezicht. . . . . . . . . . . . 33 3.19 Voorbeeld van hoe een Kalman resultaat er kan uitzien. . . . . . . . . . . . . . . . . 34 ´ dimensionale Kalman filter door middel van 3.20 Een voorbeeld opstelling voor een e´ en een wagon op een recht spoor spoor, Bron: Faragher, 2012 . . . . . . . . . . . . . 35 3.21 Gaussische distributies van zowel de gemeten (blauw), voorspelde (rood) en de gecombineerde (groen), Bron: Faragher, 2012 . . . . . . . . . . . . . . . . . . . . . 36 3.22 (a) toont het pad dat de tracking moet verwerken indien de hoek van het verwerkte frame genomen wordt als referentie. Dit zorgt voor een combinatie van het pad dat het hoofd doet en het pad dat de handen doen. Terwijl wanneer we het hoofd als referentie nemen (te zien op (b)), dan ontstaat er een veel simpeler pad. Dit geeft als gevolg dat de padden van de handen voorspelbaarder worden. . . . . . . . . . . 36

Lijst van symbolen DPM deformable part model. Dit is een detectie methode die zich baseert op een model bestaande uit kleinere modellen.. 9, 22 FFLD fast Fourier linear detector. Dit is een DPM detector die de detecties uitvoert in het Fourier domein.. 9, 22 HOG Histogram of oriented gradients. Een soort detectie model.. 9 HSV Hue Saturation Value. Een kleurruimte bestaande uit de drie parameters kleur (Hue), saturatie van de kleur (Saturation) en de intensiteit (Value.). 27 POI Point of intrest.. 6 RANSAC RANdom SAmple Consensus. Dit is een methode dat die een verband in datasets gaat zoeken. 8 RGB Red Green Blue. Een kleurruimte bestaande uit de drie parameters rood, groen en blauw.. 27 XML Extensible Markup Language. Een specifiek bestandsformaat met een specifieke opmaak leesbaar voor zowel mens als machine.. 22, 36 YCbCr Luma Chroma blue Chroma red. Een kleurruimte bestaande uit de drie parameters Luminatie, chromatisch blue en chromatisch rood. 27 YUV Zelfde als YCrCb maar een andere benaming.. 27

xvii

Inleiding In deze thesis wordt een algoritme voorgesteld met de bedoeling om handen te detecteren op beelden afkomstig van een mobiele eye-tracker. Deze scriptie gaat als eerste de doelstellingen van deze thesis bespreken. Vooraleer het mogelijk was om te starten aan het ontwikkelen van het effectieve algoritme moest er over het onderwerp een studie gemaakt worden. Deze studie wordt besproken in het volgende hoofdstuk na de bespreking van de doelstellingen. Hierin zal er meer achtergrond gegeven worden over alles rond een eye-tracker en welke algoritmes er al bestaan voor het detecteren van handen. Het volgende hoofdstuk gaat dieper ingaan op het ontwikkeld algoritme. Hier worden de verschillende stappen besproken waardoor het algoritme gaat om van een sequentie van afbeeldingen een lijst te maken van gedetecteerde handen. Als laatste hoofdstuk wordt er een conclusie gemaakt, hier worden de resultaten vergeleken met de vooropgestelde doelstellingen en de eventuele verbetering die er nog mogelijk zijn.

1

Hoofdstuk 1

Doelstellingen Het doel van deze masterproef is het toepassen van een algoritme om handen en handgebaren te detecteren in beelden afkomstig van een mobiele eye-tracker. De eerste doelstelling bestaat uit het onderzoeken van reeds bestaande algoritmes voor het detecteren van handen en handgebaren. Vervolgens zal het reeds geschikte algoritme toegepast worden op de beelden afkomstig van de mobiele eye-tracker. Het resultaat van de masterproef is een algoritme dat handen kan detecteren in beelden afkomstig van een mobiele eye-tracker ten opzichte van de persoon zijn/haar gezicht. De resultaten moeten ook nadien nog beschikbaar blijven om verder te kunnen verwerken, om bijvoorbeeld nadien deze data te gebruiken samen met de data eye-tracking.

3

Hoofdstuk 2

Literatuurstudie De literatuurstudie wordt volgens de onderzoeksvragen ingedeeld. In elk van deze onderverdelingen zal de onderzoeksvraag beantwoord worden met behulp van voorafgaande gerelateerde informatie. Onderzoeksvragen:

• Welke algoritmes worden er gebruikt voor eye-tracking? • Welke algoritmes bestaan er om handen te detecteren in beelden? In hoofdstuk 2.1 bespreken we wat een eye-tracker is en welke methodes er worden gebruikt om ogen te volgen. Dit wordt gevolgd door hoofdstuk 2.2, waar er wordt besproken welke algemene methodes er kunnen worden gebruikt voor het detecteren van handen. Dit wordt opgedeeld in drie secties, het eerste is handdetectie op basis van een model van een hand, vervolgt door pose estimation detectie en als laatste wordt er snel 3D benaderingen besproken.

2.1

Eye-tracker

Wat is een eye-tracker, waar worden ze voor gebruikt en wat zijn de meest gebruikte methodes voor eye-tracking? Deze informatie is nuttig als achtergrondinformatie voor de thesis, door een beter inzicht te geven op de problematiek en de mogelijkheden dat een eye-tracker het systeem biedt.

2.1.1

Wat is een eye-tracker

Een eye-tracker is een apparaat dat de oogpositie en de oogbeweging meet, de data hiervan wordt dan op zijn beurt gebruikt om te bepalen naar waar de persoon in kwestie aan het kijken is. Om te weten naar waar de persoon aan het kijken is, heeft men een tweede beeld nodig. Dit onderscheidt de twee soorten systemen. Het eerste systeem genoemd remote eye-trackers (zie figuur 2.1a) wordt op een vaste positie bevestigd. Deze eye-trackers maken geen contact met de persoon en dus ondervinden zij hier geen last van. Dit systeem wordt voornamelijk gebruikt bij eye-tracking op computerschermen. 5

6

2 Literatuurstudie

Bij het andere systeem, ook wel een mobiele eye-tracker genoemd, wordt de eye-tracker volledig geplaatst op het hoofd van een persoon (zie figuur 2.1b). Dit wordt verwezenlijkt door de eye-tracker op een hoofddeksel of een brillenmontuur te bevestigen.

(a)

(b)

Figuur 2.1: (a) remote eye-tracker en (b) mobile eye-tracker

Beide systemen hebben allebei andere doeleinden. Het eerste systeem wordt exclusief gebruikt bij het analyseren van computer data, zoals bijvoorbeeld:

• Analyseren van hotspots op websites. • Interessante punten op foto’s (zie figuur 2.2) • Controles voor gaming doeleinde

Figuur 2.2: Ilya Repin, An Unexpected Visitor, 1884 + eye-track data

Een mobiele eye-tracker kan door zijn mobiliteit meer in het dagelijkse leven gebruikt worden om POI’s (points-of-interest) te lokaliseren. Dit apparaat kan bijvoorbeeld gebruikt worden om te zien waar de mensen naar kijken in een museum en naar waar zij het langst focussen en dus belangrijk vinden aan een tentoonstelling. In het algemeen wordt een eye-tracker gebruikt om het kijkgedrag van een persoon in een omgeving te analyseren en aan de hand van deze gegevens een conclusie te vormen.

2.1.2

Algoritmes eye-tracker

In dit deel bespreken we de verschillende blokken waaruit een algoritme kan bestaan, om van twee beelden (scene en oog) de point-of-gaze te kunnen berekenen. Dit gebeurt op chronologische

2 Literatuurstudie

7

wijze en begint met de manier waarop het oog kan worden opgenomen.

2.1.2.1

Zichtbaar spectrum t.o.v. Infrarood spectrum:

De manier waar op men de beelden opneemt van het oog kan op twee methodes. De eerste manier maakt gebruik van het zichtbare licht. Op deze beelden kan men goed de verschillende onderdelen van het oog zien (zie figuur 2.3c), maar heeft last van veranderlijk omgevingslicht en reflecties op het oog. Om dit deels tegen te gaan, gaat men de beelden opnemen in het infrarood spectrum eye-com research (2013). Dit wordt verwezenlijkt door een infrarood bron dicht bij het oog te plaatsen. Omdat men in het infrarood spectrum werkt, moet de camera ook in dit spectrum werken.

(a)

(b)

(c) Figuur 2.3: (a) Bright-pupil methode, (b) Dark-pupil methode en (c) Anatomie van het menselijk oog

De positie van de infraroodbron heeft een groot effect op de opgenomen beelden. Als de bron dicht bij de camera staat zal hij de infrarood reflectie op de retina waarnemen, dit noemt men bright-pupil (zelfde effect als rode ogen in foto’s). De bright-pupil methode zal dus een lichte pupil geven (figuur 2.3a). Dit geeft een groot contrast tussen de iris en de pupil. Omdat de pupil licht is, zullen de wimpers, die soms delen van het oog kunnen bedekken, geen valse positieven geven(dit komt omdat de wimpers zelf donker kleuren op de beelden). De hoeveelheid reflectie die de pupil doorlaat, is afhankelijk van de grootte van de pupil. Deze grootte is afhankelijk van verschillende factoren, een grootte factor is licht. Het gevolg hiervan is dat men deze methode moeilijk kan gebruiken in omgevingen met veel licht. Wanneer men de infrarood bron verder van de camera plaatst en de reflectie van het infrarood licht op de retina niet meer kan worden waargenomen door de camera, zal de pupil donker kleuren, dit noemt men de dark-pupil methode. Omdat de pupil altijd donker gekleurd is, werkt deze methode wel goed in verlichte ruimtes. Ook zullen donkere irissen lichter kleuren en als gevolg ontstaat er een groot contrast tussen de pupil en de iris. Deze methode kan wel last hebben van valse positieven door middel van wimpers die voor het oog komen te zitten. Over het algemeen worden de meeste algoritmes gebaseerd op de dark-pupil methode. Dit omdat deze de meest robuuste is van de beide methodes.

8

2 Literatuurstudie

2.1.2.2 Feature-based t.o.v. Model-based: De volgende grote stappen, die de meeste algoritmes volgen, kunnen opgedeeld worden in twee grote groepen. De eerste groep is feature-based detectie, deze groep gaat features detecteren en lokaliseren door middel van de positie op een afbeelding (of eventueel samen met een andere afbeelding). Dit houdt vaak in dat deze features afhankelijk zijn van intensiteit en intensiteit variantie op een afbeelding. Veel gebruikte methodes zijn bijvoorbeeld: thresholding, edge-detection enzovoort. De andere groep, Model-based detecties, gaat een model proberen te fitten op een afbeelding. Bijvoorbeeld een cirkel of een ellips bij iris detectie. Dit geeft een nauwkeuriger resultaat ten opzichte van de meeste feature-based detecties, maar deze oplossingsmethodes zijn vaak zeer complex met gevolg dat model-based algoritme in moet boeten op tijd en flexibiliteit. In de detectie van de positie van een iris kunnen deze twee groepen ook wel gecombineerd worden. Dit gebeurt in Li et al. (2005), hier gaat men eerst de ongewenste reflectie op de corneal verwijderen. Daarna worden vanuit de vorige locatie van de iris uit het vorige frame, een paar radialen getrokken. Op deze radialen wordt een edge-detection uitgevoerd. Afhankelijk van de score zal de locatie verschoven worden. De laatste stap zal met behulp van RANSAC (RANdom SAmple Consensus) de valse edges proberen te elimineren met behulp van een ellips model. Na deze stap is de positie van de iris gevonden door het midden te nemen van de ellips. Door de twee groepen te combineren wordt er een combinatie gemaakt tussen snelheid en nauwkeurigheid.

2.1.2.3

¨ ` ¨ Coordinaten iris omzetten naar scene coordinaten:

¨ ` coordinaten ¨ Om van oog coordinaten naar naar scene te gaan heeft men een verband nodig tussen deze twee. Dit verband wordt bepaald door de kalibratie procedure. Dit duurt gemiddeld 30 tot 60 ` seconde. Het kalibreren bestaat uit het vinden van een verband tussen de pupil en de scene. Het verband tussen deze twee is een 3x3 matrix H. Deze matrix wordt bepaald door homographic mapping toe te passen. Het bereken van H wordt bepaalt door verschillende bekende kalibratie punten, meestal 6 a` 9 punten. Door ononderbroken in correcte volgorde op de punten te focussen kan men het verband vinden en dus de matrix H berekenen.

Figuur 2.4: Kalibratie van mobile eye-tracker met 9 kalibratie punten

De positie van deze kalibratie punten heeft een invloed op de correctheid van het uiteindelijk resultaat. Hier mee wordt bedoeld dat als het berekende resultaat dichter bij een kalibratie punt ligt het resultaat nauwkeuriger is dan wanneer deze verder ligt van een kalibratie punt. Dit is niet de enigste beperking die deze punten hebben, ook moeten deze punten in de field-of-view liggen van de gebruiker bij het kalibreren Locarna (2009). Na de kalibratie kan via de matrix H de locatie van het oog (~e) omgezet worden naar een locatie op

2 Literatuurstudie

9

` de scene (~s). De omzetting wordt berekend door de formule 2.1.

~s = H~e

(2.1)

¨ De twee vectoren ~e en ~s bevatten beiden x en y coordinaten van hun positie en een constante 1.

2.1.2.4

~s = (xs , ys , 1)

(2.2)

~e = (xe , ye , 1)

(2.3)

Besluit:

De meeste algoritmes gebruiken de dark-pupil methode omdat deze betrouwbaarder is in dagdagelijkse omgevingen, zoals bijvoorbeeld in winkels en museums. Om een evenwicht te houden tussen een snel maar toch nauwkeurig systeem gaat men vaak een combinatie maken van zowel feature-based (snelheid) en model-based (nauwkeurige) methodes.

2.2

Hand detectie

Het detecteren van een hand in afbeeldingen kan op verschillende manieren aangepakt worden. Volgende paragrafen gaan verschillende bestaande methodes verduidelijken, per methode worden de pro’s en contra’s besproken om latere beslissingen te verantwoorden. Uit het onderzoek is gebleken dat men twee benaderingen kan onderscheiden om handen te detecteren in lage resolutie beelden. De eerste benadering gaat proberen een model te trainen van een hand, door middel van dat model wordt er in de afbeelding gezocht naar overeenkomsten. Hoe hoger de overeenkomst hoe waarschijnlijker het is dat er een hand is gevonden. In de andere benadering gaat men er vanuit dat elke persoon een hand heeft aan de uiteinden van de armen. Met deze veronderstelling gaat men modellen trainen op lichaamsdelen zoals bovenen onderarmen, schouders enzovoort. Deze methodes worden pose estimation genoemd. Als voorlaatste paragraaf worden 3D algoritmes in het algemeen besproken. Hier wordt niet al te diep op ingegaan om dat mobile eye-trackers over het algemeen niet zijn uitgerust met 3D camera’s (zien hoofdstuk 2.1) en dus 3D algoritmes niet toepasbaar zijn. Als laatste wordt de detector besproken die gebruikt wordt in de uitwerking, genaamd FFLD (= Fast Fourier Linear Detector ). Dit is een DPM detector zoals gebruikt in het voorstel van Arpit Mittal and Torr (2011). Het voordeel aan de FFLD detector is dat deze sneller werkt dan een klassieken DPM detectoren.

2.2.1

Hand model gebaseerde detectie

Deze detectie methode baseert zich op een model van een hand. Afhankelijk van de methode wordt het model anders beschreven. In volgende paragrafen zullen respectievelijk zowel de Haar filters benadering (van Viola and Jones (2001)) besproken worden als de HOG (Histograms of Oriented Gradients, Dalal and Triggs (2005)) benadering. Dit zijn de twee meest bekende methodes om op voorhand getrainde modellen te gebruiken voor detecties in beelden. Per methode wordt er telkens een hand gerelateerde toepassing besproken.

10

2 Literatuurstudie

2.2.1.1

Haar filter gebaseerde detectie

De meest bekende methode is de methode gebaseerd op Viola en Jones Viola and Jones (2001) Haar filter detector. Deze methode gaat de afbeelding op verschillende schalen schalen, dit noemt men sub-windows. Voor elke sub-window wordt er een berekening gemaakt met behulp van een cascade classifier. De cascade classiefier (zie figuur 2.5a) is opgebouwd uit verschillende stappen, elke stap gaat proberen te beslissen of de sub-window een deel van het gewenste model bevat, ook wel classificatie genoemd. De classificatie gebeurt met behulp van haar-like features, te zien op figuur 2.5b. Merk op dat deze altijd bestaan uit een lichte en een donkere rechthoek. Deze rechthoeken zijn zones waar men een score gaat in berekenen op een model afhankelijke positie ¨ in de sub-window. Indien de score niet gunstig is wordt de sub-window geelimineerd, anders wordt de volgende classifier toegepast.

(a)

(b)

Figuur 2.5: (a) cascade classifier en (b) haar-like feature + uitbreiding Lienhart and Maydt (2002)

Om de features snel te kunnen berekenen wordt de methode intergral image gebruikt. Als men deze methode gebruikt moet men per feature regio maar maximaal 3 integer berekeningen maken. Om voor te zorgen dat men maar maximaal drie berekeningen moeten uitgevoerd worden gaat men eerst een summed area table opmaken. Men gaat voor elke pixel positie de totale oppervlakte bereken tot deze pixel locatie. Een voorbeeld is te zien op figuur 2.6a.

(a)

(b)

Figuur 2.6: (a) Toont aan hoe dat de summed area table berekent wordt en (b) geeft weer hoe dat er een deel van een feature berekent wordt met behulp van intergral image

Met deze tabel kan men dan nadien zeer gemakkelijk meervoudige totale oppervlakte bereken met maar vier waarden. Dit wordt gedaan met de formule 2.4.

S = 1−2−3+4

(2.4)

2 Literatuurstudie

11

S = 3 − 8 − 7 + 22 = 10

(2.5)

2.2.1.1.1 Toepassing In het voorstel van Bo et al. (2007) wordt deze methode gebruikt als eerste stap. Om valse positieven te proberen te elimineren, wordt er gebruik gemaakt van andere features van handen (zie overzicht op figuur 2.7).

Figuur 2.7: Hand detection system architecture, Nyan Bo Bo

Om te elimineren wordt de cascade classifier gevolgd door een skin-detector. De skin-detector gaat de sub-window omzetten naar een binaire afbeelding die correspondeert met skin/nonskin. Uit de binaire afbeelding worden er verschillende features berekend. De features worden altijd berekend ten opzichte van de grootst verbonden skin component. Deze features zijn als volgt:

• Oppervlakte • Omtrek • Excentriciteit • Aantal pixels die raken met de zijden van de binaire afbeelding De Mahalonobis-afstand Mahalanobis (1936) berekent de correlaties tussen verschillende variabelen en vergelijkt deze met een bekende set variabelen. In dit geval is de bekende data die van een hand. Omdat de kans klein is dat deze afstanden exact overeenkomen wordt er een tolerantie op toegepast in de vorm van een threshold. Omdat deze methode een cascade classifier gebruikt, is dit een zeer snelle detector. Dit moet wel inboeten in het leer proces van het gewenste model, aangezien dit kan soms meerdere dagen kan duren, afhankelijk van hoe groot de dataset is en de infrastructuur van de computer. 2.2.1.2

Histograms of Oriented Gradients gebaseerde detectie

Deze methode gebruik zoals in de vorige paragraaf een classifier, die enkel bestaat de features ¨ ¨ uit bins. Deze bins bevatten een histogram van de orientatie van de gradienten. Hiermee wordt bedoelt dat voor elke pixel in de bin het verloop wordt berekend. Ook wordt er voor elk verloop de richting van dit verloop berekend. Als men deze allemaal te samen neemt, krijgen we een histogram van richtingen vandaar de naam Histograms of Oriented Gradients, dit is te zien op figuur 2.8. Een aantal van deze bins vormen een model, een voorbeeld van zo een model is te zien op figuur 2.10. Deze methode is zo goed als direct implementeerbaar met vorige methode van de vorige paragraaf, maar men kan door gebruik te maken van DPM (Deformable Parts Model) de detector robuuster maken. Deze methode gebruikt verschillende HOG modellen om te detecteren.

12

2 Literatuurstudie

Figuur 2.8: Visuele voorstelling van berekening Histogram oriented gradient van een bin

2.2.1.2.1 Deformable Parts Models Deze methode van Felzenszwalb et al. (2010) gebruikt verschillende HOG modellen. In het algemeen bestaan deze modellen uit een algemeen zwak model root model en sterkere onderdeel modellen. Het root model gaat algemeen zoeken naar een object en ten opzichte van dit model worden de onderdelen gedetecteerd. Deze strengere onderdelen worden relatief van het root model gebruikt. Op figuur 2.9 rechts bovenaan is te zien hoe een model er kan uitzien en hoe dat de kleine striktere onderdelen worden verdeeld over het root ¨ model. Men kan ook op deze afbeelding zien hoe ver deze striktere onderdelen mogen varieren ten opzichte van hun ideale locatie. Zoals verder te zien is op figuur 2.9 worden alle resultaten samen genomen, dit resultaat geeft een identificatie waar er eventueel gewenste objecten kunnen zitten in een afbeelding.

Figuur 2.9: Werking diagram van het algemeen DPM algoritme

2 Literatuurstudie

13

2.2.1.2.2 Toepassing Deze methode wordt gebruikt in Arpit Mittal and Torr (2011) maar met hand modellen. Op figuur 2.10 zijn de drie modellen te zien, deze HOG modellen tonen drie aanzichten van een hand (de rug, palm en het profiel). Bij handen moet men rekening houden ¨ met verschillende orientaties, dit lost Arpit Mittal and Torr (2011) men op door bij het trainen van ¨ de hand modellen, alle handen in dezelfde richting te orienteren. Dit zorgt voor duidelijkere en betrouwbaardere modellen. Door de afbeelding te roteren met een vast interval kan men zo handen detecteren onder verschillende hoeken. Net zoals in de vorige paragraaf gebruikt Arpit Mittal and Torr (2011) extra stappen om valse positieven te elimineren. Figuur 2.11 toont een overzicht van de verschillende technieken die in Arpit Mittal and Torr (2011) gebruikt worden om valse positieven te verminderen. Deze methode bestaat uit twee stappen waar van de eerste stap bestaat uit drie verschillende detectoren.

• Hand detector • Context detector • Skin detector

Figuur 2.10: Histograms of Oriented Gradients modellen van handen. Op de twee links afbeeldingen zijn de rug en de palm modellen te zien. De rechtse afbeelding toont het profiel.

De eerste detector, namelijk de hand detector is al besproken. De context detector gaat naar het omliggende gebied kijken. Dit gebeurt door een tweede DPM te trainen maar met een grotere omgeving rond het hand. Deze DPM detector zal dus een score geven op basis van de omgeving van de al gevonden handen. De laatste detector, de Skin detector gaat de huid proberen te segmenteren afhankelijk van het gezicht van de persoon. Als het gezicht van de persoon niet gevonden is wordt deze stap overgeslagen. Met deze data gaat men een edge detection uit voeren. De methode waarop deze edge detector werkt noemt de canny operatie. Deze Canny operatie gaat gebruik maken van twee niveaus. Als de waarde boven het eerste niveau is wordt deze geclassificeerd als huid. Door het tweede (lagere) niveau te gebruiken wordt er een hysterisch gegenereerd. Deze hysterisch zorgt er voor dat de edge detector stabieler wordt en dus minder foute randen genereert. Na deze stap wordt er nog een bootstrapping uitgevoerd. Deze gaat meerdere malen kijken naar de naburige pixels om de waarschijnlijkheid te verhogen van de huid segmentatie. Nadat de huid gesegmenteerd is, gaat men proberen armen te detecteren die aan handen hangen. Dit wordt verwezenlijkt door een Hough transformatie uit te voeren op de huid segmentatie. Omdat deze enkel de zijkant van de armen detecteert, gaat men de mediaan axis zoeken. De score wordt bepaald door hoe goed een mediaanlijn samenvalt en kruist met een al gevonden bounding box van een hand. Uit deze drie voorgaande detectoren worden drie scores berekend. Deze scores worden verwerkt door een hypothese classificator. Deze classificator gaat met behulp van een SVM valse positieven proberen te elimineren.

14

2 Literatuurstudie

(a)

(b)

(c)

(d)

(e)

Figuur 2.11: (a) Originele afbeelding (b) Hand en context detectie (c) skin en hypothese detector (d) Superpixel segmentatie (e) uiteindelijk resultaat

2.2.2

Pose estimation gebaseerde detectie:

Vorige paragrafen spraken van methoden om via een handmodel een hand te detecteren. Een andere manier is meer gebaseerd op een menselijkere aanpak vooral wanneer men handen probeert te lokaliseren van op een afstand. Het idee is dat men eerst de bouw van de persoon probeert te onderscheiden, specifiek van het bovenlichaam. Deze informatie is makkelijker te detecteren van op een grotere afstand (dit correspondeert met een lagere resolutie) ten opzichte van direct handen te proberen te detecteren. Methode Eichner et al. (2012) ook bekend als Buffy Stickmen methode stelt een methode voor om in stilstaande beelden poses van personen te detecteren.

(a)

(b)

Figuur 2.12: (a) Buffy stickmen voorbeeld (b) Distributie data

Deze methode gaat proberen een bovenlichaam in te delen in zes stukken. Het hoofd, torso en linker/rechter boven- en onderarm kunnen ten opzichte van elkaar maar een aantal verschillende posities aannemen. Deze distributie van lichaamsdelen wordt gevisualiseerd op figuur 2.12b. Om tijd en rekenwerk te besparen wordt er eerst met behulp van een zwak bovenlichaam model gezocht doorheen een afbeelding. Uit deze resultaten kan men al een ruwe schatting maken van de positie van het hoofd en de torso. Om schaal factoren te elimineren bij het fitten van lichaamsdelen gaat men elk gedetecteerd bovenlichaam op een vaste schaal schalen. Vanaf dit punt gaat men strengere modellen gebruiken om de verschillende onderdelen te zoeken. Een bijkomende manier om valse positieven te verminderen is de achtergrond proberen weg te filteren, dit elimineert achtergrond ruis. Dit wordt verwezenlijkt door het GrabCut Rother et al. (2004) algoritme en omdat men een goed idee heeft van waar de verschillende ledematen kunnen zitten werkt dit GrabCut algoritme zeer goed.

2.2.3

3D gebaseerde algoritmes:

Een 3D beeld bekomen met een 3D camera, bestaat algemeen uit twee afbeeldingen. De eerste is vaak een gewone foto (figuur 2.13a) en de tweede bestaat uit een diepte map (ook wel depth-map genoemd, Muller et al. (2011)). Op deze afbeelding wordt de diepte afgebeeld in de vorm van een ¨

2 Literatuurstudie

15

¨ gradient. Hoe intenser de waarde van de pixel hoe dieper (of dichter) het object ligt ten opzichte van de camera.

(a)

(b)

Figuur 2.13: (a) normale vlakke afbeelding en (b) is een dept map van (a)

In deze beelden zijn bijvoorbeeld mensen gemakkelijker te vinden omdat deze vaak een groot contrast geven ten opzichte van de achtergrond en dus geen last hebben van zelfde (of dicht bij liggende) kleuren of grijswaarden. Op deze manier is het dus ook gemakkelijker om bijvoorbeeld handen te detecteren via een model of pose-estimation algoritmes Suryanarayan et al. (2010). Aangezien de thesis zich spitst op mobiele eye-trackers, werken we niet met deze methodes. Dit ` camera gebruiken om de scene ` omdat mobiele eye-trackers vaak alleen maar e` en te bekijken (zie hoofdstuk 2.1).

2.2.4

Fast Fourier Linear Detector

Deze detector haalt zijn hogere snelheid door twee innovatieve veranderingen te gebruiken. De eerste en grootste verandering gebruikt in plaats van een convolutie een vermenigvuldiging. Alvorens de vermenigvuldiging uitgevoerd kan worden, moeten de beelden en de modellen eerst getransformeerd worden naar het Fourier domein. Op figuur 2.14 is het verschil te zien tussen deze twee methodes. De vermenigvuldiging zorgt wel voor geheugen overconsumptie en gebrek aan geheugenbandbreedte. Het geheugen overconsumptie komt door dat men zowel van de afbeelding en het model een image pyramid moet maken (zie figuur 2.15a), de oplossing is patchwork. Gebrek aan geheugen bandbreedte is te wijten aan het feit dat de volledige afbeeldingen en de modellen vaak te groot zijn voor het cache.

2.2.4.1

Patchwork

Door een filter te maken (met daar in het model) die voor elke schaal dezelfde afmetingen heeft, krijgt men het effect dat de geschaalde afbeeldingen toch de zelfde grootte moeten hebben ten opzichte van de filter. Dit effect is te zien op figuur 2.15b. Dit geeft de mogelijkheid om meerdere geschaalde afbeeldingen op een iteratie beeld te plaatsen. Door dat er minder dus meerdere afbeeldingen op een iteratie worden gezet, zijn er dus per detectie minder iteraties nodig (te zien op figuur 2.15c). Omdat de detector per iteratie telkens dezelfde filter gebruikt en minder iteraties doet is het geheugengebruik verminderd.

16

2 Literatuurstudie

Figuur 2.14: Fourier Transformatie ten opzichte van convolutie

(a)

(b)

(c)

Figuur 2.15: (a) conventionele image pyramid met model, (b) Image pyramid in het Fourier domein met model en (c) Patchwork

2.2.4.2

profiteren van het cache geheugen

Als men gewoon weg de punt vermenigvuldiging zouden uitvoeren zal de limiet van het geheugen snel bereikt zijn (na¨ıeve implementatie). In vergelijking 2.6 is te zien dat de tijd afhankelijk is van de verschillende groten van de filters, patchwork enzovoort, als men de na¨ıeve methode gebruikt. Dit resulteert vaak in een tekort aan cache geheugen en ook aan een zeer lange uitvoer tijd.

2 Literatuurstudie

17

Variabelen

R is het totaal aantal te verwerken patchworks L is het totaal aantal filters K zijn het aantal features M × N is de grootte van het patchwork u(F) is de tijd nodig om 2 vlaktes te vermenigvuldigen met grootte F v(F) is de tijd nodig om een vlakte van grootte F te lezen/schrijven F fractie van het geheugen dat wordt gebruikt (Zie figuur 2.16)

Tnaive = KLR2v(MN) + KLRu(MN) + LRv(MN) | {z } | {z } | {z } lezen

vermenigvuldiging

(2.6)

schri jven

Door de verschillende vlakte op te delen in fracties gaan men het cache geheugen niet overbelasten ¨ en efficienter gebruiken. Het resultaat is te zien in de vergelijking 2.7 en 2.8, deze methode wordt de fast methode genoemd. Dit wordt ge¨ıllustreerd op figuur 2.16.



 T f ast =

MN F |{z}

  K(L + R)v(F) + KLRu(F) + LRv(F) | {z } | {z } | {z }

aantal verdelingen

lezen

vermenigvuldiging

= K(L + R)v(MN) + KLRu(MN) + LRv(MN)

(2.7)

schri jven

(2.8)

Als men deze twee methoden vergelijken met behulp van vergelijking 2.9 en 2.10 is te zien dat inderdaad de snelle methode beter is.

(2 + K1 ) + u(MN) Tnaive v(MN) = L+R 1 T f ast ( LR + K ) + u(MN) v(MN) ≈2

v(MN) +1 u(MN)

(2.9)

(2.10)

In theorie zou het zijn dat hoe kleiner de fractie hoe sneller, in praktijk ligt dit anders. Op figuur 2.17 is te zien dat wanneer F te klein wordt die resulteert in een lichte verhoging van uitvoer tijden.

18

2 Literatuurstudie

Figuur 2.16: Strategie om cache beter te benutten. R = te verwerken patchworks, L = aantal filters en K = aantal features

¨ meting tijd ten opzichte van fractie grootte Figuur 2.17: Reele

2 Literatuurstudie

2.2.4.3

19

resultaten

Deze twee versnellingsmethode resulteren in gemiddelde snelheidsverhoging van 7.5. In onderstaande grafiek zijn de tijden van verschillende modellen te zien ten opzichte van de DPM detector voc-release 4 (V4).

V4 (ms) Ours (ms) Speedup (x)

aero 409 55 7.4

bike 437 56 7.8

bird 403 53 7.6

boat 414 56 7.4

bottle 366 57 6.4

bus 439 56 7.9

car 352 54 6.5

cat 432 56 7.7

chair 417 56 7.5

cow 429 57 7.5

table 450 57 8.0

Volgende tabel toon de betrouwbaarheid aan van de 2 verschillende detecties. Deze tweed verschilt licht van elkaar.

V4 (%) Ours (%)

aero 28.9 29.4

bike 59.5 58.9

bird 10.0 10.0

boat 15.2 13.4

bottle 25.5 25.3

bus 49.6 50.6

car 57.9 57.6

cat 19.3 18.9

chair 22.4 22.6

cow 25.2 24.9

table 23.3 24.4

Men kan hier uit concluderen dat de betrouwbaarheidsverschillen verwaarloosbaar zijn en dat de detector veel voordelen heeft op gebied van detectie tijd.

Hoofdstuk 3

Uitwerking

Figuur 3.1: Werkingsdiagram

In dit hoofdstuk wordt een algoritme voorgesteld om handen te detecteren op een sequentie van beelden. Op figuur 3.1 is het overzicht te zien van de ontworpen methode. Tevens is dit ook de basis indeling van dit hoofdstuk. Het hoofdstuk zal dus de methode zo bespreken zoals het programma een frame verwerkt. Te beginnen met de detectie van het bovenlichaam. Van deze detectie wordt een uitsnijding gemaakt. Op deze uitsnijding gaat er een gezichtsdetectie uitgevoerd worden. De informatie van het gezicht zal in latere stappen gebruikt worden om bepaalde beslissingen te nemen in verband met eliminatie van foutieve detecties. Ook zorgt de kleinere uitsnijding voor een korte uitvoering tijd bij de handdetectie in de volgende stap. Deze stap gaat handen proberen te detecteren op 3 verschillende onafhankelijke manieren. Elk van die 3 stappen geven dus drie reeksen detecties en scores per detecties. De hand en context detectoren werkt op basis van een hand model. Het eerste model is getraind op alleen handen en de tweede is getraind op basis van handen en hun omgeving. Detector drie werkt op een volledig ander systeem, namelijk het gegeven dat elke arm een hand heeft. Vervolgens worden deze detecties en hun score verwerkt. Het verwerken gebeurt door middel van het elimineren van onjuiste detecties, samen voegen van overlappende detecties en rekening houden met de voorspelde positie. Om detecties in het volgende frame te voorspellen worden de gevonden detecties door een Kalman filter gehaald. Dit filter gaat proberen een voorspelling te doen afhankelijk van de detectie zijn gedrag in het verleden. Het resultaat geeft een indicatie 21

22

3 Uitwerking

van waar de handen in het volgende frame eventueel kunnen zijn. Deze voorspelling wordt dan teruggegeven aan de vorige stap. Omdat deze data nadien nog toegankelijk moet blijven wordt deze opgeslagen in een XML bestand. Dit zorgt voor een leesbaar formaat voor zowel een persoon als

3.1

Bovenlichaam detector

De bovenlichaam detector zorgt voor een kleiner zoekoppervlak voor de handdetectors. Doordat de zoek oppervlakte kleiner is, zal de detectie tijd drastisch dalen. Omdat het model gebaseerd is op een DPM en om toch een relatief snelle detectie te realiseren wordt er gebruikt gemaakt van de FFLD. De FFLD is een detector gebaseerd op de paper van Dubout and Fleuret (2012).

3.1.1

Implementatie van bovenlichaamsdetector

Op elk ingelezen frame wordt er een boven lichaam detectie uitgevoerd. Dit heeft als gevolg dat het zoekgebied voor de volgende stappen kleiner wordt. Omdat de FFLD detector niet altijd 1 bounding box per persoon geeft moeten de overlappende detectie samengevoegd worden. Het samenvoegen gebeurt aan de hand van een standaard OpenCV functie genaamd groupRectangles(). Functie groupRectangles() gebruikt de functie partition(), deze functie gaat proberen aan de hand van een beschrijving overlappende rechthoeken zoeken (Zie figuur 3.2a). Elk van de gevonden rechthoeken krijgen dan een label, met deze labels gaat groupRectangles() de vierkanten samenvoegen, te zien op figuur 3.2b.

(a)

(b)

Figuur 3.2: (a) functie illustratie partition() en (b) illustratie functie groupRectangles()

Nadat alle overlappende bounding boxes samengevoegd zijn, wordt de grootte hiervan aangepast. Met deze aangepaste bounding boxes worden er uit het frame uitsnijdingen gemaakt. Omdat er een kans bestaat dat in deze uitsnijding geen handen bevinden wordt er op voorhand de grote van de bounding box aangepast. Door de grootte aan te passen van de boundig box vergroot de kans dat de handen in de vergrootte bounding box zitten (verduidelijkt in figuur 3.3). Zodat achteraf wanneer deze bounding box omgezet wordt naar een uitsnijding en verwerkt worden door de hand detector, er hier allebei de handen in aanwezig zijn. En er dus geen handen verloren gaan terwijl deze toch aanwezig kunnen zijn in het totaal beeld.

3 Uitwerking

23

Figuur 3.3: De rode kaders tonen de boundig box aan in beide afbeeldingen. De bovenste boundig box is verkregen van uit de bovenlichaamsdetector. Deze wordt vergroot in verschillende richtingen. Dit zorgt er voor dat de handen zeker aanwezig zijn in de bounding box.

3.2

Gezichtsdetectie

Op de uitgesneden beelden afkomstig van de bovenlichaamsdetector gaat deze stap gezichten proberen te detecteren. Deze informatie is noodzakelijk voor tracking van de handen. Niet alleen voor de tracking wordt het gezicht gebruikt, ook wordt deze gebruikt om informatie te vinden en verwerken van de handdetecties in volgende stappen. Om een gezicht te detecteren wordt er gebruik gemaakt van Haar feature gebaseerde cascade classificator. Deze is standaard te gebruiken van OpenCV.

3.2.1

Implementatie

´ gezicht in het beeld aanwezig is zal de Aangezien er van uitgegaan wordt dat er altijd maar e´ en ´ ´ classificator er minstens een detecteren. Als er geen gezicht gedetecteerd wordt bij het starten van het programma zullen alle stappen die hier afhankelijk van zijn niet uitgevoerd worden. Dit is niet meer van toepassing wanneer er al een gezicht gedetecteerd geweest was in de loop van het programma. Dan zal de tracking deze taak overnemen en een voorspelling doen van waar het hoofd zich zou kunnen bevinden (zie hoofdstuk 3.5.2. Deze detectie wordt gerealiseerd door de standaard Haar feature gebaseerde cascade classificator van OpenCV. Het model is ook een standaard model van OpenCV. De derde handdetector gebruikt de grootte van het gezicht om te bepalen of dat een huidstuk een

24

3 Uitwerking

arm is of een hand (zie hoofdstuk 3.3.2). Dit wordt bepaald door dat men kan zeggen dat een hoofd ten opzichte van een arm kleiner is, dit is te zien op figuur 3.4.

Figuur 3.4: Deze figuur toont aan dat een arm van hand tot schouder groter is dan 3,5 keer het hoofd.

In klasse hoogste waarschijnlijkheid (zie hoofdstuk 3.4) wordt de informatie van het gezicht gebruikt voor valse detecties te elimineren door middel van de grootte, ook wordt deze gebruikt om de scores te verlagen als er handen in het gezicht gedetecteerd worden. Dit wordt gedaan omdat de handdetectie vaak valse detecties vindt in gezichten.

3.3

Hand detecties

In dit hoofdstuk gaan we de drie detectors bespreken. Deze drie detectors gaan onafhankelijk van elkaar handen zoeken. Dit heeft als resultaat dat er meer detecties worden gedetecteerd, en hopelijk handen die niet gedetecteerd worden door een van de andere detectoren toch nog gedetecteerd worden door een andere detector. De twee eerste zijn beide op model gebaseerde detectoren gebaseerd op de detector gebruikt in hoofdstuk 3.1. Het verschil tussen deze twee detectoren is dat ze beiden een ander model gebruiken. Het eerste model is getraind op handen terwijl de andere getraind is met achtergrond en een deel van de pols, deze wordt het context model genoemd. Het verschil is goed te zien op figuur 3.5. De derde detector gaat afhankelijk van de armen trachten de handen te detecteren. Dit geeft extra detecties die door de voorgaande detectoren kunnen gemist worden, bijvoorbeeld door bewegingsonscherpte (in het Engels motion blur ). Deze detector wordt hand-aan-arm detector genoemd.

3.3.1

Hand en context detector implementatie

De hand en context detectors worden samen besproken omdat deze zeer hard op elkaar gelijken. Zij gebruiken allebei dezelfde detector, deze detector is besproken in hoofdstuk 3.1. Het enige verschil tussen de twee is het model. Het eerste model is getraind op alleen handen. Dit model bestaat uit 3 root modellen, te zien op figuur 3.6.

3 Uitwerking

25

Figuur 3.5: Op deze figuur is een hand detectie te zien (blauwe kader) en een context detectie (rode kader)

Figuur 3.6: De drie root modellen met van links naar rechts de palm, rug en profiel van een hand.

Detector twee, de context detector zijn model is getraind op einde van armen met de achtergrond. Arpit Mittal and Torr (2011) geeft als verdediging voor gebruik van deze detector dat een einde van een arm soms meer zichtbaar of herkenbaar is dan een hand. Omdat de modellen getraind zijn op rechtstaande handen en arm eindes moet ofwel het model of de de afbeelding geroteerd worden per detectie. Aangezien dat de afbeelding gemakkelijker te draaien is dan het model is er voor deze aanpak gekozen. Op figuur 3.7 is goed te zien hoe het originele frame elke keer 10 graden geroteerd wordt. Om te vermijden dat er handen buiten de afbeelding zouden vallen tijdens het roteren (te zien op figuur 3.8 bovenste rij), wordt de afbeelding voorzien van een zwarte boorden. Deze worden geplaatst aan de langste zijden van het frame (Zie figuur 3.8, links onder). Omdat de detectievlakken in een geroteerde afbeelding gevonden zijn moeten ze omgerekend ¨ worden naar coordinaten bruikbaar in de niet geroteerde afbeelding, te zien in figuur 3.9. Bij het ¨ omrekenen naar de juiste coordinaten moet er ook rekening gehouden worden met de toegevoegde zwarte boorden die toegevoegd waren aan de afbeelding. ¨ De omrekening gaat aan de hand van de formules 3.1 de juiste coordinaten berekenen. In deze formule is ook de correctie C van de zwarte boord te zien als deze onder en boven aan de afbeelding was geplaatst. Indien dit deze aan de zijkanten was geplaatst was de correctie gebeurt in de vergelijking xc .

26

3 Uitwerking

Figuur 3.7: De afbeelding toont aan hoe een frame er uit ziet dat 360 graden gedraaid wordt met stappen van elke keer 10 graden ten opzichte van de vorige rotatie. De rotatie wordt telkens gedaan met de originele afbeelding om verlies aan data te vermijden.

Figuur 3.8: De bovenste rij symboliseert een afbeelding zonder toevoeging van zwarte band en de tweede rij met zwarte band. In de eerst kolom is de originele afbeelding te zien, gevolgd door een afbeelding die 90 graden gedraaid is. De laatste kolom toont aan welke delen zeker zijn verwerkt en de rode cirkels tonen aan dat door geen zwarte band toe te voegen informatie verloren kan gaan.

3 Uitwerking

27

xc = cosθ · (x − xcenter ) − sinθ · (y − xcenter ) + xcenter yc = sinθ · (x − ycenter ) − cosθ · (y − ycenter ) + xcenter −C

(3.1)

Variabelen

xc , yc Gecorrigeerd centrum van bounding box x, y Centrum detectie in geroteerd detectievlak xcenter , ycenter centrum detectievlak θ Rotatie van detectievlak ten opzichte van origineel C Correctie = hoogte van zwarte band

Figuur 3.9: Omzetting van een detectie naar de juiste geroteerde detectie

3.3.2

Hand-aan-arm implementatie

De hand-aan-arm gaat in drie stappen handen proberen te detecteren. Dit met de filosofie dat aan ´ gaat een huid segmentatie uitvoeren, vervolgens elke arm zeker 1 hand moet hangen. Stap e´ en wordt deze segmentatie geskeletteerd. Het skeletteren heeft als gevolg dat er van de segmentatie alleen de botten overblijven. Op deze botten wordt een Hough lijn detectie uitgevoerd dit geeft een idee over de locatie van de armen en handen. Omdat een persoon op verschillende afstanden kan staan moet er ergens een referentie gemaakt worden om te beslissen wat een hand is en wat een arm is. Deze beslissing wordt gebaseerd op de grootte van het hoofd (zie hoofdstuk 3.2). 3.3.2.1

Huid segmentatie

De huid segmentatie is gebaseerd op de paper van N. A. Abdul Rahim (2006) in deze paper maakt men gebruik van drie kleurruimten, RGB (Red Green Blue), HSV (Hue Saturation Value), en YCbCr (Luma Chroma red Chroma blue = YUV). Door op deze verschillende kleurruimten begrenzende regels toe te passen wordt er een huid gesegmenteerd. Deze begrenzende regels zijn via machine learning geleerd. Op figuur 3.10 is goed te zien hoe de huidskleur van een persoon verspreid is over de verschillende kleurruimten. Met deze gegevens kan men dan begrenzende regels uitwerken en nadien toepassen.

28

3 Uitwerking

(a)

(b)

Figuur 3.10: (a) Toont de distributie van huidskleur met Saturation en Value ten opzichte van Hue en (b) toont de distributie van Cr ten opzichte van Cb

(R > 95)AND(G > 40)AND(B > 20)AND (max{R, G, B} − min{R, G, B} > 15)AND (|R − G| > 15)AND(R > G)AND(R > B)

(3.2)

Vergelijking 3.2 toont de begrenzende regel voor de RGB kleurruimte. De vergelijkingen 3.3 tonen dan weer de regels voor de segmentatie in de YCrCb ruimte.

Cr ≤ 11.5862 ×Cb + 20 Cr ≥ 0.3448 ×Cb + 76.2069 Cr ≥ −4.5652 ×Cb + 234.5652 Cr ≤ −1.15 ×Cb + 301.75 Cr ≤ −2.2857 ×Cb + 432.85

(3.3)

Voor de HSV ruimte is het minder complex, zie vergelijking 3.4.

H < 25 H > 230 3.3.2.2

(3.4)

Skeletteren

Deze bewerking wordt soms ook wel thinning genoemd. Het skeletteren is een iteratief proces. Bij elke iteratie gaat deze methode de blob eroderen en dilateren. Het verschil tussen deze dilatie en het originele frame wordt bijgehouden. Deze bijgehouden data zal wanneer de hele afbeelding ¨ volledig is weg geerodeerd, het skelet vormen. Figuur 3.11 toont een resultaat van deze operatie. 3.3.2.3

Arm detectie

Om van het skelet bruikbare gegevens te verkrijgen, wordt hier op een lijn detector, detecties uitgevoerd. Deze lijn detector noemt Hough transform.

3 Uitwerking

29

(a)

(b)

Figuur 3.11: (a) toont een gesegmenteerd beeld op basis van huid pixels. Wanneer deze wordt wordt verwerkt door de skelet bewerking bekomt men (b)

Afhankelijk van de lengte van de gedetecteerde lijn gaan we beslissen of dit een hand is of een arm. Omdat de lengte van een arm kan verschillen van persoon tot persoon en van de afstand ten opzichte van de camera, wordt het hoofd als referentie gebruikt. Dit is duidelijk te zien op figuur 3.4. Als het lijnstuk langer is dan de hoogte van het hoofd dan wordt het lijn stuk aanschouwd als een arm. Aan beide lijneinden wordt er een fictieve hand detectie toegevoegd, omdat het niet zeker is of dat de einden nu een hand of een elleboog zou kunnen zijn. Wanneer de lengte van de lijn gelijk of kleiner is dan de hoogte van het gezicht dan wordt het centrum van de lijn gezien als een hand detectie. De rotatie van de detecties is gelijk aan de hoek van de lijnen.

Figuur 3.12: Deze figuur illustreert de twee mogelijkheden van de armdetectie. Rechts bovenaan is een arm gedetecteerd en links onderaan is er een hand gedetecteerd op basis van de lijnlengte.

3.4

Hoogste waarschijnlijkheid

In dit deel wordt het gedeelte hoogste waarschijnlijkheid besproken. Hier worden alle detecties samengevoegd en verwerkt. Eveneens zal geprobeerd worden een links en rechts hand te onderscheiden. Dit wordt gedaan in 5 stappen, dit is ge¨ıllustreerd op figuur 3.13. De eerste twee stappen proberen valse positieven te elimineren op basis van aantal huid pixels in de detecties en op grootte van de detectie. De overige resultaten worden dan geclusterd op basis van overlappende resultaten. Omdat er vaak valse positieven gedetecteerd op het gezicht en men niet kan uitsluiten dat deze toch handen zouden kunnen zijn, worden enkel hun scores verlaagd. Als laatste stap wordt er een links en rechts hand gezocht.

30

3 Uitwerking

Figuur 3.13: Werking diagamma van de klasse Hoogste waarschijnlijkheid

3.4.1

Eliminaties

Er zijn twee eliminaties, de eerste gebeurt op basis van de aantal gevonden huid pixels in de detectie. Deze eliminatie maakt gebruik van de al gesegmenteerde huidafbeelding die gemaakt is in de handdetectie stap (zie hoofdstuk 3.3.2.1). Uit deze segmentatie wordt dan de detectie ¨ uitgesneden en de aantal huid pixels geteld. Vervolgens worden de resultaten geelimineerd op basis van het oppervlakte percentage huid pixels in een detectie. De tweede eliminatie gaat de overblijvende resultaten elimineren op basis van de grootte van de detectie. Dit is gebaseerd op het idee dat een hand ongeveer dezelfde grootte heeft als een gezicht, ge¨ıllustreerd op figuur 3.14. Om deze eliminatie uit te voeren is er wel een gedetecteerd gezicht nodig. Als deze gevonden is, wordt er gekeken hoe deze twee van grootte verschillen, indien deze ¨ groter is dan het gezicht wordt deze geelimineerd uit de lijst van detecties.

Figuur 3.14: Illustratie van de menselijke maten van een hand ten opzichte van het gezicht

3 Uitwerking

3.4.2

31

Clustering

Om dubbele of gelijkende resultaten te vermijden worden deze samengevoegd. Voordat men deze kan samenvoegen moeten ze eerst gegroepeerd worden. Dit wordt gedaan door middel van het algoritme disjoint set of ook wel find-union algoritme genoemd (Hopcroft and Ullman (1973)). Nadat de verdeling gevonden is moeten de resultaten nog samengevoegd worden.

3.4.2.1

Find-union

Het find-union algoritme gaat proberen de resultaten te groeperen zonder dat er een resultaat in ´ groep kan zitten. Zoals de naam al suggereert bestaat de methode uit twee functies, meer dan e´ en de eerste is de find functie en gaat gelijkende resultaten zoeken. Elke keer er een gevonden is worden ze gelinkt met elkaar, gedaan door de union functie. Dit geeft als resultaat een lijst met verzamelingen indicatoren, te zien op figuur 3.15.

Figuur 3.15: Deze figuur illustreert een lijst van data. De bovenste rij toont de niet verwerkte data, elk resultaat heeft dus een eigen groep. Volgende rij toont de gegroepeerde lijst (union functie), deze bestaat uit drie onafhankelijke. Dit wordt nog eens getoond in de laatste rij door middel van een lijst van de verzameling indicatoren.

De find functie gaat op basis van een beschreven voorwaarde (vergelijking 3.5) die twee detecties met elkaar vergelijken. Deze voorwaarden gaan op basis van de afstand tussen de twee detecties zien of dat deze binnen een factor van de oppervlakte ligt van het detectie vlak.

q (Ax − Bx )2 + (Ay − By )2 ≤ Aarea · ε2

(3.5)

Variabelen

Ax , Ay Centrum van detectie A Bx , By Centrum van detectie B Aarea Oppervlakte van detectie A ε Variantie factor 3.4.2.2

Samenvoeging resultaten

Nadat alle resultaten gegroepeerd zijn moeten deze nog samengevoegd worden. Het samenvoegen gebeurt door gemiddelden te berekenen van alle parameters van de detecties. Dit geeft als resultaat dat alle respectievelijke posities worden opgeteld en gedeeld worden door het totaal aantal van de respectievelijke groep. Hetzelfde wordt gedaan voor de grootte. Om het gemiddelde van een hoek te berekenen kan men niet op dezelfde manier te werk gaan. Men moet de hoek omzetten naar het polaire domein (ontbinden in twee vectoren volgens de x- en

32

3 Uitwerking

y-as, zie vergelijking 3.6). Dan kan men deze twee vectoren optellen met elkaar (te zien op figuur 3.16). Bij het terug rekenen naar een hoek is het hier niet nodig om het resultaat te delen door het aantal elementen (zie vergelijking 3.7).

¨ som gemaakt. Figuur 3.16: Links zijn alle hoeken hoeken te zien, rechts daarvan is de vectoriele

 π  x + = cos α ·  180 π  y + = sin α · 180 α = tan−1 3.4.3

 y  180 · x π

(3.6)

(3.7)

Verlagen van hansdetecties in het gezicht

Soms worden er valse positieven gedetecteerd op het gezicht. Deze worden niet weg gefilterd door de voorgaande eliminaties. Dit omdat het huid pixels bevat en de grootte klein genoeg zijn, blijven ze deze in de lijst van resultaten. Dit is deels gewenst omdat het soms kan zijn dat de persoon zijn hand(en) voor het gezicht kan houden. Om er voor te zorgen dat deze niet direct gezien worden ¨ handen wordt hun scores verlaagt. Het verlagen van de scores zal er voor zorgen als potentiele dat echte handen meer kans maken om gekozen te worden in de volgende stappen.

Figuur 3.17: Op deze figuur zijn er enkele handen gedetecteerd op het gezicht.

Het beslissen om de score van bepaalde resultaten te verlagen, hangt vast aan de locatie van de resultaten. Hiervoor wordt de positie van het gezicht gebruikt (zie hoofdstuk 3.2). Als het centrum

3 Uitwerking

33

van de detectie binnen het gezichtsveld ligt plus een bepaalde vergroting dan zal de score hier van met een bepaalde waarde verlaagd worden.

´ binnen het gezichtsveld ligt en met gevolg de Figuur 3.18: De figuur illustreert twee detecties waarvan e´ en score zou verlaagd worden. De andere detectie ligt ver genoeg buiten de het gezicht, zelfs met de marge (oranje boord) ronde het gezicht.

3.4.4

Vinden van het linkse en het rechtse hand

De gemiddelde mens heeft twee handen. We onderscheiden deze als een links en een rechts hand. Het onderscheiden van deze twee handen is noodzakelijk voor het tracken van de handen. ¨ Als deze eens wisselen van orientatie wordt de tracking verstoord. Niet enkel is dit noodzakelijk voor de tracking maar kan ook handig zijn in latere toepassingen. De methode voor het vinden van het linkse hand ten opzichte van het rechtse hand verschilt niet, enkel wanneer er nog geen hand gedetecteerd is geweest en er dus ook geen voorspelling is gemaakt verschilt deze. Dit wilt zeggen dat men deze methode kan indelen in twee delen volgens wanneer er een geen voorspelling is en wanneer wel. Hier verschilt de methode voor het vinden van het linkse en het rechtse hand. Dit deel gaat gebruik maken van het idee dat in het begin de handen zich aan de juiste kant van het hoofd bevinden. Hier wordt weer het gezicht gebruikt, maar nu voor het bepalen van het centrum van het lichaam. Vervolgens gaat men aan de linkse kant van het gezicht in de afbeelding zoeken naar het rechtse hand. Dit gebeurt door de detectie te nemen met de hoogste scores. Dezelfde benadering wordt gebruikt voor het vinden van het linkse hand maar dan aan de rechtse kant van het gezicht in de afbeelding. Als er geen resultaten zijn aan een zijde dan wordt er voor die zijde geen hand gedetecteerd. Indien er wel een voorspelling gevonden is gaan de afstanden ten opzichte van de voorspelling en alle detecties berekend worden. Hoe dichter deze is ten opzichte van de voorspelling wordt de score verhoogd. Als na de verhoging van de scores en niet genoeg variatie is in de scores dan wordt er geen hand geselecteerd voor een van die zijden. Wanneer er genoeg variatie is worden de detecties met de ´ resultaat. hoogste score samen gevoegd tot e´ en

34

3 Uitwerking

Figuur 3.19: Voorbeeld van hoe een Kalman resultaat er kan uitzien.

3.5

Tracking

De laatste stap gaat proberen door middel van resultaten in het verleden, nieuwe resultaten bij te sturen en voorspellingen maken. Dit wordt verwezenlijkt door een Kalman filter te gebruiken, een illustratie is te zien op figuur 3.19. Voor het hoofd en de twee handen wordt er een Kalman filter aangemaakt. Het hoofd is belangrijk omdat dit als referentie wordt gebruikt voor de positie van de handen. Dit geeft een stabieler resultaat omdat het lichaam wel eens kan bewegen in een onvoorspelbare manier, terwijl dat de handen zich ten opzichte van het gezicht meestal voorspelbaarder gedragen. Eveneens worden foutieve of ontbrekende gezichtsdetecties gecorrigeerd.

3.5.1

Kalman filter

Een Kalman filter is een datamining algoritme dat verstoorde gemeten data gaat trachten te filteren. Op basis van een wiskundige model worden er voorspellingen berekent, samen met de gemeten data kan hier uit een beter schatting gemaakt worden naar een correcter resultaat. Het wiskundig model dat Kalman filter gebruikt is te zien in formule 3.8, dit bestaat uit drie delen. Het eerste deel is het gedragsmodel van het systeem. Meestal wordt deze beschreven als een lineair rechtlijnige beweging (voor een voorbeeld, zie formule 3.10). Dit geeft Kalman de mogelijkheid om te voorspellen wat de volgende positie kan zijn op basis van vorige resultaten. Deel twee is het bijsturend orgaan van de formule. In deze vector komen de metingen die gemaakt zijn van het systeem. Door deze twee eerste delen te combineren wordt er een betrouwbaarder resultaat gegenereerd. het laatste deel gaat trachten de ruis in het systeem te onderdrukken

~xt = Ft~xt−1 + Bt~ut + ~wt

(3.8)

3 Uitwerking

35

Variabelen:

~xt State vector, bevat gewenste waarde ~xt−1 Vorig state vector ~ut Control vector, bevat de veranderings model Ft State transition matrix, bevat het effect de vorige state heeft op de huidige state Bt Control input matrix, bevat et effect dat elke input heeft op de huidige state ~wt Process noise, ruis het proces kan hebben Om het beter te kunnen uitleggen wordt hier een voorbeeld gegeven (gebaseerd op een lecture note van Faragher, 2012). De opstelling is gebaseerd op een rechtlijnige lineaire beweging, gesymboliseerd door een wagon op een recht spoor.

´ dimensionale Kalman filter door middel van een wagon Figuur 3.20: Een voorbeeld opstelling voor een e´ en op een recht spoor spoor, Bron: Faragher, 2012

Het model hiervan is te zien in het eerste deel van de formule 3.10. Het tweede deel is het controle orgaan van de opstelling. Dit is de kracht aangebracht aan de wagon dat zich vertaalt naar een versnelling a, te zien in de vergelijking 3.9. Als 3.8 vergeleken wordt met 3.10 kunnen we hier de state transistion matrix en de control input matrix afleiden. Deze twee matrices zijn nodig om de Kalman filter te configureren.

Voorbeeld:

ft =a m

(3.9)

0 xt = xt−1 + (xt−1 ∆t) + 0 xt0 = xt−1    xt 1 = xt0 0  1 Ft = 0



ft ∆t m 2

ft ∆t m    ∆t 2  ∆t xt−1 + 2 0 1 xt−1 ∆t   ∆t 2  ∆t , Bt = 2 1 ∆t

 2

(3.10) (3.11) (3.12)

Op de voorspellingen en de metingen zit ruis, dit kan veroorzaakt worden door een incorrecte model beschrijving of door onnauwkeurige meetmethoden. Om dit probleem aan te pakken wordt de ruis beschreven als een Gaussverdeling, dit wordt ge¨ıllustreerd door de blauwe en de rode grafieken op

36

3 Uitwerking

figuur 3.21. Deze worden ingesteld als betrouwbaarheidsfactoren bij het opbouwen van de Kalman filter. Door deze twee verdelingen samen te voegen ontstaat er een nieuwe Gaussverdeling, dit is het uiteindelijk resultaat van de Kalman filter.

Figuur 3.21: Gaussische distributies van zowel de gemeten (blauw), voorspelde (rood) en de gecombineerde (groen), Bron: Faragher, 2012

3.5.2

Tracking van hoofd en handen

(a)

(b)

Figuur 3.22: (a) toont het pad dat de tracking moet verwerken indien de hoek van het verwerkte frame genomen wordt als referentie. Dit zorgt voor een combinatie van het pad dat het hoofd doet en het pad dat de handen doen. Terwijl wanneer we het hoofd als referentie nemen (te zien op (b)), dan ontstaat er een veel simpeler pad. Dit geeft als gevolg dat de padden van de handen voorspelbaarder worden.

De beelden zijn opgenomen door een mobiele eye-tracker, dit heeft als effect dat de beelden niet stabiel zijn. Mogelijk oorzaken zijn bijvoorbeeld knikken met het hoofd of plots het hoofd bewegen om naar iets te kijken. Indien het referentiepunt van de hand tracking zou liggen op het bewegend camera beeld, zou het pad dat de handen volgen moeilijker voorspelbaarder worden. De oorzaak is dat het pad een sommatie is van het pad dat de camera maakt ten opzichte van de persoon en het pad dat de handen maken ten opzichte van de persoon. Het fenomeen wordt ge¨ıllustreerd op figuur 3.22a. ¨ Dit kan opgelost worden door een zeer complex model te creeren. Ook is het mogelijk om het referentie punt te veranderen. Als het hoofd als referentie wordt genomen gedragen de handen zicht meer voorspelbaar (zie figuur 3.22b). Dit zorgt ervoor dat we de complexiteit van het Kalman model kunnen verlagen. Dit heeft als gevolg dat er een extra Kalman filter moet opgebouwd worden voor het hoofd. Indien we het hoofd verliezen doordat bijvoorbeeld de persoon naar beneden kijkt, wensen we het referentiepunt voor de handen niet te verliezen. Aangezien we een onderscheid maken tussen linker en rechter hand, hebben we twee aparte Kalman filters nodig. Voor elke Kalman filter moeten zowel de positie van het hand als de rotatie

3 Uitwerking

37

worden bijgehouden. Deze stap dient niet alleen om een correctie toe te passen op de gemeten data, maar geeft ook feed-back naar de vorige stap. In het onderdeel hoogste waarschijnlijkheid (hoofdstuk 3.4), gebruiken we de door Kalman voorspelde positie om in het volgende frame te bepalen welke van de overgebleven detectie het linkse en het rechtse hand is. Met deze gegevens kan de stap hoogste waarschijnlijkheid in het volgende iteratie bepalen welke van de overgebleven detectie het linkse en het rechtse hand is.

3.6

Data opslag

Omdat de data die gegenereerd is door het hier boven besproken algoritme later verwerkt moet kunnen worden wordt deze opgeslagen in een bestand. Het gebruikte bestandsformaat is het XML-formaat. Door het gebruiken van het XML-formaat wordt het bestand leesbaar voor niet alleen een machine maar ook voor een persoon, tevens is dit een veel gebruikte standaard. Het XML formaat maakt het mogelijk om de data eenvoudig te verwerken of te raadplegen in een andere programma. Ook is dit een handig formaat om data toe te voegen, veranderen of te verwijderen zonder dat hier speciale of zelfontwikkelde software voor nodig is. Dit omdat het formaat zo kan geopend worden in een standaard tekstverwerker (bijvoorbeeld kladblok op Windows of Text editor op Mac).

3.6.1

Structuur opbouw

Een voorbeeld van een XML bestand dat gegenereerd is door het hand detector algoritme is te zien in de listing 3.1. De eerste regel is een optionele declaratie van het type XML formaat, maar het wordt wel aangeraden. Tussen de twee Saves tags (gekenmerkt door < Saves > en < /Saves > ) worden alle gegevens opgeslagen die verzamelt zijn in de loop van het programma. Als eerste wordt vermeld van welk bestand de detecties afkomstig zijn. Dit voorkomt dat verschillende XML bestanden en datasets door elkaar gemengd worden. Dit wordt vervolgd door frame data, in deze data kan terug gevonden worden waar de bovenlichaamsdetector een lichaam gevonden heeft (zie hoofdstuk 3.1). Omdat deze data altijd een vierkant is wordt deze altijd opgeslagen in een Rect tag. Deze bestaat ¨ een de linkerbovenhoek coordinaten en de grootte van het vierkant. Enkel bij de handdetecties wordt er nog twee extra tags toegevoegd , de rotatie en de score van de detectie.

38

3 Uitwerking

´ verwerkt frame opgeslagen in een XML bestand. Listing 3.1: Voorbeeld van hand detectie data van e´ en

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

<Saves> [Directory path]/[file name].avi 150 <x>425 257 <Width>655 463 <x>198 46 <Width>68 68 <x>762 457 <Width>34 68 -160.602 <Score>0.681806 <x>542.641 409.571 <Width>46.75 70.75 -169.745 <Score>0.682803

Hoofdstuk 4

Conclusie Het algoritme kan linkse en rechtse handen detecteren in beelden afkomstig van een mobiele eyetracker. Dit zorgt ervoor dat manuele annotatie overbodig wordt. Door gebruik te maken van het hoofd als referentie, is deze relatief robuust tegen knikken en schudden van het hoofd van de drager van de eye-tracker. Door het gebruik van drie detectors ´ of twee detectors een hand worden er minder handen gemist in de beelden. Wanneer er e´ en missen is de kans groot dat de derde deze vind. Het gebruik van de FFLD bij de eerste twee detectors maakt deze methode sneller dan de vergelijkbare methode voorgesteld door Arpit Mittal and Torr (2011). Door de derde detector te gebruiken die zich baseert op armen, is het algoritme minder gevoelig voor motion-blur in de afbeeldingen. Maar dit geeft het effect dat er een hand verkeert gedetecteerd wordt, door bijvoorbeeld de arm te nemen als hand of het hand aan de verkeerde kant te nemen. Dit is te wijten aan de huid segmentatie. Omdat er drie detectors zijn, worden er veel resultaten gegenereerd. Door het verwijderen van de data door middel van verschillende stappen (eliminaties, clustering en locatie) kan de detector gemakkelijk en nauwkeurig de linkse en rechtse handen vinden. Door de terugkoppeling van de tracking kan men de juiste handen onderscheiden van links en rechts, zelfs als deze beide zijn gekruist. De Kalman filter probeert afhankelijk van vorige gegevens de resultaten bij te sturen. Indien er soms geen links of rechts hand wordt gedetecteerd, zal de filter trachten een voorspelling te maken, er dus voorzorgen dat vanaf er een hand gedetecteerd is er altijd een gevonden zal worden.

4.1

Future work

Er zijn paar punten waar nog verder aan gewerkt kan worden om het algoritme te verbeteren. Door de tracking verder uit te breiden kan het detectie resultaat alleen maar verbeteren. Om het blur problemen nog verder te onderdrukken kan er een betere en dynamische huid segmentatie gebruikt worden. Om er voor te zorgen dat het nog voordeliger wordt om dit algoritme te gebruiken zou de detectie ´ of meerdere manieren verder versneld kunnen snelheid van de verschillende detectoren op e´ en worden. Als laatste zou het algoritme uitgebreid kunnen worden door zodat deze meerdere personen kan tracken en dus kun handen hiervan zou kunnen detecteren. 39

40

4 Conclusie

Aangezien het algoritme ontwikkeld is voor mobiele eye-trackers zou men de gaze data kunnen gebruiken samen met de hand detectie data. Dit kan nuttig zijn voor verdere toepassingen, zoals bijvoorbeeld de afstand tussen het gaze punt en de handen. Deze methode kan verder ook gebruikt worden als fundering om een handgebaren detector te ontwerpen

Bibliografie Arpit Mittal, A. Z. and Torr, P. (2011). Hand detection using multiple proposals. In Proceedings of the British Machine Vision Conference, pages 75.1–75.11. BMVA Press. http://dx.doi.org/10.5244/C.25.75. Bo, N. B., Dailey, M. N., and Uyyanonvara, B. (2007). Robust hand tracking in low-resolution video sequences. In Proceedings of the third conference on IASTED International Conference: Advances in Computer Science and Technology, ACST’07, pages 228–233, Anaheim, CA, USA. ACTA Press. Dalal, N. and Triggs, B. (2005). Histograms of oriented gradients for human detection. In In CVPR, pages 886–893. Dubout, C. and Fleuret, F. (2012). Exact acceleration of linear object detectors. In Proceedings of the European Conference on Computer Vision (ECCV), pages 301–311. Eichner, M., Marin-Jimenez, M., Zisserman, A., and Ferrari, V. (2012). 2d articulated human pose estimation and retrieval in (almost) unconstrained still images. International Journal of Computer Vision, 99:190–214. eye-com king

research (2013). methods.

A

comparison

of

bright

and

dark

pupil

trac-

http://eyecomresearch.com/eyetrackingresearch/ a-comparison-of-bright-and-dark-pupil-tracking-methods/.

Faragher, R. (2012). Understanding the Basis of the Kalman Filter Via a Simple and Intuitive Derivation [Lecture Notes]. Signal Processing Magazine, IEEE, 29(5):128–132. Felzenszwalb, P. F., Girshick, R. B., McAllester, D., and Ramanan, D. (2010). Object detection with discriminatively trained part-based models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(9):1627–1645. Hopcroft, J. and Ullman, J. (1973). Set merging algorithms. SIAM Journal on Computing, 2(4):294– 303. Li, D., Winfield, D., and Parkhurst, D. J. (2005). Starburst: A hybrid algorithm for video-based eye tracking combining feature-based and model-based approaches. Computer Vision and Pattern Recognition. Lienhart, R. and Maydt, J. (2002). An extended set of haar- like features for rapid object detection. pages 900–903. IEEE International Conference on Image Processing (ICIP). Locarna (2009). Calibration robustness. 41

42

BIBLIOGRAFIE

Mahalanobis, P. C. (1936). On the generalised distance in statistics. In Proceedings National Institute of Science, India, volume 2, pages 49–55. Muller, K., Merkle, P., and Wiegand, T. (2011). 3-d video representation using depth maps. Pro¨ ceedings of the IEEE, 99(4):643–656. N. A. Abdul Rahim, C. W. Kit, J. S. (2006). Rgb-h-cbcr skin colour model for human face detection. In MMU International Symposium on Information and Communications Technologies (M2USIC), Petaling Jaya, Malaysia. Rother, C., Kolmogorov, V., and Blake, A. (2004). ”grabcut”: Interactive foreground extraction using iterated graph cuts. In ACM SIGGRAPH 2004 Papers, SIGGRAPH ’04, pages 309–314, New York, NY, USA. ACM. Suryanarayan, P., Subramanian, A., and Mandalapu, D. (2010). Dynamic hand pose recognition using depth data. In ICPR, pages 3105–3108. IEEE. Viola, P. and Jones, M. (2001). Rapid object detection using a boosted cascade of simple features. pages 511–518. IEEE Computer Society Conference on Computer Vision and Pattern Recognition.

FACULTEIT INDUSTRIELE INGENIEURSWETENSCHAPPEN CAMPUS DE NAYER (@Thomas More) Jan De Nayerlaan 5 2860 SINT-KATELIJNE-WAVER, België tel. + 32 15 31 69 44 [email protected] www.iiw.kuleuven.be