System and Method for Generation of Complex Signatures for Multimedia Data Content

• US 20090313305A1
• Filed: 08/10/2009
• Published: 12/17/2009
• Est. Priority Date: 10/26/2005
• Status: Active Grant

• Current Assignee: Cortica Ltd.
• Original Assignee: Cortica Ltd.
• Inventors: ODINAEV, Karina, ZEEVI, Yehoshua Y., RAICHELGAUZ, Igal
• Granted Patent: US 8,312,031 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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 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.

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, wherein generating the signature further comprising:

generating a first signature and a second signature, wherein the first signature being a robust signature.

6. The method of claim 1, further comprising:

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

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

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

9. A method for matching an input multimedia data element to previously stored multimedia content comprising:

receiving an input multimedia data element;

generating signatures and at least a complex signature responsive of the input multimedia data element;

comparing between the signatures and the complex signature responsive of the input multimedia data element to at least signatures and the complex signature of the multimedia data element stored in the 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 a plurality of complex signatures of a lower partition level of a multimedia data element or signatures of a plurality of minimum size multimedia data elements.

10. The method of claim 9, wherein comparing between the signatures is performed by a plurality of computational cores responsive of signatures and/or complex signatures of the input multimedia data element and the at least signatures and at least a complex signature of a multimedia data element stored in the storage unit.

11. The method of claim 10, further comprising:

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

12. The method of claim 9, further comprising:

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

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

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

15. 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 there of 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 for each of the plurality of minimum size multimedia data elements a respective 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 either a plurality of signatures of the minimum size multimedia data elements or a plurality of complex signatures of an immediately lower partitioning level; and

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

16. The system of claim 15, further comprising:

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

17. The system of claim 15, wherein generation of a signature for a minimum size multimedia data element further comprising:

generating a signature to at least a permutation of the minimum size multimedia data element.

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

19. The system of claim 15, 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.

20. The system of claim 19, 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.

21. The system of claim 15, wherein the signature generator further comprising:

a plurality of computational cores, each computational core having properties set to be independent of each other computational core, each computational core generates responsive to the first multimedia data element the signature comprising of a first signature element and a second signature element, said first signature element being a robust signature.

22. 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 element, 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, for each of the plurality of minimum size multimedia data elements a respective 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 either a plurality of signatures of the minimum size multimedia data elements or a plurality of complex signatures of an immediately lower partitioning level; and

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

23. The method of claim 22, 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.

24. The method of claim 23, 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.

25. The method of claim 23, wherein the signature generator comprises a plurality of computational cores, each computational core having properties to be independently of each other computational core, each computational cores generates responsive to the first multimedia data element the signature comprising of a first signature element and a second signature element, said first signature element being a robust signature.

26. 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 there of 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 for each of the plurality of minimum size multimedia data elements a respective 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 either a plurality of signatures of the minimum size multimedia data elements or a plurality of complex signatures of an immediately lower partitioning level;

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

a comparison unit for comparing the signatures comprising the complex signature of the input multimedia data element to the 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 a previously partitioned multimedia data element is found.