AN SIMD ALGORITHM FOR RANGE IMAGE SEGMENTATION

Understanding 3D scenes from range images need the segmentation of 3D surfaces into approximate planar surface patches from which curved sur faces can be constructed quickly for high level vision purpose [Biswas el al., Qualitative description of three-dimensional scenes, Intl. J. Pattern Recognition and Artificial Intelligence 6(4), 651-672 (1992)] . In this paper we have presented a new parallel algorithm for 3D surf ace segmentation wherein the problem of surface segmentation is modell ed as a quantization problem. The surface normals are quantized to som e predefined directions, or stated otherwise, the surface regions are approximated by planar surface patches which are parallel to some pred efined planes. The novelty of the algorithm lies in the fact that, tho ugh surface segmentation is achieved by quantization of surface normal s, the algorithm does not compute the surface normals explicitly. Rath er the quantization is achieved using simple operations of shift, subt ract and threshold. This technique suitably avoids the computations of the differential properties of the surfaces or the surface fitting ex pressions which are used in most of the other existing techniques. Hen ce this approach is computationally attractive. This algorithm is easi ly implementable on an SIMD array computer. Another advantage of this technique is that it is robust to noise present in the image. The algo rithm has been explained with a number of examples. Experimental resul ts with synthetic as well as real range images are cited in this paper to highlight distinctive features of the algorithm.