Image Matting via LLE/iLLE Manifold Learning

David Tien, Junbin Gao, Jim Tulip


Accurately extracting foreground objects is the problem of isolating the foreground in images and video, called image matting which has wide applications in digital photography. This problem is severely ill-posed in the sense that, at each pixel, one must estimate the foreground and background pixels and the so-called alpha value from only pixel information. The most recent work in natural image matting rely on local smoothness assumptions about foreground and background colours on which a cost function has been established. In this paper, we propose an extension to the class of affinity based matting techniques by incorporating local manifold structural information to produce both a smoother matte based on the socalled improved Locally Linear Embedding. We illustrate our new algorithm using the standard benchmark images and very comparable results have been obtained.


Image Matting; Locally Linear Embedding; Manifold Learning; Alpha Matte; Nesterov's Method;


J. Wang and M. F. Cohen, "Image and video matting: A survey," Foundations and Trends in Computer Graphics and Vision, vol. 3, no. 2, pp. 97-175, 2007.

Y. Chuang, B. Curless, D. Salesin, and R. Szeliski, "A Bayesian approach to digital matting," in Proceedings of CVPR, vol. 2, 2001, pp. 264-271.

X. Bai and G. Sapiro, "A geodesic framework for fast interactive image and video segmentation and matting," in Proceedings of International Conference on Computer Vision, 2007, pp. 1-8.

J. Sun, J. Jia, C. K. Tang, and H. Y. Shum, "Poisson matting," ACM Trans. Graph., vol. 23, no. 3, pp. 315-321, 2004.

L. Grady, T. Schiwietz, and S. Aharon, "Random walks for interactive alpha-matting," in VIIP, 2005.

A. Levin, D. Lischinski, and Y. Weiss, "A closed-form solution to natural image matting," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 2, pp. 228-242, 2008.

K. He, J. Sun, and X. Tang, "Fast matting using large kernel matting Laplacian matrices," in Proceedings of CVPR 2010, 2010, pp. 2165-2172.

J. Gao, M. Paul, and J. Liu, "The image matting method with regularized matte," in Proceedings of ICME, 2012.

S. Tierney and J. Gao, "Natural image matting with total variation regularisation," in Proceedings of DICTA, 2012, pp. 1-8.

J. Gao, "Image matting via local tangent space alignment," in Proceedings of the International Conference on Digital Image Computing: Techniques and Applications (DICTA), 2011.

Z. Zhang and H. Zha, "Principal manifolds and nonlinear dimension reduction via local tangent space alignment," SIAM Journal of Scientific Computing, vol. 26, pp. 313-338, 2004.

L. van der Maaten, E. O. Postma, and H. van den Herick, "Dimensionality reduction: A comparative review," Tilburg University, Technical Report TiCC-TR 2009-005, 2009.

N. D. Lawrence, "A unifying probabilistic perspective for spectral dimensionality reduction," Sheffield Institute for Translational Neuroscience, University of Sheffield, Tech. Rep., 2010, arXiv:1010.4830v1.

S. T. Roweis and L. K. Saul, "Nonlinear dimensionality reduction by locally linear embedding," Science, vol. 290, pp. 2323-2326, 2000.

S. Xiang, F. Nie, C. Pan, and C. Zhang, "Regression reformulations of LLE and LTSA with locally linear transformation," IEEE Trans on Systems, Man and Cybernetics, Part B: Cybernetics, vol. 41, no. 5, pp. 1250-1262, 2011.

Y. Li, J. Sun, C. K. Tang, and H. Y. Shum, "Lazy snapping," ACM Transactiona on Graphics, vol. 23, no. 3, pp. 303-308, 2004.

C. Rother, V. Kolmogorov, and A. Blake, "Grabcut: Interactive foreground extraction using iterated graph cuts," ACM Transactions on Graphics, vol. 23, no. 3, pp. 309-314, 2004.

D. DeCoste, "Visualizing mercer kernel feature spaces via kernelized locally-linear embeddings," in Proc. of the Eighth International Conference on Neural Information Processing, 2001.

M. Belkin and P. Niyogi, "Laplacian eigenmaps for dimensionality reduction and data representation," Neural Computation, vol. 15, pp. 1373-1396, 2003.

D. L. Donoho and C. Grimes, "Hessian eigenmaps: locally linear embedding techniques for high-dimensional data," in Proceedings of the National Academy of Arts and Sciences, vol. 10, 2003, p. 55915596.

H. Chang and D. Yeung, "Robust locally linear embedding," Pattern Recognition, vol. 39, pp. 1053-1065, 2006.

Y. Pan, S. Ge, and A. Al-Mamun, "Weighted locally linear embedding for dimension reduction," Pattern Recognition, vol. 42, pp. 798-811, 2009.

S. Q. Zhang, "Enhanced supervised locally linear embedding," Pattern Recognition Letters, vol. 30, no. 13, pp. 1208-1218, 2009.

L. Zhao and Z. Zhang, "Supervised locally linear embedding with probability-based distance for classification," Computers & Mathematics with Applications, vol. 57, no. 6, pp. 919-926, 2009.

W. L. Zheng, N. Ru, and F. H. Yao, "Locally linear embedding for fault diagnosis," Advanced Materials Research, vol. 139-141, pp. 2599-2602, 2010.

C. J. Lin and J. J. More, "Newton's method for large bound-constrained optimization problems," SIAM Journal on Optimization, vol. 9, pp. 1100-1127, 1999.

Y. Nesterov, "A method for solving a convex programming problem with convergence rate o(1=k2)," Soviet Math. Dokl., vol. 27, pp. 372-376, 1983. [Online]. Available:

--, "Gradient methods for minimizing composite objective function," Universit'e catholique de Louvain, Belgium, CORE DISCUSSION PAPER 76, 2007. [Online]. Available:

A. Beck and M. Teboulle, "A fast iterative shrinkage-thresholding algorithm for linear inverse problems," SIAM Journal of Imaging Sciences, vol. 2, no. 1, pp. 183-202, 2009.

Full Text: PDF


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

IT in Innovation IT in Business IT in Engineering IT in Health IT in Science IT in Design IT in Fashion

IT in Industry @ (2012 - ) . . ISSN (Online): 2203-1731; ISSN (Print): 2204-0595