Distances de similarité d’images basées sur les arbres quaternaires

Distances de similarité Distances de similarité d’images basées sur les d’images basées sur les

arbres quaternairesarbres quaternaires

Marta RukozMarta Rukoz11 Maude ManouvrierMaude Manouvrier22

Geneviève JomierGeneviève Jomier22

** Réalisé dans le cadre d’une coopération scientifique CNRS-FONICIT

1. CCPD - Université Centrale du Venezuela - Caracas

2. LAMSADE - Université Paris-Dauphine - France

Plan

Introduction

Représentation multi-niveau

Définition de la distance

Conclusion et perspectives

2

BDA’2002 M. Manouvrier

Introduction

Recherche d’images par le contenu

Représentation des images

Distance / similarité entre images

Interrogation des images

3BDA’2002 M. Manouvrier

Image adaptée de http://simulant.ethz.ch/Chariot/

Bavg

G avg

Ravg


4

Représentation des images par des vecteurs de caractéristiques (points dans un espace multidimensionnel)


Distance entre images

Vérifiant i, j, k trois images :

symétrie

réflexivité

inégalité triangulaire

5

:d

0),( jid

),(),( ijdjid

0),( iid

),(),(),( jkdkidjid


Similarité d’images Point de vue utilisateur :

similarité par rapport à une caractéristique

Point de vue système :

distance entre vecteurs de caractéristique

Similarité : fonction décroissante de la distance

avec d la distance entre deux images et dmax la distance maximale entre deux images

6

maxd

d-1 similarité

S. Lin, An Extendible Hashing Structure for Image Similarity, Rapport technique, University of Alberta, 2000

Requêtes sur les images

B : une base d'images i : une imageq : une image requêteQ : le résultat des : un seuil la requête

Requêtes d’intervalle

Requêtes de voisinage

B} s, i i) { i / d(q,Q

kQ avec d(q,j) d(q,i)QB, jjQ, i

7S. Lin, An Extendible Hashing Structure for Image Similarity, Rapport technique, University of Alberta, 2000


8

Histogrammes en niveaux de gris

Noir Blanc


00 010 000 001

02 03

...

... ...

...

002 003

9

Utilisation d’un arbre quaternaire (quadtree)

0

03

...000 001 002 003

...

00 01 02



10

0

...000 001 002 003

...

0300 01 02

),(),(0 jidjid

Niveau 0

),(4

1),( 11

4

111 kk

k

jidjid

Niveau 1

),(4

1),(

4

1

nn

knnn kk

n

jidjid

Niveau n

0

...000 001 002 003

...

0300 01 02

Utilisation des arbres quaternaires lors de la recherche des images

par le contenu H. Lu, B-C. Ooi and K-L. Tan, Efficient Image Retrieval by

Color Contents, ADB’1994• S. Lin, M. Tamer Özsu, V. Oria, and R. Ng. An Extendible

Hash for Multi-Precision Similarity Querying of Image Databases, VLDB'2001

• J. Malki, N. Boujemaa, C. Nastar, and A. Winter. Region Queries without Segmentation for Image Retrieval by Content. Visual’1999

• Hae-Kwang Kim and Jong-Deuk Kim. Region-based shape descriptor invariant to rotation, scale and translation. Signal Processing: Image Communication 2000

11


Notre proposition

12

k

k

k

kk

c

jicji

),(),(

Définition générale de distances entre images représentées par des arbres quaternaires


k : identificateur de nœud parmi l’union des identificateurs de nœuds des arbres quaternaires de i et j

ck : coefficient représentant le poids du nœud k dans le calcul de la distance

),( jik : distance normalisée entre les nœuds k

Certaines distances d’articles scientifiques sont des cas particuliers de

De nouvelles distances apparaissent

Distance T : distance entre structures d’arbres

13

0),(01 JI

Distance entre les arbres quaternaires d’une même image découpée selon deux critères différents :

0),(02 JI

1),(011 JI

0

00

01

02 03

011010 012 013

j

1),(011 JIx Valeur particulière

0

00

01

02 03

010 012 013

i

011

0110 0111 0112 0113

13/5),( jiT 9/1),()2( jiTE. Albuz, E.D. Kocalar, and A.A. Khokhar. Quantized CIELab* Space and Encoded Spatial Structure for Scalable Indexing of Large Color Image Archives. IEEE ICASSP, June 2000

Distance T : distance entre structures d’arbres

14

0),(01 ji

Distance entre les arbres quaternaires de deux images différentes découpées selon le même critère : 0),( jiT

0),(02 ji

0),(011 ji

0),(011 jix

0

00

01

02 03

010 012 013

011

0110 0111 0112 0113

i 0

00

01

02 03

011

010 012 013

0110 0111 0112 0113

j


Distance Q Pour évaluer le partage entre arbres quaternaires

15

M. Manouvrier, M. Rukoz, and G. Jomier. Quadtree representations for storage and manipulation of clusters of images. Image and Vision Computing, 2002

Image A Image B Image C

0

00 01 02 03

0

00 01 02

03

030 031032033

0

00 01 02 03

Q(B,C)=5/9

Q(A,C)=1/5

A

B C

0

00 01 02

03

030 031 032 033

Distance V Distance visuelle entre images organisées en

arbre quaternaire

16

0

00 01 02

03

Image i Image j

030 031 032 033

Nœuds occupant 1/4 de la surface de l’image

Nœuds occupant 1/16 de la surface

V(i,j)1*1/4

3*1/4

+ 2*1/16

+ 4*1/16 8

3

8

3

4

1*

2

10

4

1),(

~ )1(

jiV

1/2


2

1

4

1

4

1),()1( jiV

Expérimentations

• Image en N&B de 512 x 512 pixels dont 89% de pixels égaux• Critère de découpage en arbre quaternaire : couleur• Distance Q : 0.13503• Distance V : 0.1081543

BDA’2002 M. Manouvrier 17

• Image en 16 millions de couleur de 512 x 512 pixels • Critère de découpage : couleurs uniformes en moyenne• Distance Q : 0.24198• Distance V : 0.5578308

Expérimentations


Distance Q jusqu’au niveau 2 : 1.5290287E-5

Distance V jusqu’au niveau 2 : 0.0

Distance Q jusqu’au niveau 5 : 0.0034167327


Distance Q de la région 02 : 0.26614186

Distance V de la région 02 : 0.46246338



Expérimentations


Distance Q : 0.24262393

Distance V : 0.8547058









Expérimentations


Conclusion

Définition générale de distance

Utilisation de quels que soient les valeurs des nœuds et le choix de

Possibilité de filtrage

Calcul de distances entre régions d’images

21


k

Perspectives

Développement d’un prototype de recherche d’images par le contenu

Indexation multi-niveau

Agrégation de plusieurs distances

22



Caractéristiques visuelles de bas niveau

23

Tapis tissé

Granit

Papier kraft

Couleur

Texture

Forme


Documents

Distances de similarité d’images basées sur les arbres quaternaires