Manifold learning and matting

• US 9,311,567 B2
• Filed: 05/10/2011
• Issued: 04/12/2016
• Est. Priority Date: 05/10/2010
• Status: Expired due to Fees

• Current Assignee: Flashfoto, Inc.
• Original Assignee: Flashfoto, Inc.
• Inventors: Lee, Kuang-chih, Piramuthu, Robinson
• Primary Examiner(s): Sherali, Ishrat I
• Application Number:
  US13/068,460
• Publication Number:
  US 20110274344A1
• Time in Patent Office: 1,799 Days
• Field of Search: 382/173, 382/155
• US Class Current: 1/1
• CPC Class Codes: G06F 18/21375 involving differential geometry, e.g. embedding of pattern manifold
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/143 involving probabilistic approaches, e.g. Markov random field [MRF] modelling
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods

Abstract

Systems for manifold learning for matting are disclosed, with methods and processes for making and using the same. The embodiments disclosed herein provide a closed form solution for solving the matting problem by a manifold learning technique, Local Linear Embedding. The transition from foreground to background is characterized by color and texture variations, which should be captured in the alpha map. This intuition implies that neighborhood relationship in the feature space should be preserved in the alpha map. By applying Local Linear Embedding using the disclosed embodiments, the local image variations can be preserved in the embedded manifold, which is the resulting alpha map. Without any strong assumption, such as color line model, the disclosed embodiments can be easily extended to incorporate other features beyond RGB color features, such as gradient and texture information.

Claims

1. A method comprising:

receiving an image from a memory component;

determining a feature vector associated with features of pixels in a region of the image, wherein the feature vector includes color feature information and texture feature information of the pixels;

determining alpha values associated with opacity level of the pixels within the region, wherein the alpha values are associated with a transition from a foreground to a background of the image, and wherein the alpha values are based on color and texture; and

forming a manifold based on the alpha values and further based on the feature vector.

2. The method of claim 1, wherein the feature vector further includes gradient of luminance information and location information of the pixels.

3. The method of claim 1, wherein determining the feature vector is based on determining features of neighboring pixels to the pixels in the region.

4. The method of claim 1 further comprising:

forming an alpha map of feature variations at a transition from a foreground to a background associated with the image by applying a local linear embedding to the transition.

5. The method of claim 1 further comprising:

determining a Laplacian matrix based on an alpha map of pixels associated with either the foreground or the background of the image, and wherein the Laplacian matrix is further based on an alpha map of pixels associated with the foreground and the background of the image.

6. The method of claim 1 further comprising:

determining a Laplacian matrix based in part on the alpha values and a diagonal matrix,

wherein the alpha values are associated with pixels of a first subregion of the image and with pixels of a second subregion of the image, wherein the first subregion is a width from a diagonal region to a region including foreground pixels and the second subregion is a width from the diagonal region to a region including background pixels, and

wherein the diagonal matrix is a matrix of features associated with pixels at the diagonal region.

7. The method of claim 1, wherein the manifold includes pixels in the foreground of the image, pixels in the background of the image, or pixels that transition from the background to the foreground.

8. The method of claim 1 further comprising:

forming another manifold associated with another region of the image based on shape information of the another manifold.

9. The method of claim 1 further comprising:

forming a matte of the image based on the manifold.

10. A system comprising:

a memory; and

a processor configured to;

receive an image;

determine a feature vector associated with features of pixels in a region of the image, wherein the feature vector includes color feature information and texture feature information of the pixels;

determine alpha values associated with opacity level of the pixels within the region, wherein the alpha values are associated with a transition from a foreground to a background of the image, and wherein the alpha values are based on color and texture; and

form a manifold based on the alpha values and further based on the feature vector.

11. The system of claim 10, wherein the feature vector further includes gradient of luminance information and location information of the pixels.

12. The system of claim 10, wherein determining the feature vector is based on determining features of neighboring pixels to the pixels in the region.

13. The system of claim 10, wherein the processor is further configured to:

form an alpha map of feature variations at a transition from a foreground to a background associated with the image by applying a local linear embedding to the transition.

14. The system of claim 10, wherein the processor is further configured to:

determine a Laplacian matrix based in part on the alpha values and a diagonal matrix,

wherein the alpha values are associated with pixels of a first subregion of the image and with pixels of a second subregion of the image, wherein the first subregion is a width from a diagonal region to a region including foreground pixels and the second subregion is a width from the diagonal region to a region including background pixels, and

wherein the diagonal matrix is a matrix of features associated with pixels at the diagonal region.

15. The system of claim 10, wherein the processor is further configured to:

form another manifold associated with another region of the image based on shape information of the another manifold.

16. The system of claim 10, wherein the processor is further configured to:

form a matte of the image based on the manifold.

17. A non-transitory computer readable medium having stored thereon, computer executable instructions that, if executed by a device, causes the device to perform a method comprising:

determining manifolds of regions in an image based on color and texture of pixels within the regions; and

compositing the manifolds to form a matte based on a transition from a foreground to a background of the image, wherein the transition is characterized by the color and texture of pixels.

18. The method of claim 17, wherein the manifolds are regions of the image including pixels in the foreground of the image, pixels in the background of the image, and pixels that transition from the background to the foreground of the image.

19. The method of claim 17, wherein determining the manifolds are further based on a gradient of luminance of the pixels in the image.

20. The method of claim 17 further comprising:

determining each manifold based on shape information of its respective neighboring manifolds.