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

Abstract 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. It is shown that dynamic‐programming (DP) matching can be treated as a special case of the extended method. 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 extended relaxation matching.