© The Institution of Engineering and Technology
Image labelling tasks are usually formulated within the framework of discrete Markov random fields where the optimal labels are recovered by extremising a discrete energy function. The authors present an alternative continuous relaxation approach to image labelling, which makes use of a quadratic cost function over the class labels. The cost function to be minimised is convex and its discrete version is equivalent up to a constant additive factor to the target function used in discrete MRF approaches. Moreover, its corresponding Hessian matrix is given by the graph Laplacian of the adjacency matrix. Therefore the optimisation of the cost function is governed by the pairwise interactions between pixels in the local neighbourhood. This leads to a sparse Hessian matrix for which the global minimum of the continuous relaxation problem can be efficiently found by solving a system of linear equations using the Cholesky factorisation. The authors elaborate on the links between the method and other techniques elsewhere in the literature and provide results on synthetic and real-world imagery. The authors also provide a comparison with competing approaches.
References
-
-
1)
-
Torr, P.H.S.: `Solving markov random fields using semi definite programming', Int. Workshop on Artificial Intelligence and Statistics, 2003.
-
2)
-
T. Davis
.
(2006)
Direct methods for sparse linear systems.
-
3)
-
Boykov, Y., Jolly, M.P.: `Interactive graph cuts for optimal boundary & region segmentation of objects in n-d images', Int. Conf. Computer Vision, 2001, p. 105–112.
-
4)
-
Zhu, X., Ghahramani, Z., Lafferty, J.: `Semi-supervised learning using gaussian fields and harmonic functions', 20thInt. Conf. Machine Learning, 2003.
-
5)
-
L. Grady
.
Random walks for image segmentation.
IEEE Trans. Pattern Anal. Mach. Intell.
,
11 ,
1768 -
1783
-
6)
-
S.Z. Li
.
(2001)
Markov random field modeling in image analysis.
-
7)
-
F. Chung
.
(1994)
Spectral graph theory.
-
8)
-
Kumar, M.P., Torr, P.H.S., Zisserman, A.: `Solving markov random fields using second order cone programming relaxations', IEEE Conf. Computer Vision and Pattern Recognition, 2006, p. 1045–1052.
-
9)
-
Martin, D., Fowlkes, C., Tal, D., Malik, J.: `A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics', Int. Conf. Computer Vision, July 2001, 2, p. 416–423.
-
10)
-
Keuchel, J.: `Multiclass image labelling with semidefinite programming', European Conf. Computer Vision, 2006, p. 454–467.
-
11)
-
Zhou, D., Bousquet, O., Lal, T., Weston, J., Schölkopf, B.: `Learning with local and global consistency', Neural Information Processing Systems, 2003.
-
12)
-
Rother, C., Kolmogorov, V., Lempitsky, V.S., Szummer, M.: `Optimizing binary mrfs via extended roof duality', IEEE Conf. Computer Vision and Pattern Recognition, 2007.
-
13)
-
W.T. Freeman ,
E.C. Pasztor ,
O.T. Carmichael
.
Learning low level vision.
Int. J. Comput. Vis.
,
1 ,
25 -
47
-
14)
-
V. Kolmogorov ,
R. Zabih
.
What energy functions can be minimized via graph cuts.
Trans. Pattern Anal. Mach. Intell.
,
2 ,
147 -
159
-
15)
-
Y. Boykov ,
O. Veksler ,
R. Zabih
.
Fast approximate energy minimisation via graph cuts.
IEEE Trans. Pattern Anal. Mach. Intell.
,
11 ,
1222 -
1239
-
16)
-
Y. Boykov ,
V. Kolmogorov
.
An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision.
IEEE Trans. Pattern Anal. Mach. Intell.
,
9 ,
1124 -
1137
-
17)
-
D. Greig ,
B. Porteous ,
A. Seheult
.
Exact maximum a posteriori estimation for binary images.
J. R. Stat. Soc. Ser. B
,
271 -
279
-
18)
-
E.R. Hancock ,
J.V. Kittler
.
Discrete relaxation.
Pattern Recognit.
,
711 -
733
-
19)
-
Szeliski, R., Zabih, R., Scharstein, D.: `A comparative study of energy minimization methods for markov random fields', European Conf. Computer Vision, 2006, p. 16–29.
-
20)
-
Cour, T., Shi, J.: `Solving markov random fields with spectral relaxation', Int. Conf. Artificial Intelligence and Statistics, 2007.
-
21)
-
J. Keuchel ,
C. Schnorr ,
C. Schellewald ,
D. Cremers
.
Binary partitioning, perceptual grouping, and restoration with semidefinite programming.
IEEE Trans. Pattern Anal. Mach. Intell.
,
11 ,
1364 -
1379
-
22)
-
S. Geman ,
D. Geman
.
Stochastic relaxation, gibbs distributions, and the bayesian restoration of images.
IEEE Trans. Pattern Anal. Mach. Intell.
,
721 -
741
-
23)
-
C. Rother ,
V. Kolmogorov ,
A. Blake
.
GrabCut – interative foreground extraction using iterated graph cut.
ACM Trans. Graph.
,
3 ,
309 -
314
-
24)
-
Ravikumar, P., Lafferty, J.: `Quadratic programming relaxations for metric labelling and markov random field map estimation', Int. Conf. Machine Learning, 2006, p. 737–744.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cvi_20080033
Related content
content/journals/10.1049/iet-cvi_20080033
pub_keyword,iet_inspecKeyword,pub_concept
6
6