Dynamic Programming Procedures for Image Analysis

A.V. Kopylov (Russia)


Signal and image processing, optimization, dynamic pro gramming.


Most of image or 3D arrays processing problems may be mathematically formulated as optimization problems of a special kind over the set of variables associated with pixels of the discrete image plane. The specificity of these optimi zation problems consists in the structure of the objective function which is sum of elementary objective functions each depending on a pair of variables at immediately neighboring pixels. If the variables of such an objective function are ordered like a chain, the classical dynamic programming is the appropriate means of solving this kind of optimization problems with linear computational com plexity relative to the number of variables. In this paper we show that all the computational advantages of dynamic programming are retained for tree-like adjacency of pairs of variables. To benefit from this fact in constructing image processing algorithms, we propose replace the lattice of pixel neighborhood in two- or three-dimensional images by a series of trees. A series of image processing algorithms of linear computational complexity with respect to the number of pixels is proposed for both discrete and continuous goal variables at pixels. In the latter case, the algorithms essen tially exploit the Kalman-Bucy filter of special kind applied to horizontal and vertical rows of the image.

Important Links:

Go Back