Given user query images, finding quickly similar relevant images is a fundamental challenging task of multimedia search engines with industrial applications to video/image copy detection and object recognition systems. The Internet contains nowadays billions of freely available online images that are currently searched mainly by associated text labels (eg., Google Image http://images.google.com/ ). Although the indexing/retrieval scheme of image databases is somehow quite old, many novel research breakthroughs have been recently attested in the computer vision community. We informally present a few key results below.

Traditionally, database images are indexed using signatures obtained from various feature extractors. First, features of images (histograms, points of interests) are computed and compacted into high-dimensional vectors that represent handles of images. Then given a query image, the signature of the query is computed and similar image signatures are sought out. Finally, an output ranked list is reported after cross-checking geometrically that images carry out indeed semantic similarity (and not only similar signatures). Studying the statistics of (1) natural images, (2) computing short and good feature descriptors, and (3) performing nearest-neighbor queries under the appropriate distance is of primal importance.

We present several recent work along these guidelines:

1/ Carlsson et al. present qualitative topological analysis of the local behavior of the space of natural images.

They consider the toy model of 3 by 3 high-contrast patches. They suprisingly show that these high-contrast patches have the topology of a Klein bottle, and use these findings to develop a compression algorithm based on a Klein bottle dictionary

Carlsson, G., Ishkhanov, T., Silva, V., and Zomorodian, A. 2008. On the Local Behavior of Spaces of Natural Images. Int. J. Comput. Vision 76, 1 (Jan. 2008), 1-12. DOI= http://dx.doi.org/10.1007/s11263-007-0056-x http://comptop.stanford.edu/preprints/mumford.pdf

2/ Discriminating images using feature vectors is an art: Making signature vectors long (=high-dimensional) allows one to better differentiate images at the cost of more time-consuming nearest-signature retrieving.

Making the signatures short allows fast retrieval algorithms but does not discriminate them enough. A recent breakthrough is to use fully automatic machine learning algorithms to learn compact signatures from long signatures. Having short yet discriminative signatures allows one to store locally the fully million-size index. Torralba et al. showed how to convert a real-valued so-called Gist descriptor to a compact binary code with a mere few hundred bits per image. They obtain real-time search performances using millions of Internet images using a single PC and obtain recognition results comparable to the full descriptor.

Small codes and large databases for recognition Torralba, R. Fergus, Y. Weiss. IEEE Computer Vision and Pattern Recognition, June 2008. http://people.csail.mit.edu/torralba/tinyimages/

3/ In order to further improve query search performance, the signature signatures vectors are partitionned into a few clusters.

A celebrated clustering algorithm is Lloyd's iterative k-means method, originally designed for the squared Euclidean distance that yields the center of mass in each cluster. Recently, this algorithm has been generalized to the broadest class of distances, called Bregman divergences by Barnerjee et al. Furthermore, we have shown how to compute the centroids for symmetrized Bregman divergences that allows one to design better information-theoretic clusterings tailored for CBIRs tasks. Clustering is an essential step for designing tree-based nearest neighbor data-structures.

Banerjee, A., Merugu, S., Dhillon, I. S., and Ghosh, J. 2005. Clustering with Bregman Divergences. J. Mach. Learn. Res. 6 (Dec. 2005), 1705-1749.

Nielsen, F., and Nock, R. Sided and Symmetrized Bregman Centroids, IEEE Transactions on Information Theory. IEEE CS Press, 2009 http://www.sonycsl.co.jp/person/nielsen/BregmanCentroids/

Frank Nielsen, Paolo Piro and Michel Barlaud
Tailored Bregman Ball Trees for Effective Nearest Neighbors, European Workshop on Computational Geometry, 2009.

It is my pleasure to annouce that the videos of ETVC'08 are now available at:

http://videolectures.net/etvc08_paris/

The web site (with abstracts and photo albums) is:

http://www.lix.polytechnique.fr/etvc08/

Last April, Bernard Chazelle had a nice column in Nature "news and views" section about convincing general audience of the concept of zero-knowledge. The classic example is the hamiltonian tour that is described in term of tourism: visit once and only once all places in a city named `orbiville'.

The layout of Bernard's is of course more abstract than the above RATP and funny! So zero-knowledge proof is all about convincing someone you know the solution to a hard problem without giving any clue of the solution. This is possible by using randomness in a question-and-answer-session that is well summarized in Fig 1 of Nature's column:
http://www.cs.princeton.edu/~chazelle/pubs.html Thus the puzzling question is randomness and computing, without forgetting the reality of entangled particles...

<