Taesup Kim, Pushmeet Kohli, Sebastian Nowozin and Chang D. Yoo
This research deals with the problem of efficiently solving large-scale energy minimization problems encountered in computer vision. We propose an energy-aware method for merging random variables to reduce the size of the energy to be minimized. The method examines the energy function to find groups of variables which are likely to take the same label in the minimum energy state and thus can be represented by a single random variable. We propose and evaluate a number of extremely efficient variable grouping strategies. Experimental results show that our methods result in a dramatic reduction in the computational cost and memory requirements (in some cases by a factor of one hundred) with almost no drop in the accuracy of the final result. Comparative evaluation with efficient super-pixel generation methods, which are commonly used in variable grouping, reveals that our methods are far superior both in terms of accuracy and running time.
The 9 variables in the original energy (a) are merged to obtain a new energy (c) defined on only 3 grouped variables. The final solution (d) is now computed by solving the smaller problem (c). The solution may differ slightly from the MAP solution (b) of the original problem.
Variable grouping reduces the energy minimization problem size with only a small loss in accuracy. The budget is the relative number of variables used in our approximation.