Back to results
US 7,609,888 B2Granted
Separating a video object from a background of a video sequence
AssigneeMicrosoft Corporation
InventorsJian Sun, Heung-Yeung Shum, Yin Li
Life of this patent
Estimating the term…
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.
Claims18
A computer implemented method comprising:
- automatically separating a video object from a background of a video sequence via a processor performing operations comprising:
- pre-segmenting frames of the video sequence into regions;
- selecting two model frames of the video sequence via a user interface, wherein each of the two model frames has a foreground representing the video object, and said 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;
- segmenting the 3-D graph into associated foreground regions and associated background regions separated by a boundary according to a global color model, wherein the associated foreground regions represent the video object in the frames of the video sequence and wherein segmenting the 3-D graph into associated foreground regions and associated background regions is achieved by minimizing a plurality of energy functions of the 3-D graph, wherein:
- a first energy function represents the conformity of a color of a region to a foreground/background color model associated with the color information in the two model frame;
- a second energy function represents color differences between two adjacent regions in the same frame;
- and
- a third energy function represents color differences between two regions in two adjacent frames;
- specifying a video tube portion around a localized section of the boundary in the 3-D graph with the user interface, wherein the video tube comprises a subportion of a video frame and corresponding parts of at least one other video frame in 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 localized boundary between the foreground regions and the background regions.
9 more elements
A computer implemented method of automatically separating a video object from a background of a video sequence, comprising a processor performing:
- pre-segmenting frames of the video sequence into regions;
- selecting two model frames of the video sequence, wherein each of the two model frames has a foreground representing the video object, and said background;
- constructing a 3-dimensional (3-D) graph from a 3-D volume of the frames temporally bounded by the two model frames;
- segmenting the 3-D graph into associated foreground regions and associated background regions by minimizing an energy function of the 3-D graph, wherein the energy function to be minimized is represented by
- E
-
- (
- 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 xr and xs are foreground/background labels of region r and s respectively;
- X ={xr :∀r};
- E1 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;
- E2 represents color differences between two adjacent regions in the same frame;
- E3 represents color differences between two regions in two adjacent frames;
- and λ1 and λ2 are constants.
75 more elements
A computer implemented method of separating a video object from a background of a video sequence, a processor performing steps in the method comprising:
- pre-segmenting frames of the video sequence into regions;
- selecting two model frames of the video sequence via a user interface, wherein each of the two model frames has a foreground representing the video object, and said background;
- constructing a 3-dimensional (3-D) graph having two spatial dimensions and a third temporal dimension to form 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;
- segmenting the 3-D graph into associated foreground regions and associated background regions separated by a boundary according to a global color model, wherein the associated foreground regions represent the video object in the frames of the video sequence;
- refining a localized boundary between the video object and the background by a video tube engine by:
- specifying a subportion of at least one video frame in the 3-D graph;
- propagating the subportion across frames in the 3-D graph, defining a video tube;
- and
- applying a local color model to a local 2-dimensional (2-D) graph cut segmentation within the video tube;
- and
- seamlessly embedding the refined boundary into the existing segmentation by marking the pixels on the video tube boundary with a hard constraint.
8 more elements
Dependencies are inferred from the claim text.