KNN Matting
∗
Qifeng Chen Dingzeyu Li Chi-Keung Tang
The Hong Kong University of Science and Technology
Abstract
We are interested in a general alpha matting approach
for the simulta neous extraction of multiple image lay ers;
each layer may have disjoint segments for material matting
not limited to foregro und mattes typical of natural image
matting. The estimated alphas also satisfy the summation
constraint. Our approach does not assume the local color-
line model, does not n e ed sophisticated sampling strategies,
and generalizes well to any co lor o r feature space in any
dimensions. Our matting techn ique, aptly called KNN mat-
ting, capitalizes on the nonlocal principle by using K near-
est neighbors (KNN ) in matching nonlocal neighborhoods,
and contributes a simple and fast algorithm giving compet-
itive results with sparse user markups. KNN matting ha s
a closed-form solution that can leverage on the precondi-
tioned conjugate g radient method to produce an e fficien t
implementation. Experimental evaluation on benchmark
datasets indicates that o ur matting results are comparable
to or of higher quality than state of the art methods.
1. Introduction
Alpha matting refers to the problem of decomposing an
image into two layers, called foreground and background,
which is a convex combination under the image composit-
ing equation:
I = αF + (1 − α)B (1)
where I is the given pixel color, F is the unknown fore-
ground layer, B is the unknown background layer, and α is
the unknown alpha matte. This compositing equation takes
a general form when there are n ≥ 2 layers:
I =
n
X
i=1
α
i
F
i
,
P
n
i=1
α
i
= 1. (2)
We are interested in solving the general alpha matting prob-
lem for extracting multiple image layers simultaneously
with sparse user markups, where such markups may fail
∗
The research was supported by the Google Faculty Award and the
Hong Kong Research Grant Council under grant no 619711.
Input clicks Closed-form Nonlocal KNN
Figure 1. Using the sparse click inputs same as in nonlocal mat-
ting [
11], KNN matting produces better results. Top row: clearer
and cleaner boundary; middle: more details preserved for hairs as
well as the red fuzzy object; bottom: furs are more clearly sepa-
rated from background. Figure best viewed in electronic version.
approaches requiring reliable color samples to work. Re-
fer to Figures
1 and 2. While the output can be fore-
ground/background layers exhibiting various degrees of
spatial coherence as in natural image matting on single RGB
images, the extracted layers with fractional alpha bound-
aries can also be disjoint, as those obtained in material mat-
ting from multi-channel images that capture spatially vary-
ing bidirectional distribution function (SVBRDF).
Inspired by nonlocal matting [
11], and sharing the math-
ematical properties of nonlocal denoising [3], our approach
capitalizes on K nearest neighbors (KNN) searching in the
feature space for matching, and uses an improved match-
ing metric to achieve good results with a simpler algo-
rithm than [
11]. We do not assume the local 4D color-line
model [
13, 14] widely adopted by subsequent matting ap-
proaches, thus our approach generalizes well in any color
space (e.g., HSV) in any dimensions (e.g., six-dimensional
SVBRDF). It does not require a large kernel to collect good
samples [
9, 11] in defining the Laplacian, nor does it require
good foreground and background sample pairs [
20, 8, 6]
(which need user markups more than a few clicks, much less