Suivi de personnes par filtrage particulaire pour la vidéo-surveillance

DRT LIST - DTSI

Service Architectures et Conception CEA/SACLAY 91191 GIF-SUR-YVETTE CEDEX

TL : +33 (0)1 69 08 65 25 - FAX : +33(0)1 69 08 83 95 E-MAIL : [email protected]

Ce document et les informations quil contient, sont la proprit exclusive du CEA. Ils ne peuvent pas tre communiqus ou divulgus sans une autorisation pralable du Cea-List.

DIRECTION DE LA RECHERCHE TECHNOLOGIQUE

CEA/SACLAY DEPARTEMENT DES TECHNOLOGIES DES SYSTEMES INTELLIGENTS

SERVICE ARCHITECTURES ET CONCEPTION

Service Architectures et Conception

Saclay, le 30 aot 2005

REF. : DTSI/SARC/05-235/ND

Suivi de personnes par filtrage particulaire pour la vido-surveillance

Par

Nicolas DUFAUR

DRT/LIST/DTSI/SARC/LCEI (CEA)

Suivi de personnes par filtrage particulaire pour une application de vidosurveillance __________________________________________________________________________

__________________________________________________________________ ii DRT LIST - DTSI

Service Architectures et Conception CEA/SACLAY 91191 GIF-SUR-YVETTE CEDEX

TL : +33 (0)1 69 08 65 25 - FAX : +33 (0) 1 69 08 83 95 E-MAIL : [email protected]

Ce document et les informations quil contient, sont la proprit exclusive du CEA. Ils ne peuvent pas tre communiqus ou divulgus sans une autorisation pralable du Cea-List.

Ce document est la proprit du CEA. Il ne peut tre reproduit ou communiqu sans son autorisation.

REDACTEURS

VERIFICATEUR

CHEF DE SERVICE

NOM

Nicolas DUFAUR

Quoc-Cuong PHAM

Thierry COLLETTE

DATE

SIGNATURE

IDENTIFICATION : Rapport DTSI/SARC/05-235/ND TITRE : Suivi de personnes par filtrage particulaire pour la vido-

surveillance AUTEURS : Nicolas DUFAUR Mots-clefs : Suivi de personnes, Filtrage particulaire, Vido-surveillance UNITE : DRT/LIST/DTSI/SARC/LCEI RESUME/Contexte Nous nous intressons au problme du suivi de personnes dans

le contexte de la vido-surveillance. La dtection et le suivi dobjets, robustes et temps rel, sont des tapes fondamentales du systme danalyse vido et des entres indispensables une interprtation plus haut niveau des scnes. Le problme du suivi reste un problme ouvert en situation relle o lon rencontre de nombreuses difficults telles que les changements dclairement et dapparence des objets, les occultations, le bruit, la gestion des cibles multiples... Le filtre particules est lune des solutions retenues au laboratoire, en raison de sa gnricit et sa robustesse. Nous prsentons dans ce rapport diffrentes contributions au suivi par filtrage particulaire bas sur des histogrammes couleur, ainsi que leur valuation quantitative sur des squences de rfrence.

Liste de diffusion :

DTSI / SARC / LCEI / Q.C. Pham, L. Letellier, N. Dufaur


Remerciements

Je souhaiterais tout dabord remercier lensemble des personnes qui ont rendu cestage possible et qui mont accueilli au sein de leur unit, notamment M. ThierryCollette, chef de service, et M. Laurent Letellier, chef de laboratoire.

Je remercie bien sr tout particulirement mon tuteur de stage, M. Quoc-Cuong Pham,qui ma guid tout au long de ces six mois, qui a toujours t disponible pour mesquestions, et qui a toujours su me rpondre et me conseiller avec simplicit et efficacit.

Je tiens enfin remercier tous les membres de lquipe pour lambiance studieusemais sympathique prsente au sein du laboratoire, et notamment les autres stagiaires,JC, Antoine et Gal, qui mont galement fait profiter de leurs nombreuses connais-sances en C++.

DRT LIST DTSIService Architectures et Conception

CEA/SACLAY 91 191 GIF-SUR-YVETTE CEDEXTL : +33 (0) 1 69 08 65 25 FAX : +33 (0) 1 69 08 83 95 EMAIL : [email protected]

Ce document et les informations quil contient, sont la proprit exclusive du CEA. Ils ne peuvent pastre communiqus ou divulgus sans une autorisation pralable du CeaList.

v


Table des matires

Remerciements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix

1 Prsentation du CEA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Histoire, Implantations gographiques et chiffres . . . . . . . . . . . . . 31.2 Organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2.1 Le ple dfense . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2.2 Le ple nuclaire . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2.3 Le ple de recherche . . . . . . . . . . . . . . . . . . . . . . . . 51.2.4 Le ple de recherche technologique . . . . . . . . . . . . . . . . 5

1.3 Le LIST . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Problmatique du suivi dobjets et tat de lart . . . . . . . . . . . . 92.1 Problmatique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Caractristiques visuelles . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2.1 Caractristiques bas niveau . . . . . . . . . . . . . . . . . . . . 122.2.2 Caractristiques haut niveau . . . . . . . . . . . . . . . . . . . . 14

2.3 Espace de recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.3.1 Recherche exhaustive . . . . . . . . . . . . . . . . . . . . . . . . 142.3.2 Optimisation dune fonction de cot . . . . . . . . . . . . . . . . 142.3.3 Modle dynamique a priori . . . . . . . . . . . . . . . . . . . . . 14

2.4 Mthodes sappuyant sur une segmentation . . . . . . . . . . . . . . . . 152.4.1 Soustraction de fond . . . . . . . . . . . . . . . . . . . . . . . . 152.4.2 Dtection des objets mobiles par diffrence temporelle . . . . . . 152.4.3 Contours actifs . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.5 Suivi par Mean Shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.6 Filtres baysiens rcursifs . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.6.1 Le filtre de Kalman . . . . . . . . . . . . . . . . . . . . . . . . . 192.6.2 Le filtre particules . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Suivi par filtrage particulaire . . . . . . . . . . . . . . . . . . . . . . . . 21




vii


3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2 Implmentation du filtre particules . . . . . . . . . . . . . . . . . . . 23

3.2.1 Caractristiques visuelles . . . . . . . . . . . . . . . . . . . . . . 243.2.2 Distance entre histogrammes . . . . . . . . . . . . . . . . . . . . 243.2.3 Modle dynamique . . . . . . . . . . . . . . . . . . . . . . . . . 253.2.4 Rsum de lalgorithme . . . . . . . . . . . . . . . . . . . . . . . 253.2.5 Performances . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.3 Amliorations apportes au filtre particules . . . . . . . . . . . . . . . 263.3.1 Grille dchantillonnage . . . . . . . . . . . . . . . . . . . . . . . 263.3.2 Mise jour du modle . . . . . . . . . . . . . . . . . . . . . . . 263.3.3 Pr-traitement des images . . . . . . . . . . . . . . . . . . . . . 283.3.4 Dcoupage spatial . . . . . . . . . . . . . . . . . . . . . . . . . . 313.3.5 Mise jour de lchelle . . . . . . . . . . . . . . . . . . . . . . . 343.3.6 Combinaison avec le Mean Shift . . . . . . . . . . . . . . . . . . 36

4 valuation des algorithmes de suivi implments . . . . . . . . . . . 394.1 Vrit Terrain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2 Dfinition dune mtrique utilise pour valuer les algorithmes . . . . . 414.3 Rsultats exprimentaux . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.3.1 Ajout de linformation spatiale par dcoupage . . . . . . . . . . 444.3.2 Mise jour de lchelle . . . . . . . . . . . . . . . . . . . . . . . 444.3.3 Influence du nombre de particules . . . . . . . . . . . . . . . . . 464.3.4 Influence du nombre de classes des histogrammes . . . . . . . . 484.3.5 Influence de la mthode de tirage . . . . . . . . . . . . . . . . . 494.3.6 Combinaison avec le MeanShift . . . . . . . . . . . . . . . . . . 514.3.7 Pr-traitement des images . . . . . . . . . . . . . . . . . . . . . 524.3.8 Ajustement de la variance de la loi de tirage des particules . . . 52

4.4 valuation du filtre particules . . . . . . . . . . . . . . . . . . . . . . 524.4.1 Comparaison avec le filtre particules de base . . . . . . . . . . 534.4.2 Comparaison avec le MeanShift . . . . . . . . . . . . . . . . . . 59

4.5 Bilan des tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5 Conclusion et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . 655.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.2 Perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.2.1 Prise en compte du fond . . . . . . . . . . . . . . . . . . . . . . 675.2.2 Mise jour du modle . . . . . . . . . . . . . . . . . . . . . . . 685.2.3 Orientation des cibles . . . . . . . . . . . . . . . . . . . . . . . . 695.2.4 Information de haut niveau base sur lorientation du gradient

pour la corrlation . . . . . . . . . . . . . . . . . . . . . . . . . 705.2.5 Interpolation de la fonction de densit de probabilit . . . . . . 70

viiiDRT LIST DTSI

Service Architectures et ConceptionCEA/SACLAY 91 191 GIF-SUR-YVETTE CEDEX

TL : +33 (0) 1 69 08 65 25 FAX : +33 (0) 1 69 08 83 95 EMAIL : [email protected]


TABLE DES MATIRES


5.3 Bilan personnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

Annexes et bibliographie 73

A Lespace de couleur HSV . . . . . . . . . . . . . . . . . . . . . . . . . . 75

B La mthode de Monte-Carlo . . . . . . . . . . . . . . . . . . . . . . . . 78

C Filtre baysien rcursif . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80C.1 quation de prdiction . . . . . . . . . . . . . . . . . . . . . . . . . . . 80C.2 quation de mise jour . . . . . . . . . . . . . . . . . . . . . . . . . . 81

D Environnement de dveloppement . . . . . . . . . . . . . . . . . . . . 83

E Planning sommaire du stage . . . . . . . . . . . . . . . . . . . . . . . . 84

Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

TABLE DES MATIRESDRT LIST DTSI




ix


Introduction

Les travaux raliss au cours de ce stage concernent le dveloppement de tech-niques gnriques pour le suivi de personnes dans le contexte de la vido-surveillance.La dtection et le suivi de personnes sont des tapes cls et des entres ncessairesau systme dinterprtation automatique de scnes. Typiquement, dans une applica-tion de vido-surveillance visant accrotre la scurit dans les transports publics, ilest essentiel de pouvoir tout moment connatre le nombre et la position des per-sonnes prsentes dans la scne, et dtre capable de les suivre au cours du temps,afin de reconnatre le cas chant une situation anormale (agression, vandalisme,...).La dtection permet de trouver dans limage les rgions o se situent les personnes.Lalgorithme de suivi, quant lui, doit tre capable dassocier temporellement lescibles et de dterminer leur trajectoire. Le suivi dobjets robuste et en temps rel at ces dernires annes lobjet de nombreux travaux de recherche. Malgr les avan-ces importantes dans le domaine, il reste un problme ouvert, car il faut faire face ensituation relle de nombreuses difficults telles que les occultations, le changementde luminosit et dapparence, la confusion des cibles, le caractre souvent imprvisiblede leur trajectoire.

La premire partie du rapport est consacre la prsentation du CEA, et situele laboratoire dans lequel sest droul le stage. Dans une deuxime partie, nous ex-poserons la problmatique du suivi de personnes et ferons un rapide tat de lart destechniques existantes. Dans la troisime partie, nous prsenterons plus en dtail lasolution retenue au laboratoire, savoir le filtrage particulaire. Le filtre particulesest une approche probabiliste largement utilise aujourdhui. Il permet dexplorer deshypothses multiples, ce qui le rend particulirement robuste par rapport aux autresmthodes. Nous exposerons ensuite les diverses amliorations que nous avons appor-tes la mthode de base.Dans le chapitre suivant, les diffrentes variantes de la mthode sont values quan-titativement partir de squences de rfrence et dune vrit terrain tablie sur cesdonnes. Nous donnerons enfin un bilan et les perspectives damlioration de lalgo-rithme de suivi.




xi


Chapitre

1Prsentation du

Commissariat lnergieAtomique




1


1.1 Histoire, Implantations gographiques et chiffresLe Commissariat lnergie Atomique est un tablissement public de recherche

fondamentale et technologique. Lordonnance de la cration du CEA a t approuvepar le gouvernement du gnral de Gaulle, le 18 octobre 1945. Cet tablissement estcharg de donner la France la matrise de latome et de ses applications.

Mais les activits du CEA se sont dveloppes dans tous les domaines connexes au nu-claire. Cette diversification a permis au CEA dtre un acteur majeur de la recherchedans des domaines lis au nuclaire mais aussi trs loigns de ce dernier : dissuasionnuclaire, micro et nano technologies, astrophysique, imagerie mdicale. . .

Le CEA est reparti sur neuf centres sur toute la France. Il existe deux types decentres :

les centres dtudes pour les applications militaires (Bruyres-le-Chtel, Cesta,Valduc et le Ripault)

les centres dtudes civils (Fontenay-aux-Roses, Saclay, Grenoble, Cadarache,Valrh)

Leur implantation peut tre visualise sur la figure 1.1.

En ce qui concerne les chiffres, le CEA fonctionne avec un budget de 2.8 mil-liards deuros annuels et emploie plus de 15 000 personnes. Il travaille aussi pour lesentreprises, en 2001 par exemple, 1300 contrats ont t signs avec lindustrie. Plusrcemment, en 2005, 14 projets dans lesquels le CEA est impliqu ont t labelli-ss comme ples de comptitivit, dont 5 projets mondiaux. On retrouve dans cesprojets les principales thmatiques de recherche et dveloppement du CEA: fusion,fission, nergies renouvelables, hydrogne, sciences du vivant, sciences de la matire,technologies de linformation et de la communication et dfense.

1.2 LorganisationLe CEA est organis autour de 4 grands ples dactivits :

1.2.1 Le ple dfense

Cest au ple Dfense du CEA qua t confie la mission de concevoir, fabriqueret entretenir les ttes nuclaires qui quipent les forces ocaniques et aroportes.Apportant aux pouvoirs publics la garantie que ces ttes sont fiables et sres, il estlun des principaux artisans de la crdibilit de la dissuasion nuclaire franaise.

1 . Prsentation du CEADRT LIST DTSI




page 3 sur 86


Fig. 1.1 Implantation gographique des sites

Aujourdhui, lobjectif du Ple dfense, est de continuer assurer sur le long termecette capacit de dissuasion sans recourir aux essais nuclaires, dfinitivement arrtsdepuis 1996. A cette fin, sa priorit pour la dcennie venir est de mettre en oeuvrele programme Simulation.

1.2.2 Le ple nuclaire

La Direction de lnergie Nuclaire (DEN) mne la ralisation de programmes ma-jeurs sur les systmes prsents et futurs de production de lnergie nuclaire ainsi quesur les aspects combustibles, sret, gestion des dchets et traitement des combustiblesuss.

page 4 sur 86DRT LIST DTSI




1 . Prsentation du CEA


1.2.3 Le ple de recherche

Le ple de recherche est compos de deux directions :

La Direction des Sciences du Vivant (DSV): Le premier axe de recherche decette direction concerne la recherche biologique et mdicale pour lnergie nu-claire. Il comprend ltude des effets sur la matire vivante des rayonnementsionisants et des toxiques utiliss dans la recherche et lindustrie nuclaire.Le second axe de recherche privilgi porte sur les applications des technologiesissues du nuclaire la sant et aux biotechnologies (exemple : marquage lorsdexamens mdicaux).

La Direction des Sciences de la Matire (DSM): Les recherches la DSM sontorientes sur des domaines trs varis tels que le domaine de lnergie et de len-vironnement (chimie, physique, . . . ), des sciences de la matire pour linnovationindustrielle (nano-physique, . . . ), de lutilisation des technologies du nuclaireen recherche biologique et mdicale, de la connaissance de la matire (physiquedes noyaux et des particules, astrophysique, etc. . . ).

1.2.4 Le ple de recherche technologique

La Direction de la Recherche Technologique (DRT) est un acteur majeur concer-nant les transferts de technologie et de connaissances vers lindustrie et les PME-PMI.La DRT voit son activit dcoupe en trois secteurs:

les nouvelles technologies de lnergie (systmes voltaques, changeurs ther-miques...)

les matriaux mergents (matriaux nanostructurs,...) Les technologies de linformation et de la communication: micro et nano techno-logies, technologies logicielles et systmes embarqus, interactifs et instrumen-tation

Ce ple est constitu de trois units de recherche que sont le Laboratoire dlec-tronique et des Technologies de lInformation (LETI) dont les activits principalessont la microlectronique, les microtechnologies, loptronique, les techniques informa-tiques, et linstrumentation et qui est lun des plus gros laboratoires europens de re-cherche applique en lectronique, le Laboratoire dInnovations pour les Technologiesdes Energies nouvelles et les Nanomatriaux (LITEN) et le Laboratoire dIntgrationdes Systmes et des Technologies (LIST).

La figure 1.2 ci-aprs prsente lorganigramme du CEA, pour la branche recherche/techniquedune part, pour la branche administrative dautre part.





page 5 sur 86


Fig. 1.2 Organigramme

1.3 Prsentation du Laboratoire dIntgration des Sys-tmes et des Technologies

Le LIST est un laboratoire de recherche technologique en Ile de France.Il dveloppe des systmes numriques destins tre intgrs dans des produits etdes procds innovants. Il regroupe des comptences dans les domaines des systmesembarqus (autonomes), des systmes interactifs (interaction homme-machine, ralitvirtuelle, robotique), de linstrumentation et de la mtrologie, ainsi que dans celui desmatriaux (assemblage et contrle non destructif de systmes mcaniques, laborationet mise en forme de matriaux).

Ce laboratoire est structur autour de deux dpartements:

le Dpartement des TEchnologies du Capteur et du Signal (DETECS) le Dpartement des Technologies des Systmes Intelligents (DTSI)

Le DTSI est charg des travaux de recherche et dveloppement sur les technologiesassociant le logiciel au matriel pour constituer des systmes fort niveau dintgra-





1 . Prsentation du CEA


tion. Le DTSI est constitu de trois services:

le Service Outils Logiciels (SOL) le Service Cognitique Robotique et Interaction (SCRI) le Service ARchitectures et Conception (SARC)

Ce dernier est constitu de deux laboratoires qui tudient et dveloppent des sys-tmes embarqus destins des applications de traitements dimage et de donnes,disposant dune trs forte puissance de calcul, sous contraintes oprationnelles (volumeet consommation) et environnementales (robustesse):

le Laboratoire Conception des Systmes Durcis (LCSD) le Laboratoire Calculateurs Embarqus et Image (LCEI)

Le Laboratoire Calculateurs Embarqus et Image

Le LCEI tudie des solutions de calcul innovantes et performantes, ralise des pro-totypes de calculateurs embarqus pour ses partenaires industriels et dveloppe desoutils de programmation.

Ses thmes de recherche portent sur les architectures de calcul pour les SoC (Sys-tem on Chip) notamment autour de structures parallles et reconfigurables mais aussiles rseaux NoC (Network on Chip) pour des problmatiques image. Dans ce contexte,le LCEI a dvelopp des comptences en systmes de vision pour la mesure dimen-sionnelle de grande prcision, la reconstruction 3D denvironnements et la vidosur-veillance.





page 7 sur 86


Chapitre

2Problmatique du suividobjets et tat de lart




9


2.1 Problmatique du suivi temps rel dobjetsDfinition et difficults techniques

Le suivi dun objet dans une squence vido consiste le dfinir un temps initial(modle de rfrence reprsent par un vecteur de caractristiques q) et le retrouverautomatiquement dans les images suivantes en cherchant la cible candidate p ayant laplus grande ressemblance avec le modle. Cette recherche peut tre interprte commela minimisation dune distance entre le modle et la cible candidate d(p, q) reprsen-tant la dissimilarit entre le modle et la cible. La dfinition du modle est importantedans le sens o elle conditionne le type dinformation que lon doit rechercher danslimage. Si lapparence de lobjet change beaucoup, il conviendra deffectuer une mise jour du modle de rfrence. Ce modle peut tre issu dune initialisation manuelledune rgion dintrt par exemple, ou le rsultat dune dtection automatique.

Le suivi dun objet peut tre envisag en 2-D ou en 3-D (si lon dispose de plusieursvues dune mme scne, ou si lon peut remonter avec suffisamment de prcision uneinformation tri-dimensionnelle grce aux informations de position, de taille, et uncalibrage de la camra). Dans ce qui suit, nous ne considrons que le problme desuivi en deux dimensions.

Les principales difficults rencontres sont les suivantes :

prsence de motifs similaires aux cibles qui peuvent faire driver lalgorithme desuivi,

changements (qui peuvent tre brutaux) de lapparence des cibles (rotation delobjet dans lespace par exemple, modification de lclairement des cibles et dufond, changements dchelle importants...)

occultation des cibles, proximit et croisement des cibles, disparition, apparition et rapparition des cibles.

La figure 2.1 illustre quelques unes de ces difficults.

Les changements dapparence de la cible entranent une dissimilarit importanteentre le modle de rfrence et les cibles candidates, ce qui peut faire chouer lalgo-rithme de suivi qui va prfrer saccrocher sur une zone qui na rien voir avec ce quelon dsirait suivre, mais qui prsente une meilleure ressemblance avec la rfrence.

Enfin, lalgorithme de suivi doit tre le plus robuste possible par rapport auxproblmes mentionns ci-dessus, tout en restant efficace. Il y a donc un compromis trouver entre robustesse et complexit algorithmique.

2 . Problmatique du suivi dobjets et tat de lartDRT LIST DTSI




page 11 sur 86


Fig. 2.1 Suivi de visages - Exemples de problmes rencontrs : changement dappa-rence, dchelle, occultations.

2.2 Caractristiques visuellesCest linformation extraite de limage qui va permettre de caractriser une cible

au cours du temps. Elle doit tre la plus stable possible.

2.2.1 Caractristiques bas niveau

On utilise couramment les caractristiques visuelles suivantes : la valeur des pixels, des statistiques sur une rgion (moyenne, variance, histogrammes...), le gradient de limage (orientation, norme), la forme de contours...

Mthodes de corrlation

La mthode la plus simple consiste effectuer un calcul de corrlation entre deuxrgions, directement sur la valeur des pixels exprims.Exemple :

7 8 78 9 87 8 7

et6 8 97 8 59 7 6

sont fortement corrls

7 8 78 9 87 8 7

et12 241 98186 1 352 145 203

sont faiblement corrls

Le rsultat du suivi est la position du maximum de corrlation.Dans [1], deux critres sont valus, la somme des diffrences au carr et linter-corrlation normalise.





2 . Problmatique du suivi dobjets et tat de lart


Mthodes bases sur les histogrammes couleur

Les histogrammes couleur sont utiliss dans [2], [3], [4]. Les espaces de couleur lesplus utiliss sont le RGB et le HSV qui permet de dcorrler linformation de couleurde la luminosit. Les histogrammes reprsentent des distributions. Pour lhistogrammedu modle :

q = {qu}u=1...m tel quemu=1

qu = 1 (2.1)

et pour lhistogramme des cibles candidates :

p(y) = {pu(y)}u=1...m tel quemu=1

pu = 1 (2.2)

avec m le nombre de classes des histogrammes, et y reprsentant la position ducentre du candidat.

Chaque classe de lhistogramme du modle est calcul selon la relation 2.3.

qu = Cni=1

k(||xi||2)(b(xi),u) (2.3)

o reprsente le symbole de Kronecker (valant 1 si ses deux paramtres sont gaux,0 sinon), xi les n pixels constituant le modle et b la fonction qui associe un pixellindex de la classe de lhistogramme dans lequel il se situe, k un noyau de pondration 1

et C une constante de normalisation dfinie par :

C =1n

i=1 k(||xi||2)(2.4)

Et pour le calcul des classes de celui des cibles candidates :

pu(y) = Ch

nhi=1

k(||y xih

||2)(b(xi),u) (2.5)

o nh est le nombre de pixels prsents dans le candidat et Ch dfini par :

Ch =1nh

i=1 k(||yxih ||2)(2.6)

1. Un noyau est une fonction K vrifiant:i) u Rd,K(u) 0 (positive)ii) M R,u Rd,K(u) M (borne)iii)Rd K(u)du = 1 (normalise)

iv) lim||u||+

||u||dK(u) = 0 (dcroissance rapide)





page 13 sur 86


2.2.2 Caractristiques haut niveau

On peut galement envisager des caractristiques visuelles plus "haut niveau" lies la nature de lobjet suivre. Par exemple, pour suivre un visage, on peut essayerde trouver des candidats contenant deux yeux, un nez, une bouche..., ressemblant leplus au visage de rfrence, lobjet "visage" tant appris au pralable. Ce type desuivi implique des techniques de reconnaissance dobjets. Dans [5], le suivi se basesur des caractristiques relatives aux silhouettes de joueurs de hockey apprises avecAdaboost.

2.3 Espace de recherche

2.3.1 Recherche exhaustive

Lespace de recherche le plus simple est limage entire (recherche exhaustive).Une telle recherche est trs coteuse en temps de calcul. De plus, aucune cohrenceau niveau de la trajectoire des cibles nest garantie et lalgorithme de suivi peut sansdistinction saccrocher sur nimporte quel maximum local du critre de similarit.Cette mthode peut tre amliore par une approche multi-chelle.

2.3.2 Optimisation dune fonction de cot

La recherche peut tre guide selon loptimisation dune fonction de cot. La po-sition de la cible est alors dplace vers un optimum de cette fonction. La procduredu mean-shift, qui sera dtaille ultrieurement, permet de trouver le minimum localdune fonction de dissimilarit [2].

2.3.3 Modle dynamique a priori

Par ailleurs, si lon dispose dun modle de mouvement suffisamment fin, on peutorienter la recherche en faisant une prdiction de la trajectoire des cibles, en faisantlhypothse quil existe une relative continuit dans les positions successives dun ob-jet au cours du temps. Le mouvement des cibles respecte la plupart du temps deslimites physiques. Par exemple, un humain ne peut se dplacer nimporte quellevitesse (35km/h semble tre une limite raisonnable). Dans [6], les auteurs proposentun modle dynamique dordre 2. Dans un cas gnral, tablir un modle dynamiquefidle la ralit est dlicat. En effet, une personne peut avancer, sarrter, se tourneret repartir en sens inverse ou dans une autre direction... En labsence da priori surle mouvement des objets, on peut utiliser un modle dordre 0, cest--dire rechercherautour de la position trouve dans limage prcdente [4].







2.4 Mthodes sappuyant sur une segmentationCertaines techniques de suivi intgrent une segmentation de limage qui est parti-

tionne en objets dintrt et en fond.

2.4.1 Soustraction de fond

Idalement, si le fond est entirement connu, et dans le cas dune camra fixe, ilest possible de le soustraire limage pour ne garder que les objets dintrt. La plusgrosse difficult consiste obtenir une image du fond. Dans le cas de scnes prsentanttrs peu de variabilit du fond (clairage constant, objets du fond statiques), limagede fond peut tre simplement obtenue en slectionnant manuellement une image quel-conque o aucun objet napparat. Les approches statistiques, plus robustes, consistent effectuer lapprentissage du fond au cours du temps afin de construire un modlemoyen de ce fond et dtre moins sensible sa variabilit. Lune des techniques lesplus abouties est lestimation paramtrique par noyaux des densits de probabilitdapparition des valeurs de pixels [7]. La figure 2.4.1 illustre la suppression de fondpar cette mthode.

Fig. 2.2 Suppression de fond

Elle se rvle cependant insuffisante lorsque les changements du fond sont tropbrutaux (changement important dclairage par exemple).

2.4.2 Dtection des objets mobiles par diffrence temporelle

La dtection de mouvement permet de trouver dans une squence dimages tousles objets mobiles. La mthode la plus intuitive consiste comparer les images suc-cessives et rechercher les pixels modifis. La mthode la plus simple consiste donc faire une soustraction entre images conscutives. Cette mthode peut tre modifieen considrant une fentre temporelle glissante sur laquelle on fait la dtection desobjets en mouvement, comme dans [8].

Comme les techniques de soustraction de fond, ces mthodes sont sensibles au bruitet aux changements dillumination. Il est galement possible de coupler la soustractionde fond et la diffrenciation temporelle [9].





page 15 sur 86


Les objets qui sont identifis comme mobiles par rapport la scne peuvent treclasss suivant des critres gomtriques de forme qui sont ensuite utiliss dans laphase de suivi [10].

Une revue de ces mthodes est donne dans [11].

2.4.3 Contours actifs

Un contour actif est un contour lastique qui sajuste aux formes dtectes dansune image. Il est caractris par une fonction dnergie qui fait apparatre les caract-ristiques gomtriques de la courbe et son interaction avec limage. Isard et Blake ontutilis le contour actif combin lalgorithme condensation [6]. Paragios et Deriche[12] ont formul le contour actif avec des level-sets pour le suivi dobjets en mouve-ment. En gnral, les contours actifs sont relativement dpendants de la qualit delinitialisation.

2.5 Suivi par Mean ShiftLalgorithme du Mean Shift est une mthode dterministe itrative consistant en

la recherche du maximum local dune fonction partir dune position donne par d-calage de la moyenne. Il permet par exemple de trouver les modes dune fonction dedensit [13]. Concrtement, cette mthode est en fait base sur la calcul dun vecteur(le vecteur de Mean Shift), dont la direction est celle de la plus forte pente ascendantede la densit. Il suffit donc de "suivre" ce vecteur pour aboutir au maximum local.En thorie, ce dernier est atteint lorsque le vecteur de Mean Shift ne fait plus varierla position de lobjet, cest--dire quand il est nul. Puisque lon travaille dans un es-pace discret, il convient de dfinir un certain seuil en-de duquel on considre que cevecteur est nul.Le principe intuitif de cette mthode peut tre visualis sur la figure 2.3.

Cet algorithme ncessite lutilisation dun noyau, tel que le noyau gaussien ou lenoyau dEpanechnikov 2, 3 . Les donnes sont pondres de manire dcroissante aufur et mesure que lon sloigne du centre.

Lalgorithme de suivi propos dans [2] (algorithme 1 ritrer chaque image)consiste optimiser le coefficient de Bhattacharyya calcul entre les histogrammescouleur de la rfrence de la cible candidate, par la procdure du Mean Shift.

2. Ce noyau est dfini comme suit: KE(x) ={

12C

1d (d+ 2)(1 ||x||2) si ||x|| < 1

0 sinono Cd est le volume de lhypersphre unit de dimension d (donc laire du cercle unit en dimension2).

3. le profil dun noyau K est une fonction k : [0; +[ R telle que K(x) = k(||x||2)







Algorithme 1 Procdure du MeanShiftEntres: modle q, position du centre de lobjet dans limage prcdente y0, profilk dune fonction noyau, seuil

Sorties: position estime du centre de lobjet dans limage courante y11. Calculer la distribution de la ROI ayant pour centre celui de lobjet limageprcdente:p(y0) = {pu(y0)}u=1...m2. Calculer la corrlation entre cette distribution et celle du modle:

(p(y0),q) =mu=1

qupu(y0)

3. Calculer les poids {wi}i=1...nh avec wi =mu=1

(b(xi),u)

qu

pu(y0)

4. Calculer le vecteur de MeanShift (ie. la nouvelle position de lobjet):

y1 =

nhi=1

xiwik(||y0 x1

h||2)

nhi=1

wik(||y0 x1

h||2)

5. Calculer la distribution de la ROI centre en la nouvelle position y1:p(y1) = {pu(y1)}u=1...m6. Calculer sa corrlation avec celle du modle: (p(y1),q) =

mu=1

qupu(y1)

tantque (p(y1),q) < (p(y0),q) fairey1 =

12(y0 + y1)

Calculer (p(y1),q)fin tantquesi ||y1 y0|| < alorsPasser limage suivante

sinony0 = y1 puis aller ltape 2

finsi





page 17 sur 86


Fig. 2.3 Itrations du MeanShift

Cette mthode est relativement efficace car le maximum est atteint le plus souventen quelques itrations seulement. Cependant, le principal problme de cette mthodeest le risque de tomber dans des maxima locaux qui ne sont pas toujours la solutionrecherche, ce qui provoque une drive du suivi.

2.6 Filtres baysiens rcursifsLa problmatique de suivi peut tre formule de manire gnrale comme lesti-

mation dun vecteur dtat contenant les paramtres de position, dchelle,... On notexk ce vecteur dtat linstant k. Lquation dvolution scrit de manire gnrale :

xk = fk(xk1,vk1) (2.7)

o fk est une fonction ventuellement non-linaire et vk1 le bruit de process. Il fautestimer xk partir dobservations zk.

zk = hk(xk,nk) (2.8)

o hk est une fonction ventuellement non-linaire et nk1 le bruit de mesure.Dans un cadre probabiliste baysien [14], cela revient estimer la probabilit a

posteriori p(xk|z1:k) partir dune quation de prdiction et dune quation de mise jour. Lquation de prdiction est une propagation temporelle, elle relie la probabilita priori p(xk|z1:k1) et la probabilit a posteriori p(xk1|z1:k1) linstant prcdent :

p(xk|z1:k1) =

p(xk|xk1) p(xk1|z1:k1) dxk1 (2.9)La mise jour partir des observations est ralise par :

p(xk|z1:k) = 1kp(zk|xk) p(xk|z1:k1) (2.10)

Le dtail de ces quations est donn en annexe C.







2.6.1 Le filtre de Kalman

Le filtre de Kalman est un filtre optimal pour rsoudre ce problme destimationdans les conditions suivantes [15]:

les probabilits a posteriori suivent une loi gaussienne, les bruits de process et de mesure sont gaussiens, hk est une fonction linaire de xk et vk1.

Ces conditions sont cependant trs restrictives, et ne sappliquent pas en gnral dansles situations relles de suivi dobjets dans un environnement bruit et en prsencedoccultations.

2.6.2 Le filtre particules

Le filtre particules est une mthode qui est ne dans les annes 1950. Elle nadabord pas rencontr un grand succs, mais sest considrablement dveloppe depuisune dizaine dannes, grce la puissance des calculateurs actuels qui permettent defaire tourner cet algorithme en temps rel. Le filtre particules, galement appelbootstrap, ou algorithme de condensation [6], est une mthode probabiliste capablede grer des densits de probabilits multimodales (donc les hypothses multiples),ce qui lui confre une grande robustesse. Elle permet dapprocher une distributionimpossible estimer directement au moyen dun ensemble dchantillons pondrs(les particules) qui la reprsente. Cet algorithme a t utilis en conjonction avec descontours actifs [6] ou encore pour le suivi de rgions bas sur les histogrammes couleur[3], [4].

[14] et [15] sont de trs bonnes rfrences pour aborder la thorie du filtre parti-cules. Le dtail de cet algorithme sera abord au chapitre suivant, puisque cest cettemthode de suivi qui a t retenue au laboratoire.





page 19 sur 86


Chapitre

3Suivi par filtrage

particulaire bas sur lacouleur




21


3.1 Principe du filtre particules pour le suiviNous avons vu dans le chapitre prcdent les fondements du filtrage particulaire.

Nous allons dans cette section prciser son fonctionnement dans le cadre du suividobjets en 2-D. Dans notre cas, le vecteur dtat contient la position de la cible etson chelle dans les deux dimensions

xk = {x,y,hx,hy}k (3.1)

Lquation de mise jour de la position de lobjet x linstant k note xk enfonction des observations recueillies aux instants prcdents notes z1,z2, . . . ,zk2,zk1est donne par lquation 2.10. Il nous faut donc estimer la densit conditionnellep(zk|xk) (vraisemblance). Cette probabilit peut tre approche par un ensemble deN chantillons, les particules notes {s1,...,sN}. Chaque particule est pondre par

wi =pz(s

i)Nj=1 pz(s

j)(3.2)

avec pz(x) = p(z|x). La vraisemblance est donne par la similarit entre le candidat valuer et le modle de rfrence. Autrement dit, les particules ayant le poids le plusimportant sont les solutions les plus probables. Pour estimer la probabilit a poste-riori p(xk|z1:k), il suffit donc de faire un tirage alatoire selon la distribution discrteconstitue par le poids des particules. A chaque itration, les diffrentes valeurs pos-sibles du vecteur dtat sont prdites par lquation 2.9. Pour raliser ce calcul, on adonc besoin de connatre p(xk|xk1) qui reprsente le modle dynamique de lobjet.Le rsultat du suivi est la moyenne des particules tires selon la distribution de leurpoids. Il existe diffrentes versions du filtre particules [15]. Nous allons considrerpour simplifier qu chaque nouvelle image, on part du rsultat du suivi linstantprcdent pour diffuser les particules.

3.2 Implmentation du filtre particules bas sur leshistogrammes couleur

Nous nous basons sur lalgorithme propos par Perez et al dans [3]. La premiretape consiste donc dfinir un modle, manuellement ou partir dun algorithme dereconnaissance, rcuprer sa position sur la premire image de la squence, puis construire son histogramme. Les histogrammes sont valus dans des zones rectangu-laires de limage, qui sont en ralit des ellipses en raison de lutilisation dun noyaude pondration (voir 2.5).

3 . Suivi par filtrage particulaireDRT LIST DTSI




page 23 sur 86


3.2.1 Caractristiques visuelles

A partir de la problmatique dfinie dans la section 2.1, le choix des caractris-tiques utilises pour le suivi sest port sur la caractristique la plus simple et la plusbas niveau, la couleur, pour des raisons de simplicit et de rapidit de lalgorithmeLespace retenu est le HSV (voir annexe A), qui est le plus intuitif pour ltre humain,contrairement au RGB correspondant lespace sur lequel sont construits nos moni-teurs.Lespace HSV va permettre au suivi daugmenter sa robustesse, par rapport au RGB,face aux effets de lumire et dombrage, trs frquents dans les trains (de par les fe-ntres omniprsentes dans les rames). En effet, il suffira de ne pas prendre en comptedans lhistogramme la valeur de luminosit, mais uniquement celles de la teinte et lasaturation.En revanche, lorsque la ROI possdera une valeur de saturation ou de luminosit tropfaible, la valeur de la teinte ne sera pas pertinente car cette dernire sera en fait quasiinexistante. En effet, les valeurs de gris ntant pas codes sur laxe des H, dans cecas, le mieux sera de prendre en compte dans lhistogramme la valeur de la luminosit(en esprant donc que celle-ci ne change pas trop brutalement dans la vido).Dans notre algorithme, les histogrammes seront donc calculs dans lespace HSV,chaque pixel prenant donc sa valeur soit dans H*S, soit dans V, conformment cequi est propos dans [3].Le nombre de classes de lhistogramme sera fix ultrieurement partir de tests.

3.2.2 Distance entre histogrammes

Pour quantifier la ressemblance entre deux objets, il nous faut dfinir une fonctionde distance.Cette distance peut par exemple prendre la valeur 0 pour signifier que la cible et lemodle sont totalement dcorrls, et la valeur 1 quand la cible et le modle sontparfaitement identiques.La pseudo-distance de Bhattacharyya est une mesure tout fait pertinente pour lacomparaison dhistogrammes. Elle est largement utilise dans le contexte du suivi [2],[3].Le coefficient de Bhattacharyya est dfini comme suit:

(y) =mu=1

qupu(y)

Gomtriquement, ce coefficient reprsente le cosinus de langle form par les vecteursunits m-dimensionnels (

p1,...,

pm)

et (q1,...,

qm)

Etant donn les proprits du cosinus entre deux vecteurs, ce coefficient peut tre vucomme une mesure de la corrlation entre ceux-ci. En effet, deux vecteurs confondus





3 . Suivi par filtrage particulaire


sont considrs comme totalement corrls, deux vecteurs orthogonaux comme tota-lement dcorrls.

On dfinit ensuite la distance 1 base sur ce coefficient de Bhattacharyya ainsi (lapseudo-distance de Bhattacharyya ne vrifiant pas lingalit triangulaire):

d(y) =1 (y)

Cette distance est bien inversement proportionnelle la corrlation entre les deuxobjets.

3.2.3 Modle dynamique

Contrairement [3], nous navons aucun a priori sur le mouvement des personnes,donc nous utilisons un modle de mouvement dordre 0 en labsence de modle demouvement suffisamment raliste pour reprsenter la trajectoire de personnes pouvantavoir des mouvements complexes (changement de direction, arrt....). Autrement dit,les particules seront diffuses dans un voisinage de la solution trouve ltape prc-dente. Cependant, afin de capturer les mouvements rapides, nous utiliserons ltapede prdiction un bruit gaussien de matrice de covariance suffisamment grande :

xk = xk1 + vk1, v N (0,) (3.3)

3.2.4 Rsum de lalgorithme

Pour chaque particule, on calcule son histogramme, puis sa corrlation au modlepar la distance de Bhattacharyya de son histogramme celui du modle, puis on luiassigne un poids wi correspondant donc p(zk|xk) proportionnelle cette distance.Ensuite, daprs le principe de lchantillonnage pondr pour les mthodes de Monte-Carlo, on ralise un nouveau tirage parmi ces particules, pondr par leur poids (ie.plus une particule possde un poids fort, plus elle a de chances dtre tire).On ralise ensuite la moyenne pondre(que ce soit au niveau de la position du centreou des dimensions si une mise jour de ces dernires est effectue) des particulesnouvellement tires, pour calculer la nouvelle position (et donc ventuellement lesnouvelles dimensions) de lobjet.

1. d est une distance de K dans R si et seulement si:i) x,y K,d(x,y) 0 (positive)ii) x,y K,d(x,y) = 0 x = yiii) x,y K,d(x,y) = d(y,x) (symtrique)iv) x,y,z K,d(x,y) + d(y,z) d(x,z) (ingalit triangulaire)





page 25 sur 86


Lalgorithme 2 prsente en pseudo-code cet algorithme de filtrage particulaire de baseimplment au laboratoire.

3.2.5 Performances

Sur une machine quipe dun processeur Intel Xeon 3.06Ghz, de 1.5Go de mmoirevive et dune carte graphique Nvidia Quadro FX 500, cet algorithme tourne environ 10/15 images par seconde pour le suivi dune unique cible (la taille de la cibleninfluant pas sur les performances grce la grille dchantillonnage, voir 3.3.1) aveclutilisation de 200 particules. Pour le suivi de 5 cibles en parallle, le nombre dimagestraites par seconde et denviron 6 8.

3.3 Contributions : amliorations apportes au filtre particules

Dans cette section, nous prsentons les diffrentes amliorations que nous avonsimplmentes dans le filtre particules dcrit prcdemment.

3.3.1 Grille dchantillonnage

En nous basant sur [3], nous avons implment une contribution non pas pouramliorer le suivi, mais pour rduire le temps de calcul.Le principe est simple: pour garder un temps dexcution constant quelque soit lataille de la cible suivre, on va calculer lhistogramme de cette dernire non pas enprenant en compte tous ses pixels, mais uniquement un sur quatre, un sur seize, etc. . .On va en fait calculer un facteur dchantillonnage proportionnel la taille de la bote.Nous avons dtermin empiriquement la relation suivante:

facteur echantillonnage =d

30+ 1

d tant le minimum de la largeur et de la longueur de la bote dfinissant la ROI.

Par exemple, pour une bote de longueur 28 pixels et de largeur 35 pixels, seuls 1/4des pixels seront pris en compte pour la construction de lhistogramme.

3.3.2 Mise jour du modle

Ce problme est complexe car il faut trouver le bon compromis pour que le pro-gramme effectue une mise jour qui doit tre sensible aux changements dapparencede lobjet mais qui ne doit pas tenir compte des erreurs de suivi (risque de drive).







Algorithme 2 Filtre particulesEntres: Nombre de cibles suivre n; Vecteur dtat de chaque cible j (dfini ma-nuellement ou automatiquement) dans limage prcdente xj0 contenant notammentyj0 centre de j; Nombre de particules nbpar; Variance V

Sorties: Vecteur dtat de chaque cible j dans limage courante xj1si premire image alorspour tout cible j faireCalcul de son histogramme qj de rfrence

fin pourfinsipour tout image fairepour tout cible j faire1. Tirage des particules dans limage suivant une distribution gaussienne decentre yi0 et de variance Vpour tout particule i faireConstruction de son histogramme pjiCalcul de son poids wji = dBhattacharyya(p

ji ,qj)

fin pour2. Re-tirage des particules pondr par leur poids wji3. Calcul et mise jour du vecteur dtat estim de lobjet par moyenne des

particules prcdemment re-tires, pondre par leur poids: xj1 =1

nbpar

nbpari=0

wjixjpi

o xjpi est le vecteur dtat de la particule ifin pour

fin pour





page 27 sur 86


Une tentative dimplmentation fut base sur une mise jour basique du modlecomme indiqu dans [16] et [17]: chaque image, lhistogramme du modle est recal-cul par la formule:

qt = qt1 + (1 )pEto qt est lhistogramme du modle au temps t, pEt est lhistogramme de la positionestime de lobjet linstant t et un coefficient de pondration.Les rsultats ont montr que la cible finit par sloigner irrmdiablement de lobjetquelle est cense suivre.Dautres essais, dans lesquels le modle tait mis jour uniquement si lapparencede lobjet changeait dans de faibles proportions (on considre que lalgorithme sest"perdu" dans le cas contraire), ou linverse changeait suffisamment (on considreici que la mise jour nest justifie que si lapparence a chang de manire notable,comme dcrit dans [17]), nont pas montr non plus de rsultats concluants.

3.3.3 Pr-traitement des images

Le critre de similarit que nous utilisons se base sur la distance entre deux histo-grammes couleur. De ce fait, malgr lutilisation de lespace couleur HSV qui permetde dcorrler en partie linformation de couleur de la luminosit, lalgorithme risquedtre sensible linhomognit de lclairement de la scne. Il peut alors tre int-ressant dapporter une correction locale du contraste de limage par un traitement.Pour cela, nous avons mis en place lalgorithme Contrast Limited Adaptive HistogramEqualization (CLAHE) disponible dans [18].Cette technique permet de rehausser localement le contraste de limage, ce qui peuttre trs utile pour des images du type de celle de la figure 3.1, qui souffre duneinsuffisance de contraste.

Fig. 3.1 Image trop homogne

La mthode la plus basique pour accentuer le contraste dune image est lgalisa-tion de son histogramme.Cette mthode consiste tout simplement modifier lhistogramme de telle manire que







chaque classe de celui-ci possde le mme nombre de pixels que les autres. Malheu-reusement cette technique peut selon les cas produire un rsultat pire que loriginal,en accentuant le bruit ou les rgions du fond qui ne nous intressent pas (si la ROIne reprsente quune infime partie de limage par exemple) comme sur la figure 3.2.

Fig. 3.2 Image dont lhistogramme a t galis

Pour pallier ce problme, on peut utiliser le mthode AHE (Adaptive HistogramEqualization), qui effectue en fait une galisation dhistogramme, mais localement.Pour chaque pixel, on considre un voisinage (par exemple une fentre de 8x8) surlequel on effectue une galisation dhistogramme basique. Aprs calculs, on attribue chaque pixel sa nouvelle valeur. Ici, on ne prend donc pas en compte lintgralit delimage pour calculer la nouvelle valeur dun pixel, mais uniquement son voisinage.Cette technique, bien que meilleure quune galisation basique, peut considrablementaccentuer les bruits du fond.Ceci est d au fait que la taille du voisinage est la mme pour chaque pixel, quecelui-ci appartienne une zone homogne ou non. Dans une zone faible contraste,lgalisation va donc trs fortement accentuer les diffrences, mme minimes, et doncpar exemple, faire ressortir le bruit dun fond uni comme sur la figure 3.3.

Fig. 3.3 AHE applique sur limage

Il existe donc une mthode, nomme CLAHE, qui permet de dcouper limage enrgions dintrt comme le ferait une segmentation basique. Lgalisation est ensuite





page 29 sur 86


Fig. 3.4 CLAHE applique sur limage

applique sur chacune de ces rgions. Les zones homognes (ie. ou le contraste est trsfaible) sont identifies dans lhistogramme par des pics (beaucoup de pixels avec desvaleurs extrmement proches). Pour viter que ces zones ne soient trop rehausses etlaissent apparatre du bruit non dsir, on attribue lhistogramme une valeur maxi-male pour toutes ses classes. Si une de celles-ci possdent une valeur suprieure cemaximum, on lui attribue comme valeur ce maximum, et on redistribue de manireuniforme sur tout lhistogramme les pixels qui ont t retranchs.Ainsi, le niveau de dtails apparents ne sera pas suraccentu pour les rgions homo-gnes comme le montre lexemple de la figure 3.4.

On peut voir sur la figure 3.5 un exemple dune image tire dune squence de testo lutilisation du CLAHE est particulirement pertinente.

Image originale Image dont le contrastea t rehauss par CLAHE

Fig. 3.5 Effet du CLAHE sur une image dune squence de test







3.3.4 Dcoupage spatial

La premire tape de lamlioration du filtre particule fut de raliser un dcou-page des ROI, ce qui permet de rajouter de linformation spatiale (mais qui entranegalement malheureusement un lger surcot de calcul) comme cela est suggr dans[3]. Les modifications apportes aux programmes permettent deffectuer un dcoupagergulier des rgions dont on veut calculer les histogrammes.Chaque sous-rgion dispose alors de son propre histogramme, et les comparaisons sefont donc sous-rgions sous-rgions.Comme nous le verrons dans le chapitre suivant, les rsultats sont trs probantspuisque lon observe une bien meilleure stabilit dans le suivi, notamment des per-sonnes peu animes.Lamlioration apporte par ce dcoupage apparat trs clairement sur le cas de syn-thse que nous avons construit: deux carrs dcoups chacun en quatre rgions ho-mognes (sous-carrs de couleur unie) se dplacent dans le plan. Pour le carr quenous voulons suivre, nous faisons varier assez modrment la couleur de chacune deses rgions homognes, quant lautre carr, nous ne faisons pas varier ses couleurs,mais nous permutons la position de ses rgions homognes.Les rsultats peuvent tre visualiss sur les figures 3.6 et 3.7.

Linconvnient du dcoupage apparat lorsque lobjet suivi effectue une rotationsur lui-mme. En effet, dans ce cas, les sous-rgions des candidats ne vont plus cor-respondre aux sous-rgions du modle.Le pseudo-code de cette contribution se trouve dans lalgorithme 3.





page 31 sur 86


Algorithme 3 Filtre particules avec dcoupage spatial des ROIEntres: Nombre de cibles suivre n; Vecteur dtat de chaque cible j (dfinimanuellement ou automatiquement) dans limage prcdente xj0 contenant notam-ment yj0 centre de j; Nombre de particules nbpar; Variance V ; Nombre de rgions enlesquelles sont dcoupes les ROI nbdec

Sorties: Vecteur dtat de chaque cible j dans limage courante xj1si premire image alorspour tout cible j fairepour tout rgion r faireCalcul de son histogramme qjr de rfrence

fin pourfin pour

finsipour tout image fairepour tout cible j faire1. Tirage des particules dans limage suivant une distribution gaussienne decentre yi0 et de variance Vpour tout particule i fairepour tout rgion r faireConstruction de son histogramme pjir

fin pour

Calcul de son poids wji =1

nbdec

nbdecm=0

dBhattacharyya(pjir,qjr)



nbpar

nbpari=0

wjixjpi


fin pour







Image 1 Image 5

Image 6 Image 18

Fig. 3.6 Carr A: lgre variation de couleur pour chacune de ses 4 rgionsCarr B: aucune variation de couleur, mais changements de position de ses rgionsNous constatons lchec du suivi du carr A en labsence de dcoupage spatial

Image 1 Image 5

Image 6 Image 18

Fig. 3.7 Suivi correct du carr A avec dcoupage spatial





page 33 sur 86


3.3.5 Mise jour de lchelle

Lorsque une personne se rapproche ou sloigne de la camra, la rgion dintrtla caractrisant varie bien videmment de taille, do la ncessit de raliser une mise jour de lchelle du modle.

Le premier test, bas sur une mthode propose dans [2], propose de tirer les par-ticules avec trois chelles diffrentes.On tire un tiers des particules lchelle dorigine, un autre tiers 10% plus grandesque le modle, et enfin un autre tiers 10% plus petites que le modle.On retient la particule ressemblant le plus au modle (ie. possdant le plus haut co-efficient de Bhattacharyya), on lui applique lchelle de lobjet linstant prcdentque lon fait varier seulement de 1% (dans le sens induit par la particule) pour vitertout changement trop brusque.

La seconde possibilit est de tirer des chelles selon une distribution gaussienne 2centre en lchelle du modle et dcart-type ( dterminer empiriquement), cou-pe au-del dune certaine valeur M (et en-de de -M), pour viter des changementsdchelle trop brutaux, comme le montre la figure 3.8.

Si la cible devient trop petite (cela na pas de sens de suivre un objet de seulementquelques pixels, ses caractristiques tant trop peu nombreuses), il convient dessayerde raccrocher la cible en tirant des particules avec une chelle plus leve. Dans ce cas,lalgorithme augmente lcart-type de la distribution, et la coupe en-dessous de 0et au-dessus dune nouvelle valeur de M suffisamment grande, comme sur la figure 3.9.

Cette distribution signifie que lon ne distribue plus seulement les particules danslespace des coordonnes (x,y) de limage, mais en plus dans lespace des chelles.Pour paver au mieux lespace global dans lequel les particules sont tires, il fautaugmenter leur nombre ce qui accrot srieusement les cots de calcul.Pour pallier cet inconvnient, il paraissait intressant dutiliser une mthode quasi-alatoire en lieu et place de celle pseudo-alatoire comme propos dans [19]. En effet,le tirage quasi-alatoire permet de tirer des nombres en n dimensions de manire paver au mieux lespaceLalgorithme 4 prsente le pseudo-code du filtrage particulaire accompagn de cettecontribution.

2. Une variable alatoire X desprance et dcart type suit une loi normale gaussienne si sadensit de probabilit est:f(x) = 1

2pie

12 (

x )

2

On a notamment les proprits:p(X [ ;+ ]) 0,68 et p(X [ 3;+ 3]) 0,997







Algorithme 4 Filtre particules avec changement dchelleEntres: Nombre de cibles suivre n; Vecteur dtat de chaque cible j (dfini ma-nuellement ou automatiquement) dans limage prcdente xj0 contenant notammentyj0 centre de j; Nombre de particules nbpar; Variance V ; chelle de rfrence de jechj = 1; Variance Ve


fin pourfinsipour tout image fairepour tout cible j faire1. Tirage des particules dans limage suivant une distribution gaussienne decentre yi0 et de variance V , et dans la dimension des chelles avec une distribu-tion gaussienne de centre ech et de variance Vepour tout particule i faireConstruction de son histogramme pjiCalcul de son poids wji = dBhattacharyya(p

ji ,qj)



nbpar

nbpari=0

wjixjpi

o xjpi est le vecteur dtat de la particule i; et de lchelle courante:

echj = 1nbpar

nbpari=0

wji echjpi o ech

jpi est lchelle de i

fin pourfin pour





page 35 sur 86


Fig. 3.8 Distribution normale demoyenne , dcart-type et tronqueen-de de -M et au-del de M

Fig. 3.9 Distribution normale demoyenne , dcart-type et tronqueen-de de 0 et au-del de M

3.3.6 Combinaison avec le Mean Shift

Meanshift appliqu au rsultat du filtre particules

Dans ce programme, pour chaque image de la vido, on applique lalgorithmedu MeanShift au rsultat donn par le filtre particules. On espre ainsi affiner laposition de la cible en cherchant un maximum local du coefficient de Bhattacharyya,tant donn que le filtre particules nous renvoie une moyenne pondre de positionsde botes.Lalgorithme 5 nous prsente ce pseudo-code.

Meanshift appliqu aux particules

Ici, lalgorithme repose sur un filtre particules standard, mais dans lequel onapplique le MeanShift sur les particules tires.On espre ainsi quune grande partie des particules, censes atteindre leur maximumlocal grce au MeanShift, vont atteindre des modes de la fonction de densit de pro-babilit, donc des positions intressantes.Ainsi, le nombre de particules ncessaires au filtre devrait tre moindre pour arriverau mme rsultat quun filtre particules basique.Le pseudo-code de cette contribution se trouve dans lalgorithme 6.







Algorithme 5 Filtrage particulaire suivi dun MeanShiftEntres: Nombre de cibles suivre n; Vecteur dtat de chaque cible j (dfini ma-nuellement ou automatiquement) dans limage prcdente xj0 contenant notammentyj0 centre de j; Nombre de particules nbpar; Variance V



ji ,qj)



nbpar

nbpari=0

wjixjpi

o xjpi est le vecteur dtat de la particule i4. Application de lalgorithme du MeanShift (voir algorithme 1) avec commeentres le modle qj et la position du centre de lobjet ltape prcdente yj1(calcule dans 3.), puis mise jour de xj1 avec le rsultat du MeanShift

fin pourfin pour





page 37 sur 86


Algorithme 6 Filtre particules avec application du MeanShift sur les particulesEntres: Nombre de cibles suivre n; Vecteur dtat de chaque cible j (dfini ma-nuellement ou automatiquement) dans limage prcdente xj0 contenant notammentyj0 centre de j; Nombre de particules nbpar; Variance V



ji ,qj)

Application de lalgorithme du MeanShift (voir algorithme 1) i, avec commeentres le modle qj et la position du centre de lobjet ltape prcdenteyi centre de i, puis mise jour de yi avec le rsultat du MeanShift



nbpar

nbpari=0

wjixjpi


fin pour







Chapitre

4

valuation des algorithmesde suivi implments




39


4.1 Ralisation dune vrit terrainPour valuer la prcision dune mthode de suivi, il faut disposer dun critre

quantitatif. Dans un premier temps, nous avons observ la variation du coefficient deBhattacharyya au cours du temps sur des squences de rfrence, et nous avons essayde trouver une corrlation entre cette variation et la qualit du suivi obtenu. Dans denombreux cas, on observe un chec du suivi alors que le critre de Bhattacharyya estlev (lalgorithme trouve un candidat qui nest pas lobjet suivi mais qui prsente lesmmes caractristiques visuelles), et inversement (lobjet a chang dapparence).

Une manire plus rigoureuse de raliser lvaluation consiste tablir une vritterrain (ground truth) sur des squences de rfrence, et destimer la distance entre lesrsultats du suivi et cette vrit terrain, pour chacune des versions de lalgorithme. Laconstitution de la vrit terrain consiste, image par image, pour chacune des vidos detests, dfinir manuellement les botes englobantes des objets suivis, comme lillustrela figure 4.1.

Fig. 4.1 Dfinition de la bote pour le suivi du casque

4.2 Dfinition dune mtrique utilise pour valuerles algorithmes

Afin dvaluer les performances dun algorithme, il faut dfinir une distance per-mettant de mesurer lcart entre les rsultats de lalgorithme et la vrit terrain.Or, pour notre mthode de suivi, son efficacit est juge en fonction de la position etde la taille de la bote cense reprsenter lobjet.Il a donc fallu dfinir une distance entre deux rectangles dans le plan.

4 . valuation des algorithmes de suivi implmentsDRT LIST DTSI




page 41 sur 86


Une premire pseudo-distance que nous avons utilise, base sur une mesure derreurquantifie dans [20], tait dfinie ainsi:

d(BA,BV ) =A((BA\BV ) (BV \BA))

A(BV )o \ est loprateur "priv de", A est loprateur Aire, BA la bote sortie par lalgo-rithme et BV la bote de la vrit terrain.Cette pseudo-distance a lavantage de prendre en compte et la diffrence de taille etla diffrence de position des botes quand celles-ci possdent une partie commune,comme le montre la figure 4.2.Cependant, elle ne prend pas en compte lloignement des botes quand celles-ci nontplus de partie commune, et nest pas symtrique (par exemple, la distance peut de-venir trs grande si la bote de la vrit terrain, et non celle de lalgorithme, devienttrs petite, comme nous pouvons le voir sur la figure 4.3).

Fig. 4.2 La distance est caractrisepar la division de la surface grise par lasurface raye (bote de la vrit terrain)

Fig. 4.3 Asymtrie de la distance:cette dernire peut se rvler relative-ment petite si la bote de la vrit ter-rain est la grise (surface grise divisepar la surface grise+rouge), ou bien trsgrande si la bote de la vrit terrain estla rouge (surface grise divise par sur-face rouge)

Dans un second temps, nous avons donc relanc les tests en dfinissant une distanceplus satisfaisante, base sur une dfinition trouve dans [21].





4 . valuation des algorithmes de suivi implments


Tout dabord, notons S le segment reliant le centre de BA au centre BV , s1 le pointdintersection de S avec BA et s2 le point dintersection de S avec BV .Alors nous dfinissons:

d(BA,BV ) =

{1 2A(BAT

BV )A(BA)+A(BV ) si A(BA

BV ) 6= 0

1 + log((xs1 xs2)2 + (ys1 ys2)2) sinon

Cette pseudo-distance (elle ne vrifie en effet pas lingalit triangulaire) est compriseentre 0 et 1 si les deux botes ont une partie commune et dpend de la taille de cettedernire par rapport la taille des deux botes. Ainsi lloignement et la diffrence detaille sont pris en compte tel que le montre la figure 4.4.Si les botes nont pas de parties communes, nous prenons le logarithme en base 10de la distance euclidienne entre les deux botes pour rendre compte de lloignementde celles-ci tout en gardant des valeurs raisonnables (infrieures 10), laquelle nousrajoutons 1 pour assurer la continuit de la fonction. Ceci est illustr par la figure 4.5.

Fig. 4.4 La distance est caractrisepar: surface rouge 2

surface grise + (surface rouge 2)

Fig. 4.5 La distance est ici dfinie parla distance euclidienne entre les botes,cest--dire le trait bleu

Aprs vrifications visuelles, cette pseudo-distance semble renseigner tout faitconvenablement sur la prcision des algorithmes.

4.3 Rsultats exprimentauxDans la suite du chapitre, o nous prsenterons les rsultats des tests, il est noter

que les botes de la Vrit Terrain seront en jaune sur les captures dcran des vidos.





page 43 sur 86


Nous allons maintenant passer en revue les rsultats des diffrents tests des am-liorations apportes au filtre particules.Les scores sont en fait ici la distance sparant les botes des algorithmes avec cellesde la Vrit Terrain, le score dun algorithme est donc inversement proportionnel saprcision.

4.3.1 Ajout de linformation spatiale par dcoupage

Le fait dajouter de linformation spatiale apporte clairement de la robustesse ausuivi.De manire gnrale, on vite loscillation des cibles autour de lobjet cens tre suivi,on vite galement des dcrochages complets. Sur les 12 cibles de test, 6 ont t bienmieux suivis avec ce dcoupage de la ROI.

Analysons deux exemples, ceux des figures 4.6 et 4.7:Sur les images de la figure 4.6, on voit clairement que le suivi est bien plus prcis

avec un dcoupage spatial. Ceci est notamment d au fait que les objets suivis nechangent ici pas dapparence, le dcoupage spatial permet donc de mieux localiser lesobjets.Dans la squence de la figure 4.7, le suivi est globalement plus fin sur toutes les cibles,et vite le dcrochage pour deux dentre elles, notamment pour la cible dont nousavons affich le score). En effet, la vido ntant pas de trs bonne qualit, les visagesse ressemblent beaucoup, ce qui explique que lalgorithme puisse saccrocher sur unmauvais visage au gr des changements de luminosit ou cause doccultations. Maisle dcoupage permet dacqurir des informations sur le visage (par exemple cheveuxdans la partie suprieure, peau et bouche dans la partie infrieure, orientation duvisage, etc. . . ), et permet donc une meilleure identification de celui-ci.

Cette amlioration a t la premire tre implmente. Les rsultats sont incon-testablement meilleurs, voila pourquoi elle a t garde pour les tests suivants.

4.3.2 Mise jour de lchelle

Dans le cas des squences tournes dans la rame de train, les changements dchelledans laxe optique peuvent tre importants comme le montre lexemple de la figure4.8.

Cette dernire montre lchec du suivi taille fixe. En revanche, en distribuant lesparticules galement dans lespace des chelles suivant une distribution gaussienne, lesuivi est satisfaisant.

Des tests ont t effectus pour savoir laquelle des mthodes de tirage sur trois chelles





4 . valuation des algorithmes de suivi implments


Sans dcoupage Avec dcoupage

En bleu: Score de "la chvre" sans dcoupage / En rose: Avec dcoupage

Fig. 4.6 Extrait de la squence "mobile": Amliorations apportes par le dcoupagespatial

ou avec distribution gaussienne tait la meilleure, mais il est trs difficile de concluretant donn que chaque mthode est meilleure dans certains cas et pas dautres. Nousavons tout de mme pu noter que la mthode de tirage sur trois chelles est notable-ment meilleure dans deux cas sur douze, et celle de la distribution gaussienne danstrois cas sur douze.Nous avons donc gard limplmentation de la distribution gaussienne pour la suitedes tests. Nous avons ensuite cherch la variance optimale de la distribution gaus-sienne qui tire lchelle des particules. Les diffrents essais ont montr quune variancede 7 pixels produit globalement les meilleurs rsultats.Il faut galement garder lesprit le ct forcment ngatif du changement dchelle:pour le suivi des objets de taille fixe, le rsultat ne peut tre meilleur. Et dans denombreux cas, le suivi se rvle nettement moins bon, comme par exemple celui de lafigure 4.9, o la balle est partiellement occulte.

Ce problme est en partie rsolu en augmentant le nombre de particules distribues;





page 45 sur 86


Sans dcoupage Avec dcoupage

En bleu: Score de "lhomme en haut gauche" sans dc

Documents

Suivi de personnes par filtrage particulaire pour la vidéo-surveillance