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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.