METHOD AND APPARATUS FOR DETERMINING A SEQUENCE OF TRANSITIONS

摘要

An apparatus and a method of determining a sequence of transitions for a varying state of a system, wherein the system is described by a finite number n of states, and wherein a transition from a current state to a next state causes a cost in dependence of a distance that is dependent on a previous state, the current state, and the next state. The method comprises: combining each two consecutive states to generate super states, wherein the cost for a transition from a current super state to a next super state only depends on the current super state and the next super state; in an iterative process, applying a dynamic programming algorithm to the super states in order to determine a minimum accumulated cost for each varying super state and to determine a preceding super state that led to the minimum accumulated cost; and after a final iteration, determining a final super state with the minimum accumulated cost and retrieving the sequence of the preceding super states leading to the final super state with the minimum accumulated cost.

主权项

1. A method for determining a sequence of optimal states for a varying state of a system describing a varying margin line in a sequence of images, the margin line being divided into a plurality of segments, wherein for each segment an optimal state out of a finite number of n states is to be determined, each state describing a profile across the margin line, and wherein a transition from a current state in a current segment to a next state in a next segment causes a cost in dependence of a distance that is dependent on a previous state in a preceding segment, the current state, and the next state, the method comprising:
combining the states of each two consecutive segments along the margin line into super states; and determining an optimal state for each segment by applying a dynamic programming algorithm to the sequence of super states.