Simultaneous optical flow estimation and image segmentation Number:7,522,749 from the United States Patent and Trademark Office (PTO) owispatent A technique for estimating the optical flow between images of a scene and a segmentation of the images is presented. This involves first establishing an initial segmentation of the images and an initial optical flow estimate for each segment of each images and its neighboring image or images. A refined optical flow estimate is computed for each segment of each image from the initial segmentation of that image and the initial optical flow of the segments of that image. Next, the segmentation of each image is refined from the last-computed optical flow estimates for each segment of the image. This process can continue in an iterative manner by further refining the optical flow estimates for the images using their respective last-computed segmentation, followed by further refining the segmentation of each image using their respective last-computed optical flow estimates, until a prescribed number of iterations have been completed.<H segmentation, Simultaneous, Simultaneous, op, 7522749.html, Patent, pto, 7522749

Title: Simultaneous optical flow estimation and image segmentation

Abstract: A technique for estimating the optical flow between images of a scene and a segmentation of the images is presented. This involves first establishing an initial segmentation of the images and an initial optical flow estimate for each segment of each images and its neighboring image or images. A refined optical flow estimate is computed for each segment of each image from the initial segmentation of that image and the initial optical flow of the segments of that image. Next, the segmentation of each image is refined from the last-computed optical flow estimates for each segment of the image. This process can continue in an iterative manner by further refining the optical flow estimates for the images using their respective last-computed segmentation, followed by further refining the segmentation of each image using their respective last-computed optical flow estimates, until a prescribed number of iterations have been completed.

Patent Number: 7,522,749 Issued on 04/21/2009 to Zitnick, III, et al.

Inventors: Zitnick, III; Charles (Seattle, WA), Kang; Sing Bing (Redmond, WA), Jojic; Nebojsa (Redmond, WA)
Assignee: Microsoft Corporation (Redmond, WA)

Appl. No.: 11/193,273

Filed: July 30, 2005

Related U.S. Patent Documents


Application Number	Filing Date	Patent Number	Issue Date
60669675	Apr., 2005

Current U.S. Class: 382/107 ; 382/103; 382/164; 382/173

Current International Class: G06K 9/00 (20060101)

Field of Search: 382/103,107,162,164,173 348/699

References Cited [Referenced By]

U.S. Patent Documents


5594504	January 1997	Ebrahimi
5748761	May 1998	Chang et al.
5929940	July 1999	Jeannin
6005625	December 1999	Yokoyama
6008865	December 1999	Fogel
6049619	April 2000	Anandan et al.
6385245	May 2002	De Haan et al.
6542639	April 2003	Konoshima et al.
6766037	July 2004	Le et al.
7039110	May 2006	Ernst et al.
2002/0090133	July 2002	Kim et al.
2004/0091170	May 2004	Cornog et al.
2004/0125877	July 2004	Chang et al.
2005/0226462	October 2005	Wittebrood et al.
2006/0023786	February 2006	Li et al.
2006/0177145	August 2006	Lee et al.
2007/0185946	August 2007	Basri et al.

Foreign Patent Documents


579319	Jan., 1994	EP

Other References

Michael G. Ross, "Exploiting Texture-Motion Duality in Optical Flow and Image Segmentation", Aug. 2000, Massachusetts Institute of Technology, pp. 33-46. cited by examiner .
Ayer, S., and H. Sawhney, Layered representation of motion video using robust maximum-likelihood estimation of mixture models and MDL encoding, Proc. of the 5.sup.th Int'l Conf. on Computer Vision, 1995, pp. 777-784. cited by other .
Black, M., and P. Anandan, The robust estimation of multiple motions: Parametric and piecewise-smooth flow fields, Comp. Vision and Image Understanding, 1996, vol. 63, No. 1, pp. 75-104. cited by other .
Black, M, and Y. Yacoob, A. Jepson and D. Fleet, Parameterized models of image motion, CVPR, 1997, pp. 561-567. cited by other .
Chang, M., A. Tekalp, and M. Sezan, Simultaneous motion estimation and segmentation, IEEE Trans. on Image Processing, 1997, vol. 6, pp. 1326-1333. cited by other .
Criminisi, A., P. Perez, and K. Toyama, Region filling an object removal by exemplar-based inpainting, IEEE Trans. on Image Processing, 2004, vol. 9, No. 13, pp. 1200-1212. cited by other .
Heisele, B., U. Krebel, and W. Ritter, tracking non-rigid, moving objects based on color cluster flow, CVPR, 1997, pp. 253-257. cited by other .
Horn, B., and B. Schunck, Determining optical flow, Artificial Intelligence, 1981, vol. 17, pp. 185-204. cited by other .
Jepson, A., and M. Black, Mixture models for optical flow computation, CVPR, 1993, pp. 760, 761. cited by other .
Kanna, A. N. Jojic, and B. Frey, Generative model for layers of appearance and deformation, AIStats, '05, 2005. cited by other .
Khan, S., and M. Shah, Object based segmentation of video using color, motion and spatial information, CVPR, 2001, pp. 746-751. cited by other .
Kschischang, F., B. Frey, and H. Loeliger, Factor graphs and the sum-product algorithm, IEEE Trans. on Information Theory, 2001, vol. 47, No. 2, pp. 498-519. cited by other .
Lucas, B., and T. Kanade, An iterative image registration technique with an application to stereo vision, Proc. of Image Understanding Workshop, 1981, pp. 121-130. cited by other .
Mukherjee, D., Y. Deng, and S. Mitra, Region based video coder using edge flow segmentation and hierarchical affine region matching, Proc. SPIE, Visual Communications and Image Processing, 1998, vol. 3309, pp. 338-349. cited by other .
Neal, R., and G. Hinton, A veiw of the EM algorithm that justifies incremental, sparse and other variants, Learning in Graphical Models, ed. Jordan, M.I., 1998, pp. 355-368. cited by other .
Szeliski, R., and J. Coughlin, Spline-based image registration, IJCV, 1997, vol. 22, No. 3, pp. 199-218. cited by other .
Tao, H., H. Sawhney, and R. Kumar, A global matching framework for stereo computation, ICCV, 2001, pp. 532-539. cited by other .
Wang, J., and E. Adelson, Representing moving images with layers, Proc. of IEEE Trans. on Image Processing, 1994, vol. 3, No. 5, pp. 625-638. cited by other .
Wang, J., Y. Xu, H. Shum, M. Cohen, Video toning, ACM SIGGRAPH and ACM trans. on Graphics, 2004, pp. 574-583. cited by other .
Weiss, Y. and E. Adelson, A unified mixture framework for motion segmentation: Incorporating spatial coherence and estimating the number of models, CVPR, 1996, pp. 321-326. cited by other .
Weiss, Y., Smoothness in layers: Motion segmentation using nonparametric mixture estimation, CVPR, 1997, pp. 520-527. cited by other .
Zitnick, C., S. B. Kang, M. Uyttendaele, S. Winder, and R. Szeliski, High-quality video view interpolation using layered representation, ACM SIGGRAPH, 2004, pp. 600-608. cited by other.

Primary Examiner: Bali; Vikkram
Assistant Examiner: Zeilberger; Daniel
Attorney, Agent or Firm: Lyon & Harr, LLP Lyon; Richard T.

Parent Case Text

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit of a previously-filed provisional patent application Ser. No. 60/669,675 on Apr. 8, 2005.

Claims

Wherefore, what is claimed is:

1. A computer-implemented process for segmenting and estimating the optical flow between a pair of images of a scene, comprising using a computer to perform the to following process actions: establishing an initial segmentation for each image; establishing an initial optical flow estimate for each segment of each image, wherein the optical flow estimate is the estimate of a translation that describes any movement of the segment from a position in one of the images to a position of the segment as seen in the other image; computing a refined optical flow estimate for each segment of a first one of the images from the initial segmentation of that image and the initial optical flow of the segments of that image; computing a refined optical flow estimate for each segment of the second image from the initial segmentation of that image and the initial optical flow of the segments of that image; refining the segmentation of the first image from the last-computed optical flow estimates for each segment of the first image; refining the segmentation of the second image from the last-computed optical flow estimates for each segment of the second image; further refining the optical flow estimates for each segment of the first image from the last-computed segmentation of the first image; further refining the optical flow estimates for each segment of the second image from the last-computed segmentation of the second image; and iteratively repeating process actions of refining of the segmentation of the images followed by the process actions of refining the optical flow estimates for each segment of the images until a prescribed number of iterations have been completed, wherein, all of the pixels of the images are assigned to a main segment in that image, and except in the initial segmentation, those pixels of the images that contribute color to a lesser extent to a second segment in that image are also assigned to a secondary segment, and the process actions of refining the segmentation of the images from the last-computed optical flow estimates for each segment of that image, comprise the actions of, for every pixel in each image, identifying the segments having pixels which fall within a prescribed-sized pixel neighborhood surrounding the pixel under consideration using the last-computed segmentation of the image as a basis, designating as candidate segments those identified segments which are the main segment for a pixel in the pixel neighborhood, whenever more than one segment is designated as a candidate segment for a pixel under consideration, identifying a winning pair of candidate segments which represent the closest in color and physical distance to the pixel under consideration, computing an alpha value for the pixel under consideration which represents the percentage of the color of the pixel contributed to the segment of the winning pair which is closest in color to the pixel and assigning the alpha value to the pixel, assigning the pixel under consideration to the segment of the winning pair which is closest in color to the pixel and designating the segment as the pixel's main segment, and assigning the pixel under consideration to the other segment of the winning pair which is not the closest in color to the pixel and designating the other segment as the pixel's secondary segment, and whenever only one segment is designated as a candidate segment for a pixel under consideration, assigning the pixel under consideration to the segment and designating the segment to be the pixel's main segment, and assigning an alpha value of 1 to the pixel under consideration.

2. The process of claim 1, wherein the process action of identifying the winning pair of candidate segments, comprises the actions of: for each possible pair of candidate segments, determining how many pixels in a second prescribed-sized neighborhood around the pixel under consideration have either of tie pair of candidate segments under consideration as a main segment and designating the number as a first scoring component, projecting the pixel under consideration into the other image using the last-computed flow estimate for the segment that the pixel has as its main segment, determining how many pixels in a third prescribed sized neighborhood surrounding the projected location of the pixel under consideration in the other image have as their main segments a segment that corresponds to one of the pair of candidate segments under consideration in the image being re-segmented, and designating the number as a second scoring component, computing an alpha similarity factor for the pixel and candidate segment pair under consideration, wherein the alpha similarity factor represents how close the pixel color is to an alpha blended color of the candidate segment pair, and multiplying the first and second scoring components and the alpha similarity factor, and designating the result to be an overall score for the candidate segment pair under consideration; and designating the candidate segment pair with the highest overall score as the winning pair.

3. The process of claim 2, further comprising performing a process action of dividing the product of the first and second scoring components and the alpha similarity factor, by the number of pixels in the segment of the candidate segment pair under consideration which is closest in color to the pixel under consideration, prior to designating the result to be the overall score for the candidate segment pair.

4. The process of claim 1, wherein the process actions of refining the optical flow estimates for each segment of the images, comprises, for each image, the actions of: finding a corresponding segment in the other image; and computing an optical flow vector which represents the translation between the position of the centroid of the segment under consideration in the image under consideration and the centroid of the corresponding segment in the other image.

5. The process of claim 4, wherein the process action of finding the corresponding segment in the other image, comprises the actions of: for each segment in the other frame, computing a color similarity factor representing how close in color the segment in the image under consideration is to the segment under consideration in the other image, computing a segment size similarity factor representing how close in size the segment in the image under consideration is to the segment under consideration in the other image, computing a regularization factor representing how consistent the optical flow between the segment in the image under consideration and the segment under consideration in the other image is to optical flow associated with other segments in the image under consideration, multiplying the color similarity, segment size similarity and regularization factors to produce an overall similarity score for the segment in the image under consideration and the segment under consideration in the other image; and identifying the segment in the other image associated with the highest overall similarity score and designating it as the corresponding segment to the segment under consideration in the image under consideration.

6. The process of claim 4, wherein the process action of finding the corresponding segment in the other image in the sequence, comprises the actions of: for each segment in the other frame, computing a color similarity factor representing how close in color the segment in the image under consideration is to the segment under consideration in the other image, computing a segment size similarity factor representing how close in size the segment in the image under consideration is to the segment under consideration in the other image, computing a regularization factor representing how consistent the optical flow between the segment in the image under consideration and the segment under consideration in the other image is to optical flow associated with other segments in the image under consideration, multiplying the color similarity, segment size similarity and regularization factors to produce an overall similarity score for the segment in the image under consideration and the segment under consideration in the other image; determining if the highest overall similarity score produced exceeds a prescribed minimum similarly threshold; and whenever the highest overall similarity score produced exceeds the prescribed minimum similarity threshold, identifying the segment in the other image associated with the highest overall similarity score and designating it as the corresponding segment to the segment under consideration in the image under consideration.

7. The process of claim 1 wherein the process actions of refining the optical flow estimates for each segment of the images, comprise, for each image, the actions of: finding a corresponding segment in the other image for each segment in the image under consideration, computing an optical flow vector which represents the translation between the position of the centroid of the segment under consideration in the image under consideration and the centroid of the corresponding segment in the other image for each segment in the image under consideration; and for each of a set of the segments in the image under consideration, using the optical flow vector computed for each segment in the image under consideration that are immediately adjacent the segment under consideration and the flow vector computed for the segment under consideration, projecting each pixel of the segment under consideration into the other image, for each projected pixel, identifying the pixel in said other image that approximately corresponds in location to the projected pixel and computing a color difference between the projected pixel and said correspondingly located pixel in the other image, computing an overall color difference based on the individual color differences computed for each projected pixel, and establishing the optical flow vector associated with the smallest overall color difference as the refined optical flow estimate for the segment under consideration.

8. The process of claim 7, wherein the set of the segments in the image under consideration comprises all the segments in the image.

9. The process of claim 7, further comprising, once the process action of computing an optical flow vector for each segment in the image under consideration is completed, an action of establishing the set of the segments in the image, said establishing action comprising: determining which pixels in the other image are occluded; identifying the segments in the image under consideration that correspond to segments in the other image that include at least one occluded pixel; and establishing the identified segments as the set of segments in the image under consideration.

10. A computer-readable storage medium having computer-executable instructions stored thereon for performing the process actions recited in claim 1.

11. A system for segmenting and estimating the optical flow between a first image and a second image of a scene, comprising: a general purpose computing device; and a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to, compute an initial segmentation for each image, wherein each segment comprises a plurality of pixels, compute an initial optical flow estimate for each segment of the first image, said computation comprising for each segment of the first image computing a single optical flow vector based on a centroid of the segment of the first image, wherein the single vector represents an estimate of a translation between a position of the centroid of the segment of the first image to a position of the centroid of the segment as seen in the second image, compute an initial optical flow estimate for each segment of the second image, said computation comprising for each segment of the second image computing a single optical flow vector based on a centroid of the segment of the second image, wherein the single vector represents an estimate of a translation between a position of the centroid of the segment of the second image to a position of the centroid of the segment as seen in the first image, compute a refined segmentation of the first image wherein refined segments are computed from the initial optical flow estimates for each segment of the first image, and compute a refined segmentation of the second image wherein refined segments are computed from the initial optical flow estimates for each segment of the second image.

12. The system of claim 11, further comprising program modules for refining the optical flow estimates for each segment of the first image from the last-computed segmentation of the first image; and refining the optical flow estimates for each segment of the second image from the last-computed segmentation of the second image, wherein, the process actions of refining the optical flow estimates for each segment of the images, comprise, for each image, the actions of, finding a corresponding segment in the other image, and computing a single optical flow vector based on a centroid of the segment wherein the single vector represents the translation between the position of the centroid of the segment under consideration in the image under consideration and the centroid of the corresponding segment in the other image.

13. The system of claim 12, further comprising program modules for: further refining the segmentation of the first image from the last-computed optical flow estimates for each segment of the first image; further refining the segmentation of the second image from the last-computed optical flow estimates for each segment of the second image; iteratively repeating the execution of the program modules for refining of the optical flow estimates for each segment of the images followed by refining the segmentation of the images until a prescribed number of iterations have been completed.

14. A computer-implemented process for segmenting and estimating the optics flow between a sequence of three or more images of a scene, comprising using a computer to perform the following process actions: (a) computing an initial segmentation of each image in the sequence, wherein each segment comprises a plurality of pixels; (b) computing an initial optical flow estimate for each segment in each image between it and its neighboring image or images, said computation comprising computing a single optical flow vector based on a centroid of the segment, wherein the single vector represents an estimate of a translation between a position of the centroid of the segment in said image to a position of the centroid of the segment as seen in its neighboring image or images; (c) computing a refined optical flow estimate for each segment of each image between it and its neighboring image or images from the initial segmentation of the image and the initial optical flow of the segments of the image, wherein said computation comprises, for each image, the sub-actions of, (c1) finding a corresponding segment in the neighboring image or images for each segment in the image under consideration, and (c2) computing a single optical flow vector based on a centroid of the segment under consideration in the image under consideration, wherein the single vector represents the translation between the position of said centroid and the centroid of the corresponding segment in the neighboring image or images for each segment in the image under consideration; (d) computing a refined segmentation for each image in the sequence from the last-computed optical flow estimates for the segments of the image; (e) computing a further refined optical flow estimate for each segment of each image between it and its neighboring image or images horn the last-computed segmentation of the image, wherein said computation comprises, for each image, repeating sub-actions (c1) and (c2); (f) computing a further refined segmentation for each image in the sequence from the last-computed optical flow estimates for the segments of the image; and (g) repeating actions (e) and (f) until a prescribed number of repetitions have been completed.

Description

BACKGROUND

Background Art

Motion estimation is inherently ill-posed, and techniques ranging from regularization, use of global or parametric motion models, and segmentation have been used to reduce the problem. The approach of pre-segmenting images based on color similarity and estimating the motion of segments has been shown to be effective. Such approaches depend on the reasonable assumption that similarly colored neighboring pixels have similar motions (or depths). However, these approaches use statically-determined segments for motion estimation.

The problem with using static color segments is the inability to recover from errors in the segmentation process. Ideally, the shape of segments should evolve based on spatial-temporal evidence. Another challenge is the effect of discretization and area integration--pixels near texture or object boundaries are mixtures of foreground and background colors. Again, ideally, motion estimation should account for this effect.

Early work in optical flow centered around efficient methods using image gradients and hierarchical approaches. These methods were expanded upon using robust statistics to handle discontinuities in the flow field. Another approach uses 2D splines to approximate pair-wise image flow. Layered or segmentation approaches have also been proposed to allow for discontinuities while being able to enforce constraints on the flow within the segments. A first such attempt used the affine model for flow. This involved an iterative approach to create and remove segments, based on the pixel-wise flow. For segmentation, several methods use an expectation maximization approach. These methods include using mixture models, minimum description length encoding for segment creation and spatial coherence. Different constraints for flow vectors within segments have been used, including smoothness constraints and parameterized motion models. Unfortunately, results obtained using flow-based segmentation tend to be unpredictable at object boundaries due to the local aperture ambiguity. One approach for joint segmentation and flow computation involved a patch-based technique, but this method is computationally expensive.

Instead of segmenting based on just flow, techniques have also proposed using color information or a combination of flow and color for segmentation. Color-based segmentation has also been successfully used in the context of stereo and view interpolation.

SUMMARY

The present invention is directed toward an improved technique for estimating the optical flow between images of a scene and a segmentation of the images. This involves first establishing an initial segmentation of the images of the scene and an initial optical flow estimate for each segment of the images. In one embodiment of the present technique, the image segmentation is initialized using the a quad-tree approach that recursively breaks the image into smaller segments based on the variance of the color within the segment, and the flow vectors are initialized to 0 with the corresponding mappings. These flow vectors are estimates of the translation in an image plane that describes any movement of a segment from a position in the image under consideration to a position of the segment as seen in the next image in the sequence.

In one embodiment of the present technique, using a pair of images of a scene as an example, a refined optical flow estimate is computed for each segment of a first one of the images from the initial segmentation of that image and the initial optical flow of the segments of that image. This is followed by computing a refined optical flow estimate for each segment of the second image from the initial segmentation of that image and the initial optical flow of the segments of that image. Next, the segmentation of the first image is refined from the last-computed optical flow estimates for each segment of the first image, and the segmentation of the second image is refined from the last-computed optical flow estimates for each segment of the second image. Thus, the optical flow estimates are refined for both images and then the segmentation is refined for both images. The optical flow estimates represent a bi-directional optical flow between the images. This process can continue in an iterative manner by further refining the optical flow estimates for both images using their respective last-computed segmentation, followed by further refining the segmentation of each image using their respective last-computed optical flow estimates, until a prescribed number of iterations have been completed.

In embodiments of the present invention involving the segmentation and estimation of the optical flow for a sequence of images of a scene (i.e., 3 or more) the process is essentially the same, except each process action is performed on all the images. Thus, for each image in the sequence optical flow estimates will be computed or refined for all the images before computing or refining the segmentation of each image. In addition, for images in the sequence with neighbors both preceding it and succeeding it, the bi-directional optical flow estimates are computed between each neighbor and the image being processed.

It is noted that while the above-described technique initially refined the optical flow estimate for each segment of the image under consideration, before refining the segmentation, the order can be reversed. Thus, the segmentation would be refined first using the last-computed flow estimates (which could be the initial estimates if this is the first refinement cycle) and then the flow estimates would be refined based on the newly refined segmentation.

It is further noted that during the segmentation refining process, all of the pixels of the image under consideration are assigned to a main segment, and except in the initial segmentation, those pixels that contribute color to a lesser extent to a second segment (such as segment boundary pixels) are also assigned to a secondary segment. This also includes computing and assigning an alpha value to each pixel.

In addition to the just described benefits, other advantages of the present invention will become apparent from the detailed description which follows hereinafter when taken in conjunction with the drawing figures which accompany it.

DESCRIPTION OF THE DRAWINGS

The specific features, aspects, and advantages of the present invention will become better understood with regard to the following description, appended claims, and accompanying drawings where:

FIG. 1 is a diagram depicting a general purpose computing device constituting an exemplary system for implementing the present invention.

FIG. 2 is a flow chart diagramming a process for segmenting and estimating optical flow between a pair of images of a scene according to the present invention.

FIGS. 3A-C are a continuing flow chart diagramming a process for segmenting images according to one embodiment of the present invention.

FIG. 4 is a flow chart diagramming a process for estimating the optical flow between images according to one embodiment of the present invention.

FIGS. 5 A-B are a continuing flow chart diagramming a process for finding corresponding segments between two neighboring images according to one embodiment of the present invention, which is employed as part of the optical flow estimation process.

FIGS. 6A-C are a continuing flow chart diagramming a process for computing a flow vector for each segment of an image with regard to a neighboring image according to one embodiment of the present invention, which is employed as part of the optical flow estimation process.

FIG. 7 is a flow chart diagramming a process for identifying segments in a neighboring image having occluded pixels according to one embodiment of the present invention, which is employed as part of a flow vector computation process.

FIG. 8 is a flow chart diagramming a process for segmenting and estimating optical flow between three or more images in a sequence of images of a scene according to the present invention.

FIG. 9 is a diagram of a corresponding factor graph representing the generative model of an image having overlapping segments expressed in terms of multiplicative factors.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

In the following description of the preferred embodiments of the present invention, reference is made to the accompanying drawings which form a part hereof, and in which is shown by way of illustration specific embodiments in which the invention may be practiced. It is understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the present invention.

1.0 The Computing Environment

Before providing a description of the preferred embodiments of the present invention, a brief, general description of a suitable computing environment in which portions of the invention may be implemented will be described. FIG. 1 illustrates an example of a suitable computing system environment 100. The computing system environment 100 is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment 100 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment 100.

The invention is operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.

The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices.

With reference to FIG. 1, an exemplary system for implementing the invention includes a general purpose computing device in the form of a computer 110. Components of computer 110 may include, but are not limited to, a processing unit 120, a system memory 130, and a system bus 121 that couples various system components including the system memory to the processing unit 120. The system bus 121 may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus.

Computer 110 typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by computer 110 and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computer 110. Communication media typically embodies computer readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term "modulated data signal" means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of the any of the above should also be included within the scope of computer readable media.

The system memory 130 includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM) 131 and random access memory (RAM) 132. A basic input/output system 133 (BIOS), containing the basic routines that help to transfer information between elements within computer 110, such as during start-up, is typically stored in ROM 131. RAM 132 typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit 120. By way of example, and not limitation, FIG. 1 illustrates operating system 134, application programs 135, other program modules 136, and program data 137.

The computer 110 may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only, FIG. 1 illustrates a hard disk drive 141 that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive 151 that reads from or writes to a removable, nonvolatile magnetic disk 152, and an optical disk drive 155 that reads from or writes to a removable, nonvolatile optical disk 156 such as a CD ROM or other optical media. Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive 141 is typically connected to the system bus 121 through a non-removable memory interface such as interface 140, and magnetic disk drive 151 and optical disk drive 155 are typically connected to the system bus 121 by a removable memory interface, such as interface 150.

The drives and their associated computer storage media discussed above and illustrated in FIG. 1, provide storage of computer readable instructions, data structures, program modules and other data for the computer 110. In FIG. 1, for example, hard disk drive 141 is illustrated as storing operating system 144, application programs 145, other program modules 146, and program data 147. Note that these components can either be the same as or different from operating system 134, application programs 135, other program modules 136, and program data 137. Operating system 144, application programs 145, other program modules 146, and program data 147 are given different numbers here to illustrate that, at a minimum, they are different copies. A user may enter commands and information into the computer 110 through input devices such as a keyboard 162 and pointing device 161, commonly referred to as a mouse, trackball or touch pad. Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are often connected to the processing unit 120 through a user input interface 160 that is coupled to the system bus 121, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor 191 or other type of display device is also connected to the system bus 121 via an interface, such as a video interface 190. In addition to the monitor, computers may also include other peripheral output devices such as speakers 197 and printer 196, which may be connected through an output peripheral interface 195. A camera 192 (such as a digital/electronic still or video camera, or film/photographic scanner) capable of capturing a sequence of images 193 can also be included as an input device to the personal computer 110. Further, while just one camera is depicted, multiple cameras could be included as input devices to the personal computer 110. The images 193 from the one or more cameras are input into the computer 110 via an appropriate camera interface 194. This interface 194 is connected to the system bus 121, thereby allowing the images to be routed to and stored in the RAM 132, or one of the other data storage devices associated with the computer 110. However, it is noted that image data can be input into the computer 110 from any of the aforementioned computer-readable media as well, without requiring the use of the camera 192.

The computer 110 may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer 180. The remote computer 180 may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer 110, although only a memory storage device 181 has been illustrated in FIG. 1. The logical connections depicted in FIG. 1 include a local area network (LAN) 171 and a wide area network (WAN) 173, but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet.

When used in a LAN networking environment, the computer 110 is connected to the LAN 171 through a network interface or adapter 170. When used in a WAN networking environment, the computer 110 typically includes a modem 172 or other means for establishing communications over the WAN 173, such as the Internet. The modem 172, which may be internal or external, may be connected to the system bus 121 via the user input interface 160, or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer 110, or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation, FIG. 1 illustrates remote application programs 185 as residing on memory device 181. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used.

The exemplary operating environment having now been discussed, the remaining parts of this description section will be devoted to a description of the program modules embodying the invention.

2.0 The Simultaneous Optical Flow Estimation and Image Segmentation Technique

The simultaneous optical flow estimation and image segmentation technique according to the present invention is motivated by, among others, the application of high-quality video editing. This requires not only good optical flow estimation, but accurate segmentation and background/foreground separation. All these must exist concurrently for the video editing results to be acceptable.

In general, the present technique involves matching segments instead of pixels, which is significantly more efficient without sacrificing visual quality. In addition, it reduces the ill-posed nature of flow estimation. The technique also avoids committing to an initial fixed segmentation for flow estimation. Instead, the segments are adaptively reshaped based on both spatial and temporal evidence. Matting is also deliberately factored in to account for mixed pixels. The extracted alpha value distributions help to significantly reduce typical artifacts (such as haloing at object boundaries) in applications requiring the interpolation of frames. In addition, it permits extraction of very thin objects, which would have been very difficult to recover otherwise.

Once the segmentation and optical flow estimates for the corresponding segments between a pair of images of the scene have been computed and refined to the desired degree, they can be employed for a variety of purposes. For example, many applications such as video de-noising, re-timing video, and object tracking employ per pixel optical flow estimates. These per pixel estimate can be obtained according to the present invention by simply assigning the optical flow computed for a segment to each its pixels. Other applications such as object extraction and editing use per segment flow estimates. The present invention is particularly advantageous in these applications because in the past segment-based optical flow estimation procedures involved computing the flow of each pixel between frames and then averaging the flow of the pixels in each segment to establish a flow for that segment. However, the present invention involves finding corresponding segments between images and then determines the translation associated with the segment from one image to the next. This translation is designated as the segment's flow. Thus, no pixel-by-pixel flow calculations are needed, thereby simplifying the process considerably.

In its most general terms, the technique according to the present invention estimates the segmentation of, and optical flow between, a pair of images of a scene. This basic technique can then be expanded to a longer sequence of images, such as frames in video. The basic two-image segmentation and optical flow estimation technique will be described first followed by its expansion for longer image sequences.

2.0 Optical Flow Estimation and Image Segmentation for an Image Pair

As outlined in FIG. 2, in its most general terms the technique according to the present invention for segmenting and estimating the optical flow between a pair of images of a scene involves first establishing an initial segmentation of the images (process action 200) and establishing an initial optical flow estimate for each segment of each image with regard to the other image (process action 202). In this case, the optical flow estimate is the estimate of a translation that describes any movement of the segment from a position in one image to a position of the segment as seen in the other image in the sequence. This is significant because in the past segment-based optical flow estimation procedures employed large segments and complex six-degree-of-freedom affine flow descriptions to define the movement of the segments from frame to frame. However, the system and process according to the present invention employs relatively small segments that allow the optical flow to be estimated as a one-degree translation--e.g., as a direction and distance in the image plane representing the difference in position between the centroids of two corresponding segments between the images.

Referring again to FIG. 2, the process continues with the computation of a refined optical flow estimate for each segment of a first one of the images based on the initial segmentation of the image and the initial optical flow of the segments of the image (process action 204), and then refining the optical flow estimate for each segment of the other image based on the initial segmentation of the image and the initial optical flow of the segments of the image (process action 206). If desired, a refined segmentation of the images can be computed at this point. More particularly, a refined segmentation of the first image is computed from the last-computed optical flow estimates for the segments of the first image (process action 208), and then a refined segmentation of the other image is computed from the last-computed optical flow estimates for the segments of the other image (process action 210). The optical flow estimates and image segmentation can be further refined in an iterative manner starting with the first image and then the other image by computing a more refined optical flow estimate for each segment of each image using the last-computed segmentation of that image (process action 212), and then computing a more refined image segmentation using the last-computed optical flow estimates for the segments of that image (process action 214). This iterative refinement procedure can continue until a prescribed number of iterations have been completed (e.g., 30-50 iterations). More particularly, it is determined if the prescribed number of iterations has been completed (process action 216). If not, then process actions 212 through 216 are repeated. When the prescribed number of iterations has been reached, the process ends.

It is also noted that while the above-described process initially refined the optical flow estimate for each segment of each image, before refining the segmentation of each image, the order can be reversed. Thus, the segmentation would be refined first using the last-computed flow estimates (which could be the initial estimates if this is the first refinement cycle) and then the flow estimates would be refined based on the newly refined segmentation.

2.1 Initial Segmentation and Optical Flow Field

The initial segmentation of an image is accomplished in one embodiment of the present invention using a quadtree approach. More particularly, the image is divided into a grid of equal-sized squares referred to as blocks. For example, in tested embodiments the image was divided into 60.times.60 pixel blocks. A block is selected and it is determined if the pixels of the block exhibit a color variation that exceeds a prescribed threshold. If the threshold is exceeded, the selected block is split into four equal blocks. One of these newly formed blocks is then selected and the above-described color variation test is performed. Again if the threshold is exceeded, the selected block is split into four equal blocks. This process is repeated until a resulting block has a color variation that does not exceed the threshold, or the block is at or below a prescribed minimum segment size, as measured by the number of pixels in the block (e.g., 10.times.10). This block is then designated as one of the initial segments of the image being segmented and the pixels of the block are assigned to that segment. At this point, another of the blocks in the same level as the newly designated segment is selected and the color variation test/splitting segment designation actions are repeated as described above. When all the blocks in a particular level down from the original block have been designated as segments, then the foregoing process is repeated for the unprocessed blocks in the next level up in the same manner. Eventually the original block will be completely segmented. At that point the entire process is repeated for another of the original blocks not yet processed. When the last original block is completely segmented, the process ends. At this point all the pixels of the image will be assigned to a segment.

As for the initial flow field, all the segments are assigned the same flow vector. In tested embodiments all the segments were assign zero vectors (i.e., no movement).

2.2. Segmentation Refinement

Given an optical flow field made up of flow vectors for each segment (initial or refined), a refined segmentation can be computed as follows. Essentially, the refinement process involves determining which main and secondary segments each pixel in the image under consideration belongs to and if the pixel is not already assigned to either its main or secondary segment, doing so. A main segment is the segment to which the pixel gives the most color contribution and the secondary segment is an adjacent segment to which the pixel contributes lesser color. It is noted that only pixels existing on the borders of segments are mixed in that they contribute to more than one segment. These pixels are defined as having an alpha value (.alpha.) between 0 and 1 in association with the main segment and 1-.alpha. in the secondary segment. For those pixels that are farther in the interior of a segment and which do not contribute any color to an adjacent segment, their .alpha. is equal to 1. In these cases the pixel is only assigned to a main segment and not to a secondary segment. The color contributions to the main and secondary segments are defined by the following equation: C.sub.pixel=.alpha.C.sub.main+(1-.alpha.)C.sub.secondary (1), where C.sub.pixel is the color of the pixel under consideration, C.sub.main is the average color of the segment to which the pixel contributes the greatest amount and C.sub.secondary is the average color of the segment to which the pixel contributes a lesser amount.

While every possible pair of segments in the image under consideration can be tested to determine which pair are the main and secondary segments for a pixel, processing cost can be reduced by employing the following procedure. Referring to FIGS. 3A-C, first a previously unselected pixel of the image being re-segmented is selected (process action 300). All the segments in a prescribed-sized pixel neighborhood surrounding the selected pixel are then identified using the last-computed segmentation of the frame--which could be the initial segmentation (process action 302). While any size pixel neighborhood can be employed, a 5.times.5 neighborhood was used in tested embodiments. Next, it is determined which of the identified segments are currently designated as the main segment for any pixel in the neighborhood (process action 304). If the last-computed segmentation is the initial segmentation, then the segment to which a pixel was assigned in the segmentation process is considered the main segment for that pixel. The segments determined to be main segments for any of the pixels in the pixel neighborhood are designated as candidate segments for the selected pixel (process action 306). It is noted that for interior pixels of a segment, the foregoing actions will result in only one segment being identified as a candidate segment if the prescribed-sized pixel neighborhood is made small as in the tested embodiments. Given this, it is next determined if more than one segment has been designated as a candidate segment for the selected pixel (process action 308). If not, the sole candidate segment is designated as the main segment for the pixel and an alpha value of 1 is assigned to the selected pixel (process action 310).

In general the next part of the process entails finding the pair of candidate segments that are closest both in color to the pixel under consideration and physical distance to the pixel, whenever more than one candidate segment is designated for that pixel. This is accomplished in one embodiment of the present invention as follows. Referring again to FIGS. 3A-C, whenever it is determined that the selected pixel has more than one designated candidate segment, a previously unselected pair of candidate segments taken from all the possible pairs is selected (process action 312). It is next ascertained how many pixels in a prescribed-sized neighborhood around the currently selected pixel have either of the selected candidate segment pair as a main segment (process action 314). This is designated as the first scoring component (process action 316). While any size pixel neighborhood can be employed, a 5.times.5 neighborhood was used in tested embodiments. In addition, the currently selected pixel is projected into the other image using the given flow vector for the segment that the pixel has currently assigned as its main segment (process action 318). This flow vector approximates the distance and direction the pixel moves in the other image. It is then determined how many pixels in a prescribed sized neighborhood surrounding the projected location of the pixel in the other image have as their main segments a segment that corresponds to one of the selected pair of candidate segments in the image being re-segmented (process action 320). This is designated as the second scoring component (process action 322). While any size pixel neighborhood can be employed, a 3.times.3 neighborhood was used in tested embodiments.

Next an alpha similarity factor associated with the currently selected pixel, given the selected candidate pair of segments, is computed (process action 324). The alpha similarity factor represents how close the pixel color is to alpha blended color of the candidate pair of segments. This can be accomplished using the following equation: e.sup.-R(p,S.sup.i,k.sup.,S.sup.i,l.sup.).sup.2.sup./.sigma..sup.s.sup.2 (2) where R is the residual associated with pixel p, main segment S.sub.i,k and secondary segment S.sub.i,l; and .sigma..sub.s is an estimated standard deviation of the variation in color among pixels within the main segment. The residual R is computed using conventional means.

In geometric terms, the alpha value is the distance between a point on a line in color space (e.g., RGB color space) passing through the coordinates of the average color associated with a candidate pair of segments, to the more distant color coordinate associated with one of the pair of segments, divided by the overall distance between the color coordinates of the two segments, whenever the aforementioned point is between the color coordinates of the segment pair. The point is defined as the place where a line (representing the residual R) extends perpendicularly to the color coordinates of the pixel under consideration. The segment corresponding to the color closest to the color of the pixel under consideration is the main segment of the pixel, while the other segment of the segment pair is the secondary segment. However, if the aforementioned point does not fall in between the color coordinates of the candidate segment pair, then the segment of the pair corresponding to the closest color is the main segment of the pixel under consideration, but the pixel is not assigned to a secondary segment. This latter case corresponds to an interior pixel.

Referring again to FIGS. 3A-C, the first and second scoring components and the alpha similarity factor are multiplied together to produce an overall score for the selected candidate segment pair (process action 326). It is next determined if all the candidate pairs have been selected (process action 328). If not, process actions 312 through 328 are repeated. When all the candidate pairs have been processed, it is then determined which pair has the highest overall score and this pair is designated as the winning pair (process action 330). The currently selected pixel is assigned to the segment of the winning pair which is closest in color to the pixel and this segment is designated as the pixel's main segment (process action 332). In addition, the alpha value associated with the currently selected pixel is computed (process action 334). This can be accomplished using Eq. (1) as the average colors of the winning candidate segment