Border matting by dynamic programming

• US 20060039611A1
• Filed: 08/09/2004
• Published: 02/23/2006
• Est. Priority Date: 08/09/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kolmogorov, Vladimir, Rother, Carsten Curt Eckard, Blake, Andrew
• Granted Patent: US 7,430,339 B2
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/20041 Distance transform
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/162 involving graph-based methods
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: H04N 5/275 Generation of keying signals

Abstract

Techniques are disclosed to provide more efficient and improved border matting for extracted foreground images, e.g., without requiring excessive user interaction. Border matting techniques described herein generate relatively continuous transparency (or alpha values) along the boundary of the extracted object (e.g., limiting color bleeding and/or artifacts).

Claims

1. A method comprising:

receiving a segmented image having a foreground region and a background region;

determining a contour along a boundary between the foreground and background regions;

defining an energy function corresponding to one or more parameters of an alpha map of pixels in an unknown region extending from the contour;

estimating a center parameter and a width parameter for the alpha map by minimizing the defined energy function; and

computing the alpha map corresponding to the estimated center and width parameters.

2. A method as recited by claim 1, wherein the image is segmented as a bimap or a trimap.

3. A method as recited by claim 1, wherein the unknown region is defined by a trimap.

4. A method as recited by claim 1, wherein the energy function has one or more terms selected from a group comprising a smoothing regularizer term and a data likelihood term.

5. A method as recited by claim 1, wherein the contour is determined by a curve-fitting technique applied to a boundary of the unknown region.

6. A method as recited by claim 1, wherein the contour is determined by fitting a poly-line to a boundary of the unknown region.

7. A method as recited by claim 1, wherein the segmented image is provided by hard segmentation.

8. A method as recited by claim 1, wherein the energy minimization is performed by dynamic programming.

9. A method as recited by claim 1, wherein the image segmentation is defined by a user.

10. A method as recited by claim 1, wherein for a bimap segmented image, the method further comprises determining an unknown region extending from the contour.

11. A method as recited by claim 1, further comprising estimating one or more foreground pixel colors to limit color bleeding in from the background region.

12. A method as recited by claim 1, further comprising estimating one or more foreground pixel colors to limit color bleeding in from the background region, wherein the estimating of the foreground pixel colors comprises:

applying Bayes matte to obtain an estimate of a foreground color of a first pixel; and

borrowing a pixel color from a second foreground pixel within a neighborhood of the first pixel that is most similar in color to the estimated foreground color of the first pixel.

13. A method comprising:

receiving a bimap-segmented image having a foreground region and a background region;

determining a contour along a boundary between the foreground and background regions;

determining an unknown region extending from the contour;

defining an energy function for pixels in the unknown region, the energy function having one or more terms selected from a group comprising a smoothing regularizer term and a data likelihood term;

estimating a center and a width parameter for the alpha map by minimizing the defined energy function; and

computing the alpha map corresponding to the estimated center and width parameters.

14. A method as recited by claim 13, wherein the contour is determined by a curve-fitting technique applied to a boundary of the unknown region.

15. A method as recited by claim 13, wherein the bipmap is provided by hard segmentation.

16. A method as recited by claim 13, wherein the energy minimization is performed by dynamic programming.

17. A method as recited by claim 13, further comprising estimating one or more foreground pixel colors to limit color bleeding in from the background region.

18. A method as recited by claim 13, further comprising estimating one or more foreground pixel colors to limit color bleeding in from the background region, wherein the estimating of the foreground pixel colors comprises:

applying Bayes matte to obtain an estimate of a foreground color of a first pixel; and

borrowing a pixel color from a second foreground pixel within a neighborhood of the first pixel that is most similar in color to the estimated foreground color of the first pixel.

19. One or more computer-readable media having instructions stored thereon that, when executed, direct a machine to perform acts comprising:

receiving a segmented image having a foreground region and a background region;

determining a contour along a boundary between the foreground and background regions;

defining an energy function corresponding to one or more parameters of an alpha map of pixels in an unknown region extending from the contour;

estimating a center parameter and a width parameter for the alpha map by minimizing the defined energy function; and

computing the alpha map corresponding to the estimated center and width parameters.

20. One or more computer-readable media as recited by claim 19, wherein the image is segmented as a bimap or a trimap.

21. One or more computer-readable media as recited by claim 19, wherein the unknown region is defined by a trimap.

22. One or more computer-readable media as recited by claim 19, wherein the energy function has one or more terms selected from a group comprising a smoothing regularizer term and a data likelihood term.

23. One or more computer-readable media as recited by claim 19, wherein the contour is determined by a curve-fitting technique applied to a boundary of the unknown region.

24. One or more computer-readable media as recited by claim 19, wherein the segmented image is provided by hard segmentation.

25. One or more computer-readable media as recited by claim 19, wherein the energy minimization is performed by dynamic programming.

26. One or more computer-readable media as recited by claim 19, wherein the image segmentation is defined by a user.

27. One or more computer-readable media as recited by claim 19, wherein the acts further comprise estimating one or more foreground pixel colors to limit color bleeding in from the background region.

28. One or more computer-readable media as recited by claim 19, wherein the acts further comprise estimating one or more foreground pixel colors to limit color bleeding in from the background region, wherein the estimating of the foreground pixel colors comprises:

applying Bayes matte to obtain an estimate of a foreground color of a first pixel; and

borrowing a pixel color from a second foreground pixel within a neighborhood of the first pixel that is most similar in color to the estimated foreground color of the first pixel.