Programme INRIA "Equipes Associées"

• 3.1. sur la collaboration déjà existante avec votre partenaire
• 3.2. sur la collaboration avec d'autres projets INRIA: metiss pour romain
• 3.3. sur la collaboration avec d'autres équipes de l'organisme étranger partenaire.
  

II. BILAN 2006

Rapport scientifique pour l'année 2006

This scientific report describing the work achieved in 2006 is divided in two parts. First, we list 5 key milestones for this 2006 year. Then, we present two new scientific issues that have appeared during the course of our studies and that will grow larger in the future.

1. We have signed, in December 2005 a formal aggreement of cooperation between IRISA, Reykjavík University and Morgunblaðið , the main newspaper in Iceland. Reykjavík University, in cooperation with the TexMex at IRISA, is developing and researching software to efficiently find images by their visual content. This software, referred to as PvS, may, among other uses, become part of an image copyright protection system designed to track violations of image copyright. This aggreement defines the terms under which Reykjavík University and the TexMex team can obtain access to the image collection of Morgunblaðið while Morgunblaðið will have use of PvS software. This collection consists of about 300,000 high-resolution images. The images were delivered to us after being thumbnailed to 512x512 pixels, which is sufficient for performing extensive recognition-based performance measurements. We can keep the images for two years. Then, we have to destroy them. Their descriptions, however, can be kept as long as needed for research and development purposes, since this format does not allow for any presentation or reconstruction of the images.
   It is extremely difficult to get access to real image collections, and signing this aggreement gave us a real push since we were able to conduct a series of experiments at a scale never reached. That work resulted in a publication in ACM Multimedia, the premier annual multimedia conference, as well as a prototype demonstration in that same conference. This is described next. 
2. ACM Multimedia 2006: paper "Scalability of Local Image Descriptors: A Comparative Study". The bulk of the work achieved in 2006 was focused on refining our fast and scalable multidimensional indexing scheme called PvS. In short, the extensive performance experiments measuring response times convinced us that we came up with an efficient and scalable database support. We therefore started to study the scalability of local image descriptors that are used in key applications including face recognition, shape recognition and image copyright protection. With these schemes, each image yields many descriptors (several hundreds for high-quality images), where each descriptor describes a small ``local'' area of the image. Two images are typically considered similar when many of their descriptors are found to be similar.
   All of these approaches, however, have only been studied and compared at a small scale (typically less than few hundred images). Overall, all existing studies fail to predict how local description schemes will perform with collections of tens of thousands of images or more. In [14], we have demonstrated that our PvS-framework achieves efficient query processing for large collections of local descriptors. We therefore decided to compare three major local descriptor schemes (SIFT, PCA-SIFT and RDTQ) to study their recognition power at large scale. This comparison included a fourth scheme that we designed, and called eff². Using a collection of almost thirty thousand images, we showed that our new descriptor scheme gives the best results in almost all cases. We then gave two stop rules to reduce query processing time and show that in many cases only a few query descriptors must be processed to find matching images.  Finally, we test our descriptors on a collection of over three hundred thousand images (these are the Morgunblaðið images), resulting in over 200 million local descriptors, and show that even at such a large scale the results are still of high quality, with no change in query processing time.
3. ACM Multimedia 2006: demo "Blazingly Fast Image Copyright Enforcement". Many photo agencies use the web to sell access to their image collections. Despite significant security measures, images may be stolen and distributed, making it necessary to detect copyright violations.  Our demonstration paper describes a content-based system for large-scale automatic copyright enforcement. It briefly describes the image description, indexing and retrieval algorithm that lie at the heart of the system.
   It also describes our proposed demonstration, which is a realistic scenario of copyright violations of a large image collection. The image collection used in the demonstration consists of 287,268 high-quality news images, resulting in 169,159,548 descriptors of 72-dimensions.  During the conference, we will take many "news"' photos such that we are constantly updating our image collection.  We will demonstrate, by "stealing'' and modifying new and old images, that the system practically always finds a match to copyright violations.  Overall, this demonstration will show that our system offers robust and effective descriptions, dynamic storage and blazingly fast retrieval.  More importantly, it will show that these desirable properties hold even at a very large scale.
4. Based on the experience gained with the PvS-framework, we have designed a more sophisticated and general index which is also based on ranking, projections and partitions. This index is called the NV-tree (Nearest Vector tree) and we are in the process of patenting it. With respect to the PvS-framework, the NV-tree yields better performance and space utilization, is better able to capture the real distribution of data by self-tuning the projection and partitioning strategies, copes with on-the-fly updates of the descriptor collections, can be used stand-alone or by aggregating the results from two or more indices, and lends itself effectively to distributed processing to further reduce response times. All in all, the NV-tree yields efficient query processing and good result quality with extremely large descriptor collections.
5. In March 2006, we published an article describing our work in the issue # 53 of the Newsletter of INRIA. This article, entitled "Un logiciel pour identifier rapidement les images piratées / A Software for Fast Identification of Pirated Images" was for some time in the front page of INRIA, as a typical example of good international cooperation. Roughly at the same time, we also published an article in a French popular scientific magazine called "Science & Vie Junior", entitled "Des images piratées débusquées en 1 seconde" (unfortunately, subscription is needed to read the article). Also, we had a article in the Les Échos economic newspaper on April 12, entitled "A la recherche d'images piratées". We had another article in the scientific journal of the CNRS, published in the issue number 197 of June 2006, entitled "Un logiciel contre le vol d'images". Finaly, we were asked by an editor named "Techniques pour l'ingénieur" (see here) to write an extended article describing not only our techniques but also the context within which enforcing copyright protection is key. This article, entitled "Contrer le piratage d'images : un logiciel précis et rapide" will be published in February 2007.

1. Sequences. As described in this document, we can today quite well exploit rather large databases of still images and we know how to efficiently query them by contents. The next step asks to turn our focus on more complex documents, typically video and audio. There are today several description techniques for audio and video but only very few techniques to efficiently perform query-by-content on video or audio databases. Being able to use such techniques is particularly crucial for professional multimedia archivers.
   People working in such organizations typically want to annotate incoming video or audio streams before archiving. Those annotations are then used by any subsequent search since they are at the roots of document matching. It is key to note that document annotation is an entirely manual process and to understand that this process can not scale with the constantly increasing number of streams to annotate. Therefore, one salient application is the automated segmentation of multimedia streams into separate units, then the automatic annotation of each unit, before archiving the documents. It is thus necessary to perform searches in streams to detect for example jingles, trailers, or the periodic broadcast of elements, etc. Those searches are more complex then searching simply for the repetition of identical patterns since it is necessary to find correlations despites distortions, duration variations, super-imposition of noise, text, additional music, inclusion of multiple side-streams, etc.
   The state of the art make such searches possible, but only at a very small scale, i.e., on a very small amount of data. Today, no search technique is efficient enough to allow any practical usage of real-scale audio or video archive. In addition, it has been observed that it is not possible to simply extend existing multidimensional indexing techniques since they were designed for description schemes in which the concept of sequences is lacking. One of the most prevalent difficulties comes from the temporal aspect of video and/or audio descriptions. Describing video and audio means creating sequences of descriptions in which the notion of order between descriptions is central. That notion of order is ignored by all traditional search techniques that only search for independent elements that are, at most, very loosely coupled. We therefore try to understand how multidimensional indexing techniques can integrate in their principles the notion of sequences of descriptions. This needs to be done to make possible searches by content in very large archives of video and/or audio documents.
   We have started to work on this topic with a student in France named Romain Tavenard. Romain is starting a PhD with Laurent Amsaleg. Romain has implemented few techniques from the state of the art (exhaustive search, dynamic time warping, mixture of Gaussian models and SVM-based modelling) and ran performance evaluations on audio recognition. Using a collection of real audio sample, he checked the ability of each technique to handle recognition despite time shifts, time distortions and some other signal distortions. It turns out that SVM-based models perform quite nicely but are very inefficient in terms of response time. This open room for improvement.
   In parallel to this study, processing huge corpuses of audiovisual content enforces the need to create an adapted infrastructure. This infrastructure has to cope with three main constraints: First, data management and storage aspects are crucial; Two, video or sound analysis tools consume a large part of the computer processing power; Three, that infrastructure must be easily accessible, independently of the operating system used by the client. An engineer at IRISA (Arnaud Dupuis) designed a client/server solution built to facilitate the processing and indexing of video (and audio shortly). In this context, we had one internship (Lian Liu) who worked on completing the ground truth on our three weeks video dataset. It was thus mainly to check manually the consistency of the existing ground truth and to create the ground truth on the last week of the corpus. Creating this ground truth meant to parse the video stream in order to find the boundaries of the television programs and assign them a title. This was done using the infrastructure.
2. Personal Image Collections. In recent years, the world has seen a tremendous increase in the capability to create, share and store digital images. As a result, personal image collections are growing at an astounding rate and it is clear that in the future individuals will need to access tens of thousands, or even hundreds of thousands, of digital images. It is therefore imperative to start studying ways to access these images in a useful and interesting manner. What is needed is software that will allow users to seamlessly organize, search and browse their images. Kari Hardarson will carry out the research needed to progress on this topic. Kari has held a full-time teaching position at Reykjavik University for several years. He has an M.Sc. degree in computer science from the University of North Carolina, Chapel Hill, and has already started working towards a Ph.D. degree at Reykjavik. We have sent a grant application to Rannis that will be used to reduce Kari's teaching load by about 50%, to allow him the time to conduct his research. So far, Kari has investigated the state-of-the-art in this area in detail, including the installation and testing of several research prototypes. Next, he will start working towards a flexible prototype for use in our research.
   
   

1. Hafþór Guðnason. Median Rank in Face Recognition, M.Sc. thesis, Reykjavík University, June 1st, 2006.
2. Friðrik Heiðar Ásmundsson. The NV-Network: A Distributed Architecture for High Throughput Image Retrieval, M.Sc. thesis, Reykjavík University, August 21st, 2006.
3. In 2005, I was involved in the following committee, but forgot to mention it in last year's report: Herwig Lejsek. The PvS-Index, M.Sc. thesis, Reykjavík University, June 20, 2005.