Method and system for segmentation, classification, and summarization of video images

• US 7,630,562 B2
• Filed: 08/18/2006
• Issued: 12/08/2009
• Est. Priority Date: 11/24/1999
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Gong, Yihong, Liu, Xin
• Primary Examiner(s): Mariam; Daniel G
• Assistant Examiner(s): Seth; Manav
• Application Number:
  US11/505,833
• Publication Number:
  US 20060280365A1
• Time in Patent Office: 1,208 Days
• Field of Search: 382/100, 382/103, 382/106, 382/130, 382/162, 382/164, 382168-173, 382/181, 382190-191, 382199-219, 382/236, 37524008-24018
• US Class Current: 382/219
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 16/785 using colour or luminescence
• 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: G11B 27/031 Electronic editing of digitised analogue information signals, e.g. audio or video signals
• CPC Class Codes: H04N 5/147 Scene change detection
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

In a technique for video segmentation, classification and summarization based on the singular value decomposition, frames of the input video sequence are represented by vectors composed of concatenated histograms descriptive of the spatial distributions of colors within the video frames. The singular value decomposition maps these vectors into a refined feature space. In the refined feature space produced by the singular value decomposition, the invention uses a metric to measure the amount of information contained in each video shot of the input video sequence. The most static video shot is defined as an information unit, and the content value computed from this shot is used as a threshold to cluster the remaining frames. The clustered frames are displayed using a set of static keyframes or a summary video sequence. The video segmentation technique relies on the distance between the frames in the refined feature space to calculate the similarity between frames in the input video sequence. The input video sequence is segmented based on the values of the calculated similarities. Finally, average video attribute values in each segment are used in classifying the segments.

Claims

1. A method for determining a similarity between a first and a second frame in an input video sequence comprising a plurality of frames, said method comprising:

calculating a refined feature space representation of said input video sequence to generate a plurality of refined frames;

using said calculated refined feature space representation to compute said similarity between said first and said second frame; and

grouping said plurality of refined frames including the first and the second frame into a plurality of video shots, wherein the grouping is determined using a minimum threshold for frame inclusion, a maximum threshold for frame exclusion, and a threshold range from the minimum threshold to the maximum threshold, for which threshold range further analysis is performed,

wherein the refined feature space representation is a matrix, wherein each column of said matrix represents a frame in a refined feature space corresponding to a frame in said plurality of frames.

2. The method of claim 1, wherein in said calculating the refined feature space representation, said refined feature space representation is calculated using a singular value decomposition.

5. The method of claim 1, wherein said grouping comprises including two consecutive frames, among the plurality of the refined frames, in a video shot if a distance between the two consecutive frames is below the minimum threshold, and if the distance between the two consecutive frames is above the maximum threshold, declaring a shot boundary between the consecutive frames.

3. A computer-readable storage medium containing a program for executing a method of determining a similarity between a first and a second frame in an input video sequence comprising a plurality of frames, said method comprising:

calculating a refined feature space representation of said input video sequence to generate a plurality of refined frames;

using said calculated refined feature space representation to compute said similarity between said first and said second frame; and

grouping said plurality of refined frames including the first and the second frame into a plurality of video shots, wherein the grouping is determined using a minimum threshold for frame inclusion, a maximum threshold for frame exclusion, and a threshold range from the minimum threshold to the maximum threshold, for which threshold range further analysis is performed,

wherein the refined feature space representation is a matrix, wherein each column of said matrix represents a frame in a refined feature space corresponding to a frame in said plurality of frames.

4. The computer-readable storage medium of claim 3, wherein in said calculating the refined feature space representation, said refined feature space representation is calculated using a singular value decomposition.

6. The computer-readable storage medium of claim 3, wherein said grouping comprises including two consecutive frames, among the plurality of the refined frames, in a video shot if a distance between the two consecutive frames is below the minimum threshold, and if the distance between the two consecutive frames is above the maximum threshold, declaring a shot boundary between the consecutive frames.