Digital video fingerprinting based on resultant weighted gradient orientation computation

• US 8,385,644 B2
• Filed: 06/25/2009
• Issued: 02/26/2013
• Est. Priority Date: 07/08/2008
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Zeitera LLC
• Inventors: Stojancic, Mihailo M.
• Primary Examiner(s): Werner, Brian P
• Application Number:
  US12/491,896
• Publication Number:
  US 20100007797A1
• Time in Patent Office: 1,342 Days
• Field of Search: None
• US Class Current: 382/170
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: G06V 20/46 Extracting features or characteristics from the video content, e.g. video fingerprints, representative shots or key frames
• CPC Class Codes: H04N 21/835 Generation of protective data, e.g. certificates protecting software against unauthorised usage in a vending or licensing environment G06F21/10
• CPC Class Codes: H04N 5/147 Scene change detection

Abstract

Video sequence processing with various filtering rules is applied to extract dominant spatial features and generate unique set of signatures describing video content. Accurate active regions are determined for each video sequence frame. Subsequently, a video sequence is structured by tracking statistical changes in the content of a succession of video frames, and suitable frames are selected for further spatial processing. Selected video frames are processed for feature extraction and description, and compact representative signatures are generated, resulting in an efficient video database formation and search.

Claims

1. A method for content based video sequence identification comprising:

determining preliminary active regions in frames of a video sequence filtered to reduce noise wherein preliminary inactive regions in a selected video frame are determined by selecting frame boundary lines, each line having a normalized average brightness level that is less than a programmed percentage of a total normalized average brightness for the selected video frame;

computing a gradient based activity measure in the preliminary inactive regions to adjust the programmed percentage of the total normalized average brightness for the selected video frame, wherein the active regions are determined based on the adjusted programmed percentage of the total normalized average brightness for the selected video frame;

selecting a set of video frames in response to temporal statistical characteristics of the determined active regions;

extracting spatial video features from the selected set of video frames; and

generating multi-dimensional content based signatures based on the extracted spatial video features to identify the video sequence.

2. The method of claim 1, wherein determining active regions in frames comprises:

processing lines selected from video frame edges advancing through successive lines inward across a frame, and marking the successive lines that have a normalized average brightness that are less than the programmed percentage of the total normalized average brightness for the frame, wherein the marked successive lines represent the preliminary inactive regions;

determining a gradient based activity measure for the preliminary inactive regions;

comparing the gradient based activity measure for the preliminary inactive regions to an activity threshold value, wherein the programmed percentage of the total normalized average brightness for the frame is adjusted based on the comparison;

reprocessing the frame to mark lines selected from video frame edges advancing through successive lines inward across the frame that have a normalized average brightness that is less than the adjusted programmed percentage of the total normalized average brightness for the frame; and

discarding frame inactive area leaving the determined active regions remaining in the frame.

3. The method of claim 1 further comprising:

computing a normalized video frame brightness value for an entire frame and a frame brightness threshold parameter as a percentage of the normalized frame brightness value;

computing a normalized line brightness value for lines around frame boundaries;

comparing a normalized line brightness value for boundary lines with the frame brightness threshold parameter; and

determining a preliminary inactive boundary region defined by a number of successive horizontal and vertical boundary lines having a normalized line brightness value below the frame brightness threshold parameter.

4. The method of claim 1 further comprising:

deriving activity measures for preliminary inactive boundary regions by using an average intensity of a spatial gradient vector computed for pixels in the preliminary inactive boundary regions;

comparing the activity measure for a preliminary inactive boundary region against an activity threshold; and

deciding based on this comparison whether to accept the preliminary inactive boundary region as final or continue with active region determination.

5. The method of claim 4, wherein the activity measures are computed for each non-zero candidate inactive region around video frame boundaries as a normalized average sum of the intensity of spatial gradient vectors computed for pixels in the preliminary inactive boundary regions.

6. The method of claim 4 further comprising:

repeating the determination of active regions in frames based on a normalized line brightness value for boundary lines with an adjusted frame brightness threshold parameter used for line brightness evaluation;

enclosing a frame active region with horizontal, top and bottom, and vertical, left and right boundary lines having an average brightness that is less than the adjusted frame brightness threshold parameter; and

discarding frame boundary areas up to the boundary lines of the frame active region.

7. The method of claim 1, wherein extracting spatial video features comprises:

computing an intensity gradient vector [G_x(x), G_y(y)], an intensity gradient vector magnitude a function of [G_x(x), G_y(y)], and an intensity gradient vector phase θ

_p for active region pixels; and

computing multiple resultant weighted gradient vector orientations Ω

_ks each a function of G_p and θ

_p for sub-regions of the selected video frame as the extracted spatial video features for an active region of the selected video frame.

8. The method of claim 1, wherein generating multi-dimensional content based signatures comprises:

inscribing a rectangular functional space in an active region of a selected video frame to form k rectangular bins;

computing a resultant weighted gradient vector orientation Ω

_k value, as a function of an intensity gradient vector magnitude and an intensity gradient vector phase for each rectangular bin;

comparing the resultant weighted gradient vector orientation Ω

_k value for each rectangular bin to a weighted gradient vector orientation Ω

computed for the rectangular a functional space; and

generating a multi-dimensional content based signature by assigning 0 or 1 to signature bit positions corresponding to the rectangular bins, depending whether Ω

_k≦

Ω

or Ω

_k>

Ω

, respectively.

9. The method of claim 1, wherein generating multi-dimensional content based signatures comprises:

inscribing a log-polar functional space in an active region of a selected video frame to form k log-polar bins;

computing a resultant weighted gradient vector orientation Ω

_k value, as a function of an intensity gradient vector magnitude and an intensity gradient vector phase for each log-polar bin;

comparing the resultant weighted gradient vector orientation Ω

_k value for each log-polar bin to a weighted gradient vector orientation Ω

value computed for the log-polar functional space; and

generating a multi-dimensional content based signature by assigning 0 or 1 to the signature bit positions corresponding to the log-polar bins, depending whether Ω

_k≦

Ω

or Ω

_k>

Ω

, respectively.

10. The method of claim 1, wherein generating multi-dimensional content based signatures comprises:

forming a histogram of resultant weighted gradient vector orientation Ω

_k values computed for a set of sub-regions of size N×

M covering a determined active region of a video frame;

assigning to each histogram bin a bin count of Ω

_k values falling into an assigned range;

computing a mean value of bin counts for the histogram; and

generating a signature by comparing each bin count to the mean value of bin counts for the histogram.

11. The method of claim 2, wherein the gradient based activity measure comprises:

calculating a gradient vector intensity for each pixel in the non-zero regions surrounding the preliminary active region; and

calculating the gradient based activity measure as a normalized average sum of the gradient vector intensities.

12. The method of claim 1, wherein mean absolute difference (MAD) values are computed for contiguous pairs of video frame active regions in a succession of video frames in a video sequence.

13. The method of claim 12, wherein a temporal statistical function f₀(n) is generated in response to the MAD values, wherein the f₀(n) function is a time series with its samples having identical values as the MAD values computed for the entire video sequence.

14. The method of claim 13, wherein the f₀(n) function is partitioned with a programmable size sliding window into multiple overlapping temporal partitions, wherein the starting point of each sliding window in time succession is attached to local extrema of f₀(n) computed for the previous sliding window.

15. The method of claim 13 wherein video frames are selected for further spatial processing at extrema positions of f₀(n) local to sliding windows, alternating between a local maximum or a local minimum position within the scope of each sliding window.

16. A method for content based video sequence identification comprising:

determining active regions in frames of a video sequence filtered to reduce noise, wherein the active regions in frames are determined by comparing a normalized sum of gradient vector intensities computed for preliminary inactive regions with an activity threshold in a process that adjusts a programmed percentage of a total normalized average brightness for the frame to refine the selection of regions that exceed the adjusted programmed percentage of the total normalized average brightness for the frame as the active regions;

selecting a set of video frames in response to temporal statistical characteristics of the determined active regions;

extracting spatial video features from the selected set of video frames; and

generating multi-dimensional content based signatures based on the extracted spatial video features to identify the video sequence.

17. The method of claim 16, wherein a normalized sum of gradient vector intensities computed for the preliminary inactive regions is used to refine the initial active region determination.