System for selecting a keyframe to represent a video

• US 20050002452A1
• Filed: 07/26/2004
• Published: 01/06/2005
• Est. Priority Date: 01/29/1999
• Status: Active Grant

• Current Assignee: Frederic Dufaux, Michael J. Swain
• Original Assignee: Frederic Dufaux, Michael J. Swain
• Inventors: Swain, Michael J., Dufaux, Frederic
• Granted Patent: US 7,643,657 B2
• Time in Patent Office: Days
• US Class Current: 375/240.10
• CPC Class Codes: G06F 16/785 using colour or luminescence
• CPC Class Codes: G11B 2220/41 Flat as opposed to hierarchical combination, e.g. library of tapes or discs, CD changer, or groups of record carriers that together store one title

Abstract

A key frame representative of a sequence of frames in a video file is selected. The sequence of frames is divided into shots, sequences of frames captured by a single continuous operation of the camera, by detecting shot boundaries. Shot boundaries are detected by measuring changes in motion activity between frames using measures of pixel intensity and histogram differences between frames. The most interesting shot in the sequence of frames is selected using measures of motion activity, spatial activity, skin pixel color and shot length. The key frame is selected in the most interesting shot using measures of spatial activity and motion activity.

Claims

1. A method of extracting a key frame from a sequence of frames comprising the steps of:

detecting shot boundaries in the sequence of frames;

selecting a key shot from shots within the detected shot boundaries; and

selecting a key frame in the selected key shot.

2. A method as claimed in claim 1 wherein the step of detecting shot boundaries is based on pixel-wise frame difference.

3. A method as claimed in claim 2 wherein the step of detecting shot boundaries is based on distribution of a luminance histogram.

4. A method as claimed in claim 3 wherein the step of detecting shot boundaries is based on luminance.

5. A method as claimed in claim 4 wherein the step of detecting shot boundaries is based on a discontinuity in pixel-wise frame difference.

6. A method as claimed in claim 5 wherein the step of detecting shot boundaries is dependent on the result of a first test to determine if the maximum of a forward discontinuity in pixel-wise frame difference and a backward discontinuity in pixel-wise frame difference relative to a distribution of a luminance histogram is greater than a first threshold value.

7. A method as claimed in claim 6 wherein the step of detecting shot boundaries is dependent on the result of a second test to determine if the maximum of a forward discontinuity in pixel-wise frame difference and a backward discontinuity in pixel-wise frame difference relative to a distribution of a luminance histogram is greater than a second threshold value, which is less than the first threshold, and the minimum of a forward discontinuity in pixel-wise frame difference and a backward discontinuity in pixel-wise frame difference relative to a distribution of a luminance histogram is less than a third threshold value which is less than the second threshold.

8. A method as claimed in claim 1 wherein the step of selecting a key shot is based on level of skin color pixels.

9. A method as claimed in claim 8 wherein the step of selecting a key shot is based on motion between frames.

10. A method as claimed in claim 8 wherein the step of selecting a key shot is based on spatial activity within frames.

11. A method as claimed in claim 8 wherein the step of selecting a key shot is selected based on shot length.

12. A method as claimed in claim 8 wherein the step of selecting a key shot is based on motion between frames, spatial activity within frames, level of skin pixels and shot length.

13. A method as claimed in claim 1 wherein the step of selecting a key frame is based on frame activity.

14. A method as claimed in claim 13 wherein the step of selecting a key frame based on spatial activity within frame.

15. A method as claimed in claim 13 wherein the step of selecting a key frame is based on motion between frames.

16. A method of selecting a key shot from a sequence of shots based on the level of skin color pixels comprising:

determining the level of skin pixels of individual frames; and

selecting the key shot based on the level of skin pixels.

17. A method as claimed in claim 16 wherein the key shot is selected based on motion between frames.

18. A method as claimed in claim 16 wherein the key shot is selected based on spatial activity within frames.

19. A method as claimed in claim 16 wherein the key shot is selected based on shot length.

20. A method as claimed in claim 16 wherein the key shot is selected based on motion between frames, spatial activity within frames and shot length.

21. A method of selecting a key frame from a sequence of frames comprising:

determining frame activity of individual frames; and

selecting a key frame based on the frame activity.

22. A method as claimed in claim 21 wherein the frame activity is based on spatial activity within each frame.

23. A method as claimed in claim 21 wherein the frame activity is based on motion between frames.

24. A method for extracting a key frame from a sequence of frames comprising the steps of:

detecting shot boundaries in the sequence of frames based on discontinuity in pixel-wise frame difference and distribution of a luminance histogram;

the result of a first test to determine if the maximum of a forward discontinuity in pixel-wise frame difference and a backward discontinuity in pixel-wise frame difference relative to a distribution of a luminance histogram is greater than a first threshold value and the result of a second test to determine if the maximum of a forward discontinuity in pixel-wise frame difference and a backward discontinuity in pixel-wise frame difference relative to a distribution of a luminance histogram is greater than a second threshold value and the minimum of a forward discontinuity in pixel-wise frame difference and a backward discontinuity in pixel-wise frame difference relative to a distribution of a luminance histogram is less than a third threshold value which is less than the second threshold;

selecting a key shot from shots within the detected shot boundaries dependent on level of skin color pixels and spatial activity within frames, motion between frames and shot length; and

selecting a key frame in the selected key shot dependent on frame activity based on spatial activity within the frame and motion between frames.

25. A world wide web search engine comprising:

a video analyzer which analyzes video accessed from the web and identifies a single representative keyframe from the video; and

a searchable index providing access to the keyframe over the internet.

26. A computer program product for extracting a key frame from a sequence of frames, the computer program product comprising a computer usable medium having computer readable code thereon, including program code which:

detects shot boundaries in the sequence of frames;

selects a key shot from shots within the detected shot boundaries; and

selects a key frame in the selected key shot.

27. A computer program product as claimed in claim 26 wherein the step of detecting shot boundaries is based on pixel-wise frame difference.

28. A computer program product as claimed in claim 27 wherein the step of detecting shot boundaries is based on distribution of a luminance histogram.

29. A computer program product as claimed in claim 28 wherein the step of detecting shot boundaries is based on luminance.

30. A computer program product as claimed in claim 29 wherein the step of detecting shot boundaries is based on a discontinuity in pixel-wise frame difference.

31. A computer program product as claimed in claim 30 wherein the step of detecting shot boundaries is dependent on the result of a first test to determine if the maximum of a forward discontinuity in pixel-wise frame difference and a backward discontinuity in pixel-wise frame difference relative to a distribution of a luminance histogram is greater than a first threshold value.

32. A computer program product as claimed in claim 31 wherein the step of detecting shot boundaries is dependent on the result of a second test to determine if the maximum of a forward discontinuity in pixel-wise frame difference and a backward discontinuity in pixel-wise frame difference relative to a distribution of a luminance histogram is greater than a second threshold value which is less than the first threshold and the minimum of a forward discontinuity in pixel-wise frame difference and a backward discontinuity in pixel-wise frame difference relative to a distribution of a luminance histogram is less than a third threshold value which is less than the second threshold.

33. A computer program product as claimed in claim 26 wherein the step of selecting a key shot is based on level of skin color pixels.

34. A computer program product as claimed in claim 33 wherein the step of selecting a key shot is based on motion between frames.

35. A computer program product as claimed in claim 33 wherein the step of selecting a key shot is based on spatial activity within frames.

36. A computer program product as claimed in claim 33 wherein the step of selecting a key shot is selected based on shot length.

37. A computer program product as claimed in claim 33 wherein the step of selecting a key shot is based on motion between frames, spatial activity within frames and shot length.

38. A computer program product as claimed in claim 26 wherein the step of selecting a key frame is based on frame activity.

39. A computer program product as claimed in claim 38 wherein the step of selecting a key frame based on spatial activity within frame.

40. A computer program product as claimed in claim 38 wherein the step of selecting a key frame is based on motion between frames.

41. A computer program product for selecting a key shot from a sequence of shots based on the level of skin color pixels, the computer program product comprising a computer usable medium having computer readable code thereon, including program code which:

determines the level of skin pixels of individual frames; and

selects the key shot based on the level of skin pixels.

42. A computer program product as claimed in claim 41 wherein the key shot is selected based on motion between frames.

43. A computer program product as claimed in claim 41 wherein the key shot is selected based on spatial activity within frames.

44. A computer program product as claimed in claim 41 wherein the key shot is selected based on shot length.

45. A computer program product as claimed in claim 41 wherein the key shot is selected based on motion between frames, spatial activity within frames and shot length.

46. A computer program product for selecting a key frame from a sequence of frames, the computer program product comprising a computer usable medium having computer readable code thereon, including program code which:

determines frame activity of individual frames; and

selects a key frame based on the frame activity.

47. A computer program product as claimed in claim 46 wherein the frame activity is based on spatial activity within each frame.

48. A computer program product as claimed in claim 46 wherein the frame activity is based on motion between frames.

49. An apparatus for extracting a key frame from a sequence of frames, comprising:

a keyframe extractor routine;

means, within the keyframe extractor routine, for detecting shot boundaries in the sequence of frames;

means, within the keyframe extractor routine, for selecting a key shot from shots within the detected shot boundaries; and

means, within the keyframe extractor routine, for selecting a key frame in the selected key shot.

50. An apparatus as claimed in claim 49 wherein the means for detecting shot boundaries is based on pixel-wise frame difference and distribution of a luminance histogram.

51. An apparatus as claimed in claim 49 wherein the means for selecting a key shot is based on motion between frames, spatial activity within frames, level of skin pixels and shot length.

52. An apparatus as claimed in claim 49 wherein the means for selecting a key frame is based on frame activity.

53. An apparatus for extracting a key frame from a sequence of frames, comprising:

a keyframe extractor routine responsive to a request for extracting a keyframe from the sequence of frames, the extractor comprising;

a shot boundary detector detecting boundaries in the sequence of frames;

a key shot selection which selects a key shot from shots within the detected shot boundaries; and

a key frame selector which selects a key frame in the selected key shot.

54. An apparatus as claimed in claim 53 wherein the shot boundary detector detects shot boundaries based on pixel-wise frame difference and distribution of a luminance histogram.

55. An apparatus as claimed in claim 53 wherein the key shot selector selects the key shot based on motion between frames, spatial activity within frames, level of skin pixels and shot length.

56. An apparatus as claimed in claim 53 wherein the key frame selector selects the key frame based on frame activity.

57. A computer system comprising:

a memory system; and

a keyframe extractor routine located in the memory system responsive to a request for extracting a key frame from a sequence of frames which;

detects shot boundaries in the sequence of frames;

selects a key shot from shots within the detected shot boundaries; and

selects a key frame in the selected key shot.

58. A computer system as claimed in claim 57 wherein the keyframe extractor detects shot boundaries based on pixel-wise frame difference and distribution of a luminance histogram.

59. A computer system as claimed in claim 57 wherein the keyframe extractor selects the key shot based on motion between frames, spatial activity within frames, level of skin pixels and shot length.

60. A computer system as claimed in claim 57 wherein the keyframe extractor selects the key frame based on frame activity.