Shot boundary detection

• US 20030091235A1
• Filed: 11/09/2001
• Published: 05/15/2003
• Est. Priority Date: 11/09/2001
• Status: Active Grant

• Current Assignee: ArcSoft, Inc.
• Original Assignee: ArcSoft, Inc.
• Inventors: Xiong, Wei
• Granted Patent: US 7,123,769 B2
• Time in Patent Office: Days
• 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;

determining whether the first difference exceeds a threshold; and

when the first difference exceeds the threshold,

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

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

determining whether the first frame and the second frame comprise a shot boundary based on the value of the edge difference or color difference.

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 first difference is computed using a partial block-based comparison technique.

11. The method of claim 1, 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 consecutive frames, further comprising:

computing a second difference between the first frame and the second frame.

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 color difference or edge difference exceeds a second threshold; and

if the color difference or edge difference exceeds the second threshold, 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 color difference or edge difference do not exceed the second threshold, 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 11, further comprising:

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.

18. The method of claim 17, 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.

19. The method of claim 17, 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.

20. The method of claim 1, further comprising:

when the first frame and the second frame comprise a border for a shot boundary, outputting the first frame and the second frame.

21. The method of claim 1, further comprising:

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

22. 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;

when the first difference exceeds the threshold, computing an edge difference between the first frame and the second frame; and

determining whether the first frame and the second frame comprise a shot boundary based on the edge difference.

23. The method of claim 22, further comprising:

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

24. The method of claim 23, 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.

25. The method of claim 22, further comprising:

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

26. The method of claim 22, further comprising:

generating an edge histogram; and

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

27. 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;

when the first difference exceeds the threshold, computing a color difference between the first frame and the second frame; and

determining whether the first frame and the second frame comprise a shot boundary based on the color difference.

28. The method of claim 27, further comprising:

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

29. The method of claim 28, 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.

30. The method of claim 27, further comprising:

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

31. The method of claim 27, further comprising:

generating an color histogram; and

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

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

computing a first difference between a first frame and a distant frame;

determining whether the first difference exceeds a first threshold;

if the first difference exceeds the first threshold, computing an edge difference or a color difference between the first frame and the distant frame;

determining whether a candidate shot boundary exists between the two frames based on the edge difference or the color difference;

when a candidate shot boundary exists, using a step variable technique to locate the actual boundary between two consecutive frames.

33. The method of claim 32, wherein the first difference is determined using a partial block-based comparison technique.

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; and

when the first difference exceeds the threshold,

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

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

determine whether the first frame and the second frame comprise a shot boundary based on the value of the edge difference or color difference.

35. The system of claim 34, further comprising:

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

36. A system, comprising:

a video camera recording a sequence of frames;

a computer with a processor and a memory, wherein the sequence of frames is stored in the memory of the computer; and

means for detecting a shot boundary based on a color difference or an edge difference between a first frame and a second frame in the sequence of frames.

37. The system of claim 36, further comprising:

means for determining a first difference between the first frame and the second frame.

38. The system of claim 37, further comprising:

means for, if the first difference exceeds a first threshold, detecting an abrupt break.

39. The system of claim 37, further comprising:

means for, if the first difference exceeds a second threshold, detecting a gradual transition.

40. A system, comprising:

a camera including a processor and memory;

a sequence of frames captured by the camera and stored in the memory; and

a program stored in the memory, wherein the program is executed by the processor to detect a shot boundary based on a color difference or an edge difference between a first frame and a second frame in the sequence of frames.

41. A computer readable storage medium encoded with software instructions, wherein execution of the instructions comprises:

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

determining whether the first difference exceeds a threshold; and

when the first difference exceeds the threshold,

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

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

determining whether the first frame and the second frame comprise a shot boundary based on the value of the edge difference or color difference.

42. The computer readable storage medium of claim 41, wherein execution of the instructions to compute an edge difference further comprises:

generating an edge histogram.

43. The computer readable storage medium of claim 41, wherein execution of the instructions to compute a color difference further comprises:

generating a color histogram.

44. The computer readable storage medium of claim 41, wherein execution of the instructions further comprises:

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

45. The computer readable storage medium of claim 44, wherein execution of the instructions further comprises:

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.

46. The computer readable storage medium of claim 41, wherein execution of the instructions further comprises:

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