A new relaxation algorithm based on distribution of matched errors and possibility is proposed to solve efficiently correspondence problem. This algorithm can be applied to various method, such as BMA, feature-, and region-based matching methods, by modifying its smoothness function. It consists of two stages which are transformation and iteration process. In transformation stage, the errors obtained by any matching algorithm are transformed to possibility values according to these statistical distribution. Each grade of possility is updated by some constraints which are defined as smoothness, uniqueness, and discontinuity factor in iteration stage. The discontinuity factor is used to reserve discontinuity of disparity. In conventional methods, it is difficult to find proper weights and stop condition, because only two factors, smoothness and uniqueness, have been used. However, in the proposed mthod, the more smoothing is not ocurred because of discontinuity factor. And it is efective to the various image, even if the image has a severe noise and repeating patterns. In addition, it is shown that the convergence rate and the quality of output are improved.