CS576 PA2

---

Fast Matting Using Large Kernel Matting Laplacian Matrices

20113252 HyoSub Park

[Download] Source Code & Executable
How to execute: Project2.exe input_bmp_file input_trimap_file
Output: Result of algorithm at every iteration. Iteration goes to 100.

Project Description

Large Kernel Matting Laplacian

The hallmark of this paper is that it replaces the time-consuming process of multiplying laplacian matrix with analytically correct but less time consuming alternative. In closed form matting, we are trying to optimize the following equation:



Which can is equivalent to:



where each L is a NXN laplacian matrix and each entry of L is defined as:



We use conjugate gradient method to solve the optimization problem here. Thus, the main bottleneck in this process is the multiplying L with conjugate p part. The main contribution of this paper is that they approximated each entry of Lp with:



So that the whole process becomes O(N)
In this paper, authors suggest using local-global-local approach in order to make optimization faster. At first, authors divide the scene with kd-tree. For each leaf node, the matting is done separately. After local matting is done, matting is done global again. After this, matting is done local again, in order to fix the errors.

Implementation

I implemented the Lp part of the algorithm, but I was not able to implement local-global-local. Also, the algorithm does not seem to be working as well as expected. The results of the implementation is shown as follows:

(Resoultion = 400 X 300, Window radius=20, Iteration = 30 Time= 72.12 seconds)
Input image and trimap
Result

(Resolution = 1152 X 864, Window radius = 20, Iteration = 30 Time = 619.80 seconds)

Result

I tried to implement local-global-local scheme, but it didn't work. When I tried to use solution from first local pass for initial solution of global pass, strange artifact occurred. I think it is either due to problem of approximated Lp or my implementation problem.
As it can be seen from the result, the algorithm sort of works but its quality is not satisfactory. Since it is sort of working, implementation doesn't seem to be having critical problem, but it seems it is very dependent to the detail of trimap provided. The more detailed the trimap is, the better the algorithm works. However, what would be the point of using matting if we have to put effort to the trimap? Anyways, it seems to be some problem with either this algorithm or my implementation.

Conclusion and Future works

This was a fun project to implement, but the theoretical part was very difficult to understand. I guess I might be able to implement the complete version of this paper later if I learn what Laplace matrix really is and what exactly it does. Still, it is a shame I wasn't able to implement the complete version of this paper. One thing I noticed when running the algorithm was that as the number of iteration increases, the convergence speed decreases. Maybe there could be some way to make convergence faster.







.