  Natural image matting, which separates foreground from background, is a very
important intermediate step in recent computer vision algorithms. However, it
is severely underconstrained and difficult to solve. State-of-the-art
approaches include matting by graph Laplacian, which significantly improves the
underconstrained nature by reducing the solution space. However, matting by
graph Laplacian is still very difficult to solve and gets much harder as the
image size grows: current iterative methods slow down as $\mathcal{O}\left(n^2
\right)$ in the resolution $n$. This creates uncomfortable practical limits on
the resolution of images that we can matte. Current literature mitigates the
problem, but they all remain super-linear in complexity. We expose properties
of the problem that remain heretofore unexploited, demonstrating that an
optimization technique originally intended to solve PDEs can be adapted to take
advantage of this knowledge to solve the matting problem, not heuristically,
but exactly and with sub-linear complexity. This makes ours the most efficient
matting solver currently known by a very wide margin and allows matting finally
to be practical and scalable in the future as consumer photos exceed many
dozens of megapixels, and also relieves matting from being a bottleneck for
vision algorithms that depend on it.
