In this paper we present a method for nding optimal parameters of graph Laplacian-based semantic segmentation. This method is fully unsupervised and provides parameters individually for each image. In the experiments on Graz dataset the accuracy of segmentation obtained with the parameters provided by our method is very close to the accuracy of segmentation obtained with the parameters chosen on the test set.
Let us denote W : Wij = exp d (xi; xj ))2 - a weight matrix with Gaussian kernel. Let gi = Pj wij stand for a sum of W along the i-th row. Let D be a diagonal matrix with values gi on diagonal. Graph Laplacian is de ned as a matrix L = W D.
The methods for image segmentation and matting solve the following energy function with respect to vector f = (f1; :::; fN ):
In the matrix form (
E(f ) =
X ci (fi i yi)2 +
X wij (fi i;j
fj )2 :
E(f ) = (f
y)T C (f
y) + f T Lf ;
where C denotes a square diagonal matrix with ci on diagonal and y denotes
an N -dimensional vector of initial likelihood scores yi. This optimization problem
reduces to solving a sparse linear system:
(L + C)f = Cy:
(
The object/background segmentation algorithm then consists in: 1)
computing graph Laplacian matrix L; 2) solving the sparse linear system (
This framework can be extended to a multi-class segmentation. Let K denote
the number of labels corresponding to object categories. If we solve (
Suppose that the distance function d is represented as a weighted sum of metrics di : R R ! R+; i = 1; :::; K:
K d(xi; xj )2 = 1 X
kdk(xi; xj )2 ; k=1 log X wij ( ) i;j m=2 log( ) + log
N 2(
Consider the logarithmic plot of log Pi;j wij with respect to log . Figure (
In the limit ! 1, wij ! 1, so Pij wij ! N 2. On the other hand, as ! 0, wij ! ij , so Pij wij ! N . These two limiting values set two asymptotes of the plot and assert that logarithmic plot cannot be linear for all values of .
Therefore in order to get better approximation of Laplace-Beltrami operator
with 1; :::; K xed we have to choose the value of from the linear region
of logarithmic plot. We use the point of maximum derivative as the point of
maximum linearity.
(
Unsupervised learning of 1; :::; K and . As follows from (
In order to nd optimal values of 2; :::; K we solve the following optimization problem: ( 2(opt); :::; K(opt)) = arg min 2;:::; K kS ( 2; :::; K )
where S ( 2; :::; K ) is the slope of the logarithmic plot in the point of maximum derivative.
S ( 2; :::; K ) can be estimated numerically. We can compute log Pij wij
for di erent values of and estimate the slope of this function in the point of
maximum derivative. Therefore the optimization problem (
The unsupervised learning method for graph Laplacian therefore has two
steps:
2; :::; K by solving optimization problem (
2 rj k 2 r + kxi 2 g
2 xj k ; where r encodes mean RGB color in the superpixel, x encodes coordinates of the center of the superpixel, r > 0 and g > 0 are the parameters of the method. The meaning r > 0 and g > 0 is the scale of chromatic neighbourhoods and the scale of geometric neighbourhoods respectively.
This distance function (7) can be rewritten in the form of (
In the second step of the learning method (
A
sigmoid function:T (x) = B+exp(Cx+D) + E. Since the asymptotes of the sigmoid
are set by (
In most cases the slope of the logarithmic plot S( ) is monotonic function of
. Monotonicity of S( ) allows using simple bin-search for optimization problem
(
Graz dataset 1 contains 1096 images of three classes: "person", "bike" and "car". In our experiments we solved a separate binary segmentation problem for each category. To measure the quality of segmentation we used a standard metric - percent of incorrectly classi ed pixels in the image.
In our experiments we used an open-source VlBlocks toolbox 2, which implements the method described in [6]. We chose it for comparison for the following reasons. First, it allows using di erent local appearance models. The method has a parameter N meaning number of neighbouring superpixels which features are used for classi cation of each particular superpixel. So we report performance metrics for di erent values of N to illustrate the performance of proposed graph Laplacian framework applied to di erent local models. Second, the toolbox in1 available at http://www.emt.tugraz.at 2 code available at http://vlblocks.org/index.html (a) input image (b) N=0 (c) N=1 (d) N=2 (e) N=3 (f) N=4 cludes implementation of discrete CRF with graph-cut inference, which we use for comparison. Note, this CRF model uses similar types of features (color and spatial coordinates of superpixels) to those used in our graph Laplacian.
In our experiments on GrabCut dataset we used the same over-segmentation and the same local appearance model based on SVM as [6]. To obtain initial estimates yi for graph Laplacian framework we scaled SVM outputs to [0; 1] interval for each image.
In the rst experiment the parameters and were validated on the GrabCut dataset. In the second experiment we validated the parameters on the test set. In the third experiment we used our unsupervised learning method for choosing the parameters individually for each image. We also compared with Vlblocks implementation of CRF with graph-cut inference. The strategy for choosing internal parameters of CRF was the same as in [6].
Table 1 contains results of the comparison. Our unsupervised learning gives results comparable to upper bound on performance of graph Laplacian with cars bNi=ke0 pers cars bNi=ke1 pers cars bNi=ke2 pers cars bNi=ke3 pers cars bNi=ke4 pers (SOOOGvVuuuraaMrrrlipsssdh.((CGlveauraltaribdnC.tt)uest)tset) 5454503416.....00296 6565607063.....17953 5454569899.....03541 6666550659.....52316 6666687686.....71849 6666638839.....95864 7776710182.....61900 7776600099.....82425 7766700661.....84963 7776720293.....27643 7777712100.....00273 6666759950.....45422 6776780061.....80854 7777722113.....22952 6666648378.....20639 Table 1. Performance on Graz dataset at equal precision and recall rates for "cars", "bike" and "person" classes. First row: local appearance model (from VlBlocks toolbox). Second row: result of applying discrete CRF with graph cut inference (from VlBlocks toolbox). Third row: graph Laplacian with parameters validated on GrabCut dataset. Fourth row: graph Laplacian with parameters validated on the test set. Fifth row: graph Laplacian with parameters learnt individually for each image. For each appearance model used in our experiments (we varied the number of neighboring regions as in [6]) the best result is shown in bold font. Underlined are the best overall results.
xed parameters from the second experiment. The value of performance gain compared to local appearance model di ers for di erent values of parameter N . The smaller N is the smaller neighborhood is considered by low-level model, and the more signi cant is the gain in performance attained by both CRF and graph Laplacian.
The gain in performance of graph Laplacian is almost uniformly higher than the performance gain obtained by discrete CRF. Figure 2 shows results provided by local appearance model (SVM) and corresponding results of using graph Laplacian with learnt parameters. Figure 3 shows how the results vary for di erent local models.
The running time is the following: learning phase takes about 0.2 seconds on average, solving of linear system 3 takes about 0.02 seconds on average. 5
We presented a method for tuning internal parameters of graph Laplacian in a fully unsupervised manner individually for each test image. Proposed method has a low computational cost and shows better performance compared to discrete CRF with graph-cut inference. In the future work we plan to use more complex distance functions and investigate the case then distance function has more parameters.