Digital Video Content Fingerprinting Based on Scale Invariant Interest Region Detection with an Array of Anisotropic Filters

• US 20100303338A1
• Filed: 11/05/2009
• Published: 12/02/2010
• Est. Priority Date: 05/27/2009
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Zeitera LLC
• Inventors: Wendt, Peter, Stojancic, Mihailo, Pereira, Jose Pio, Ramanathan, Prashant
• Granted Patent: US 8,189,945 B2
• Time in Patent Office: Days
• US Class Current: 382/154
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: G06F 16/7854 using shape G06F16/7837 takes precedence
• CPC Class Codes: G06F 16/7864 using domain-transform features, e.g. DCT or wavelet transform coefficients
• CPC Class Codes: G06F 2218/02 Preprocessing
• CPC Class Codes: G06F 2218/10 by analysing the shape of a waveform, e.g. extracting parameters relating to peaks
• CPC Class Codes: G06V 10/464 using a plurality of salient features, e.g. bag-of-words [BoW] representations
• 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 5/14 Picture signal circuitry for video frequency region cameras or camera modules comprising electronic image sensors, or control thereof H04N23/00

Abstract

Video sequence processing is described with various filtering rules applied to extract dominant features for content based video sequence identification. Active regions are determined in video frames of a video sequence. Video frames are selected in response to temporal statistical characteristics of the determined active regions. A two pass analysis is used to detect a set of initial interest points and interest regions in the selected video frames to reduce the effective area of images that are refined by complex filters that provide accurate region characterizations resistant to image distortion for identification of the video frames in the video sequence. Extracted features and descriptors are robust with respect to image scaling, aspect ratio change, rotation, camera viewpoint change, illumination and contrast change, video compression/decompression artifacts and noise. Compact, representative signatures are generated for video sequences to provide effective query video matching and retrieval in a large video database.

Claims

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

determining active regions in video frames of a video sequence;

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

using a two pass analysis to detect a set of initial interest points and interest regions in the selected video frames to reduce the effective area of images that are refined by complex filters that provide accurate region characterizations resistant to image distortion for identification of the video frames in the video sequence.

2. The method of claim 1 further comprises:

applying bi-level filters in the selected video frames in a first pass analysis to detect the set of initial interest points and interest regions; and

applying the complex filters to regions of pixels around the initial interest points in a second pass analysis to refine interest point spatial position and determine precise scale parameters.

3. The method of claim 1 further comprises:

applying bi-level filters of various spatial support on a selected video frame to produce multiple filter response images with the same spatial support as the original video frame;

constructing a set of contiguous rectangular spatial areas on filter response images derived for the selected video frame;

constructing a corresponding set of 3-dimensional scale-space pixel volumes for each of the contiguous rectangular spatial areas;

determining a set of local filter response maxima at spatial-scale 3-dimensional pixel volumes; and

sorting local filter response maxima at spatial-scale 3-dimensional pixel volumes, and selecting a set of local filter response maxima with their spatial (x, y) coordinates to represents the initial interest points of a first pass of selected video frame analysis.

4. The method of claim 1 further comprises:

generating Laplacian of Gaussian second order partial derivative bi-level filters.

5. The method of claim 4 wherein the Laplacian of Gaussian second order partial derivative bi-level filters are bi-level octagonal shaped filters or star-shaped filters that approximate circular filters.

6. The method of claim 4 further comprises:

convolving the Laplacian of Gaussian second order partial derivative bi-level filters of various sizes with one of the selected video frames to form bi-level filter response images for a specified set of scales.

7. The method of claim 6 wherein a local maximum value is determined for each 3-dimensional image volume in a set of contiguous 3-dimensional image volumes associated with pixels of bi-level octagonal-shaped or star-shaped filter response images.

8. The method of claim 7, wherein local maximum values are sorted according to their magnitude, and a subset of maxima are selected to represent the set of initial interest points.

9. The method of claim 1 further comprises:

computing a set of Hessian determinant response images for each interest region formed around an initial interest point detected in a first pass analysis to determine a precise scale for the initial interest point.

10. The methods of claim 9 further comprises:

generating a convolution of an array of sampled anisotropic filters of finite spatial support, representing an array of scales (s_x, s_y), with rectangular regions around the initial interest points determined in a first pass processing of a selected video frame, wherein the generated convolution result is resistant to image distortions.

11. The methods of claim 10 wherein the sampled anisotropic filters comprise sampled elliptic-shaped Gaussian second order partial derivative filters with finite rectangular spatial support directly proportional to (s_x, s_y) scales.

12. The method of claim 9 further comprises:

generating of a set of second order partial derivative images L_xx, L_yy, L_xy, L_yx computed along x and y coordinates to determine the set of Hessian determinant response images.

13. The method of claim 9 further comprises:

generating a convolution of an image I(z) with sampled Gaussian second order partial derivative filters of finite, rectangular spatial support.

14. The method of claim 10 further comprises:

forming a Hessian matrix and an image with pixels representing a determinant of the Hessian matrix for each sampled anisotropic filter from the array of sampled anisotropic filters with various (s_x, s_y) scales.

15. The method of claim 14 further comprises:

determining non-interpolated refined interest points based on non-interpolated local maxima computed for each combined spatial-scale 4-dimensional pixel volume constructed at equidistant spatial locations in Hessian determinant response images.

16. The method of claim 15 wherein the non-interpolated local maxima are sorted and a subset of the non-interpolated local maxima are selected to represent non-interpolated refined interest points.

17. The method of claim 16 further comprises:

interpolating the subset of non-interpolated local maxima in scale and image space domains to generate interpolated local maxima values.

18. The method of claim 17 further comprises:

generating interest point parameter vectors with (s_x s_y, x, y, peak polarity) components based on the interpolated local maxima values.

19. A method for interest point descriptor and signature generation, the method comprising:

generating refined interest point parameter vectors, wherein each vector contains a set (s_x, s_y, x, y, peak polarity);

drawing a rectangular box encompassing Ns_x×

Ms_y pixels and centered at an interest point (x, y) location associated with a set (s_x, s_y, x, y, peak polarity); and

determining a multi-dimensional descriptor and a multi-dimensional signature based on pixels in the rectangular box.

20. The method of claim 19 further comprising:

re-sampling the rectangular box into a J×

J pixel square area box.

21. The method of claim 20 wherein a gradient vector is computed for each pixel of the J×

J box.

22. The method of claim 20 wherein the J×

J square-area box is comprised of a set of K×

K re-sampled square area sub-boxes.

23. The method of claim 22 further comprises:

computing a resultant gradient vector magnitude for each of the K×

K sub-boxes.

24. The method of claim 22 further comprises:

computing a resultant gradient vector in spatial x direction for each of the K×

K sub-boxes.

25. The method of claim 22 further comprises:

computing a resultant gradient vector in spatial y direction for each of the K×

K sub-boxes.

26. The method of claim 22 further comprises:

computing a resultant sum of gradients in both x and y directions for each of the K×

K sub-boxes.

27. The method of claim 19 further comprises:

generating the multidimensional descriptor and the multi-dimensional signature by combining K×

K sets of four computed values comprising a resultant gradient vector magnitude, a resultant gradient vector in spatial x direction, a resultant gradient vector in spatial y direction, and a resultant sum of gradients in both x and y directions.

28. A method of applying an array of anisotropic filters for image scale-space analysis, the method comprising:

forming an array of elliptic-shaped, sampled anisotropic second order partial derivative Gaussian filters with (s_x, s_y) scale parameters;

forming an array of rectangular-shaped, sampled anisotropic second order partial derivative Gaussian filters with finite spatial support with (s_x, s_y) scale parameters to approximate the elliptic-shaped sampled anisotropic second order partial derivative Gaussian filters;

analyzing scale space for a selected frame by the array of rectangular sampled anisotropic second order partial derivative Gaussian filters of finite spatial support corresponding to different (s_x, s_y) scales; and

convolving a region of pixels in a surrounding neighborhood of an initial interest point with the array of rectangular sampled anisotropic second order partial derivative Gaussian filters to produce a result that is resistant to image distortion.

29. The method of claim 28 further comprises:

computing a Hessian determinant and a Hessian determinant response image for each sampled anisotropic second order partial derivative Gaussian filter with scale parameters (s_x, s_y).

30. The method of claim 29 further comprises:

determining a set of local maxima in contiguous 4-dimensional scale-space volumes of the Hessian determinant response images, wherein the set of local maxima is further sorted in magnitude and a new set of local maxima is selected that represents a set of non-interpolated interest points.

31. The method of claim 30 further comprises:

interpolating the selected set of local maxima for a combined spatial-scale 4-dimensional pixel volume, constructed for equidistant spatial locations of the Hessian determinant response image, to produce a final set of spatial positions and scales of refined interest points.

32. The method of claim 31 wherein the refined interest points are described with a 5-tuple (s_x, s_y, x, y, peak polarity).

33. A computer readable medium storing a computer program which causes a computer system to perform a method of applying an array of anisotropic filters for image scale-space analysis, the method comprising:

forming an array of elliptic-shaped, sampled anisotropic second order partial derivative Gaussian filters with (s_x, s_y) scale parameters;

forming an array of rectangular-shaped, sampled anisotropic second order partial derivative Gaussian filters with finite spatial support with (s_x, s_y) scale parameters to approximate the elliptic-shaped sampled anisotropic second order partial derivative Gaussian filters;

analyzing scale space for a selected frame by the array of rectangular sampled anisotropic second order partial derivative Gaussian filters of finite spatial support corresponding to different (s_x, s_y) scales; and

convolving a region of pixels in a surrounding neighborhood of an initial interest point with the array of rectangular sampled anisotropic second order partial derivative Gaussian filters to produce a result that is resistant to image distortion.

34. The computer readable medium of claim 33 further comprises:

applying bi-level filters of various spatial support on a selected video frame to produce multiple filter response images with the same spatial support as the original video frame;

constructing a set of contiguous rectangular spatial areas on filter response images derived for the selected video frame;

constructing a corresponding set of 3-dimensional scale-space pixel volumes for each of the contiguous rectangular spatial areas; and

determining a set of local filter response maxima at spatial-scale 3-dimensional pixel volumes, wherein the set of local filter response maxima with their spatial (x, y) coordinates represents initial interest points of a first pass of selected video frame analysis.