Method and device for verifying multimedia entities and in particular for verifying digital images

• US 8,031,979 B2
• Filed: 09/24/2004
• Issued: 10/04/2011
• Est. Priority Date: 09/25/2003
• Status: Expired due to Fees

• Current Assignee: Canon Finetech Incorporated (Canon Inc.)
• Original Assignee: Canon Finetech Incorporated (Canon Inc.)
• Inventors: Nguyen, Eric, Baron, Stéphane, Le Floch, Hervé
• Primary Examiner(s): Tran; Phuoc
• Assistant Examiner(s): LIEW, ALEX KOK SOON
• Application Number:
  US10/948,178
• Publication Number:
  US 20050105798A1
• Time in Patent Office: 2,566 Days
• Field of Search: 382/305, 382181-231, 382/306
• US Class Current: 382/305
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: H04N 1/32144 embedded in the image data, i.e. enclosed or integrated in the image, e.g. watermark, super-imposed logo or stamp
• CPC Class Codes: H04N 1/32149 Methods relating to embedding, encoding, decoding, detection or retrieval operations

Abstract

The method of verifying multimedia entities according to the invention to determine whether a first multimedia entity matches a second multimedia entity, is characterized in that it comprises a step of selecting from a plurality of second multimedia entities, by a content-based search, a set of second multimedia entities close to the first multimedia entity, and a step of deciding as to at least one match between the first multimedia entity and at least one second multimedia entity of the set of second multimedia entities, based on a comparison between the first multimedia entity and the second multimedia entities of the set.

Claims

1. A method of verifying multimedia entities in a processing device to determine whether a first multimedia entity matches a second multimedia entity, characterized in that it comprises the steps of:

selecting, by a content-based search, from a plurality of second multimedia entities, a set of second multimedia entities close to said first multimedia entity, and

deciding, in the processing device, as to at least one match between said first multimedia entity and at least one second multimedia entity of said set of second multimedia entities, based on a comparison between said first multimedia entity and said second multimedia entities of said set, wherein said deciding step comprises sub-steps of;

obtaining a first criterion (C1) of match reliability,

comparing the first reliability criterion (C1) obtained with a predetermined threshold, in the processing device,

according to the result of the comparison, deciding, in the processing device, whether a first match between the first multimedia entity and the second multimedia entity exists, and

in case of a positive first match decision, the method comprises the following steps performed by the processing device;

extracting a first item of information from the first multimedia entity,

comparing the extracted item of information with a second item of information of the second multimedia entity,

obtaining a second criterion (C2) of match reliability,

according to the result of the comparison of items of information, deciding as to a match between the first and second items of information,

deciding as to a second match between the first multimedia entity and the second multimedia entity depending, on the one hand, on the decision of the first match between the first and second multimedia entity and, on the other hand, on the decision as to a match between the first and second items of information, and

determining a measurement of the reliability of the decision as to the second match depending on at least one of the first and second match reliability criteria.

2. A method of verifying at least one match between a first multimedia entity and a second multimedia entity in a processing device, characterized in that the method comprises the following steps:

obtaining a first criterion (C1) of match reliability,

comparing the first reliability criterion (C1) obtained with a predetermined threshold, in the processing device

according to the result of the comparison, deciding, in the processing device, whether a first match between the first multimedia entity and the second multimedia entity exists, and

in case of a positive first match decision, the method comprises the following steps performed in the processing device;

extracting a first item of information from the first multimedia entity,

comparing the extracted item of information with a second item of information of the second multimedia entity,

obtaining a second criterion (C2) of match reliability, according to the result of the comparison of items of information, deciding as to a match between the first and second items of information,

deciding as to a second match between the first multimedia entity and the second multimedia entity depending, on the one hand, on the decision of the first match between the first and second multimedia entity and, on the other hand, on the decision as to a match between the first and second items of information, and

determining a measurement of the reliability of the decision as to the second match depending on at least one of the first and second match reliability criteria.

3. A method according to claim 2, characterized in that the first item of information extracted from the first multimedia entity is a watermarking message.

4. A method according to claim 3, characterized in that the extraction of the watermarking message is performed on the basis of at least one extraction parameter associated with a second watermarking message of the second multimedia entity.

5. A method according to claim 4, characterized in that said at least one extraction parameter is associated with at least one insertion parameter used for the insertion of said second watermarking message in the second multimedia entity.

6. A method according to claim 2, characterized in that prior to said step of extracting a first item of information from the first multimedia entity, the method comprises a step of readjusting said first multimedia entity with respect to said second multimedia entity, in order to allow extraction of said first item of information from said readjusted first multimedia entity.

7. A method according to claim 2, characterized in that said first multimedia entity is obtained from a network.

8. A method according to claim 7, characterized in that obtaining said first multimedia entity comprises a step of identifying the address on the network of said first multimedia entity and/or the address referencing said first multimedia entity.

9. A method according to claim 2, characterized in that, the multimedia entities being images, the step of deciding as to the second match is followed by a step of producing a report containing a same scene indication if the decision as to the first match between the first multimedia entity and said second multimedia entity is positive and if the decision as to the match between the first and second items of information is negative.

10. A method according to claim 9, characterized in that, the measurement of the reliability of the decision as to the second match is associated with the same scene indication and corresponds to the first criterion of match reliability (C1).

11. A method according to claim 9, characterized in that the step of deciding as to the second match is followed by a step of inserting a same image indication in the report if the decision as to the first match between the first multimedia entity and the second multimedia entity is positive and if the decision as to the match between the first and second items of information is positive.

12. A method according to claim 11, characterized in that the measurement of the reliability of the decision as to the second match is associated with the same image indication and corresponds to the product of the first criterion of match reliability and the second criterion of match reliability.

13. A method according to claim 8, further comprising the step of producing a report that comprises an address on the network of said first multimedia entity and/or an address referencing said first multimedia entity.

14. A method according to claim 2, characterized in that the second multimedia entity forms part of a set of second multimedia entities.

15. A method according to claim 14, characterized in that, prior to the step of obtaining a first criterion of match reliability, the method comprises a step of selecting, from the set of second multimedia entities, a plurality of second multimedia entities close to said first multimedia entity.

16. A method according to claim 2, each multimedia entity comprising a plurality of units of interest, characterized in that obtaining the first criterion of match reliability comprises the following sub-steps:

matching information on local content of the first multimedia entity with information on local content of the second multimedia entity, said information on local content being associated with units of interest,

geometric matching of units of interest of the first multimedia entity with units of interest of the second multimedia entity, and

defining, in one of the multimedia entities, a region comprising the units of interest resulting from the step of geometric matching;

obtaining of the first criterion of match reliability being performed on the basis of the result of the steps of matching information on local content and geometric matching over the defined region.

17. A method according to claim 16, characterized in that, with each multimedia entity there is associated at least one descriptor determined prior to the step of obtaining the first criterion of match reliability, said at least one descriptor associated with at least one unit of interest of the multimedia entity comprising at least one item of information on local content and at least one item of position information said at least one descriptor being used during the steps of matching information on local content and of geometric matching.

18. A method according to claim 16, characterized in that the step of matching information on local content of the first multimedia entity with information on local content of the second multimedia entity comprises the following steps:

for each item of information on local content of the first multimedia entity, selecting, from the information on local content of the second multimedia entity, information substantially close to the item of information on local content concerned, so defining a first set of matches of which each forms a pair between the item information on local content concerned of the first entity and one of the items of information substantially close to the second entity,

for each item of information on local content of the second multimedia entity, selecting, from the information on local content of the first multimedia entity, information substantially close to the item of information on local content concerned, so defining a second set of matches of which each forms a pair between the item of information on local content concerned of the second entity and one of the items of information substantially close to the first entity,

determining the intersection of the first and second set of matches.

19. A method according to claim 18, characterized in that selecting a set of matches for an item of information on local content concerned of a multimedia entity comprises the following steps:

calculating the distances between said item of information on local content concerned and each of the items of information on local content of the other multimedia entity,

determining the distances less than a predetermined threshold, so defining the set of matches concerned.

20. A method according to claim 16, characterized in that the step of geometric matching comprises the following steps:

determining a possible geometric transformation necessary to obtain the first multimedia entity from the second multimedia entity,

determining a set of units of interest of the first and of the second entity for which the geometric transformation makes it possible to match a unit of interest of the first multimedia entity and a unit of interest of the second multimedia entity.

21. A method according to claim 20, characterized in that the step of determining a possible geometric transformation comprises estimating the geometric coherence between position information associated with matched items of information on local content.

22. A method according to claim 16, characterized in that the second multimedia entity forms part of a set of second multimedia entities and in that obtaining the first criterion of match reliability is performed on the basis of the ratio between a probability that the first multimedia entity does not match one of the second multimedia entities and a probability that the first multimedia entity matches one of the second multimedia entities, these two probabilities being a function of the result of the matching steps.

23. A method according to claim 16, characterized in that the step of deciding is followed by a step of producing a report that comprises a thumbnail image in which a region is defined that comprises the units of interest resulting from the step of geometric matching.

24. A method according to claim 2, characterized in that, prior to the step of obtaining the first criterion (C1) of match reliability, the method comprises the steps of:

obtaining at least one descriptor for each of the first and second multimedia entities,

calculating a distance between the descriptors obtained.

25. A method according to claim 24, characterized in that obtaining the first criterion of match reliability is performed on the basis of the calculation of a probability of first match depending on the distance calculated.

26. A method according to claim 24, characterized in that the descriptor is obtained by the following steps:

obtaining division of the multimedia entity into at least a predetermined number of blocks,

and for each block;

extracting at least one unit of interest, and

storing the coordinates of said at least one unit of interest.

27. A method according to claim 26, characterized in that the calculation of a distance, between the descriptors obtained from the first multimedia entity and from the second multimedia entity, is performed by adding, over the set of blocks obtained by dividing each multimedia entity, the distances between units of interest belonging to said spatially matching blocks.

28. A method according to claim 27, characterized in that the distances between units of interest by block is equal to the maximum distance between coordinates of the units of interest.

29. A method according to claim 27, characterized in that the calculated distance is equal to the minimum of the distances obtained after application, to one of the multimedia entities considered, of a geometric transformation belonging to a predetermined set of transformations.

30. A method according to claim 26, characterized in that the step of obtaining division comprises the steps of:

standardizing the size of the multimedia entity to a predetermined size

dividing the standardized multimedia entity into said at least a predetermined number of blocks.

31. A method according to claim 26, characterized in that a unit of interest is an extremum of a filtering operator.

32. A method according to claim 15, characterized in that in the step of selecting a plurality of second multimedia entities close to said first multimedia entity comprises the following steps:

for each pair of first and of second multimedia entities, the steps of obtaining descriptors and of calculating the distance associated with the method of claim 24, and

selecting second multimedia entities for which the distances with the first multimedia entity are the least.

33. A method according to claim 32, characterized in that the first criterion of match reliability further depends on the number of second multimedia entities of the set of second multimedia entities.

34. A method according to claim 24, characterized in that the predetermined threshold is a predetermined value (P⁰_FA) of the probability of taking an erroneous decision as to the first match between the first multimedia entity and a second multimedia entity.

36. A computer program embodied in a non-transitory computer-readable medium, said program containing instructions enabling the implementation of a method of verifying a match between a first multimedia entity and a second multimedia entity according to claim 2, when that program is loaded and executed by a computer system.

35. A device for verifying at least one match between a first multimedia entity and a second multimedia entity, characterized in the device comprises:

means for obtaining a first criterion (C1) of match reliability,

means for comparing the first reliability criterion (C1) obtained with a predetermined threshold,

means for deciding as to a first match between the first multimedia entity and the second multimedia entity and which are adapted to decide as to the first match according to the result of the comparison,

means for extracting a first item of information from the first multimedia entity,

means for comparing between the extracted item of information and a second item of information of the second multimedia entity,

means for obtaining a second criterion (C2) of match reliability,

means for deciding as to a match between the first and second items of information and which are adapted to decide as to said match according to the result of the comparison of items of information, and

means for deciding as to a second match between the first multimedia entity and the second multimedia entity, said deciding means being adapted to decide as to the second match depending, on the one hand, on the decision of the first match between the first and second multimedia entity and, on the other hand, on the decision as to a match between the first and second items of information, and

means for determining a measurement of the reliability of the decision as to the second match which are adapted to determine the measurement of the reliability of the decision depending on at least one of the first and second match reliability criteria.