Intelligent scissors are a tool a cut an object out of an image by using a live wire that automatically wraps around that object. It still requires a user to guide the wire, but does much of the work and might create a better result than a user would. This produces an alpha mask that can then be used to add images together. However, the alpha mask is either one or zero; there is just a hard edge and no mix of alpha values. If the cut is imperfect or if it contains a mixture of foreground and background colors (such as hair), then this hard cut will be noticeable to the viewer. A solution to this is to implement an alpha matting algorithm to solve for the best alpha value for the pixel. I initially tried the Bayesian algorithm to find the alpha value but stopped when I couldn’t find any information on how to compute the Orchard-Bouman clusters that are essential to the algorithm. The algorithm that I settled on was the one described in "A Closed Form Solution to Natural Image Matting”. This algorithm creates a matting laplacian and then solves a sparse linear system in order to compute the alpha values.
The equation for an image I given the alpha map α the foreground F and background B is
I = α*F+(1-α)B
This is severely under-constrained as I is the only known value. This can be rewritten as
α = aI+b
a = 1/(F-B)
b=-b/(F-B)
assuming that F and B are smooth over a window w. The goal is then to find values to minimize the equation
with ε as a regularization term.
This can be reduced to J(α) = α^T * L * α, where L(i,j) =
with |w| being the size of the window around k, mean μ, and variance σ^2
Finally this can be extended to an RGB image by setting L(i,j) to
with covariance matrix Σ.
When solving for alpha, some alpha values are already specified as known foreground or known background. The equation can be modified to become
With D being a diagonal matrix where D(i,i) is 1 when the pixel is known foreground or background, vector β is 1 when it is known foreground, and λ being a large number to force the system to find a solution. If this is differentiated it becomes a sparse linear system.
This system is solved with the Eigen library for sparse matrices so that α can be found.
The intelligent scissors executable in the scissors library is the provided solution from this project. This can be used to trace out the known background and then trace the known foreground. These can then be combined into a trimap or sent directly into the RunLaplacian program. The RunLaplacian program should run in two to three minutes for the provided inputs.
A picture of a woman taken from natural background and added onto an ocean background.
A squirrel with fuzzy edges rendered onto a different background
The lighthouse on the left is the original cut, and the lighthouse on the right with my alpha mask.
Results were generally poorer that I expected them to be when I was started the project. Initially I tried using Chuang's Bayesian matting approach, however I hit a roadblock when I could not find any information about implementing the Orchard-Bouman cluster algorithm save for a complicated 38 page paper from 1991. I also looked into the Poisson matting algorithm, but eventually decided the current algorithm. I am sure that the matting Laplacian is computed correctly, as I checked the means, covariance matrix, and pixel id's to make sure that they were the correct values. The rows also sum to zero like the correct matrix would. Eigen should be solving the linear system correctly as well, so I couldn’t pin point any problem in the implementation. Despite not being perfect, the results are still adequate. The combination images were created using GIMP.
Libvips and glm are required in order for this to build. Since Eigen and clap are implemented in header files they should work fine.
mkdir build
make all
This takes in either a trimap or a pair of foreground and background maps and creates an alpha mask. Foreground and background maps can be created with the executable in the scissors directory. These can then either be manually assembled into a trimap, or they can be passed directly into the program.
- -i, --input : Input image (required)
- -o, --output : Output image (required)
- -t, --trimap : Trimap
- -f, --foreground : Foreground map
- -b, --background : Background map
- -e, --epsilon : Epsilon value
- -g, --generate : Use foregound and background maps instead of trimap
Either a trimap or a pair of foreground and background maps are required. Images are loaded with vipsload which takes in most image types, but it won't accept .tga files, which is the output format of the scissors tool, so these will have to be converted with convert, gimp, or some other tool. The default epsilon is the suggested value of 1e-7. This code was built on a mac and will work on one. The scissors code is from the this scissors solution and is a windows executable. It can however be run with Wine for use on a mac.
./RunLaplacian -i examples/squirrel.jpg -o out.jpg -t examples/squirrelTrimap.png
./RunLaplacian -i examples/squirrel.jpg -o out.jpg -f examples/squirrelForeground.png -b examples/squirrelBackground.png -g
A Closed Form Solution to Natural Image Matting
Fast Matting Using Large Kernel Matting Laplacian Matrices