Radial projection: an efficient update rule for relaxation labeling

Abstract

Relaxation labeling uses contextual information for finding consistent labelings of graphs. Although relaxation labeling is parallel and iterative, the complexity of updating with standard rules is too costly for practical implementation. A description is given of a computationally more efficient updating rule that utilizes radial projection instead of normal projection to avoid the complexities incurred by previous update rules when boundaries to the labeling space are encountered. This reduction in complexity is achieved by first restricting support vectors to the positive quadrant, and then using radial projection onto the constraint instead of normal projection. Crucial order information is conserved through smooth convergence towards the optimum and a rate of convergence proportional to the magnitudes of the support functions