Video object cut and paste

• US 20070003154A1
• Filed: 07/01/2005
• Published: 01/04/2007
• Est. Priority Date: 07/01/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sun, Jian, Shum, Heung-Yeung, Li, Yin
• Granted Patent: US 7,609,888 B2
• Time in Patent Office: Days
• US Class Current: 382/254
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/20072 Graph-based image processing
• CPC Class Codes: G06T 2207/20104 Interactive definition of region of interest [ROI]
• CPC Class Codes: G06T 2207/20152 Watershed segmentation
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/162 involving graph-based methods
• CPC Class Codes: G06V 40/103 Static body considered as a whole, e.g. static pedestrian or occupant recognition

Abstract

Video object cutting and pasting is described. In one implementation, pre-segmentation of video frames into regions is performed prior to a 3-D graph cut segmentation. The 3-D graph cut segmentation uses temporal coherence and a global color model to achieve accuracy of video object boundaries. A 2-D local graph cut segmentation can then be used to refine the boundaries. The boundaries can be tracked within a user-selected sequence of windows and refined using a local color model.

Claims

1. A method, comprising:

dividing frames of a video sequence into regions prior to applying a 3-D graph cut segmentation for designating an outline of a video object in the video sequence;

constructing a 3-dimensional graph including embedding temporal coherence in the 3-dimensional graph by forming associations between corresponding regions in adjacent video frames;

applying the 3-D graph cut segmentation to the 3-dimensional graph according to a global color model to derive a binary segmentation representing the outline of the video object; and

applying a 2-D graph cut segmentation to at least some of the binary segmentation according to a local color model to obtain a refined outline of the video object.

2. The method as recited in claim 1, wherein the dividing frames of a video sequence into regions includes pre-segmenting the video sequence using a watershed technique.

3. The method as recited in claim 1, further comprising applying a modified coherent matting technique to the binary segmentation to obtain a matte sequence for cutting the video object from the video sequence.

4. The method as recited in claim 3, further comprising cutting the video object from the video sequence and pasting the video object into a different video sequence.

5. The method as recited in claim 1, further comprising receiving a window selection input, wherein the window selection input designates part of a video frame of the video sequence;

automatically generating a temporal sequence of windows within the video sequence based on the window selection input; and

applying the 2-D graph cut segmentation within the sequence of windows; and

limiting the local color model to colors within the sequence of windows.

6. A method, comprising:

pre-segmenting frames of a video sequence into regions;

selecting two model frames of the video sequence, wherein each of the two model frames has a foreground representing a video object, and a background;

constructing a 3-dimensional (3-D) graph from a 3-D volume of the frames temporally bounded by the two model frames, including

associating regions on a single frame with adjacent regions on the same frame and

associating the regions on the single frame with candidate corresponding regions on adjacent frames; and

segmenting the 3-D graph into associated foreground regions and associated background regions according to a global color model, wherein the associated foreground regions represent the video object in the frames of the video sequence.

7. The method as recited in claim 6, wherein pre-segmenting frames uses one of a watershed technique or a tobogganing technique.

8. The method as recited in claim 6, wherein the associating the regions on the single frame with candidate corresponding regions on adjacent frames further includes associating a region on the single frame with regions on the adjacent frames that lie within a given radius of a likely corresponding position of the region on the adjacent frames.

9. The method as recited in claim 6, wherein the associating the regions on the single frame with candidate corresponding regions on adjacent frames further includes associating regions on the single frame with regions on the adjacent frames according to a color energy comparison between the regions on the single frame and the regions the adjacent frames.

10. The method as recited in claim 6, wherein the segmenting the 3-D graph into associated foreground regions and associated background regions is achieved by minimizing an energy function of the 3-D graph.

11. The method as recited in claim 10, wherein the energy function to be minimized is represented by

$\begin{array}{c}E\end{array}$

( X ) = ⁢

∑

r ∈

V ⁢

E 1 ⁡

( x r ) + λ

1 ⁢

∑

( r , s ) ∈

A I ⁢

E 2 ⁡

( x r , x s ) + ⁢

λ

2 ⁢

∑

( r , s ) ∈

A T ⁢

E 3 ⁡

( x r , x s )

where x_r and x_s are foreground/background labels of region r and s respectively;

X={x_r;

∀

_r};

E₁ represents the conformity of a color of region r to a foreground/background color model associated with the color information in the two model frames;

E₂ represents color differences between two adjacent regions in the same frame;

E₃ represents color differences between two regions in two adjacent frames; and

λ

₁ and λ

₂ are constants.

12. The method as recited in claim 6, wherein the global color model includes foreground/background color distributions derived globally from the two model frames.

13. The method as recited in claim 6, further comprising:

specifying a video tube portion of the 3-D graph, wherein the video tube comprises a part of a video frame and corresponding parts of other video frames of the video sequence; and

applying a local color model to a 2-dimensional (2-D) graph cut segmentation within the video tube portion to refine a boundary between the foreground regions and the background regions with the video tube.

14. The method as recited in claim 13, wherein the specifying a video tube portion further includes specifying a first video tube window on a first frame and a second video tube window on a second frame, wherein at least one of the two model frames is between the first frame and the second frame.

15. The method as recited in claim 14, further comprising bidirectionally tracking one of the first or second windows through a part of the video sequence to automatically generate additional windows of the video tube on frames between the first frame and the second frame.

16. The method as recited in claim 13, further comprising applying a 2-D graph cut segmentation to each window of the video tube portion using local foreground and background color models derived from colors of one of the video tube windows in one of the two model frames.

17. The method as recited in claim 16, further comprising seamlessly connecting a refined boundary in a video tube window to a preexisting boundary adjacent to the video tube window.

18. The method as recited in claim 15, further comprising overriding the 3-D segmentation and the 2-D segmentation by manually assigning foreground and background pixels of a video frame after one of the 3-D segmentation or the 2-D segmentation have taken place.

19. The method as recited in claim 6, further comprising applying a modified coherent matting technique to separate the foreground regions from the background regions.

20. A system, comprising:

means for determining visual regions that endure from frame to frame within a video sequence;

means for building a 3-dimensional graph from the regions of the video sequence;

means for embedding temporal coherence in the 3-dimensional graph by including associations between corresponding regions in adjacent frames of the video sequence;

means for applying a 3-dimensional graph cut segmentation to the 3-dimensional graph, based on global colors of the video sequence, in order to obtain segmentation results;

means for designating a local part of the segmentation results; and

means for applying a 2-dimensional graph cut segmentation to the local part based on local colors of the local part.