88
DEA PHOTONIQUE , IMAGE ET CYBERNETIQUE Mémoire de stage de DEA THOMSON MULTIMEDIA R&D FRANCE 1, avenue Belle Fontaine – BP 19 - 35511 CESSON-SEVIGNE Cedex Tél. (33) 02 99 27 30 00 Fax. (33) 02 99 27 30 01 Durée du stage : du 05 Mars au 31 Août 2001 Indexation vidéo orientée objet : Combinaison des techniques de segmentation d’images en régions avec l’extraction des descripteurs de couleur Responsable de stage : M. Bertrand CHUPEAU Tuteur : Pr. Fabrice HEITZ Nesrine CHEHATA

Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Embed Size (px)

Citation preview

Page 1: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

DEA PHOTONIQUE , IMAGE ET CYBERNETIQUE

Mémoire de stage de DEA

THOMSON MULTIMEDIA R&D FRANCE 1, avenue Belle Fontaine – BP 19 - 35511 CESSON-SEVIGNE Cedex Tél. (33) 02 99 27 30 00 Fax. (33) 02 99 27 30 01 Durée du stage : du 05 Mars au 31 Août 2001

Indexation vidéo orientée objet : Combinaison des techniques de segmentation

d’images en régions avec l’extraction des descripteurs de couleur

Responsable de stage : M. Bertrand CHUPEAU

Tuteur : Pr. Fabrice HEITZ

Nesrine CHEHATA

Page 2: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 2 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Remerciements

Je remercie tout particulièrement mon maître de stage, M. Bertrand Chupeau qui a su me guider et m’orienter grâce à ses précieux conseils tout au long de mon stage. Je tiens également à remercier M. François Le Clerc, M. Lionel Oisel et Melle. Ewa Kijak pour les nombreux renseignements et aides qu’ils m’ont apportés.

J’adresse également toute ma reconnaissance aux ingénieurs, à l’ensemble des techniciens et à la secrétaire du laboratoire « Advanced Visual Processing » pour leur bonne humeur quotidienne et la bonne ambiance qui régnait dans le laboratoire.

Enfin, mes remerciements s’adressent à toutes les personnes, qui de près ou de loin, m’ont permis de réaliser un stage riche en enseignements.

Page 3: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 3 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Page 4: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 4 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Sommaire

Table des figures................................................................................................ 7

Introduction .............................................................................................................. 8

Présentation du stage .................................................................................... 9 I. CADRE DU STAGE ........................................................................................................ 9

I.1.Thomson Multimédia ................................................................................9 I.2. Thomson Multimédia R&D France à Rennes .........................................10 I.3. Le laboratoire Advanced Visual Processing (AVP) ................................10

II. CAHIER DES CHARGES ............................................................................................. 11 III. ANALYSE DU PROBLEME......................................................................................... 12

III.1. Recherche d’images dans leur globalité ...............................................12 III.2. Recherche d’images par requête partielle.............................................13

IV. ORGANISATION DU TRAVAIL............................................................................... 14

Etat de l’art.............................................................................................................. 15 I. LE DESCRIPTEUR DE COULEURS DOMINANTES.................................................... 15

I.1. Choix du descripteur ..............................................................................15 I.2. Les techniques de regroupement ou « clustering »..................................15

I.2.1) La quantification vectorielle.................................................................................. 15 I.2.2) Algorithme du K-means ........................................................................................ 16

I.3. Le descripteur et les métriques associées..............................................16 I.3.1) Fonction quadratique de distance.......................................................................... 17 I.3.2) Fonction quadratique de distance améliorée ......................................................... 18 I.3.3) Améliorations possibles de la métrique : contenu spatial ..................................... 19

II. ALGORITHMES DE SEGMENTATION EN REGIONS................................................ 20

II.1. Critère d’homogénéité couleur ..............................................................20 II.1.1) Fusion de régions: RSST( Recursive Shortest Spanning Tree) .......................... 20 II.1.2) Morphologie mathématique : Le partage des eaux ou « watershed »................. 21

II.2. Critère d’homogénéité mouvement .......................................................22 II.2.1) Estimation du mouvement dominant ................................................................. 22 II.2.2) Segmentation couleur suivie d’une fusion de régions selon un......................... 23 critère d’homogénéité mouvement [Chupeau 00].............................................. 23

Page 5: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 5 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

III. COMBINAISON DES TECHNIQUES DE SEGMENTATION..................................... 24 AVEC LE DESCRIPTEUR COULEUR................................................................................ 24

III.1. Régions fixées : Quadrillage de l’image...............................................24 III.1.1) Principe............................................................................................................... 24 III.1.2) Métriques globales.............................................................................................. 24

III.2. Segmentation de l’image en régions ....................................................26 III.2.1) Application de requête globale ........................................................................... 26

Description technique................................................................................ 29 I. DESCRIPTION DES REALISATIONS............................................................................ 29

I.1. Description des méthodes utilisées .........................................................29 I.1.1) Les couleurs dominantes ....................................................................................... 29 I.1.2) Les métriques ........................................................................................................ 30

I.2. Description des séquences de tests .........................................................30 I.3. Principe du programme de validation .....................................................31 I.4. Critères d’évaluation ..............................................................................34

I.4.1) Interface graphique de validation.......................................................................... 34 I.4.2) Critères numériques d’évaluation.......................................................................... 34 I.4.3) Complémentarité des deux méthodes.................................................................... 35

Résultats...................................................................................................................... 36 I. LE DESCRIPTEUR DE COULEURS DOMINANTES................................................... 36

I.1. Influence de la précision de la quantification..........................................36 I.2. Comparaison des deux métriques élémentaires.......................................37

II. LE DESCRIPTEUR COULEURS DOMINANTES OBTENU AVEC ............................ 38 UN QUADRILLAGE DE L’IMAGE................................................................................. 38

II.1. Influence de la taille des blocs et du nombre de couleurs dominantes ..38 II.2.Influence de la métrique globale sur les critères d’évaluation.................40

II.2.1) Détermination des coefficients de pondération de la métrique............................ 40 globale bloc à voisins........................................................................................... 40 II.2.2) Comparaison des deux métriques globales .......................................................... 41

II.3. Influence de la mesure de confiance sur les critères ..............................41 d’évaluation..................................................................................................41 II.4. Bilan du descripteur local utilisé ...........................................................43 II.5. Comparaison avec le descripteur global ................................................43

Page 6: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 6 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

III. LE DESCRIPTEUR COULEURS DOMINANTES OBTENU...................................... 47 AVEC UNE SEGMENTATION DE L’IMAGE EN REGIONS ........................................... 47

III.1. Comparaison des différents algorithmes de segmentation ....................47 III.2. Application de requête globale : La métrique globale ..........................48

III.2.1) Le seuil de fusion au niveau du RSST................................................................ 48 III.2.2) Compromis entre le seuil de fusion au niveau du RSST et le seuil.................... 48 de similarité entre régions ................................................................................... 48 III.2.3) Amélioration de la métrique globale .................................................................. 49 III.2.4) Résultats de la métrique globale améliorée ........................................................ 53

III.3. Application de requête partielle ...........................................................54 III.3.1) Principe............................................................................................................... 54 III.3.2) Métrique globale................................................................................................. 54 III.3.3) Compromis entre le seuil de fusion au niveau du RSST et le seuil.................... 55 de similarité entre régions ................................................................................... 55 III.3.4) Résultats de la métrique globale améliorée ........................................................ 55

Conclusion............................................................................................................... 56

Bibliographie ........................................................................................................ 57

Annexes .................................................................................................. 59 ANNEXE 1: Description des séquences de tests...........................................60 ANNEXE 2: Les séquences de tests adaptées au descripteur local de couleurs dominantes par quadrillage de l’image.......................61 ANNEXE 3: Influence du seuil de fusion .....................................................63 ANNEXE 4: Distance quadratique améliorée ...............................................65 ANNEXE 5: Exemples de segmentation en régions .....................................66 ANNEXE 6: Interface de validation des résultats : .......................................68 Requête globale........................................................................68 ANNEXE 7: Interface de validation des résultats : .......................................69 Requête partielle ......................................................................69 ANNEXE 8: Coût de fusion maximum du RSST .........................................70 ANNEXE 9: Descripteur local avec segmentation de l’image en régions : comparaison des deux métriques globales proposées ...............73 ANNEXE 10: Résultats du descripteur local obtenu avec segmentation de l’image en régions........................................75 ANNEXE 11: Résultats de requêtes partielles ..............................................81 ANNEXE 12: Architectures UML utilisées pour les descripteurs locaux ...................................................................................87

Page 7: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 7 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Table des figures Figure 1. Organisation de Thomson multimédia ..................................................................... 9 Figure 2. Extraction des couleurs dominantes sur une carte de segmentation en régions .... 12 Figure 3. Distance quadratique croisée................................................................................... 17 Figure 4. Organigramme du RSST ........................................................................................ 20 Figure 5. Algorithme hiérarchique d’estimation du mouvement dominant........................... 22 Figure 6. Algorithme de segmentation basé sur le mouvement.............................................. 23 Figure 7. Comparaison bloc à bloc .......................................................................................... 24 Figure 8. Comparaison bloc à voisinage................................................................................ 25 Figure 9. Métrique globale dans le cas d’une segmentation des images en régions ............... 28 Figure 10. Schéma d’extraction du descripteur couleur local ................................................ 31 Figure 11. Principe du programme de validation................................................................... 32 Figure 12. Influence de la taille des blocs sur la distance entre images.................................. 38 (a) Bloc de taille 32*32 ; (b) Bloc de taille 64*64 ................................................... 38 Figure 13. Influence de la taille des blocs sur les critères NAVR et RR ................................ 39 Figure 14. Comparaison bloc à voisinage - coefficients de pondération............................... 40 Figure 15. Influence de la taille des blocs et de la métrique globale sur le critère NAVR...... 41 Figure 16. Intérêt de la mesure de confiance .......................................................................... 42 Figure 17. Influence de la mesure de confiance sur le critère NAVR .................................... 42 Figure 18. Comparaison de l’histogramme couleur avec le descripteur local......................... 44 de couleurs dominantes.......................................................................................... 44 Figure 19. Comparaison visuelle : Avantage du descripteur couleur local ............................ 45 Figure 20. Comparaison visuelle : Avantage du descripteur couleur global.......................... 46 Figure 21 . Inconvénient de la maximisation du recouvrement ............................................. 49 Figure 22. Influence du facteur d’échelle :(a) métrique brute ; (b) métrique améliorée.......... 50 Figure 23. Influence de la limitation des translations ............................................................ 50 Figure 24. Inconvénient des régions de couleur presque uniforme ........................................ 51 (a) descripteur couleur par quadrillage ; (b) descripteur couleur par régions segmentées..... 51 Figure 25. Influence du seuil de fusion sur le descripteur à 16 couleurs dominantes ........... 64 Figure 26. Résultats de segmentation selon un critère d’homogénéité couleur ..................... 66 Figure 27. Résultats de segmentation selon un critère d’homogénéité mouvement............... 67 Figure 28. Interface de validation : Choix de l’image de référence ......................................... 68 Figure 29. Interface de validation : Comparaison des résultats de la requête automatique pour le descripteur global et les descripteurs locaux ............................................ 68 Figure 30. Choix d’une ou plusieurs régions de l’image de référence .................................... 69 Figure 31. Affichage des résultats de la requête partielle ....................................................... 69 Figure 32. comparaison de deux coûts de fusion au niveau du RSST ................................... 72

Page 8: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 8 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Introduction _____________

Le développement croissant des moyens de communication ces dernières années, a permis l’accumulation d’immenses quantités de données numériques composées d’images, de son et de vidéo. L’Internet est un très bon exemple de base de données multimédia disponibles à des millions d’utilisateurs. Traditionnellement, des attributs textuels ou mots-clés, sont utilisés pour indexer les images et permettre aux systèmes de recherche de répondre rapidement à une requête d’un utilisateur. Mais le nombre croissant d’images a rendu nécessaire le développement d’outils robustes d’analyse d’images pour leur annotation automatique. Ainsi se pose le problème de l’indexation automatique des images fondée sur leur contenu. Ce thème de recherche s’attaque au problème de la reconnaissance d’objets en se basant uniquement sur des similarités entre images.

Les outils d’analyse d’images utilisés en indexation extraient dans un pré-traitement des caractéristiques compactes, pertinentes pour la comparaison d’images. Une image peut être caractérisée par plusieurs attributs :

• la couleur, définie par les valeurs des trois canaux couleurs des pixels de l’image,

• la forme, décrite par le contour des régions ou des objets contenus dans l’image,

• la texture,

• le mouvement, lorsque les images à indexer appartiennent à une séquence vidéo.

La similarité entre deux images est évaluée en comparant leurs caractéristiques respectives. Dans ce contexte, le futur standard MPEG-7 [MPEG 01] propose un large ensemble de descripteurs normalisés, parmi lesquels les attributs « bas niveau » évoqués ci-dessus.

Dans le cadre de mon stage, je m’ intéresse à l’attribut couleur en essayant de le

combiner à une segmentation de l’image en régions pour introduire une information spatiale et obtenir ainsi un descripteur local. Je présenterai dans un premier temps la problématique et le cahier des charges. Ensuite je ferai une présentation de l’état de l’art des descripteurs couleurs et des algorithmes de segmentation en régions. Dans une troisième partie, je ferai une description technique des réalisations et des méthodes utilisées. Enfin, je présenterai la phase de validation et l’interprétation des résultats et je finirai par un bilan du travail et les évolutions possibles pour les méthodes utilisées.

Page 9: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 9 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Présentation du stage I. CADRE DU STAGE I.1.Thomson Multimédia

Thomson Multimédia dont l’histoire débute dans le laboratoire de Elihu Thomson à Philadelphie à la fin du XIXe siècle était la filiale d’électronique grand public du groupe Thomson, d’abord sous le nom de Thomson Grand Public puis de Thomson Consumer Electronics, au moment de l’acquisition de RCA en 1988, et enfin de Thomson Multimédia en 1995. Le groupe Thomson Multimédia (TMM), est né seulement en 2000 de la privatisation de cette même filiale du grand groupe français, fruit de la fusion en 1981 de Thomson-Brandt et Thomson-CSF puis nationalisé en 1982.

Tout comme Thomson-CSF, devenu Thalès, est partenaire d’autres grands noms de

l’électronique de défense, Thomson Multimédia est resté l’un des fleurons de l’industrie française, gardant son rang de groupe multinational hérité de son histoire : N°1 mondial de la vente de nombreux produits audio-visuels (tubes cathodiques, décodeurs numériques, téléphones, DVD, etc.) et leader sur le marché américain des téléviseurs couleur sous la marque RCA. Il y a plus de 50 millions de produits vendus dans le monde. TMM a réalisé un chiffre d'affaires de 9 094 millions d'€uros en 2000.

Les quatre domaines d’activité sont : Ecrans et Composants ; Produits grand public, Nouveaux Médias et Services, Brevets Licences sont organisés en 8 centres de profits : Strategic Business Units (SBU).

Figure 1. Organisation de Thomson multimédia

Page 10: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 10 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Son effectif atteint 55 000 personnes sur 3 continents (Amérique, Europe, Asie),

dont 2400 personnes réparties sur six centres de recherche : Hanovre, Vilingen, Indianapolis, Princeton, Rennes et Tokyo.

I.2. Thomson Multimédia R&D France à Rennes

Présent sur le site rennais depuis 1973, Thomson a pris un nouvel élan lors de la création de Thomson multimedia R&D France. Cette nouvelle entité, créée le 1er janvier 1996 est née du regroupement d’une partie du personnel et des activités de recherche de Thomson Broadcast Systems avec le personnel transféré du centre de Thomson Consumer Electronics R&D France de Strasbourg. Thomson multimedia R&D France est le centre de recherche de Thomson multimédia en France et le centre de développement des produits numériques en Europe. Il regroupe 400 personnes dont 75% d’ingénieurs et cadres. Les activités de R&D France concernent l’ensemble de la chaîne de l’image, de la génération à la visualisation, dans des systèmes et réseaux multimédias.

I.3. Le laboratoire Advanced Visual Processing (AVP)

AVP est l’une des sept équipes de recherche de TMM R&D France, elle est constituée d’une quinzaine de permanents, auxquels s’ajoutent des stagiaires.

Les thèmes de recherche du laboratoire AVP sont les suivants :

• Traitement d’images et vidéo et développement d’algorithmes :

o Représentation et codage de scènes 2D et 3D o Analyse de mouvement et techniques d’estimation o Analyse de scènes et classification o Etude de nouvelles possibilités multimédia et de techniques de codage

améliorées (streaming et navigation pour les scènes 3D, indexation vidéo par contenu)

• Etude d’architectures o Compression vidéo MPEG : implémentation d’une nouvelle génération de

codeurs MPEG-2 o Analyse d’architectures de plate-formes média-processeurs

• Activité de standardisation (notamment MPEG-7)

Page 11: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 11 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

II. CAHIER DES CHARGES

Descriptif du sujet Indexation d’images orientée objet: combinaison des techniques de segmentation d’images en régions avec l’extraction des descripteurs couleurs.

Application principale : Recherche d’images dans leur globalité

• Evaluation du descripteur de couleurs dominantes :

- Choix de la métrique associée.

- Réglage des différents paramètres.

• Phase de validation, sur station, sur un échantillon représentatif d’images de la pertinence du descripteur couleur.

• Evaluation des algorithmes de segmentation développés au sein du laboratoire AVP sous Sun Solaris 2.5.

• Implémentation des algorithmes de segmentation sélectionnés et du descripteur couleur sur PC avec Visual C++ en utilisant la méthodologie UML.

• Combinaison de la segmentation en régions avec le descripteur de couleurs dominantes et calcul d’une métrique adaptée.

• Phase de validation de la pertinence du descripteur couleur appliqués aux régions de l’image, un descripteur local :

- Sélection des images des séquences adaptées au descripteur couleur local.

- Implémentation d’une interface graphique qui permet de lancer une requête par l’exemple, rechercher les images similaires dans toute la séquence vidéo et les afficher par ordre décroissant de similarité.

- Comparaison des résultats de requête automatique avec le jugement d’un opérateur humain en établissant une « vérité terrain » et en spécifiant des critères d’évaluation adaptés.

Autre application : Recherche d’images par requête partielle

• Utilisation du descripteur local développé précédemment pour une recherche partielle d’une région ou d’un objet de l’image de référence.

- Choix d’une métrique appropriée

• Implémentation d’une interface graphique appropriée.

Contexte technique Programmation : C++, Visual C++, Rational Rose 2000.

Environnement : Station de travail Sun sous Solaris 2.5. , PC sous Windows NT.

Page 12: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 12 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

III. ANALYSE DU PROBLEME III.1. Recherche d’images dans leur globalité

Le travail du stage s’insère dans le cadre d’un projet de création de résumés vidéos. Disposant d’une séquence vidéo, on commence par extraire un certain nombre d’images clés et on cherche par la suite à les regrouper par similarité visuelle en utilisant différents attributs. Mon étude porte principalement sur l’attribut couleur en essayant d’inclure une information sur la structure de l’image. L’année dernière une étude approfondie a été réalisée sur deux descripteurs couleurs : les histogrammes couleurs et les couleurs dominantes et les métriques associées [Forest 00]. Ils ont été utilisés en tant que descripteurs globaux sur toute l’image. Dans le cadre de mon travail, on a envisagé d’implémenter un descripteur local de couleurs qui prend en compte l’information spatiale et la distribution des couleurs dans l’image. On comparera par la suite les performances de ce descripteur local à celles du descripteur global. La finalité de ce stage sera de juger si ce nouveau descripteur améliore l’indexation des séquences vidéos et ce dans quels cas.

Pour implémenter ce descripteur local, on a pensé à extraire les couleurs dominantes sur des petites régions de l’image obtenues par segmentation. L’analyse de ce problème comporte trois phases importantes à traiter :

Phase de choix :

- Choix du descripteur et de la métrique associée. - Réglage des différents paramètres de la métrique choisie. - Choix de l’algorithme de segmentation qui convient le mieux à notre usage.

Cette phase est à réaliser sur la station Sun puisque tous les algorithmes développés au sein de l’équipe sont implémentés en C ou C++ sur la station.

Phase de combinaison des algorithmes de segmentation avec les descripteurs

couleurs. Une fois que l’on dispose des descripteurs de couleurs dominantes sur différentes régions de l’image, le point important est de trouver les métriques globales appropriées pour comparer deux images dans leur globalité.

Figure 2. Extraction des couleurs dominantes sur une carte de segmentation en régions

Métrique : ?? Vc1 Vc2

Vc6

Vc4 Vc6

Vc8

Vc7

Vc1Vc2

Vc3

Vc4

Vc5

Vc5 Vc7

Page 13: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 13 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Pour chaque région, on a un vecteur de couleurs dominantes vci , i ∈[1.. NR]. NR étant le nombre de régions par image. On va traiter le problème en deux parties :

- Pour s ‘affranchir des problèmes liés à l’utilisation de régions de formes

quelconques, on commence tout d’abord par un simple quadrillage de l’image. On calcule pour chaque bloc, le descripteur couleur correspondant et on essaye de trouver la meilleure métrique pour comparer deux images quadrillées.

- On appliquera, dans un deuxième temps, le descripteur couleur sur des régions quelconques de l’image (obtenues suite aux algorithmes de segmentation) et, de même, le problème est de trouver la métrique appropriée. Ce problème pose plus de difficultés que le cas précédent puisque la forme, la position et le nombre de régions varient d’une image à l’autre.

Cette phase sera en partie réalisée sous Sun pour avoir une première idée sur les résultats obtenus et pouvoir réfléchir à l’architecture logicielle qu’il faudra développer sur PC. Il faudra ensuite implémenter le descripteur choisi, les algorithmes de segmentation sous Visual C++.

Phase de validation Enfin, il faudra valider tous les algorithmes choisis en utilisant des critères d’évaluation à déterminer. Ces mêmes critères nous permettront de comparer le descripteur local de couleurs dominantes au descripteur global utilisant les histogrammes de couleurs. III.2. Recherche d’images par requête partielle Une fois que l’on a obtenu le descripteur local de couleurs dominantes, on va l’utiliser pour une deuxième application qui ne s’inscrit pas dans le cadre des résumés vidéos.

Comme les couleurs dominantes sont adaptées à une description locale de l’image, on va lancer des requêtes partielles sur une ou plusieurs régions d’une image de référence, ce qui permet de choisir un objet précis ou bien de rendre la recherche plus pertinente en choisissant des régions discriminantes tel que le fond, les motifs des objets… . Le problème sera encore de trouver la métrique appropriée pour renvoyer automatiquement les images qui contiennent les régions d’intérêt choisies.

Page 14: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 14 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

IV. ORGANISATION DU TRAVAIL

Semaines 1,2,3

Semaine 4

Semaine 5

Semaine 6

Semaine 7

Semaine 8, 9

Semaine 10

Semaine 11

Semaine 12,13

Semaine 14,15

Semaine 16, 17

Semaine 18

Semaine 19

Semaine 20,21

Semaine 22

Semaine 23

Semaine 24

Semaine 25

Semaine 26

Bibliographie X X X

Evaluation des algorithmes de segmentation X X

Couleurs dominantes : choix de la métrique X X

Combinaison : quadrillage & couleurs dominantes X X X

Modèle UML et compréhension de l’architecture du projet existant

(cf. Annexe 12) X X

Implémentation sur PC des algorithmes existants sur SUN X

Implémentation sur PC: - Interface de recherche automatique - quadrillage - mesure de confiance

X

Implémentation du RSST sur PC

X

- Implémentation descripteur basé

sur la segmentation en régions - Choix de la métrique - Réglage des paramètres

X

Application requête partielle : - interface graphique - choix de la métrique

X

X

Expériences et exploitation des résultats X X

X

X

Rédaction du rapport X X X X

X

X

Descripteur couleurs dominantes basé sur un quadrillage de l’image. Descripteur couleurs dominantes basé sur une segmentation en régions de l’image. Application de recherche par requête partielle.

Page 15: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 15 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Etat de l’art I. LE DESCRIPTEUR DE COULEURS DOMINANTES I.1. Choix du descripteur

Il y a deux types de descripteurs qui ont été développés au sein du laboratoire : Les histogrammes couleurs et les couleurs dominantes.

Les histogrammes couleurs sont généralement associés à une quantification qui ne dépend pas du contenu couleur de l’image et, par conséquent, on peut se retrouver avec des colonnes de l’histogramme vides, c’est-à-dire inexploitées. Par contre le descripteur de couleurs dominantes est plus compact ; il est basé sur une quantification adaptative en fonction de l’image et permet donc de décrire plus efficacement le contenu couleur d’une image.

En outre, d’après le cahier des charges, on veut caractériser localement les régions de l’image. On n’a donc pas besoin d’un grand nombre de couleurs par région, et le dernier descripteur est plus adapté, dans ce cas, que les histogrammes couleurs.

I.2. Les techniques de regroupement ou « clustering »

L’extraction du descripteur de couleurs dominantes est basée sur les techniques de regroupement. Ce regroupement de couleurs est effectué pour chaque image ou région indépendamment, de telle sorte que chacune soit représentée par sa propre table de couleurs, et le pourcentage de présence de chacune. Pour cela, la quantification vectorielle est utilisée.

I.2.1) La quantification vectorielle

Un quantificateur vectoriel est une fonction qui à chaque vecteur source x de dimension k associe un vecteur représentant de même dimension, extrait d’un dictionnaire C de taille L [VDLynden 95]. Deux actions sont donc nécessaires pour faire une quantification : déterminer les mots (centroïdes) du dictionnaire et pour chaque pixel de l’image trouver le vecteur du dictionnaire le plus représentatif.

Après la quantification vectorielle, on peut classifier les pixels selon les centroïdes qui les quantifient. Cette classification non supervisée donne une quantification intéressante de l’image source.

Il existe de nombreux algorithmes de quantification vectorielle, avec des classiques comme l’algorithme de Lloyd et Max [Lloyd 82], K-means et ses variantes…

Page 16: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 16 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

I.2.2) Algorithme du K-means

Cet algorithme a été développé par Mac-Queen en 1967 [MacQueen67], qui généralisait un principe de quantification scalaire optimale de Lloyd et Max [Lloyd 82].

Au départ, on dispose de l’ensemble des coordonnées des pixels dans l’espace colorimétrique, et on connaît le nombre de centroïdes, ou représentants de classes, autour desquels on va découper l’espace. L’initialisation des coordonnées trichromatiques des centroïdes se fait en leur donnant des valeurs de pixels pris au hasard. On itère ensuite de la manière suivante :

Calcul du centroïde auquel est assigné chaque pixel (centroïde le plus proche au sens de la distance Euclidienne).

Calcul des nouvelles coordonnées des centroïdes : on prend le barycentre de tous les pixels qui lui sont assignés.

Ce processus est répété tant que les classes formées ne sont pas stables, mais généralement, un nombre d’itérations maximal est fixé à l’avance.

Formellement, si C(Pj) est le numéro de la classe à laquelle est affectée la donnée Pj, G le barycentre de la classe, la méthode consiste à minimiser l’expression :

∑ −j

PCj jGP

2

)(

L’algorithme converge assez rapidement, mais appelle quelques commentaires :

Il faut fournir le nombre de classes (centroïdes) souhaité, ce qui n’est pas toujours évident ; la quantification nécessite un nombre différent de classes suivant l’image traitée.

La solution trouvée dépend de l’étape d’initialisation. Dans le code utilisé, celle-ci est faite en utilisant un générateur de nombres aléatoires.

I.3. Le descripteur et les métriques associées

L’algorithme du K-means va nous permettre de construire un descripteur de couleur plus compact que les histogrammes, mais plus coûteux en temps de calcul pour son extraction. En général, ce descripteur de couleurs dominantes est plus approprié pour décrire localement une région de l’image. Néanmoins, il peut s’étendre à une description globale du contenu couleur d’une image : dans ce cas, il est recommandé d’utiliser 4 à 32 couleurs (dans MPEG-7, le nombre de classes maximum est fixé à 7).

Le descripteur de couleurs dominantes contient donc les informations suivantes :

N : nombre de couleurs dominantes du descripteur.

Pi : pourcentage de présence de la couleur i dans la région, i ∈ [1…N].

Ci : coordonnées trichromatiques de la couleur i.

Page 17: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 17 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Maintenant, il faut mettre en place une méthode pour quantifier la similarité entre de tels descripteurs. Comme les tables de couleur sont différentes pour chaque région, une métrique classe à classe ne peut pas donner des résultats satisfaisants. On va donc utiliser des mesures de similarité croisée (cf. Figure 3.).

I.3.1) Fonction quadratique de distance

L’avantage de cette métrique est qu’elle tient compte de la similarité des couleurs proches et par conséquent elle est robuste aux changements de luminosité. Par exemple, si sur une première image on a un objet monochrome rouge et qu’avec un changement de lumière, on obtient sur une deuxième image un objet monochrome orange, l’objet sera reconnu d’une image à l’autre.

Cette distance [Hafner 95] est donnée par l’expression suivante:

( ) ( ) ( ) ( )ijT aAavecKHAKHKHD =−−=, (1)

Les coordonnées de la matrice de similarité ente couleurs A sont :

( )ij

ijij

ij

dd

jeticouleursdeuxentreeeuclidienndistancedavecdd

a

max

:1

max

max

=

−=

Néanmoins, la matrice A est une matrice N*N avec N le nombre de couleurs dominantes. Elle est donc coûteuse à utiliser. Dans la pratique, on pourra utiliser le fait que cette matrice soit à diagonale dominante pour négliger tous les termes éloignés de la diagonale.

Figure 3. Distance quadratique croisée

L’explication de la distance quadratique ci-dessus est faite dans le cas de deux

histogrammes de N classes, obtenu chacun avec la même quantification (c’est à dire les mêmes représentants de classes). Dans notre cas, on compare deux vecteurs de couleurs dominantes F1 et F2 obtenus par une quantification adaptative, qui donne donc des représentants de classes différents selon les images. Soit N1 couleurs associées à F1 et N2 couleurs associées à F2 potentiellement différentes. Pour appliquer la distance quadratique,

Page 18: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 18 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Il faut créer un histogramme de dimension N1+N2 associé aux couleurs quantifiées des deux vecteurs réunies. Dans chaque classe de l’histogramme, on représente le pourcentage de présence de la couleur correspondante. La distance quadratique appliquée aux couleurs dominantes s’écrit alors :

( ) ( ) ( )2'

1'

2'

1'

212 ,' FFAFFFFD T −−= avec

=

=

2

1

,2

.

.

2,2

1,2

.

.

2'

.

.

,1

.

.

2,1

1,1

1'

0

0

0

0

N

N

p

ppFetp

pp

F (2)

I.3.2) Fonction quadratique de distance améliorée

Afin de simplifier le calcul de la distance quadratique, on va mettre en place une étape de fusion des couleurs qui sont proches perceptuellement. Ainsi, une fois l’étape de quantification terminée, on va récupérer les K couleurs les plus représentatives de notre image que l’on va ensuite regrouper par une méthode agglomérative. En effet, l’algorithme du K-means permet d’extraire des couleurs dominantes qui peuvent être proches d’un point de vue colorimétrique. Par la suite, on va fusionner les deux classes les plus proches, puis mettre à jour les indices d’agrégations, et on recommence jusqu’à ce que les différentes couleurs dominantes que l’on a extraites de notre image soient toutes différentes perceptuellement. La recherche des deux groupes les plus proches se fait par recherche de l’élément minimal dans la matrice des distances. C’est un processus de complexité quadratique.

Ainsi, à la fin de cette étape de fusion, toutes les couleurs dominantes de l’image seront au moins éloignées entre elles d’une distance notée Td. A partir de là, le calcul de la distance quadratique se simplifie [Deng 99], et on obtient alors la formule suivante:

∑ ∑∑∑= = ==

−+=2 1 21

1 1 1212,1

22

1

2121 2),(

N

j

N

i

N

jjijij

N

ii ppappFFD (3)

avec :

d

lk

dlklklk

Tdeeuclidienndistanced

Tddda

∗=

≤−

=

αmax

,

,max,,

:sinon0si/1

Td est la distance maximale pour laquelle deux couleurs sont considérées similaires, et une valeur normale pour α est de l’ordre de 1.0-2.0.

Le fait que ( ) ( )2121 ','', FFDFFD = est démontré en annexe 4.

Page 19: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 19 of 88

M é m o i r e d e D E A P h o t o n i q u e , I m a g e e t C y b e r n é t i q u e M a r s - A o û t 2 0 0 1 I . 3 . 3 ) A m é l i o r a t i o n s p o s s i b l e s d e l a m é t r i q u e : c o n t e n u s p a t i a l Enfin, on peut ajouter au descripteur couleur une information sur la répartition s p a t i a l e d e l a c o u l e u r . A c e t e f f e t , o n u t i l i s e u n e v a r i a b l e q u i é v a l u e l e d e g r é d e c o n f i a n c e d a n s n o t r e r é p a r t i t i o n d e s c o u l e u r s d o m i n a n t e s : l a v a r i a b l e C M ( p o u r Confidence Measure) . O n a u n e m e s u r e d e c o n f i a n c e p a r v e c t e u r d e c o u l e u r s d o m i n a n t e s . C e t t e v a r i a b l e e s t u n e s o m m e d e s c o h é r e n c e s d e s c o u l e u r s d o m i n a n t e s e x t r a i t e s , p o n d é r é e s p a r l e p o u r c e n t a g e d e p r é s e n c e d e c h a q u e c o u l e u r d a n s l a r é g i o n . N

i

P

i

C

i

C

O

H

C

M

.

.

1

_

(

4

)

C

O

H

_

C

i

e

s

t

l

a

c

o

h

é

r

e

n

c

e

d

e

l

a

c

o

u

l

e

u

r

C

i

e

t

P

i

s

o

n

p

o

u

r

c

e

n

t

a

g

e

d

e

p

r

é

s

e

n

c

e

d

a

n

s

l

a

r

é

g

i

o

n

.

régionl a d a n s C i c o u l e u r d e p i x e l s d e N o m b r e C i c o u l e u r d e c o h é r e n t s p i x e l s d e N o m b r e

C i C O H _ ( 5 ) Un pixel de couleur C

i est considéré comme cohérent si tous les pixels dans son voisinage

3*3 ont la même couleur C

i.

L

a

c

o

h

é

r

e

n

c

e

d

u

n

e

c

o

u

l

e

u

r

t

r

a

d

u

i

t

s

a

r

é

p

a

r

t

i

t

i

o

n

s

p

a

t

i

a

l

e

d

a

n

s

u

n

e

r

é

g

i

o

n

d

e

l

i

m

a

g

e

.

S

i

,

p

a

r

e

x

e

m

p

l

e

,

u

n

e

c

o

u

l

e

u

r

d

o

m

i

n

a

n

t

e

e

s

t

c

o

n

c

e

n

t

r

é

e

d

a

n

s

u

n

e

r

é

g

i

o

n

d

e

l

i

m

a

g

e

,

e

l

l

e

a

u

r

a

u

n

e

g

r

a

n

d

e

c

o

h

é

r

e

n

c

e

e

t

s

i

,

a

u

c

o

n

t

r

a

i

r

e

,

o

n

a

u

n

e

d

i

s

p

e

r

s

i

o

n

s

p

a

t

i

a

l

e

d

e

n

o

t

r

e

c

o

u

l

e

u

r

d

o

m

i

n

a

n

t

e

,

s

a

c

o

h

é

r

e

n

c

e

s

e

r

a

f

a

i

b

l

e

.

P

a

r

c

o

n

s

é

q

u

e

n

t

,

d

e

s

g

r

a

n

d

e

s

v

a

l

e

u

r

s

d

e

c

o

h

é

r

e

n

c

e

p

e

r

m

e

t

t

e

n

t

d

e

d

i

r

e

q

u

e

n

o

s

c

o

u

l

e

u

r

s

d

o

m

i

n

a

n

t

e

s

s

o

n

t

b

i

e

n

s

é

p

a

r

é

e

s

e

t

d

i

s

t

i

n

c

t

e

s

e

n

t

r

e

e

l

l

e

s

.

L

e

f

a

i

t

d

e

p

o

n

d

é

r

e

r

a

v

e

c

l

e

p

o

u

r

c

e

n

t

a

g

e

d

e

p

r

é

s

e

n

c

e

p

e

r

m

e

t

d

e

d

o

n

n

e

r

p

l

u

s

d

e

p

o

i

d

s

à

u

n

e

c

o

u

l

e

u

r

p

r

é

p

o

n

d

é

r

a

n

t

e

d

a

n

s

l

a

r

é

g

i

o

n

m

ê

m

e

s

i

e

l

l

e

e

s

t

d

i

s

p

e

r

s

é

e

,

c

e

q

u

i

e

s

t

l

e

c

a

s

d

e

s

o

b

j

e

t

s

t

e

x

t

u

r

é

s

.

C

e

t

t

e

m

e

s

u

r

e

d

e

c

o

n

f

i

a

n

c

e

p

e

r

m

e

t

d

o

n

c

d

e

r

e

n

d

r

e

l

e

d

e

s

c

r

i

p

t

e

u

r

p

l

u

s

r

o

b

u

s

t

e

a

u

b

r

u

i

t

.

E

l

l

e

e

s

t

a

u

s

s

i

b

i

e

n

a

d

a

p

t

é

e

p

o

u

r

d

é

t

e

c

t

e

r

d

e

s

o

b

j

e

t

s

d

e

c

o

u

l

e

u

r

s

u

n

i

f

o

r

m

e

s

q

u

i

d

o

n

n

e

n

t

d

e

g

r

a

n

d

e

s

v

a

l

e

u

r

s

d

e

C

M

.

E

n

u

t

i

l

i

s

a

n

t

c

e

t

t

e

m

e

s

u

r

e

d

e

c

o

n

f

i

a

n

c

e

,

o

n

a

u

n

e

f

o

r

m

u

l

e

p

o

u

r

n

o

t

r

e

m

é

t

r

i

q

u

e

e

n

t

r

e

d

e

u

x

d

e

s

c

r

i

p

t

e

u

r

s

d

e

c

o

u

l

e

u

r

s

d

o

m

i

n

a

n

t

e

s

q

u

i

d

e

v

i

e

n

t

:

Diff

DC

W

Diff

CM

W

D

D

Difference

_

_

)

,

(

2121

(6)

Page 20: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 20 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

II. ALGORITHMES DE SEGMENTATION EN REGIONS

Parmi le très grand nombre de techniques de segmentation d’images [Cocquerez 95], on a évalué quatre algorithmes dont le code était disponible dans le laboratoire. Les deux premiers sont basés sur un critère d’homogénéité couleur, les deux suivants sur un critère d’homogénéité mouvement.

II.1. Critère d’homogénéité couleur

II.1.1) Fusion de régions: RSST( Recursive Shortest Spanning Tree) RSST est une technique relativement simple, qui consiste à regrouper les régions

voisines en se basant sur un poids de lien que l’on expliquera plus loin. L’organigramme de cet algorithme est illustré Figure 3 . A l’initialisation une image de

M*N pixels est partionnée en M*N régions (segments) de taille 1 et les liens sont générés pour toutes les paires de régions en connectivité 4.

Figure 4. Organigramme du RSST

Test d’arrêt atteint ?

Stop Non

- Fusionner les deux régions les plus proches. - Calculer les valeurs des pixels des nouvelles régions et leurs tailles.

- Recalculer et trier les nouveaux poids des liens entre régions. - éliminer les liens dupliqués. Itération RSST

Initialisation RSST

Partionnement de l’image en

M*N régions de taille 1

Initialisation et tri des poids des liens entre les paires de régions en connectivité 4.

Page 21: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 21 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Chaque lien est assigné à un poids égal à la distance entre deux régions respectives, qui est généralement définie par une distance euclidienne entre les moyennes des composantes couleur des deux régions, utilisant un biais qui favorise la fusion des petites régions. Supposons que l’on utilise l’espace YUV, la mesure de distance entre deux régions A et B est définie par:

( ) ( ) ( ){ }TailleBtailleAtailleBtailleAVVUUYYd BABABAAB +

∗−+−+−=.222 (7)

où YX, UX et VX sont respectivement les moyenne des valeurs de Y, U et V de tous les pixels de la région X. Taille X étant le nombre de pixels dans cette région. Tous les poids des liens sont ensuite triés par ordre croissant, de telle façon que le plus petit poids corresponde aux régions les plus proches ensuite on déclenche la phase itérative du RSST où on fusionne les régions. On arrête l’itération quand on atteint soit, un nombre minimal de régions préfixé, soit un poids de lien maximal au delà duquel on ne fusionne plus les régions. Le premier critère dépend de l’image. Une fois le nombre de régions préfixé, on peut avoir soit une sur- segmentation soit une sous-segmentation suivant le contenu couleur de l’image. Il est donc préférable de prendre un poids de lien maximal comme paramètre car il fournit un résultat indépendant de l’image. II.1.2) Morphologie mathématique : Le partage des eaux ou « watershed »

En morphologie mathématique, une image est considérée comme un relief topographique où la variation d’altitude correspond à la variation de contraste le long du contour original.

Cet algorithme utilise la notion de gradient morphologique. Il est obtenu en assignant à chaque point x, la différence entre le plus haut et le plus bas pixel dans le voisinage de x. Ainsi, le gradient morphologique est en lui-même une fonction de niveaux de gris. Les grandes valeurs correspondent aux contours les plus contrastés sur l’image de départ.

L’algorithme est basé sur l’immersion du relief. On suppose que l’on perce des trous dans tous les minima locaux du relief. Chaque minimum constitue le fond d’un bassin. Ensuite la surface est immergée progressivement par le bas, en commençant par le minimum global. Lorsque deux bassins voisins tendent à se verser l’un dans l’autre, on construit un barrage. Cette procédure permet de partitionner l’image en plusieurs bassins autour des minima locaux et les barrages constituent les lignes de partage des eaux. Cependant, cet algorithme conduit à une sur-segmentation due au bruit de l’image qui crée des minima locaux parasites. D’où une phase nécessaire de simplification de l’image avant la segmentation.

Page 22: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 22 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

II.2. Critère d’homogénéité mouvement II.2.1) Estimation du mouvement dominant

Il s’agit d’une méthode hiérarchique d’estimation du mouvement dominant et de

segmentation de son support spatial. Le mouvement de chaque région est décrit par le modèle affine 2D (2 paramètres de translation et 4 paramètres affines). La procédure de segmentation comporte 6 étapes :

1. Le mouvement dominant DMt (modèle affine) entre l’image courante Yt et la précédente Yt-1 dans la séquence est identifié par régression linéaire multirésolution robuste [Odobez 95]. L’image précédente est alors compensée à l’aide de ce mouvement dominant.

2. Une carte de segmentation prédite PSt est obtenue en projetant la carte de segmentation finale à l’instant précédent St-1 dans la direction du mouvement.

3. Les pixels qui ne sont pas cohérents vis à vis du mouvement dominant sont détectés « mal étiquetés » et groupés en régions. La carte résultante est comparée à la carte prédite. Les régions des pixels mal étiquetés, qui n’ont pas de correspondance dans la carte prédite, sont considérés comme de nouvelles régions (apparaissantes). Cette étape fournit une carte initiale St.

4. Pour chaque région de la carte prédite, un vecteur de paramètres affines de mouvement MVt est estimé par régression linéaire multirésolution.

5. Les frontières des régions sont optimisées. La carte de segmentation est modélisée par un champ Markovien, sur lequel un algorithme de relaxation est appliqué. La carte résultante est notée RSt.

6. Un processus de fusion de régions, dés lors que l’erreur de compensation ne s’accroît pas significativement, est appliqué et donne une carte finale St.

Figure 5. Algorithme hiérarchique d’estimation du mouvement dominant

Yt-1 Estimation et compensation du mouvement global

Création de régions étiquetées

Estimation des

paramètres d

Prédiction d’une carte de segmentation

Fusion de régions

Relaxation de la carte de

segmentation

Yt

DM t IS t MV t

RS t

S t

t=t+1

S t-1

PS t

Page 23: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 23 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

II.2.2) Segmentation couleur suivie d’une fusion de régions selon un critère d’homogénéité mouvement [Chupeau 00]

Cet algorithme regroupe selon un critère d’homogénéité mouvement des régions élémentaires obtenues à partir d’une carte de segmentation couleur. L’estimation du flot optique est réalisée entre les composantes de luminance de l’image courante et l’image précédente Yt et Yt-1. Elle renvoie un vecteur de mouvement D(p) par pixel. En parallèle, une segmentation couleur de l’image courante utilisant le RSST(cf. II.1.1), renvoie une carte de segmentation couleur Sc(p)=i, i∈ [1,Nc], Nc étant le nombre de couleurs. Par la suite, pour chaque région couleur Rc, un vecteur affine de 6 paramètres de mouvement MP est estimé à partir du vecteur de mouvement dense. Enfin, les régions colorées avec des mouvements similaires sont fusionnées (cf. Figure 6. ). Le processus de fusion est paramétré par la taille minimale des régions significatives.

Figure 6. Algorithme de segmentation basé sur le mouvement

Estimation du flot optique

Segmentation colorée

Y(t) Cb(t) Cr(t)Y(t-1)

Estimation robuste des paramètres de

mouvement

Fusion des régions selon un critère basé

sur le mouvement

D(p) Sc(p)=i

MP(i)

Page 24: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 24 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

III. COMBINAISON DES TECHNIQUES DE SEGMENTATION AVEC LE DESCRIPTEUR COULEUR Dans un premier temps, on s’affranchit des problèmes liés à une partition en régions de formes quelconques en utilisant un quadrillage en blocs carrés.

III.1. Régions fixées : Quadrillage de l’image

III.1.1) Principe Cette technique s’inspire du système de recherche d’images par similarité QBIC, développé par IBM [Flickner 95]. Notre méthode consiste à quadriller l’image en petits blocs et calculer un vecteur de couleurs dominantes par bloc. Par conséquent, cette méthode entraîne le réglage de nombreux paramètres dont la taille du bloc et le nombre de couleurs dominantes par bloc. Evidemment, le nombre de couleurs dépend de la taille des blocs : plus la taille du bloc est grande, plus il faut augmenter le nombre de couleurs. De plus, le nombre de couleurs dominantes obtenu dépend d’une part du nombre de centroïdes au départ du K-means mais aussi du seuil de fusion appliqué à la suite du K-means pour regrouper les régions perceptuellement proches. Il y a donc un compromis à trouver entre ces différents paramètres. Les étapes de réglage de ces paramètres sont détaillées dans le chapitre des résultats (cf. Résultats I.1 et II.1).

III.1.2) Métriques globales

On cherche, dans notre application, à lancer une requête sur une image de référence (image clé) et effectuer ensuite une recherche automatique parmi toutes les images de la séquence qui sont similaires à cette dernière. On sait calculer la mesure de similarité entre deux vecteurs de couleurs dominantes (cf. I.3.). En pratique, on a choisi d’utiliser la distance quadratique améliorée (voir plus loin Résultats I.2.). Une fois que les vecteurs de couleurs dominantes ont été extraits pour tous les blocs de toutes les images de la séquence, on cherche à établir une métrique globale qui permet de calculer une mesure de similarité entre deux images.

III.1.2.2) Comparaison bloc à bloc :

Figure 7. Comparaison bloc à bloc

Image de référence Autre image de la séquence

Métrique distancequadratique améliorée

Page 25: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 25 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Chaque bloc de l’image de référence est comparé avec son bloc équivalent dans la

deuxième image. On somme les distances obtenues pour tous les blocs et on divise par le nombre total de blocs. L’inconvénient de cette métrique est qu’elle n’est pas très robuste aux mouvements des objets et/ou de la caméra. En effet, dès qu’un objet se déplace d’une distance supérieure à la taille du bloc, on ne le retrouve plus en comparant bloc à bloc d’où l’idée de considérer aussi le voisinage du bloc.

III.1.2.2) Comparaison bloc à voisinage :

Chaque bloc de l’image de référence est comparé à son bloc équivalent dans la deuxième image et au huit voisins de ce dernier. Des coefficients de pondération permettent de donner plus de poids au bloc central par rapport à son voisinage. En outre, on donne plus de poids aux blocs centraux d’une image qu’aux blocs de bords. Ceci est dû, d’une part, au fait que les blocs du bord de l’image ne peuvent pas être comparés à un voisinage et qu’ils sont, par conséquent, comparés bloc à bloc d’où un poids plus faible. D’autre part, on suppose que les objets que l’on recherche sont, en général, centrés dans l’image.

Figure 8. Comparaison bloc à voisinage

En comparant les mêmes images entre elles, le calcul bloc à voisinage ne renvoie pas une distance nulle puisqu’on prend en compte des blocs voisins qui ne ressemblent pas au bloc central. On n’a plus une distance au sens mathématique. Mais ceci ne gène pas dans le cas de notre application puisque seul le classement relatif des images par distance croissante à l’image de référence nous importe.

Enfin, cette métrique permet d’augmenter la robustesse vis à vis des petites translations.

Image de référence Autre image de la séquence

Métrique distancequadratique améliorée

Page 26: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 26 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

III.2. Segmentation de l’image en régions

Dans un deuxième temps, on va extraire le descripteur de couleurs dominantes sur les différentes régions de l’image, obtenues avec un algorithme de segmentation vu précédemment (cf. II ). On rappelle que les régions peuvent être obtenues selon un critère d’homogénéité couleur ou bien mouvement. Elles représentent donc des parties d’un objet ou bien un objet entier de l’image.

III.2.1) Application de requête globale

III.2.1.1) Principe On cherche, dans notre application, à quantifier la mesure de similarité entre deux

images segmentées en régions. On sait calculer la mesure de similarité entre deux vecteurs de couleurs dominantes de deux régions (cf. I.3.). En pratique, on a choisi d’utiliser la distance quadratique améliorée (voir plus loin Résultats I.2.). On cherche maintenant à établir une métrique globale qui permet de comparer deux images. Le fait d’utiliser une carte de segmentation de l’image pose beaucoup plus de difficultés qu’un simple quadrillage en blocs carrés. Tout d’abord, les régions sont de formes quelconques, ensuite la position et le nombre de régions varient d’une image à l’autre.

III.2.1.2) Métrique globale

Supposons que l’on dispose de deux images Q (Query) et T (Target). L’image Q est

l’image de référence et l’image T étant l’image cible. Chacune est composée respectivement des régions suivantes : nTTetmQQ KK ,1,,1 . La mesure de similarité entre Q et T est définie en termes de pourcentage de l’aire recouverte par les régions similaires entre les deux images par rapport à l’aire totale des deux images. Cette métrique est inspirée des travaux sur le système WALRUS [Natsev 99] et nécessite trois phases pour la mettre en oeuvre, on va donc donner quelques définitions auparavant: Définition 1 : ( Similarité de régions) Une paire de régions, dont on a extrait les vecteurs de couleurs dominantes F1 et F2 , est similaire si la distance quadratique améliorée entre F1 et F2 (cf. Etat de l’art I.3.2) : ( )21, FFD est inférieure à un seuil ε . Définition 2 : ( Ensemble de paires de régions similaires) Pour deux images Q et T, l’ensemble des paires ordonnées ( ) ( ){ }ll TQTQ ,,,, 11 K constitue un ensemble de paires de régions similaires entre Q et T si :

iQ est similaire à iT et pour jiji TTQQji ≠≠≠ ,,

Page 27: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 27 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Définition 3 : ( Similarité entre images) Deux images Q et T sont similaires s’il existe un ensemble de paires de régions similaires entre Q et T ( ) ( ){ }ll TQTQ ,,,, 11 K tel que :

( ) ξ≥+

+

==)(

11TaireQaire

TaireQairel

ii

l

ii UU

(8)

iQ : Les régions de l’image de référence (Query)

iT : Les régions de l’image cible (Target)

l : Le nombre de paires de régions similaires entre les deux images Q et T La mise en œuvre de cette métrique globale est illustrée sur l’organigramme figure 9. On dispose de deux images Q et T partitionnées en régions. Les vecteurs de couleurs dominantes sont calculés pour chaque région. La première étape consiste à comparer de façon exhaustive toutes les régions de Q à celles de T, afin d’établir une première liste de régions similaires entre Q et T tel que la distance entre régions soit inférieure à un seuil ε (cf. III.2.1.2.). On notera que dans cette liste, une région donnée iQ peut avoir plusieurs régions qui lui sont similaires de T . La similarité entre les deux images est égale ensuite à la fraction de l’aire recouverte par les régions similaires sur l’aire totale des deux images d’après la formule (8) vue ci-dessus.

( ) ( ) )(,

'

1

'

1TaireQaire

TaireQaire

TQSim

l

ii

l

ii

+

+

= ==UU

(9)

L’inconvénient de cette métrique est qu’une région de l’image de requête Q peut être similaire à différentes régions de T, ce qui augmente l’aire recouverte par les régions « cibles ». Ceci peut être gênant si l’image de référence , contient au départ un petit nombre de régions, on aura alors plus de régions de T et la métrique donnera plus de poids à l’image cible ce qui fausse les résultats. La solution serait alors de restreindre les similarités entre régions à une correspondance une à une, c’est à dire qu’une région de Q ne peut être similaire qu’à une et une seule région de T. Il faut donc trouver un deuxième critère pour choisir les meilleures paires de régions. Dans notre cas, on choisira de maximiser le recouvrement.

Page 28: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 28 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Figure 9. Métrique globale dans le cas d’une segmentation des images en régions

( )[ ] [ ] nj mi

jFiFD

.. 1 ,.. 1

',∈ ∈ < ε

Image requ ête Q Régions : mQQ , , 1 K Vect e u rs couleurs domi n antes mFF ,, 1 K

Image cible T Régions : nTT K,1 Vect eurs couleurs domin antes n F F ' ,,1' K

Liste de l paires de régions similaires ( ) ( ) { } l l T Q T Q , , , , 11 K

Deuxième critère pour qu’une région iQ soit assignée à une seule région jT

Maximisation du recouvrement : ( )

+ jTaireiQaireMax

Liste de 'l paires de régions ( ) ( ){ }''11 ,,,, ll TQTQ K avec des correspondances une à une. ( )nml ,min' ≤

Métrique globale permettant de comparer les deux images segmentées

Similarité entre Q et T

Calcul des similarités entre les deux ensembles de régions en utilisant la distance quadratique améliorée

Page 29: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 29 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Description technique I. DESCRIPTION DES REALISATIONS

On rappelle dans cette partie les caractéristiques du descripteur couleur et les métriques associées que l’on va comparer afin de choisir les plus pertinentes pour notre application. On détaillera aussi les séquences de tests utilisées, les programmes d’extraction et de validation du descripteur et les critères d’évaluation des résultats.

I.1. Description des méthodes utilisées

L’espace couleur qui a été choisi pour tester les métriques est YCbCr qui constitue un espace à peu près perceptuellement uniforme auquel une quantification non linéaire simple est associée [Forest 00]. L’autre avantage de travailler dans l’espace YCbCr est qu’il nécessite peu de temps de calcul quant aux transformations entre espaces couleurs, puisque les images d’origine sont codées dans cet espace.

I.1.1) Les couleurs dominantes

L’attribut de couleur dominante qui a été testé est construit grâce à l’algorithme du K-means dont l’implémentation est tirée des travaux de Jean-Ronan Vigouroux [VDL95] travaillant sur le site de Thomson Multimédia à Rennes.

On étudiera l’influence du seuil de fusion, ainsi que du nombre de couleurs dominantes sur l’efficacité de la métrique associée à cet attribut. Dans le cas d’un quadrillage de l’image, on étudiera dans un premier temps l’influence de la taille des blocs, ensuite on prendra en compte la mesure de confiance CM cet attribut.

En ce qui concerne le nombre de couleurs dominantes, il n’y a pas de limite théorique ni pratique quant aux nombres de couleurs dominantes que l’on veut extraire. Néanmoins, comme on veut appliquer le descripteur à des petites régions de l’image, on se limite à 16 couleurs par région.

On a donc un attribut de couleurs dominantes avec les caractéristiques suivantes :

• Nombre de couleurs dominantes N allant de 4 à 16.

• Seuil Td donné en pourcentage : cela veut dire que toutes les couleurs distantes de moins de Td *Dmax1 seront fusionnées.

• Variable qui mesure la répartition spatiale des couleurs dans l’image CM.

On comparera enfin ce descripteur au descripteur global utilisant des histogrammes couleurs.

1 Dmax est la distance euclidienne maximale entre deux points dans l’espace couleur considéré. Par exemple, dans le cube

des couleurs RGB quantifiées sur 256 niveaux, Dmax est égale à la racine carré de 255*255*3.

Page 30: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 30 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

I.1.2) Les métriques On dispose de deux métriques élémentaires qui permettent de calculer la similarité entre deux régions (cf. Etat de l’art : I.3.)

• La fonction quadratique de distance • La fonction quadratique de distance améliorée Application principale : Recherche d’images dans leur globalité

Pour le descripteur couleur obtenu avec un quadrillage de l’image, on a deux métriques globales qui combinent les distances obtenues pour les blocs afin de comparer deux images (cf. Etat de l’art : III.1.2.)

• Comparaison bloc à bloc • Comparaison bloc à voisinage

Pour le descripteur couleur utilisant une segmentation de l’image en régions, on a une métrique globale basée sur une maximisation du recouvrement. Deuxième application : Recherche d’images par requête partielle

On dispose pour cette application d’une métrique qui permet de chercher une ou plusieurs régions d’une image dans une base de données d’images.

I.2. Description des séquences de tests

Toutes ces séquences ont été sélectionnées parmi celles qui sont proposées par MPEG-7 [MPEG 98] pour effectuer des tests. La taille des images est de 288*352. Ces séquences de test sont variées. On peut néanmoins les regrouper en plusieurs catégories :

• Les journaux télévisés : ce sont les séquences « jornaldanoite » et « news » qui sont

respectivement tirées d’un journal portugais et espagnol. Dans ces deux séquences assez longues, mon but a été de retrouver le présentateur télévisé pris dans différentes conditions d’illumination et de prise de vue.

• Les émissions sportives : ce sont les séquences « basket » et « golf ». Dans ces deux séquences, je cherche généralement, à retrouver un certain type de joueur, le terrain ou un certain type d’action (action sur le green pour le golf, action de jeu au basket). De même, au basket, des flashes d’appareils photo fréquents changent brutalement l’illumination des images, ce qui donne des indications quant à la robustesse des métriques aux changements d’illumination.

• Les documentaires : ici, ce sont les séquences « antilope » et « flamant » où je recherche les images où apparaissent soit des antilopes, soit des flamants roses.

• Les dessins animés : c’est la séquence « harmony » qui est étudiée avec une palette de couleurs évidemment beaucoup plus restreinte que les précédentes séquences.

Page 31: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 31 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Pour mettre en évidence l’avantage du descripteur local, j’ai aussi recherché des images de séquences qui présentent une certaine structure, des détails, des motifs sur les objets. J’ai alors retenu les images suivantes :

• Les journaux télévisés : mon but a été de retrouver le présentateur télévisé quand il débute un nouveau sujet, ce qui se traduit par un encadré à sa droite. J’ai aussi cherché à retrouver un grand amphithéâtre avec plusieurs personnes.

• Les émissions sportives : séquence « golf », mon but a été de retrouver les joueurs ayant des tee-shirts à rayures ou bien un joueur qui a un petit mouvement de translation.

• Les documentaires : séquence « Lascaux » où je recherche des objets texturés comme les pierres granitées ou bien un paysage naturel assez structuré (le ciel en haut de l’image et la verdure en bas). Il y a aussi une autre séquence « waste » qui présente plusieurs translations d’objets sur une même image.

L’ensemble de ces images est affiché en annexe 2 et l’ensemble des caractéristiques recherchées au niveau du descripteur couleur local est indiqué pour chaque image. I.3. Principe du programme de validation

Travailler directement sur des séquences vidéos MPEG est difficilement réalisable puisqu’on a un débit de 25 images par seconde, on obtient alors rapidement une base d’images importante sans que pour autant le contenu de ces images ait beaucoup évolué. On va donc découper la séquence vidéo en plans qui sont obtenus en détectant les changements globaux de la luminance de l’image : ainsi, on va associer une image clé à chaque nouveau plan détecté .

Pour chaque image, on va extraire l’attribut couleur qui est ici un ensemble de descripteurs de couleurs dominantes par région. Cette extraction se déroule en plusieurs étapes :

Figure 10. Schéma d’extraction du descripteur couleur local

Avec :

• Le bloc segmentation de l’image en régions désigne soit un quadrillage de l’image soit une segmentation basée sur un critère d’homogénéité couleur ou mouvement.

• Le calcul de la signature couleur est fait pour chaque région de l’image. On commence par une initialisation des centroïdes pour déclencher l’algorithme du

Image originale

Segmentation de l’image en régions

Un descripteurpar région

Calcul de la signature couleur

par région

Boucle sur le nombre de régions NR par image

NR descripteurs par image

Page 32: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet
Page 33: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 33 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

On récupère ainsi une liste de mesures de distances entre les images. A partir de là, un script en Matlab va classer les images par ordre décroissant de similarité, et calculer les différents critères énoncés ci-dessous. Pour cela, il m’a fallu tout d’abord noter dans chaque séquence de test toutes les images qui ressemblent à l’image de référence sélectionnée et établir ainsi ce que l’on appelle « la vérité terrain ».

L’établissement de la vérité terrain est subjectif, toutefois, pour le descripteur local, j’ai essayé de respecter certains critères tel que :

• La position de l’objet dans l’image puisqu’on cherche à garder l’information spatiale.

• Les détails des motifs (textures, rayures…)

La vérité terrain est mise sous la forme d’un tableau (voir annexe 2) où chaque élément correspond à la position de l’image dans la séquence.

Enfin, pour évaluer les performances du descripteur, on compare les images trouvées par requête automatique aux images choisies manuellement.

Deuxième application : Recherche d’images par requête partielle

Pour cette deuxième application, on garde exactement le même programme de validation, mais on mettra à l’entrée du système un ensemble de régions de référence d’ une image donnée et non pas toute l’image. L’utilisateur aura donc a choisir de manière interactive les régions d’intérêts qu’il veut retrouver dans la base de données d’images.

Au niveau du bloc « comparaison » , on utilisera la métrique appropriée à cette application.

Page 34: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 34 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

I.4. Critères d’évaluation

On envisage deux méthodes complémentaires pour évaluer les résultats de la recherche automatique. Une première méthode repose sur des critères numériques d’évaluation qui permettent de tracer des courbes de comparaison entre descripteurs et de réaliser des statistiques sur un grand nombre de séquences. La deuxième méthode repose sur un jugement visuel de la qualité des résultats, en utilisant une interface graphique.

I.4.1) Interface graphique de validation

Cette interface permet dans un premier temps d’afficher les images clés d’une séquence vidéo. Les attributs couleurs sont extraits en même temps que les images, donc on dispose en mémoire d’une base de données de descripteurs. On peut aussi sauver les cartes de segmentation des images clés.

Dans le cas d’une requête globale, on choisit par la suite, l’image de référence et on lance la recherche automatique. Les résultats de la requête sont affichés pour trois descripteurs : le global, le local avec quadrillage et le local avec segmentation de l’image en régions. Les images sont affichées par ordre de similarité décroissant et les distances entre images sont également affichées. Un exemple de ces deux étapes est illustré dans l’annexe 6. Pour l’application de requête partielle, on sélectionne une image de référence comme précédemment, on affiche la carte de segmentation de cette image et l’utilisateur peut choisir interactivement une ou plusieurs régions et lancer une requête sur ces régions d’intérêt. Les résultats s’affichent par ordre croissant de distance de gauche à droite (cf. Annexe 7).

I.4.2) Critères numériques d’évaluation

Afin de pouvoir évaluer les performances du descripteur, il est nécessaire d’utiliser des critères d’évaluation [Forest 00] afin de pouvoir les classer. Ces critères ont été inspirés des différentes contributions MPEG-7 :

NS : le nombre d’images de notre base de données

NK : la profondeur de la recherche, c’est-à-dire le nombre d’images que l’on veut récupérer après classement : ce sont les NK meilleures images (i.e. les plus proches de l’image de référence). Evidemment NK ≤ NS.

NG(q) : le nombre de bonnes images par rapport à l’image q de la séquence.

NR(q) : le nombre de bonnes images parmi les NK meilleures images, par rapport à l’image de référence q de la séquence. (NR ≤ NK)

MR(q) : le nombre d’images manquantes : MR = NG - NR

RR(q) : le taux de bonnes images :NGNRqRR =)(

Page 35: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 35 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

PR(q) : la précision de la recherche : NKNRqPR =)(

A partir de ces critères, on peut calculer le classement moyen des bonnes images qu’il faut trouver, ce qui permet de mieux comparer différents descripteurs entre eux dans le cas où ils renvoient tous deux les mêmes bonnes images.

Soit rank(q) le classement d’une image en sachant que le rang 1 correspond à l’image la plus proche (similarité maximale) de l’image de référence q au sens de la métrique.

Soit AVR(q) le rang moyen normalisé des bonnes images à trouver et on lui associe NAVR qui est une simple normalisation de AVR(q) :

−−−

=

= ∑=

)()(*5.05.0)()(

)()()(

1

qNGNSqNGqAVRqNAVR

qNGkrankqAVR

NG

i

(10)

Dans le cadre des tests effectués, on a opté pour une profondeur de la recherche qui dépend du nombre de bonnes images à trouver. Ainsi, NK dépend de l’image de référence k :

10

)()()( qNGqNGqNK += (11)

I.4.3) Complémentarité des deux méthodes L’interface graphique permet de voir rapidement les résultats de la recherche et de

juger la qualité du descripteur. On peut voir immédiatement l’influence d’un paramètre sur le descripteur au cas par cas. Cependant, les critères numériques restent indispensables pour faire des statistiques et moyenner les résultats sur plusieurs séquences. Un autre point complémentaire est le fait que l’interface permet de mieux interpréter les différences au niveau des critères d’évaluation, de savoir par exemple si une erreur de 0,1 sur le critère NAVR a une grande importance visuellement ou pas.

Page 36: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 36 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Résultats

I. LE DESCRIPTEUR DE COULEURS DOMINANTES I.1. Influence de la précision de la quantification

Pour ce descripteur, l’étude de l’influence de la précision de la quantification revient à étudier l’influence du nombre de couleurs dominantes (nombre de centroïdes) sur les performances de la métrique, ainsi que du choix du seuil de fusion.

Il faut bien préciser que le nombre de couleurs dominantes dont on parle est en fait le nombre de centroïdes utilisés par l’algorithme du K-means. Ensuite il y a une étape de fusion qui va diminuer ce nombre de couleurs dominantes.

Il faut donc trouver un compromis entre ces deux paramètres car plus le seuil de fusion est grand, moins il y aura de couleurs dominantes pour une image.

L’étude de l’influence du nombre de couleurs dominantes a été effectuée l’année dernière en considérant le descripteur comme global c’est à dire appliqué à une image entière. D’après [Forest 00], le nombre de couleurs optimal est de 16 pour un seuil de fusion de 0,07 (1).

D’après le cahier des charges, le descripteur de couleurs dominantes sera utilisé en local sur des petites régions de l’image, on n’a donc pas besoin d’un grand nombre de couleurs dominantes. On rappelle que le nombre de couleurs obtenues à la fin dépend de deux paramètres, le nombre de centroïdes et le seuil de fusion (cf. Etat de l’art : III.1). J’ai alors testé plusieurs seuils de fusion avec 8 et 16 couleurs dominantes. Ces deux valeurs permettent d’avoir une quantification fine avec le K-means et c’est donc le seuil de fusion qui sera décisif pour le nombre de couleurs dominantes à la fin.

Comme on peut le voir sur les images (cf. Annexe 3), un grand seuil de fusion rend la quantification très grossière, même si au départ notre algorithme de K-means effectue une quantification fine de notre image. Ainsi, on se rend bien compte que cette étape de fusion ne doit pas être trop importante, sinon on risque de perdre tout l’intérêt de la quantification adaptative par l’algorithme du K-means qui nous permet d’obtenir une quantification optimale de notre image.

Suite à des tests sur différentes séquences, j’ai opté pour un seuil de 0.03 pour 8 ou 16 couleurs dominantes au départ. Avec un seuil de 0.03, le rapport SNR ( Rapport signal sur bruit) entre l’image initiale et l’image quantifiée varie de 8 à 17 dB selon les séquences.

Le choix définitif du nombre de couleurs dépendra aussi de la métrique que l’on utilisera (voir plus loin I.2) et dans un deuxième temps, de la taille des blocs (voir plus loin III.1).

(1) Il faut rappeler que la valeur du seuil indiquée est écrite sous forme de pourcentage par rapport à la distance maximale

possible entre deux couleurs dans l’espace colorimétrique choisi (YCRCB dans notre cas).

Page 37: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 37 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

I.2. Comparaison des deux métriques élémentaires Pour comparer les deux métriques (cf. Etat de l’art I.3), je me suis basée sur plusieurs critères :

• La plage de variation des distances entre les deux valeurs extrêmes 0 et 1 doit être

suffisamment large. • Le nombre de couleurs dominantes souhaité doit être faible; d’une part on travaille

sur des petites régions et on n’ a donc pas besoin d’un grand nombre de couleurs, d’autre part, plus le nombre de centroïdes augmente, plus le temps de calcul au niveau du K-means augmente.

• Prendre en compte, si cela est possible, les caractéristiques de l’algorithme d’extraction des couleurs dominantes pour la simplification de la métrique ( par exemple la distance minimale entre deux couleurs d’un même vecteur (cf. Etat de l’art I.3.2)).

• Un temps de calcul raisonnable.

La distance quadratique :

- Un grand temps de calcul car il n’y a pas de simplification de la formule.

- Ne tient pas compte de l’algorithme d’extraction utilisé ni de l’étape de fusion des couleurs après le K-means.

+ Les performances de la métrique ne se dégradent pas quand on augmente le nombre de couleurs dominantes au delà du nombre de couleurs dans la région. En effet, même si une couleur est dispersée sur plusieurs classes voisines, la similarité croisée permet de voir qu’elles sont similaires et de les retrouver.

La distance quadratique améliorée :

+ Prend en compte l’étape de fusion ce qui simplifie les calculs.

+ Le coefficient α permet de régler les distances obtenues pour qu’elles aient une grande plage de variation entre 0 et 1.

- Les performances de cette métrique se dégradent quand on augmente le nombre de couleurs au delà du nombre de couleurs réelles dans la région. En effet, si une couleur est dispersée sur plusieurs classes voisines, d’après l’hypothèse de simplification de la formule quadratique (cf. Etat de l’art I.3.2), les classes sont considérées comme distinctes et les coefficients de similarité entre ces dernières sont mis à zéro. Ceci explique pourquoi les résultats sont faussés.

En faisant l’hypothèse que sur des petites régions de l’image on dépasse rarement 8 couleurs dominantes2, on évite le dernier problème évoqué pour la distance quadratique améliorée.

Finalement, on a opté pour la distance quadratique améliorée avec 8 couleurs et α =1.7.

2 MPEG-7 recommande un nombre de couleurs maximum de 7.

Page 38: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 38 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

II. LE DESCRIPTEUR COULEURS DOMINANTES OBTENU AVEC UN QUADRILLAGE DE L’IMAGE II.1. Influence de la taille des blocs et du nombre de couleurs dominantes

Les deux paramètres dépendent l’un de l’autre (cf. Etat de l’art : III.1)

Cette étude a été réalisée en utilisant la métrique globale bloc à bloc. On a pu remarquer que :

• plus la taille des blocs est petite plus le temps de calcul est important. • plus la taille de blocs est petite, plus la distance entre deux images augmente (cf.

Figure 12.). Remarque : La figure 12 montre le résultat de la requête sur la première image à gauche, en utilisant une comparaison bloc à bloc et les images sont affichées par ordre croissant de distance.

Figure 12. Influence de la taille des blocs sur la distance entre images (a) Bloc de taille 32*32 ; (b) Bloc de taille 64*64

Interprétation de l’augmentation de la distance quand on réduit la taille des

blocs et solutions apportées:

• La métrique devient très sensible aux translations ; il suffit que le déplacement de l’objet soit supérieur à la taille du bloc pour qu’on ne le retrouve pas avec une comparaison bloc à bloc. ⇒ Il faudrait utiliser une comparaison bloc à voisinage pour augmenter la robustesse vis à vis des petites translations tout en gardant l’information spatiale.

• L’algorithme du K-means converge moins bien.

⇒ Il faut soit, diminuer le nombre de centroïdes au départ pour éviter de dépasser le nombre de couleurs réelles, soit augmenter le nombre d’itérations pour laisser le temps à l’algorithme de bien converger sinon il s’arrête dans un état aléatoire, loin de la quantification optimale.

(a)

(b)

Page 39: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet
Page 40: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 40 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

En fait, l’utilisation des blocs 32*32 augmente la distance par rapport aux blocs 64*64 certes, mais comme on cherche à classer les images de la recherche automatique par ordre croissant de distance, cette augmentation est par conséquent relative et en moyenne les résultats sont meilleurs avec les blocs de 32*32.

⇒ Finalement, on opte pour des blocs 32*32 avec 8 couleurs dominantes par bloc.

II.2.Influence de la métrique globale sur les critères d’évaluation

II.2.1) Détermination des coefficients de pondération de la métrique globale bloc à voisins

Chaque bloc de l’image de référence est comparé à son bloc équivalent dans la

deuxième image et au huit voisins de ce dernier (cf. Etat de l’art III.1.2.2). Des coefficients de pondération permettent de donner plus de poids au bloc central par rapport à son voisinage : 3/4 pour le centre et 1/32 pour chacun des huit voisins (cf. Figure 14.). En outre, on donne plus de poids aux blocs centraux d’une image qu’aux blocs de bords. Ainsi, les blocs de contour sont affectés d’un coefficient de pondération de 1 alors que les blocs centraux ont un coefficient de pondération égal à 3.

Figure 14. Comparaison bloc à voisinage - coefficients de pondération

En comparant les mêmes images entre elles, le calcul bloc à voisinage ne renvoie pas une distance nulle puisqu’on prend en compte des blocs voisins qui ne ressemblent pas au bloc central. On n’a plus une distance au sens mathématique. Les coefficients de pondération ont été choisis de telle façon qu’ils diminuent au maximum la distance entre deux images semblables (en diminuant les coefficients de pondération des blocs voisins), tout en gardant la robustesse vis à vis des petites translations d’objets.

1

3 3

3 3

1 1

1

1

1/32 1/32 1/32

1/32

1/32 1/32 1/32

1/32 3/4

Métrique distancequadratique simplifiée

Image de référence Autre image de la séquence

Page 41: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 41 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

II.2.2) Comparaison des deux métriques globales La figure 13 permet de comparer les deux métriques globales utilisées : bloc à bloc et bloc à voisins (cf. Etat de l’art III.1.2).

Influence de la taille des blocs et de la métrique globale sur le critère NAVR

00.010.020.030.040.050.060.070.080.09

0.1

64*64

bloc

abloc

64*64

bloc

avois

in

32*32

bloc

abloc

32*32

bloc

avois

in

Critère NAVR

Figure 15. Influence de la taille des blocs et de la métrique globale sur le critère NAVR

On peut remarquer que sur des blocs de 64*64, le fait de comparer bloc à voisins dégrade les résultats en augmentant le NAVR. Ceci est dû au fait que la taille d’une image est de 288*352 et par conséquent, en la quadrillant, on obtient 4*5 blocs. Les blocs sont trop grands et pas assez nombreux et donc d’un bloc à l’autre il y a un grand changement du contenu couleur. Par contre, dans le cas des blocs de 32*32, la comparaison bloc à voisins donne sensiblement les mêmes résultats. Le plus important est que cette métrique est beaucoup plus robuste aux petites translations d’objets et aux changements de zoom. ⇒ Par conséquent on opte pour une métrique globale bloc à voisins sur des blocs de 32*32. II.3. Influence de la mesure de confiance sur les critères d’évaluation La mesure de confiance CM nous donne une information sur la dispersion spatiale d’une couleur. Plus la couleur est condensée dans une région, plus elle est fiable et plus la variable CM augmente. Dans la formule suivante de distance élémentaire entre deux descripteurs (cf. Etat de l’art I.3.3), on utilise comme poids de pondération : W1=1/3 et W2 =2/3.

Page 42: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 42 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

DiffDCWDiffCMWDDDifference __),( 2121 ∗+∗= (12)

CM_Diff étant la différence absolue entre les variables CM des deux descripteurs D1 et D2 et DC_Diff = D(F1, F2), la distance quadratique améliorée entre deux descripteurs.

L’intégration de la mesure de confiance améliore les résultats, prenant l’exemple simple de la figure suivante :

Figure 16. Intérêt de la mesure de confiance

Le fait de rajouter la mesure de confiance permet de détecter que la couleur est dispersée dans l’image de droite et on va donc distinguer ces deux images. On va étudier l’influence de cette métrique élémentaire avec la mesure de confiance sur la métrique globale.

Influence de la mesure de confiance sur le critère NAVR

00.050.1

0.150.2

0.250.3

0.350.4

0.45

32*32blocavoisin

mesure deconfiance,

b_32,blocabloc

mesure deconfiance,

b_32,blocavoisin

jornaldanoite2_ref162news_ref129

lascaux_ref33

lascaux_ref16

golf_ref44

Figure 17. Influence de la mesure de confiance sur le critère NAVR

Difference(D1,D2)

Page 43: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 43 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

On peut remarquer que les résultats de la métrique bloc à voisins sont améliorés avec la mesure de confiance. Cependant, les résultats de la métrique bloc à bloc sont dégradés avec la mesure de confiance qui donne une information supplémentaire sur la couleur dans le bloc et qui rend par conséquent cette métrique globale encore plus discriminante, car elle devient très sensible aux translations d’objets. ⇒ On opte par conséquent pour une métrique élémentaire avec une mesure de confiance et on garde la métrique globale bloc à voisins. II.4. Bilan du descripteur local utilisé

Finalement, on aboutit à un attribut de couleurs dominantes local « optimal » qui donne d’après nos tests les meilleures performances dans le cadre de notre application de recherche par similarité. Il faut cependant relativiser ces résultats puisque notre base de données d’images était limitée. Le descripteur local final a les caractéristiques suivantes :

Le descripteur lui-même : • Nombre de couleurs dominantes : 8 couleurs.

• Descripteur normalisé : ∑=

=N

jjp

11

• Seuil Td donné en pourcentage : Td = 3%.

• Variable qui mesure la répartition spatiale des couleurs dans l’image CM.

Les métriques associées et la taille des blocs utilisée

• Taille des blocs : 32*32 • Métrique élémentaire : la distance quadratique améliorée avec mesure de

confiance

• Métrique globale utilisée : comparaison bloc à voisins II.5. Comparaison avec le descripteur global

On n’attend pas le même comportement des deux descripteurs, global et local; on veut

que le descripteur global soit robuste aux translations, aux changements d’échelle.

Page 44: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 44 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Mais par définition, ce descripteur n’incorpore aucune information sur la position spatiale des objets. Par conséquent on ne peut pas différencier deux images distinctes ayant le même histogramme couleur. D’où l’intérêt du descripteur local qui garde une information spatiale sur la position des objets. Par contre cet avantage le rend plus sensible aux changements dans l’image.

Donc, pour effectuer cette comparaison, des séquences ont été spécialement choisies pour mettre en évidence l’avantage du descripteur local de couleurs sur certains types d’images :

- objets texturés ou présentant des motifs

- des images où l’on veut retrouver un objet à une position précise.

- des images naturelles assez structurées : le ciel en haut et la verdure en bas de l’image.

Et on voit bien, d’après la figure 18, que le descripteur local améliore les résultats dans ces cas là.

Comparaison des descripteurs

00.10.20.30.40.50.60.70.80.9

1

histogramme couleur couleurs dominantes32*32 blocabloc

Critère RRCritère NAVR

Figure 18. Comparaison de l’histogramme couleur avec le descripteur local de couleurs dominantes

La figure 19 présente des séquences où l’on cherche à retrouver la présentatrice du journal télévisé avec un encadré à sa droite ou le sommaire du JT qui se traduit par des grands encadrés ou bien un joueur de golf avec un pull rayé . Les résultats sont nettement meilleurs avec le descripteur local.

Page 45: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 45 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Figure 19. Comparaison visuelle : Avantage du descripteur couleur local

(a) image référence News 129 ;(b) image référence Golf 29 ; (c) image de référence Jornadanoite2_0

Sur d’autres images, où l’on cherche un objet central par exemple (avec une couleur dominante assez présente tel que le vert pour le gazon), les résultats sont meilleurs pour le

(a)

(b)

(c)

Page 46: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 46 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

descripteur global qui est totalement robuste aux translations et aux changements d’échelle (cf. Figure 20). La couleur du fond parasite les résultats pour le quadrillage.

Figure 20. Comparaison visuelle : Avantage du descripteur couleur global image référence Harmony 26

Jusqu’à maintenant, on a comparé les deux descripteurs en se basant sur les résultats des requêtes automatiques. Pour conclure cette comparaison, il faut ajouter que le descripteur « histogramme couleur » nécessite 15 à 20 fois plus de place en mémoire pour être stocké. Quant à l’attribut de couleur dominante, il nécessite des temps de calcul pour l’extraire qui sont beaucoup plus importants.

Page 47: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 47 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

III. LE DESCRIPTEUR COULEURS DOMINANTES OBTENU AVEC UNE SEGMENTATION DE L’IMAGE EN REGIONS

III.1. Comparaison des différents algorithmes de segmentation Les résultats sont présentés dans l’annexe 5. Avec l’algorithme de partage des eaux, on obtient une sur-segmentation des régions. Avec l’algorithme de fusion couleur, RSST, on fixe à l’avance le nombre de régions que l’on veut obtenir. Mais l’inconvénient de cette méthode est que si le nombre fixé de régions est trop petit, la fusion devient arbitraire et ne correspond plus au contenu de l’image. Avec l’algorithme d’estimation du mouvement dominant, on obtient grossièrement les différentes régions de l’image, on n’a pas une grande précision sur les contours. Cet algorithme est efficace si la scène présente un objet ou un personnage central, on obtient alors deux régions qui correspondent au fond de l’image et à l’objet en déplacement. L’algorithme utilisant le RSST et la fusion de régions par le mouvement, renvoie des régions plus significatives que l’algorithme précédent. Cependant le résultat de la segmentation sur une séquence d’images ne peut être fiable qu’à partir de la 5ème image. Pour cet algorithme, on peut rentrer, en paramètre, la taille minimale que peut avoir une région ce qui nous évite d’avoir une sur-segmentation. En agrandissant la taille minimale, l’algorithme se stabilise plus rapidement mais le nombre de régions obtenues diminue. Il faut trouver un compromis entre taille de régions, nombre de régions et stabilité de l’algorithme. D’après les cartes de segmentation, le choix est à faire entre le RSST et le dernier algorithme. Le RSST : - renvoie des régions colorées qui correspondent soit aux objets de l’image, soit à

des parties de couleurs uniformes de l’objet. - Le temps de calcul est raisonnable. - Un paramètre à régler

L’algorithme utilisant le RSST et la fusion de régions : - renvoie des régions colorées qui correspondent aux différents objets. - Il nécessite un grand temps de calcul (*). - Un compromis à trouver entre trois paramètres

(*) D’une part, le deuxième algorithme utilisant le RSST est beaucoup plus lent. D’autre part, il utilise une estimation de mouvement et doit donc être lancé sur toute la séquence source pour récupérer par la suite la segmentation pour les images clés alors que le RSST peut être appliqué sur une image donnée indépendamment du critère temporel. Finalement, on opte pour l’algorithme RSST.

Page 48: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 48 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

III.2. Application de requête globale : La métrique globale III.2.1) Le seuil de fusion au niveau du RSST

Il faut tout d’abord régler le seuil de fusion au niveau de l’algorithme de

segmentation. D’après (Etat de l’art II.1.1), ce seuil constitue un poids de lien maximal au delà duquel on ne fusionne plus les régions. Plus le seuil de fusion est petit , plus la segmentation est fine. Cependant, si le seuil de fusion entre régions est trop faible, on obtient beaucoup de régions colorées et l’appariement des régions de deux images devient presque aléatoire et très parasité par les petites régions. Au contraire, si le seuil de fusion est grand, on aura une segmentation grossière de l’image et on peut perdre les objets de l’image. J’ai testé deux seuils de fusions : coût1=3* 8*8 qui correspond donc à un maximum de 8 niveaux de gris entre deux régions, pour chaque composante de l’espace couleur. Le deuxième coût est égal à coût2 = 3 *12 *12 . Les résultats de segmentation avec les deux seuils sont présentés dans l’annexe 8 pour différentes séquences. On peut remarquer que : - La segmentation avec un seuil de 3*12*12 ( 12 niveaux de gris maximum entre deux régions) décroche pour certaines images. On perd alors la notion d’objets dans l’image. - Le nombre de régions varie beaucoup d’une séquence à une autre pour le même seuil de fusion. Par exemple on peut avoir 7 régions pour la séquence « Golf » contre 90 régions pour la séquence « Harmony » pour un seuil de 3*8*8 et donc le traitement sera plus ou moins lent selon les séquences.

III.2.2) Compromis entre le seuil de fusion au niveau du RSST et le seuil de similarité entre régions

On rappelle que le seuil de similarité entre régions ε intervient dans la métrique

globale pour établir la première liste de régions similaires. En effet, pour que deux régions soient similaires il faut que la distance quadratique améliorée entre leurs vecteurs de couleurs dominantes respectifs: ( )21, FFD soit inférieure à un seuil ε (cf. Etat de l’art III.2.1.2.).

On a vu précédemment (cf. Résultats I.2.) que les résultats avec la distance quadratique améliorée se dégradent si le nombre de couleurs dominantes (8 dans notre cas) est très supérieur au nombre de couleurs réelles. Cet inconvénient nécessite de trouver un compromis entre la finesse de la segmentation et le seuil de similarité. En effet : - Si la segmentation est grossière, on obtient des régions avec beaucoup de couleurs dominantes. La distance quadratique améliorée entre régions est alors bien représentative et on peut alors mettre un seuil bas de similarité entre régions. - Par contre, si la segmentation est fine, on aura un petit nombre de couleurs réelles par région ( d’autant plus qu’on utilise un critère d’homogénéité couleur pour la segmentation). Une même couleur nuancée sera alors dispersée sur plusieurs classes voisines et la distance renvoyée entre régions sera grande. Il faut alors mettre un seuil de similarité régions plus grand que le cas précédent mais pas trop grand sinon il y aura beaucoup de régions parasites. Après plusieurs essais, je suis arrivée au compromis suivant :

Page 49: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet
Page 50: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 50 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Figure 22. Influence du facteur d’échelle :(a) métrique brute ; (b) métrique améliorée

Dans le cas de la métrique brutale, dans l’image de référence, le fond vert derrière le joueur de golf est assigné à des images entières de verdure. La quatrième image qui apparaît est aussi due au fait que la casquette du joueur est assignée au pull du deuxième joueur et au contraire le pull du premier est assigné à la casquette du second, pour éviter ces problèmes le fait de limiter le facteur d’échelle permet d’éviter d’assigner des petites régions à de trop grandes régions et vice versa.

On peut voir sur la figure 23, l’influence de la limitation des translation des régions.

Figure 23. Influence de la limitation des translations:(a) métrique brute ; (b) métrique + facteur d’échelle ;(c) métrique+facteur d’échelle+limitation translation

On voit bien que les résultats sont nettement améliorés avec l’ajout de ces deux paramètres.

Le fait de donner plus de poids aux régions centrales de l’image n’a pas été réalisé en pratique.

(a) (b) (c)

Page 51: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 51 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

III.2.3.2) Inconvénient des régions de couleur presque uniforme Le problème apparaît d’autant plus qu’on utilise un algorithme de segmentation

selon un critère d’homogénéité couleur. En effet, les régions sont pauvres en couleur et contiennent par conséquent des nuances d’une même couleur et les résultats de la distance quadratique améliorée se dégradent dans ces cas (cf. ci dessus III.2.2). Ce problème est présent dans toutes les images mais on arrive à le cerner sur des images à une région. On peut voir, par exemple, sur la figure 24, une image de référence qui représente un feuillage, les deux autres images de feuillages ne sont pas retrouvées dans le cas d’une segmentation en régions.

Figure 24. Inconvénient des régions de couleur presque uniforme

(a) descripteur couleur par quadrillage ; (b) descripteur couleur par régions segmentées En effet, la distance renvoyée entre les images est égale à 0.6 minimum. Il faut donc

augmenter le seuil de similarité régions mis à 0.4 auparavant. On décide donc de mettre le seuil de similarité à 0.73. Cependant, ceci rajoute beaucoup de paires de régions « similaires » dans la première liste qui ne le sont pas forcément et le choix des bonnes paires de régions similaires devient aléatoire. Il a donc fallu trouver un autre critère pour sélectionner les bonnes paires de régions similaires mis à part le maximum de recouvrement ( cf. Etat de l’art III.2.2.1). J’ai proposé la métrique suivante :

( )( ) ( ) ( )( ) ( ) 3

231,1 2121 ==

+

+∗+−∗ wetwavec

TAireQAire

TAireQAirewTQDwMax ji

ji (13)

( )ji TQD , étant la distance quadratique améliorée. Cette métrique prend toujours en compte le maximum de recouvrement, mais inclut cette fois la similarité entre régions. Au lieu d’avoir deux étapes : un premier filtrage avec un seuil

3 Ce seuil permet de faire un premier filtrage des paires de régions, ce qui permet de réduire le temps de calcul. Mais on peut

se passer de ce seuil puisque le critère de sélection prend en compte la mesure de similarité entre régions.

(a) (b)

Page 52: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 52 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

de similarité bas et un maximum de recouvrement dans un deuxième temps, cette métrique perme de combiner les deux points. Par conséquent la métrique globale inclut aussi les mesures de similarités en plus du maximum de recouvrement et on a:

( )( )( )

( ) )('

,1

,

'

1

'

1

'

1TaireQaire

TaireQaire

l

TQD

TQSim

l

ii

l

ii

l

iii

+

+

= ===∑ UU

(14)

'l étant le nombre de bonnes paires de régions similaires entre Q et T.

III.2.3.3) Comparaison des deux métriques globales proposées

On rappelle les caractéristiques des deux métriques globales que l’on va comparer : Métrique 1 :

- seuil de similarité entre régions à 0.4 - Critère de sélection des « bonnes »paires de régions similaires : maximum de

recouvrement. - zoom = 4 - limitation des translations des régions au 1/6 de l’image. - Métrique globale : fraction de l’aire couverte par les régions similaires sur l’aire totale

des deux images. Métrique 2 :

- seuil de similarité entre régions à 0.7 - Critère de sélection des « bonnes »paires de régions similaires : maximum de

recouvrement et similarité entre régions en utilisant des coefficients de pondération. - zoom = 4 - limitation des translations des régions au 1/6 de l’image. - Métrique globale : fraction de l’aire couverte par les régions similaires sur l’aire totale

des deux images et mesure de similarité. La métrique 2 nécessite un temps de calcul plus grand. D’une part, le seuil de similarité est plus élevé, on a donc plus de paires de régions à traiter. D’autre part, le critère de sélection et la métrique globale nécessitent plus d’opérations arithmétiques. Les résultats des requêtes globales sont présentés en annexe 9. Pour la plupart des séquences, la métrique 2 améliore sensiblement les résultats. L’amélioration est spectaculaire sur la séquence « Tennis » où on arrive à bien retrouver le joueur en vert alors que la première métrique ne permet pas de retrouver les bonnes paires similaires à cause du problème évoqué dans le (III.2.3.2). On choisira, par conséquent de garder la métrique 2 comme métrique globale du descripteur local sur régions segmentées.

Page 53: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 53 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

III.2.4) Résultats de la métrique globale améliorée

III.2.4.1) Comparaison avec les autres descripteurs couleurs développés

On va comparer les résultats du descripteur couleur avec segmentation de l’image avec ceux du descripteur local avec quadrillage et avec le descripteur global utilisant les histogrammes couleurs. Les résultats sont présentés et commentés en annexe 10.

Globalement, les deux descripteurs locaux améliorent les résultats de la requête automatique par rapport au descripteur global. En comparant les deux descripteurs locaux, on voit que sur quelques séquences, les résultats sont améliorés avec le descripteur à régions segmentées. Sur la séquence « Tennis » où l’on cherche des joueurs, on peut voir la nette amélioration des résultats avec la segmentation en régions. Cependant, ce descripteur local avec régions dégradent les résultats dans le cas d’images en plans larges ou d’images texturées, où il n’y a pas forcément de détails à voir et où il vaut mieux regarder l’image dans sa globalité (cf. Tennis 22, Lascaux 32). De plus ce dernier descripteur nécessite un plus grand temps de calcul pour deux raisons principales :

• Il nécessite un algorithme de segmentation en régions. • La métrique globale utilisée nécessite un grand temps de calcul :

- Le seuil de fusion choisi au niveau du RSST donne une segmentation fine de l’image

et donc un grand nombre de régions à traiter qui peut atteindre 90 régions pour certaines séquences.

- Le grand seuil de similarité entre régions, fixé à 0.7, augmente le nombre de paires de régions similaires de la première liste ce qui nécessite un plus grand temps de calcul.

Finalement pour cette application de requête globale, bien que ce descripteur améliore nettement les résultats sur quelques séquences, j’opterai pour le descripteur avec quadrillage pour des raisons de temps de calcul d’une part, d’autre part il permet d’avoir un descripteur local sans dégrader pour autant les résultats dans le cas des plans larges ou des images texturées.

Page 54: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 54 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

III.3. Application de requête partielle

III.3.1) Principe On cherche, dans cette application, à retrouver dans une base de données d’images

des régions d’intérêt d’une image de référence. On sait calculer la mesure de similarité entre deux vecteurs de couleurs dominantes de deux régions (cf. Etat de l’art I.3.). On cherche maintenant à établir une métrique globale qui permet de comparer un ensemble de régions de référence à des images segmentées. Les régions de référence sont de formes quelconques et il faut être capable de retrouver d’une image à l’autre une région qui a changé de position , ou bien qui a été grossie…

III.3.2) Métrique globale

Supposons que l’on dispose de deux images Q (Query) et T (Target). L’image Q est

l’image de référence et l’image T étant l’image cible. Chacune est composée respectivement des régions suivantes : nTTetmQQ KK ,1,,1 .

rQQ ,,1 K étant les régions de référence choisies par l’utilisateur avec mr ≤<0 . La mise en œuvre de cette métrique se déroule en trois étapes comme pour

l’application de requête globale (cf. Figure 9). Le seuil de similarité entre régions est fixé à 0.7. Ce seuil permet d’avoir une première liste de paires de régions similaires. On choisit, dans un deuxième temps, les « bonnes » paires de régions sur un critère de maximisation de la similarité. Ce critère de sélection ne prend pas en compte la taille des régions. On obtient alors une deuxième liste de « bonnes » paires de régions similaires

( ) ( ){ }''11 ,,,, rr TQTQ K rravec ≤< '0 .

Enfin, la métrique globale caractérise la similarité entre l’ensemble de régions de référence et une image cible. J’ai proposé une métrique afin de répondre aux critère suivants :

- Les régions de référence ne sont pas toutes forcément assignées à des régions

cibles. Donc plus il y a de régions iQ assignées , plus la similarité renvoyée doit être grande.

- Sur un ensemble de régions de référence, on doit donner plus d’importance aux

grandes régions.

- Dans le cas d’une seule région de référence, la métrique globale doit revenir à une simple maximisation de la mesure de similarité entre régions, utilisant la distance quadratique améliorée.

On aboutit alors à la métrique suivante :

Page 55: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 55 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

(15) R : L’ensemble des régions de référence constitué de rN régions. I : Une image de la séquence.

iQ : une région de référence et jT une région de l’image I .

'rN : nombre de régions de R assignés = nombre de paires de régions similaires dans la deuxième liste

III.3.3) Compromis entre le seuil de fusion au niveau du RSST et le seuil de similarité entre régions

Pour cette application, on choisira un coût de fusion du RSST égal à 3*12*12.

En effet, le coût à 3*8*8 choisi pour l’application de requête globale fournit une segmentation fine de l’image, ce qui n’est pas très pratique pour choisir quelques régions de référence. Les régions sont trop petites pour pouvoir cliquer dessus avec la souris et il faut un grand nombre de région pour caractériser un objet.

Pour le seuil de similarité entre régions on garde le même seuil à 0.7. III.3.4) Résultats de la métrique globale améliorée

Les résultats de la requête partielle sont présentés en annexe 11.

On peut remarquer que dans la plupart des cas, le fait d’augmenter le nombre de régions de référence permet d’affiner la recherche et renvoie donc de bonnes images. Toutes fois , il faut que les régions rajoutées soient bien caractéristiques d’un objet précis de l’image comme dans le cas de « Harmony 9 » ou bien « News 95 » ou bien des régions du fond qui rendent la recherche bien discriminante. On peut voir par exemple dans le cas de la séquence « Lascaux » , si on choisit des régions assez éloignées : verdure et ciel, les résultats sont dégradées. On peut voir aussi que sur des séquences comme « Tennis », on peut retrouver des joueurs sur un fond différent. Néanmoins, il faut relativiser ces résultats parce que notre base de données est restreinte aux images clés d’une séquence vidéo. Il faudrait tester cette application sur de grandes bases de données. Remarque : Pour améliorer cette métrique, on pourrait prendre en compte la taille des régions au niveau de la sélection des paires similaires qui se fait juste sur un critère de maximisation de la similarité.

( )( ) ( )[ ]( )

( )

( )

=∑∑==

RAire

QAire

RAire

QAireTQdistIRSim

rr N

ii

N

iiji

''

11 **,1

),(

Page 56: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 56 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Conclusion

___________

Le but de ce stage était de proposer un descripteur de couleurs local en utilisant les couleurs dominantes sur des petites régions de l’image afin de garder l’information spatiale. On a utilisé dans un premier temps un quadrillage de l’image et on a essayé d’améliorer les performances du descripteur obtenu en réglant les différents paramètres tel que le nombre de couleurs dominantes, le seuil de fusion, la taille des blocs et la mesure de confiance. On a abouti à un descripteur « optimal » qui donne les meilleurs résultats pour l’application de recherche globale.

Toujours dans le cadre de l’application de recherche globale, on a implémenté dans un deuxième temps un descripteur local qui extrait les vecteurs de couleurs dominantes sur des régions de formes quelconques en utilisant des cartes de segmentation colorées. On aboutit aussi à une métrique globale améliorée qui donne améliore les performances.

On a ensuite comparé les deux descripteurs locaux et le descripteur global basé sur les histogrammes couleurs. On en a déduit que les descripteurs locaux sont mieux adaptés à des images structurées, à la recherche de détails des objets. Ils dégradent les résultats pour des plans larges par exemple où il vaut mieux prendre l’image dans sa globalité.

Vu que le deuxième descripteur local avec régions est coûteux en temps de calcul pour toute une image, on a pensé à l’utiliser pour une autre application de requête partielle où l’on effectue une recherche sur quelques régions d’intérêt d’une image de référence.

Pour cette application, on a aussi proposé une métrique globale qui donne de bons résultats. Néanmoins, il faut un peu relativiser les différents résultats obtenus puisque nos expériences se limitaient à une base d’images limitée en nombre.

Les différentes applications proposées jusqu’ici ont un but précis : classer les images par similarité. Cependant, il y a bien d’autres perspectives pour l’indexation d’images. La plus évidente est la recherche d’images fixes dans une base de données très large tel qu’Internet le propose. L’autre grand défi qui rejoint celui de l’appariement concerne la modélisation de la variabilité des données. Le seul domaine où quelques résultats ont déjà été publiés est celui de la reconnaissance de visages, et aussi celui de la détection de panneaux routiers. Une dernière perspective peut par exemple être celle de la structuration de vidéos qui reprend le principe de la modélisation de la variabilité des données. Les applications de ce système sont nombreuses : fabrication de résumés, navigation rapide dans une vidéo offrant plus de possibilités que la seule avance rapide, mise au point de vidéos cliquables, voire mais cela reste encore lointain, indexation de vidéos dans une médiathèque.

Page 57: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 57 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Bibliographie _____________

[Avrithis 99] Y.S. Avrithis, A.D. Doulamis, N.D. Doulamis,

S.D.Kollias.”A Stochastic Framework for Optimal Key Frame Extraction from MPEG Video Databases”, Computer Vision and Image Understanding, Vol 75, July/August, pp 3-9,1999.

[Carson 99] C. Carson, M. Thomas, S. Belongie, J.M. Hellerstein, J. Malik. “Blobworld: A system for region-based image indexing and retrieval”. Proc. Int.Conf.Visual.Inf.Sys.1999.

[Chupeau 00] B. Chupeau, E. François, “Region-based motion estimation for content-based video coding and indexing”, Proc. Int. Conf. on Visual Communications and Image Processing 2000, Perth, Australia, June 2000.

[Cocquerez 95] J.-P Cocquerez, S. Philipp. “Analyse d’images : filtrage et segmentation “. MASSON 1995, 457 pages.

[Deng 99] Y. Deng, B.S. Manjunath.” An efficient low -dimensional color indexing scheme for region-based image retrieval ”. ICASSP’99.

[Deng 99] Y. Deng, B.S. Manjunath. “Tools for texture/color based search of images”. SPIE, Volume 3016,pages 496-506.

[Flickner 95] M.Flickner et al. : “Query by Image and Video Content : The QBIC System “, IEEEE Computer, Special Issue on Content Based Retrieval, September 1995, pp. 23-32.

[Forest 00] R. Forest. “Indexation Vidéo par le contenu : Extraction d’attributs de couleur d’une image “ . Rapport de stage de fin d’études, ENSPS,2000.

[François 94] E.François, B. Chupeau. “ Segmentation d’un champ de mouvement dense. Application au codage très bas débit “ . CCETT, journées sur les « nouvelles techniques pour la compression et la représentation des signaux audiovisuels » 12-13/1/94.

Page 58: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 58 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

[Hafner 95]

J.Hafner, H.S. Sawhney, W.Equitz, M.Flickner and W.Niblack. “Efficient Color Histogramm Indexing for Quadratic Form Distance Functions”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 17, no 7, 729-736, July 1995.

[Lloyd 82] S.P. Lloyd. ”Least squares quantization in PCM ”. In IEEE Transactions on information theory, vol. 28, pp 127-135, March 1982.

[MacQueen 67] J. MacQueen. “Some methods for classification and analysis of multivariate observations”. In Proceedings of the Fifth Symposium on Mathematical Statistics and Probability, pages 281-297, University of California Press, 1967.

[Meyer 90] F. Meyer, S. Beucher. “Morphological segmentation”. Journal of Visual Communication and Image Representation ,vol1,pp.21-46,1990.

[MPEG 01] MPEG Requirements Group, ”Overview of the MPEG-7

Standard”, Doc. ISO/MPEG N4031, MPEG Singapore Meeting,2001. (http://www.cselt.it/mpeg/standards/mpeg-7/mpeg7.htm)

[MPEG 98] MPEG Requirements Group, ”description of MPEG-7

Content Set”, Doc. IOS/MPEG N2467, MPEG Atlantic City Meeting,1998.

[Mulroy 97] P.J. Mulroy. “Video content extraction :Review of current

automatic segmentation algorithms ”.Proc. Workshop on Image Analysis for multimedia Interactive Services, Louvain-la-Neuve,Belgium,1997.

[Natsev 99] A. Natsev, R. Rastogi, K. Shim. “WALRUS: A similarity

Retrieval Algorithm For Image databases ”. Proc CAN SIGMOD Int. Conf. on Management of Data, Philadelphia, June 1999.

[Odobez 95] J.M.Odobez , P.Bouthemy, ”Robust multiresolution

estimation of parametric motion models ”, J. of Visual Comm. And Image Representation, Vol 6,No. 4, December 1995.

[VDLynden 95] T.VanDer Lynden. “Indexation automatique de séquences“ . Rapport de fin d’étude, Juin 1995.

Page 59: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 59 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Annexes

Page 60: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 60 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 1 Description des séquences de tests

____________

Séquence basket Séquence golf

Séquence harmony Séquence news

Remarque : Ces images ont été utilisées sur la station Sun, pour tester les paramètres du descripteur de couleurs dominantes et les métriques associées. Sous Visual C++ , le programme qui génère les images clés d’une séquence donnée a été modifié donc on n’a plus exactement les mêmes images de référence. Cependant la requête automatique a été lancée sur des images très semblables à celles-ci , en gardant ces mêmes séquences.

Page 61: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 61 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 2 Les séquences de tests adaptées au descripteur local de

couleurs dominantes par quadrillage de l’image ____________

Image de référence/ Liste des positions des images

qui lui sont similaires Caractéristiques recherchées

Séquence Golf Position 29

29 ;30 ;44 ;40

- Un joueur de golf portant un tee-Shirt rayé. - Gros plan, l’objet prend une grande place dans l’image

Séquence Golf Position 44

29 ;30 ;44 ;40

- Un joueur de golf portant un tee-Shirt rayé. - Le zoom est plus faible que l’image précédente donc elle nous permet de tester la robustesse aux zooms

Séquence Golf Position 20

20 ;22 ;25

- La personne bouge dans l’image et le fond reste le même, ceci nous permet de tester la robustesse aux translations

Séquence Waste Position 7

7 ;5 ;11 ;13 ;15

- Deux objets qui bougent dans l’image : la personne et la poubelle. - Petit changement du fond

Séquence Jornaldanoite2 Position 0

0 ;1 ;2 ;3 ;4 ;62 ;63

- Sommaire du journal télévisé, on recherche l’encadré général indépendamment du sujet traité.

Page 62: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 62 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Séquence Jornaldanoite2 Position 162

161 ;162 ;163 ;164 ;165 ;166 ;167 ;168 ;169 ;170 ;171 ;172

- Amphithéâtre avec la présence de personnes : des couleurs parasites qui peuvent gêner le descripteur global pour reconnaître le lieu.

Séquence News1 Position 129

41 ;79 ;95 ;129 ;166 ;184

- Présentateur télévisé avec un encadré à sa droite sur l’image (information de structure). Ceci nous permet de rechercher tous les débuts de sujets dans un JT.

Séquence Lascaux Position 16

10 ;11 ;12 ;13 ;14 ;15 ;16 ;17

- Image structurée : ciel en haut et verdure en bas de l’image. - Image texturée qui permet de tester la mesure de confiance

Séquence Lascaux Position 33

31 ;32 ;33 ;36

- Image texturée qui permet de tester la mesure de confiance

Page 63: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 63 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 3 Influence du seuil de fusion

________________

image initiale seuil à 0,03 - 14 cols – SNR ≈ 13dB

seuil à 0,05 -10 cols - SNR ≈12dB seuil à 0,07- 4 cols – SNR ≈ 10dB

image initiale seuil à 0,03 - 11 cols – SNR ≈ 17dB

seuil à 0,05 - 5 cols – SNR ≈ 15dB seuil à 0,07- 3 cols – SNR ≈ 14 dB

Page 64: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 64 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

image initiale seuil à 0,03 - 16 cols –SNR ≈ 8 dB

seuil à 0,07-11 cols – SNR ≈ 6 dB seuil à 0,1 - 3 cols – SNR ≈ 5 dB

image initiale seuil à 0,03 -14 cols –SNR ≈ 14dB

seuil à 0,05 -9 cols – SNR ≈ 9dB seuil à 0,03 - 8 cols – SNR ≈ 8dB

Figure 25. Influence du seuil de fusion sur le descripteur à 16 couleurs dominantes

Page 65: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 65 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 4 Distance quadratique améliorée

_________________

La distance quadratique appliquée aux couleurs dominantes s’écrit :

( ) ( ) ( )2'

1'

2'

1'

212 ','' FFAFFFFD T −−= avec

=

=

2

1

,2

.

.

2,2

1,2

.

.

2'

.

.

,1

.

.

2,1

1,1

1'

0

0

0

0

N

N

p

ppFetp

pp

F (1)

En ignorant tous les termes nuls et en réécrivant la distance quadratique, on a :

( ) ∑∑∑∑∑∑= == == =

−+=1 22 21 1

1 1,2,12,1

1 1,2,22,2

1 1,1,11,121

2 2',''N

i

N

jjiji

N

i

N

jjiji

N

i

N

jjiji ppappappaFFD (2)

Après la fusion , toutes les couleurs seront au moins éloignées d’une distance Td , ce qui permet de simplifier cette équation puisque :

≠=

=jiji

aoua jiji 01

2,21,1 (3)

La matrice de similarité est alors constituée de deux matrices identités sur la diagonale ce qui simplifie les calculs.

(4)

Et on retrouve bien ( ) =21 ','' FFD ∑ ∑∑∑= = ==

−+=2 1 21

1 1 1212,1

22

1

2121 2),(

N

j

N

i

N

jjijij

N

ii ppappFFD .

N1 N2

1

1

0

0

0

0 N1

N2 a 1i,2 j

a 2i,1j

A =

Page 66: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 66 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 5 Exemples de segmentation en régions

________________________

Figure 26. Résultats de segmentation selon un critère d’homogénéité couleur

Remarque : Les régions sont représentées en fausses couleurs.

Image initiale Image segmentée par le RSST (10 régions)

Image segmentée par le partage des eaux

Page 67: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 67 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Image initiale Image segmentée par

estimation de mouvement Image segmentée par

RSST+ fusion de régions

Figure 27. Résultats de segmentation selon un critère d’homogénéité mouvement

Remarques : (1) Ces séquences sont des séquences sources c’est à dire une suite d’images qui se suivent temporellement, contrairement aux séquences présentées dans l’annexe 2 qui sont un ensemble d’images clés. On ne peut pas appliquer directement les algorithmes de segmentation utilisant une estimation de mouvement sur ces dernières. Cette partie reste à être implémentée sous Visual C++. C’est pour cette raison, que j’ai eu recours aux séquences sources, qui sont différentes des séquences test, pour évaluer ces algorithmes. (2) Pour le RSST, le nombre de régions fixé est de 10. (3) Pour l’algorithme utilisant le RSST et la fusion de régions, la taille minimale de régions est fixée à 38 pixels par défaut.

Page 68: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 68 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 6 Interface de validation des résultats :

Requête globale ________________________

Figure 28. Interface de validation : Choix de l’image de référence

Figure 29. Interface de validation : Comparaison des résultats de la requête automatique pour le descripteur global et les descripteurs locaux

Page 69: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 69 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 7 Interface de validation des résultats :

Requête partielle ________________

Figure 30. Choix d’une ou plusieurs régions de l’image de référence

Figure 31. Affichage des résultats de la requête partielle

Page 70: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 70 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 8

Coût de fusion maximum du RSST __________________

Image initiale Coût 3*8*8 Coût 3*12*12

Page 71: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 71 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Page 72: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 72 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Figure 32. comparaison de deux coûts de fusion au niveau du RSST

Page 73: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 73 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 9 Descripteur local avec segmentation de l’image en régions :

comparaison des deux métriques globales proposées __________________

Métrique 1

Métrique 2

(1) (2)

(1)

Page 74: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 74 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

(1) (2)

(1) (2)

(1) (2)

(1) (2)

Page 75: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 75 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 10

Résultats du descripteur local obtenu avec segmentation de l’image en régions

________________________

On peut voir que le descripteur par régions est plus discriminant sur l’image « Golf 20 », la distance augmente de 0.3 pour la quatrième image renvoyée.

Pour cette image, le descripteur par régions donne de meilleurs résultats que les deux autres descripteurs.

Page 76: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 76 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

On peut voir ici, le problème des régions presque uniformes, on arrive à avoir juste une image similaire avec le descripteur par régions.

Les deux descripteurs locaux renvoient le mêmes images et améliorent les résultats par rapport au descripteur global.

Page 77: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 77 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Le descripteur par régions permet d’enlever la troisième image parasite qui apparaît dans le cas du quadrillage.

Dans ce cas, le descripteur global donne les meilleurs résultats. Cependant, le descripteur par régions améliore les résultats par rapport à un simple quadrillage en termes de nombre de bonnes images renvoyées.

Page 78: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 78 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Cette image montre bien l’avantage du descripteur par régions par rapport à un quadrillage de l’image. Tout d’abord, par rapport à l’histogramme couleur, on retrouve la notion de structure de l’image puisqu’on retrouve l’encadré. Ensuite on peut voir que la troisième image renvoyée correspond en fait à l’intérieur de l’encadré de l’image de référence. En effet, ce deuxième descripteur local prend plus en compte le contenu de l’image.

On retrouve encore la notion de structure (le petit encadré) par rapport à l’histogramme couleur. Mais il y a une image parasite qui apparaît.

Page 79: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 79 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Le descripteur par régions améliore les résultats de la requête automatique.

Pour les images texturées, on obtient de toutes petites régions uniformes qu’on arrive pas à bien associer puisqu’on n’a plus la texture. Dans notre cas, on cherche à retrouver des petites régions grises et d’autres noires. Ce qui explique la dégradation des résultats.

Page 80: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 80 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Sur les séquences de tennis, les résultats sont nettement améliorés avec le descripteur local de régions. On arrive à bien retrouver les joueurs.

Par contre, dans le cas de régions où on ne cherche pas forcément à voir le détail, tel que les terrains de tennis, le descripteur avec régions dégrade les résultats parce que des régions comme le filet ou les bords de terrain sont assignées aux pulls des joueurs.

Page 81: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 81 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 11 Résultats de requêtes partielles

________________________

R1

Harmony 9

R1,R2

R1, R2, R3

R1R2R3R4

R1, R2, R3 R4

Page 82: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 82 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

News1 95

R1

R1 R2 R3R4 R5 R6

R1,R2

R1, R2,R3

R1, R2,R3 R4,R5

R1, R2,R3 R4,R5,R6

Page 83: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 83 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

R1 R2

R1

R3

R1, R2, R3

Golf 19

R1, R2

RG-ES-04 18

R1

R1 R2

R1, R 2

Page 84: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 84 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

R1 R2 R3

R1

R1, R2

R1, R2, R3

RG-ES-05 15

Page 85: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 85 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

RG-ES-05 21

R1

R1 R2 R3

R1, R2

R1, R2, R3

Page 86: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 86 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

R1

R1, R2

R1 R2

R1

R1,R2

R1R2

Lascaux 9

R3

R1, R3

Page 87: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 87 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

ANNEXE 12 Architectures UML utilisées pour les descripteurs locaux

________________________

Figure 33. Architecture UML du descripteur local obtenu avec un quadrillage de l’image

K_means

<<static>> kmeans()<<static>> trouver_centroide_largeur()<<static>> trouver_centroide_profondeur()<<static>> plus_proche_voisin()<<static>> compare()<<static>> calculer_barycentre()<<static>> distance_euclidienne()<<static>> bruit_quantification()<<extern>> init_quantification_vectorielle()<<extern>> quantification_vectorielle()<<extern>> end_quantification_vectorielle()<<static>> bzero()

Dominant_Colors_Distance_Parametersm_distance_method : int = DEFAULT_DOMINANT_COLORS_DISTANCEm_grid_method : int = DEFAULT_GRID_METHOD

Dominant_Colors_Distance_Parameters()<<virtual>> Set_Default_Value()

Array_2D<Dominant_Colors>

Dominant_Colorsm_num_colors : intm_threshold : floatm_dominant_colors : float*m_percent : float*m_coherence : float*m_color_space : intm_p_color_picture : Picture*m_confidence : floatm_p_tree_region : rsst_region_t*

Dominant_Colors()~Dominant_Colors()Display_Dominant_Colors()Find_Color_Triplet()Find_Dominant_Colors()Find_Dominant_Colors()Update_Distance_Table()Merge_Color_Vectors()<<const>> Get_Color_Space()<<const>> Get_Polar_Param()<<const>> Get_Distance_Max()<<const>> Euclidean_Distance()<<const>> Get_Dominant_Colors_Value()<<friend>> Compute_Dominant_Colors_Distance()<<friend>> Domcol_Quadratic()<<friend>> Domcol_Simplified_Quadratic()Extract_Dominant_Colors()Extract_Dominant_Colors()<<virtual, const>> dump_state()Set_Image()Reset()<<virtual>> Load_Data()<<virtual, const>> Save_Data()

Dominant_Colors_Featurem_block_size_x : intm_block_size_y : intm_block_numx : intm_block_numy : intm_grid : intm_confidence_measure : BOOLm_grid_method : int

Dominant_Colors_Feature()Dominant_Colors_Feature()Compute()<<virtual>> Distance()<<virtual>> ~Dominant_Colors_Feature()Set_Block_size()Set_Block_num()<<virtual, const>> Save_Data()<<virtual>> Load_Data()<<virtual>> Set_Image()<<virtual>> Reset()Distance()

Dominant_Colors_Arraym_block_size_x : intm_block_size_y : int

Dominant_Colors_Array()Compute_Array()~Dominant_Colors_Array()<<virtual>> Load_Data()<<virtual, const>> Save_Data()<<virtual>> Reset()Dominant_Colors_Array()

-m_p_feature_array

Feature

m_computed_feature : BOOL = FALSE

Feature()<<virtual>> ~Feature()Feature()<<abstract>> Distance()<<virtual>> Set_Image()<<virtual>> Reset()<<abstract, const>> Save_Data()<<abstract>> Load_Data()<<virtual, const>> dump_state()

(from Feature extraction)

Distance_Parameters

<<abstract>> Set_Default_Value()Distance_Parameters()

(from Feature extraction)

Keyframe_Feature

DELETE_KEYFRAME_FLAG : BOOL = TRUEm_number : int = 0m_computed_flag : bool = FALSEm_keyframe_name : CString = ""

Keyframe_Feature()Keyframe_Feature()<<const>> Distance()~Keyframe_Feature()Reset()Save_Data()<<const>> number()Compute()Set_Image()Load_Data()<<const>> Load_BMP()<<virtual, const>> dump_state()<<const>> Edge_Distance()<<const>> Color_Distance()<<static>> Extract_Root_Name()<<const>> Dominant_Colors_Distance()<<const>> Weighted_Color_Distance()<<const>> Dominant_Colors_Region_Distance()<<const>> Dominant_Colors_Query_Region_Distance()<<const>> Dominant_Colors_Query_Many_Regions_Distance()

(from Feature extraction)

Page 88: Mémoire de stage de DEA Indexation vidéo orientée …recherche.ign.fr/labos/matis/pdf/autres/2001_chehata_DEA.pdf · Combinaison des techniques de segmentation ... L’Internet

Page 88 of 88

Nesrine CHEHATA

Mémoire de DEA Photonique, Image et Cybernétique Mars- Août 2001

Figure 34. Architecture UML du descripteur local basé sur des cartes de segmentation

Dominant_Colors(from Dominant Color Feature)

K_means(from Dominant Color Feature)

Keyframe_Feature(from Feature extraction)

Distance_Parameters

<<abstract>> Set_Default_Value()Distance_Parameters()

(from Feature extraction)

Rsst

<<static>> UpHeapLPA()<<static>> InitGenericRSST()<<static>> MergeRegionRSST()<<static>> AllocRSST()<<static>> CopyRSST()<<static>> FreeRSST()<<static>> InitColourRSST()<<static>> ColourBasedFusionRSST()<<static>> InitColourRegionsArray()<<static>> LinkCostColourRSST()<<static>> JointRegParamColourRSST()<<static>> ReheapLPA()<<static>> SetLink()<<static>> InitLinksRSST()<<static>> InitPL()<<static>> UpdateRegion()<<static>> SearchRLL()<<static>> UpdateLinks()<<static>> InsertElementRLL()

rsst_link_tidx : unsigned longcost : floatregion[2] : unsigned long

<<struct>>

rsst_rll_tlink : rsst_link_t*next : rsst_rll_t*

<<struct>>

rsst_region_tmean[3] : floatarea : intxg : intyg : intmarker : intlabel : intrll : rsst_rll_t*pl : rsst_pl_t*pl_last : rsst_pl_t*

<<struct>>

rsst_tnrow : intncol : intnlink : unsigned longnreg : intregion : rsst_region_t*lpa : rsst_link_t**JointRegParam : rsst_join_f*pl : void*rll : void*LinkCost : rsst_cost_f*

<<struct>>

Segment_Rsst

<<static>> segment()<<static>> ColorSegmentation()<<static>> ShortSort()<<static>> ShortCompare()<<static>> QuickMedianLum()<<static>> MedianLum()<<static>> MedianChr()<<static>> WriteSegm()

rsst_pl_tpel : unsigned longnext : rsst_pl_t*

<<struct>>

Feature

m_computed_feature : BOOL = FALSE(from Feature extraction)

Dominant_Colors_Region_Distance_Parametersm_distance_method : int = DEFAULT_DOMINANT_COLORS_DISTANCE

Dominant_Colors_Region_Distance_Parameters()<<virtual>> Set_Default_Value()

Regionm_p_domcols_region : Dominant_Colors*m_mean[3] : floatm_area : intm_xg : intm_yg : intm_label : intm_p_region_pic : Picture*

Region()~Region()<<virtual>> Reset()Set_Values()<<virtual, const>> Save_Data()<<virtual>> Load_Data()Region()

CList <Region*,Region*>

CList<float*,float*>

Region_Listm