Method and system for real time feature based motion analysis for key frame selection from a video

• US 6,252,975 B1
• Filed: 12/17/1998
• Issued: 06/26/2001
• Est. Priority Date: 12/17/1998
• Status: Expired due to Term

• Current Assignee: Majandro LLC (IP Edge LLC)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Bozdagi, Gozde, Bryll, Robert
• Primary Examiner(s): Johns, Andrew W.
• Assistant Examiner(s): NAKHJAVAN, SHERVIN K
• Application Number:
  US09/215,594
• Time in Patent Office: 922 Days
• Field of Search: 382/100, 382/103, 382/107, 382/190, 382/194, 382/195, 382/203, 382/236, 382/238, 382/282, 382/283, 382/268, 382/270, 382/274, 382/291, 348/26, 348/169, 348/180, 348/426, 348/439, 348/441, 348/572, 348/573, 348/575, 348/576, 348/577, 348/700, 348/701, 345/326, 345/327, 345/333
• US Class Current: 382/107
• CPC Class Codes: G06F 16/786 using motion, e.g. object motion or camera motion
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• 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

Abstract

A method and system for real time converting a dynamic video to a set of static image frames includes segmenting the video into a plurality of frames. Significant parts of the frames are selected to comprise interest points. An operator estimates a motion trajectory of the interest points for real time computing of a global motion. Upon detection of global motion, selected key frames are selected from the set of static frames to represent the dynamic video. Interest points are identified as areas of high gradient and are further minimized by limiting interest points by imposing a grid on image frame and limiting the interest points to one point per grid cell.

Claims

1. A method of real time converting a dynamic video to a set of static image frames comprising steps of:

digitizing the video into a plurality of frames;

automatically selecting in real time significant parts of the frames comprising interest points, wherein the selecting significant parts comprises distributing the interest points through each of the frames;

identifying a global motion by real time computing of changes to the interest points; and

,

selecting from the frames including the global motion, key frames comprising the set of static frames representative of the dynamic video.

2. The method of claim 1 wherein the selecting significant parts comprises identifying an area of high gradient.

3. The method of claim 1 wherein the distributing includes dividing the frames into a grid of frame cells.

4. The method of claim 3 wherein the selecting significant parts comprises selecting a single interest point per cell portion.

5. The method of claim 1 wherein the identifying a global motion comprises estimating a constant intensity of an interest point along a motion trajectory in a predetermined time period.

6. The method of claim 5 wherein the estimating includes representing the motion trajectory with a plurality of affine parameters of a selected optical flow equation.

7. The method of claim 6 wherein the estimating includes thresholding the affine parameters.

8. The method of claim 7 wherein the estimating includes a comparing of the affine parameters after the thresholding for detecting a pattern representative of the global motion.

9. The method of claim 8 wherein the selecting the key frames includes capturing the frames during a detected pattern at a predetermined rate during a time period of the global motion.

10. The method of claim 1 wherein the identifying the global motion includes identifying video sequences comprising panning, zooming and abrupt scene cuts.

11. A method of selecting key frames from a video whereby the key frames will comprise a sequence of static images representative of the video, including steps of:

receiving a stream of data into a processing device wherein the stream is representative of the video;

segmenting the stream into a sequence of frames comprising pixels corresponding to an image of the video;

selecting certain pixels from the frames associated with significant features of the image;

comparing the certain pixels over a selected time period for identification of a global motion; and

,

selecting the key frames from the sequence of frames based upon the identified global motion.

12. The method as described in claim 11 wherein the comparing of the certain pixels is contemporaneous with the receiving of the stream of data for real time selecting of the key frames by the processing device.

13. The method as described in claim 12 wherein the selecting certain pixels comprises identifying pixels having a high gradient difference from adjacent pixels.

14. The method as described in claim 12 wherein the comparing comprises computing an error estimation of a constant pixel intensity along a motion trajectory.

15. The method as described in claim 14 wherein the computing includes thresholding the error estimations.

16. A system for converting a video into a representation thereof comprised of a compilation of static key frames, including:

means for segmenting the video into a plurality of static frames comprised of a plurality of pixels;

means for selecting significant interest pixels from the plurality;

means for determining from the significant interest pixels whether a successive set of the static frames is imaging a global motion; and

,

means for selecting the static key frames from the static frames based upon the determined global motion.

17. The system as defined in claim 16 wherein the means for selecting significant interest pixels includes means for identifying pixels at high gradient locations.