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

• US 20050105798A1
• Filed: 09/24/2004
• Published: 05/19/2005
• Est. Priority Date: 09/25/2003
• Status: Active Grant

• Current Assignee: Canon Finetech Incorporated (Canon Inc.)
• Original Assignee: Canon Finetech Incorporated (Canon Inc.)
• Inventors: Nguyen, Eric, Le Floch, Herve, Baron, Stephane
• Granted Patent: US 8,031,979 B2
• Time in Patent Office: Days
• US Class Current: 382/181
• 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 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 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.

2. A method according to claim 1, characterized in that in said selecting step, said selected set of second multimedia entities comprises the K second multimedia entities that are the closest to said first multimedia entity, K having a predetermined constant value.

3. A method according to claim 1, characterized in that the selecting step comprises sub-steps of:

calculating one or more first descriptors for said first multimedia entity, and

obtaining at least one second descriptor for each said second multimedia entity,

said content-based search uses said first and second descriptors describing said first and second multimedia entities for selecting said set of second multimedia entities.

4. A method according to claim 3, characterized in that said descriptors comprise at least one global type descriptor.

5. A method according to claim 4, characterized in that said descriptors comprise at least one local type descriptor.

6. A method according to claim 1, characterized in that said deciding step comprises sub-steps of:

readjusting said first multimedia entity relative to a said second multimedia entity in course of processing said set of second multimedia entities,

measuring a level of match, after readjusting, between said first multimedia entity and said second multimedia entity in course of processing said set of second multimedia entities, and

comparing said level of match and a first predetermined threshold in order to decide on the match between said first multimedia entity and said second multimedia entity in course of processing said set of second multimedia entities.

7. A method according to claim 6, characterized in that said readjusting sub-step comprises a change of scale of said first multimedia entity and/or reframing of said first multimedia entity and/or use of points of interest in said multimedia entities.

8. A method according to claim 1, characterized in that said deciding step comprises sub-steps of:

extracting a first watermarking message inserted into said first multimedia entity,

calculating a binary distance between said first watermarking message and a second watermarking message of a second multimedia entity in course of processing said set of second multimedia entities, and

comparing said binary distance and a second predetermined threshold in order to decide on the match between said first multimedia entity and said second multimedia entity in course of processing said set of second multimedia entities.

9. A method according to claim 8, characterized in that the extraction of the first watermarking message inserted into said first multimedia entity is performed on the basis of at least one extraction parameter associated with the second watermarking message of the second multimedia entity.

10. A method according to claim 9, 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.

11. A method according to claim 8, characterized in that said deciding step also comprises a sub-step of readjusting said first multimedia entity relative to said second multimedia entity in course of processing said set of second multimedia entities, said readjusting sub-step being performed before said extracting sub-step in order to enable extraction of said first watermarking message from said readjusted first multimedia entity.

12. A method according to claim 1, characterized in that said multimedia entities are digital images which may be represented, at the operator managing the verifying device, and according to the processing performed, by metadata and/or a low resolution summary and/or a set of points of interest and/or dimensions of said images and/or a visual descriptor of the image.

13. A method according to claim 1, characterized in that comprises, prior to the selecting step, a step of obtaining the first multimedia entity.

14. A method according to claim 1, characterized in that the deciding step is followed by a step of producing a report on the match or non-match between the first multimedia entity and said at least one second multimedia entity.

15. A method according to claim 1, characterized in that the first multimedia entity is a request multimedia entity and the set of second multimedia entities is a set of reference multimedia entities.

16. A method according to claim 15, characterized in that the request multimedia entity is obtained from a network.

17. A method according to claim 16, characterized in that obtaining the request multimedia entity comprises a step of identifying the address on the network of the request multimedia entity and/or the address referencing the request multimedia entity.

18. A method according to claim 14, characterized in that the report comprises metadata and/or a low resolution summary and/or a set of points of interest and/or dimensions of said multimedia entities.

19. A method according to claim 14, characterized in that the report comprises the address on a network of the request multimedia entity and/or the address referencing the request multimedia entity.

20. A method according to claim 1, characterized in that the method further comprises a step of recording the first multimedia entity in a set of first multimedia entities.

21. A method according to claim 20, characterized in that the set of first multimedia entities is a set of reference multimedia entities and the set of second multimedia entities is a set of request multimedia entities.

22. A method according to claim 20, characterized in that the set of first multimedia entities is a set of request multimedia entities and the set of the second multimedia entities is a set of reference multimedia entities.

23. A method according to claim 22, characterized in that the set of request multimedia entities comprises a predetermined number of request multimedia entities.

24. A method according to claim 22, characterized in that the set of request multimedia entities comprises request multimedia entities obtained after a given date.

25. A method according to claim 21, characterized in that, in case of a match between a reference multimedia entity and a request multimedia entity, a report is produced which comprises the address on a network of the request multimedia entity.

26. A method according to claim 1, characterized in that the 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,

according to the result of the comparison, deciding as to a first match between the first multimedia entity and the second multimedia entity,

in case of positive first match decision, the method comprises the following steps;

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

comparing between the extracted item of information and 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.

62. An information processing device adapted to operate as a device for verifying a match between a first multimedia entity and a second multimedia entity, characterized in that it comprises means adapted to implement a method of verifying a match according to claim 1.

65. An information carrier readable by a computer system, possibly wholly or partly removable, in particular a CD-ROM or magnetic medium, such as a hard disk or a diskette, or a transmissible medium, such as an electrical or optical signal, said carrier comprising instructions of a computer program enabling the implementation of a method of verifying a match between a first multimedia entity and a second multimedia entity according to claim 1, when that program is loaded and run by a computer system.

66. A computer program stored on an information carrier, 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 1, when that program is loaded and executed by a computer system.

27. A method of verifying at least one match between a first multimedia entity and a second multimedia entity, characterized in 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,

according to the result of the comparison, deciding as to a first match between the first multimedia entity and the second multimedia entity,

in case of positive first match decision, the method comprises the following steps;

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

comparing between the extracted item of information and 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.

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

29. A method according to claim 28, 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.

30. A method according to claim 29, 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.

31. A method according to claim 27, 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.

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

33. A method according to claim 32, 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.

34. A method according to claim 27, 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.

35. A method according to claim 34, 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).

36. A method according to claim 34, 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.

37. A method according to claim 36, 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.

38. A method according to claim 33, 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.

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

40. A method according to claim 39, 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.

41. A method according to claim 27, 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.

42. A method according to claim 41, 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.

43. A method according to claim 41, 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.

44. A method according to claim 43, 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.

45. A method according to claim 41, 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.

46. A method according to claim 45, 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.

47. A method according to claim 41, 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.

48. A method according to claim 41, 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.

49. A method according to claim 27, 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.

50. A method according to claim 49, 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.

51. A method according to claim 49, 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.

52. A method according to claim 51, 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.

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

54. A method according to claim 52, 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.

55. A method according to claim 51, 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.

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

57. A method according to claim 40, 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 49, and

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

58. A method according to claim 57, 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.

59. A method according to claim 49, 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.

60. A device for verifying multimedia entities to determine whether a first multimedia entity matches a second multimedia entity, characterized in that it comprises:

means for 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

means for deciding as to at least one match between said first multimedia entity and at least one said 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.

63. A telecommunications system comprising a plurality of terminal devices connected via a telecommunications network, characterized in that it comprises at least one terminal device equipped with a device for a match between a first multimedia entity and a second multimedia entity according to claim 60.

64. A device for storing multimedia entities, characterized in that it comprises at least one device for verifying a match between a first multimedia entity and a second multimedia entity according to claim 60.

61. 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.