Digital video content fingerprinting based on scale invariant interest region detection with an array of anisotropic filters
View Patent ↗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.
1. A method for interest point descriptor and signature generation used in a video sequence fingerprinting process, the method comprising:
generating interest point parameter vectors for selected frames of a video sequence having a plurality of video frames, wherein each generated vector contains a set (s x , s y , x, y, pixel maximum value), wherein x, y are coordinates of interest point location, s x is a scale parameter in the x direction, and s y is a scale parameter in the y direction representing a scale pair (s xq , s yr ) at the interest point (x,y) location for a Q by R scale neighborhood, wherein Q and R are integers, xqε{x0,x1, . . .x(Q−1)}, yrε{y0,y1, . . .y(R−1), and the pixel maximum value is determined from a sorting of local pixel maximum vales according to their magnitudes;
establishing for each generated vector a rectangular box encompassing a spatial extent, in pixels, of Ns x by Ms y and centered at the interest point (x, y) location assciated with the set (s x , s y , x, y, pixel maximum value), wherein N and M are multiplication factors which determine the size in pixel of a neighborhood around the interest point; and
determining for each generated vector a multi-dimensional descriptor and a multi-dimensional signature based on pixels in the rectangular box, wherein a collection of multi-dimensional descriptors and multi-dimensional signatures for the generated vectors of each selected frame of the video sequence comprises a compact representation of the video sequence used in the video sequence fingerprinting process.
2. The method of claim 1 further comprising:
subdividing the rectangular box into a J by J square area box having J 2 blocks of pixels, wherein j is a preselected integer value greater than one.
3. The method of claim 2 , wherein each block of pixels of the J 2 blocks of pixels is subdivided into a K by K grid of pixels, and pixels contained within each K by K sub-grid area are combined to produce a re-sampled pixel, wherein K is an integer greater than one and K 2 re-sampled pixels are produced for the K by K sub-grid areas.
4. The method of claim 3 further comprising:
computing a resultant gradient vector magnitude for each of the K by K sub-grid areas.
5. The method of claim 3 further comprising:
computing a resultant gradient vector in the x direction for each of the by K by K sub-grid areas.
6. The method of claim 3 further comprising:
computing a resultant gradient vector in the y direction for each of the K by K sub-grid areas.
7. The method of claim 3 further comprising:
computing a resultant sum of gradients in both x and y directions for each of the K by K sub-grid areas.
8. The method of claim 3 further comprising:
generating the multidimensional descriptor and the multi-dimensional signature by combining K 2 sets of four computed values comprising a resultant gradient vector magnitude, a resultant gradient vector in the x direction, a resultant gradient vector in the y direction, and a resultant sum of gradients in both x and y directions.
9. The method of claim 1 further comprising:
storing the collection of multi-dimensional signatures that represent the video sequence in a signature database;
receiving a query comprising a set of query signatures representing an unknown query video sequence;
performing a similarity search between each query signature and signatures stored in the signature database to generate a list of matching candidate signatures; and
determining from the list of matching candidate signatures a most probable matching video sequence that is presented as a search result.
10. A method for interest point descriptor and signature generation used in a video sequence fingerprinting process, the method comprising:
generating, for selected frames of a video sequence having a plurality of video frames, four dimensional (4D) volumes, wherein each 4D volume is configured as an X by Y spatial neighborhood by a Q by R scale neighborhood in which local maximums of image intensity are identified, and X, Y, Q, and R are positive integers;
generating interest point parameter vectors for the identified local maximums in the (X by Y by Q by R) volume, wherein each generated vector contains a set (s x , s y , x, y, pixel maximum value), wherein x, y are coordinates of an interest point location, s x , is a scale parameter in the x direction, and s y is a scale parameter in the y direction representing a scale pair (s xq , s yr ) at the interest point (x,y) location for a Q by R scale neighborhood, wherein xqε{x0,x1, . . . ,x(Q−1)}, yrε{y0,y1, . . . ,y(R−1)}, and the pixel maximum value is determined from a sorting of local pixel maximum values according to their magnitudes;
establishing for each generated vector a rectangular box encompassing a spatial extent, in pixels, of Ns x , by Ms y and centered at the interest point (x, y) location associated with the set (S x , S y , x, y, pixel maximum value), wherein N and M are multiplication factors which determine the size in pixels of a neighborhood around the interest point; and
determining for each generated vector a multi-dimensional signature based on pixels in the rectangular box, wherein a collection of multi dimensional signatures for the generated vectors of each selected frame of the video sequence comprises a compact representation of the video sequence used in the video sequence fingerprinting process.
11. The method of claim 10 further comprising:
subdividing the rectangular box into J by J blocks of pixels and each block of pixels is subdivided into K by K sub-grid areas, and pixels contained within each sub-grid area are combined to produce a re-sampled pixel, wherein K 2 re-sampled pixels are produced for the K by K sub-grid areas for pre-selected J and K integers greater than one.
12. The method of claim 11 further comprising:
generating a single average pixel intensity, representing a re-sampled pixel value, for each sub-grid area by combining intensity values of the pixels contained within each sub-grid area.
13. The method of claim 11 further comprising:
generating M gradient values for each J 2 K by K sub-grid areas to fomi an M*J 2 dimensional descriptor having two or more bits per dimension; and
reducing the two or more bits per dimension of the M*J 2 dimensional descriptor to produce an M*J 2 dimensional signature with a reduced number of bits per dimension.
14. The method of claim 10 further comprising:
storing the collection of multi-dimensional signatures that represent the video sequence in a signature database;
receiving a query comprising a set of query signatures representing an unknown query video sequence;
performing a similarity search between each query signature and signatures stored in the signature database to generate a list of matching candidate signatures; and
determining from the list of matching candidate signatures a most probable matching video sequence that is presented as a search result.
15. A computer readable non-transitory medium storing a computer program which causes a computer system to perform a method for interest point descriptor and signature generation used in a video sequence fingerprinting process, the method comprising:
generating interest point parameter vectors for selected frames of a video sequence having a plurality of video frames, wherein each generated vector contains a set (s x , s y , x, y, pixel maximum value), wherein x, y are coordinates of an interest point location, s x is a scale parameter in the x direction, and s y is a scale parameter in the y direction representing a scale pair (s xq , s yr ) at the interest point (x,y) location for a Q by R scale neighborhood, wherein Q and R are integers, xqε{x0,x1, . . . ,x(Q−1)}, yrε{y0,y1, . . . ,y (R−1)}, and the pixel maximum value is determined from a sorting of local pixel maximum values according to their magnitudes;
establishing for each generated vector a rectangular box encompassing a spatial extent, in pixels, of Ns x by Ms y and centered at the interest point (x, y) location associated with the set (s x , s y , x, y, pixel maximum value), wherein N and M are multiplication factors which determine the size in pixels of a neighborhood around the interest point; and
determining for each generated vector a multi-dimensional descriptor and a multi-dimensional signature based on pixels in the rectangular box, wherein a collection of multi-dimensional descriptors and multi-dimensional signatures for the generated vectors of each selected frame of the video sequence comprises a compact representation of the video sequence used in the video sequence fingerprinting process.
16. The computer-readable non-transitory medium of claim 15 , the method further comprising:
subdividing the rectangular box into J by J blocks of pixels and each block of pixels is subdivided into K by K sub-grid areas, and pixels contained within each sub-grid area are combined to produce a re-sampled pixel, wherein K 2 re-sampled pixels are produced for the K by K sub-grid areas for pre-selected J and K integers greater than one.
17. The computer-readable non-transitory medium of claim 16 , the method further comprising:
generating a single average pixel intensity, representing a re-sampled pixel value, for each sub-grid area by combining intensity values of the pixels contained within each sub-grid area.
18. The computer-readable non-transitory medium of claim 16 , the method further comprising:
generating M gradient values for each J 2 K by K sub-grid areas to form an M*J 2 dimensional descriptor having two or more bits per dimension; and
reducing the two or more bits per dimension of the M*J 2 dimensional descriptor to produce an M*J 2 dimensional signature with a reduced number of bits per dimension.
19. The computer-readable non-transitory medium of claim 15 , the method further comprising:
storing the collection of multi-dimensional signatures that represent the video sequence in a signature database;
receiving a query comprising a set of query signatures representing an unknown query video sequence;
performing a similarity search between each query signature and signatures stored in the signature database to generate a list of matching candidate signatures; and
determining from the list of matching candidate signatures a most probable matching video sequence that is presented as a search result.