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

• US 20120207402A1
• Filed: 04/25/2012
• Published: 08/16/2012
• Est. Priority Date: 05/27/2009
• Status: Active Grant

• Current Assignee: Roku, Inc.
• Original Assignee: Zeitera LLC
• Inventors: Stojancic, Mihailo, Ramanathan, Prashant, Wendt, Peter, Pereira, Jose Pio
• Granted Patent: US 8,781,245 B2
• Time in Patent Office: Days
• US Class Current: 382/260
• 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 of applying an array of anisotropic filters for image scale-space analysis, the method comprising:

forming an array of elliptic-shaped anisotropic filters with a first scale parameter in the x direction (s_x) and a second scale parameter in the y direction (s_y) as scale parameters (s_x, s_y), wherein the s_x and the s_y scale parameters are separately varied to provide accurate region characterization;

analyzing scale space for a selected frame by the array of elliptic-shaped anisotropic filters of finite spatial support corresponding to selected different values of the (s_x) and (s_y) scale parameters;

computing a Hessian determinant response image for each elliptic-shaped anisotropic filter of finite spatial support corresponding to selected pairs (s_x, s_y) of scale parameters; and

determining a set of local maxima in contiguous 4-dimensional scale-space volumes of the Hessian determinant response images with coordinates (x, y, s_x, s_y).

2. The method of claim 1, wherein the array of elliptic-shaped anisotropic filters with a first scale parameter in the x direction (s_x) and a second scale parameter in the y direction (s_y) is an array of discretized rectangular-shaped anisotropic second order partial derivative Gaussian filters with finite spatial support according to the (s_x, s_y) scale parameters.

3. The method of claim 2, wherein the scale space for a selected frame is analyzed by the array of discretized rectangular-shaped anisotropic second order partial derivative Gaussian filters of finite spatial support corresponding to different values of the (s_x) and (s_y) scale parameters.

4. The method of claim 2 further comprising:

convolving a region of pixels in a surrounding neighborhood of an initial interest point with the array of discretized rectangular-shaped anisotropic second order partial derivative Gaussian filters with finite spatial support according to the (s_x, s_y) scale parameters to produce component images for the Hessian matrix.

5. The method of claim 2 further comprising:

computing a Hessian determinant response image for each of the discretized rectangular-shaped anisotropic second order partial derivative Gaussian filter according to the (s_x, s_y) scale parameters.

6. The method of claim 5 further comprising:

determining a set of local maxima in contiguous 4-dimensional scale-space volumes of the Hessian determinant response images with coordinates (x, y, s_x, s_y), wherein the set of local maxima is further sorted in according to a specified magnitude threshold to determine a new set of local maxima that represents a set of non-interpolated interest points.

7. The method of claim 6 further comprising:

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

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

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

applying an array of discretized rectangular-shaped anisotropic filters of finite spatial support corresponding to different values of a first scale parameter in the x direction (s_x) and a second scale parameter in the y direction (s_y) to interest points in a selected frame;

forming a Hessian determinant response image with pixels representing a determinant of a Hessian matrix for each anisotropic filter of the array of discretized rectangular-shaped anisotropic filters with the finite spatial support corresponding to the s_x and s_y scale values;

interpolating a subset of non-interpolated local maxima that exceed a specified magnitude threshold to generate interpolated local maxima values, wherein the non-interpolated local maxima are computed for each spatial-scale 4-dimensional pixel volume constructed at equidistant spatial locations in the Hessian determinant response image; and

generating a multi-dimensional descriptor in a region centered at an (x,y) refined interest point, the region having a rectangular spatial extent proportional to the s_x and s_y scale values, wherein the s_x and s_y values and the x and y position values are based on the interpolated local maxima values.

10. The method of claim 9 further comprising:

drawing a rectangular box encompassing Ns_x by Ms_y pixels and centered at a refined interest point (x, y) location, wherein N and M are multiplication factors which determine a neighborhood size around the refined interest point; and

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

11. The method of claim 10 further comprising:

generating a k by k grid in the rectangular box and a j by j re-sampled sub-region containing j² interpolated pixels for each cell of the k by k grid.

12. The method of claim 11 further comprising:

generating a horizontal gradient Gx and a vertical gradient Gy based on a partial derivative of each pixel in the j by j re-sampled sub-region; and

generating a plurality of computed gradient values for each sub-region to be concatenated as the multi-dimensional descriptor.

13. The method of claim 11 further comprising:

generating the multidimensional descriptor by combining j by j 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.

14. The method of claim 9 further comprising:

generating, from the multidimensional descriptor, a multidimensional signature with a reduced number of bits per dimension.

15. A computer readable non-transitory 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:

applying an array of discretized rectangular-shaped anisotropic filters of finite spatial support corresponding to different values of a first scale parameter in the x direction (s_x) and a second scale parameter in the y direction (s_y) to interest points in a selected frame;

forming a Hessian determinant response image with pixels representing a determinant of a Hessian matrix for each anisotropic filter of the array of discretized rectangular-shaped anisotropic filters with the finite spatial support corresponding to the s_x and s_y scale values;

interpolating a subset of non-interpolated local maxima that exceed a specified magnitude threshold to generate interpolated local maxima values, wherein the non-interpolated local maxima are computed for each spatial-scale 4-dimensional pixel volume constructed at equidistant spatial locations in the Hessian determinant response image; and

generating a multi-dimensional descriptor in a region centered at an (x,y) refined interest point, the region having a rectangular spatial extent proportional to the s_x and s_y scale values, wherein the s_x and s_y values and the x and y position values are based on the interpolated local maxima values.

16. The computer readable non-transitory medium of claim 15 further comprising:

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.

17. The computer readable non-transitory medium of claim 15 further comprising:

drawing a rectangular box encompassing Ns_x by Ms_y pixels and centered at a refined interest point (x, y) location, wherein N and M are multiplication factors which determine a neighborhood size around the refined interest point; and

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

18. The computer readable non-transitory medium of claim 17 further comprising:

generating a k by k grid in the rectangular box and a j by j re-sampled sub-region containing j² interpolated pixels for each cell of the k by k grid.

19. The computer readable non-transitory medium of claim 18 further comprising:

generating a horizontal gradient Gx and a vertical gradient Gy based on a partial derivative of each pixel in the j by j re-sampled sub-region; and

generating a plurality of computed gradient values for each sub-region to be concatenated as the multi-dimensional descriptor.

20. The computer readable non-transitory medium of claim 18 further comprising:

generating the multidimensional descriptor by combining j by j 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.