System and method for generation of complex signatures for multimedia data content

• US 8,312,031 B2
• Filed: 08/10/2009
• Issued: 11/13/2012
• Est. Priority Date: 10/26/2005
• Status: Active Grant

• Current Assignee: Cortica Ltd.
• Original Assignee: Cortica Ltd.
• Inventors: Raichelgauz, Igal, Odinaev, Karina, Zeevi, Yehoshua Y.
• Primary Examiner(s): Girma, Anteneh
• Application Number:
  US12/538,495
• Publication Number:
  US 20090313305A1
• Time in Patent Office: 1,191 Days
• Field of Search: None
• US Class Current: 707/756
• CPC Class Codes: G06F 16/152 using file content signatures, e.g. hash values
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/43 Querying
• CPC Class Codes: G06F 16/48 Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
• CPC Class Codes: Y10S 707/913 Multimedia
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A method and system for generating a complex signature of a multimedia data element. The method comprises partitioning the multimedia data element recursively until a minimum size multimedia data element is reached; generating a signature for each minimum size multimedia data element; assembling at least a complex signature comprising a plurality of signatures of the minimum size multimedia data elements; and storing the signatures of each of the minimum size multimedia data elements and the complex signature of the multimedia data element in association with the multimedia data element and partitions thereof in a storage unit.

Claims

1. A computer-implemented method for generating a complex signature of a multimedia data element, comprising:

partitioning the multimedia data element recursively until a minimum size multimedia data element is reached;

generating a first signature and second signature for each minimum size multimedia data element, wherein the first and second signatures are generated by a plurality of computational cores that process each of the plurality of minimum size multimedia data elements, each core having properties that have at least some statistical independency from other of the computational cores, the properties are independent of each other core, wherein the properties of each of the plurality of computational cores include a first threshold and a second threshold, each of the plurality of computational cores generates responsive to each of the minimum size multimedia data elements the first signature and the second signature, wherein the first signature is generated respective of a robust selection criterion and a first threshold, and the second signature is generated respective of a second threshold, wherein the first threshold is higher than the second threshold, the first signature is a robust to signature;

assembling at least a complex signature comprising a plurality of the first and second signatures of the minimum size multimedia data elements; and

storing the first and second signatures of each of the minimum size multimedia data elements and the complex signature of the multimedia data element in association with the multimedia data element and partitions thereof in a storage unit.

2. The method of claim 1, wherein assembling the complex signature of the multimedia data element, further comprising:

assembling a complex signature for each partition level, wherein a complex signature of a higher partition level comprises a plurality of complex signatures of a lower partition level or signatures of a plurality of the minimum size multimedia data elements.

3. The method of claim 1, wherein the multimedia data element is selected from the group consisting of an image, graphics, a video stream, a video clip, an audio stream, an audio clip, a video frame, a photograph, images of signals, combinations thereof, and portions thereof.

4. The method of claim 3, wherein the images of signals are images selected from the group consisting of medical signals, geophysical signals, subsonic signals, supersonic signals, electromagnetic signals, and infrared signals.

5. The method of claim 1, further comprising:

generating at least a first signature and a second signature to a permutation of at least one minimum size multimedia data element.

6. The method of claim 5, wherein the permutation is an angular permutation.

7. The method of claim 1, is executed by computer executable code stored in computer readable medium.

8. A computer-implemented method for matching an input multimedia data element to previously stored multimedia content comprising:

receiving an input multimedia data element;

generating first and second signatures and at least a complex signature responsive of the input multimedia data element, wherein the first and second signatures includes generating a first signature and a second signature responsive of each input minimum size multimedia data element by a plurality of computational cores that process each of the plurality of minimum size multimedia data elements, each core having properties that have at least some statistical independency from other of the computational cores, the properties are independent of each other core, wherein the properties of each of the plurality of computational cores include a first threshold and a second threshold, each of the plurality of computational cores generates responsive to each of the minimum size multimedia data elements the first signature and the second signature, wherein the first signature is generated respective of a robust selection criterion and a first threshold, and the second signature is generated respective of a second threshold, wherein the first threshold is higher than the second threshold, the first signature is a robust to signature;

comparing between the first and second signatures and the complex signature generated responsive of the input multimedia data element to at least first and second signatures and the complex signature of the multimedia data element stored in a storage unit; and

determining if a match is found by comparing a match score to a matching threshold, and if a match is found generating a match indication;

otherwise, generating a no-match indication;

wherein a complex signature comprises any one of a plurality of complex signatures of a lower partition level of a multimedia data element and first and second signatures of a plurality of minimum size multimedia data elements.

9. The method of claim 8, wherein the comparison between the generated signatures and the signatures stored in the storage unit is performed by a plurality of computational cores responsive of at least one of the first and second signatures and complex signatures of the input multimedia data element and the first and second signatures and at least a complex signature of a multimedia data element stored in the storage unit.

10. The method of claim 9, further comprising:

setting properties of each of said plurality of computational cores to be independently of each other core.

11. The method of claim 8, further comprising:

generating at least first and second signatures to a permutation of at least one minimum size multimedia data element.

12. The method of claim 11, wherein the permutation is an angular permutation.

13. The method of claim 8, is executed by computer executable code stored in computer readable medium.

14. A system for generating a complex signature of a multimedia data element, comprising:

a partitioning unit for partitioning the multimedia data element or partitions thereof to a plurality of multimedia data elements, and if a multimedia data element or partition thereof is larger than a threshold, further partitioning each multimedia data element or partition thereof that is larger than the threshold until no further partitioning is possible, wherein the partitioning unit outputs a plurality of minimum size multimedia data elements;

a signature generator for generating a first signature and a second signature for each of the plurality of minimum size multimedia data elements, wherein the signature generator includes a plurality of computational cores that process each of the plurality of minimum size multimedia data elements, each core having properties that have at least some statistical independency from other of the computational cores, the properties are independent of each other core, wherein the properties of each of the plurality of computational cores include a first threshold and a second threshold, each of the plurality of computational cores generates responsive to each of the minimum size multimedia data elements the first signature and the second signature, wherein the first signature is generated respective of a robust selection criterion and a first threshold, and the second signature is generated respective of a second threshold, wherein the first threshold is higher than the second threshold, the first signature is a robust to signature;

a signature assembly unit for assembling a complex signature for a partition level higher than a level of the minimum size multimedia data elements, wherein the complex signature comprises any one of a plurality of signatures of the minimum size multimedia data elements and a plurality of complex signatures of an immediately lower partitioning level; and

a storage unit for storing the first and second signatures and the complex signatures.

15. The system of claim 14, further comprising:

a comparison unit for comparing at least a complex signature generated for the multimedia data element to at least a complex signature stored in the storage unit.

16. The system of claim 14, wherein the signal generator is further configured to generate;

a first signature and a second signature to at least a permutation of the minimum size multimedia data element.

17. The system of claim 16, wherein the permutation is an angular permutation.

18. The system of claim 14, wherein the multimedia data element is selected from the group consisting of an image, graphics, a video stream, a video clip, an audio stream, an audio clip, a video frame, a photograph, images of signals, a combinations thereof, and portions thereof.

19. The system of claim 18, wherein the images of signals are images selected from the group consisting of medical signals, geophysical signals, subsonic signals, supersonic signals, electromagnetic signals, and infrared signals.

20. A method for generating a complex signature of a multimedia data element comprising:

partitioning, by a partitioning unit, the multimedia data element or partitions thereof to a plurality of multimedia elements, if the multimedia element or partition thereof is larger than a threshold further partitioning each partitioned multimedia data element larger than the threshold until no further partitioning is possible, wherein the partitioning process produces a plurality of minimum size multimedia data elements;

generating, by a signature generator, a first signature and a second signature for each of the plurality of minimum size multimedia data elements, wherein the signature generator includes a plurality of computational cores that process each of the plurality of minimum size multimedia data elements, each core having properties that have at least some statistical independency from other of the computational cores, the properties are independent of each other core, wherein the properties of each of the plurality of computational cores include a first threshold and a second threshold, each of the plurality of computational cores generates responsive to each of the minimum size multimedia data elements the first signature and the second signature, wherein the first signature is generated respective of a robust selection criterion and a first threshold, and the second signature is generated respective of a second threshold, wherein the first threshold is higher than the second threshold, the first signature is a robust to signature;

assembling, by a signature assembly unit, a complex signature for a partition level higher than the level of the minimum size multimedia data elements, wherein the complex signature comprises any one a plurality of first and second signatures of the minimum size multimedia data elements and a plurality of complex signatures of an immediately lower partitioning level; and

storing the first and second signatures and the complex signatures in a storage unit.

21. The method of claim 20, wherein the multimedia data element is selected from the group consisting of an image, graphics, a video stream, a video clip, an audio stream, an audio clip, a video frame, a photograph, images of signals, a combinations thereof, and portions thereof.

22. The method of claim 21, wherein the images of signals are images selected from the group consisting of medical signals, geophysical signals, subsonic signals, supersonic signals, electromagnetic signals, and infrared signals.

23. A system for matching an input multimedia data element, comprising:

a partitioning unit for partitioning the input multimedia data element or partitions thereof to a plurality of multimedia data elements, and if a multimedia data element or partition thereof is larger than a threshold, further partitioning each multimedia data element or partition thereof that is larger than the threshold until no further partitioning is possible, wherein the partitioning unit outputs a plurality of minimum size multimedia data elements;

a signature generator for generating a first signature and a second signature for each of the plurality of minimum size multimedia data elements a respective signature, the signature generator includes a plurality of computational cores that process each of the plurality of minimum size multimedia data elements, each core having properties that have at least some statistical independency from other of the computational cores, the properties are independent of each other core, wherein the properties of each of the plurality of computational cores include a first threshold and a second threshold, each of the plurality of computational cores generates responsive to each of the minimum size multimedia data elements the first signature and the second signature, wherein the first signature is generated respective of a robust selection criterion and a first threshold, and the second signature is generated respective of a second threshold, wherein the first threshold is higher than the second threshold, the first signature is a robust to signature;

a signature assembly unit for assembling a complex signature for a partition level higher than a level of the minimum size multimedia data elements, wherein the complex signature comprises any one of a plurality of first and second signatures of the minimum size multimedia data elements and a plurality of complex signatures of an immediately lower partitioning level;

a storage unit for storing the first and second signatures and the complex signatures generated for the input multimedia data element and at least a complex signature and a plurality of first and second signatures of minimum size multimedia data elements of at least a previously partitioned multimedia data element; and

a comparison unit for comparing the generated complex signature of the input multimedia data element to the complex signatures of the at least previously partitioned multimedia data element and generating a match indication when a match between the input multimedia data element and the at least previously partitioned multimedia data element is found.