DocumentCode :
3016825
Title :
P3 & Beyond: Solving Energies with Higher Order Cliques
Author :
Kohli, Pushmeet ; Kumar, M. Pawan ; Torr, Philip H S
Author_Institution :
Oxford Brookes Univ., Oxford
fYear :
2007
fDate :
17-22 June 2007
Firstpage :
1
Lastpage :
8
Abstract :
In this paper we extend the class of energy functions for which the optimal alpha-expansion and alphabeta-swap moves can be computed in polynomial time. Specifically, we introduce a class of higher order clique potentials and show that the expansion and swap moves for any energy function composed of these potentials can be found by minimizing a submodular function. We also show that for a subset of these potentials, the optimal move can be found by solving an st-mincut problem. We refer to this subset as the P3 Potts model. Our results enable the use of powerful move making algorithms i.e. alpha-expansion and alphabeta-swap for minimization of energy functions involving higher order cliques. Such functions have the capability of modelling the rich statistics of natural scenes and can be used for many applications in computer vision. We demonstrate their use on one such application i.e. the texture based video segmentation problem.
Keywords :
computational complexity; computer vision; graph theory; image segmentation; video signal processing; P3 Potts model; alpha-expansion; alphabeta-swap moves; computer vision; energy functions minimization; higher order clique potential; natural scenes; polynomial time; st-mincut problem; video segmentation problem; Application software; Approximation methods; Computer vision; Higher order statistics; Inference algorithms; Labeling; Layout; Minimization methods; Polynomials; Random variables;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Vision and Pattern Recognition, 2007. CVPR '07. IEEE Conference on
Conference_Location :
Minneapolis, MN
ISSN :
1063-6919
Print_ISBN :
1-4244-1179-3
Electronic_ISBN :
1063-6919
Type :
conf
DOI :
10.1109/CVPR.2007.383204
Filename :
4270229
Link To Document :
بازگشت