Rowwise aggregation of variables in the dynamic programming algorithm for image processing

摘要

There is a wide class of image processing problems that can be formulated as optimization problems (in particular, as (min, +) labeling problems) on lattice adjacency graphs that describe the adjacency of variables. In the general case, such problems are known to be NP-complete. However, if the adjacency graph is acyclic, they can easily be solved using dynamic programming. There are many optimization techniques that use a partitioning or an approximation of a lattice graph by a set of acyclic graphs; however, some (min, +) labeling problems cannot be solved using such techniques. In this paper, an optimization technique based on a rowwise combination of variables (rather than on decomposition into acyclic graphs) is proposed that also enables one to use dynamic programming.