A scheme of categorizing Laplacians is introduced in this paper based on the computation times of similarity weights for each pair of adjacent data points. It is also theoretically proven that the Laplacian construction with multiple computations of similarity weights for each pair of adjacent points can better capture the local intrinsic structure of data than those methods with only one or two such computations. A novel Laplacian construction method is then proposed, which is more suitable for natural image matting task. In this method, all the different similarity weights for any pair of adjacent pixels are reconstructed by using a local linear model in the neighborhoods they fall into. By combining the user-provided constraints which specify some pixels as foreground or background, a quadratic objective function for matting based on semi-supervised learning is formed. When estimating the colors of unknown pixels by sampling foreground and background colors, this optimization problem is reformulated and solved in an iterative manner. What’s more, this iterative scheme can also be successfully generalized and applied into other previously constructed Laplacians for image matting tasks with only sparse label scribbles. Both the theoretical analysis and experimental results validate that the proposed Laplacian construction approach can better capture the intrinsic structure between image pixels, and can propagate the finer ingredients of an image foreground and background rather than just their labels, and thus the mattes of higher quality are obtained.