Extended relaxation matching method, that includes dynamic-programming matching method

Various optimization methods are considered in image processing and pattern recognition. These methods have hitherto been considered independently; the purpose of this study is to systematize them, despite their difficult natures, and to indicate clearly what features they have in common and where they diverge. As a first step toward this goal, this paper proposes a method called the ‘extended relaxation matching method’, which is an extension of ordinary relaxation matching. The DP matching method is transformed in this paper into an equivalent form called product-type DP matching. The relationship between the extended relaxation matching and the DP matching is discussed on the basis of this equivalent form. It is shown that DP matching constitutes a special case of the extended relaxation matching method. As a consequence, the recurrence formula that is the core of processing by DP matching corresponds to the procedures used in all algorithms for extended relaxation matching.