Content-based Copy Retrieval using Distortion-based Probabilistic Similarity Search

Alexis Joly (1) , Olivier Buisson (2) and Carl Frélicot (3) Abstract-Content-based copy retrieval (CBCR) aims at retrieving in a database all the modified versions or the previous versions of a given candidate object. In this paper, we present a copy retrieval scheme based on local features that can deal with very large databases both in terms of quality and speed. We first propose a new approximate similarity search technique in which the probabilistic selection of the feature space regions is not based on the distribution in the database but on the distribution of the features distortion. Since our CBCR framework is based on local features, the approximation can be strong and reduce drastically the amount of data to explore. Furthermore, we show how the discrimination of the global retrieval can be enhanced during its post-processing step, by considering only the geometrically consistent matches. This framework is applied to robust video copy retrieval and extensive experiments are presented to study the interactions between the approximate search and the retrieval efficiency. Largest used database contains more than one billion local features corresponding to 30, 000 hours of video.

I. INTRODUCTION

T HE principle of CBCR is close to usual Content-Based Image or Video Retrieval schemes (CBIR) when using the query by example paradigm [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF], [START_REF] Boujemaa | What's beyond query by exemple?[END_REF], [START_REF] Vu | Image retrieval based on regions of interest[END_REF], [START_REF] Niblack | The qbic project: Quering images by content using color, texture, and shape[END_REF]. One difference is that the queries are not examples given by a user but a stream of candidate documents automatically extracted from a particular medium (for example a television stream or a web downloader). The other and main difference is that the objects in demand are not the same. While general CBIR methods try to bridge the semantic gap, CBCR aims at recognizing a given document. Content-based retrieval methods dedicated to copy detection have emerged in recent years for monitoring and copyright protection issues [START_REF] Berrani | Robust content-based image searches for copyright protection[END_REF], [START_REF] Joly | Robust content-based video copy identification in a large reference database[END_REF], [START_REF] Ke | Efficient near-duplicate detection and sub-image retrieval[END_REF], [START_REF] Chang | Rime -a replicated image detector for the world-wide web[END_REF], [START_REF] Hampapur | Comparison of sequence matching techniques for video copy detection[END_REF]. In this context, contrary to the watermarking approach, the identification of a document is not based on previously inserted marks but on contentbased extracted signatures. These signatures are searched in an indexed database containing the signatures of all source documents and the retrieval can be performed without accessing the original documents. One of the main advantage of the content-based approach is that copies of already existing materials can be detected even if the original document was not marked or is no more existing. Copyright and monitoring issues are however not the only motivation for CBCR and very promising applications are (1) Alexis Joly is with INRIA Rocquencourt, 78153 Le Chesnay, France, alexis.joly@inria.fr, 01 39 63 56 97 (2) Olivier Buisson is with INA, 94366 Bry-sur-Marne, France, obuisson@ina.fr, 01 49 83 22 64 (3) Carl Frélicot is with the University of La Rochelle, 17042 La Rochelle, France, carl.frelicot@univ-lr.fr, 05 46 45 82 34 currently emerging such as database purge, cross-modal divergence detection or content-based web links creation. Automatic annotating is also a major prospect: all the versions of a given document correspond indeed to several utilization contexts and the links between them are highly informative. This could be easily used for semantic descriptions as illustrated by the two following television scenarios:

• A video which is broadcast the same day on several foreign channels refers to an international event.

• A video already having a lot of copies in the database distributed among a large period, refers to a major historical event.

More generally, a CBCR system is able to generate a lot of contextual links (utilization frequency, broadcast persistence, geographic dispersion, etc.) that could be exploited by data mining methods. Section I-A details the CBCR issue and gives basic definitions while previous work related to CBCR are discussed in section I-B. In the rest of the paper, we describe a complete CBCR framework based on local features and applied to television monitoring (section II). The main originality of this work is a new approximate similarity search technique that takes into account the special nature of a copy. The corresponding search algorithm in a multidimensional indexing structure is described and appear to be partially sublinear in database size. The other key point of our work is the study of the interactions between the retrieval and the computational performances. Intensive experiments on large and realistic databases are reported in section III. They show how the different stages of our framework enable to fullfill both the high discrimination and speed requirements of CBCR.

A. Background D UPLICATES and near-duplicates retrieval methods have emerged in recent years for a variety of applications, such as consumer photograph collections organization [START_REF] Jaimes | Duplicate detection in consumer photography and news video[END_REF], [START_REF] Meng | Enhancing dpf for near-replica image recognition[END_REF], [START_REF] Jaimes | Detection of non-identical duplicate consumer photographs[END_REF], [START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "how do i organize my holiday snaps?[END_REF], multimedia linking [START_REF] Zhang | Detecting image near-duplicate by stochastic attributed relational graph matching with learning[END_REF], copyright infringement detection [START_REF] Berrani | Robust content-based image searches for copyright protection[END_REF], [START_REF] Joly | Robust content-based video copy identification in a large reference database[END_REF], [START_REF] Hsu | Geometric distortion-resilient image hashing system and its application scalability[END_REF], [START_REF] Hampapur | Comparison of sequence matching techniques for video copy detection[END_REF], [START_REF] Chang | Rime -a replicated image detector for the world-wide web[END_REF] or forged image detection [START_REF] Ke | Efficient near-duplicate detection and sub-image retrieval[END_REF]. In this paper, we focus on the content-based copy retrieval problem which generally consists of monitoring a specific medium to retrieve copies in a large reference database. A copy of an original document is not systematically an exactduplicate but in most cases a transformed version of the original document. According to the literature definitions [START_REF] Jaimes | Duplicate detection in consumer photography and news video[END_REF], [START_REF] Zhang | Detecting image near-duplicate by stochastic attributed relational graph matching with learning[END_REF], a copy can be see as a duplicate for which the capturing conditions can not differ (camera view angle, scene lighting conditions, camera parameters, etc.). Two copies are somehow derived from the same original document. Two documents and their copy are displayed on Figure 1. The first copy is a typical televisual post-production example and the applied transformations are mainly resizing and a frame addition. In the second example, the copy was obtained by a poor kinescope (a film made of a live television broadcast). Figure 2 presents a more ambiguous case since the documents represent two different scenes and none of them is a copy of the other one. However, both of them could be considered as copies of the France map displayed in the background. On the other hand, although they are similar in a sense, none of the two images displayed on Figure 3 is a copy of the other one and they do not have a common original document. Note that, in the end, two documents that are not copies could be visually more similar than a copy obtained after a strong image processing. In practice, however, whatever the application is (copyright protection, multimedia linking, etc.), there is a subjective limit to the tolerated transformations and what is meant by copy remains a document that is visually similar. In the end, a copy is both a transformed version of a document that remains recognizable. We propose a definition of what a copy is, based on the notion of tolerated transformations:

Definition Copy -A document O 1 is a copy of a document O, if O 1 = t(O), t ∈ T ,
where T is a set of tolerated transformations. O is called the original document.

Note that T can contain combinations of several transformations and a document

O 3 = t 3 • t 2 • t 1 (O), t 1 ∈ T, t 2 ∈ T, t 3 ∈ T can be a copy of O as well as the intermediate documents O 1 = t 1 (O) and O 2 = t 2 •t 1 (O).
Given an original document O, it is possible to construct a tree of all its copies as illustrated on Figure 4. Note that, although all the documents of the tree are copies of the same original document O, they are not necessarily copies of each other, if we strictly respect the formal definition.

The general term copy retrieval we use in this paper refers to any document of the tree (all the copies of the original document(s) from which the query is derived from). We can notice on Figure 4 that the use of watermarking for the detection of copyright infringement only allows the detection of the copies of the referenced object. The content-based approach enables the detection of all the copies of the original object.

B. Related work

The works related to CBCR are not necessarily dedicated to copy retrieval. In a sense, all content-based image retrieval (CBIR) systems using the query-by-example paradigm are potentially applicable to copy retrieval. It would be too long to list all of the CBIR works and we let the reader refer to more complete reviews [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF], [START_REF] Boujemaa | What's beyond query by exemple?[END_REF], [START_REF] Vu | Image retrieval based on regions of interest[END_REF]. However, usual CBIR schemes are generally neither fast enough nor discriminant enough. Most of them are based on color, texture and shape global features that are relevant in a generalization context but not in a copy recognition context which requires more discrimination. In [START_REF] Doermann | The detection of duplicates in document image databases[END_REF], the authors are interested in detecting duplicates in document image databases (i.e scanned textual documents). The features they use are however dedicated to a textual content and not applicable to other documents. The first system entirely dedicated to image copy retrieval is the RIME system [START_REF] Chang | Rime -a replicated image detector for the world-wide web[END_REF] in which the extracted features are Daubechies wavelets coefficients. Unfortunately, no efficient similarity search strategy is proposed and the tolerated transformations are very light, excluding cropping, shifting or compositing. Several works are dedicated to the search of duplicates or near-duplicates in consumer photograph databases [START_REF] Jaimes | Duplicate detection in consumer photography and news video[END_REF], [START_REF] Meng | Enhancing dpf for near-replica image recognition[END_REF], [START_REF] Jaimes | Detection of non-identical duplicate consumer photographs[END_REF], [START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "how do i organize my holiday snaps?[END_REF], [START_REF] Zhang | Detecting image near-duplicate by stochastic attributed relational graph matching with learning[END_REF]. Two different scenarios can be distinguished: duplicate retrieval and duplicate detection [START_REF] Zhang | Detecting image near-duplicate by stochastic attributed relational graph matching with learning[END_REF]. Duplicate retrieval aims at finding all images that are duplicate to an input query image, internal or external to the source image database. Duplicate detection aims at finding all duplicate image pairs given all possible pairs from the source image database. The second scenario is a more challenging task since the number of possible pairs increases in a quadratic speed [START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "how do i organize my holiday snaps?[END_REF]. The first scenario is very close to the copy retrieval problem. However, in practice, most of the proposed methods use direct and complex image to image comparisons whereas we are interested in finding documents only thanks to the similarity search of their signature(s) (and eventually the post-processing of associated data). Jaimes and al. [START_REF] Jaimes | Detection of non-identical duplicate consumer photographs[END_REF], for example, use block based correlation computed after global alignment of image pairs. In [START_REF] Zhang | Detecting image near-duplicate by stochastic attributed relational graph matching with learning[END_REF], Zhang and al. proposed a near-duplicate detection by Stochastic Attributed Relational Graph Matching. Using such image to image comparisons provide very good results in terms of robustness and discrimination but prevent the use of large databases. From a storage point of view, the monitoring of a specific medium can not be processed faced to the signature database only. And from the computational point of view, efficient similarity query algorithm [START_REF] Böhm | Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases[END_REF] can not be used to speed up the search. In [START_REF] Yuan | Fast and robust short video clip search using an index structure[END_REF], Yuan and al. give a complete list of all query-by-videoclip methods developed in the last decade. They classify them in three main categories depending on their ability to detect high level similarity [START_REF] Jain | Query by video clip[END_REF], [START_REF] Ferman | Robust color histogram descriptors for video segment retrieval and identification[END_REF], copies [START_REF] Joly | Robust content-based video copy identification in a large reference database[END_REF], [START_REF] Cheung | Fast similarity search and clustering of video sequences on the world-wide-web[END_REF] or near-exact copies [START_REF] Kashino | A quick search method for audio and video signals based on histogram pruning[END_REF], [START_REF] Oostveen | Feature extraction and a database strategy for video fingerprinting[END_REF], [START_REF] Lienhart | On the detection and recognition of television commercials[END_REF], [START_REF] Pua | Real time repeated video sequence identification[END_REF], [START_REF] Hampapur | Comparison of sequence matching techniques for video copy detection[END_REF]. The idea behind the last category is that the low robustness requirements enable the use of very high compression rates and no multidimensional indexing structure is needed. The typical application of such methods is the detection of commercials or sponsoring and they are not applicable to more general copy retrieval applications for which the transformations are stronger. Furthermore, the database size is usually much smaller. Some of them are even dedicated to the detection of replicated sequences in a video stream and the problem is quite different from retrieving copies in a large static reference set. In [START_REF] Cheung | Fast similarity search and clustering of video sequences on the world-wide-web[END_REF], Cheung and al. propose a randomized algorithm called ViSig, aimed at measuring the fraction of visually similar frames shared between two sequences. The similarity search is accelerated by a new similarity search technique combining triangle inequality based pruning and a classical principal component analysis approach to reduce the dimension of the feature vectors. The technique enables fast and robust video copy retrieval on the world-wide-web with a large database including more than 1000 hours of video. Recently, Meng and al. [START_REF] Meng | Enhancing dpf for near-replica image recognition[END_REF] have used multi-scale color and texture features to characterize images and employ the Dynamic Partial Function (DPF) to measure the perceptual similarity of images [START_REF] Meng | Enhancing dpf for near-replica image recognition[END_REF]. Although the DPF outperforms traditional distance metrics, the global image feature they use limits the resistance to cropping, shifting or compositing. Furthermore, the DPF is not a metric and prevents the use of most similarity search techniques [START_REF] Böhm | Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases[END_REF]. Contrary to the approaches based on blocks [START_REF] Hampapur | Comparison of sequence matching techniques for video copy detection[END_REF], local features based approaches [START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "how do i organize my holiday snaps?[END_REF], [START_REF] Zhang | Detecting image near-duplicate by stochastic attributed relational graph matching with learning[END_REF], [START_REF] Hsu | Geometric distortion-resilient image hashing system and its application scalability[END_REF], [START_REF] Ke | Efficient near-duplicate detection and sub-image retrieval[END_REF], [START_REF] Joly | Robust content-based video copy identification in a large reference database[END_REF], [START_REF] Berrani | Robust content-based image searches for copyright protection[END_REF] give the best results in terms of robustness to cropping, shifting or compositing. In [START_REF] Hsu | Geometric distortion-resilient image hashing system and its application scalability[END_REF], the authors propose a mesh-based image copy retrieval method which is robust to severe image transformations. Computational performances are however not tackled in their study. Copy retrieval based on interest points and indexed local signatures has been proposed in [START_REF] Berrani | Robust content-based image searches for copyright protection[END_REF] for still images and in our previous work for video [START_REF] Joly | Robust content-based video copy identification in a large reference database[END_REF]. Such approaches enable to deal with both robustness and speed even with very large databases. The computationally critical step consisting of finding similar local features can be speed up by using multidimensional indexing structures and efficient similarity query algorithm. The final similarity measure between two documents is postponed to the post-processing of the partial results which can eventually contain associated data such as interest points position, orientation or characteristic scale [START_REF] Schaffalitzky | Multi-view matching for unordered image sets, or "how do i organize my holiday snaps?[END_REF], [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. Recently, this approach has been used again for image copy retrieval in [START_REF] Ke | Efficient near-duplicate detection and sub-image retrieval[END_REF], but with more recent distinctive points detector and local descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. The experiments reported in this work show again that this strategy outperforms the others in terms of discrimination, robustness and speed.

II. CONTENT-BASED COPY RETRIEVAL FRAMEWORK

An overview of the proposed CBCR framework is given on Figure 5. Although it is dedicated to video copy retrieval, it can be easily adapted to still images. The retrieval stage itself includes three main steps that will be discussed in this section: a local features extraction (section II-A), a new approximate similarity search technique (section II-B) and a post-processing step based on a registration algorithm and a vote (section II-C). The global principle of the retrieval can be summarized as follows: once the local features have been extracted from a candidate video sequence, they are individually searched in the database via the probabilistic similarity search technique. The search of each local feature provides a partial result consisting in a set of similar local features (called neighbors). The partial results obtained for all the candidate local features are then merged by the post-processing which consists in counting the number of geometrically-consistent local matches between the candidate sequence and the retrieved sequences (i.e. the reference video sequences having at least one of their local feature represented in the partial results).

A. Local features

The local features used in our video CBCR framework are those described in [START_REF] Joly | Robust content-based video copy identification in a large reference database[END_REF]. They are based on an improved version of the Harris interest point detector [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF] and a differential description of the local region around each interest point. To increase the compression, the features are not extracted in every frame of the video but only in key-frames corresponding to extrema of the global intensity of motion [START_REF] Eickeler | Content-based video indexing of tv broadcast news using hidden markov models[END_REF]. The final

S = s 1 s 1 , s 2 s 2 , s 3 s 3 , s 4 s 4
where the s i are 5-dimensional sub-vectors computed at four different spatio-temporal positions distributed around the interest point. Each s i is the differential decomposition of the gray level 2D signal I(x, y) up to the second order:

s i = ∂I ∂x , ∂I ∂y , ∂ 2 I ∂x∂y , ∂ 2 I ∂x 2 , ∂ 2 I ∂y 2 B. Distortion-based Probabilistic Similarity Search (DP S 2 )
Once a local feature S has been extracted from the candidate video sequence, the similar local features are searched in the database via the DP S 2 technique. After discussing the previous work related to the similarity search issue (II-B.1), we will present the DP S 2 paradigm (II-B.2) and then briefly describe the indexing structure and the search algorithm we have developed (II-B.3).

1) Related work: Efficient similarity search in large

databases is an important issue in all content-based retrieval schemes. In its essence, the similarity query paradigm [START_REF] Böhm | Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases[END_REF] is to find similar documents by searching similar features in a database. A distance between the features is generally used to perform K-nearest neighbors queries or -range queries in the features database. To solve this problem, multidimensional index structures such as R-tree family techniques [START_REF] Beckmann | The r*-tree: an efficient and robust access method for points and rectangles[END_REF], [START_REF] Berchtold | The x-tree: An index structure for high-dimensional data[END_REF], [START_REF] Katayama | The sr-tree: An index structure for highdimensional nearest neighbor queries[END_REF] have been proposed but their performances are known to degrade seriously when the dimension increases [START_REF] Weber | A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces[END_REF]. To overcome this dimensionality curse, other index structures have been proposed, e.g. the pyramid tree [START_REF] Berchtold | The pyramid-tree: breaking the curse of dimensionality[END_REF] or dimension reduction techniques [START_REF] Faloutsos | Fastmap: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets[END_REF]. Sometimes, a simple sequential scan or other sequential techniques such as the V A-file are even more useful than all other structures [START_REF] Weber | A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces[END_REF]. However, the search time remains too high for many of the emerging multimedia applications and especially those using local features [START_REF] Amsaleg | Robust object recognition in images and the related database problems[END_REF]. During the last few years, researchers have been interested in trading quality for time and the paradigm of approximate similarity search has emerged [START_REF] Indyk | Approximate nearest neighbors: towards removing the curse of dimensionality[END_REF], [START_REF] Zezula | Approximate similarity retrieval with m-trees[END_REF], [START_REF] Ciaccia | Pac nearest neighbor queries: Approximate and controlled search in high-dimensional and metric spaces[END_REF], [START_REF] Weber | Trading quality for time with nearest neighbor search[END_REF], [START_REF] Li | Clustering for approximate similarity search in high-dimensional spaces[END_REF], [START_REF] Bennett | Density-based indexing for approximate nearest-neighbor queries[END_REF], [START_REF] Berrani | Approximate searches: kneighbors + precision[END_REF], [START_REF] Tuncel | Vq-index: An index structure for similarity searching in multimedia databases[END_REF], [START_REF] Houle | Fast approximate similarity search in extremely high-dimensional data sets[END_REF]. The principle is to speed-up the search by returning only an approximation of the exact query results, according to an accuracy measure. Some of the first proposed approximate solutions are simply extensions of exact methods to the search of -KN N [START_REF] Zezula | Approximate similarity retrieval with m-trees[END_REF], [START_REF] Weber | Trading quality for time with nearest neighbor search[END_REF], [START_REF] Ciaccia | Pac nearest neighbor queries: Approximate and controlled search in high-dimensional and metric spaces[END_REF]; a -KN N being an object whose distance to the query is lower than (1 + ) times the distance of the true k-th nearest neighbor. represents the maximal relative error between the true nearest neighbors and the retrieved neighbors. In [START_REF] Weber | Trading quality for time with nearest neighbor search[END_REF], Weber and al. propose an approximate version of the V A-file which is about 5 times faster than the exact version when 20% of the exact KN N are lost. The main drawback of the V A-file is that it is strictly linear in database size and that it is profitable only for a disk storage. In [START_REF] Zezula | Approximate similarity retrieval with m-trees[END_REF], Zezula and al. deal with -KN N in a M -tree, a convenient indexing structure for general metric distance measures. The performance gain is around 20 for a recall of 50% compared to exact results. They however remarked that the real relative error was in practice seriously lower than the theoretical value . The accuracy of the search is therefore not controlled. To solve this, Ciaccia and al. [START_REF] Ciaccia | Pac nearest neighbor queries: Approximate and controlled search in high-dimensional and metric spaces[END_REF] propose another M -tree based approximate method whose accuracy is enhanced thanks to an analyse of the distances distribution between the objects of the database. However, the assumption that the global distribution is a good estimator for the local query-to-element distribution presupposes that the distributions from all queries are similar, which is often not the case. Clustering-based approximate methods have also been proposed to achieve substantial speed-ups over sequential scan [START_REF] Ferhatosmanoglu | Approximate nearest neighbor searching in multimedia databases[END_REF], [START_REF] Li | Clustering for approximate similarity search in high-dimensional spaces[END_REF], [START_REF] Berrani | Approximate searches: kneighbors + precision[END_REF]. As a pre-processing step, these algorithms partition the data into clusters. To handle a query, the clusters are ranked according to their similarity with the query vector and only the more relevant clusters are visited. These methods are efficient only if the data are well partitionable into clusters and their performances are therefore highly dependent of the data distribution. Another common drawback is that the clusters preprocessing are time consuming algorithms which can be prohibitive for very large databases. The approach of Ferhatosmanoglu and al. uses the well-known K-means heuristic to generate a large number of small clusters. The queries are handled by an original iterative selection of the clusters based only on the first few coordinates of the vector representation. It can potentially speed-up the query processing by an order of magnitude or more. The main drawback of the K-means algorithm is that it produces poor-quality clusters degrading the efficiency of the data filtering. The CLINDEX method, proposed by Li and al. [START_REF] Li | Clustering for approximate similarity search in high-dimensional spaces[END_REF], is based on a very different clustering scheme. The partition is processed via an efficient bottom-up cluster-growing technique, relative to a grid partition of the domain. The search algorithm makes use of a fast index structure over the set of clusters and achieves speedups of roughly 21 times over sequential search at the 70% recall level. The accuracy of the search is however not controlled since the stopping criterion is only the number of visited clusters. At the opposite, the method of Berrani and al. [START_REF] Berrani | Approximate searches: kneighbors + precision[END_REF] allows an accurate control of the query results thanks to a probabilistic criterion preprocessed for each cluster. The adaptation of the BIRCH algorithm [START_REF] Zhang | Birch: An efficient data clustering method for very large databases[END_REF] to form the clusters also provides a better clustering in an acceptable computation time. A comparison with CLINDEX shows that this technique is 10 to 70 times faster than CLINDEX. The search time is however linear in database size which prevents the use of extremely large databases. The method of Benett and al. [START_REF] Bennett | Density-based indexing for approximate nearest-neighbor queries[END_REF] also use a probabilistic criterion to select the more relevant clusters but it is directly issued from the clustering process: A mixture of Gaussian distributions is estimated from the dataset thanks to the Expectation Maximisation algorithm and this probability density function is used to assess the probability that a given cluster contains a closer point than the neighbors already found. The main drawback is that the maximum number of clusters is strongly limited. The method is therefore limited to very specific distributions. Some approximate methods are based on a binary representation of the vectors and the use of a simple Hamming distance to compare them [START_REF] Indyk | Approximate nearest neighbors: towards removing the curse of dimensionality[END_REF], [START_REF] Miller | Audio fingerprinting: nearest neighbor search in high dimensional binary spaces[END_REF], [START_REF] Oostveen | Feature extraction and a database strategy for video fingerprinting[END_REF]. Kalker and al. proposed the use of an inverted list where the entries are sub-vectors of the complete binary vectors. A neighbor can then be retrieved only if one if its sub-vector remains unchanged which is a strong hypothesis. The technique is therefore very fast but the quality of the results is very poor and not controlled. In the binary scheme proposed by Miller and al. [START_REF] Miller | Audio fingerprinting: nearest neighbor search in high dimensional binary spaces[END_REF], the search in a binary tree is guided by estimating bit errors probabilities. This allows to have a control of the query results accuracy but only according to the Hamming distance. Furthermore, the bit errors are supposed to be uniformly distributed along the binary vectors which is a strong assumption. Indyk and al. [START_REF] Indyk | Approximate nearest neighbors: towards removing the curse of dimensionality[END_REF] developed a randomized locally-sensitive hashing method for vector data. Contrary to other binary schemes, the unary representation of the vectors, used to form the binary vectors, makes the Hamming distance in the binary transformed space equivalent to the L 1 distance in the original space. A set of hash functions is applied to the binary vectors and the similarity search issue is translated in terms of collision probability. The main advantages of the technique is that it is sub-linear in database size and that it tolerates high dimensions. However, like other binary schemes, the quality of the query results is poor [START_REF] Houle | Fast approximate similarity search in extremely high-dimensional data sets[END_REF] and their accuracy is not controlled. In [START_REF] Houle | Fast approximate similarity search in extremely high-dimensional data sets[END_REF], Houle and al. developed a practical index called SASH for approximate similarity queries in extremely highdimensional data without any assumption regarding the representation of the data. SASH is a multi-level structure of random samples connected to some of their neighbors. Queries are processed by first locating approximate neighbors within the sample, and then using the pre-established connections to discover neighbors within the remainder of the data set. The technique can return a large proportion of the true neighbors roughly 2 orders of magnitude faster than sequential scan for moderate dimensions and less than one order of magnitude for extremely high dimensions. Main drawbacks are the cost of the pre-processing step and the absence of query accuracy control. In the following subsection, we present our new similarity search technique. Contrary to the previous methods, it is not based on the approximation of an exact geometric query but directly on a distortion-based probabilistic query in the multidimensional vector space. The technique has two main advantages:

• Searching most probable signatures instead of signatures respecting a geometric criterion is less restricting and more relevant. Furthermore, no explicit metric is needed to select the relevant domain regions.

• As the queries are supposed to be entirely independent of the database distribution, the selection of the domain regions we need to visit can be determined without accessing the database. This makes the method easily distributable and very quick since no tree is needed.

2) Distortion-based probabilistic queries: Our distortionbased probabilistic queries can be introduced in terms of approximate range queries. Intuitively, the principle of an approximate range query would be the following: by excluding several regions of the query, having a too small intersection with the bounding regions of the index structure, it is possible to speed up the search without significantly degrading the results. However, it is not possible to directly take the volume as an error measure because it would be equivalent to consider that the relevant similar features are uniformly distributed inside the range query. When the dimension increases, the features following such a distribution become closer and closer to the surface of the hyper-sphere and this is not true in reality, as illustrated on Figure 6. The solid curve (left) is the real distribution of the distance between referenced and distorted features obtained by a representative combination of image transformations. The two other dotted curves represent the estimated probability density function for two probabilistic models: an uniform spherical distribution (right) which would be obtained if we took the volume as an error measure and a zero mean normal distribution under the independence assumption (center). The figure shows that the normal distribution is much closer to the real distribution than the uniform distribution. The proposed distortion-based probabilistic queries rely on the distribution of the relevant similar features for finding a transformed document. Let the distortion vector ∆S be defined as:

∆S = S (M ) -S (t M (M ))
where S (M ) is the feature of an image local region M and S (t M (M )) the distorted feature after transformation t M of the image. We define a distortion-based probabilistic query, associated to a probability equal to α, as the retrieval of all the database features contained in a region V α of the feature space satisfying:

Vα p ∆S (X -S) dX ≥ α ( 1
)
where S is the query (i.e. the candidate feature) and p ∆S (.) is the probability density function of the distortion.

Intuitively, the probabilistic query selects only the regions of the feature space for which the probability of finding a distorted signature is high in order to reduce the number of signatures to scan during the search: usually, the first step of a search in a multidimensional indexing structure is a set of geometric filtering rules that quickly exclude most of the bounding regions of the index partition that do not intersect with the query [START_REF] Böhm | Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases[END_REF]. To compute the probabilistic queries, we propose to replace the geometric rules by probabilistic rules, according to the distortion model. The main advantage of this strategy is that a probabilistic query has no intrinsic shape constraint. Thus, the region V α can be chosen so that it minimizes the number of bounding regions that need to be explored.

3) Indexing structure and search algorithm:

The indexing structure we use to process our distortion-based probabilistic queries is described in [START_REF] Joly | Feature statistical retrieval applied to content-based copy identification[END_REF]. It is a space-partition based and a static method (dynamic insertions or deletions are not possible). The partition is induced by the regular split of a Hilbert space-filling curve as illustrated on Figure 7. It results in a set of 2 p non overlapping and hyper-rectangular bounding regions, called p-blocks [START_REF] Joly | Feature statistical retrieval applied to content-based copy identification[END_REF], which are well-suited to compute quickly the integral of Eq. 1. The depth p of the partition is equal to the number of bits of the Hilbert derived keys used to access the data pages corresponding to each block. The probabilistic search algorithm [START_REF] Joly | Feature statistical retrieval applied to content-based copy identification[END_REF] is composed of two steps: a filtering step that selects the relevant p-blocks and a refinement step that exhaustively processes all the features belonging to the selected blocks. For computational efficiency, the probabilistic filtering step of our search algorithm relies on the assumption that the components of the distortion are independent:

p ∆S = D j=1 p ∆Sj
The distortion distribution is simply modeled by a zeromean normal distribution with the same standard deviation σ whatever the component is: The unique parameter σ of this isotropic distribution makes the probabilistic query more intuitive and closer to the approximate range query paradigm, σ replacing the usual radius. The probability of a p-block b can then be computed as:

p ∆Sj (x) = f N (0,σ) (x) (2)
b p ∆S (X -S) dX = D j=1 vj uj f N (0,σg ) (x j -s j )dx j
where u j and v j are the lower and upper bounds of the pblock b along the j th axis, s j and x j are the j th component of respectively a candidate feature S and any vector X of the feature space. For a p-depth partitioned space and a candidate feature S, the probabilistic query inequality (1), may be satisfied by finding a set B α of p-blocks such as:

card(Bα) i=1 b i p ∆S (X -S) dX ≥ α b i ⊂ B α , ∀i (3)
where card(B α ) ≤ 2 p is the number of blocks in B α .

In practice, card(B α ) should be minimum to limit the cost of the search. We refer to this particular solution as B min α . Its computation is not trivial because sorting the 2 p blocks according to their probability is not affordable. Nevertheless, it is possible to quickly identify the set B(τ ) containing all the blocks having a probability greater than a fixed threshold

τ : B(τ ) = b i / b i p ∆S (X -S) dX > τ
The total probability of B(τ ) is given by:

P Σ (τ ) = card(B(τ )) i=1 b i p ∆S (X -S) dX
B(τ ) and P Σ (τ ) are computed thanks to a simple hierarchical algorithm based on the iterative increase of the partition depth (from p 1 = 1 to p p = p). At each iteration, only the blocks having a probability higher than α are kept in a priority queue. Since card(B(τ )) decreases with τ , finding B min α is equivalent to finding τ min verifying:

P Σ (τ min ) ≥ α ∀τ > τ min , P Σ (τ min ) < α (4)
As P Σ (τ ) also decreases with τ , τ min can be easily approximated by a method inspired by Newton-Raphson technique (the hierarchical algorithm is applied several times). The refinement step of the DP S 2 technique computes the L 2 distance between the query and all the vectors belonging to the selected blocks. The final results can be selected either by a K-nearest neighbor search or by a range search. As explained before, we generally prefer a range search strategy and the radius r σ is set in order to guarantee a final probability α f higher than α -0.1% (see appendix I). This range search allows to exclude a large part of the features selected by the probabilistic filtering step while preserving a final probability very close to α. The partition depth p is of major importance since it directly influences the search time t s of the DP S 2 technique:

t s (p) = t f (p) + t r (p)
The time of the filtering step t f (p) is strictly increasing with p because the number of p-blocks in B min α and thus the computation time increase with p. The refinement time t r (p) is decreasing because the selectivity of the filtering step increases, i.e the number of features belonging to the selected blocks decreases with p. The search time t s (p) has generally only one minimum at p min which can be set at the start of the system in order to obtain the best average response time. In practice, p min depends particularly on the database size and the storage support. Storing on disk makes the filtering step depending mainly on the disk access time whereas it depends mainly on CPU time when running in main memory. These costs differ from 3 orders of magnitude whereas the costs of the refinement step differ only from one order of magnitude. Therefore, the optimal depth is lower for a disk storage (from about 7 unity) and the search time is about 100 times slower.

4) Comparison to exact range queries:

Here we do not aim at testing the relevance of the distorsion model, but only at showing the advantage of a statistical query compared to an exact range query when the distortion model (see Equ. 2) is supposed to be exact. We randomly selected 1000 signatures in a real database and computed the filtering step of our similarity search technique for both a probabilistic query and an exact range query. The radius of the range query is set in order to have the same probability α than the probabilistic query. For varying values of α, we measured the average number of p-blocks intercepted by both queries (Fig. 8). The figure clearly show that the probabilistic query is widely more profitable than the exact range query: the same probability can be expected with 30 to 100 times less blocks to visit, depending on α. The default of the exact range query is its rigid shape which intercepts a lot of unlikely blocks. On the contrary, the probabilistic query selects the optimal set of blocks for the desired probability.

C. Registration and Vote

Once the local features have been searched in the database, the partial results must be post-processed to compute a global similarity measure and to decide if the more similar documents are copies of the candidate document. Usually, this step is performed by a vote on the document identifier provided with each retrieved local feature [START_REF] Schmid | Local grayvalue invariants for image retrieval[END_REF], [START_REF] Berrani | Robust content-based image searches for copyright protection[END_REF]. Thus, the similarity between the candidate document and the retrieved documents is measured by the number of local matches. This method is robust to strong geometric transformations since it does not care about the points relative position. However, as the geometry of the image is ignored, it can induce confusion between two images having similar local features but which are not copies from each other. Another method consists in keeping, for each retrieved document, only the matches which are geometrically-consistent with a global transform model [START_REF] Mikolajczyk | A comparison of affine region detectors[END_REF], [START_REF] Ke | Efficient near-duplicate detection and sub-image retrieval[END_REF], [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF], [START_REF] Rothganger | Object modeling and recognition using local affine-invariant image descriptors and multiview spatial contraints[END_REF], [START_REF] Jaimes | Detection of non-identical duplicate consumer photographs[END_REF]. The principle is to use the associated points position of the retrieved local features to estimate the parameters of the model. The vote is then applied by counting only the matches that respect the model (registration + vote strategy). The choice of the model characterizes the tolerated transformations. In this paper, we consider only resize, rotation and translation for the spatial transformations and also slow/accelerated motion from the temporal point of view:

  x y t c   =   r cosθ -r sinθ 0 r sinθ r cosθ 0 0 0 a t     x y t c   +   b x b y b t  
(5) where (x , y , t c ) and (x, y, t c ) are the spatio-temporal coordinates of two matching points. A candidate video sequence is defined as a set of n f successive key-frames (typically n f = 9, i.e about 11 seconds of video), containing n c local features that will be searched in the database. The similarity search technique provides for each of the n c candidate local features a set of matches characterized by their spatio-temporal position and an identifier V h defining the referenced video clip to which the feature belongs. All the matches of the candidate sequence are first sorted according to the value of their identifier and the transformation model parameters are estimated for each retrieved video clip V h thanks to a random sample consensus (RANSAC [START_REF] Fischler | Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[END_REF]) algorithm. For each candidate local feature, only the best match in each retrieved video clip V h is kept for the estimation (according to the L 2 distance between signatures). Once the transformation model has been estimated, the final similarity measure m(V h ) related to a retrieved video clip V h consists in counting the number of matching points that respects the model according to a small spatio-temporal precision. At the end, the similarity measure m(V h ) is thresholded to decide whether the document V h is a copy or not. m is lower or equal than n c , the number of local features in the candidate video sequence and its expected value E(m) can be ideally expressed as:

E(m) = n c R α
where R is the repeatability of the interest points detector (rate of points that remain stable after image transformation) and α the query probability.

III. EXPERIMENTAL EVALUATION

Section III-A describes the common experimental setup. Section III-B discusses the influence and the settings of the DP S 2 parameters. Section III-C presents a comparison between exact range queries and probabilistic queries. Section III-D aims at studying the influence of the database size on both the computational performances and the retrieval performances. Section III-E presents some experiments on a real ground truth and some results obtained from a TV monitoring.

A. Experimental setup

The video sequences used to construct the signatures databases come from the so-called SNC database stored at the French Institut National de l'Audiovisuel (INA), whose main tasks include collecting and exploiting French television broadcasts. The SNC video sequences are stored in M P EG1 format with an image size of 352×288. They contain all kinds of TV broadcasts from the Forties to the present: news, sport, shows, variety, films, reports, black&white archives, advertisements, etc. They also contain noise, black sequences, test cards which potentially degrade any experimental assessment. The databases used in the following experiments are randomly selected subparts of the SNC database and we note S H a randomly selected subpart containing H hours of video (the smallest used database is S 100 containing 100 hours of video and the largest S 30000 containing 30, 000 hours of video). Experiments were carried out on a Pentium IV (CPU 2.5 GHz, cache size 512Kb, RAM 1.5 Gb) and the response times were obtained with unix getrusage() command. Recall, precision and false alarm probability metrics are defined as: I. These 100 transformed video clips represent the true probes and a true positive occurs when the original video clip in S H is well retrieved with a temporal precision of 2 images. The false probes come from a foreign TV channel capture that is supposed to never broadcast archives belonging to the french SN C database (the most confident matches were manually controlled to confirm this hypothesis). This query video set is referred as Q F and it is 10 times longer than Q H , in order to have a more realistic precision measure. The total length of all the queries

(Q H + Q F ) is

B. DP S 2 parameters discussion

1) Estimation of σ: We applied four kind of transformations with increasing parameters value to 30 randomly selected video sequences of 1 minute length (from S 1000 ). For each transformation, we measured the repeatability R of the Harris detector as the pourcentage of stable points with a tolerated error of 1 pixel. We also estimated the parameter σ of the distortion model (see Equ. 2) by considering only the stable points:

σ 2 = 1 N s 1 D Ns i=1 D j=1 ∆S i j 2
where N s is the number of stable points and ∆S i j is the j-th component of the distortion vector of the i-th stable point. The results are summarized in table II. It shows that the value of σ increases with the severity of the transformations. On the other side the repeatability of the Harris detector decreases with the severity of the transformations. When this repeatability is to low, the retrieval will fail in all cases and it is useless to try to find signatures distorted by so severe transformations. The value of σ in bold in the table corresponds to the maximum value for which the Harris detector repeatability is higher than 15% and we propose to use this criterion as a selection of σ. In all the following experiments the value of σ is set to:

σ = 24.4
2) Influence of α: Figure 10 represents the average search time t s of one single local query with respect to the recall of the complete copy retrieval scheme (database S 1000 and query set Q 1000 + Q F ). Each point corresponds to a value of the query probability which varies from α = 15% to α = 98%. The recall values were determined at constant precision p r = 90% (i.e a ROC curve has been built for each point). The curve show the relevance of the approximate search paradigm: the recall remains almost constant when the probability of the query decreases from α = 98% to α = 70%, whereas the search is more than 3 times faster. For smaller values of the probability, the recall starts to degrade more significantly. It is however interesting to see that the recall is still 60% when only 15% of the signatures are expected to be retrieved. Let us emphasize that the distortion-based probabilistic search paradigm is always more efficient than reducing the number of queries. In other words, searching a fixed rate of the candidate local features is always slower than searching all the features with the appropriate approximation (for the same

ln(t s (α 2 )) -ln(t s (α 1 )) ln(α 2 ) -ln(α 1 ) < 1 , ∀(α 1 , α 2 ) (6)
where t s (.) is the average search time of one single feature and α 1 and α 2 two values of the query probability. The experimental curve t s (α) is plotted in logarithmic coordinates on Figure 11 and shows that Eq. 6 is always true, since the slope is always increasing and higher than one (A reference line with a slope equal to one has also been plotted on the figure). This proves the relevance of the approximate search paradigm for the DP S 2 technique.

In most of the following experiments the value of α is set to α = 75% in order to benefit from the approximate search paradigm without degrading the retrieval performances.

C. Comparison to exact range queries

To validate the approximate search paradigm induced by the distortion-based probabilistic similarity search, we have compared it to an exact range query strategy. For this purpose, we developed a hierarchical algorithm using the same indexing structure as the probabilistic queries, but with geometric filtering rules. Figure 12 represents the average search time of one single local feature with respect to the recall of the whole retrieval process (database S 1000 and query set

Q 1000 + Q F ).
The curve corresponding to the probabilistic queries was obtained with σ = 24 and increasing values of α. The curve corresponding to the range queries was obtained with increasing values of the query radius. Recall values are measured at constant precision p r = 90%. Table III gives the total search time for all the queries (extracted from the 4 hours 34 min of candidate video materials) at constant precision p r = 90% and constant recall r c = 80%. These results clearly show that the approximate search paradigm is widely more advantageous than exact range queries. At identical recall and precision, the search is 30 to 500 times faster than exact range queries. (rc = 80%) D. Influence of the database size 1) Computational performances of the DP S 2 technique: Figure 13 and table IV deal with the computational performances of the DP S 2 technique (databases S H and query sets Q H +Q F ). Probabilistic query parameters are set to α = 75% and σ = 24.4. The DP S 2 technique is compared to a classical sequential scan which is a reference method. Each method has been implemented both on disk and in main memory. For the main memory case, a specific strategy is used when the database size exceeds the memory size:

1) The filtering step of the DP S 2 is first processed for all the queries (Q H + Q F ). Notice that this step doesn't need to access the database.

2) The database is then split into pages that can fit in main memory.

3) The pages are loaded successively in main memory and the refinement step of all queries is processed for each page. The search times refer to the search of all the signatures extracted from the 4 hours 34 min contained in Q H + Q F . As shown on the figure, plotted in logarithmic coordinates, the search time of the DP S 2 is first sublinear in database size and then asymptotically linear for very large databases. The search time remains however very low even in the case of huge databases including more than 1.5 billion local features (30, 000 hours of video). Compared to a sequential scan, which is a reference method, the technique is asymptotically 2, 500 times faster. 2) Retrieval performances: Figure 14 and III-D.2 deal with the quality of the retrieval when the database size is strongly increasing (databases S H ). Figure 14 represents the precision/recall curves of the system for the default assessment methodology (randomly selected transformations) whereas Figure III-D Recall (%)

Length of query video clips (sec) 2500 hours 5000 hours 10000 hours 30000 hours Fig. 16. Recall vs maximal length of randomly selected databases (S 2500 , S 5000 , S 10000 , S 30000 ). The transformations that could be visually identified include resizing (±15%), frames and texts addition and contrast enhancement with overload of several regions. An example is given in figure 17. The program was then entirely searched by our content-based copy retrieval system in each database. Figure 16 displays the recall of these searches for various temporal resolution, i.e the step of the temporal splitting defining what are the researched objects. A temporal segment is considered to be retrieved if at least one correct detection occurs among all its key images (with a temporal precision of two frames). The curve shows that the retrieval is very efficient when the temporal granularity is higher than 5 seconds. Shorter video clips have a high probability to be missed which is not surprising since the average number of local signatures per second is only 17.

IV. CONCLUSION AND PERSPECTIVES

As discussed in this paper, CBCR is a challenging CBIR issue. The lack of discrimination and speed of the usual retrieval systems disables their use, whereas on the other hand, dedicated schemes are often not robust enough for all CBCR applications. Previous work did not attempt to take into account the special nature of the similarity existing between two copies. A copy is not only similar to the original document, but was obtained from the original by some specific operations. According to this property, we propose a distortion-based probabilistic approximate similarity search technique that is not based on features distribution in the database but rather on the distribution of the feature distortions. When employed in a global CBCR framework using local features, this technique enables a high speed-up compared to classical range queries and to the sequential scan method. It is asymptotically 2500 times faster than a sequential scan and, in practice, a TV channel can be monitored with a database containing 30, 000 hours of video. We think that investigations in the modeling of the feature distortions would allow to increase the performances of the DP S 2 technique. More precision during the search is indeed the best way to reduce the amount of explored data. The construction of learning databases containing real and relevant local matches will be a first step. New algorithms should also be designed to compute quickly the probability on multidimensional blocks for more complex probabilistic models. Extending our grid-structure strategy to multidimensional trees is also a project. This will allow dynamic insertions and will also better distribute the signatures in the chunks reducing the asymptotic increase of the search cost against database size. The hierarchical pruning of the chunks in such structures could be based both on the distribution in the database and a distortion model. Future work will also focus on local features extraction and databases statistical post-processing. Local features redundancy in the database is problematic both for the speed of the search and the probability to have false alarms. So, we will attempt to reduce it. The detection of spatio-temporal interest points instead of spatial points in key images could be very efficient in this way. A statistical purge of the database is also possible if it is constraint by the number of signatures per image and their geometrical distribution. Labelling interest points with motion categories during the extraction is another perspective. It will allow the post-construction of specific databases dedicated to various applications (copy retrieval, background detection, logo detection, etc.). Another important issue is the estimation of the transformations that occured between two documents. This could be widely profitable for the challenging tasks of distinguishing a copy and a original. We think that it could be used to enhance the quality of CBCR schemes and also to reconstruct the copies tree of a document which is a high level information (where, when and how a document is used). All the copies of the tree correspond indeed to several utilization contexts and the links between them are highly informative.

APPENDIX I RADIUS OF THE RANGE SEARCH

Let V B∩R be the intersection between the set of selected pblocks B(τ min ) and the range query of radius r σ . Without loss of generality, the probability α f = α B∩R to find a distorted feature in V B∩R is equal to:

α B∩R = α B + α R -α B∪R
where α B is the probability to find a distorted feature in B(τ min ), α R the probability to find a distorted feature in the range query and α B∪R the probability to find a distorted feature in V B∪R , i.e the union of B(τ min ) and the range query. As α B∪R ≤ 1 and α B ≥ α, then

α B∩R ≥ α + α R -1
Thus, in order to order to have α B∩R ≥ α -0.1%, α R should be equal to α R = 0.999. For the given normal distortion model, the L 2 norm of the distortion has the following probability density function:

p ∆S (r) = f N (0,σ) (r) (2πσ) D-1 2 π D 2 D Γ D 2 + 1 r D-1
where Γ is the gamma function and D is the dimension of the feature space. Thus, the probability α R of the range query is equal to:

α R = rσ 0 p ∆S (r) dr (7)
and the radius r σ for which α R = 0.999 can be estimated at the start of the system by a dichotomy on Eq. 7. In practice, r σ is typically equal to r σ ≈ 6.0σ.

APPENDIX II PROOF OF EQUATION 6

Let n c be the total number of candidate local features. The total search time T 1 of all local features is equal to:

T 1 (α 1 ) = n c t s (α 1 )
where t s (α 1 ) is the average search time of one single local feature when the query probability is set to α 1 . The total search time T 2 of a part only of the candidate features, say α 3 % of the candidate features, is equal to:

T 2 (α 2 , α 3 ) = α 3 n c t s (α 2 )
where t s (α 2 ) is the average search time of one single local feature when the query probability is set to α 2 . To be of equivalent quality, the expected final number of retrieved features must be the same in both cases: Rn c α 1 = Rn c α 2 α 3 where R is the repeatability of the interest points detector. This is equivalent to:

α 1 = α 2 α 3
The probabilistic search of all candidate features will be always faster than searching a part only of them if:

T 1 (α 1 ) < T 2 (α 2 , α 3 ) ∀(α 1 , α 2 , α 3 ) | α 1 = α 2 α 3 or t s (α 1 ) < α 3 t s (α 2 ) ∀(α 1 , α 2 , α 3 ) | α 1 = α 2 α 3 or t s (α 1 ) t s (α 2 ) < α 1 α 2 ∀(α 1 , α 2 )
which is equivalent to Eq. 6.

Fig. 1 .Fig. 2 .Fig. 4 .

 124 Fig. 1. Two copies (right) and their originals (left)

Fig. 5 .

 5 Fig. 5. Overview of the proposed framework local features are 20-dimensional vectors in [0, 255] D=20 and the mean rate is about 17 local features per second of video (1000 hours of video are represented by about 60 millions feature vectors). Let S be one of the local features, defined as:

Fig. 6 .

 6 Fig.[START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF]. Distribution of the distance between a feature and a distorted feature after transformation of a video sequence (small resizing, noise addition, gamma and contrast modification)

Fig. 7 .

 7 Fig. 7. Illustration of the space partition induced by the Hilbert space-filling curve at different depths p = 3, 4, 5 in 2 dimensions

Fig. 8 .

 8 Fig. 8. Average number of blocks intercepted by a probabilistic query and a range query of same probability α

5 )

 5 Recall r c = number of true positives total number of true Precision p r = number of true positives total number of positives False alarm probability p fa = number of false positives total number of false Except for section III-E, where a specific ground-truth data is used, the experiments are based on five kinds of synthetic transformations illustrated in Figure 9: 1) Resizing: resize factor w scale 2) Vertical shifting: parameter w shif t in % of the image height 3) Contrast modification: I (x, y) = I(x, y) × w contrast 4) Gamma modification: I (x, y) = 255 I(x,y) 255 wgamma Gaussian noise addition: standard deviation w noise The default assessment methodology is as follows: 100 video clips of 15 seconds are randomly selected in the database S H original w shif t = 30% w gamma = 0.40 w scale = 0.75 w contrast = 2.5 w noise = 30.0

Fig. 9 .

 9 Fig. 9. The five kinds of transformations studied in the experiments: resize, shift, contrast, gamma, noise addition and then corrupted with a combination of previous transformations. This query video set is referred as Q H . The number of transformations n T and the transformation parameters are randomly selected for each video clip. The range values of each parameter are given in tableI. These 100 transformed video clips represent the true probes and a true positive occurs when the original video clip in S H is well retrieved with a temporal precision of 2 images. The false probes come from a foreign TV channel capture that is supposed to never broadcast archives belonging to the french SN C database (the most confident matches were manually controlled to confirm this hypothesis). This query video set is referred as Q F and it is 10 times longer than Q H , in order to have a more realistic precision measure. The total length of all the queries (Q H + Q F ) is 16, 500 seconds (4 hours 34 min).

Fig. 10 .

 10 Fig. 10. Search time of the DP S 2 technique with respect to recognition recall, at constant precision (pr = 90%), for different query probabilities α

Fig. 11 .

 11 Fig. 11. Search time of the DP S 2 technique with respect to the query probability α

Fig. 13 .Fig. 14 .

 1314 Fig. 13. Total search time with respect to database size

Fig. 15 .

 15 Fig. 15. Recall at constant precision pr = 90% for several transformations and several database sizes

Fig. 17 .

 17 Fig. 17. A match of the ground truth -left: video clip of the controlled video tape -right: video clip in the source database 2) Television channel monitoring: A television monitoring system based on the proposed framework has been developed for copyright protection. A French TV channel has been continuously monitored for 4 months faced with a reference video set containing 30, 023 hours of SN C video materials (1, 813, 902, 051 local features). The average number of false alarms is about 30 per day and the average number of correct matches is about 320 per day (including trailers, channel events, start and end video clips of programs, etc.). The detection examples presented in the beginning of the paper (Figure 1 and 2), as well as the results presented on Figure 18, were obtained in that context. Figure 19 presents typical false alarms of the systems. The average time costs of each

Fig. 18 .

 18 Fig. 18. Four good detections of the TV monitoring system: the left image of each match is the broacasted video (captured in black and white) and the the right image of each match is the retrieved video

  [START_REF] Doermann | The detection of duplicates in document image databases[END_REF], 500 seconds (4 hours 34 min).

	min value max value	n T 0 5	w scale 0.7 1.5	w shif t 0% 35%	wcontrast 0.4 2.5	wgamma 0.4 2.5	w noise 0.0 35.0
				TABLE I
	RANGE VALUES FOR THE RANDOMLY SELECTED TRANSFORMATIONS

  .2 represents the recall at constant precision p r =

	DB size (hours) DB size Search time DP S 2 in memory Search time DP S 2 on disk Search time sequential scan in memory Search time sequential scan on disk	250 14,098,729 4 min 32 s 5 h 3 min 23 s 38 h 36 min 262 h (interpolated)	2,500 126,562,273 22 min 24 s 25 h 12 min 54 s 346 h (interpolated) 2352 h (interpolated)	25,000 1,286,585,349 2 h 48 min 42 s 3519 h (interpolated) 23911 h (interpolated)

TABLE IV TOTAL

 IV SEARCH TIME OF THE SIGNATURES EXTRACTED FROM THE 4 HOURS 34 MIN OF CANDIDATE VIDEO MATERIALS90% for varying parameters of the five studied transformations. Probabilistic query parameters were set to α = 75% and σ = 24.4. Despite of the two orders of magnitude between the smallest and the largest database, the recall and the precision of the system do not significantly degrade. This robustness to database size is closely linked to the use of local features and to the discrimination of voting strategies. Even if the number of non relevant features provided by the search for each local feature is linear in database size, the impact on the final similarity measure is very limited because the number of consistent matches remains very low.

TABLE V TIME

 V COST OF EACH STEP