
We propose a solution to determine the optimal elastic matching of a deformable template to an image. The central idea is to cast the optimal matching of each template point to a corresponding image pixel as a problem of finding a minimum cost cyclic path in the three-dimensional product space as well as in four-dimensional product space spanned by the template and the input image. We introduce a cost functional associated with each cycle, which consists of three terms: a data fidelity term favoring strong intensity gradients, a shape consistency term favoring similarity of tangent angles of corresponding points, and an elastic penalty for stretching or shrinking. The functional is normalized with respect to the total length to avoid a bias toward shorter curves. Optimization is performed by Lawler’s Minimum Ratio Cycle algorithm parallelized on state-of-the-art graphics cards. The algorithm provides the optimal segmentation and point correspondence between template and segmented curve in computation times that are essentially linear in the number of pixels. A new approach to 4-D shape-based segmentation and tracking of multiple, deformable anatomical structures used in cardiac MR images can be implemented here. We propose to use an energy-minimizing geometrically deformable template (GDT) which can deform into similar shapes under the influence of image forces. The degree of deformation of the template from its equilibrium shape is measured by a penalty function associated with mapping between the two shapes. By minimizing this term along with the image energy terms of the classic deformable model, the deformable template is attracted towards objects in the image whose shape is similar to its equilibrium shape. This allows the simultaneous segmentation of multiple deformable objects using intra-as well as inter-shape information. Simulated Annealing (SA),a stochastic relaxation technique is used for segmentation while Iterated Conditional Modes (ICM),a deterministic relaxation technique is used for tracking.