DIMACS TR: 2002-45

Serial and tree-serial dynamic programming with application to fact identification

Authors: Vadim Mottl and Ilya Muchnik


This report continues the series of DIMACS Technical Reports on the variational approach to constructing algorithms of data analysis that consists in systematically exploiting the fact that all the kinds of decision making rest on the intent, at least, a mental one, to minimize an appropriate measure of discrepancy between the observed data set and result of its processing in the form of a model of the original data set to be evaluated. The specificity of the optimization problems adequate to a majority of practical data analysis problems is that the variables constituting the sought-for data set model are associated with the nodes of a graph that determines its a priori structure. As a rule, the objective function to be minimized turns out to be pair-wise separable in accordance with this graph, i.e. be the sum of partial functions of one and two variables associated with nodes and edges of graph.

However, for a separable objective function of general kind, the problem of global optimization does not lend itself to an effective algorithmical solution until the variable adjacency graph is assumed to be a tree. For this latter kind of objective functions, the original optimization problem breaks up into a hierarchy of partial problems each of which consists in the optimization of a set of functions of only one variable. The proposed principle of solving tree-like pair-wise separable optimization problems on the basis of a hierarchical elimination of variables is called in this Report the tree-serial dynamic programming as a generalization of the classical serial dynamic programming.

Such a structure of the interaction of variables in an objective function is an intermediate special case between easily solvable serial problems and challenging nonserial ones. It is shown, that such a moderate generalization, on the one hand, retains practically all the computational advantages of the serial problems and, on the other, easily allows for using it, with a bit of heuristics, in solving typical image processing problems.

As a practical problem, we address in this work the problem of face recognition from a single image. The tree-serial dynamic programming is applied to fulfill a nonlinear transformation of one image plane relative to another by spatially constrained elastic matching of two pixel grids for the purpose of featureless face identification by immediate measuring image similarity. The method provides the linear computational complexity with respect to the number of pixels without application of parallel computers.

It will be shown in the next Report that the proposed approach is adequate, along with the problem of face identification, also the problems of face detection and tracking in an image flow and, so, covers the entire concept of dynamic vision.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-45.ps.gz

DIMACS Home Page