EP2245555A1

EP2245555A1 - Method of identifying a multimedia document in a reference base, corresponding computer program and identification device

Info

Publication number: EP2245555A1
Application number: EP09706882A
Authority: EP
Inventors: Nicolas Gengembre; Patrick Lechat; Sid Ahmed Berrani
Original assignee: France Telecom SA
Current assignee: Orange SA
Priority date: 2008-01-30
Filing date: 2009-01-28
Publication date: 2010-11-03
Also published as: US20100332541A1; WO2009095616A1

Abstract

The invention relates to a method of identifying a multimedia document, aimed at verifying whether the multimedia document to be identified (21) is similar or not to at least one multimedia document referenced in a base (22) of reference multimedia documents, comprising the following steps: assignment (23) of a number of votes to at least one reference multimedia document, selection (24) of multimedia documents similar to said multimedia document to be identified. According to the invention, the selection step comprises the following substeps, determination (241) of a probabilistic distribution of the number of votes assigned to a reference multimedia document, as a function of the total number of documents referenced in said base and of the total number of votes, under a random voting assumption; obtainment (242) of a threshold of selection of said similar multimedia documents from among the reference multimedia documents, on the basis of said probabilistic distribution.

Description

A method of identifying a multimedia document in a reference database, computer program, and corresponding identification device.

FIELD OF THE INVENTION The field of the invention is that of the transmission or exchange of multimedia documents, for example an image, a video, an audio content, a textual content, etc.

More specifically, the invention relates to the identification of such multimedia documents, in particular for the detection of copies of a referenced document (for example illegal copies of a protected document).

2. Prior Art

2.1 Detection of illegal copies

The advent of broadband offered by ADSL has led to the emergence of new services allowing for easier consumption of multimedia content, such as video-on-demand services.

The historical suppliers, such as France Television, TFl, Gaumont, etc. (registered trademarks) as well as other players from the world of telecoms, such as Orange, Neuf, Free, etc. (trademarks), search engines like Google video, Yahoo video, etc. (registered trademarks) or specialized companies such as vodeo.fr, glowria, blinkx, TVEyes, skouk, etc. (trademarks), thus offer online part of their video catalog. The multimedia documents offered by these services are protected, and for example subject to the payment of a fee to be able to download them.

In addition, the recent development of multimedia document exchange sites such as YouTube, DailyMotion, MySpace, etc. (trademarks) highlights the existence of a second source of multimedia documents. These documents come from the users themselves. Unfortunately, although some of the documents observed on these exchange sites come from documents actually created by the users, another part consists of documents illegally offered for download. It is therefore desirable to be able to detect the illicit copies of a protected multimedia document.

More specifically, the detection of video copies makes it possible: to identify the contents referenced in a catalog, that is to say referenced in a reference database, in order to detect the illicit copies of the reference contents; Highly copied content (de-doubling) to detect content that generates audience, or to limit storage sizes; - locate an entire program from a short excerpt.

Such detection must be able to take into account the usual alterations that a multimedia document can undergo in this context: high compression, resampling, reframing, but also text embedding, logos, filmed projections (in English "camcording"), etc. Indeed, a copied multimedia document generally undergoes intentional transformations, in order to make it difficult to detect, as well as unintentional transformations, due to the recording of the document, its transcoding, or even editorial constraints during its republication. .

Conventionally, the detection of copies of multimedia documents (images, sounds, videos, etc.) consists of searching for the presence or absence of a "suspect" request document in a protected database. Such a technique relies on two essential aspects: the description of the visual content of the multimedia document, i.e. the descriptors used; - the descriptor indexing technique, i.e. the method used to structure the descriptor database of protected documents, which makes it possible to efficiently execute searches. 2.2 Document descriptors

Typically, the descriptor of a document is a digital vector that represents, by summarizing, the content of the document or part of the document. In the field of video content analysis, a description based on keyframes is commonly used. This technique consists of selecting from a video-type document a subset of images, called keyframes, and describing these keyframes. For example, these keyframes may come from an algorithm adaptively selecting the representative images of the video, or a regular time sub-sampling selecting for example one frame per second. These keyframes are represented by one or more descriptors calculated from the visual content of the image.

There are two approaches to the descriptors: - local approaches: from each key image, a set of points of interest is selected in the image. These points of interest correspond to visually remarkable points of the image that can be found even after alteration. A descriptor is then calculated in the vicinity of each point of interest; - global approaches: each image of the video, or each key image is described as a whole by calculating a single descriptor. In particular, the descriptors must be robust to the alterations of the documents.

Thus, a large part of the techniques for detecting copies of multimedia documents uses a local description of the document, considering that the local descriptors are more robust than the global descriptors. The information describing the multimedia document is thus divided into different regions of the document. Consequently, the alteration of some of these regions (for example when embedding a logo in an image, or during cropping or cropping of the image in English "cropping") does not affect other regions that identify the document.

2.3 Search by similarity

As already indicated, the detection of copies of multimedia documents consists of searching for the presence or absence of a request document to be identified in a protected database. This research is based on two distinct phases: an "offline" phase for the construction of the multimedia reference database; a so-called "online" phase for searching for the presence or absence of the document to be identified in the reference database.

More specifically, the search phase associates a measure of similarity (often a distance) with a document to be identified. This measure of similarity makes it possible to quantify the similarity between two documents by measuring the proximity between their respective descriptors. In a video copy detection application, for example, not only identical documents, but also documents of moderate resemblance are searched for, in order to take into account any alterations suffered by the video.

On the other hand, it is not enough for two documents to have some descriptors in common so that they are copies of each other (for example, two text documents can have words in common without dealing with the same subject ).

Therefore, it is desirable to define effectively the degree of similarity (also called the selection threshold) from which the documents are considered to have a significant resemblance.

In fact, a threshold that is too low leads to the presence of many false alarms, considering multimedia documents that are not similar as similar, while a threshold that is too high leads to non-detections, by not detecting certain similar documents (similar documents not returned by the system).

FIG. 1 illustrates more precisely the various steps implemented for the online search phase of the presence or absence of a document to be identified in the reference database.

For example, consider a document to identify QI 1, corresponding to an image. During a first description step 12, a set of local descriptors m is extracted from the document to be identified. It is considered that the more complex the image, the more the number of local descriptors increases. Conversely, if the image is simple (image representing the sky for example), the number of descriptors is low.

During a next search step 13, a request to the multimedia reference database 14 returns, for each of the m descriptors, a set of candidate documents (zero, one or more) from the reference base and having a similar descriptor. In other words, we associate with each descriptor j (for j ranging from 1 to m), Dj candidate documents from the base 14.

In particular, it is noted that among the returned candidate documents, some appear several times, that is to say that they are returned by more than one of the m queries, during step 13 similarity search in the reference database. .

In a next step of selecting similar documents 15, it is decided, based on the number of their appearances, which documents can be considered as similar to the document to be identified 11. The step 15 of selecting similar documents can therefore be assimilated to a vote counting stage: it is considered that each descriptor j of the document to be identified 11 "votes" for candidate documents (zero, one or more), and that the candidate documents receiving the most votes will be the closest of the document to be identified. A set of documents similar to the document to be identified is thus obtained. Different techniques are presented in the literature for the counting of votes in a search system of similar documents in a reference database.

Thus, a first technique is based on an absolute thresholding system. In other words, only candidate documents that have received a number of votes above a predetermined threshold are retained. It should be noted that such a technique is not very efficient because it does not adapt to the total number of votes cast or the size of the reference base. It therefore generates an increased number of false alarms and no detections.

Another technique presented by S. -A. Berrani, L. Amsaleg, and P. Gros. ("Robust Content-Based Image Searches for Copyright Protection", Proceedings of the ACM International Workshop on Multimedia Databases, pages 70-77,

New Orleans, Louisiana, USA, November 2003) is based on an analysis of the orderly list of candidate documents in ascending order of the number of votes.

A jump search method (the so-called Page-Hinkley method) separates the list of non-significant votes from those that are.

Unfortunately, this technique requires a phase of scheduling candidate documents by the number of votes received. This technique also requires that candidate documents whose similarity is significant are clearly distinguishable from background noise (corresponding to non-significant votes). Such a technique is therefore restrictive, and expensive in terms of resource and time.

3. Presentation of the invention

The invention proposes a new solution that does not have these disadvantages of the prior art, in the form of a method for identifying a multimedia document, aimed at checking whether the multimedia document to be identified is similar to least one reference multimedia document referenced in a reference multimedia database, comprising the following steps: assigning a number of votes to at least one reference multimedia document, each of said votes being indicative of a proximity between a descriptor of said reference document multimedia reference document and a descriptor of said multimedia document to be identified, selecting from among said at least one multimedia reference document, multimedia documents similar to said multimedia document to be identified.

According to the invention, the selection step comprises the following sub-steps: - determining a probabilistic distribution of the number of votes allocated to a reference multimedia document, based on the total number of documents referenced in said database and the total number of votes, under a random voting hypothesis, obtaining a selection threshold for said similar multimedia documents, among the multimedia reference documents, from said probability distribution.

Thus, the invention proposes a novel and inventive solution for automatically determining a selection threshold of reference multimedia documents similar to the multimedia document to be identified. To do this, we consider a number of votes assigned to at least one reference multimedia document, and for example to all documents referenced in the database. Thus, this number of votes will be zero for a document that has not received a vote.

Multimedia documents (reference and to be identified) can be still images, videos, audio contents, textual contents, etc. These multimedia documents are each described by at least one descriptor.

More specifically, if the multimedia documents (to be identified and referenced) are described by at least two local descriptors, characterizing an aspect and / or a region of said multimedia documents, a vote is assigned to a reference multimedia document when one of the descriptors the multimedia document to be identified is similar to one of the descriptors of the reference multimedia document.

If the multimedia documents (to be identified and referenced) are described by a global vector descriptor, comprising at least two components, a vote is assigned to a reference multimedia document when one of the components (or subset of components) of the descriptor the multimedia document to be identified is similar to one of the components (or subset of components) of the descriptor of the reference multimedia document.

A probabilistic distribution of the number of votes assigned to a reference multimedia document is then determined, based on the total number of votes cast. referenced documents in the database and the total number of votes. In other words, this probability distribution is valid for all the reference documents. It allows to represent the number of votes assigned to a document i, under a hypothesis of random voting. This probabilistic distribution is also called probabilistic representation of the distribution of the number of votes, or probabilistic modeling.

We then obtain a selection threshold of similar multimedia documents, from the reference multimedia documents of the database, from this probabilistic distribution. In particular, the selection threshold is defined taking into account the number of false alarms possible, estimated from said probability distribution, so that the number of false alarms for the selection threshold is less than a predetermined decision value ε.

This selection threshold therefore takes into account the probabilistic distribution previously determined.

More precisely, a "false alarm" for a reference multimedia document amounts to considering this document as similar to the document to be identified, whereas it is not. The number of false alarms can be expressed by the product of the total number of multimedia documents referenced in the database and the probability that a reference multimedia document has a number of votes greater than or equal to the selection threshold S. Again, this probability is calculated under a hypothesis of random voting.

For example, the decision value is chosen equal to 1 (£ = 1). The choice of this decision value makes it possible in particular to omit a parameter.

Indeed, by setting this value to 1, we know that statistically, less than one reference multimedia document on all reference multimedia documents will receive a number of votes greater than threshold S if the votes occur randomly. If a particular reference multimedia document receives a number of votes exceeding this threshold S, it constitutes a false alarm observed, while the probabilistic distribution following the random vote predicts less.

Thus, we can assume that such a number of votes may not be due to chance but rather to a certain similarity with the multimedia document to be identified.

According to a particular aspect of the invention, where the random votes are uniformly distributed, the probabilistic distribution implements a binomial law of parameters V and XIn, denoted B iv ^ V, -, where: vn ⁾

- n is the total number of multimedia documents referenced in the database; - V is the total number of votes;

- V (is the number of votes for a reference multimedia document i referenced in the database.

Such a law corresponds to the following experiment: one independently renews a Bernoulli test of parameter XIn (random experiment with two possible outcomes, generally denoted respectively "success" and "failure", with a chance of success of 1 / ή). We then count the number of successes V; obtained at the end of the V tests.

The set of values taken by V; then follows a binomial law

B (vf, V, -) \ n / In particular, the binomial distribution can be approximated by a Poisson distribution of parameter L = V / n, according to the following equation:

1 L ^k

B (k; V, -) ≈ - exp (-L). n k \

This approximation makes it possible in particular to simplify the numerical implementation of the calculations, and to minimize the calculation times. In particular, the step of obtaining a selection threshold implements an iterative algorithm from an initialization value of the selection threshold equal to zero and as long as the number of false alarms for the selection threshold is greater than the decision value ε. This iterative algorithm can in particular be implemented when the binomial law is approximated by a Poisson law.

According to one variant, the selection threshold S is determined prior to the selection step for different values of the total number of multimedia documents referenced in said base (n) and of the total number of votes (V), and stored in a table. Obtaining the selection threshold then implements a reading of the table.

Another aspect of the invention relates to a computer program product downloadable from a communication network and / or recorded on a computer-readable and / or executable medium by a processor comprising program code instructions for the implementation of the identification method described above.

In another embodiment, the invention relates to a device for identifying a multimedia document, intended to verify whether the multimedia document to be identified is similar or different from at least one reference multimedia document referenced in a multimedia document database. reference, said multimedia documents to be identified and referenced being described by at least one descriptor, comprising: means for allocating a number of votes to at least one reference multimedia document, each of said votes being significant of a proximity between a descriptor of said reference multimedia document and a descriptor of said multimedia document to be identified, means for selecting, from said at least one multimedia reference document, multimedia documents similar to said multimedia document to be identified.

According to this embodiment, the selection means comprise: means for determining a probabilistic distribution of the number of votes allocated to a reference multimedia document, as a function of the total number of documents referenced in said database and the total number of votes , under a hypothesis of random voting, means for obtaining a threshold for selecting said similar multimedia documents from the multimedia reference documents, from said probabilistic distribution.

Such an identification device is particularly suitable for implementing the identification method described above. It is for example included in an analysis server, allowing the exchange or downloading of multimedia documents, and in particular the detection of copies of multimedia documents.

4. List of figures

Other features and advantages of the invention will appear more clearly on reading the following description of a particular embodiment, given as a simple illustrative and nonlimiting example, and the appended drawings, among which: FIG. 1 presents the various steps implemented for the search for similar documents according to the prior art; FIG. 2 illustrates the main steps of the identification method according to the invention; Figure 3 represents an example of a probability distribution of the number of votes under the hypothesis of random voting; Figure 4 shows the structure of an identification device according to a particular embodiment of the invention.

5. Description of an embodiment of the invention 5.1 General principle

The general principle of the invention relies on the use of a probabilistic approach to identify a multimedia document, that is to say to check if one or more multimedia documents referenced in a multimedia reference database are similar ( or not) with the multimedia document to be identified. Such a multimedia document can be an image (possibly extracted from a video), a video, an audio content, a textual content, etc.

More precisely, the invention makes it possible to decide which multimedia reference documents can be considered as similar to the document to be identify, taking into account an automatically determined threshold of selection.

Automatically determined selection threshold means a threshold which is not pre-established (as in the techniques implementing absolute thresholding), but which is automatically calculated by the algorithm of the invention. FIG. 2 illustrates more precisely the general principle of the identification of a multimedia document according to the invention, aimed at checking whether a multimedia document to be identified is similar or not to at least one multimedia document referenced in a database 22 reference multimedia each described by at least one descriptor. To do this, during a first step 23, a number of votes is assigned to at least one of the multimedia documents referenced in the base 22. Each of these votes is indicative of a proximity between a descriptor of the reference multimedia document. and a descriptor of the multimedia document to be identified. For example, we assign a number of votes to each of the documents referenced in base 22. Reference documents not receiving a vote are given a number of votes equal to zero.

For example, in the case of a multimedia document described from local descriptors, zero, one or more multimedia reference documents are associated with each local descriptor j, by searching in the base 22 the multimedia reference documents comprising this descriptor or a descriptor close to it (in terms of distance for example). In other words, it is considered that each descriptor j of the document to be identified "vote" for reference multimedia documents (zero, one or more).

In the case of a multimedia document described from a global descriptor, zero, one or more reference multimedia documents are associated with each component of the global descriptor. In other words, it is considered that each component of the global descriptor of the document to be identified "vote" for reference multimedia documents (zero, one or more).

For example, if the base 22 includes four reference multimedia documents denoted D1 to D4, and the multimedia document to be identified is described by three local descriptors, the first local descriptor may vote for the reference multimedia documents D1 and D3, the second local descriptor may vote for the reference multimedia document D3, and the third local descriptor may vote for no reference multimedia document. Then the number of votes allocated to the document Dl will be equal to 1, the number of votes allocated to the documents D2 and D4 will be equal to 0, and the number of votes allocated to the document D3 will be equal to 2. The total number of votes will then be equal to 3.

Next, (24), in the database 22, the multimedia documents similar to the multimedia document to be identified 21 are selected. To do this, a probabilistic distribution of the number of votes assigned to a reference multimedia document is first determined (241). , based on the total number of documents in the database and the total number of votes, under a hypothesis of random voting. Such modeling applies to all reference multimedia documents. Next, (242) a selection threshold of similar multimedia documents is obtained from among the reference multimedia documents of the database, from the probabilistic distribution, similar multimedia documents having a number of votes greater than the selection threshold. To do this, we can take into account the number of false alarms possible, estimated from the probability distribution.

In other words, only multimedia reference documents with a number of votes greater than the selection threshold are considered as similar documents to the multimedia document to be identified.

In particular, the method according to the invention can be implemented in various ways, in particular in cabled form or in software form. 5.2 Case of local descriptors

An exemplary implementation of the invention is described below, in which the probabilistic distribution of the number of votes allocated to the multimedia reference documents is a binomial law. It is also considered that the multimedia document to be identified is described by a plurality of descriptors local.

More precisely, n is the number of multimedia documents referenced in the reference multimedia database, and i is one of these reference multimedia documents ie We denote Vi the number of votes received by the document i (Vi may be equal to O), and V the total number of votes, received by all the multimedia reference documents. These votes are derived from the search by similarity of a set of descriptors of a document to identify Q in the reference base, as described in relation with the prior art. It is sought according to the invention to determine the selection threshold S corresponding to the minimum number of votes for which it can be assumed that reference multimedia document i is similar to the multimedia document to be identified Q.

In order to determine this selection threshold S, we therefore assume a contrario hypothesis, considering that each of the V votes was made by randomly selecting, in a uniform manner, a reference multimedia document among the n referenced multimedia documents. in the base (hypothesis of random voting). For each vote, the probability of voting for the reference multimedia document i is then 1 / n. Indeed, contrary reasoning in this context makes it possible to question whether chance is enough to explain the common points observed between the document to be identified and the reference documents. If this is not the case, then there is indeed a similarity between the documents.

Voting for the reference multimedia document i is a random phenomenon with two possible outcomes (generally referred to as "success" and "failure") whose probability distribution follows the law called Bernoulli distribution of parameter 1 / n. In other words, if you randomly and uniformly select a reference multimedia document from the database, there is a chance on n to choose the document i. Thus, if we choose the document i, the result is a success, and if we choose another document from the database, the result is a failure.

When one reproduces this experiment V times, with V corresponding to the total number of votes, the probability that one chooses the document i several times (Vi times) follows as for him a binomial law with two parameters: V and 1 / n. Thus, the probability that the reference multimedia document i receives exactly Vi votes follows the binomial law of parameters V and 1 / n. We notice

B V-; V, - this probability. v n)

A probabilistic representation of the distribution of the number of votes allocated to a reference multimedia document (i) is thus determined, as a function of the total number of documents present in said database (n), and of the total number of votes (V).

We then try to determine a selection threshold S of similar multimedia documents (with S an integer).

We can write the probability that the number of votes assigned to the document i, denoted Vi, is greater than or equal to the selection threshold S in the following form: if ₁ p (V _i ≥ S) = l - Σ B (k; V , -) k = 0 ⁿ

Figure 3 shows an example of a probability distribution of the number of votes under the hypothesis of random voting. More specifically, the hatched portion represents the probability that the number of votes for a reference multimedia document i is greater than or equal to the threshold S.

According to this exemplary implementation of the invention, the decision on the similarity or otherwise of the reference multimedia document i with the multimedia document to be identified Q is performed by calculating, for different values of increasing S, the selection threshold to from which the estimated number of false alarms observed is less than a decision value, for example equal to 1. This means that a "random" vote is not enough to explain such a number of votes, but that a certain similarity is responsible for it. This number of false alarms can be estimated from the probabilistic distribution illustrated in FIG. 3. In this example, the number of false alarms, denoted NFA (S), corresponds to number of reference multimedia documents that have received at least S votes when they are randomly conducted.

The number of false alarms is expressed by the product of the probability that a multimedia reference document has a number of votes greater than or equal to the selection threshold S, by the total number of multimedia documents in the database:

NFA (S) = n.p (Vi> S)

It can also be noted that the binomial law B V ^; V, - which intervenes v n / is expressed by means of combinations, themselves expressed by factorials (f actorial V notably).

For the sake of ease of numerical implementation of the calculations, it is possible to approach, very reliably, the binomial law by a Poisson law whose parameter L is V / n.

It can be noted that such an approximation is valid when 1 / n is small and V large, which is the case in general for this context (in practice, this approximation is used when V> 30 and L <5).

Thus, we can approach the binomial law by the following expression:

1 L ^k

B (k; V, -) ≈ - exp (-L) n k \

Although the Poisson's law also involves a factorial, this factorial only concerns, in the proposed implementation, small values, and is easily calculable.

It is also possible to deduce a recursive formulation of the binomial law thus approximated: for k = 0: β (0; V, -) ≈ exp (-L); n - for £> 6>: B (k; V, -) = - B (k - l; V, -). n k n

This formulation can then be used to determine the value of the selection threshold S.

The following notations are introduced: L = V / n, where L is the parameter of the Poisson's law; s corresponds to different threshold values tested; the variables p and b, associated with the variable s, are defined as follows: ob is the probability that a multimedia reference document has received exactly the same votes under the hypothesis of random voting previously described; op is the probability that a reference multimedia document has received at least s votes under the assumption of random votes previously described.

The variables are initialized first: s = 0, corresponding to the first selection threshold value tested; b = exp (-L), corresponding to the probability that a reference multimedia document received exactly zero votes under the assumption of random votes previously described; P = I, corresponding to the probability that a reference multimedia document has received at least zero votes under the assumption of random votes previously described. The following steps are then repeated as long as the probability of false alarms NFA is greater than a predetermined decision value ε, equal to 1 for example.

Thus, as long as np> ε (ie NFA (s)> ε): we increment the variable s by 1 (s: = s + l) and we update the variables that depend on it: we affect the probability p - b to the variable p (p: = p - b), which thus becomes the probability that a reference multimedia document i has received at least s votes under the assumption of random votes previously described; the probability bx L ls is assigned to the variable b (b: = b * L / s), which thus becomes the probability that a reference multimedia document i has received exactly s votes under the assumption of random votes previously described;

Finally, when the probability of false alarms NFA (s) is less than or equal to the predetermined decision value ε, with ε = 1 for example, the final value of s is assigned to the selection threshold S. Multimedia reference documents that have received a number of votes greater than or equal to S are assumed to be similar and are returned by the procedure.

According to another variant, it is considered that the number of false alarms can be deduced directly from a selection threshold value, that is to say that the value NFA (s) can be calculated without using the value NFA (sl ). Since the NFA (s) function is monotonic and decreasing as a function of s, the determination of the selection threshold can then be implemented by dichotomy: the probability of false alarms NFA (s) is calculated for different values of s in an interval. possible values (usually with a lower bound of 0 and an upper bound related to the number of descriptors used). The values of s are chosen to divide the interval into two subintervals. The estimation of the false alarm probabilities NFA (s) at the boundaries of these subintervals and the property of monotony make it possible to locate the sub-interval in which the function NFA (s) passes through the value ε. We keep only this subinterval and repeat the same operations, until we obtain an interval whose boundaries are two consecutive integers. The value of the selection threshold S sought is then determined by the upper bound of this interval.

According to another variant of implementation, the selection threshold S can be calculated from one of the methods mentioned previously in advance for different possible values of V and n, and stored in a table (if the we use a database with a fixed number of reference documents, we can also perform this tabulation only for different values of V). Thus, during an analysis phase, it is no longer necessary to calculate the threshold value S, but it is sufficient to read it in said table, thus saving more time of calculation.

5.3 Case of global descriptors

According to the invention, the multimedia document to be identified may be described by a global descriptor, instead of a plurality of local descriptors. Such a global descriptor generally takes the form of a vector with m dimensions.

In this case, one applies the same technique as described previously, by assimilating each component (or subset of components) of the global descriptor to a local descriptor. In other words, it is considered that each component (or subset of components) of the global descriptor of the document to identify "vote" for a set of reference multimedia documents (zero, one or more).

5.4 Advantages of the invention

The technique according to the invention has numerous advantages, according to at least one of its embodiments, and in particular: it does not require any parameter to be adjusted, if the predetermined decision value ε is fixed at ε = 1; the selection threshold is evaluated automatically, and does not require expensive manipulation of the lists of values taken by the numbers of votes. In particular, the decision of similarity or lack of similarity with respect to the selection threshold does not require any scheduling of multimedia documents based on their number of votes. Similarly, the number of votes assigned to a "good" reference multimedia document

(That is, a reference multimedia document similar to a multimedia document to be identified) need not be clearly distinguishable from those assigned to non-significant reference multimedia documents to be detected; it relies on a rigorous probabilistic formalism; it allows to control the number of false alarms. Indirectly, we can deduce the probability that a reference multimedia document selected either a false alarm, the number of votes he has received. This feature may be useful in particular in the case of a video copy detection system for which a sequential filtering allows to temporally aggregate the results obtained for each image; it involves very few calculations and its execution is therefore fast: according to a particular embodiment, it makes it possible to shorten the decision-making time before having analyzed all the local descriptors (or all the components of a descriptor). global) of the multimedia document to be identified. We can decide, when V votes have been collected (with V <V, where V is the total number of votes awarded taking into account all the descriptors), to evaluate or read in a table the selection threshold S associated with values V and n, and use it to select any reference multimedia documents similar to the multimedia document to be identified. One can then choose to stop the analysis as soon as at least one reference multimedia document has been identified as similar.

5.5 Application of the invention

The invention can in particular be implemented in a system for detecting copies of a referenced multimedia document (for example, illegal copies of a protected document).

For example, it can effectively detect the presence of copies of protected video content within a suspicious video stream. In particular, the use of local descriptors according to one embodiment of the invention allows this detection to be robust to alterations, voluntary or otherwise, of the original document.

The invention can thus be integrated into an automatic system for protecting copyright. It allows for example a content exchange platform, such as Youtube, MyZoneVideo, Dailymotion, etc.

(registered trademarks) to intervene very early in the process of filing multimedia documents (text, image, audio or video) by filtering documents unlawfully deposited, and thus to comply with the rules of copyright protection.

Moreover, and always in the context of content exchange platforms, such a system can be used to detect multiple copies of the same document referenced in a database of a server. Indeed, the same document is generally loaded by several users with different names and text descriptions. Such a copy detection system can thus be applied to a multimedia document search engine to suppress duplicate entries in the database and provide undelivered query results. In this way, the user is presented with a unique instance of each multimedia document (possibly with a link to the other copies).

Such a tool may also be used for analytics purposes for content that is allowed to be broadcast but whose audience is desired. Another possible application is the location and playback of a program (TV show, video, ...) from an excerpt of the document.

More generally, the technique for obtaining a threshold of selection and vote counting according to the invention can be applied to any type of multimedia document (sound, text, still images, video), as well as to any system putting a game a voting strategy with a large number (not infinite) of potential candidates.

5.6 Structure of the identification device

Finally, in connection with FIG. 4, the simplified structure of an identification device implementing an identification technique according to the particular embodiment described above is presented. Such a device comprises a memory 41 consisting of a buffer memory, a processing unit 42, equipped for example with a microprocessor μP, and driven by the computer program 43, implementing the identification method according to the present invention. invention.

At initialization, the code instructions of the computer program 43 are for example loaded into a RAM memory before being executed by the user. processor of the processing unit 42. The processing unit 42 receives as input a multimedia document to be identified 21.

The microprocessor of the processing unit 42 implements the steps of the identification method described above, according to the instructions of the computer program 43, to check whether the multimedia document to be identified is similar or different from at least one multimedia document. referenced in a reference multimedia database. For this purpose, the identification device comprises, in addition to the buffer memory 41, means for assigning a number of votes to at least one reference multimedia document and selection means, among the at least one reference multimedia document. , multimedia documents similar to the multimedia document to be identified. More specifically, the selection means comprise: means for determining a probabilistic distribution of the number of votes allocated to a reference multimedia document, according to the total number of documents referenced in the database and the total number of votes, under a random voting hypothesis, means for obtaining a selection threshold of similar multimedia documents among the multimedia reference documents, from said distribution, similar multimedia documents having a number of votes greater than the selection threshold.

These various means are controlled by the microprocessor of the processing unit 42.

The identification device delivers zero output, one or more reference multimedia documents of the database, having a number of votes greater than the selection threshold.

Such a device can notably be integrated in a system for detecting copies of multimedia documents.

Claims

A method of identifying a multimedia document, for checking whether the multimedia document to be identified (21) is similar or different from at least one reference multimedia document referenced in a base (22) of reference multimedia documents, comprising the following steps: assigning (23) a number of votes to at least one reference multimedia document, each of said votes being indicative of a proximity between a descriptor of said reference multimedia document and a descriptor of said multimedia document to be identified, selecting (24), from among said at least one multimedia reference document, multimedia documents similar to the said multimedia document to be identified, characterized in that the said selection step comprises the following sub-steps: - determining (241) a probabilistic distribution the number of votes assigned to a reference multimedia document, based on the total number of referenced documents embedded in said database and the total number of votes, under a hypothesis of random voting, obtaining (242) a selection threshold of said similar multimedia documents among the multimedia reference documents, from said probability distribution.

2. Identification method according to claim 1, characterized in that said selection threshold is defined by taking into account the number of false alarms possible, estimated from said probability distribution, so that the number of false alarms for said threshold selection is less than a predetermined decision value.

3. Identification method according to claim 2, characterized in that said decision value is equal to 1.

4. Identification method according to any one of claims 1 to 3, characterized in that said probabilistic distribution implements a law binomial BIV _t ; V, -, where: vn /

n is the total number of multimedia documents referenced in said database;

- V is the total number of votes; - V ₁ is the number of votes for a reference multimedia document i referenced in said database.

5. Identification method according to claim 4, characterized in that said binomial law is approximated by a Poisson law of parameter L = V / n, according to the following equation:

1 L ^k B (k; V, -) ≈ - exp (-L). n kl

6. Identification method according to claim 2 and any one of claims 3 to 5, characterized in that said step of obtaining (242) a selection threshold implements an iterative algorithm from a initialization value of the selection threshold equal to zero and as long as the number of false alarms for said selection threshold is greater than said decision value.

7. Identification method according to any one of claims 1 to 6, characterized in that said selection threshold S is determined before said selection step (24) for different values of the total number of multimedia documents referenced in said base and the total number of votes, and stored in a table, and in that said step of obtaining (242) a selection threshold implements a reading of said table.

8. Identification method according to any one of claims 1 to 7, characterized in that said multimedia documents belong to the group comprising: an image; a video ; audio content; textual content.

9. Identification method according to any one of claims 1 to 8, characterized in that said multimedia documents are described by at least two local descriptors, characterizing an aspect and / or a region of said multimedia documents, a vote being assigned to a reference multimedia document when one of the descriptors of the multimedia document to be identified is similar to one of the descriptors of said reference multimedia document.

10. Identification method according to any one of claims 1 to 8, characterized in that said multimedia documents are described by a global vector descriptor comprising at least two components, a vote being assigned to a multimedia reference document when a components of the descriptor of the multimedia document to be identified is similar to one of the components of the descriptor of said reference multimedia document.

11. Computer program product downloadable from a communication network and / or recorded on a computer readable medium and / or executable by a processor, characterized in that it comprises program code instructions for the implementation of the identification method according to at least one of claims 1 to 10.

12. Device for identifying a multimedia document, intended to verify whether the multimedia document to be identified (21) is similar or different from at least one reference multimedia document referenced in a base (22) of multimedia reference documents, comprising : means for assigning (23) a number of votes to at least one reference multimedia document, each of said votes being significant of a proximity between a descriptor of said reference multimedia document and a descriptor of said multimedia document to be identified, selection means (24), among said at least one multimedia reference document, of multimedia documents similar to said multimedia document to be identified, characterized in that said selection means comprise: means for determining (241) a probabilistic distribution of the number of votes allocated to a reference multimedia document, based on the total number of documents referenced in said database and the total number of votes, under a hypothesis of random voting, means for obtaining (242) a threshold for selecting said similar multimedia documents from the multimedia reference documents, based on said probabilistic distribution.