Relaxation optimizing operations in extended probabilistic space

Abstract

The classical probabilistic relaxation method has been widely used to solve optimization problems in various fields, including image processing and pattern recognition. The authors have also been developing handwritten character recognition system using the probabilistic relaxation method. However, we realize that there exist cases in which a probability theoretic model is inadequate, especially where there exists incompleteness in available information by noise such as patchy segments and ink spots. In that case, we must introduce ad hoc rules for one-to-two correspondence and no correspondence in the probabilistic algorithm. As the Dempster-Shafer (DS) theory is a kind of natural extension of the probabilistic theory by reducing additivity on probability measure and it can cope with incomplete data. This paper proposes a relaxation matching method based on the Dempster-Shafer theory. Then the update process in probabilistic relaxation method is derived as a special case of Dempster's combination rule in DS theory.