Extraction of video fingerprints and identification of multimedia using video fingerprinting

Patent metadata

Field	Value
Publication number	US-8934545-B2
Application number	US-70665810-A
Country	US
Kind code	B2
Filing date	Feb 16, 2010
Priority date	Feb 13, 2009
Publication date	Jan 13, 2015
Grant date	Jan 13, 2015

Abstract

A video fingerprinting algorithm extracts characteristic features from regions of interest in a media object, such as a video signal. The regions of interest contain the perceptually important parts of the video signal. A fingerprint may be extracted from a target media object, and the fingerprint the target media content may then be matched against multiple regions of interest of known reference fingerprints. This matching may allow identification of complex scenes, inserts, and different versions of the same content presented in different formats of the media object.

First claim

What is claimed is:

1. A method for generating a characteristic fingerprint for a multimedia signal, the method comprising:
receiving, by a computing device, a media object, the media object comprising at least spatial components;
identifying, by the computing device, a region of interest within the media object, the region of interest comprising a portion of the media object within a set of boundaries in the media object, the identifying of the region of interest comprises detecting the boundaries in the media object and comprising calculating statistics of changes in pixels across multiple frames and identifying areas of maximum variation of pixel values;
transforming, by the computing device, the region of interest into a format for fingerprinting, the transforming based on size, stability, and length of the region of interest, the transforming comprising scaling, by the computing device, at least a portion of the region of interest into a plurality of sets of columns, each set of columns comprising a plurality of columns containing data from the region of interest at a different horizontal scaling thereof;
computing, by the computing device, a plurality of sub-fingerprints for each of the sets of columns, each sub-fingerprint comprising characteristic information about one or more of the columns in the set of columns;
combining, by the computing device, the sub-fingerprints into a characteristic fingerprint for the media object; and
storing, by the computing device, the characteristic fingerprint in a storage medium.

2. The method of claim 1 , wherein the media object comprises a video signal, and the media object further comprises a time component.

3. The method of claim 1 , wherein the detected region of interest comprises at least two spatial components and a time component.

4. The method of claim 1 , wherein the detecting of the boundaries in the media object comprises detecting a key frame in the media object.

5. The method of claim 1 , wherein the detecting of the boundaries in the media object comprises performing motion estimation on the media object and inferring boundaries based on a gap in the motion of a feature within the media object.

6. The method of claim 1 , wherein the detecting of the boundaries in the media object comprises computing a divergence of a gradient field in the media object.

7. The method of claim 1 , wherein the detecting of the boundaries in the media object comprises detecting contour lines within the media object, wherein the contour lines are perpendicular to a spatial gradient in the media object.

8. The method of claim 1 , further comprising: detecting a plurality of regions of interest, wherein one region of interest is within another.

9. The method of claim 1 , wherein computing each sub-fingerprint for each of the set of columns comprises transforming the data from one or more columns into the frequency domain to produce a set of coefficients, and forming the sub-fingerprint from a plurality of the coefficients.

10. The method of claim 1 , wherein computing each sub-fingerprint for each of the set of columns comprises transforming the data from multiple columns into the frequency domain to produce a set of coefficients, and forming the sub-fingerprint from a plurality of the coefficients.

11. The method of claim 10 , wherein the transformed data is arranged in alternating spatial directions for consecutive sub-fingerprints.

12. The method of claim 1 , wherein the computed sub-fingerprints for each of the set of columns are computed from horizontally overlapping columns.

13. The method of claim 1 , further comprising: pre-processing the region of interest before the sub-fingerprints are computed, wherein the pre-processing comprises deemphasizing elements from the region of interest that are determined to be not part of a perceptual portion of the region of interest.

14. A computing device comprising:
a processor;
a storage medium for tangibly storing thereon program logic for execution by the processor, the program logic comprising computer instructions for:
receiving, by the processor, a media object, the media object comprising at least spatial components;
identifying, by the processor, a region of interest within the media object, the region of interest comprising a portion of the media object within a set of boundaries in the media object, the identifying of the region of interest comprises detecting the boundaries in the media object and comprising calculating statistics of changes in pixels across multiple frames and identifying areas of maximum variation of pixel values;
transforming, by the processor, the region of interest into a format for fingerprinting, the transforming based on size, stability, and length of the region of interest, the transforming comprising scaling at least a portion of the region of interest into a plurality of sets of columns, each set of columns comprising a plurality of columns containing data from the region of interest at a different horizontal scaling thereof;
computing, by the processor, a plurality of sub-fingerprints for each of the sets of columns, each sub-fingerprint comprising characteristic information about one or more of the columns in the set of columns;
combining, by the processor, the sub-fingerprints into a characteristic fingerprint for the media object; and
storing, by the processor, the characteristic fingerprint in the storage medium.

15. The computing device of claim 14 , wherein the media object comprises a video signal, and the media object further comprises a time component.

16. The computing device of claim 14 , wherein the detected region of interest comprises at least two spatial components and a time component.

17. The computing device of claim 14 , wherein the detecting of the boundaries in the media object comprises detecting a key frame in the media object.

18. The computing device of claim 14 , wherein the detecting of the boundaries in the media object comprises performing motion estimation on the media object and inferring boundaries based on a gap in the motion of a feature within the media object.

19. The computing device of claim 14 , wherein the detecting of the boundaries in the media object comprises computing a divergence of a gradient field in the media object.

20. The computing device of claim 14 , wherein the detecting of the boundaries in the media object comprises detecting contour lines within the media object, wherein the contour lines are perpendicular to a spatial gradient in the media object.

21. The computing device of claim 14 , further comprising detecting a plurality of regions of interest, wherein one region of interest is within another.

22. The computing device of claim 14 , wherein computing each sub-fingerprint for each of the set of columns comprises transforming the data from one or more columns into the frequency domain to produce a set of coefficients, and forming the sub-fingerprint from a plurality of the coefficients.

23. The computing device of claim 14 , wherein computing each sub-fingerprint for each of the set of columns comprises transforming the data from multiple columns into the frequency domain to produce a set of coefficients, and forming the sub-fingerprint from a plurality of the coefficients.

24. The computing device of claim 23 , wherein the transformed data is arranged in alternating spatial directions for consecutive sub-fingerprints.

25. The computi

Assignees

• Bilobrov Sergiy
• Yahoo Inc

Inventors

• Bilobrov Sergiy

Classifications

• G06V40/1347

  Preprocessing; Feature extraction · CPC title

• G06T1/0021 Primary

  Image watermarking · CPC title

• G06T1/00 Primary

  General purpose image data processing · CPC title

• G06T7/20

  Analysis of motion (motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51) · CPC title