Methods and apparatus for providing a scalable identification of digital video sequences

• US 8,229,227 B2
• Filed: 06/18/2008
• Issued: 07/24/2012
• Est. Priority Date: 06/18/2007
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Zeitera LLC
• Inventors: Stojancic, Mihailo M., Pereira, Jose Pio, Merchant, Shashank
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Park, Edward
• Application Number:
  US12/141,163
• Publication Number:
  US 20080310731A1
• Time in Patent Office: 1,497 Days
• Field of Search: 382/181, 382/190, 382/231
• US Class Current: 382/190
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44

Abstract

Scaleable video sequence processing with various filtering rules is applied to extract dominant features, and generate unique set of signatures based on video content. Video sequence structuring and subsequent video sequence characterization is performed by tracking statistical changes in the content of a succession of video frames and selecting suitable frames for further treatment by region based intra-frame segmentation and contour tracing and description. Compact representative signatures are generated on the video sequence structural level as well as on the selected video frame level, 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 video features of the selected video frames;

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

weighting pixel bins with multiple parameters dependent on pixel characteristics with respect to the surrounding area laid out as a log-polar functional space inscribed into the determined active regions of the selected video frames to form histogram bins for all video frame contours;

normalizing a pixel count for each histogram bin according to the weights and according to histogram bin area; and

applying a threshold function to generate a binary signature with a number of bits corresponding to the number of bins.

2. The method of claim 1 wherein the step of 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 the frames.

3. The method of claim 1 wherein the step of generating multi-dimensional content based signatures comprises:

counting contour pixels falling into selected bins in a log-polar space based on a shape context description; and

applying a threshold to assign a 0 or 1 to each bin in the selected collection of bins.

4. The method of claim 1 further comprising:

segmenting selected video frames utilizing selected active frame areas into a plurality of regions, each region delineated by the video frame contours; and

inscribing a log-polar functional space into the plurality of regions to form histogram bins that cover the video frame contours.

5. The method of claim 1 further comprising:

forming a content based video database to hold the multi-dimensional content based signatures.

6. 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 video features of the selected video frames;

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

weighting pixel bins with multiple parameters dependent on pixel characteristics with respect to the surrounding area laid out as a rectangular functional space inscribed into an entire video frame to form histogram bins for all video frame contours;

normalizing a pixel count for each histogram bin according to the weights and according to histogram bin area; and

applying a threshold function to generate a binary signature with a number of bits corresponding to the number of bins.

7. The method of claim 6 wherein the step of selecting a set of video frames comprises:

generating a temporal statistical function for a video sequence based on mean absolute value difference (MAD) parameters computed for corresponding pixels in two successive video sequence frames.

8. The method of claim 7 further comprising:

filtering the temporal statistic function corresponding to a normalized array of the MAD parameter values with a median filter to suppress excessive peaks due to abrupt scene changes and to suppress very low values due to undesired video frame repetitions.

9. The method of claim 6 further comprising:

determining active regions in frames of a query video sequence;

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

extracting query video features of the selected query video frames;

generating multi-dimensional content based signatures based on the extracted query video features that identify the query video sequence; and

searching the video database for a match between the query video multi-dimensional content based signatures and signatures stored in the video database.

10. The method of claim 6 further comprising:

segmenting selected video frames utilizing selected active frame areas into a plurality of regions, each region delineated by the video frame contours; and

inscribing a rectangular functional space into the plurality of regions to form histogram bins that cover the video frame contours.

11. The method of claim 6 further comprising:

forming a content based video database to hold the multi-dimensional content based signatures.

12. 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 video features of the selected video frames;

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

generating histograms containing a count of contour pixel gradient magnitude for pixels of selected video frame contours;

applying a histogram average bin count as a threshold parameter to generate a binary signature; and

generating the binary signature by comparing each histogram bin value with the threshold parameter, assigning a zero value depending on whether a histogram bin count is less than the threshold parameter, assigning a one value depending on whether a histogram bin count is greater than the threshold parameter, a number of signature bits corresponding to the number of bins of the histogram.

13. The method of claim 12 wherein the step of extracting video features comprises:

segmenting the active video frame into areas of similar light intensity and color;

determining the perimeter of the segmented areas which represent closed contours; and

tracing the contours to produce a vector of contiguous spatial coordinates (x, y) for each pixel on the contour.

14. The method of claim 12 further comprising:

segmenting selected video frames utilizing selected active frame areas into a plurality of regions, each region delineated by the selected video frame contours; and

forming a content based video database to hold the multi-dimensional content based signatures.

15. 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 video features of the selected video frames;

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

generating histograms containing a count of contour pixel gradient orientation values for pixels of all selected video frame contours;

applying a histogram average bin count as a threshold parameter to generate a binary signature; and

generating the binary signature by comparing each histogram bin value with the threshold parameter, assigning a zero value depending on whether a histogram bin count is less than the threshold parameter, assigning a one value depending on whether a histogram bin count is greater than the threshold parameter, a number of signature bits corresponding to the number of bins of the histogram.

16. The method of claim 15 wherein the step of generating multi-dimensional content based signatures comprises:

deriving a T-bit signature for each video frame partition and each time window with K frames by comparing MN_qi=Σ

fq(n)/F values for the particular time window to the corresponding partition values MPN_pk, and a 0 or 1 assigned depending whether the particular MN_qi, value is greater than or less than the corresponding MPN_pk.

17. The method of claim 16 further comprising:

computing a collection of S T-bit values for each video frame partition and a κ

-frame time window; and

combining the computed collection of S T-bits into an N-bit signature to be attached to the selected frame κ

for this window.

18. The method of claim 15 wherein the step of generating multi-dimensional content based signatures comprises:

deriving a T-bit signature for the full video frame and each time window with K frames based on function f₀(n).

19. The method of claim 15 further comprising:

segmenting selected video frames utilizing selected active frame areas into a plurality of regions, each region delineated by the selected video frame contours; and

forming a content based video database to hold the multi-dimensional content based signatures.