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