Methods and apparatuses for video segmentation, classification, and retrieval using image class statistical models

• US 6,751,354 B2
• Filed: 03/11/1999
• Issued: 06/15/2004
• Est. Priority Date: 03/11/1999
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Girgensohn, Andreas, Wilcox, Lynn, Foote, Jonathan T.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): Kassa, Yosef
• Application Number:
  US09/266,637
• Publication Number:
  US 20020028021A1
• Time in Patent Office: 1,923 Days
• Field of Search: 382/224, 382/226, 382/236, 382/238, 382/282, 382/218, 382/277, 382/278, 382/156, 382/190, 382/159, 382/160, 382/103, 382/209, 382/205, 382/171, 382/217, 382/219, 382/220, 706/25, 11/2
• US Class Current: 382/224
• CPC Class Codes: G06F 18/2415 based on parametric or probabilistic models, e.g. based on likelihood ratio or false acceptance rate versus a false rejection rate
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/85 Markov-related models; Markov random fields
• CPC Class Codes: G06V 20/48 Matching video sequences

Abstract

Techniques for classifying video frames using statistical models of transform coefficients are disclosed. After optionally being decimated in time and space, image frames are transformed using a discrete cosine transform or Hadamard transform. The methods disclosed model image composition and operate on grayscale images. The resulting transform matrices are reduced using truncation, principal component analysis, or linear discriminant analysis to produce feature vectors. Feature vectors of training images for image classes are used to compute image class statistical models. Once image class statistical models are derived, individual frames are classified by the maximum likelihood resulting from the image class statistical models. Thus, the probabilities that a feature vector derived from a frame would be produced from each of the image class statistical models are computed. The frame is classified into the image class corresponding to the image class statistical model which produced the highest probability for the feature vector derived from the frame. Optionally, frame sequence information is taken into account by applying a hidden Markov model to represent image class transitions from the previous frame to the current frame. After computing all class probabilities for all frames in the video or sequence of frames using the image class statistical models and the image class transition probabilities, the final class is selected as having the maximum likelihood. Previous frames are selected in reverse order based upon their likelihood given determined current states.

Claims

1. A method for selecting a d-entry feature set for video classification from t training images, each of the t training images having v rows and h columns of sub-images, the method comprising the steps of:

computing t transform matrices by performing a transform on each of the t training images, each transform matrix having v rows and h columns of coefficient positions, each coefficient position having a transform coefficient associated with it; and

selecting d coefficient positions as the d-entry feature set based upon the transform coefficients in the t transform matrices, the number of d coefficient positions being less than the number of total coefficient positions in the v rows and h columns.

2. A method as in claim 1,

wherein the d coefficient positions are selected by truncation.

3. A method as in claim 1,

wherein the d coefficient positions are selected by principal component analysis.

4. A method as in claim 1,

wherein the d coefficient positions are selected by linear discriminant analysis.

5. A method as in claim 1,

wherein the transform comprises a discrete cosine transform.

6. A method as in claim 1,

wherein the transform comprises a Hadamard transform.

7. A method for selecting a d-entry feature set for video classification from t training images, each of the t training images having v rows and h columns of sub-images, the method comprising the steps of:

computing t transform matrices by performing a transform on each of the t training images, each transform matrix having v rows and h columns of coefficient positions, each coefficient position having a transform coefficient associated with it;

selecting d coefficient positions as the d-entry feature set based upon the transform coefficients in the t transform matrices;

computing a variance matrix having v rows and h columns of variance positions, each variance position having a variance associated with it, where each variance is computed from t transform coefficients, the t transform coefficients being in a corresponding coefficient position of the t transform matrices; and

wherein the selecting-d-coefficient-positions step includes the step of;

selecting d coefficient positions corresponding to variance positions of the variance matrix having d highest variances.

8. A method for selecting a d-entry feature set for video classification from t training images, each of the t training images having v rows and h columns of sub-images, the method comprising the steps of:

computing t transform matrices by performing a transform on each of the t training images, each transform matrix having v rows and h columns of coefficient positions, each coefficient position having a transform coefficient associated with it; and

selecting d coefficient positions as the d-entry feature set based upon the transform coefficients in the t transform matrices;

computing a mean matrix having v rows and h columns of mean positions, each mean position having a mean associated with it, where each mean is computed from the t transform coefficients, the t transform coefficients being in a corresponding coefficient position of the t transform matrices; and

wherein the selecting-d-coefficient-positions step includes the step of;

selecting the d coefficient positions corresponding to mean positions of the mean matrix having d highest mean magnitudes.

9. A method for selecting a d-entry feature set for video classification from t training images, each of the t training images having v rows and h columns of sub-images, the method comprising the steps of:

computing t transform matrices by performing a transform on each of the t training images, each transform matrix having v rows and h columns of coefficient positions, each coefficient position having a transform coefficient associated with it; and

selecting d coefficient positions as the d-entry feature set based upon the transform coefficients in the t transform matrices;

computing a covariance matrix having v×

h rows and v×

h columns of covariance positions, each covariance position having a covariance associated with it, where each covariance is computed from t transform coefficients, the t transform coefficients being in a corresponding coefficient position of the t transform matrices; and

wherein the selecting-d-coefficient-positions step includes the step of;

selecting d coefficient positions corresponding to covariance positions of the covariance matrix.

10. A method of generating a video image class statistical model, the method comprising the steps of:

determining a first d-entry mean vector having d mean positions, each mean position having a mean associated with it, wherein each mean position corresponds to a transform coefficient position in a transform matrix; and

determining a first d-entry variance feature vector having d variance positions, each variance position having a variance associated with it, wherein each variance position corresponds to one of the mean positions.

11. A method of generating a video image class statistical model, the method comprising the steps of:

determining a first d-entry mean vector having d mean positions, each mean position having a mean associated with it, wherein each mean position corresponds to a transform coefficient position in a transform matrix; and

determining a first d-entry variance feature vector having d variance positions, each variance position having a variance associated with it, wherein each variance position corresponds to one of the mean positions;

determining a second d-entry mean vector;

determining a second d-entry variance feature vector; and

determining a mixture weight for combining the first and second d-entry mean vectors;

wherein the video image class statistical model is a Gaussian mixture;

wherein the first and second d-entry mean vectors and the first and second d-entry variance feature vectors are computed using an expectation-maximization algorithm.

12. A method of generating s video image class statistical models, the method comprising the steps of:

for each of the s video image classes, determining a d-entry mean vector having d mean positions, each mean position having a mean associated with it, wherein each mean position corresponds to a transform coefficient position in a transform matrix; and

for each of the s video image classes, determining a d-entry variance feature vector having d variance positions, each variance position having a variance associated with it, wherein each variance position corresponds to one of the mean positions.

13. A method as in claim 12, wherein each of the s d-entry mean vector refers to identical d transform coefficient positions.

14. A method as in claim 12, wherein the image class statistical model is a Gaussian distribution.

15. A method as in claim 12, further comprising the step of:

determining a class transition probability matrix having s rows and s columns of class transition probability positions, each class transition probability position having a class transition probability associated with it, wherein an ith-row-jth-column class transition probability position represents a probability of transferring from an ith video image class to a jth video image class during a frame transition from a previous video frame to a current video frame.

16. A method for classifying a video frame into one of s video image classes, the method comprising the steps of:

retrieving a d-entry feature vector corresponding to the video frame;

for each of the s video image classes, using the d-entry feature vector to compute an image class probability of the d-entry feature vector being produced by a corresponding one of s image class statistical models; and

classifying the video frame into the video image class corresponding to a maximum image class probability.

17.A method as in claim 16, further comprising the step of;

prior to the retrieving step, performing a transform on the video frame.

17. A method as in claim 16,

wherein the step of computing an image class probability is performed by applying a Gaussian probability distribution function.

18. A method as in claim 16,

wherein the step of computing an image class probability is performed by applying a Gaussian mixture probability distribution function.

19. A method for classifying a video frame into one of s video image classes, the method comprising the steps of:

retrieving a d-entry feature vector corresponding to the video frame; and

for each of the s video image classes, using the d-entry feature vector, s previous image class probabilities, a corresponding one of s class transition probability vectors, and a corresponding one of s image class statistical models to compute an image class probability for the d-entry feature vector;

for each of the s video image classes, generating a previous image class pointer corresponding to a maximum product of a previous image class probability and class transition probability.

20. A method as in claim 20, further comprising the step of:

classifying the video frame into the video image class corresponding to a maximum image class probability.

21. A method as in claim 21, further comprising the step of:

classifying a previous frame into the video image class indicated by the previous image class pointer.

22. A method for segmenting a series of video frames into one of s video image classes, the method comprising the steps of:

for each of the video frames in the series,

retrieving a d-entry feature vector corresponding to the video frame; and

for each of the s video image classes,

using the d-entry feature vector, s previous image class probabilities, a corresponding one of s class transition probability vectors, and a corresponding one of s image class statistical models to compute an image class probability for the d-entry feature vector; and

generating a previous image class pointer corresponding to a maximum product of a previous image class probability and class transition probability;

for a last video frame in the series,

classifying the video frame into the video image class corresponding to a maximum image class probability; and

for each of the video frames except the last video frame in the series,

classifying a previous frame into the video image class indicated by the previous image class pointer.

23. A method of determining similarity of a video frame using an image class statistical model, comprising the steps of:

retrieving a feature vector corresponding to the video frame;

retrieving a mean vector of the image class statistical model; and

subtracting the mean vector from the feature vector to produce a difference vector;

classifying the video frame as similar if a magnitude of the difference vector is less than a predetermined multiple of a standard deviation of the image class statistical model.

24. A method as in claim 24, further comprising the step of:

computing an image class probability of the video frame being produced by an image class statistical model using the feature vector.

25. A method as in claim 25, comprising the steps of:

computing a logarithm of the image class probability; and

displaying the logarithm of the image class probability in relation to the video frame.

26. A computer readable storage medium, comprising:

computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method for selecting a d-entry feature set for video classification from t training images, each of the t training images having v rows and h columns of sub-images, the method comprising the steps of;

computing t transform matrices by performing a transform on each of the t training images, each transform matrix having v rows and h columns of coefficient positions, each coefficient position having a transform coefficient associated with it; and

selecting d coefficient positions as the d-entry feature set based upon the transform coefficients in the t transform matrices.

27. A computer readable storage medium, comprising:

computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method of generating a video image class statistical model, the method comprising the steps of;

determining a first d-entry mean vector having d mean positions, each mean position having a mean associated with it, wherein each mean position corresponds to a transform coefficient position in a transform matrix; and

determining a first d-entry variance feature vector having d variance positions, each variance position having a variance associated with it, wherein each variance position corresponds to one of the mean positions.

28. A computer readable storage medium, comprising:

computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method of generating s video image class statistical models, the method comprising the steps of;

for each of the s video image classes, determining a d-entry mean vector having d mean positions, each mean position having a mean associated with it, wherein each mean position corresponds to a transform coefficient position in a transform matrix; and

for each of the s video image classes, determining a d-entry variance feature vector having d variance positions, each variance position having a variance associated with it, wherein each variance position corresponds to one of the mean positions.

29. A computer readable storage medium, comprising:

computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method for classifying a video frame into one of s video image classes, the method comprising the steps of;

retrieving a d-entry feature vector corresponding to the video frame;

for each of the s video image classes, using the d-entry feature vector to compute an image class probability of the d-entry feature vector being produced by a corresponding one of s image class statistical models; and

classifying the video frame into the video image class corresponding to a maximum image class probability.

30. A computer readable storage medium, comprising:

computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method for classifying a video frame into one of s video image classes, the method comprising the steps of;

retrieving a d-entry feature vector corresponding to the video frame; and

for each of the s video image classes, using the d-entry feature vector, s previous image class probabilities, a corresponding one of s class transition probability vectors, and a corresponding one of s image class statistical models to compute an image class probability for the d-entry feature vector.

31. A computer readable storage medium, comprising computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method for segmenting a series of video frames into one of s video image classes, the method comprising the steps of:

for each of the video frames in the series,

retrieving a d-entry feature vector corresponding to the video frame; and

for each of the s video image classes,

using the d-entry feature vector, s previous image class probabilities, a corresponding one of s class transition probability vectors, and a corresponding one of s image class statistical models to compute an image class probability for the d-entry feature vector; and

generating a previous image class pointer corresponding to a maximum product of a previous image class probability and class transition probability;

for a last video frame in the series,

classifying the video frame into the video image class corresponding to a maximum image class probability; and

for each of the video frames except the last video frame in the series,

classifying a previous frame into the video image class indicated by the previous image class pointer.

32. A computer readable storage medium, comprising:

computer readable program code embodied on said computer readable storage medium, said computer readable program code for programming a computer to perform a method of determining similarity of a video frame using an image class statistical model, comprising the steps of;

retrieving a feature vector corresponding to the video frame;

retrieving a mean vector of the image class statistical model; and

subtracting the mean vector from the feature vector to produce a difference vector;

classifying the video frame as similar if a magnitude of the difference vector is less than a predetermined multiple of a standard deviation of the image class statistical model.

33. A computer system, comprising:

a processor; and

a processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for programming the computer system to perform a method for selecting a d-entry feature set for video classification from t training images, each of the t training images having v rows and h columns of sub-images, the method comprising the steps of;

computing t transform matrices by performing a transform on each of the t training images, each transform matrix having v rows and h columns of coefficient positions, each coefficient position having a transform coefficient associated with it; and

selecting d coefficient positions as the d-entry feature set based upon the transform coefficients in the t transform matrices.

34. A computer system, comprising:

a processor; and

a processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for programming the computer system to perform a method of generating a video image class statistical model, the method comprising the steps of;

determining a first d-entry mean vector having d mean positions, each mean position having a mean associated with it, wherein each mean position corresponds to a transform coefficient position in a transform matrix; and

determining a first d-entry variance feature vector having d variance positions, each variance position having a variance associated with it, wherein each variance position corresponds to one of the mean positions.

35. A computer system, comprising:

a processor; and

a processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for programming the computer system to perform a method of generating s video image class statistical models, the method comprising the steps of;

for each of the s video image classes, determining a d-entry mean vector having d mean positions, each mean position having a mean associated with it, wherein each mean position corresponds to a transform coefficient position in a transform matrix; and

for each of the s video image classes, determining a d-entry variance feature vector having d variance positions, each variance position having a variance associated with it, wherein each variance position corresponds to one of the mean positions.

36. A computer system, comprising:

a processor; and

a processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for programming the computer system to perform a method for classifying a video frame into one of s video image classes, the method comprising the steps of;

retrieving a d-entry feature vector corresponding to the video frame;

for each of the s video image classes, using the d-entry feature vector to compute an image class probability of the d-entry feature vector being produced by a corresponding one of s image class statistical models; and

classifying the video frame into the video image class corresponding to a maximum image class probability.

37. A computer system, comprising:

a processor; and

a processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said processor readable program code for programming the computer system to perform a method for classifying a video frame into one of s video image classes, the method comprising the steps of;

retrieving a d-entry feature vector corresponding to the video frame; and

for each of the s video image classes, using the d-entry feature vector, s previous image class probabilities, a corresponding one of s class transition probability vectors, and a corresponding one of s image class statistical models to compute an image class probability for the d-entry feature vector.

38. A computer system, comprising:

a processor; and

a processor readable storage medium having processor readable program code embodied on said processor readable storage medium, said computer readable program code for programming the computer system to perform a method for segmenting a series of video frames into one of s video image classes, the method comprising the steps of;

for each of the video frames in the series,

retrieving a d-entry feature vector corresponding to the video frame; and

for each of the s video image classes,

using the d-entry feature vector, s previous image class probabilities, a corresponding one of s class transition probability vectors, and a corresponding one of s image class statistical models to compute an image class probability for the d-entry feature vector; and

generating a previous image class pointer corresponding to a maximum product of a previous image class probability and class transition probability;

for a last video frame in the series,

classifying the video frame into the video image class corresponding to a maximum image class probability; and

for each of the video frames except the last video frame in the series,

classifying a previous frame into the video image class indicated by the previous image class pointer.

39. A computer system, comprising:

a processor; and

a processor readable storage medium having a processor readable program code embodied on said processor readable storage medium, said processor readable program code for programming the computer system to perform a method of determining similarity of a video frame using an image class statistical model, comprising the steps of;

retrieving a feature vector corresponding to the video frame;

retrieving a mean vector of the image class statistical model; and

subtracting the mean vector from the feature vector to produce a difference vector classifying the video frame as similar if a magnitude of the difference vector is less than a predetermined multiple of a standard deviation of the image class statistical model.