UNIVERSITÉ DU QUÉBEC

MÉMOIRE PRÉSENTÉ À
L'UNIVERSITÉ DU QUÉBEC À TROIS-RIVIÈRES

COMME EXIGENCE PARTIELLE

DE LA MAÎTRISE EN MATHÉMATIQUES ET INFORMATIQUE
APPLIQUÉES

PAR
EMNAMEJRI

SÉLECTION AUTOMATIQUE DE ZOOM EN RECHERCHE D' IMAGES

OCTOBRE 2014
 Université du Québec à Trois-Rivières

Service de la bibliothèque

Avertissement

L’auteur de ce mémoire ou de cette thèse a autorisé l’Université du Québec

à Trois-Rivières à diffuser, à des fins non lucratives, une copie de son
mémoire ou de sa thèse.

Cette diffusion n’entraîne pas une renonciation de la part de l’auteur à ses

droits de propriété intellectuelle, incluant le droit d’auteur, sur ce mémoire
ou cette thèse. Notamment, la reproduction ou la publication de la totalité
ou d’une partie importante de ce mémoire ou de cette thèse requiert son
autorisation.
 Il

Résumé

En recherche d' images par le contenu, la requête peut être une image au complet ou une

partie d' une image (région d' intérêt). Nous allons appeler le premier mode « Recherche

globale », et le second « Recherche locale ». Suite à une multitude d' expériences, nous

avons constaté que la recherche globale donne de bons résultats pour certaines catégories

d' images, alors qu' elle échoue complètement avec d' autres. La même chose peut être dite à

propos de la recherche locale. Dans ce mémoire, nous proposons une solution à ce

problème. Concrètement, nous proposons un algorithme qui sélectionne, en fonction de la

situation qu' il commence par détecter, s' il faut procéder par recherche locale ou globale. La

situation est décrite par le type d ' image requête et le contenu de la BD, ce qui permet de

prendre en compte les préférences de l' usager. Notre algorithme commence par une étape

d'apprentissage, suite à laquelle, il classifie le reste de la BD en des classes locales et

,
classes globales; pour finalement exploiter cela au niveau de la recherche. Les évaluations

qui ont été faites sur une collection diversifiée d' images démontrent que notre algorithme

contribue à améliorer sensiblement la précision des résultats et à mieux capter les besoins

de l' usager.
 III

Remerciements

À mes directeurs de mémoire, Messieurs Kherfi Mohamed Lamine et Mesfioui

Mhamed, je vous remercie vivement pour votre aide dans la réalisation de ce travail et je

suis vraiment très honorée d'avoir collaboré avec vous. J'apprécie beaucoup votre

modestie, votre disponibilité et vos grandes qualités scientifiques et humaines. J'espère que

ce travail vous satisfera et reflétera ma haute gratitude.

J'exprime aussi ma reconnaissance à toute ma famille, à mes parents pour leur soutien

et leur encouragement sans faille. Ce travail n' aurait pu aboutir sans l'aide et la patience de

mon mari qui m' a énormément soutenu pendant ces années. Ces remerciements ne seraient

pas complets sans une pensée pour mon petit fils SKANDER qui a constitué ma source de

motivation et d'espoir.

Je remercie également tous les professeurs ainsi que tous les membres du département

de mathématiques et d'informatique.
 iv

Table des matières

Résumé ............................................................................................. ........................ .... ......... . ii

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

Table des matières ................................................................................................................. iv

Liste des figures ............................. .................................. ..................................................... vi

Chapitre 1 - Introduction ........................................................................................................ 7

1.1 Mise en contexte .................. .... .... ................ ..... .................. ..................................... 7

1.2 Recherche d'images ........................... ...... ............................... ................ ........ ......... 8

1.2. 1 Principe de fonctionnement d' un système de recherche

d' images ..................................................................... ..................... ..... .. ..... . 8

1.2.2 Types de moteurs de recherche d'images ...................................... ... ......... .. 9

1.3 État de l'art ............................................................................................................ 11

1.3.1 Exemple des travaux en recherche globale : .............................................. Il

1.3.2 Exemple des travaux en recherche Locale ................................................. 13

1.4 Choix de Zoom ............................ ...................... :..................................... ..... ......... 15

1.4.1 Introduction ......... ...... .................. ............................................ ...... ............. 15

1.4.2 Quelques notions ...................... .......................................... ..... ..... ..... ......... 15

 v

1.4.3 Détails de la problématique ....................................................................... 17

1.4.4 Solution proposée ........ ......... ......... .. .. ... ....... ........ ....... ....... ........ ....... .. ... .. ... 25

1.5 Conclusion ..... .... ....... ....... ....... .... ....... .... ......... ...... ..... ......... .. .... ... ....... ..... ... ... .. ... .. . 25

Chapitre 2 - Article ....... ........... ..... ............. ....... ..................... .... .................... .............. ....... .. 26

Chapitre 3 - Conclusion ... ....... ........ ......... ....... ................. .................. ... ..... ............ .. ..... ... .... 44

Bibliographies ................................ ........... ......... ....... ...... .... .......... ........ .... ..... ..... ..... .... ... .... . 48
 vi

Liste des figures

Figure 1: Fonctionnement d'un moteur de recherche ............................... ...... .... ............ ....... 8

Figure 2: Illustration de la subjectivité de l' annotation . ..... ........ ........................................... 9

Figure 3: Exemple de résultats de recherche par texte .. ...... ..... .. .......................................... 10

Figure 4: Aigle ............................................................................................................... ..... . 10

Figure 5: Illustration de segmentation en régions ......... .............. ......... ......... .............. ......... 17

Figure 6: Chevaux ................................................................................................................ 18

Figure 7: Roses .. .... .... ............................. ......... .................... ......... .............................. ..... ..... 18

Figure 8: Exemple d'une requête où la recherche globale est plus appropriée .............. ..... . 19

Figure 9: Exemple d' une requête où la recherche locale est requise ................................... 19

Figure 10: Exemple d' une requête où la recherche locale est la plus appropriée ................ 20

Figure Il: Exemple d'une requête qui se prête plus à une recherche globale .................... 20

Figure 12: Exemple d'une requête où la recherche globale donne de bons

résultats .... :.................. .... ........... .... .............................................................. . 22

Figure 13 : Exemple d'une requête où la recherche globale n'est pas suffisante ... ............. . 24
 7

Chapitre 1 - Introduction

1.1 Mise en contexte

De nos jours, les collections électroniques d' images sont nombreuses et diverses. Ceci
est dû à la progression des dispositifs de stockage, à l' augmentation de leur capacité ainsi
qu'à la baisse des prix des dispositifs d' acquisition tels que les appareils photos, les
caméras, les téléphones cellulaires, etc. En outre, le partage des images numériques est de
plus en plus facile et rapide. En effet, une personne peut partager ses images personnelles
avec ses amis à l' aide d' une clé USB, d' un disque dur externe, par courrier électronique,
via une panoplie de réseaux sociaux tels que Facebook ou Twitter, ou bien avec Microsoft
Skydrive. Cette énorme progression technologique a permis d' augmenter le nombre
d' images sur le web, dans les bases de données personnelles et professionnelles.

Prenons l' exemple du nombre d' images partagées sur Facebook. Selon Planetoscope,
toutes les secondes plus de 2 263 photos sont mises en ligne sur Facebook, soit 2 716 000
photos toutes les 20 minutes et plus de 71 milliards photos par an.

Cette disponibilité d' information a permis d'ouvrir un nouveau champ d' investigation
qui s'intéresse à organiser cette quantité d' information de façon automatique et à localiser
les images désirées en un temps raisonnable. D' où l' apparition des moteurs de recherche
d' images, appelés également systèmes de recherche d'images. Plusieurs chercheurs, dont
des chercheurs de notre équipe, se sont intéressés à cette question au cours des dernières
années, ce qui a donné naissance à un certain nombre de moteurs. Finalement, notons que
divers domaines s'intéressent à la recherche d'images, dont la médecine, l' architecture, la
géographie et les sciences du territoire, la sécurité, l' édition, la numérisation des livres
anciens, la mode, etc.
 8

1.2 Recherche d'images

1.2.1 Principe de fonctionnement d 'un système de recherche d 'images

Le moteur donne la main à l'utilisateur pour qu'il entre sa requête. Ce dernier formule
sa requête soit en saisissant un texte contenant un ensemble de mots clés qui décrivent ce
qu' il cherche, soit en choisissant une ou plusieurs image(s) exemple parmi un échantillon
d'images exposées. Ensuite, le moteur effectue sa recherche. Il compare cette requête avec
les images de la base de données, puis retourne à l'utilisateur les images qui correspondent
le plus à sa requête. Ceci est illustré dans Figure 1.

Pour pouvoir effectuer la recherche, le moteur procède comme suit:

./ Extraction de caractéristiques .

./ Calcul de la similarité (ex. distance) entre la requête et les images de la BD .

./ Tri des images selon la similarité .

./ Affichage des images résultantes

Rose
Et/ou

Résultats

Figure 1: Fonctionnement d'un moteur de recherche.

 9

1.2.2 Types de moteurs de recherche d 'images

[Link] Moteurs basés sur le texte

Le moteur de recherche donne la main à l'utilisateur pour saisir une description

textuelle de ce qu' il cherche. L' utilisateur peut alors saisir une liste de mots clés connectés
avec des connecteurs logiques, ou bien il peut exprimer ses besoins d'une façon naturelle
avec une phrase simple.

La pratique actuelle d'indexation des images repose en grande partie sur les
descripteurs de textes ou codes de classification. En dépit de sa familiarité, la requête
textuelle a des limites, dont on peut citer:

./ La dépendance du texte vis-à-vis de la langue .

./ L'impossibilité de l'utiliser quand il n' y a pas de texte qui accompagne les images .

./ La subjectivité d' annotation des images. Exemple: L' image de la figure 2 peut être
annotée avec des mots-clés différents par des utilisateurs différents, dépendarnment
de l'intérêt de chacun. Ainsi, elle peut être annotée avec: Manhattan, New York,
Skyline, Gratte-ciel, Mer, Navire, Ciel, Pont, Arbres, Urbanisme .

./ La subjectivité de texte figurant parfois sur l'image.

Figure 2: Illustration de la subjectivité de l' annotation.

 10

../ La recherche textuelle est incapable de répondre à certains besoins de l'utilisateur,

surtout s' il cherche des images avec un contenu bien précis et des détails bien
spécifiques. Voici un exemple :

Considérons le résultat de recherche par texte, que donne Google, pour le mot clé

«aigle », présenté dans la figure 3.

Figure 3: Exemple de résultats de recherche par texte.

C' est vrai que la plupart des images résultantes contiennent des
aigles. Cependant, si l' utilisateur avait besoins d' images qui
rassemblent à celle de la figure 4, serait-il possible de décrire tous
ses détails (la position, les couleurs, la montagne, le ciel, etc.) en
utilisant du texte? La réponse est évidemment « Non ». Nous
verrons plus tard que la recherche par image exemple permet de
surmonter cet obstacle; effectivement, « Une image ' vaut mille
mots ».

Figure 4: Aigle
 Il

[Link] Moteurs basés sur le contenu des images

Cette méthode est apparue pour résoudre les limitations de la recherche par le texte
précédemment annoncées. Elle consiste à permettre à l' utilisateur de formuler sa requête
en utilisant des images et à trouver des images de la base de données qui leurs ressemblent.
Il s' agit d' une recherche d' images par le contenu ou CBIR (Content-Based Image
RetrievaT). Dans le cadre de notre recherche, nous nous sommes intéressés à la recherche
par le contenu, et plus particulièrement à la «Recherche par image exemple ».

1.3 État de l'art

Plusieurs chercheurs se sont intéressés à la recherche d' images par le contenu. Les
premiers travaux se sont penchés principalement sur la recherche par image globale. Pour
ce faire, ces travaux utilisent les signatures (caractéristiques) de tous les pixels de chaque
image de la base de données d' images. Plus récemment, les recherches se sont orientées de
plus en plus vers la recherche d' images par région d' intérêt. Cette technique se base sur les
caractéristiques des régions qui composent l' image. Dans la section 1.3.1 qui suit, nous
allons présenter quelques moteurs qui font la recherche par image globale. Ensuite, nous
présenterons dans la section 1.3.2 des moteurs qui se sont intéressés à la recherche par
régions d'intérêt.

1.3.1 Exemple des travaux en recherche globale :

Lin et al. [1] ont noté que certaines images sont distinguables par leurs caractéristiques
couleur et texture, alors que d'autres sont identifiables par leurs caractéristiques couleurs et
spatiales. Afin de résoudre le problème de la diversité des bases de données d' images, ils
proposaient trois caractéristiques pour la recherche :
 12

1. La matrice de co-occurrence des couleurs (CCM),

2. La différence entre les pixels des motifs (DBPSP),

3. L'histogramme de couleurs K-moyennes (CHKM).

Pour améliorer la détection d'images et pour simplifier le calcul, ils utilisent une
technique de sélection préalable des caractéristiques.

Dans une autre étude, Saad et al. [2] utilisaient à leur tour l' information couleur et
l' information forme pour la recherche d' images. Ils exploitaient l'histogramme des couleurs
CBYR comme caractéristique globale et les descripteurs de Fourier comme caractéristique
locale. Ils ont choisi comme mesure de similarité la distance de Bhattacharyya pour le
descripteur de Fourier, tandis que pour des histogrammes CBYR, ils calculaient
l' intersection des histogrammes. Ils se sont attaqués au problème des déformations
géométriques et de bruit, mais le problème d' irrégularité des résultats persistait toujours.

Agarwal et al [3] proposent un algorithme pour la recherche d' images par le contenu
basé sur la transformée en ondelettes discrète (DWT) et sur l'histogramme des bordures
(EHD). Leur méthode consiste, en premier lieu, à décomposer l'image d'entrée en
coefficients d' ondelettes. Ces coefficients d'ondelettes donnent des caractéristiques
horizontales, verticales et diagonales de l' image. En second lieu, ils utilisent l'histogramme
des bordures sur les coefficients d'ondelettes sélectionnés afin d' assembler les informations
d' orientations des bordures dominantes.

Ainsi et après avoir calculé l'histogramme précédemment décrit, pour chaque image de
la base de données, ils les rassemblent tous dans une base de données de caractéristiques.

Ils prétendent que la combinaison de DWT et des techniques des EHD augmente la
performance du système de recherche d' image basé sur la forme et la texture. Mais ils se
limitent à des bases de données ayant une certaine particularité. En effet, ils excluent les
bases de données basées sur les descriptifs couleur. En outre, ils ne traitent pas les cas où il
y a une multitude de bords.
 13

Dans un autre travail, Shrivastava et al. [4] présentent une nouvelle technique de
récupération des images similaires en deux étapes :

1. Les images sont d'abord extraites en fonction de leur similitude de point de vu

couleurs,

2. La pertinence des images extraites est encore améliorée , par leurs

caractéristiques de texture et de forme.

Ils proposent une architecture à trois couches: où chaque étage de sortie est l'entrée
pour la prochaine étape.

Première étape : extraction des caractéristiques couleurs de toute la BD + choix de

la requête + calcul de la similarité + retour des résultats.

Deuxième étape : extraction des caractéristiques texture des images retournées à

l'étape 1 + calcul de la similarité + retour des résultats.

Troisième étape: extraction des caractéristiques forme des Images retournées à

l'étape 2 + calcul de la similarité + retour des résultats.

Selon eux, cette méthode élimine la dépendance de la précision de la technique de

segmentation utilisée par la réduction de l'intervalle de recherche à chaque étape. Elle

réduit le problème de la dimensionnalité des vecteurs de caractéristiques ainsi que le fossé

sémantique. Cependant, les résultats d'une étape donnée peuvent contenir des images de

trop ou se limiter à un champ restreint d'images. Par conséquent, la recherche de l'étape

suivante risque de retourner des images indésirables, alors que les bonnes images qui n'ont

pas été retournées à l'étape précédente seront complètement écartées.

1.3.2 Exemple des travaux en recherche Locale

D'autres chercheurs se sont penchés sur la recherche par région d'intérêt.

Premchaiswad et al. [5] présentent une méthode de détection non supervisée pour
déterminer automatiquement la région d'intérêt dans des scènes naturelles. Ils commencent
 14

par construire un contour fermé qui définit la zone de la région d' intérêt, ensuite ils
rapetissent le contour et déterminaient la région en utilisant la méthode des contours actifs.
Cependant, une scène naturelle peut convenir mieux à une recherche globale. C' est souvent
le cas, surtout si cette dernière contient plusieurs couleurs et ou plusieurs régions .

Vimina et al. [6] définissait les régions d'intérêt par la segmentation de l'image en
partitions fixes, ils détectaient la carte de bord à l' aide des bords de filtre de Sobel, puis, ils
remplissaient les trous dans la carte de bord, afin de fixer un seuil pour la détermination de
la région voulue. Les caractéristiques de couleur et de texture de la région d' intérêt sont
calculées à partir des histogrammes HSV et les niveaux de gris de la matrice de
cooccurrence. La mesure de similarité utilisée est la distance euclidienne. Cette méthode
n'est pas applicable pour les images complexes (ex. paysage). En effet, ces dernières ne
possèdent pas de contours fermés à détecter, et par conséquent c'est presque impossible de
les segmenter de cette manière.

Feng et al. [7] s'intéressent à leur tour à la recherche locale d' images par le contenu. Ils
présentent une nouvelle méthode de retour de pertinence pour résoudre le problème de la
CBIR locale.

Rudinac et al. [8] proposaient trois stratégies de recherche régionale. Ces auteurs
affirment donc que la recherche globale donne des meilleurs résultats dans certaines
situations et que la recherche locale orientée par l' utilisateur est plus appropriée dans
d'autres situations.

Suite à une investigation poussée que nous avons menée, nous avons constaté que dans
certains cas la recherche globale donne les meilleurs résultats, alors que dans d' autres c' est
la recherche locale qui est la plus précise. On se trouve donc dans une situation où le choix
entre recherche locale et globale s' impose. La sélection automatique est donc la meilleure
solution.
 15

1.4 Choix de Zoom

1.4.1 Introduction

Afin d'analyser la précision des résultats rapportés par les moteurs de recherche
existants, il a fallu faire plusieurs expériences sur les moteurs de recherche d' images
développés par notre équipe et ceux développés par d' autres chercheurs. Nous avons
constaté que la précision de leurs résultats reste très discutable, dans le sens où :
• ils peuvent donner de très bons résultats avec une requête donnée comme ils
peuvent présenter des résultats médiocres avec une autre requête,
• ils peuvent réussir à bien organiser une collection d' images donnée mais échouer
complètement avec une autre collection,

• etc.

Suite à une analyse approfondie, nous avons découvert que cette irrégularité est
[Link] due au choix des caractéristiques, des mesures de similarité, du choix de la
recherche locale versus la recherche globale (ou choix du zoom), etc.

Pour permettre au lecteur de bien comprendre la problématique, nous allons commencer

par expliquer les notions de caractéristiques, de mesures de similarité, et de zoom de
recherche; ensuite, nous parlerons de l' effet de la sélection de ces ingrédients sur la
précision de la recherche.

1.4.2 Quelques notions

[Link] Notion de caractéristique (ou descripteur)

Une étape de prime importance dans la représentation du contenu des Images est
l' extraction des caractéristiques visuelles de ces dernières.

Ces caractéristiques peuvent être classifiées en celles qui décrivent:

• La couleur: incluant les histogrammes, les moments, etc.
• La texture: incluant la matrice de cooccurrence, le filtre de Gabor,
l'autocovariance, etc.
 16

• La forme: incluant les moments invariants, les descripteurs de Fourier, les

points de contour, etc.

Les caractéristiques doivent être extraites ojJline, puis enregistrées dans un fichier créé à
cet effet. Cette étape permettra d'accélérer énormément la recherche. Évidemment, la
recherche reviendra tout simplement à comparer le vecteur descripteur de la requête et celle
de chaque image de la BD.

[Link] Notion de mesure de similarité

La mesure de similarité est le critère sur lequel se base la comparaison entre le vecteur
descripteur de la requête et le vecteur correspondant à chaque image de la BD. On peut
citer la distance Euclidienne, la distance LI , ou encore la distance de Mahalanobis.

[Link] Notion de zoom de recherche

Parfois l' utilisateur est intéressé par l' image requête au complet et parfois, il est
intéressé par une partie (région ou objet) de cette image seulement. D'où l'apparition de la
notion de la recherche globale et de la recherche locale. Voici comment procède chacun de
ces modes de recherche :

./ Recherche globale :
• Le moteur commence par extraire un ensemble de caractéristiques de chaque
image de la BD.
• Ensuite, la recherche consiste à comparer le vecteur descripteur de la requête et
celui de chaque image de la BD .
./ Recherche locale :
• Le moteur commence par segmenter chaque image de la BD en un ensemble de
régions, comme illustré dans Figure 5.
 17

Figure 5: Illustration de segmentation en régions.

• Ensuite, il extrait le vecteur descripteur de chaque région.

• Finalement, la recherche consiste à comparer le vecteur descripteur de la région
requête et celui de chaque région de chaque image de la BD (après aVOIr
segmenté chaque image de la BD en régions).

1.4.3 Détails de la problématique

Comme nous l'avons dit auparavant, nous avons procédé à une analyse approfondie du
problème, qui nous a révélé que les principales causes de l' irrégularité de la précision des
moteurs de recherche d' images par le contenu sont: le choix des descripteurs, le choix des
mesures de similarité, et le choix du zoom. Nous allons détailler ces points.

[Link] Le choix de descripteurs

L'efficacité des descripteurs ou caractéristiques peut être très variable. En effet, un

descripteur peut fonctionner bien pour un ensemble d' images et ne pas donner de bons
résultats pour d' autres ensembles. Par exemple, si on considère la couleur comme
descripteur, les images de la classe Chevaux (Figure 6) se ressemblent, alors que celles de
la classe Rose (Figure 7) ne se ressemblent pas. Ce descripteur est donc indispensable pour
détecter la ressemblance entre les images de chevaux alors qu' il doit être utilisé avec
précaution dans la classe des roses.
 18

Figure 6: Chevaux

Figure 7: Roses

[Link] Le choix des mesures de similarité

Le choix des mesures de similarité est semblable au choix des caractéristiques. En effet,
certaines mesures de similarité fonctionnent dans certaines situations, alors que d' autres
mesures fonctionnent mieux dans d' autres situations. Il s' agit donc de détecter et utiliser les
mesures qui conviennent à chaque situation.

[Link] Le choix du zoom

Notre travail dans ce mémoire se focalise justement sur le choix du zoom, donc nous
allons expliquer cet élément en détail. Mentionnons d'abord que le zoom peut être choisi
explicitement par l' utilisateur, comme il peut être choisi implicitement par le moteur. Dans
ce qui suit, nous allons expliquer chacun de ces deux scénarios.

[Link].1 Choix explicite du zoom par l'utilisateur

Dans certaines situations, l' utilisateur s' intéresse à tout le contenu de son image requête,
c'est-à-dire qu' il cherche des images contenant tous les objets et détails de son image
requête, ex. l' image requête donnée dans la figure 8. Dans ce cas, les descripteurs globaux,
ex. l' histogramme de la couleur de toute l' image, seront le bon choix. Dans d' autres
 19

situations par contre, il ne s'intéresse qu'à une partie de l'image. La figure 9 par exemple
illustre le cas d'un utilisateur qui cherche à trouver toutes les images contenant des pièces
de monnaie de cette couleur et cette forme, et ce, quel que soit la couleur du fond. Dans ce
cas, seuls les descripteurs locaux de la région qui l' intéresse (la pièce de monnaie) doivent
être utilisés, ex. histogramme de la couleur de la région d' intérêt.

Figure 8: Exemple d'une requête où la recherche globale est plus appropriée.

Figure 9: Exemple d'une requête où la recherche locale est requise.

[Link].2 Choix implicite du zoom par le moteur

Dans certaines situations, et bien que l'utilisateur ait choisi d' effectuer une recherche par
l' image globale, il se peut que la recherche locale soit la plus appropriée.
 20

Prenons comme requête l'exemple de la citrouille de Figure 10. On peut constater que
les descripteurs locaux de la citrouille répondent mieux à cette requête que les descripteurs
globaux de l' image au complet. En effet, bien qu' il ne l' ait pas précisé explicitement, le
moteur doit supposer que l'utilisateur cherche des citrouilles, et ce, quel que soit le
, background' , ce qui a du sens. Il faut donc que le moteur choisisse
AUTOMATIQUEMENT les descripteurs locaux à la place des descripteurs globaux.

Figure 10: Exemple d'une requête où la recherche locale est la plus appropriée.

Prenons maintenant l'exemple de la requête de la figure Il , image plus complexe qui

contient plusieurs objets, avec une disposition bien particulière, etc. Cette requête se prête
donc plus à une recherche par les descripteurs globaux.

Figure 11: Exemple d'une requête qui se prête plus à une recherche globale.

Nous avons confirmé cette constatation expérimentalement, et ce, en effectuant des

recherches avec un moteur de recherche qui a été développé par des membres de notre
équipe de recherche, et qui n' utilise que la recherche par descripteurs globaux.
 21

Dans l' exemple présenté à la Figure 12, nous avons choisi une image de papillon comme
requête. Voir l'image encadrée en rouge dans la partie gauche de cette figure. Dans ce cas,
nous avons obtenu les résultats présentés à la partie droite de la même figure. Nous
constatQns que les résultats de cette recherche sont parfaits, ce qui nous fait conclure que
les images de cette famille se prêtent mieux à la recherche par descripteurs globaux.
 22

Résultats de,la [Link]

Figure 12: Exemple d' une requête où la recherche globale donne de bons résultats.
 23

Dans l' exemple présenté à la figure 13, nous avons choisi une vache comme requête,
voir l'image encadrée en rouge dans la partie gauche de cette figure. Nous avons obtenu les
résultats présentés à la partie droite de la même figure. On constate que les résultats de cette
recherche ne sont pas satisfaisants. En effet, le moteur ne se limite pas à la vache brune
dans l' image requête, mais il considère également l' herbe et la verdure, puis il retourne des
images à dominance verte. Ceci nous fait conclure que les images de cette famille se prêtent
mieux à la recherche par descripteurs locaux.
 24

Rèsultats de la. recherche,

Figure 13: Exemple d' une requête où la recherche globale n'est pas suffisante.
 25

1.4. 4 Solution proposée

a. Identifier la situation dans laquelle le moteur se trouve :

• Le contenu de l' image requête.
• Les préférences de l'utilisateur.
• La constitution de la BD.
• Etc.

b. À la lumière de la situation, déterminer s' il faut utiliser la recherche locale ou bien

globale.

1.5 Conclusion

Nous avons vu que la disponibilité d' information, due à l' augmentation considérable du
nombre d' images que ce soit sur le Web ou dans les collections personnelles, a donné
naissance aux moteurs de recherche d' images. Ensuite, nous avons constaté que la précision .
4es moteurs existants est très variable. Dans notre investigation, nous mène à conclure,
entre autres, que dans certaines situations, la recherche globale donne les meilleurs
résultats, alors que dans d' autres situations, c' est la recherche locale qui est la plus
appropriée.

Nous avons décidé donc d'explorer la piste de la configuration automatique du moteur.

Nous avons commencé par développer un moteur qui permet aussi bien la recherche par
image que la recherche par région. Ensuite, nous avons développé un mécanisme qui
permet au moteur de choisir entre les deux modes, et ce, en fonction de la situation dans
laquelle il se trouve. Les détails de notre moteur et notre mécanisme de sélection seront
exposés dans le chapitre suivant.

Dans le chapitre 2, nous présentons notre article qui décrit ce travail.

 26

Chapitre 2 - Article

Plusieurs moteurs de recherche d' images par le contenu ont été développés durant les
dernières années, mais la précision des résultats qu' ils fournissent est très discutable. En
plus, le même moteur peut donner de bons résultats avec une requête donnée mais apporter
des résultats médiocres avec une autre requête; il peut réussir à bien organiser une
collection d' images donnée mais échouer complètement avec une autre collection, etc.

L' un des facteurs principaux qui contribuent à cette irrégularité est le bon choix du
Zoom. En effet, en faisant une recherche, l'utilisateur choisit une image requête. Mais la
question qui se pose toujours est la suivante : est-ce que l' usager est intéressé par l' image
requête dans son intégralité (recherche globale) ou bien par une partie particulière de cette
image requête (recherche locale)?

Dans l' article que nous présentons dans les pages qUI suivent, nous allons nous
intéresser à la sélection automatique entre recherche locale et recherche globale, ce que
nous allons appeler « Sélection du zoom ». Nous y détaillerons la problématique,
expliquerons l' idée de la solution préconisée et les détails de l' implémentation, pour
finalement présenter une évaluation expérimentale de l' algorithme proposé. Les résultats
obtenus illustrent bien la capacité de notre outil à améliorer la précision de la recherche afin
de mieux répondre aux besoins de l'utilisateur.

Les pages qui suivent contiennent notre article intitulé « An Aigorithm for Automatic
Zoom Selection in CBIR ». Cet article décrit notre travail sur la sélection automatique du
zoom en recherche d' images.
 27

J'ai réalisé, validé et rédigé ce travail, sous la supervision du Professeur Mohammed

Lamine Kherfi. En détails:

J'ai fait une analyse de la problématique de sélection entre recherche par image globale
et recherche par région d' intérêt.
J'ai développé un nouvel algorithme pour la sélection automatique entre ces deux
modes de recherche.
J'ai effectué une évaluation expérimentale du travail développé.
J'ai rédigé l' article qui décrit ce travail.

Cet article a été soumis à «Pattern Recognition Letters» le 12 juillet 2014.

 28

An Algorithm fol' Automatic Zoom Sele('tion in Content-Based Image

Retl'ieyal

Emna Mejri and Moh:unmed L'lllline Kh~

[Link], Kh~1tuqtJ. ca
L~MI."\ Llboratory, Unive:sitè du QlIèbec il Tl'ci~-Rhieres, ŒA 5H7. (QG) C:wada

,4bstract
ln C()ntellt·Bas~ Image RRtritrml (CBlR', query may IMan elltire image al' a part ojthis latter, i.e.,
regton ofInterest (ROI). The flrst mode will be caU~ "global semell", and the second "local soare;'''.
.4 multitude ofexpmimt!11ts conducted nith bath categories ofs(>.(11'ch rcvealed to us tilat global sem'ch
yie!ds good [Link] for some kiJlds of images, whi/e il camp/clety faUs wÎrlI other kinds. The smne can
b€ saül about local searck ln tllis paper; we propose a solution to tllis problem. ConC1'[Link]~ tlle.
proposed algor/thm selects, dependillg 011 the situation it detee!s beforehand, whethel' ta pl'lxe~ by
local or global SNtrÔl. The simation is dssoibed with the query inh1ge ope mld the DB contt'Jl7, wh/ch
allows (aklng users prefor81lcss hlte accOlmt. Our algerJthm stOJ'ts l lltlt a leamillg step, aft~· which,
the r~nainirlg of the DB is clust.".~ orto local class~s and global cnes. Final(v, tl!is is lJS~ Wh81l
peifonning retriewll. E:..-periments done on a diVersifled image DB show that the proposed algol'Îrhm
helps sigl1ificantly improring the Geel/roc)' ofresults and bette!' meeting flle. use,. 's ne.e:ds.

1. Inb'odnction

With the development achieved reœntly in the [Link] of acquisition, s'forage and sharing of
\isllal document, a large amount 9f such documents became available on the web and in ail kind.. of
pe!Sonal .and professional data"Oases. In order ta take [Link] of ail thi.s amount of infonnation and
make it easil)' accessible, it is \[Link] ta develop tools that automaticaily organise it, and help users locate
the document tbey look for in a reasonab!e ~, [Link] bave foc\l.s~ on this issue in receut
yeMS, which b.1S given rise ta a number ofimage search en...~s.

l
 29

An Ùll.'\ge search engiue relies on a nun\ber of "Ûlgredients" snch as features, sinlilarity measures or
queryt)-pes: by region of întmst (ROI) or by entire image. ~ Îll:lpOft31lce of a given ingredient
depends on the situation. A featu.e that yields good results \\ith a given query may gh~' poo! results .
with anatller query. ~ ;sanlt can he s.1Îd about similarity nteasUfeS. This is also lrutconcerning zoom:
in some simations, entire-image-based searc.h is more l>\ûtable, wbile in othe1 situations il is regiou-
based search that !>est suits. This depends ou severa! factors, Ù1dudîng user preferences, DB content,
and especially query image: a single object on a background. a [Link], etc.

In fuis article, we \\ul precisely locus ou ilutomatk zoom selectiou issue. Theengine we developed
st.'\rts by detecting the ClllIent situation. After !hat, it decides, in a way full)' transparent to the user.
whether to consider the entire chosen in1.1geas a qnery or a part of it ouly. Furthermore, in the second
case. it 311tomatically detennines the part that is likely to interest the user.

The paper is organise<! as follows: Section :2 will give an overview of the smte of the art. Then, in
Sectiou 3, we will show the importance of performing ZOOlll selection in order to obtaÙ1 pred.~ results,
and apose the problem. in detail. Section 4 \\>ill aplain the ~eps of the propose<! a!goritlun, then in
Section 5, an empirical e-~"a1uation of Ibis algorithm is condncted. We temÙ1L'\te the article with a brief
conchlSion.

2. Stat~ orthe al"

Severn1 researchers worked on the development of entire-image-based search enginesin recent y~ars.
Exanlples ÙlClude [1, 2. 3., 4]. In sncb [Link], fini, the user selectsoue or more quef}' images. Second.
the en...lrine traverses the DB, comparîng the fea~s of the query with those of every image in the DB.
FÜlally, [Link] c10sest to the query are retumed.

Olherresearchers focused on regîon-based searcb. Among the engines developed, we can cite [5, 6, 7.
8]. \Vhen fu1lllulatîng quet)'. rather than selectingan entire image; user chooses a part of it ouly. This
part generally represents an object or region of interest Durîng retrieval, the engine attempts to locale.
in'la~S containing a region that resembles the quel}' region.

2
 30

A multi11.1de of [Link] carried out \\'Îth. both families of engines revea1ed to us that entire-image-
based search is more suitable in son~ situations, whereas region-based search is more appropriate in
ether situations. However, despite the importance of the automatic selection between the 1WO search
modes as we will Set in Section 3, little attention 11.15 bten paid so far to this issue.

Indeed, we conducted a thorough investigation which revealed that the only ingredient researchers tried
to select 15 image features. In tbis context sevtral techniques 11.1\'e [Link]. For instance, [Link]
reweighting tedmique, which bas heen used in ilS, 16, l8}, gi\i"eS more importance to features in tenus
of which [Link] images are concentrated, and less importance to other features. S()n~ techniques
aitempt to prenoml feature selection in the case the query comprises bofh positi \le and œgative example
inlages [9, 10, Il . 12). They give more importance to fcaMes that dïscriminate well betweenpositive
and negative ex:unples and less importance ta features thatconfound them. Other techniques that are
worth mentioning include [13, 14, 17].

It is ciear that thedeveloping algorithms that automatically select hetween local and global search has
flot aroused enollgh intemt. This 'Will precisely he oÎ[Link] in this paper.

3. Problem position
As we said in previous sections, sevtral CBIR s~tems have enlerged in recrot )~ars, ~onle pe1fomûng
[Link] 00sed on entire inlage while others \lse fegiOll of interest. We carried out a thorough
aperimentation \\ith both kinds of systems, which revealed that none of them 15 ~'Uitable. for "3ll
situations. Indeed, we round out that entire~inlage~b3sed search is more appropriate in sorne situations
like:
- Thase where the quety image is compte;'\. or contains a multitude of objects but noue of them lS
s.ûient compared to theothers.
- Thase wbere the quer'f image cantains a single object wltbout background, e.g., 3 unUoml color or
a particular texture.
Images of Fig. 1 givean illustration.

3
 31

·[Link] images where global search in more

As for region-based search, it is more appropriate in other situations, like wben thequery image
comains one or ri\<'0 5..'llient objects on.a backgrotmd. For an illustration., see Fig. 2.

fig. 2. SOUle ex;unple images where local search is more suïtable.

Before contÛlUing our discussion., let us first define, two terms that '.Ilill be llsed in subsequent sections:
- Global imag.: an Un.'lge that is more suited for global search, according ta our e,x-pectations.
- LO(al imagf: an im.'lge that is more suited for focal search,.accordlng to our expectatiou'i.

4
 32

Now, and in arder to illustrale the fUldings set out above, we give in Fig. 3 the reslIlts Of!OUf retrieval
sessions we perfrumed (Notice that the query itna,ge is the one retumed atthe fint position):
- In the first, the query was [Link] image, and the el1gine perfonned global search. \Ve notice tbat
the results are very good.
- In the second, the query \vas a local image, whereas the engine perfonlledglobal se,arclL We notice
th;lt the results are rather pOOL
- In the third, the qller)' is a global image. whereas the engine perfonned local se,arch. \Ve notice that
the feSults are [Link] POOL
- In the fo\1rth, the query 1$ a local image, and the engine performed [Link] search. We notice tbat the
results are very good.

--- ••
;_ .1

Il
~ FI
Il
Global ~_)' • local remtr.s .,...,. bad [Link].~
• •
Loal qu~'" local fnlUle1 ~ food l"L-ufu
fig. 3. ~ need to select the appropriate search mode depending on the query.
5
 33

Thus,. if i5 d~M dut, in oroer to he able to yield good ~l11ts. the Olgine sllould select the right St.'UCh
mode: local or global. according to the situation. This laffer strongly depends on the qutt)' image, as
.S «1l in the previous e:xample. It aIso depends on the DB content: with a DB wheJ:e each im.,ge conttins
one or rwo salient objects on a background. local search i5 more appropriate. Otherni se. global seMCh
is more smtable.

The solution proposed in this paper allows tQ automatically select hetween local and global ~arch. This
selection is ba~d on the (}lltt)' image type and the DB content. Our selection algorithm has the
advantage [Link] the user preferences without askîng him explidtly. For ex:ullple, even îfhe
chooses an entîre image as a query. uthe algorithm ruSCO\7tfS thai this image contain a unique object
on a backgfound, it win assunlr that the user is loolcing for the object not Ihe entire image, and a local
searcn \1;iU he petfomlecl.

4. Pl'oposedsolution
The proposed solution consisfs in:
- De'l.'eloping a search engine that [Link] retnev-al by enti:re muge and by region.
- Providîng the engine with a mecbanism enabling it to decick, depending on the c:urrent situation,
wbetheJ: tocondtlCt a localo! a global search.
Ta do so, the tool we œveloped proceeds in :) steps:
L Segmenting the DB inlages.
2. Autonutlcally S11bdi.\<'iding the DB inlages into local images and global ones.
3. Classifying a small sample from the DB. This is doœ by a human administrator.
4. AutOlll3tica1ly generalising tlle classification to the !eSt of the DB.
5. Making use ofthis \\uen perfonning retrieval
Thase steps are detailed in the re![Link] of the Section. Furthe:t1llOR. Fig. 4 represents a tlowchart of
the steps 1 to 4.

4.1. StgUlf'urin~ th.e DB im.'\ges

The first step of Otlf algorithm. consis-ts in segmenting each im.'\ge in OlU' DB into region~. This
segmentation is needed for al leasl two reasons:

6
 34

1. The algoritlnll that subdi\<ides the DB mto global muges and local ones. relies on the nunlber
ofregions by in13ge.
2. Conceming images categorised as local, oo1y the regions of mterest soo1.11d be taken into
account and comparai witheach other.

Global
imaies

Classification + Detectlng
de!egate region

Fig. 4. Flowchart ofthe classification algorithm.

4.2. Subdhiding th~ DB imagtSinto l«al and global

The aim of this: step is to subdivide the DB images mto t\\"o familles: focal and global. The follo'k1ng
algorithm bas been used to do .00:

Algoritlvn 1. Subdividing imagesinto Ioca! lInd global.

foreach new image i ta he categorized, dedde whether it is local or global based on the foUowing
rules: lSt•.!-<::if""." b.....'
If it comprises between 2. and 5 reefons then
ft is considered ta be local.
els!! (Le., the number of regions is equal to 1 or greater than 5)
ft is considered te be global.
end for
7
 35

The principle ofthis algoritlun is justified by the following observation:

- Images that are better match local search are tho,se with a sma1l number of salient abjects. Such
images genet:llly comam between 1 and 4 regions. By adding the background, if gives :2 to 5
regiollS.
- .4.n image \\>ith 3 single and uniform regiQn (a background, a part of an object, etc.) better suifs
global &earch. Similarly, an image with a multitude ofregîons (more tb..-m 5) is 1ypically a
complex im:\ge contaîning too mucb. ddail. a texture, or overlapping objects. Tt better .suits
global search too.

4.3. [Link] a sl1llill samp~ oftbe DB

The lhird ,,;tep cOtlSÎ&ts in asking a htunan u&er (or adtninistrator) to chssify a smaIl sample of the DB.
according to the following. steps:

- [Link], among the global inuges, a sample thaf represents well fuis fàmily.
- Subdi\!Îding this sample mto a setofdasses (said global classes)
Choosing, rullong the local in:uges. a sample that represents weIl this family.
- [Link] this sample mto 3. set of classes (s:ùd local classes)
- C'hoos:ing a delegate region that upresents each local in:uge. nlis notion of delegate fegion is
detailed below.

Notion qfa delqgate rqgiol1.:

When retrie\'3l is based on entire inuge, it is Ibis latter that i5 considered as a query. In contrast, when
retrieval is based on a fegiOU of interest, it lS not sufficient to specify the query image, the sought
region must he specified too. It is fuis fegiou that we caI1 delegate region.

4.4. ~nualising th~ classificatiob to the l'est of th~ DB

Duringthis step, our toot CL1Ssiiies the remaining ilu.1gesofthe big DB. It assigns each global in:uge to
the appropriate global da!;s usin,g Algorithm 2 below. Ir assigns each local image to the appropriate
local clas... and autouutical1ycbooses thedelegate region ofthis image. 'This is doue \lsing Algorithm 3
belO\v.

8
 36

Aigorithm 2:. AssÎinîng eae" global image to the appropriat.e global dass
for each new global imaie i to be da~sifled
for ea<h global dass ~
ca1cutate the melllbership degree of i to k~ (tu fI.,* m N.l~ 1. œ~w}
end for
Assign i ta the dass having obtained the highest membership
degree.
end for

Note! :
lbe membership of a gfoba! image i to a global dass k... noted Mem{l. k,,), is ca1cu!ated as follaws:
- For éach image i belonging to les : pecrform il search using i as query.
- Galculate the average rank of i among results.
- Mem{i, k<J)= 1/ the average rank of i.

Algorithm 3. Assigning eath local image ta the appropnate local [Link], then determining its de!epte
region.
for eaen new local image ; to be classified
for each local dass k. ;
Caleulate the membership degtee of ita kt {to."",, ;. "."l"",,,j
end for
Assign i to the d ass haviniobtained the highest membership
degree.
Identifv the delepte relion of i. {~""'., .,-. J ' -..1
end for

Note2:
The membership deiree of a local image ; to a local dass k~, noted Me".~i, k.}, ls cakulated as foltows:
. for each image [Link] to k" perfarm a search using its delegate region as query .
. Ga!cu!ate the [Link] ran.k of i llmong results .
- Mem(i, k$} = 1/ the IIverage rank of i.

Note 3:
The deleeate relien of lin image 1$ dlosen as follows:
- ln the case the imaie comprises enlv 2 reglens, a bllckground subtractlon .algorithm was applied.
Then, the remaining region is considered as the delegate of its image .
- .In the case the image comprises more thlln 2 regions, the regton having mort freQuently been
retalned ln similarity calcullltlon during the asslgnment of the Image to a dass is cnosen te be the
delegate. In other words, it is the region closest to regions that represent the images of dass k,.

9
 37

4.5. Making use of thttobtained index to perfonD l't'Riel1ll

Now that the training and classification algorithms were exposed, Algorithm 4 explains how search is
carried out depending on the situation:
Algorith0l4. Retrlevat
The user mm by choosil'\g an image q as Quel'V, without specifving whether he is interested by a gtoba!
or il local search.

Our engine !intis out the class frc m which romes the chosen image

if it comes from il global classk"" then

Search is deme within le.; and nelghboring glabal clas.s es, using the global features of q .
else {Le., ft cames tram a local cfass ktl
*'
Search is [Link] and neighboring local classes, using the local features of the de!egate
region ofq.
end if

The engine retums results to the user.

5. Experimental evaluation
ln order to eva1uate the proposed algoritbm, we used a DB of 900 ÎDl:IgeS divided mto 30 classes of 30
images each. Our BD contains varions images, with different colors and shapes. Ob\>iously, it CQntaÎnS
both local and global images. Fig. 5 giv'eS .3n overview of the contmtofthe used DB.

Fig. 5. Somesample images from the DB u,sed.

10
 38

Each intag~ in the DB was fust segmented. S~ond, our tool chose whe~ Ibis imag.e is local or
global, base<! on the uumber of regions it embeds. Third, the administrator d assified a sample of the
global im.1ges and a sample of th.C' local images. Fourth, classification wa~ gffieralized to the rest ·o f the
DB. Finally, tbis classification lm been exploited by the ~arch module. TIle user starls by choosing an
image to CQ1lStitute a query. Then the search module automatically decides wh~ther to opt for local
search or global one.

Since the developed tool perfonns both cla"sification and search, we carried out two [Link]. The
fifst \Vas intended ta measure its classification perfornooce white the ~oud U"35 desig,led ta measme
its searcb ~[Link].

5.1. Fil'st upttimE'nt: E'\·aJuati.n.g classification

This experiment aimed to [Link] the perfoIIJl.1Jlce of our classification algorithm Foc this purpose,
we compared the classification it gave with a classification made bya hum.1Jl.

For each of the classes our algorithm generated. we .mea:.ured Iwo incbcators:

Pr~isioll- NUlllber of good intages in the class ! Total number of images assigne<! to this dass.
Recall = Number of good images the tool put in this c1as:s ! TOIal number of images tbat should
h;we been put in ibis dass.

Results are given in Table L

From Table 1, we notice that both Precision and Recall are appreciable high for most classes. Our
algorithm achieved an average precision of 93,4% and an average rttall of 92,S%. This clearlyassesses
its ability to automatically das.-sttY the DB images \\>lth a good accuracy.

11
 39

TABLEI
PKECISION ANDRECALL OF EACri CUSS

Clan PI'l'cidon Rt'cnH Cl;m Pl't'd~oll Rl'C'llU

[Link] 100 86,67 Eagle 92,59 83,.33
Wateri.àU 100 100 Bik~ 90,9'1 100
Pboto-Ff'lUlle 100 96,67 Trol~y 100 90
Kto)'boMd 100 83.33 .Puwpkùl 88,89 80
Poppy 100 86.67 Spoon 88.23 100
Dead-Le;n'~s 100 100 Hawk 96 80
Snw 100 90 Ociœ 93,75 100
Rotlse 90.91 100, Bud 100 100
M'oney 81,08 100 Fish 85 ,71 100
Mosak 75 100 Wbite-~A' 100 93,33
L'lIldscape 100 100 M01ll."ey 83,33 100
Beach-At-NI,,2ht 92.,31 80 Sfatue 84,62 7'3.33
Bri<fge 96,55 91,33 Tomato 81,S1 90
Scene 100 lOO Mud 86,67 86,67
Wa\'t's 93,75 100 Wallanan 100 90

.A doser look into Tabl~ 1 shows that petfonnance varies from c1a&.s 10 <:lass. &>ugb1y, fOUf categories of
clas~ can he iden1ified:
- Those with a bigh precision and a high recall, like "Waterfa1l".
- Those \Vith a bigh precision but a moderate (yet acceptable) reca1~ like "Hawk".
- Those with a high recall but a moderate (}-et acceptable) precision, like "Mosaic" .
- Those with a moderatt' precision and a moderatt' recall, like "Mud".

After an.:û}'sis,. we found tha! classes \\i th a moderate recall are those whose images are dispersed, i.e.,
do nol resemble each other. nUIS, if is ql1ite naturnl that the- algorithm was not able to identify them aU.
Neverthe-Iess. it succ~ locating mostofthem, reaching a fairly acceptable recall.
The- same C:Ul he said about precision.. Indeed, classes having obt.'lined a nloderate precision are those
that are dose fo other classes. Therefore, sorne oftheir images ma}' he attracted by those classes and
\[Link]-versa. This cxplains the fact that such classes contain more noise, which Mgatively affects their
precisiOll. Nevertheless, our algoritlUll was able to reach a fairl)' good precision on the whole

12
 40

5,.2. Second expt'l~nt: t'[Link] l't'oiend

The aim of this experitllent "tas to demonstrate tb.1t OUf automatic-se1ection algoritbm perfOflllS better
than a simple local ~art:.h Of a simple globalsearch.
To do 50. results of the tbr« search modes (local. global and automatic) were compared. Search
Precision 1135 been used as a measure of perfonn:mce. Ir i5 given by:
Search Precision ., ~umber of good images rettuned to the user / Total uumber of itnage$
retumed to the user .
The e."'-periment was conducted as fol1<Tw-s:
- A multituœ of retrieval sessions was launched At each session, first an Î1ll.'lge is chosen. Then,
global. local and autom.'ltic .retrieval are doue both v.'ith this image as que!)'.
- The precision of each search mode was tnelsured as a nUlCtton of Ille number Of fmûts retumed
to the user.
- oThe average precision of each search moœ \\'35. ca1rulated.

Fig. 6 shows the CUf\res of average precision as a function of scope Pr=.t(Sc) for tire 3 se.'lfch modes
(local. global and automatic) where Scope (Sc) is the [Link] of images retu:rued to the user.

0,9S
·_,··""<<<'''"~''''~ù......... ,,.........,,,,.,.~~'''''''''-,,.

0,9 ~
...""": . . .........................."C.. •• ;;.;;,.~
••••••••

O,8S + ............................,""""............................................. ~ ........................................................ - - - A\fera,epr.d~ion of

o~.s -'--.----...-'~-:;--_.~---~._.:..."'......-:::. ."""'. ..__.- , lobat surch
Ave~~. O,7S +________•___._""'~ -*- Avit".,. [Link] of IO~".1
preQSlOn search
0, 7 ·i-~·-----"---_ ..._-- - - Av.n'Il pr.cÎ$lon of
O,6S y __._.__.._.._. ___...__._.m..... _.........__....__.. ___............._-_. automatic search

0,6 T------------------
O,5S +
1 2. 3 4 5 6 7 li 9 101l1.213141516171819202t2U32<t2.5
Sropfl

Fig, 6. Comparioon of the average Search Precision for the thr« search modes: local, global and
automatic
 41

The first observation we ean tl1ake from Fig. 6 is th.,t the cUfveeorresponding to autoru.,tic mode lies
above the two other C1.11'Ve5. for an value.; of the scope. This confions that the proposed auto1ll.,tic zoom
~lection algorithm siguillcantly helps imprO\'ing results precision.

The second observation t<; that for aulomatic mode, tM relevance of the retrieved images deueases Iess
quick1y withthe mtmber of retrieved images than wben global mode Of local mode are tlSed. For a scope
of25 for example, the 3venge precision is about 0,74 \Vith global mode, [Link]'t exceed 0.63 \vith local
mode,.whereas if reaches 0.91 when automatic mode is \[Link].

The third observation is that globa:lsearch }'ields better results than local search, for almost aU values of
tlle scope. This can be eX1'lained by the fuet that:
- It 15 uot necessarily a bad thing to carry out global search \\ith a quer)' thal better fits local
~arch. fudeed. induding the backgrollndhelps sometimes fillding good results. even ifit is not
the region sought hy the user. Imagine for example a user who is l00king for planes. and who
chooses an image of a pfane in the bluesky as qoo:y. Global search takes the entire-im.,ge
fe.1tures inta account, induding th<[Link] of the sky. Therefore. images containing the sI..1' 'i\'Îll be
retrieved, and there is precisely a good probability that sucll imagescontain planes too.
- On the opposite, when local search is adopted withan image lbat better fits global ~arch, this
may ha,'e a llegalive eff'ec,t on ~ q\lalîty of results because some important paris oftM image
may be neglected.

6. Conclusion
The m:un objective of any image search engine is to rclrieve results that meet user needs and
expectations. [Link], undernanding \\,1l..,t fuis latter wants is IlOt an easy task at all, for several
reasons. Somerimes, the user is subjective or doesn'f know what he exact1ywants. SOOletimes, it is b.,t'd
for hùu ta express bis needs using the Iinlited tools av:ÛL,b1e. Sometimes, he does.n' t find the right
[Link] image to he tlSed as a query.

A careful study of ihose is-sues, [Link] the question of zoom• .revea1ed [Link] user is sotuelimes
interested by the entire query image, wbile in other situations only a part ofthis image interests him.
This Ied us to propose a nove! algorithm. for autonutic zoom selection. Depending on the situ.1tion it
14
 42

detects, our algorithm selects \\ilether to perform a local or 3 global search. Fînt, it partitions the DB
into local311d global cL'lsses. Theo., the obtained classification is exploited [Link] retrieva1.

The developed eng:ine ,vas validated on 3 mVef'ie DB. The results are very promising.

Acknowledgments
This research was partially funded by NSERC Canada waugh [Link] Grant progrnm.

Refel'ences
[1] CR Lin, RT. Chen and YXChan, "A Smart Cootem-based Imag~ Retrie...-al System Based 011 Color and
r e.'àuz"e Featute," Image and r'i:iOll C-omputing. 2009 - Eise\'Ïer
P 1l.\lli 5aad, KLSaEeh, H. Konbor, [Link], "Imag~Rmie\'lÛBasedOll1ntegratioo~t\\'-eenYCbCr­
Colot Histogramand Shape FealUl'e," 7· IntetnatiClll31 Confmm:e 011 C<>mpUter ~ (ICENCO), p.p 97-
102, 2011 .

[3] [Link]:as, D. Ramilidis. A. Dîmou, P. DarM, "MSIDX: Multi~';ort !ndexing for .Efficient Content-
base<! Image Sea!th and ~e\'aJ," IEEE T1"tl7lSlIctiOllS 011 MI/ltinwdia_ rs~ue: 99. p.p 1, 2013.

[4] N. ShriYast3\'3, V. Tyagi., '·Mu1tista~Coment-bMedlm..\gtRelril!",-al,,'· ~ IntetU3ti.ona1 ~ 011

Software Engiœe:ring (CONSEG).p.p 1-4. 2012.

{51 W. Prellldniswadi. A. TlUlgkat%aÙWl, and N. Ptl!'1llcllaîswad.i, "Umllpervised Detection for M;njmizfng a

Region of Intern1arol!D.d Di~c.t Objed Î1l Natutal Imag~s," Imematiollo1 Ccnfil1'euce OH
Dfgital l,nag.:: Computing: Tech1!tqm'lS lD!d .4FPlicatioru (DICT..4}, pp.202 - 207, 1-3 Dec. 2010.

[6] E.R.\ "unin.'1....K. Poulose Jacob, "Image Retrie....a1 U&Ülg Colouc and Tt'XtUre F~atur~ of ~OQS of Interest;'
blt~lIa.:·Î(mal COI!!111'~lce 011 lI!fomratioll &MiA'Cl &: Kmnrledge MaJlagammt (C.-L\JP), pp. 240-243, 13-15
Match. 2012.

(1) S. Feug, C. Lang, and D. Xu. ·'Localir.eô [Link] Image Reale",,! u;iag Saliency-
ba;.ed Graph LeamiugFtèlllle\\'Ott," 1er IEEE lnternilnollal Conj€7'efICJ Olt Signal PrlXcssillg (ICSP), pp. 1029-
1032, 24-2S<Xt 2010.

{81 S. Rudinac, .M. Uscum1ic, !tllù:dinac, G. Zajicand B. Reljin,

''G!.(}ba! Ima~ ~Mch v!>. Regicnal Seareh in CBIR Sy~tems," lnternafiomll WOltshop on Image .-4nal•.1'Sis j'br
Multimedia llltcracmre Sen·lu.. [Link]:lIS, W.14, 6-S J~Ull! 2007.

[9] ~f.L Khm'i, D. Ziou and A. Beroardi, "Content-Base<! Image [Link] UsÎIlg Positive aud Negative
E-:.amp16,~ Jounllli ojTî.mal Commrmica!icn
and Image ReplWcntahem, 14(-î):42S-457, Decettiler 2003.
lS
 43

(10) ML. Khem aod D. lieu, '[Link]~ [Link]"Îe\-a.1 Based on Feature Wei~tÙlg [Link] Feelllllck,~ IEEE
Intcnlonon.'ll COtifl'~lIce 011 Image Proccssiflg. SÙlgapore, Octobet 1004.

[11] ML. Khedi and D. Ziou, "Image Collection Modeling and ils Applkation to Indelting. B!OW~Ùlg and
SemamicRetrieval," lEP:" 1imuomoJ!s on Mulrintiidia. 9(4):893-900, l uœ 2007.

[111 M.L Kberl1 and D. Ziou. "[Link]œ Feelllack for CBIR: A New _.\pproach Based [Link]~tic Feature
Weighting v,ith Pooitive and Negative [Link]'les." IEEE TrtllUa'-1ÎOfu Ofl Image Proccssi»g. 15(4): 1017-1030,
Apri1 2006.

[13) N. Vasc=-e1os and M. Vl\'.lroucelos, "Scalable Di$[Link] FeatuR Selection for Ima~ [Link]'.-a.1 and
[Link]~tion," IEEE Intflmatiollol COII!errlJ!ce 011 Computel> Illsioll and Pattem Rtccgnittcm Cf'PR, Washington,
D.C., 1004.

[14) XS. Zhou, T.s. H1WJg, "Comparing Di>cri.mïnating Tramfonmtions and SVM for [Link] Dl.1ring
Multimedia R.ettieva1,·' .!OfMultimOOia Corifèf'Qlce. ona,,,-a, Canada,:2001.

[15] Y. Ishil:awa, R SlIbramany3, and C. Faloutsos, "~1indRe~ [Link]-'ÎJl.!: Databases tllI'01lgh Multiple
[Link]'1«." 2~' 1I1tenlational Co1!f~'maJ 011 rel~, LaI~e DataBarôlS f,WB, l99lt

[161 Y. Rui. aud T. Huang. ,.()[Link] Leartling in Image [Link]\"3l," IEEE littcmatiollal Cc~ife!vnN! on
Compute!' FiIion mtd Patt"" Rcccgnitioo Cl'PR, Hîltoo Head. .south Carolina. 2000.

[17] Y Liu, J.R .Kender, "Fa5t Video ~ [Link] br .sort-Ml'rgt Feanu-e Seleoctioo, BouudaJy [Link],
and Lazy Evalu.,l1011," CDmptuel' T/isitm and ImageUhdcJ'mIndiilg, 91(3), 2003.

[18] Y. Rlli •. T. S. Huang, and S. 1vfehtotl:3, <'Coutett-based In1age [Link] with [Link]."e Ftdlacl::Î1l M:.[Link],"
ProuMig; o.l'IEEE blt~"laffollal CDt!ft,-wnce Clt Image [Link]!g, Santa Barabara. CA, October 1997.

16
 44

Chapitre 3 - Conclusion

Nous avons vu que l'augmentation considérable du nombre d' images, que ce soit sur le
Web ou dans les collections personnelles, a motivé l' émergence des moteurs de recherche
d'images. Ensuite, nous avons constaté que la précision des moteurs existants est très
variable. L' investigation que nous avons menée nous a dévoilé que cette précision dépend
énormément de la situation dans laquelle le moteur se trouve. Nous nous sommes focalisés
sur la question du zoom, et nous avons découvert que dans certaines situations la recherche
globale donne de meilleurs résultats, alors que dans d'autres situations, c' est la recherche
locale qui est la plus appropriée.

Nous avons donc décidé d' explorer la piste de la configuration automatique du moteur.
Nous avons commencé à développer un moteur qui permet aussi bien la recherche par
image globale que la recherche par région. Ensuite, nous avons développé un mécanisme
qui permet au moteur de choisir entre les deux modes, et ce, en fonction de la situation dans
laquelle il se trouve. Notre mécanisme procède par :

1. Une catégorisation des images de la BD entre globales et locales.

2. Une classification des images de chaque catégorie en classes.
3. Ensuite, une fois que l'usager soumet sa requête, l' outil choisit automatiquement
entre recherche locale et globale.

Pour ce qui est de la catégorisation des images entre globales et locales, nous avons
adopté le principe suivant:

• Si une image contient une seule région

~ une recherche par image globale est plus appropriée.
• Si une image contient un nombre restreint de régions qui de surcroit sont assez
apparentes
~ une recherche par région d' intérêt est plus appropriée.
• Si une image est complexe et contient beaucoup de régions dont certaines en
cachent d' autres
 45

~ dans cette situation aUSSI une recherche par Image globale est plus
convenable.

Pour ce qui est de la classification des images (qu' elles soient locales ou globales) en
classes, nous avons développé un algorithme dont les grandes étapes sont les suivantes:

1. Un administrateur commence par classifier un échantillon de notre BD en des

classes.
2. Notre outil classifie le reste de la BD en affectant chaque nouvelle image à la classe
dont les images lui sont les plus proches.

Finalement, notre algorithme de recherche décide s' il faut procéder par recherche locale
ou globale, et ce en se basant sur les résultats des deux étapes précédentes. Nous avons
procédé à une évaluation expérimentale des algorithmes que nous avons développés. Pour
ce faire, nous avons utilisé une base de données de 900 images réparties sur 30 classes
composées de 30 images chacune. En dépit de la variation du contenu visuel de cette
dernière, notre moteur a été capable:

1) de repêcher les images appartenant à la même classe (Classification)

2) de retourner les images les plus similaires à la requête choisie par l'utilisateur
(Recherche).

Ceci a été confirmé par les deux expériences que nous avons conduites:

La première a tenté d' évaluer les performances de notre algorithme de

classification. Nous avons comparé la classification qu' il a donnée avec une
classification faite par un humain. Nous algorithme a donné une précision moyenne
de 93 ,4% et un rappel moyen de 92,8%, ce qui est très intéressant et démontre
clairement la capacité de notre outil à bien classifier les images de la [Link] de la
deuxième expérience, nous avons essayé de mesurer les performances de notre
algorithme de sélection automatique entre recherche locale et globale. Nous l' avons
comparé avec les deux algorithmes classiques: celui qui fait toujours la recherche
par image globale, et celui qui fait toujours la recherche locale. Les résultats obtenus
nous ont permis de constater que notre algorithme de sélection automatique obtient
 46

de meilleurs résultats que les deux autres. Ceci démontre l' utilité et l' importance de
la sélection automatique du zoom.

À travers le travail que nous avons accompli, nous pouvons dire que nous avons réussi
à:
Réduire le temps de calcul et par conséquent avoir un moteur plus rapide.
Réduire l' effet des régions non voulues et qui faussent souvent les résultats.
Réduire l' espace de recherche en le limitant aux classes les plus proches de la
requête. Ceci nous a permis d' augmenter la probabilité de retrouver les images les
plus pertinentes.
Combiner les avantages de la recherche globale avec ceux de la recherche locale.
Surmonter certaines faiblesses de la recherche locale et d'autres faiblesses de la
recherche globale.

Ceci étant, plusieurs autres améliorations peuvent être apportées à notre travail, comme par
exemple:
• Trouver des pnnCIpes de sélection plus élaborés, pUIS les transformer en des
algorithmes.
• Automatiser les tâches qui sont faites actuellement de façon manuelle.
• Intégrer la sélection des caractéristiques, la sélection des mesures de similarités, la
sélection du zoom et la sélections de/des objet(s) d' intérêt(s) dans un même moteur;
tout en attribuant des priorités ou des pourcentages pour chaque ingrédient selon la
situation.

• Avoir un retour de performance (un jugement humain des résultats) suivi par une
amélioration des résultats.

• Prendre en compte l' aspect sémantique des images, ce qui devrait permettre de
s' approcher davantage des préférences de l' usager et de mieux comprendre ce qu' il
veut. L' aspect sémantique repose sur le sens de l'image, ce qu' elle décrit ce qu' elle
représente, ce qu' elle contient (une ontologie de l'image).
 47

Selon mm, quelques recherches faites dans le domaine de la SCIence de

l'information peuvent être utiles pour décrire les images telles que le thesaurus par
exemple. Une bonne solution serait alors de combiner la recherche d' images par
texte et la recherche d'images par le contenu visuel. Comme ça, on pourra bien
satisfaire les besoins sémantiques et visuels de l' utilisateur.
 48

Bibliographie

[1] C.H. Lin, R.T. Chen and Y.K. Chan, :'A smart content-based image retrieval system
based on color and texture feature " , Image and Vision Computing, Elsevier, Volume 27,
Issue 6, p.p 658- 665, 4 May 2009,.

[2] M.H. Saad, H.!. Saleh, H. Konbor, M. Ashour, "Image retrieval based on integration
between YCbCr color histogram and shape feature", Computer Engineering Conference
(lCENCO), 2011 Seventh International, p.p 97-102, Giza, 2011.

[3] S. Agarwal, A. K. Verma, P. Singh, "Content Based Image Retrieval using Discrete

Wavelet Transform and Edge Histogram Descriptor", International Conference on

Information Systems and Computer Networks (ISCON), p.p 19 - 23, Mathura, India, 9-10
March 2013 .

[4] N. Shrivastava, V. Tyagi, "Multistage content-based image retrieval", 2012 CSI

Sixth International Conference on Software Engineering (CONSEG), p.p 1-4, Indore, 2012.

[5] W. Premchaiswadi, A. Tungkatsathan, and N. Premchaiswadi, "Unsupervised

Detection for Minimizing a Region of Interest around Distinct Object in Natural Images",
International Conference on Digital Image Computing: Techniques and Applications
(DICTA), pp.202 - 207, Sydney, NDW, 1-3 Dec. 2010.

[6] E. [Link], K. Poulo se Jacob, "Image Retrieval usmg Colour and Texture
Features of Regions of Interest ", International Conference on Information Retrieval &
Knowledge Management (CAMP), pp. 240-243 , Kuala Lumpur, 13-15 March. 2012.

[7] S. Feng, C. Lang, and D. Xu, "Localized content-based image retrieval using
saliency based graph learning framework", IEEE 1Oth International Conference on Signal
Processing (ICSP), pp. 1029-1032, Beijing, 24-28 Oct. 2010.

[8] S. Rudinac, M. Uscumlic, M. Rudinac, G. Zajic, B. Reljin, "Global Image Search

vs. Regional Search in CBIR Systems", International Workshop on Image Analysis for
Multimedia Interactive Services WIAMIS, pp.14, Santorini, 6-8 June 2007.