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 surfaces can be constructed quickly for high level vision purpose [Biswas et 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 surface segmentation wherein the problem of surface segmentation is modelled as a quantization problem. The surface normals are quantized to some predefined directions, or stated otherwise, the surface regions are approximated by planar surface patches which are parallel to some predefined planes. The novelty of the algorithm lies in the fact that, though surface segmentation is achieved by quantization of surface normals, the algorithm does not compute the surface normals explicitly. Rather the quantization is achieved using simple operations of shift, subtract and threshold. This technique suitably avoids the computations of the differential properties of the surfaces or the surface fitting expressions which are used in most of the other existing techniques. Hence this approach is computationally attractive. This algorithm is easily implementable on an SIMD array computer. Another advantage of this technique is that it is robust to noise present in the image. The algorithm has been explained with a number of examples. Experimental results with synthetic as well as real range images are cited in this paper to highlight distinctive features of the algorithm.