How to Compute a Primal Solution From Dual One in LP Relaxation of MAP Inference in MPF?

Abstract

Описан метод получения оптимальной размытой разметки по оптимальному решению двойственной задачи LP-релаксации на марковских случайных полях. Метод основан на LP-релаксации специального вида и алгоритме (max,+)-диффузии.The method for computation of the optimal relaxed labeling from the optimal solution of a dual problem in the LP-relaxation of Markov Random Fields is described. The method is based on the particular form of the LP-relaxation and the (max,+)-diffusion algorithm.Описано метод отримання оптимальної розмитої розмітки за оптимальним розв’язком двоїстої задачі LP-релаксації на марківських випадкових полях. Метод базується на LP-релаксації спеціального типу і алгоритмі (max,+)-дифузії.