Recherche automatique dans une base de données d’enluminures selon

l’organisation spatiale des couleurs

Thomas Hurtut, Haroldo Dalazoana, Yann Gousseau, Francis Schmitt, Farida Cheriet

Signal Image et Arts, Club EEA – Paris – 2 June 2006

1

1. Introduction2. Features3. Distance4. Matching criterion5. Experimental evaluation6. Conclusion

Presentation Plan

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

2

Color image retrieval:

Introduction

Color-spatial image retrieval, many approaches:- augmented features: e.g. chromatic histograms [Lambert et al. CGIV 2004]- points of interest : e.g. [Heidemann 2004]- region based image retrieval (RBIR): e.g. BlobWorld [Malik et al. 2002],

[Rugna et al. CGIV 2002]

Unavoidable segmentation errors false retrievals

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

without spatial information

with spatial information

3

( )

Coarsely sampled thumbnails, size n pixels

Features

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Signature: n features f i

4

Earth Mover Distance (EMD) is used [Rubner et al. 2000].

Distance

Solved with Kuhn-Munkres (1955) algorithm for assignement problems in O(n3)

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

General case (transportation problem): Assignement problem case

Best solved with simplex algorithm (can be exponential with n)

Our features/segmentation step takes full advantage of EMD

5

Distance

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

balances color and spatial distribution

tune the color dynamic,

tune the spatial dynamic

6

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Unsupervised matching criterion

An a contrario model gives an unsupervised answer: we do perceiveevents that happen rarely in a noisy situation.

Given a query, which images from the database are relevant ?

A target image will be considered as similar to a query if it is closer to the query than a noisy image could be.

A few images...

A littlle more...

Much more !

7

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Unsupervised matching criterion

Given an image database

We make a statistical test of two hypothesis against each other:

We handle this test by generating a specific thumbnail model database

And we will say that:

Where is such that:

8

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Unsupervised matching criterion

The background model :

The model we consider is a dead leaves model [Matheron 1968], consisting in the superimposition of random objects, together with a power law distribution for the size of objects.

The distribution of the color of objects is learned from the color distribution of pixels from thumbnails of the database.

9

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Experimental evaluationTests on a illuminated manuscripts database gathering 1500 images

balances color and spatial distribution

10

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Experimental evaluationTests on a illuminated manuscripts database from IRHT gathering 1500 images

Blobworld + EMD Our method

11

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Experimental evaluationTests on a illuminated manuscripts database from IRHT gathering 1500 images

12

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Experimental evaluationTests on a illuminated manuscripts database from IRHT gathering 1500 images

13

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Experimental evaluationTests on a database gathering 25000 images from multiple Canadian museums

14

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Experimental evaluationTests on a database gathering 25000 images from multiple Canadian museums

15

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Experimental evaluationTests on a database gathering 25000 images from multiple Canadian museums

16

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Conclusion and future work

ConclusionWe propose a spatial color image retrieval method without initial

segmentation, using thumbnails and EMD:- robust description- efficient use of the EMD distance

We also propose an unsupervised matching criterion relying on an a contrario method.

Future workMore elaborated features: local quantization, texture characteristicsTests on bigger databases (> 100 000 images)Recent EMD approximation, to speed up querying

More results are visible at: http://www.tsi.enst.fr/recherche/cbir

17

Introduction Features Distance Unsupervised matching criterion Experimental evaluation Conclusion

Questions ?

Acknowledgments

We thank Gilles Kagan from IRHT for providing us the IRHT database and for his helpful comments. We also thank Farida Cheriet from LIV4D Polytechnic School of Montreal for her suggestions. This work was supported by a CNRS ACI supervised by Anne-Marie Edde and Dominique Poirel from IRHT, and by a grant from the LIV4D laboratory.

18