Frame decimation for structure from motion

• US 20010031005A1
• Filed: 03/15/2001
• Published: 10/18/2001
• Est. Priority Date: 03/24/2000
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Einarsson, Torbjorn, Nister, David
• Granted Patent: US 6,952,212 B2
• Time in Patent Office: Days
• US Class Current: 375/240.16
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/269 using gradient-based methods
• CPC Class Codes: G06T 7/579 from motion

Abstract

A preprocessing mechanism automatically processes a video sequence in order to obtain a set of views suitable for structure from motion (SaM) processing. The preprocessor employs a frame decimation algorithm which removes redundant frames within the video sequence based on motion estimation between frames and a sharpness measure. The motion estimation can be performed either globally or locally. The preprocessor can be configured to process static video sequences (i.e., previously acquired/captured) to select a minimal subsequence of sharp views form the video sequence, or to process the frames of a video sequence as they are being captured to discard frames which are redundant. In either configuration, the goal of the preprocessor is to select a minimal sequence of sharp views tailored for SaM processing.

Claims

1. A method for preprocessing a video sequence, the method comprising the steps of:

receiving the video sequence; and

generating a set of views suitable for algorithmic processing by performing frame decimation on the video sequence.

2. The method according to

claim 1

, wherein said frame decimation comprises the steps of:

identifying redundant frames in the video sequence; and

deleting any frames which are identified as redundant.

3. The method according to

claim 2

, wherein the step of identifying redundant frames in the video sequence comprises the steps of:

calculating whether a frame is essential for connectivity of the video sequence; and

identifying the frame as redundant when the frame is determined not to be essential for connectivity of the video sequence.

4. The method according to

claim 2

, wherein said step of identifying redundant frames comprises the steps of:

determining a motion estimation between the frames in the video sequence; and

identifying a frame as redundant if the motion estimation yields a final correlation coefficient above a predetermined threshold.

5. The method according to

claim 4

, wherein the motion estimation is a global motion estimation.

6. The method according to

claim 4

, wherein the motion estimation is a local motion estimation.

7. The method according to

claim 1

further comprising the steps of:

determining shot boundaries of the video sequence;

dividing the video sequence into at least one subsequence of frames, wherein each of the at least one subsequence of frames corresponds to a particular shot in the video sequence;

identifying redundant frames in the at least one subsequence of frames; and

deleting from the at least one subsequence of frames any frames which are identified as redundant.

8. The method according to

claim 7

, wherein the shot boundaries are provided by the camera which captured the video sequence.

9. The method according to

claim 7

, wherein the step of determining the shot boundaries comprises the steps of:

correlating adjacent frames in the video sequence after global motion compensation; and

identifying, for each pair of adjacent frames, the second frame in the pair as a beginning of a new shot based on the correlation between the frames in the pair.

10. The method according to

claim 1

, wherein the video sequence is received from a video capture device in real-time.

11. A method for capturing a video sequence, the method comprising the steps of:

receiving video from a video capture device as a sequence of frames;

for each frame in the sequence, determining whether or not to accept the frame; and

storing the accepted frames in a storage device.

12. The method according to

claim 11

, wherein the step of determining whether or not to accept a frame from the sequence of frames further comprises the steps of:

determining whether or not the frame is redundant; and

accepting the frame if it is determined not to be redundant.

13. The method according to

claim 12

, wherein the step of determining whether or not the frame is redundant comprises the steps of:

calculating a motion estimation between the frame and a previously accepted frame; and

identifying the frame as redundant if the motion estimation yields a final correlation coefficient above a predetermined threshold.

14. The method according to

claim 12

, wherein the step of determining whether or not the select frame is redundant comprises the steps of:

calculating a motion estimation between the frame and all the previously accepted frames; and

identifying the frame as redundant if the motion estimation yields a final correlation coefficient above a predetermined threshold.

15. The method according to

claim 11

, further comprising the steps of:

monitoring the rate at which accepted frames are provided to the storage device; and

providing an indication to the user of the video capture device to decrease the motion of the camera, if the storage device is unable to process the accepted frames at the current rate.

16. A method for processing a video sequence to produce a set of views suitable for Structure from Motion processing, the method comprising the steps of:

receiving a frame;

comparing the frame with at least one previously received frame; and

storing the received frame in a storage device when the comparison indicates that a difference between the frame and the at least one previously received frame is greater than a predetermined amount.

17. The method according to

claim 16

, wherein the difference indicates a motion between the at least one previously received frame and the received frame.

18. The method according to

claim 16

, wherein the frame is received from a video capture device in real-time.

19. The method according to

claim 16

, wherein the frame is received from a storage medium.

20. A system for preprocessing a video sequence to produce a set of views suitable for Structure from Motion processing, said system comprising:

a video sequence source;

a storage medium; and

a preprocessor, wherein the preprocessor is configured to perform frame decimation.

21. The system of

claim 20

, wherein the preprocessor comprises a data buffer for receiving the video sequences.

22. The system of

claim 21

, wherein the video sequence source is a video capture device.

23. The system of

claim 21

, wherein the video sequence source is a memory device.

24. The system of

claim 20

, wherein the storage device is a flash memory device.

25. The system of

claim 20

, wherein the frame decimation further comprises the steps of:

identifying redundant frames in the video sequence; and

deleting from the video sequence any frames which are identified as redundant.

26. The system of

claim 20

, wherein the frame decimation comprises the step of:

receiving a frame;

comparing the frame with at least one previously received frame; and

storing the received frame in a storage device when the comparison indicates that a difference between the frame and the at least one previously received frame is greater than a predetermined amount.

27. The system of

claim 26

, wherein the frame is received from a video capture device in real-time.

28. The system of

claim 22

, wherein the video sequence is received as a sequence of frames from a video capture device in real-time.