Stochastic Graduated Graph Approximation Algorithm for MRF optimization

MRF;discrete optimization;graph approximation.;621

공과대학 전기·컴퓨터공학부 ;

University:서울대학교 대학원

关键词: MRF;    discrete optimization;    graph approximation.;    621;   

Others  :  http://s-space.snu.ac.kr/bitstream/10371/123161/1/000000026116.pdf

美国|英语

来源: Seoul National University Open Repository

【 摘 要 】

approximate solutions, in most cases are provided for efficiency. In this workgraduated optimization technique is applied in a novel way to develop an efficient al-gorithm for solving general multi-label MRF optimization problem called StochasticGraduated graph approximation (SGGA) algorithm. The algorithm initially min-imizes a simplied function and progressively transforms that function until it isequivalent to the original function. However, it is hard to nd how to generate thesequence of intermediate functions and what parameter to use for making transitionfrom one problem to another. For this we propose a new iterative method of build-ing the sequence of approximations for the original energy function. We exploit astochastic method to generate intermediate functions, which guides the intermedi-ate solutions to the near-optimal solution for the original problem. The transitionfrom one intermediate problem to another is controlled by the schedule of gradualaddition of edges. In each iteration, a deterministic algorithm such as block ICM isapplied to minimize intermediate functions and to generate initial solution for thenext problem. The proposed algorithm guarantees the convergence of local mini-mum. We test on a synthetic image deconvolution problem and also on the set ofexperiments with the OpenGM2 benchmark.