Digital Video Fingerprinting Based on Resultant Weighted Gradient Orientation Computation

• US 20100007797A1
• Filed: 06/25/2009
• Published: 01/14/2010
• Est. Priority Date: 07/08/2008
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Zeitera LLC
• Inventors: Stojancic, Mihailo M.
• Granted Patent: US 8,385,644 B2
• Time in Patent Office: Days
• US Class Current: 348/607
• 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 active regions in frames of a video sequence;

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

extracting spatial video features from the selected video frames; and

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

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

filtering the video sequence to reduce noise; and

analyzing frames of the video sequence to isolate the active regions in frames.

3. The method of claim 2 further comprising:

computing a normalized 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 2 further comprising:

deriving activity measures for preliminary inactive boundary regions by using a normalized sum of spatial gradient vector intensities computed for pixels in the preliminary inactive boundary regions;

comparing an 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 normalized sum of spatial gradient vector intensities for the preliminary inactive boundary region is computed as G_n=(Σ

_nG_p)/n, where n is the number of pixels in the preliminary inactive boundary region, wherein G_p=√

[G_x²+G_y²], and [G_x(x), G_y(y)]=[∂

f(x,y)/∂

x, ∂

f(x,y)/∂

y].

6. The method of claim 4 further comprising:

repeating the determining 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 brighter than the given adjusted, or not 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 gradient vector [G_x(x), G_y(y)]=[∂

f(x,y)/∂

x, ∂

f(x,y)/∂

y], G_p=√

[G_x²+G_y²], and θ

_p=arctan(G_y/G_x) for active region pixels; and

computing resultant weighted gradient vector orientation Ω

_k=Σ

_n(G_pθ

_p)/Σ

_nG_p, k=1, 2, . . . ,K, for a set of K sub-regions as the extracted video features representative of an active region of a selected video frame.

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 Ω

_k=Σ

_n(G_pθ

_p)/σ

_nG_p value for each log-polar bin, wherein G_p√

[G_x²+G_y²], [G_x(x), G_y(y)]=[∂

f(x,y)/∂

x, ∂

f(x,y)/∂

y], and θ

_p=arctan(G_y/G_x);

comparing the resultant Ω

_k value for each log-polar bin to a Ω

=Σ

_f(G_pθ

_p)/Σ

_fG_p value computed for a functional space region defined by the outer-most circle boundary of 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 angles Ω

_k=Σ

_n(G_pθ

_p)/Σ

_nG_p computed for a set of sub-regions of size N×

M covering a determined active region of a video frame, wherein G_p=√

[G_x²+G_y²], [G_x(x), G_y(y)]=[∂

f(x,y)/∂

x, ∂

f(x,y)/∂

y], and θ

_p=arctan(G_y/G_x);

assigning to each histogram bin a bin count of Ω

_k values falling into an assigned range of (k2π

/r, (k+1)2π

/r), where k=0,1, . . . ,r−

1, r is the count of histogram bins;

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.

8. The method of claim l, 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 Ω

_k=Σ

_n(G_pθ

_p)/Σ

_nG_p value for each rectangular bins wherein G_p=√

[G_x²+G_y²], [G_x(x), G_y(y)]=[∂

f(x,y)/∂

x, ∂

f(x,y)/∂

y], and θ

_p=arctan(G_y/G_x);

comparing the resultant Ω

_k value for each rectangular bin to a Ω

=Σ

_f(G_pθ

_p)/Σ

_fG_p value computed for a functional space region defined by an outer edge of the rectangular 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.

11. A method for generating a multi-bit signature based on spatial domain video frame processing, the method comprising:

tiling an active area of a video frame according to a functional grid to form a tiled functional space in the active area having multiple tile bins;

extracting spatial video features from the tile bins based on a gradient vector and orientation of pixels in the tile bins; and

generating multiple type multi-bit signatures based on the extracted video features.

12. The method of claim 11, wherein extracting spatial video features comprises:

computing the gradient vector [G_x(x), G_y(y)]=[∂

f(x,y)/∂

x, ∂

f(x,y)/∂

y], G_p=√

[G_x²+G_y²], and the orientation θ

_p=arctan(G_y/G_x) for the pixels in the tile bins; and

computing a resultant weighted gradient vector orientation Ω

_k=Σ

_n(G_pθ

_p)/Σ

_nG_p, k=1, 2, . . . ,K, for K tile bins, wherein the set of Ω

_k is the extracted video features 20 representative of the active area of a selected video frame.

13. The method of claim 12, wherein generating multiple type multi-bit signatures comprises:

computing {[G_x(x), G_y(y)], G_p, and θ

_p} for pixels in a rectangular bin of the functional grid having rectangular form and inscribed in the active area of the video frame;

computing a Ω

=Σ

_f(G_pθ

_p)/Σ

_fG_p value for the tiled active area; and

generating one of the multiple type multi-bit signatures by assigning a zero if Ω

_k≦

Ω

for a one if Ω

_k>

Ω

.

14. The method of claim 12, wherein generating multiple type multi-bit signatures comprises:

computing [G_x(x), G_y(y)], G_p, and θ

_p for pixels in a log-polar bin of the functional grid having log-polar form and inscribed in the active area of the video frame;

computing a Ω

=Σ

_f(G_pθ

_p)/Σ

_fG_p value for the tiled active area; and

generating one of the multiple type multi-bit signatures by assigning a zero if Ω

_k≦

Ω

or a one if Ω

_k>

Ω

.