Content-based characterization of video frame sequences

• US 20030086496A1
• Filed: 09/25/2001
• Published: 05/08/2003
• Est. Priority Date: 09/25/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Hong-Jiang, Ma, Yufei
• Granted Patent: US 6,965,645 B2
• Time in Patent Office: Days
• US Class Current: 375/240.16
• CPC Class Codes: G06T 7/215 Motion-based segmentation
• 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
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 5/144 Movement detection for video coding H04N19/503; analysis of motion in general G06T7/20
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

A system and process for video characterization that facilitates video classification and retrieval, as well as motion detection, applications. This involves characterizing a video sequence with a gray scale image having pixel levels that reflect the intensity of motion associated with a corresponding region in the sequence of video frames. The intensity of motion is defined using any of three characterizing processes. Namely, a perceived motion energy spectrum (PMES) characterizing process that represents object-based motion intensity over the sequence of frames, a spatio-temporal entropy (STE) characterizing process that represents the intensity of motion based on color variation at each pixel location, a motion vector angle entropy (MVAE) characterizing process which represents the intensity of motion based on the variation of motion vector angles.

Claims

1. A computer-implemented process for characterizing a sequence of video frames, comprising using a computer to perform the following process actions:

deriving from the sequence of video frames a separate value indicative of the intensity of the motion depicted over the sequence in each of a plurality of frame regions;

generating an image wherein each pixel of the image has a level reflecting the value indicating the intensity of motion, relative to all such values, associated with the region containing the corresponding pixel location.

2. The process of claim 1, wherein each region used to partition each frame is macro block sized.

3. The process of claim 1, wherein each region used to partition each frame is pixel sized.

4. The process of claim 1, wherein the process action of deriving a value indicative of the intensity of the motion for each frame region, comprises the actions of:

(a) inputting the next frame in the sequence that has not been input before;

(b) extracting and storing motion vector data from the last-input frame;

(c) computing a motion energy flux that takes into account all the motion vector data of all the inputted frames;

(d) determining whether the motion energy flux exceeds a prescribed flux threshold;

(e) whenever the motion energy flux does not exceed the threshold,

determining whether there are any remaining previously un-inputted frames of the sequence containing motion vector information,

whenever there are such remaining frames, repeating process actions (a) through (e);

(f) whenever the flux threshold is exceeded by the motion energy flux, or whenever there are no remaining previously un-inputted frames of the sequence containing motion vector information, computing a mixture energy value for each of the prescribed frame regions, said mixture energy reflecting both object motion and camera motion components of the motion intensity; and

(g) removing the camera motion component associated with each mixture energy value, thereby leaving just the object motion portion of the mixture energy value, to produce a perceived motion energy (PME) value for each frame region which represents said value indicative of the intensity of the motion in the region.

5. The process of claim 4, further comprising a process action of discarding those motion vectors having magnitudes that are a typically large which is performed prior to performing the process action of computing the motion energy flux.

6. The process of claim 4, wherein the process action of computing the motion energy flux, comprises the actions of:

computing the average motion vector magnitude for all the frame regions in each of the inputted frames;

computing a value representing the average variation of the vector angle associated with the motion vectors of every frame region in each of the frames;

multiplying the average magnitude by a first prescribed weighting factor;

multiplying the average angle variation by a second prescribed weighting factor;

summing the product of the average magnitude and the first prescribed weighting factor with the product of the average angle variation and the second prescribed weighting factor to produce a motion intensity coefficient; and

multiplying the motion intensity coefficient by a normalizing constant, the area of a tracking window and the number of frames input, to produce the motion energy flux.

7. The process of claim 4, wherein the process action of computing a mixture energy value for each of the prescribed frame regions, comprises, for each frame region, the actions of:

sorting the motion vectors associated with the frame regions residing in a tracking volume defined by a tracking window centered on the frame region under consideration and the sequence of inputted frames, in descending order of their magnitude values;

discarding a prescribed number of the sorted motion vectors having magnitude values at the high and low ends of the magnitude range of the sorted vectors;

averaging the magnitude values of the remaining, non-discarded motion vectors;

dividing the averaged magnitude values by the area of the tracking window area and the number of inputted frames and a prescribed truncating threshold to produce a candidate mixture energy value for the frame region under consideration;

determining whether the candidate mixture energy value is less than or equal to 1;

whenever the candidate mixture energy value is less than or equal to 1, assigning the candidate value as the mixture energy value for the frame region under consideration; and

whenever the candidate mixture energy value is greater than 1, assigning a value of 1 as the mixture energy value for the frame region under consideration.

8. The process of claim 7, wherein the process action of removing the camera motion component associated with each mixture energy value to produce a PME value for each frame region, comprises, for each frame region, the actions of:

creating a motion vector angle histogram by assigning to each of a set of angle range bins, the number of the remaining, non-discarded vector angles associated with the frame regions residing within the tracking volume that fall into that bin;

normalizing the motion vector angle histogram by respectively dividing the total number of motion vector angles falling into each bin by the sum of the number of angles falling into all the bins;

respectively multiplying each normalized angle histogram bin value by the logarithm of that value, summing the resulting products and designating the negative value of the sum as the angle entropy value for the frame region under consideration;

dividing the angle entropy value by the logarithm of the total number of bins in the motion vector angle histogram to produce a normalized angle entropy value representing a global motion ratio; and

multiplying the global motion ratio by the normalized mixed energy value associated with the frame region under consideration to produce the PME value for that frame region.

9. The process of claim 4, wherein the process action of generating the image, comprises the actions of:

quantizing the PME values computed for each of frame region to 256 gray levels;

assigning the gray level corresponding to each PME value to its associated frame region to create a perceived motion energy spectrum (PMES) image.

10. The process of claim 1, wherein the frames of the video sequence comprise pixel color data, and wherein the process action of deriving a value indicative of the intensity of the motion for each frame region, comprises the actions of:

(a) inputting the next frame in the sequence that has not been input before;

(b) extracting and storing pixel color data from the last-inputted frame;

(c) computing a motion energy flux that takes into account all the pixel color data of all the inputted frames;

(d) determining whether the motion energy flux exceeds a prescribed flux threshold;

(e) whenever the motion energy flux does not exceed the threshold,

determining whether there are any remaining previously un-inputted frames of the sequence,

whenever there are such remaining frames, repeating process actions (a) through (e);

(f) whenever the flux threshold is exceeded by the motion energy flux, or whenever there are no remaining previously un-inputted frames of the sequence, computing a spatio-temporal energy (STE) value for each pixel location.

11. The process of claim 10, wherein the frames of the video sequence are encoded, and wherein the process action of extracting and storing pixel color data, comprises an action of decoding the last-inputted frame.

12. The process of claim 10, wherein the process action of computing the motion energy flux, comprises the actions of:

computing a value representing the average variation in the pixel color levels of every pixel in each of the inputted frames;

multiplying the average pixel color level variation by the reciprocal of the maximum color variation observed in the pixel color levels among every pixel in each of the inputted frames to produce a motion intensity coefficient; and

multiplying the motion intensity coefficient by a normalizing constant, the area of a tracking window and the number of frames input, to produce the motion energy flux.

13. The process of claim 10, wherein the process action of computing a STE value for each pixel location, comprises, for each pixel location, the actions of:

creating a temporal color histogram by assigning to each of a set of color space range bins, the number of pixels residing within a tracking volume defined by a tracking window centered on the pixel location under consideration and the sequence of inputted frames, which fall into that bin;

normalizing the temporal color histogram by respectively dividing the total number of pixels whose color levels fall into each bin by the sum of the number of pixels whose color levels fall into all the bins;

respectively multiplying each normalized temporal color histogram bin value by the logarithm of that value, summing the resulting products and designating the negative value of the sum as the STE value fro the pixel location under consideration.

14. The process of claim 10, wherein the process action of generating the image, comprises the actions of:

quantizing the STE values computed for each of frame region to 256 gray levels;

assigning the gray level corresponding to each STE value to its associated frame region to create a STE image.

15. The process of claim 1, wherein the process action of deriving a value indicative of the intensity of the motion for each frame region, comprises the actions of:

(a) inputting the next frame in the sequence that has not been input before;

(b) extracting and storing motion vector data from the last-input frame;

(c) computing a motion energy flux that takes into account all the motion vector data of all the inputted frames;

(d) determining whether the motion energy flux exceeds a prescribed flux threshold;

(e) whenever the motion energy flux does not exceed the threshold,

determining whether there are any remaining previously un-inputted frames of the sequence containing motion vector information,

whenever there are such remaining frames, repeating process actions (a) through (e);

(f) whenever the flux threshold is exceeded by the motion energy flux, or whenever there are no remaining previously un-inputted frames of the sequence containing motion vector information, computing a motion vector angle energy (MVAE) value for each frame region.

16. The process of claim 15, wherein the process action of computing the motion energy flux, comprises the actions of:

computing the average motion vector magnitude for all the frame regions in each of the inputted frames;

computing a value representing the average variation of the vector angle associated with the motion vectors of every frame region in each of the frames;

multiplying the average magnitude by a first prescribed weighting factor;

multiplying the average angle variation by a second prescribed weighting factor;

summing the product of the average magnitude and the first prescribed weighting factor with the product of the average angle variation and the second prescribed weighting factor to produce a motion intensity coefficient; and

multiplying the motion intensity coefficient by a normalizing constant, the area of a tracking window and the number of frames input, to produce the motion energy flux.

17. The process of claim 15, wherein the process action of computing a motion vector angle energy value for each frame region location, comprises, for each frame region, the actions of:

creating a motion vector angle histogram by assigning to each of a set of angle range bins, the number of motion vector angles associated with the frame regions residing within the tracking volume defined by a tracking window centered on the frame location under consideration and the sequence of inputted frames, which fall into that bin;

normalizing the motion vector angle histogram by respectively dividing the total number of motion vector angles falling into each bin by the sum of the number of angles falling into all the bins; and

respectively multiplying each normalized angle histogram bin value by the logarithm of that value, summing the resulting products and designating the negative value of the sum as the MVAE value for the frame region under consideration.

18. The process of claim 15, wherein the process action of generating the image, comprises the actions of:

quantizing the MVAE values computed for each of frame region to 256 gray levels;

assigning the gray level corresponding to each MVAE value to its associated frame region to create a MVAE image.

19. A system for finding one or more video shots in a database, each of which comprises a sequence of video frames which depict motion similar to that specified by a user in a user query, comprising:

a general purpose computing device;

the database which is accessible by the computing device and which comprises,

a plurality of characterizing images each of which represents a shot, wherein each characterizing image is an image comprising pixels reflecting the intensity of motion associated with a corresponding region in the sequence of video frames;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

input the user query which comprises a characterizing image that characterizes motion in the same manner as at least some of the characterizing images contained in the database, and

compare the user query image to characterizing images contained in the database that characterize motion in the same manner as the user query image to find characterizing images that exhibit a degree of similarity equaling or exceeding a prescribed minimum similarity threshold.

20. The system of claim 19, further comprising a program module for providing information to the user for accessing the shot corresponding to at least one of any characterizing images contained in the database that were found to exhibit a degree of similarity equaling or exceeding the prescribed minimum similarity threshold.

21. The system of claim 19, wherein the database further comprises a plurality of pointers each of which identifies the location where the shot corresponding to one of the characterizing images contained in the database is stored, and wherein the system further comprises program modules for:

accessing the shot corresponding to at least one of any characterizing images contained in the database that were found to exhibit a degree of similarity equaling or exceeding the prescribed minimum similarity threshold, and

providing each accessed shot to the user.

22. The system of claim 19, wherein the characterizing image associated with the user'"'"'s query comprises a characterizing image that was generated in the same manner as at least some of the characterizing images contained in the database.

23. The system of claim 19, wherein the characterizing image associated with the user'"'"'s query comprises a characterizing image created by the user to simulate the manner in which motion is represented in at least some of the characterizing images contained in the database.

24. The system of claim 19, wherein the program module for comparing the user query image to characterizing images contained in the database, comprises sub-module for:

segmenting the user query image, and each of the characterizing images to which the user query image is to be compared, into m×

n panes;

constructing a normalized energy histogram with m×

n bins for the user query image and each of the characterizing images to which the user query image is to be compared;

normalizing each energy histogram;

assessing the degree of similarity between the user query image and each of the characterizing images to which the user query image is to be compared, said assessing sub-module comprising for each pair of characterizing images compared,

identifying the minimum bin value for each corresponding bin of the energy histograms associated with the pair of characterizing images being compared,

summing the identified minimum bin values,

identifying the maximum bin value for each corresponding bin of the energy histograms associated with the pair of characterizing images being compared,

summing the identified maximum bin values,

dividing the sum of the minimum bin values by the sum of the maximum bin values to produce the a similarity value indicative of the degree of similarity between the pair of characterizing images being compared.

25. The system of claim 24, wherein the sub-module for constructing a normalized energy histogram, comprises, for each characterizing image involved, sub-modules for:

averaging the pixel values residing within in each pane of the characterizing image; and

assigning to each of the histogram bins, the number of averaged values that fall into the value range associated with that bin.

26. The system of claim 25, wherein the sub-module for normalizing each energy histogram, comprises sub-modules for:

respectively dividing the total number of averaged pixel values falling into each bin by the sum of the number of such values falling into all the bins.

27. The system of claim 24, wherein the sub-modules for segmenting each of the characterizing images to which the user query image is to be compared, constructing a normalized energy histogram for each of the characterizing images to which the user query image is to be compared, and normalizing the energy histogram associated with each of the characterizing images to which the user query image is to be compared, are executed before the user query image is input and are made accessible through the database.

28. The system of claim 19, wherein the program module for comparing the user query image to characterizing images contained in the database, comprises sub-module for:

identifying regions of high energy in the user query image, and each of the characterizing images to which the user query image is to be compared; and

assessing the degree of similarity between the user query image and each of the characterizing images to which the user query image is to be compared based on a comparison of at least one of (i) the size, (ii) shape, (iii) location, and (iv) energy distribution of the identified high energy regions between the pair of characterizing images being compared to produce the a similarity value indicative of the degree of similarity between each pair of characterizing images compared.

29. The system of claim 28, wherein the sub-module for identifying regions of high energy in each of the characterizing images to which the user query image is to be compared, is executed before the user query image is input and are made accessible through the database.

30. A system for detecting motion in a scene as depicted in a sequence of video frames of the scene, comprising:

a general purpose computing device; and

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

derive from the sequence of video frames a separate value indicative of the intensity of the motion depicted over the sequence at each pixel location associated with the frames,

generate a gray scale image having the same resolution as the video frames, wherein each pixel of the gray scale image has a gray scale level reflecting a value indicating the intensity of motion, relative to all such values, depicted over the sequence at each pixel location associated with the frames,

filter the gray scale image to reduce high frequency noise,

subject the filtered gray scale image to a morphological closing operation followed by a morphological opening operation to respectively consolidate regions of motion in the gray scale image and to eliminate any extraneous region where an indication of motion is caused by noise, and

provide information that motion has been detected in the shot under consideration whenever a region of motion remains in the filtered and morphologically operated image.

31. The system of claim 30, wherein the program module for filtering the gray scale image, comprises a sub-module for filtering the gray scale image using a Gaussian filtering operation.

32. The system of claim 30, further comprising program modules for:

subjecting the filtered and morphologically operated gray scale image to a region growing operation to establish a size for each region of motion depicted in the image,

identifying the location of each region of motion using a separate bounding box for each region, wherein each bounding box encompasses its associated region of motion.

33. The system of claim 32, wherein the program module for providing information that motion has been detected in the shot under consideration, comprises a sub-module for providing to a user a frame of the video sequence which depicts an object corresponding to at least one of the regions of motion, wherein the bounding box associated with the at least one region of motion is superimposed on the frame to highlight the location of the object whose motion was detected.

34. The system of claim 30, wherein the sequence of frames is part of a continuous video monitoring the scene and represents the frames within a sliding temporal window which adds each new frame generated and simultaneously deletes the oldest frame each time a new frame is added to create a new sequence of frames, and wherein the program modules of the computer program are executed each time a new sequence of frames is created.

35. A system for finding one or more video shots in a database, each of which comprises a sequence of video frames which depict motion similar to that specified by a user in a user query, comprising:

a general purpose computing device;

the database which is accessible by the computing device and which comprises,

a plurality of characterizing images each of which represents a shot, wherein each characterizing image is a gray scale image comprising pixels which each have a gray scale level reflecting the intensity of motion associated with a corresponding region in the sequence of video frames;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

input the user query which comprises a first type of said characterizing images representing a video shot and the video shot itself,

identify regions of high energy in the user query image,

generate a new characterizing image from just those portions of the frames of the user input video shot corresponding to the identified regions of high energy in the user query image, wherein the new characterizing image of a second type of said characterizing images,

compare the new characterizing image to characterizing images contained in the database that are also the second type of said characterizing images to find characterizing images that exhibit a degree of similarity equaling or exceeding a prescribed minimum similarity threshold, and

provide information for accessing the shot corresponding to at least one of any characterizing images contained in the database that were found to exhibit a degree of similarity equaling or exceeding the prescribed minimum similarity threshold.

36. A system for finding one or more video shots in a database, each of which comprises a sequence of video frames which depict motion similar to that specified by a user in a user query, comprising:

a general purpose computing device;

the database which is accessible by the computing device and which comprises,

a plurality of characterizing images each of which represents a shot, wherein each characterizing image is an image comprising pixels which each have a level reflecting the intensity of motion associated with a corresponding region in the sequence of video frames;

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

input the user query which comprises a first type of said characterizing images and which characterizes motion in the same manner as at least some of the characterizing images contained in the database,

input a video shot from which the user query image was generated,

compare the user query image to characterizing images contained in the database that characterize motion in the same manner as the user query image to find characterizing images that exhibit a degree of similarity equaling or exceeding a prescribed minimum similarity threshold associated with the first type of characterizing images,

generate a new characterizing image from the user input video shot, wherein the new characterizing image of a second type of said characterizing images,

respectively generate a characterizing image of the second type from each of the video shots associated with the characterizing images of the first type that exhibited a degree of similarity equaling or exceeding the prescribed minimum similarity threshold,

compare the new characterizing image to the characterizing images generated from each of the video shots associated with the characterizing images of the first type that exhibited a degree of similarity equaling or exceeding the prescribed minimum similarity threshold associated with the first type of characterizing images, to find which of the images exhibit a degree of similarity equaling or exceeding the prescribed minimum similarity threshold associated with the second type of characterizing images, and

provide information for accessing the shot corresponding to at least one of any the characterizing images of the second type that were found to exhibit a degree of similarity equaling or exceeding the prescribed minimum similarity threshold associated with the second type of characterizing images.

37. The system of claim 36, wherein the program module for respectively generating a characterizing image of the second type from each of the video shots associated with the characterizing images of the first type that exhibited a degree of similarity equaling or exceeding the prescribed minimum similarity threshold, is accomplished before the user query image is input by generating a characterizing image of the second type from the video shots associated with every characterizing image of the first type in the database.

38. A computer-readable medium having computer-executable instructions for characterizing at least a portion of a shot that is made up of a sequence of video frames, said computer-executable instructions comprising:

deriving from the sequence of video frames a separate value indicative of the intensity of the motion depicted over the sequence in each of a plurality of frame regions;

generating a gray scale image comprising pixels which each have a gray scale level reflecting the intensity of motion associated with a corresponding region in the sequence of video frames.

39. The computer-readable medium of claim 38, wherein at least some of the frames of the shot comprise motion vector data, and wherein the instruction for deriving a value indicative of the intensity of the motion for each frame region, comprises sub-modules for:

inputting a prescribed number of frames, which comprise motion vector data, in shot sequence order;

extracting and storing the motion vector data from the inputted frames;

discarding those motion vectors having magnitudes that are a typically large;

computing a mixture energy value for each of the prescribed frame regions, said mixture energy reflecting both object motion and camera motion components of the motion intensity; and

removing the camera motion component associated with each mixture energy value, thereby leaving just the object motion portion of the mixture energy value, to produce a perceived motion energy (PME) value for each frame region which represents said value indicative of the intensity of the motion in the region.

40. The computer-readable medium of claim 38, wherein the frames of the shot comprise pixel color data, and wherein the instruction for deriving a value indicative of the intensity of the motion for each frame region, comprises sub-modules for:

inputting a prescribed number of frames in shot sequence order;

extracting and storing pixel color data from the inputted frames;

computing a spatio-temporal energy (STE) value for each pixel location.

41. The computer-readable medium of claim 38, wherein at least some of the frames of the shot comprise motion vector data, and wherein the instruction for deriving a value indicative of the intensity of the motion for each frame region, comprises sub-modules for:

inputting a prescribed number of frames, which comprise motion vector data, in shot sequence order;

extracting and storing the motion vector data from the inputted frames;

computing a motion vector angle energy value for each frame region.

42. The computer-readable medium of claim 38, wherein the frames of the shot comprise pixel gray level data, and wherein the instruction for deriving a value indicative of the intensity of the motion for each frame region, comprises sub-modules for:

(a) inputting the next frame in the sequence that has not been input before;

(b) extracting and storing pixel gray level data from the last-inputted frame;

(c) computing a motion energy flux that takes into account all the pixel gray level data of all the inputted frames;

(d) determining whether the motion energy flux exceeds a prescribed flux threshold;

(e) whenever the motion energy flux does not exceed the threshold,

determining whether there are any remaining previously un-inputted frames of the shot,

whenever there are such remaining frames, repeating process actions (a) through (e);

(f) whenever the flux threshold is exceeded by the motion energy flux, or whenever there are no remaining previously un-inputted frames of the shot, computing a spatio-temporal energy (STE) value for each pixel location.

43. The computer-readable medium of claim 42, wherein the frames of the shot are encoded, and wherein the instruction for extracting and storing pixel gray level data, comprises a sub-module for decoding the last-inputted frame.

44. The computer-readable medium of claim 42, wherein the instruction for computing the motion energy flux, comprises sub-modules for:

computing a value representing the average variation in the pixel gray level values of every pixel in each of the inputted frames;

multiplying the average pixel gray level value variation by a prescribed gray level variation weighting factor to produce a motion intensity coefficient; and

multiplying the motion intensity coefficient by a normalizing constant, the area of a tracking window and the number of frames input, to produce the motion energy flux.

45. The computer-readable medium of claim 42, wherein the instruction for computing a STE value for each pixel location, comprises, for each pixel location, sub-modules for:

creating a temporal gray level histogram by assigning to each of a set of gray level range bins, the number of pixels residing within a tracking volume defined by a tracking window centered on the pixel location under consideration and the sequence of inputted frames, which fall into that bin;

normalizing the temporal gray level histogram by respectively dividing the total number of pixels whose gray level values fall into each bin by the sum of the number of pixels whose gray level values fall into all the bins;

respectively multiplying each normalized temporal gray level histogram bin value by the logarithm of that value, summing the resulting products and designating the negative value of the sum as the STE value for the pixel location under consideration.

46. The computer-readable medium of claim 42, wherein the instruction for generating the gray scale image, comprises sub-modules for:

quantizing the STE values computed for each of frame region to 256 gray levels;

assigning the gray level corresponding to each STE value to its associated frame region to create a STE image.