Method and system for automatic classification of video images

• US 5,872,865 A
• Filed: 02/08/1995
• Issued: 02/16/1999
• Est. Priority Date: 02/08/1995
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Normile, James, Wang, Katherine
• Primary Examiner(s): Cumming, William
• Assistant Examiner(s): JOHNSON, BRIAN
• Application Number:
  US08/386,308
• Time in Patent Office: 1,469 Days
• Field of Search: 382/165, 382/190, 382/224, 382/225, 382/205, 382/217, 382/218, 382/221, 364/725, 348/526
• US Class Current: 382/224
• 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

Abstract

A computer system and computer implemented method automatically classify video sequences into categories. A set of categories is defined either manually through the association of selected video sequences with user supplied category designations, or automatically through segregation of a set of video sequences into groups of similar sequences. Input video sequences are then classified by either pixel decomposition or primitive attribute decomposition; the former analyzing each image on a pixel basis, the latter employing extracted image information. Categories can be trained as new video sequences are input into the system, or new categories can be created to accommodate such new sequences that are dissimilar from existing categories.

Claims

1. A method of automatically classifying a video sequence into a category, the video sequence including at least one frame, comprising the steps of:

creating a set of categories, each category representing a set of video sequences having a set of similar primitive image attribute values orthogonally representing the category, by;

receiving a user specification of selected video sequences;

determining for each selected video sequence at least one primitive image attribute value;

segregating the video sequences into sets, each set of video sequences having a set of similar primitive image attribute values;

defining each category by associating each of the sets of video sequences with each category;

for each category, creating a covariance matrix of dot products for each pair of the video sequences in the category; and

determining a set of eigen vectors from the covariance matrix as the set of similar primitive image attribute values of the category;

receiving an input video sequence;

determining a distortion measure for each category with respect to the input video sequence by projecting the input video sequence onto the set of similar primitive image attribute values of each category; and

classifying the input video sequence in the category having a minimum distortion measure.

2. The method of claim 1, wherein the step of creating a covariance matrix of dot products further comprises the steps of:

for each primitive image attribute value, creating a covariance matrix of dot products for the primitive image attribute value for each pair of video sequences; and

wherein the step of determining a set of eigen vectors further comprises the step of;

determining from the covariance matrix for each primitive image attribute value a set of eigen vectors, the set of eigen vectors being the set of similar primitive image attribute values of the category.

3. The method of claim 2, the step of determining a distortion measure, further comprising for each category, the steps of:

determining for the input video sequence a set of primitive image attribute values;

determining for each primitive image attribute value of the input video sequence a primitive image attribute vector comprising a dot product between the primitive image attribute value and the set of eigen vectors of the set of similar primitive image attribute values for the category;

comparing each primitive image attribute eigen vector with the primitive image attribute vectors for each input video sequence associated with the category to produce a distortion measure for each primitive image attribute value of the input video sequence;

determining for each primitive image attribute value of the input video sequence a distortion measure having a minimum value; and

determining a total distortion measure for the category as a function of the minimum distortion measures for each primitive image attribute value of the input video sequence.

4. The method of claim 1, the step of determining a distortion measure, further comprising for each category, the steps of;

determining for each frame of the input video sequence a frame vector comprising a dot product between the frame and the eigen vectors of the category;

comparing each frame vector with frame vectors for each video sequence associated with the category to produce a distortion measure for each frame; and

determining the distortion measure having a minimum value.

5. The method of claim 1, further comprising the steps of:

comparing the minimum distortion measure with a threshold; and

if the minimum distortion measure exceeds the threshold, creating a new category including the input video sequence.

6. The method of claim 1, further comprising the steps of;

comparing the minimum distortion measure with a threshold;

if the minimum distortion measure exceeds the threshold, associating the input video sequence with the category having minimum distortion measure;

recreating the covariance matrix of dot products for each pair of video sequences associated with the category; and

,

re-determining the set of eigen vectors from the covariance matrix as the set of similar primitive image attribute values of the category.

7. A computer system for automatically classifying an input video sequence including at least one frame into a category, comprising:

a processing unit programed to;

create a set of categories, each category representing a set of video sequences having a set of similar primitive image attribute values orthogonally representing the category, the categories created by the processing unit further programmed to;

receive a user specification of selected video sequences;

determine for each selected video sequence at least one primitive image attribute value;

segregate the video sequences into sets, each set of video sequences having a set of similar primitive image attribute values;

define each category by association of each of the sets of video sequences with each category;

for each category, create a covariance matrix of dot products for each pair of video sequences in the category; and

determine a set of eigen vectors from the covariance matrix as the set of similar primitive image attribute values of the category;

receive the input video sequence;

determine a distortion measure for each category with respect to the input video sequence by projecting the input video sequence onto the set of similar primitive image attribute values of each category; and

classify the input video sequence in the category having a minimum distortion measure.

8. The computer system of claim 7, further comprising:

a storage device, operatively coupled to the processing unit, and storing thereon a plurality of video sequences, a plurality of categories, each category defined by a set of similar primitive image attribute values and having a category designation;

a video input device operatively coupled to We storage device, for receiving video sequences from a source external to the computer system, and storing the video sequences on the storage device; and

a display device, operatively coupled to the processing unit, for displaying thereon selected portions of selected video sequences, and flier displaying category designations; and

an electronic pointing device, responsive to user inputs, for associating a selected portion of a selected video sequence with a selected category designation.

9. The computer system of claim 7, wherein the processing unit is further programmed to:

for each primitive image attribute value, create a covariance matrix of dot products for the primitive image attribute value for each pair of video sequences; and

,

determine from the covariance matrix for each primitive image attribute value a set of eigen vectors, the sets of eigen vectors being the set of si similar primitive image attribute values of the category.

10. The computer system of claim 9, wherein the processing unit is further programmed to:

determine for each primitive image attribute value of the input video sequence a primitive image attribute vector as a dot product of the primitive image attribute values and the set of eigen vectors of the set of similar primitive image attribute values for the category;

produce a distortion measure for each primitive image attribute value by comparing each primitive image attribute vector with primitive image attribute vectors for each video sequence associated with the category;

determine for each primitive image attribute value a distortion measure having a minimum value; and

determine a total distortion measure for the category as a function of the minimum distortion measures for each primitive image attribute value.

11. The computer system of claim 7, wherein the processing unit is further programmed to:

determine for each frame of the video sequence a frame vector as a dot product between the frame and the eigen vectors of the category;

compare each free vector with frame vectors for each video sequence associated with the category to produce a distortion measure for each frame; and

determine the distortion measure having a minimum value.

12. The computer system of claim 7, wherein the processing unit is further programmed to:

compare the minimum distortion measure with a threshold; and

if the minimum distortion measure exceeds the threshold, create a new category and include the input video sequence.

13. The computer system of claim 7, wherein the processing unit is further programmed to:

compare the minimum distortion measure with a threshold;

if the minimum distortion measure exceeds the threshold, associate the input video sequence with the category having the minimum distortion measure;

recreate the covariance matrix of dot products for each pair of video sequences associated with the category; and

,

re-determine the set of eigen vectors from the covariance matrix as the set of similar primitive image attribute values of the category.