IDENTIFYING SCENE BOUNDARIES USING GROUP SPARSITY ANALYSIS

• US 20160328615A1
• Filed: 07/22/2016
• Published: 11/10/2016
• Est. Priority Date: 08/03/2012
• Status: Active Grant

• Current Assignee: Kodak Alaris Inc (KPP (no. 2) Trustees Ltd.)
• Original Assignee: Kodak Alaris Inc (KPP (no. 2) Trustees Ltd.)
• Inventors: Kumar, Mrityunjay, Loui, Alexander C., Pillman, Bruce Harold
• Granted Patent: US 9,665,775 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 18/00 Pattern recognition
• CPC Class Codes: G06F 18/2136 based on sparsity criteria, e.g. with an overcomplete basis
• CPC Class Codes: G06V 10/513 Sparse representations
• 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/47 Detecting features for summarising video content
• 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 for identifying a set of key video frames from a video sequence comprising extracting feature vectors for each video frame and applying a group sparsity algorithm to represent the feature vector for a particular video frame as a group sparse combination of the feature vectors for the other video frames. Weighting coefficients associated with the group sparse combination are analyzed to determine video frame clusters of temporally-contiguous, similar video frames. The video sequence is segmented into scenes by identifying scene boundaries based on the determined video frame clusters.

Claims

1-15. -15. (canceled)

16. A method for determining scene boundaries within a video sequence including a time sequence of video frames, each video frame including an array of image pixels having pixel values, comprising:

a) selecting a set of video frames from the video sequence, the set of video frames comprising a starting point and an ending point;

b) extracting a feature vector for each video frame in the set of video frames;

c) applying a group sparsity algorithm to represent the feature vector for a particular video frame as a group sparse combination of the feature vectors for the other video frames in the set of video frames, each feature vector for the other video frames in the group sparse combination having an associated weighting coefficient, wherein the weighting coefficients for feature vectors corresponding to other video frames that are most similar to the particular video frame are non-zero, and the weighting coefficients for feature vectors corresponding to other video frames that are most dissimilar from the particular video frame are zero;

d) analyzing the weighting coefficients to determine a video frame cluster of temporally-contiguous, similar video frames that includes the particular video frame;

e) repeating steps c)-d) for a plurality of particular video frames to provide a plurality of video frame clusters;

f) identifying one or more scene boundaries corresponding scenes in the video sequence based on the locations of boundaries between the determined video frame clusters; and

g) storing an indication of the identified scene boundaries in a processor-accessible memory;

wherein selecting a set of video frames from the video sequence comprises temporally sub-sampling the video sequence to select a subset of video frames.

17. The method of claim 16 wherein selecting a set of video frames further comprises separating the selected subset of video frames by a predefined interval.

18. The method of claim 17 wherein the predefined interval comprises an interval defined by every tenth video frame in the video sequence.

19. The method of claim 16 wherein selecting a set of video frames from the video sequence comprises using a user interface to enable a user to manually indicate the starting point and the ending point for the set of video frames.

20. A method for determining scene boundaries within a video sequence including a time sequence of video frames, each video frame including an array of image pixels having pixel values, comprising:

a) selecting a set of video frames from the video sequence, the set of video frames comprising a starting point and an ending point;

b) extracting a feature vector for each video frame in the set of video frames;

c) applying a group sparsity algorithm to represent the feature vector for a particular video frame as a group sparse combination of the feature vectors for the other video frames in the set of video frames, each feature vector for the other video frames in the group sparse combination having an associated weighting coefficient, wherein the weighting coefficients for feature vectors corresponding to other video frames that are most similar to the particular video frame are non-zero, and the weighting coefficients for feature vectors corresponding to other video frames that are most dissimilar from the particular video frame are zero;

d) analyzing the weighting coefficients to determine a video frame cluster of temporally-contiguous, similar video frames that includes the particular video frame;

e) repeating steps c)-d) for a plurality of particular video frames to provide a plurality of video frame clusters;

f) identifying one or more scene boundaries corresponding scenes in the video sequence based on the locations of boundaries between the determined video frame clusters; and

g) storing an indication of the identified scene boundaries in a processor-accessible memory;

wherein the video sequence comprises a plurality of independently encoded video frames and a plurality of video frames that are encoded using inter-frame coding, and wherein selecting a set of video frames from the video sequence comprises selecting at least a subset of the plurality of independently encoded video frames.

21. The method of claim 20 wherein selecting a set of video frames from the video sequence comprises using a user interface to enable a user to manually indicate the starting point and the ending point for the set of video frames.

22. A method for determining scene boundaries within a video sequence including a time sequence of video frames, each video frame including an array of image pixels having pixel values, comprising:

a) selecting a set of video frames from the video sequence, the set of video frames comprising a starting point and an ending point;

b) extracting a feature vector for each video frame in the set of video frames;

c) applying a group sparsity algorithm to represent the feature vector for a particular video frame as a group sparse combination of the feature vectors for the other video frames in the set of video frames, each feature vector for the other video frames in the group sparse combination having an associated weighting coefficient, wherein the weighting coefficients for feature vectors corresponding to other video frames that are most similar to the particular video frame are non-zero, and the weighting coefficients for feature vectors corresponding to other video frames that are most dissimilar from the particular video frame are zero;

d) analyzing the weighting coefficients to determine a video frame cluster of temporally-contiguous, similar video frames that includes the particular video frame;

e) repeating steps c)-d) for a plurality of particular video frames to provide a plurality of video frame clusters;

f) identifying one or more scene boundaries corresponding scenes in the video sequence based on the locations of boundaries between the determined video frame clusters; and

g) storing an indication of the identified scene boundaries in a processor-accessible memory;

wherein extracting a feature vector for each video frame comprises extracting a color channel of each video frame.

23. The method of claim 22 wherein the color channel comprises a green color channel.

24. The method of claim 22 wherein the color channel comprises pixel values for a plurality of color channels.

25. The method of claim 22 wherein selecting a set of video frames from the video sequence comprises using a user interface to enable a user to manually indicate the starting point and the ending point for the set of video frames.