VIDEO SEGMENTATION

• US 20110317982A1
• Filed: 02/26/2010
• Published: 12/29/2011
• Est. Priority Date: 02/27/2009
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Xu, Li-Qun, Anjulan, Arasanathan
• Granted Patent: US 8,385,663 B2
• Time in Patent Office: Days
• US Class Current: 386/241
• 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 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06V 10/7635 based on graphs, e.g. graph cuts or spectral clustering
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 20/49 Segmenting video sequences, i.e. computational techniques such as parsing or cutting the sequence, low-level clustering or determining units such as shots or scenes

Abstract

A method of segmenting a sequence of video images according to scene activity, the method comprising: defining a first series of nodes in a first multi-dimensional space, each node corresponding to an image of the sequence of video images; defining a transformation function that maps each of the first series of nodes to a corresponding node in a second multi-dimensional space having a lower dimensionality than the first multi-dimensional space; applying said transformation function to each of the first series of nodes to define a second series of respective nodes in the second multi-dimensional space; applying a data clustering algorithm to the second series of nodes to identify clusters of nodes within the second multi-dimensional space, the data clustering algorithm being constrained by a measure of feature distance between a pair of clusters of nodes and a measure of temporal distance between the pair of clusters of nodes; determining a representative image from each cluster of nodes and plotting each representative image with respect to a measure of the elapsed time of the sequence of video images to form an scene density curve indicating the underlying scene change activities; and segmenting the sequence of video images in accordance with local minima and/or maxima of the scene density curve.

Claims

1. A method of segmenting a sequence of video images according to scene activity, the method comprising:

defining a first series of nodes in a first multi-dimensional space, each of the first series of node corresponding to an image of the series of images and its location in the first space being defined in dependence on appearance components of the respective image;

defining a transformation function that maps each of the first series of nodes to a corresponding node in a second multi-dimensional space having a lower dimensionality than the first multi-dimensional space in such a way that neighbourhood relationships that exist between the nodes in the first multidimensional space are preserved between the respective nodes in the second multidimensional space;

applying said transformation function to each of the first series of nodes to define a second series of respective nodes in the second multi-dimensional space;

applying a data clustering algorithm to the second series of nodes to identify clusters of nodes within the second multi-dimensional space, characterised in that

the data clustering algorithm being constrained by a measure of feature distance between a pair of clusters of nodes and a measure of temporal distance, between the pair of clusters of nodes;

further characterised by

determining a representative image from each cluster of nodes and plotting each representative image with respect to a measure of the elapsed time of the sequence of video images to form an scene density curve indicating the underlying scene change activities, the scene density value for each representative image being inversely related to the time interval between that image'"'"'s neighbouring representative images; and

segmenting the sequence of video images in accordance with local minima and/or maxima of the scene density curve.

2. The method of claim 1, wherein the data clustering algorithm includes computing the measure of feature distance and the measure of temporal distance between pairs of nodes, selecting a pair of nodes and determining if the measure of temporal distance between the selected nodes is within a temporal threshold value.

3. The method of claim 2, wherein if the measure of temporal distance is within the temporal threshold value then further determining if the measure of feature distance between the selected nodes is within a feature distance threshold value.

4. The method of claim 3, wherein if the measure of feature distance is within the feature distance threshold value then merging the selected nodes to form a new single node.

5. The method of claim 2, wherein if the measure of temporal distance exceeds the temporal threshold value then a further pair of nodes are selected.

6. The method of claim 5, wherein the pairs of nodes are selected in ascending order of feature distance.

7. The method of claim 1, wherein the scene density curve is smoothed by application of a fitter.

8. The method of claim 7, wherein the filter has a window length.

9. The method of claim 8, wherein the filter window length is selected in dependence on one or more of the duration of the sequence of video images and the average duration of scene activity within the video images.

10. The method of claim 7, wherein the filter comprises a Kaiser filter.

11. A video processing system comprising a source of a sequence of video images and a data processor arranged to process the video images according to the method of claim 1.