Integrated method for scene change detection

• US 7,110,454 B1
• Filed: 12/21/1999
• Issued: 09/19/2006
• Est. Priority Date: 12/21/1999
• Status: Expired due to Fees

• Current Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Original Assignee: Siemens Corporate Research Incorporated (Siemens AG)
• Inventors: Chakraborty, Amit
• Primary Examiner(s): Philippe, Gims S.
• Application Number:
  US09/468,653
• Time in Patent Office: 2,464 Days
• Field of Search: 348/700, 348/699, 348/402.1, 348/407.1, 348/413.1, 348/416.1, 375/240.16, 375/240.25, 382/236, 382/243, 382/268, 382/266, 382/235, 382/173, 345/700
• US Class Current: 375/240.16
• 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: H04N 5/147 Scene change detection

Abstract

A system and method for detecting scene changes in a sequence of video frames utilizing a combination of a plurality of difference metrics including an interframe difference metric, a histogram difference metric and an interframe variance difference metric, as well as adaptive threshold level selection methods to dynamically select appropriate threshold levels for each of the difference metrics. The interframe and histogram difference metrics are used to identify abrupt scene changes and the interframe variance difference metric is used to identify gradual scene changes. The identified gradual and abrupt scene changes are validated by applying a plurality of conditions.

Claims

1. A method for detecting scene changes in a video, comprising the steps of:

computing a plurality of difference metrics of successive frames in a sequence of video frames, wherein the plurality of difference metrics comprise an interframe difference metric, a histogram difference metric, and an interframe variance difference metric;

automatically identifying candidate scene changes in the sequence of video frames using each of the computed difference metrics, wherein the candidate scene changes comprise abrupt scene changes that are identified using a combination of the computed interframe difference and histogram difference metrics, and gradual scene changes that are identified using the computed interframe variance difference metric; and

verifying that the candidate scene changes satisfy at least one predetermined condition for selecting final scene changes,

wherein the step of identifying candidate scene changes comprises the steps of;

identifying a given video frame as a candidate scene change based on the interframe difference metric, if the computed interframe difference between the given video frame and a previous video frame satisfies a first threshold;

identifying a given video frame as a candidate scene change based on the histogram difference metric, if the computed histogram difference between the given video frame and a previous video frame satisfies a second threshold; and

identifying a given video frame as a candidate scene change based on the interframe variance difference metric, if the computed interframe variance difference between the given video frame and a previous video frame satisfies a third threshold,

wherein the step of verifying comprises the steps of;

(a) selecting as a potential abrupt scene change, each video frame that was identified as a candidate scene change based on both the interframe difference metric and the histogram difference metric;

(b) removing a least probable one of any two successive potential abrupt scene changes, if a distance between the two successive potential abrupt scene changes is less than a predetermined minimum shot duration;

(c) selecting as a potential gradual scene change, each video frame that was identified as a candidate scene change based on the interframe variance difference metric;

(d) removing as a potential gradual scene change, each video frame selected in step (c) that is also a potential abrupt scene change remaining after step (b);

(e) for each potential gradual scene change remaining after step (d), determining if there are proximate frames that were selected as potential gradual scene changes;

(f) removing as a potential gradual scene change, each frame having no proximate frames that were selected as potential gradual scene changes;

(g) for each frame remaining after step (f) that is not selected as a potential gradual scene change, determining if the frame is located between sequences of frames that are selected as potential gradual scene changes;

(h) selecting each frame in step (g) as a potential gradual scene change if the frame is determined to be located between sequences of frames that are selected as potential gradual scene changes;

(i) determining a length of each sequence of potential gradual scene changes remaining after step (h);

(i) comparing the length of each sequence to a predetermined scene change duration threshold; and

(k) removing as a potential gradual scene change location, each frame of each sequence having a length that exceeds the predetermined scene change duration threshold.

2. The method of claim 1, wherein the video frames are compressed.

3. The method of claim 1, further comprising the step of dynamically computing the first, second and third thresholds.

4. The method of claim 3, wherein the step of dynamically computing the first threshold comprises the steps of:

selecting a window of a predetermined number of frames;

determining a minimum value and maximum value of the computed interframe difference metric associated with the frames in the window; and

computing the first threshold based on the determined minimum and maximum values.

5. The method of claim 3, wherein the step of dynamically computing the second threshold comprises the steps of:

selecting a window of a predetermined number of frames;

determining a minimum value and maximum value of the computed histogram difference metric associated with the frames in the window; and

computing the second threshold based on the determined minimum and maximum values.

6. The method of claim 3, wherein the step of dynamically computing the third threshold comprises the steps of:

selecting a window comprising n frames;

arranging in increasing order, the computed values of the interframe variance difference associated with the n frames in the window; and

computing the third threshold as an m^th order statistic, where m=(1−

∀

)n and ∀

denotes a user selected variable.

7. The method of claim 1, wherein the step of verifying further comprises the steps of:

(l) determining if the distance between any two successive potential scene changes is less than the predetermined minimum shot duration threshold, the potential scene changes comprising the potential abrupt scene changes remaining after step (b) and the potential gradual scene changes remaining after step (k); and

(m) removing a least probable one of any two successive potential scene changes, if the distance between the two successive potential scene changes is less than the predetermined minimum shot duration.

8. The method of claim 7, wherein the step of verifying further comprises the steps of:

(n) computing a keyframe for each shot generated by the potential scene changes remaining after step (m);

(o) computing an interframe difference between the keyframe of successive shots;

(p) merging successive shots with keyframes having a computed interframe difference that is less than a predetermined threshold; and

(q) selecting as final scene changes, the potential scene changes associated with the shots remaining after step (p).

9. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for detecting scene changes in a video, the method comprising the steps of:

computing a plurality of difference metrics of successive frames in a sequence of video frames, wherein the plurality of difference metrics comprise an interframe difference metric, a histogram difference metric, and an interframe variance difference metric;

automatically identifying candidate scene changes in the sequence of video frames using each of the computed difference metrics, wherein the candidate scene changes comprise abrupt scene changes that are identified using a combination of the computed interframe difference and histogram difference metrics, and gradual scene changes that are identified using the computed interframe variance difference metric; and

verifying that the candidate scene changes satisfy at least one predetermined condition for selecting final scene changes,

wherein the instructions for performing the step of identifying candidate scene changes comprise instructions for performing the steps of;

identifying a given video frame as a candidate scene change based on the interframe difference metric, if the computed interframe difference between the given video frame and a previous video frame satisfies a first threshold;

identifying a given video frame as a candidate scene change based on the histogram difference metric, if the computed histogram difference between the given video frame and a previous video frame satisfies a second threshold; and

identifying a given video frame as a candidate scene change based on the interframe variance difference metric, if the computed interframe variance difference between the given video frame and a previous video frame satisfies a third threshold,

wherein the instructions for performing the step of verifying comprise instructions for performing the steps of;

(a) selecting as a potential abrupt scene change, each video frame that was identified as a candidate scene change based on both the interframe difference metric and the histogram difference metric;

(b) removing a least probable one of any two successive potential abrupt scene changes, if a distance between the two successive potential abrupt scene changes is less than a predetermined minimum shot duration;

(c) selecting as a potential gradual scene change, each video frame that was identified as a candidate scene change based on the interframe variance difference metric;

(d) removing as a potential gradual scene change, each video frame selected in step (c) that is also a potential abrupt scene change remaining after step (b);

(e) for each potential gradual scene change remaining after step (d), determining if there are proximate frames that were selected as potential gradual scene changes;

(f) removing as a potential gradual scene change, each frame having no proximate frames that were selected as potential gradual scene changes;

(g) for each frame remaining after step (f) that is not selected as a potential gradual scene change, determining if the frame is located between sequences of frames that are selected as potential gradual scene changes;

(h) selecting each frame in step (g) as a potential gradual scene change if the frame is determined to be located between sequences of frames that are selected as potential gradual scene changes;

(i) determining a length of each sequence of potential gradual scene changes remaining after step (h);

(j) comparing the length of each sequence to a predetermined scene change duration threshold; and

(k) removing as a potential gradual scene change location each frame of each sequence having a length that exceeds the predetermined scene change duration threshold.

10. The program storage device of claim 9, wherein the video frames are compressed.

11. The program storage device of claim 9, further comprising instructions for performing the step of dynamically computing the first, second and third thresholds.

12. The program storage device of claim 11, wherein the instructions for performing the step of dynamically computing the first threshold comprise instructions for performing the steps of:

selecting a window of a predetermined number of frames;

determining a minimum value and maximum value of the computed interframe difference metric associated with the frames in the window; and

computing the first threshold based on the determined minimum and maximum values.

13. The program storage device of claim 11, wherein the instructions for performing the step of dynamically computing the second threshold comprise instructions for performing the steps of:

selecting a window of a predetermined number of frames;

determining a minimum value and maximum value of the computed histogram difference metric associated with the frames in the window; and

computing the second threshold based on the determined minimum and maximum values.

14. The program storage device of claim 11, wherein the instructions for performing the step of dynamically computing the third threshold comprise instructions for performing the steps of:

selecting a window comprising n frames;

arranging in increasing order, the computed values of the interframe variance difference associated with the n frames in the window; and

computing the third threshold as an m^th order statistic, where m=(1−

∀

)n and ∀

denotes a user selected variable.

15. The program storage device of claim 9, wherein the instructions for performing the step of verifying further comprise instructions for performing the steps of:

(l) determining if the distance between any two successive potential scene changes is less than the predetermined minimum shot duration threshold, the potential scene changes comprising the potential abrupt scene changes remaining after step (b) and the potential gradual scene changes remaining after step (k); and

(m) removing a least probable one of any two successive potential scene changes, if the distance between the two successive potential scene changes is less than the predetermined minimum shot duration.

16. The program storage device of claim 15, wherein the instructions for performing the step of verifying further comprise instructions for performing the steps of:

(n) computing a keyframe for each shot generated by the potential scene changes remaining after step (m);

(o) computing an interframe difference between the keyframe of successive shots;

(p) merging successive shots with keyframes having a computed interframe difference that is less than a predetermined threshold; and

(q) selecting as final scene changes, the potential scene changes associated with the shots remaining after step (p).