Shot boundary detection

• US 7,123,769 B2
• Filed: 11/09/2001
• Issued: 10/17/2006
• Est. Priority Date: 11/09/2001
• Status: Active Grant

• Current Assignee: ArcSoft, Inc.
• Original Assignee: ArcSoft, Inc.
• Inventors: Xiong, Wei
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US10/008,338
• Publication Number:
  US 20030091235A1
• Time in Patent Office: 1,803 Days
• Field of Search: 348/700, 348/701, 348/722, 382/155, 382/156, 382/157, 382/160, 382/165, 382/173, 382/225, 382/236, 382/170, 382/203
• US Class Current: 382/199
• CPC Class Codes: G06F 16/785 using colour or luminescence

Abstract

A video segment is processed to identify frames representing shot boundaries in the video segment. Initially, a partial block-based comparison technique is used to determine the amount of change (i.e., a first difference) that occurs between a pair of distant (i.e., not consecutive) frames. Additionally, edge and/or color differences are computed between the pair of frames to confirm that a change has occurred. If the change is confirmed, a step variable technique is used to locate the change between two consecutive frames between the distant frames. If the partial block-based comparison technique obtains a difference between the consecutive frames that exceeds the first threshold, then an abrupt change is detected. Otherwise, the edge and/or color differences are used to determine whether a gradual transition has occurred.

Claims

1. A method for detecting a shot boundary, comprising:

determining a first difference between a first frame and a second frame, wherein the first difference comprises a partial comparison between the first frame and the second frame;

determining whether the first difference exceeds a threshold, wherein the first frame and the second frame comprise a border for a candidate shot boundary when the first difference exceeds the threshold; and

when the first difference exceeds the threshold,

computing at least one of an edge difference and a color difference between the first frame and the second frame;

confirming whether the first frame and the second frame comprise a border for a candidate shot boundary based on the value of at least one of the edge difference and the color difference; and

searching for a shot boundary between the first frame and the second frame.

2. The method of claim 1, further comprising:

selecting the first frame and the second frame from a video segment.

3. The method of claim 2, further comprising:

selecting the first frame and the second frame based on a predetermined value that is used to step through the video segment.

4. The method of claim 3, wherein the predetermined value is user defined.

5. The method of claim 3, wherein the predetermined value is set at a default value.

6. The method of claim 1, further comprising:

when the first difference does not exceed the threshold, selecting third and fourth frames based on a predetermined value for stepping through a video segment.

7. The method of claim 1, when the first difference exceeds the threshold, further comprising:

setting a candidate flag to indicate that the first frame and the second frame comprise a border for a candidate shot boundary.

8. The method of claim 7, further comprising:

selecting a new first frame and a new second frame; and

using the candidate flag to determine whether to compute a second difference between the new first frame and the new second frame.

9. The method of claim 1, when the first difference exceeds the threshold, further comprising:

setting a candidate frame to the first frame.

10. The method of claim 1, wherein the partial comparison comprises:

dividing the first frame and the second frame into blocks;

selecting some corresponding blocks between the first frame and the second frame;

determining whether the selected corresponding blocks are similar, wherein the first difference is a total number of the selected corresponding blocks that are different.

11. The method of claim 1, when it is determined that the first difference exceeds the threshold, further comprising:

determining whether the first frame and the second frame are consecutive frames.

12. The method of claim 11, when it is determined that the first frame and second frame are not consecutive frames, further comprising:

performing a binary search within the first frame and the second frame to locate consecutive frames that may comprise a shot boundary;

computing a second difference between the consecutive frames.

13. The method of claim 12, further comprising:

if the second difference exceeds the threshold, detecting an abrupt break.

14. The method of claim 12, wherein the threshold comprises a first threshold, further comprising:

if the second difference does not exceed the first threshold, determining whether the second difference exceeds a second threshold or at least one of the color difference and the edge difference confirms the first frame and the second frame comprise a border for a candidate shot boundary; and

if the second difference exceeds the second threshold or at least one of the color difference and the edge difference confirms the first frame and the second frame comprise a border for a candidate shot boundary, detecting a gradual transition.

15. The method of claim 14, wherein the second threshold is smaller than the first threshold.

16. The method of claim 14, further comprising:

if the second difference does not exceed the second threshold or at least one of the color difference and the edge difference does not confirm the first frame and the second frame comprise a border for a candidate shot boundary, selecting a third frame and a fourth frame for processing to detect a shot boundary based on a previously selected candidate frame.

17. The method of claim 1, further comprising:

performing post-processing to identity potential shot boundaries that are false alarms.

18. A method for detecting a shot boundary, comprising:

determining a first difference between a first frame and a second frame;

determining whether the first difference exceeds a threshold, wherein the first frame and the second frame comprise a border for a candidate shot boundary when the first difference exceeds the threshold; and

when the first difference exceeds the threshold,

computing at least one of an edge difference and a color difference between the first frame and the second frame; and

confirming whether the first frame and the second frame comprise a border for a candidate shot boundary based on at least one of the edge difference and the color difference;

determining whether the first frame and the second frame are consecutive frames;

when the first frame and the second frame are not consecutive frames,

selecting a middle frame between the first frame and the second frame;

computing a second difference between the first frame and the middle frame;

computing a third difference between the second frame and the middle frame; and

determining a range of frames in which to search for a shot boundary based on whether the second difference is smaller than the third difference.

19. The method of claim 18, further comprising:

when the second difference is smaller than the third difference, searching for a shot boundary using the middle frame and the second frame.

20. The method of claim 18, further comprising:

when the second difference is greater than the third difference, searching for a shot boundary using the first frame and the middle frame.

21. A method for detecting a shot boundary, comprising:

determining a first difference between a first frame and a second frame, wherein the first difference comprises a partial comparison between the first frame and the second frame;

determining whether the first difference exceeds a threshold, wherein the first frame and the second frame comprise a border for a candidate shot boundary when the first difference exceeds the threshold;

when the difference exceeds the threshold,

computing an edge difference between the first frame and the second frame;

confirming whether the first frame and the second frame comprise a border for a candidate shot boundary based on the edge difference; and

searching for a shot boundary between the first frame and the second frame.

22. The method of claim 21, further comprising:

setting a candidate flag to indicate that the first frame and the second frame comprise a border for a candidate shot boundary.

23. The method of claim 22, further comprising:

selecting a new first frame and a new second frame; and

using the candidate flag to determine whether to compute a second difference between the new first frame and the new second frame.

24. The method of claim 21, further comprising:

selecting the first frame and the second frame based on a previously selected candidate frame.

25. The method of claim 21, wherein said computing an edge difference comprises:

generating an edge histogram; and

using the edge histogram to determine whether the first frame and the second frame comprise a possible border for a candidate shot boundary.

26. A method for detecting a shot boundary, comprising:

determining a first difference between a first frame and a second frame, wherein the first difference comprises a partial comparison between the first frame and the second frame;

determining whether the first difference exceeds a threshold, wherein the first frame and the second frame comprise a border for a candidate shot boundary when the first difference exceeds the threshold;

when the first difference exceeds the threshold,

computing a color difference between the first frame and the second frame; and

confirming whether the first frame and the second frame comprise a border for a candidate shot boundary based on the color difference; and

searching for a shot boundary between the first frame and the second frame.

27. The method of claim 26, further comprising:

setting a candidate flag to indicate that the first frame and the second frame comprise a border for a candidate shot boundary.

28. The method of claim 27, further comprising:

selecting a new first frame and a new second frame; and

using the candidate flag to determine whether to compute a second difference between the new first frame and the new second frame.

29. The method of claim 26, further comprising:

selecting the first frame and the second frame based on a previously selected candidate frame.

30. The method of claim 26, wherein said computing a color difference comprises:

generating an color histogram; and

using the color histogram to determine whether the first frame and the second frame comprise a border for a candidate shot boundary.

31. A method for detecting a shot boundary, comprising:

computing a difference between a first frame and a distant frame, wherein the difference comprises a partial comparison between the first frame and the distant frame;

determining whether the first difference exceeds a threshold, wherein the first frame and the distant frame comprise a border for a candidate shot boundary when the difference exceeds the threshold;

if the difference exceeds the threshold,

computing at least one of an edge difference and a color difference between the first frame and the distant frame;

confirming whether the first frame and the distant frame comprises a border for a candidate shot boundary based on at least one of the edge difference and the color difference; and

performing a binary search for a shot boundary between the first frame and the distant frame.

32. A system, comprising:

a computer including a processor and a memory;

a sequence of frames stored in the memory; and

a program comprising instructions stored in the memory of the computer, wherein the instructions are executed by the processor of the computer to;

determine a difference between a first frame and a second frame, wherein the difference comprises a partial comparison between the first frame and the second frame;

determine whether the difference exceeds a threshold, wherein the first frame and the second frame comprise a border for a candidate shot boundary when the difference exceeds the threshold; and

when the difference exceeds the threshold,

compute at least one of an edge difference and a color difference between the first frame and the second frame;

confirm whether the first frame and the second frame comprise a border for a shot boundary based on the value of at least one of the edge difference and color difference; and

searching for a shot boundary between the first frame and the second frame.

33. The system of claim 32, further comprising:

a video camera, wherein the sequence of frames is recorded with the video camera.

34. A system, comprising:

a computer including a processor and a memory;

a sequence of frames stored in the memory; and

a program comprising instructions stored in the memory of the computer, wherein the instructions are executed by the processor of the computer to;

determine a first difference between a first frame and a second frame;

determine whether the first difference exceeds a threshold, wherein the first frame and the second frame comprise a border for a candidate shot boundary when the first difference exceeds the threshold; and

when the first difference exceeds the threshold,

compute at least one of an edge difference and a color difference between the first frame and the second frame;

confirm whether the first frame and the second frame comprise a border for a candidate shot boundary based on at least one of the edge difference and the color difference; and

determine whether the first frame and the second frame are consecutive frames;

when the first frame and the second frame are not consecutive frames,

select a middle frame between the first frame and the second frame;

compute a second difference between the first frame and the middle frame;

compute a third difference between the second frame and the middle frame; and

determine a range of frames in which to search for a shot boundary based on whether the second difference is smaller than the third difference.