Method and apparatus for video digest generation

• US 8,224,087 B2
• Filed: 07/16/2007
• Issued: 07/17/2012
• Est. Priority Date: 07/16/2007
• Status: Active Grant

• Current Assignee: Vdoqwest, Inc.
• Original Assignee: Novafora, Inc.
• Inventors: Bronstein, Michael, Bronstein, Alex, Rakib, Shlomo S., Matatyaou, Asaf
• Primary Examiner(s): Desire, Gregory M
• Application Number:
  US11/778,633
• Publication Number:
  US 20090025039A1
• Time in Patent Office: 1,828 Days
• Field of Search: 382/170, 725/32, 725/36, 725/38, 725/42
• US Class Current: 382/170
• CPC Class Codes: G06F 16/739 in form of a video summary, e.g. the video summary being a video sequence, a composite still image or having synthesized frames
• CPC Class Codes: G06F 16/7837 using objects detected or recognised in the video content
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• CPC Class Codes: G06V 20/47 Detecting features for summarising video content
• CPC Class Codes: H04N 21/4334 Recording operations recording of a television signal H04N5/76; arrangements for recording or accumulating broadcast information or broadcast-related information H04H60/27
• CPC Class Codes: H04N 21/4348 Demultiplexing of additional data and video streams
• CPC Class Codes: H04N 21/4402 involving reformatting operations of video signals for household redistribution, storage or real-time display details of conversion of video standards at pixel level H04N7/01; video transcoding H04N19/40; adapting incoming signals to the display format of the display terminal G09G5/005; media handling at the source in data packet switching networks H04L65/764
• CPC Class Codes: H04N 21/4532 involving end-user characteristics, e.g. viewer profile, preferences monitoring of user activities for profile generation for accessing a video database G06F16/739; user profiles in network data switching protocols H04L67/306; processing of user preferences or user profiles in wireless networks H04W8/18
• CPC Class Codes: H04N 21/8456 by decomposing the content in the time domain, e.g. in time segments

Abstract

The present invention is a video digest which extracts only the relevant information out of the video content according to user preferences. Video digest generator is a combination of hardware and software constituting a component of the digital video recorder, which analyzes the content and extracts only the portions which are meaningful or important for the user.

Claims

1. A method of using a video digest generator device for automated generation of a metadata related to video content from at least a plurality of at least ten sequential frames, comprising the steps of:

inputting the plurality of sequential frames;

identifying a plurality of video elements from the sequential frames of the video content, each of the video elements including a spatio-temporal group of contiguous pixels spanning at least some of the plurality of sequential frames, wherein the spatio-temporal group of contiguous pixels includes 3 dimensions in which 2 dimensions are 2 spatial axes and 1 dimension is a temporal axis, and wherein the 2 spatial axes form a plane corresponding to a video frame, and the temporal axis corresponds to time over which different ones of the video frames occur;

operating upon various ones of the video elements to obtain a plurality of video aggregates, each video aggregate including an aggregate spatio-temporal group of contiguous pixels spanning at least certain ones of the plurality of sequential frames, and wherein at least some of the video aggregates include more than one video element therein; and

assigning a rating to each video aggregates, the step of assigning including, for certain ones of the video aggregates, calculating a similarity or a dissimilarity based upon a similarity algorithm or a dissimilarity algorithm, respectively, thereby obtaining the metadata related to the video content; and

using said metadata to control, in conjunction with input from the user of a Digital Video Recorder or other device that displays video content, and/or factory default information, the operation of said Digital Video Recorder or other device that displays said video content.

2. A method according to claim 1 further including the steps of:

selecting a plurality of video aggregates from the metadata to obtain a digest of video content; and

presenting the digest to an end user for visual display.

3. A method according to claim 2, wherein the step of selecting video aggregates includes the steps of arranging various ones of the video aggregates through a user interface to obtain the video digest.

4. A method according to claim 3, wherein the selected video aggregates are arranged to be displayed sequentially.

5. A method according to claim 3, wherein the user interface provides hyperlinks between video aggregates and their corresponding original video content.

6. A method according to claim 3, wherein the selected video aggregates are arranged to be displayed simultaneously.

7. A method according to claim 3 wherein the step of selecting includes the step of sorting each of the video aggregates according to their rating.

8. The method according to claim 2 wherein the video digest includes a plurality of frames, and further including the step of navigating through the plurality of frames using temporal zooming.

9. The method according to claim 8 wherein the temporal zooming includes the step of determining which video aggregates are unimportant based upon the rating.

10. The method according to claim 9 wherein the step of determining is further based upon a desired total time for the video digest.

11. The method according to claim 9 wherein the temporal zooming is user adjustable, based upon a user selection of a zoom up button and a zoom down button.

12. The method according to claim 2 wherein the video digest includes a plurality of frames, and further including the step of navigating through the plurality of frames using spatial zooming.

13. The method according to claim 12 wherein the spatial zooming is obtained by automatically rendering selected ones of the video aggregates to a display size.

14. The method according to claim 13 wherein the step of navigating further includes user adjustable magnification and panning of the automatically rendered selected ones of the video aggregates.

15. The method according to claim 2 wherein the video digest includes a plurality of frames, and further including the step of navigating through the plurality of frames using temporal zooming and spatial zooming.

16. The method according to claim 15 wherein the temporal zooming includes the step of determining which video aggregates are unimportant based upon the rating.

17. The method according to claim 16 wherein the step of determining is further based upon a desired total time for the video digest.

18. The method according to claim 15 wherein the temporal zooming is user adjustable, based upon a user selection of a zoom up button and a zoom down button.

19. The method according to claim 18 wherein the spatial zooming is obtained by automatically rendering selected ones of the video aggregates to a display size.

20. The method according to claim 19 wherein the step of navigating further includes user adjustable magnification and panning of the automatically rendered selected ones of the video aggregates.

21. A method according to claim 1, wherein the step of operating includes the step of defining each of the video aggregates as a three-dimensional rectangular block of pixels wherein each side of the three-dimensional block is parallel to one of the axes and wherein each three-dimensional rectangular block includes therein at least one corresponding video element.

22. A method according to claim 1, wherein a plurality of video elements are overlapping, and wherein the overlapping video elements, in the step of operating, form a single video aggregate.

23. A method according to claim 1, wherein a plurality of video elements are non-overlapping and wherein the non-overlapping video elements, in the step of operating, form distinct video aggregates.

24. A method according to claim 1, wherein the step of identifying the plurality of video elements includes identifying continuously appearing pre-defined objects in consecutive frames.

25. A method according to claim 24, wherein objects includes human faces, human body parts, nudity contents, texture patterns, and texts.

26. A method according to claim 1, wherein the step of identifying the plurality of video elements includes identifying rectangular three-dimensional blocks of pixels.

27. A method according to claim 26, wherein the rectangular three-dimensional blocks of pixels are overlapping.

28. A method according to claim 26, wherein the rectangular three-dimensional blocks of pixels are non-overlapping.

29. A method according to claim 1, wherein the step of identifying the plurality of video elements includes the step of detecting objects with properties known a priori.

30. A method according to claim 1, wherein the step of identifying the plurality of video elements includes the step of identifying three-dimensional irregularly-shapes regions of pixels utilizing edge detection.

31. A method according to claim 1, wherein the step of identifying the plurality of video elements includes the step of detecting an object with consistent motion.

32. A method according to claim 31, wherein the step of detecting an object with consistent motion include the step of utilizing motion vector information.

33. A method according to claim 31, wherein the step of detecting an object with consistent motion includes the step of occlusion detection.

34. A method according to claim 1, wherein the step of calculating a similarity or dissimilarity includes the step of applying the similarity algorithm or the dissimilarity algorithm to video elements that are contained in the video aggregate.

35. A method according to claim 34, wherein the applying of the similarity algorithm or the dissimilarity algorithm includes the step of comparing a video element to an example video element and returning quantified results.

36. A method according to claim 35, wherein the example video element includes at least one of a positive example and a negative example.

37. A method according to claim 36, wherein the example video elements are obtained from user interactions, from the video elements, or from predefined elements.

38. A method according to claim 37, wherein the user interactions are performed during preview of recorded or broadcast content.

39. A method according to claim 36, wherein positive example video elements are video elements to which a user devotes more time or attention.

40. A method according to claim 36, wherein negative example video elements are video elements being skipped or fast-forwarded by a user during preview.

41. A method according to claim 36, wherein each rating is proportional to negative example similarity distances and is inversely proportionate to positive example similarity distances.

42. A method according to claim 34, wherein the similarity algorithm or the dissimilarity algorithm uses at least one of a plurality of measures between video elements.

43. A method according to claim 42, wherein the at least one of the plurality of measures include earth moving distance (EMD), sum of absolute differences (SAD), and sum of squared differences (SSD).

44. A method according to claim 42, wherein the at least one of the plurality of measures is based on a comparison of motion vector histograms of video elements.

45. A method according to claim 42, wherein the at least one of the plurality of measures is based on comparison of pixel intensity histogram.

46. A method according to claim 42, wherein the at least one of the plurality of measures is based on comparison of pixel intensity histogram obtained in time and frequency domains.

47. A method according to claim 1, wherein the steps of identifying video elements and assigning are an iterative process to refine the identified video elements.

48. A method according to claim 1, wherein at least some of the video aggregates are provided in a format that can be displayed.

49. A method according to claim 48, wherein the at least some of the video aggregates are bounded by a spatio-temporal bounding box or a temporal bounding box.

50. A method according to claim 48, wherein a particular video aggregate contains one or a sequence of images that temporally occur before a particular video element corresponding thereto.

51. A method according to claim 50, wherein the particular video aggregate contains one or a sequence of images that temporally occur after the particular video element corresponding thereto.

52. A method according to claim 48, wherein each video aggregate is assigned a particular rating aggregated from the ratings of video elements contained therein.

53. A method according to claim 52, wherein the rating of one of the video aggregates is the sum over the ratings of video elements contained therein.

54. A method according to claim 52, wherein the rating of one of the video aggregates is the maximum over the ratings of video elements contained therein.

55. A method according to claim 52, wherein the rating of one of the video aggregates is the minimum over the ratings of video elements contained therein.

56. A method according to claim 52, wherein the rating of one of the video aggregates is the average of the ratings of video elements contained therein.

57. The method of claim 1, in which the video digest generator device is a combination of hardware and software constituting a component of a digital video recorder device.

58. A method using a video digest generator device for the presentation of a video digest of video content based upon predetermined metadata related to the video content, comprising the steps of:

providing the metadata, the metadata including a plurality of video aggregates each having a rating corresponding thereto, wherein each video aggregate includes an aggregate spatio-temporal group of contiguous pixels spanning at least certain ones of a plurality of sequential frames, wherein at least some of the video aggregates include more than one video element therein, each video element including a spatio-temporal group of contiguous pixels spanning at least some of the plurality of sequential frames, wherein the spatio-temporal group of contiguous pixels includes 3 dimensions in which 2 dimensions are 2 spatial axes and 1 dimension is a temporal axis, and wherein the 2 spatial axes form a plane corresponding to a video frame, and the temporal axis corresponds to time over which different ones of the video frames occur, and wherein the rating includes a calculated similarity or dissimilarity based upon a similarity algorithm or a dissimilarity algorithm;

selecting from the metadata to obtain the digest of video content; and

presenting the video digest to an end user for visual display;

wherein said end user is the user of a Digital Video Recorder or other device that displays video content;

and further using said metadata to control, in conjunction with either input from said end user, and/or factory default information, the operation of said Digital Video Recorder or other device that displays said video content.

59. A method according to claim 58, wherein the step of selecting includes the steps of sorting and arranging various ones of the video aggregates through a user interface to obtain the digest.

60. A method according to claim 59, wherein the video aggregates are arranged to be displayed sequentially.

61. A method according to claim 59, wherein the user interface provides hyperlinks between video aggregates and their corresponding original video content.

62. A method according to claim 59, wherein the video aggregates are arranged to be displayed simultaneously.

63. A method according to claim 59, wherein the step of selecting includes the step of sorting each of the video aggregates according to their rating.

64. The method according to claim 58 wherein the video digest includes a plurality of frames, and further including the step of navigating through the plurality of frames using temporal zooming.

65. The method according to claim 58 wherein the temporal zooming includes the step of determining which video aggregates are unimportant based upon the rating.

66. The method according to claim 65 wherein the step of determining is further based upon a desired total time for the video digest.

67. The method according to claim 65 wherein the temporal zooming is user adjustable, based upon a user selection of a zoom up button and a zoom down button.

68. The method according to claim 58 wherein the video digest includes a plurality of frames, and further including the step of navigating through the plurality of frames using spatial zooming.

69. The method according to claim 68 wherein the spatial zooming is obtained by automatically rendering selected ones of the video aggregates to a display size.

70. The method according to claim 69 wherein the step of navigating further includes user adjustable magnification and panning of the automatically rendered selected ones of the video aggregates.

71. The method according to claim 58 wherein the video digest includes a plurality of frames, and further including the step of navigating through the plurality of frames using temporal zooming and spatial zooming.

72. The method according to claim 71 wherein the temporal zooming includes the step of determining which video aggregates are unimportant based upon the rating.

73. The method according to claim 72 wherein the step of determining is further based upon a desired total time for the video digest.

74. The method according to claim 71 wherein the temporal zooming is user adjustable, based upon a user selection of a zoom up button and a zoom down button.

75. The method according to claim 74 wherein the spatial zooming is obtained by automatically rendering selected ones of the video aggregates to a display size.

76. The method according to claim 75 wherein the step of navigating further includes user adjustable magnification and panning of the automatically rendered selected ones of the video aggregates.

77. A method according to claim 58, further providing at least one audio stream that is synchronized with a plurality of sequential frames.

78. A method according to claim 77, wherein the at least one audio stream includes a sequence of sampled audio digital signals.

79. A method according to claim 78, further identifying a plurality of audio elements from the at least one audio stream, wherein each of the audio elements includes a block of sampled audio digital signals that is derived from the sequence of sampled audio digital signals.

80. A method according to claim 79, wherein the step of identifying the plurality of audio elements includes the step of detecting uniform blocks of sampled audio digital signals.

81. A method according to claim 79, wherein the step of identifying the plurality of audio elements includes the step of detecting pre-defined audio patterns in the sequence of sampled audio digital signals.

82. A method according to claim 81, wherein the audio patterns include shots, human speeches, words, and music.

83. A method according to claim 79, further operating upon various ones of the audio elements to obtain a plurality of audio aggregates.

84. A method according to claim 83, wherein at least one of a plurality of audio aggregates contains a continuous sequence of sampled audio digital signals around the block thereof.

85. A method according to claim 79, further assigning a rating to each audio element.

86. The method of claim 58, in which the video digest generator device is a combination of hardware and software constituting a component of a digital video recorder device.