Von-Wun Soo and Karen Huang
Department of Computer Science
National Tsing Hua University
Hsinchu, Taiwan 30043, R.O.C.
The traditional relaxation labeling (RL) scheme  suffers from the difficulty of computing correlations or compatibilities. We extend RL into an extended relaxation labeling (ERL) scheme by redesigning the way of calculating compatibilities. Furthermore, a new scheme using Dempster-Shafer theory to combine the uncertain knowledge sources, called the evidential relaxation labeling (EVRL) scheme, is proposed. These two schemes accept relational and constraint information from problem domains and translate them into numerical compatibilities so that a relaxational weight updating process can be carried out. We show that the EVRL scheme has advantages over the RL scheme as well as the ERL scheme. Firstly, it provides a more general framework for expressing uncertain knowledge. Secondly, it avoids the difficulty of computing numerical or probabilistic compatibilities. Thirdly, it takes less iterations to converge.
Keywords: Dempster-shafer theory, relaxation labeling, knowledge-based vision, compatibility mapping, uncertainty reasoning, evidential reasoning, object relations, and label constraints
Received September 7, 1992; revised March 9, 1993.
Communicated by Wen-Hsiang Tsai.