A computer-implemented method for automatically separating a video object from a background of a video sequence, the 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 (408, 410, 412, 414) on the same frame and associating the regions on the single frame with candidate corresponding regions on adjacent frames (416, 418, 420, 422, 424, 426, 428, 430); 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, and the segmenting the 3-D graph into associated foreground regions and associated background regions is achieved by minimizing at least one energy function of the 3-D graph,wherein the global color model includes foreground/background color distributions derived globally from key frames; specifying a video tube portion around a localized section of a boundary separating foreground and background regions of the 3-D graph, wherein the video tube comprises a rectangle of a video frame and corresponding parts of at least one other video frame of the video sequence, the corresponding parts corresponding to propagation of the rectangle; and applying a 2-dimensional, 2-D, graph cut segmentation within the video tube portion, using a local color model, to refine a boundary between the foreground regions and the background regions with the video tube, the local color model comprising color distributions from the parts of the video tube corresponding to key frames of the video sequence. 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 (408, 410, 412, 414) on the same frame and associating the regions on the single frame with candidate corresponding regions on adjacent frames (416, 418, 420, 422, 424, 426, 428, 430); and associating regions on a single frame with adjacent regions (408, 410, 412, 414) on the same frame and associating the regions on the single frame with candidate corresponding regions on adjacent frames (416, 418, 420, 422, 424, 426, 428, 430); 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, and the segmenting the 3-D graph into associated foreground regions and associated background regions is achieved by minimizing at least one energy function of the 3-D graph,wherein the global color model includes foreground/background color distributions derived globally from key frames; specifying a video tube portion around a localized section of a boundary separating foreground and background regions of the 3-D graph, wherein the video tube comprises a rectangle of a video frame and corresponding parts of at least one other video frame of the video sequence, the corresponding parts corresponding to propagation of the rectangle; and applying a 2-dimensional, 2-D, graph cut segmentation within the video tube portion, using a local color model, to refine a boundary between the foreground regions and the background regions with the video tube, the local color model comprising color distributions from the parts of the video tube corresponding to key frames of the video sequence.