Classifications

• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
  • G06F16/40—Information retrieval; Database structures therefor; File system structures therefor of multimedia data, e.g. slideshows comprising image and additional audio data
  • G06F16/41—Indexing; Data structures therefor; Storage structures
• • G—PHYSICS
  • G06—COMPUTING OR CALCULATING; COUNTING
  • G06F—ELECTRIC DIGITAL DATA PROCESSING
  • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
  • G06F16/70—Information retrieval; Database structures therefor; File system structures therefor of video data
  • G06F16/78—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
  • G06F16/783—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually using metadata automatically derived from the content

Definitions

• a method of identifying a multimedia document in a reference database, computer program, and corresponding identification device is a method of identifying a multimedia document in a reference database, computer program, and corresponding identification device.
• 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.
• 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).
• ADSL Advanced Driver Assistance Systems
• 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.
• 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. .
• the descriptor of a document is a digital vector that represents, by summarizing, the content of the document or part of the document.
• 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.
• 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.
• descriptors 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.
• 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.
• 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.
• a measure of similarity 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.
• 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.
• a document to identify QI 1, corresponding to an image For example, consider a document to identify QI 1, corresponding to an image.
• 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.
• 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.
• a set of candidate documents zero, one or more from the reference base and having a similar descriptor.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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 can be still images, videos, audio contents, textual contents, etc. These multimedia documents are each described by at least one descriptor.
• 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.
• 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.
• 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.
• 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.
• the choice of this decision value makes it possible in particular to omit a parameter.
• 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
• 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.
• 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.
• the invention in another embodiment, 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.
• 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.
• 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.
• 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.
• a multimedia document can be an image (possibly extracted from a video), a video, an audio content, a textual content, etc.
• 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.
• 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.
• 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.
• each descriptor j of the document is identified "vote" for reference multimedia documents (zero, one or more).
• each component of the global descriptor of the document 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).
• 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
• 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.
• the multimedia documents similar to the multimedia document to be identified 21 are selected.
• 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.
• 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.
• 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
• n is the number of multimedia documents referenced in the reference multimedia database, and i is one of these reference multimedia documents ie
• 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.
• V may be equal to O
• 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.
• 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.
• success two possible outcomes
• failure Bernoulli distribution of parameter 1 / 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).
• 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.
• 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.
• a decision value for example equal to 1.
• NFA the number of false alarms
• 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)
• This formulation can then be used to determine the value of the selection threshold S.
• 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 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.
• 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 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).
• 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.
• the multimedia document to be identified may be described by a global descriptor, instead of a plurality of local descriptors.
• a global descriptor generally takes the form of a vector with m dimensions.
• each component (or subset of components) of the global descriptor to a local descriptor.
• 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).
• 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.
• 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.
• 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).
• 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.
• 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.
• 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.
• 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.
• 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 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.
• 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.
• 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.
• 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.

Landscapes

• Engineering & Computer Science (AREA)
• Theoretical Computer Science (AREA)
• Multimedia (AREA)
• Data Mining & Analysis (AREA)
• Databases & Information Systems (AREA)
• Physics & Mathematics (AREA)
• General Engineering & Computer Science (AREA)
• General Physics & Mathematics (AREA)
• Library & Information Science (AREA)
• Software Systems (AREA)
• Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Applications Claiming Priority (2)

Publications (1)

Family

ID=39718992

Family Applications (1)

Country Status (3)

Families Citing this family (2)

Family Cites Families (5)

• 2009
  • 2009-01-28 WO PCT/FR2009/050129 patent/WO2009095616A1/fr not_active Ceased
  • 2009-01-28 EP EP09706882A patent/EP2245555A1/de not_active Withdrawn
  • 2009-01-28 US US12/865,309 patent/US20100332541A1/en not_active Abandoned

Non-Patent Citations (1)

Also Published As

Similar Documents

Legal Events