# Introduction any researchers have studied the range image segmentation in the 80's mainly, then, this area has been neglected at the expense of intensity images due to their easy acquisition (acquiring a range image requiring a laser) and they are much more prevalent that the range images. During the past decade, with the influx of 3D geometric representations and their complex geometric representations a different interest was focused on range images, 3D image segmentation can go through a projection of the 2D image for segment it as a range image. So much work on the range images were presented and improvements have been made but not using the deformable model. Range image segmentation algorithms can be broadly classified into two categories: edge-based and regionbased segmentation. Region-based approaches group pixels into connected regions based on homogeneity measures, while boundaries between regions are located by edge detection methods. Both techniques have their strengths and drawbacks. Edge detection is mostly criticized for its tendency to produce disconnected boundaries. The challenge is to extract the boundary elements belonging to the range image and this process should be performed as efficiently and automatically as possible. Deformable models, which include the popular deformable contours or snakes are a powerful segmentation technique designed to meet this challenge, they tackle the segmentation problem by considering an object boundary as a single, connected structure and exploit a priori knowledge of object shape and inherent smoothness, usually formulated as internal deformation energies, to compensate for noise, gaps and other irregularities in object boundaries. Our work was fully motivated by the fact that there are no algorithms known from the literature that used an active contour « Snake » for range image segmentation and a classification according to the criterion of homogeneity was never been proposed before. In this work, the first section will be dedicated to the definition of the range image and its capture mode, then, an extensive survey on the range image segmentation methods will be made to establish a classification that will have an overview of the field and will facilitate a possible proposal of an algorithm for range image segmentation. Finally a deformable model "snake" will be proposed to segments range images. # II. # The range image a) Definition A range image (RI) is a two-dimensional array of 3D positions [1] satisfying the property of spatial coherence, each component of this matrix represents the distance between a reference point and a point in the field of vision sensor. It is the equivalent of a video image [2 ] in which the gray level of each pixel (x, y) is replaced by an altitude z (2.5D is an intermediate case between the 2D and 3D, it is not fractal dimensions).The peculiarity of this type of data lies in the grid structure (x, y) and the possibility of describing the scene as a graph of function z = f (x, y) the term of Rangel (range image element) denotes an element of the range image. The range images can be seen as clouds of 3D points [3] and have a regular representation [4] and are considered as organized in the sense that neighboring points in the range image are also neighbors in space. In some works [5] an image of accumulation of point clouds is associated to a range image, using a virtual camera positioned on the XY plane, the range image records the maximum distance of 3D points projected onto the plane of the camera and the image of accumulation counts the number of points (3D) that are projected onto the same pixel camera. The range images offer a precise correspondence with the latest laser scanning techniques [6], we found range images in areas such as image recognition, image retrieval, image transmission, modeling object, location and simultaneous construction of a map. The depth is the distance between the visible surface of objects in a scene and the sensor of the camera, it is a useful indication for the calculation of the coordinates of points on the surface in threedimensional space of reference, many methods have been developed [7] to obtain the 3D coordinates of objects using images, all exploit changes in acquisition parameters of the system of shooting, the acquisition parameters of the system or the light environment provides essential information to establish a relationship between the image and the real scene. # c) Range Image Acquisition Systems There are a wide variety of acquisition systems for range images, they are distinguished by the method of measurement, geometry of the device, the accuracy and speed, here, only two examples are presented for illustrative purposes. ? The first is an [8] experimental laboratory system "Fig. 2" made with non-specialized equipment where a laser beam shaped plan illuminates the scene, the beam draws a visible trace on the surface of objects and the trace is marked in the image of a camera and thinned to a width of one pixel. For each pixel of the trace in the image, the 3D point defined by the intersection of the plane of light and line of sight corresponding to the pixel is calculated and this is used as Rangel. Fig. 2 : Experimental system for range image acquisition ? The second is a system sold, operating on the principle of flight time "Fig. 3". An amplitude modulated laser beam is projected in one direction [9] and a light sensor measures the light returning to the source, with amplitude modulation lag between the light signal emitted and received. The time shift is a direct measure of the distance between data acquisition and surface area encountered by the laser beam and a measure of distance in one direction to define a point in the RI, the range image is built by scanning the laser beam. The curvature estimation is affected by the presence of noise (measurement error) and the presence of discontinuities. The estimate of curvature is sufficiently good but must be low noise, on the other hand, we must eliminate disturbances due to discontinuities by proper treatment for this type of thresholding segmentation method and labeling of connected components is preferred. ? Besl and Jain [10] use this segmentation only to determine initial seeds and then perform an independent growth region. ? Yokoya and Levine [11] combined with the detection of discontinuities in segmentation type of curvature, discontinuities of the image is used as a mask during the labeling of connected components of the image type of curvature, then a simple region growing is applied to the image. ? Kasvand [12] performs an erosion of 1 to 2 pixels on the image type of curvature to remove the effect of discontinuities, then place in the labeling of connected components of the image type of curvature and finally growing regions is performed. # b) Surface Segmentation Two criteria define segmentation into homogeneous flat surfaces "same orientation" and "same plane equation" methods based on the first criterion must take into account the discontinuities of depth to prevent a merger between two planes parallel but not collinear (example, an upper surface of a cube and a surface on which it is placed). Taking into account ( D D D D ) F 2012 June the discontinuities of order 0 is often made implicitly, it is estimated through the orientation of discontinuities, it creates a zone of steep acting separation and the major inconvenient is the appearance of regions (segments) parasites. ? Maitre and Hügli [13] have a fusion method based on normal (gradient) to the surface normal are calculated on the facets of minimum size, these facets are used as initial partition. Then, the fusion is performed sequentially by merging each time, among all pairs of neighboring regions, those with the angle between the normal is the smallest. ? Parvin and Medioni [14] use a method of divisionfusion based on the normal to the surface or, more precisely, the gradient of the range image, the gradient is estimated by the conventional method using a 3x3 neighborhoods, the method of divisionfusion is then applied to the image gradient, the ? measure defines the homogeneity criterion for the division (the standard deviation of the gradient). The angle value between normal vectors associated with the regions define the homogeneity for fusion, this method is subject to the same phenomenon of parasitic regions as Master and Hügli. ? Taylor [15] applies the method of dividing an image fusion of normal (gradient), the estimated gradient is a suitable neighborhood, and the problem areas of parasites is eliminated at the division and fusion, a depth test must be done when the homogeneity tests are positive on the normal, this prevents parallel planes separated by a discontinuity in depth form a single segment. # c) Segmentation in Algebraic Surfaces The segmentation of algebraic surfaces (not strictly planar) is divided into two categories depending on the nature of 2.5D and 3D surfaces, surfaces 2.5D all correspond to polynomial functions of two variables and obviously apply only images of scalar type. The 3D surfaces are the quadrics and super quadrics where the treatment is more complex than 2.5D surfaces. ? Leonardi [16] presents a method (independent growth areas) division-fusion linked to a 2.5D surface model type polynomial (the degree of the polynomial can vary from 0 to 3), the test for homogeneity division and the merger is based on the approximation error of image values by the polynomial of best approximation and in the merger, approximation error and the polynomial coefficients are updated from those regions merged (It is not necessary to calculate an approximation of the new region), for this method, it is necessary to extract first the depth discontinuities. ? Gupta and Bajcsy [17] present a segmentation method that result in the description of the range image by superquadrics (specifically superellipsoid). To achieve the result, the approach taken by Gupta performs geometric reasoning on the basis of two other segments, the 2.5D surfaces preliminary segmentation and a current segment of super-ellipsoid approximation residues, this process goes beyond the treatment of low-level image depth. ? Jiang and Bunke [18] conduct a region growing constrained approximation by a plane (2.5D), the method of growth is special because it is based on straight line segments, regions are lists segments and the growth is done segment by segment, line segments are obtained by dividing a profile (row or column) of the range image. Regional growth is sequentially (one region after another). The seed which is initialized with the growth consists of three line segments neighboring profiles from three consecutive growth starts with the seed that best satisfies a test of parallelism between segments. # d) Segmentation of Continuity of Order 1 Several methods lead to segmentation with the criterion of homogeneity of surface can be defined as C1 continuity, two principles are applied. # ? Detection of discontinuities and labeling of connected components: This is the principle of boundary detection described above, the border points are the points of discontinuity (C ^ 0) and (C ^ 1). In the Davignon's approach [19], growth in the field of border points detected is performed so as to form still closed borders, the growth is done by choosing at each step the neighboring pixel which is the measure of discontinuity nearest (below) the threshold, once the closed borders, regions are approximated by a related algebraic surface (polynomial type) of increasing complexity, until the approximation error is sufficiently small, the position of the discontinuities is then adjusted based on this surface representation. ? Fusion of segments from a segmentation constraint: The method of Besl [20] begins with a segmentation by type of curvature, the derived regions are eroded from seed obtained, the method proceeds by growth, as described above, finally takes place a merger of the regions on the basis of the presence or absence of discontinuity between regions. This process has the effect of systematic closure of borders associated with discontinuities. # e) Other Segmentation Methods The methods described below apply the same principle of merging segments more constrained as the method of Besl, however, the merger is based on more restrictive conditions than the absence of discontinuities between segments, the final segmentation therefore obeys a homogeneity criterion more stringent than C1 continuity. # ( D D D D ) F ? The method used by Ade and Ylä-Jääski [21] has three steps. The first step is a "clustering" of normal vectors and labeling of connected components, the small regions (narrow) are eliminated at the end of this first stage, the second stage performs a growth of conserved regions, finally, held a melting step in which two adjacent regions are merged if their normal and principal curvatures have similar values and if they have a sufficiently long common border. ? Wand and Suter developed the MDPE (Maximum Density Power Estimator) which is a nonparametric estimator of density and including the gradient estimation techniques [22] similar to many random sampling estimators. The algorithm consists of choosing a search window and a p-random subset, then the Mean Shift algorithm is applied on every point of the window, then the density is calculated on all data points of the window chosen to determine the power density. The essence of the method lies in the application of several procedures for finding the maximum local density of these residues (data points with less residue should be as many as possible, and residues should be as low as possible). ? Paulo Fabiano proposes an algorithm [23] for range image segmentation combining depth and region technical. First, a 3 * 3 median filter and an analysis of main components is applied to estimate the vectors of surfaces, then for each pixel, the angular variation in the normal direction is calculated from the pixel P in a Q pixel neighborhood, after the use of a low and high threshold, each point is then marked as belonging to a flat, curved, or indeterminate (if not), this pre-treatment allows the classification of pixels to be used to identify flat and curved regions. June best location of one or more surface models in the picture. ? Flat surface: The methods are numerous, but most use specific properties to a flat surface, the segmentation into planar surfaces should be treated the same way as the more general case of algebraic surfaces. ? Continuity C1: Next to the simple method of segmentation following C1, there are sophisticated methods, all the effort invested by these methods is devoted to forcing the closure of borders defined by the discontinuities, a systematic closure of borders is a change in the criterion of homogeneity, making it more restrictive than the pure C1 continuity, it is noted that it provide, unlike other methods, a simplified representation of the segment. IV. # Range image segmentation using an active contour As we can see, so much works on the range images were presented and improvements have been made but not using the deformable model, this may be due to the noise in the range image (the range images are too noisy) which may distort the results knowing the snake sensitivity. The frame work of active contours minimizes the contour energy E defined as the sum of external energy and internal energy. The external energy pulls the contours towards desired image features while the internal energy helps achieve smooth boundaries. An early implementation of active contours, called Snakes, is based on deforming an initial contour at a number of control points selected along a given initial contour. The deformation is directed towards the object boundary by minimizing the energy E so that its local minimum occurs at the boundary of the object. # a) Development and Design The algorithm developed consists of an active contour model "Snake" defined as a geometric object with parameters such as orientation, position, shape, this parameters change the image to reach a stable state, while respecting a set of constraints. The steady state corresponds to the minimum of energy E. The energy model (Formula1) includes a term of internal energy regularization or smoothing term and external power or fitness to the data. The method is to minimize this energy by deforming the contour until the points of the snake does not change their positions. The proposed algorithm was implemented in java NetBeans which is a RAD (Rapid Application Development) designed by Sun for creating applications and a GUI with the publisher resources while benefiting from the robustness of the Java language. i. # Our Segmentation Algorithm Before starting the segmentation, the image is filtered by the Floyd & Steinberg filter which improves the overall perception of a range image and to avoid the exclusion of the area of low intensity "Fig. 5 (d)", as shown in "Fig. 5(c)" a piece of bone is neglected because of its low intensity, the aim is to use a simple threshold dithering "Fig. 5 (b)" on each pixel and to accurately account for the errors in brightness it induces. We define our snake model as closed 2D contour elements. We associate with these nodes time varying consisting of a set of nodes connected in series. The Snake is initialized on the center of the image and composed of 40 nodes. The internal and external energies are calculated for each snake point to characterize the outline shape and all the elements of its own and the positioning of the contour on the image taking into account the gradient lines. For each contour point, we determine a new position, on which the contour should minimize the difference constraints. Then, we arrange the contour to respect the constraint of distance between the regular points (we rebuild the snake using cubic spline interpolation). As we can see in Fig. 6 these last two steps are repeated until the stopping condition is reached (impossible to improve the positioning of the snake points or when the maximum number of iterations is reached). Where ? and ? are two real constants, respectively, coefficients of elasticity and rigidity of the curve. An analogy compares the energy behavior of the snake to that of a membrane (a term related to the spring constant) and that of a thin plate (a term related to the stiffness constant). We denote by v (s) = (x (s), y (s)) (the arc length s ? [0, 1]) the current point of the contour C. Volume XII Issue X Version I of the curve. This energy is composed of two terms, a first-order term corresponding to the energy of continuity, which increases when the curve is weakening and a second-order term corresponding to the curvature, which increases when the curve bends sharply such as obtaining a corner (Formula-1). iii. # Calculation of the External Energy External energy is the adequacy of data and therefore depends on the processed image. Typically, in segmentation, this energy (Formula-1) is equal to the gradient that will attract the curve towards the edges of an object in an image. # Convergence Condition The snake algorithm stops when it reaches a steady state in which no point change position. To prevent the search does continue indefinitely if the points continue to change their positions, a maximum number of iterations is determined. If this number is reached, the search terminates and the result of the current iteration is proposed as a final solution. # b) Experimentation Here we present the segmentations produced by our algorithm on several images. We have segmented from a variety of range images from the database of Stuttgart University. The database contains a collection of synthetic range images taken from highresolution polygonal models available on the web [24]. Six of these models were reconstructed from real range scans in the Stuttgart lab (07_Deoflach, 08_Deorund, 15_Mole, 24_Kroete, 28_Ente, 29_Schwein). These range images are in a custom format (RIF), which is an ASCII file. This database contains 10836 images (42 images from different angles). The snake algorithm was applied to twenty range images. For our first experiment we applied the snake to the simple images containing no cavities, then, in the second experiment we applied the snake for images with cavities. As we can see in Fig. 8 segmentations results for range images with cavity obtained are quite satisfactory, however, the results of segmentations obtained for range images with cavities are not complete and the snake did not go after the cavities, this is due to insufficient number of iterations that made the snake stops before reaching these areas. Unlike traditional snakes, the set of nodes and inter-connecting elements of our snake does not remain constant during its evolution. This model is quite versatile since it can either reproduce the classical behavior of snake with high values of regularization, but also can segment very thin and complex structures. However, this implementation has several disadvantages. First, the Snakes approach the nearest local minimum of the initial contour and are therefore prone to finding a local minimum which in general does not coincide with the object contour. This leads to sensitivity to initialization, e.g. when there are a large number of local minima near the initial contour due to image noise or background clutter. Second, the discretization of the contours into a number of control points may cause problems with uneven spacing and # Conclusions The aim of this work was to provide a new classification of the range image segmentation methods and the literature review has shown how the basic methods were used in practice, sometimes forming methods combined, although the test for homogeneity of the resulting segmentation were not always explicit. A new approach using the deformable model "Snake" was applied and the results obtained was unsatisfactory and incomplete for the range images with cavities, some items do not always converge and require additional iterations. 1![Fig.1: At right the range image, left him the image intensity corresponding b) Depth of an Image](image-2.png "Fig. 1 :") 3![Fig. 3 : Flight time system for range image acquisition III. Range image segmentation methods According to documents found in the literature, we can classify the methods of segmentation into four classes according to the criterion of homogeneity which obeys the segmentation, we can find the segmentation depending on the type of curvature, surface, algebraic surface continuity C1 and a fifth category combines other methods. a) Segmentation by Type of Curvature](image-3.png "Fig. 3 :") 4![Fig. 4: Range image segmentation methods classificationWe can still classify virtually all methods following the four criteria"Fig.4" of homogeneity (type of curve, surface, algebraic surface and continuity C1), here is an overview of methods, accompanied by critical comments. ? Type of curvature methods face the problem of estimating the curvature, it is affected by both noise and discontinuities, segmentation is representative of the measured surface as if the noise is low and if the disturbances due to discontinuities are removed by appropriate treatment.? Algebraic Surface: On algebraic surfaces there are two types of methods, division / fusion and regionindependent growth, methods of division / fusion are poorly adapted to the segmentation of range images based on a model surface because of the particular algebraic discontinuities in the methods of independent growth area, there are two approaches that differ in their fundamental principle, the approach initiated by Besl seeks a minimum approximate representation of the image depth and approach Leonardis is an exhaustive search of the](image-4.png "Fig. 4 :") 5![Fig. 5: (a) The range image, (b) the range image filtered by Floyd & Steinberg, (c) segmentation without using the Floyd & Steinberg filter, (d) segmentation after using the Floyd & Steinberg filter](image-5.png "Fig. 5 :") 6![Fig. 6: Our snake algorithm](image-6.png "Fig. 6 :") 7![Fig. 7: Sample real range images used](image-7.png "Fig. 7 :") ![while the contours are deforming, and make it difficult to extend the approach to segment 3D objects. Finally, automatic selection of various parameters such as the weights in the energy function is still an open problem.](image-8.png "") 8![Fig. 8: Segmentation results, the images are 400*400 pixels in size](image-9.png "Fig. 8 :") ![](image-10.png "") © 2012 Global Journals Inc. (US)Global Journal of Computer Science and Technology © 2012 Global Journals Inc. (US) * EmericoNatonek Fast Range Image Segmentation for Servicing Robots, International Conference on Robotics and Automation -ICRA 1998 1 * Thoma Chaperon, segmentation of point cloud 3d modeling for automatic industrial environments digitized 2002 école des mines de Paris PhD thesis * Recalage géométrique avec plusieurs prototypes Jean-PhilippeTarel institut national de recherche en informatique et en automatique des Yvelines 1996 * AtillaBaskurt, Segmentation and Superquadrics Modeling of 3D Objects, The 11-th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision LaurentChevalier FabriceJaillet February 2003 Plzen-Bory, Czech Republic * Point Cloud Segmentation towards Urban Ground Modeling JorgeHernández BeatrizMarcotegui 5 * Joint workshop on remote sensing and data fusion over urban areas Grss/Isprs May 2009 Shangai, China * Replicator Dynamics in the Iterative Process for Accurate Range Image Matching YonghuaiLiu International Journal of Computer Vision 83 1 2009 * Influence of mathematic models used on the quality of estimation of the depth in images ChristopheSimon FrédériqueBicking ThierrySimon Proceedings of 20th IEEE Instrumentation and Measurement Technology conference, IEEE/IMTC2003 20th IEEE Instrumentation and Measurement Technology conference, IEEE/IMTC2003Vail, Colorado, USA 2003 * Low-cost system for ancient stamps range image acquisition EdouardThomas FredericNicolier GillesMillon Machine Vision Applications in Industrial Inspection XIII San Jose, CA, USA January 2005 5679 * Exploiting sparsity in time-of-flight range acquisition using a single timeresolved sensor AhmedKirmani AndreaColaço NCFranco VivekKWong Goyal Optics Express 19 2011 * Segmentation through variable-order surface fitting PJBesl RCJain IEEE Trans. Pattern Anal. Machine Intell 10 March 1988 * Range image segmentation based on differential geometry: a hybrid approach NYokoya MDLevine IEEE Trans. Patt. Anal. Mach. Intell 11 June 1989 * The k1k2 space in range image analysis TKasvand Proc.9th Int. Conference on Pattern Recognition .9th Int. Conference on Pattern RecognitionItaly 1988 * Range image segmentation based on function approximation, Close-Range Photogrammetry Meets Machine Vision GMaître HHügli F& J PTièche Amann 1990 1395 * Segmentation of range images into planar surfaces by split and merge, Computer Vision Pattern Recognition BParvin GMedioni 1986 * Fast segmentation of range imagery into planar regions RWTaylor MSavini APReeves Computer Vision Graphics and Image Processing 1989 45 * Segmentation based image coding with l-infinity norm error control MDalai RLeonardi Proceedings of the Picture Coding Symposium PCS'04 the Picture Coding Symposium PCS'04USA 2004 * Integrated approach for surface and volumetric segmentation of range images using biquadrics and superquadrics, Applications of Artificial Intelligence X: Machine Vision and AGupta RRBajcsy Editor Proc.SPIE 1708 KWRobotics Bowyer 1992 * Fast segmentation of range images into planar regions by scan line grouping XYJiang HBunke 1994 * Contribution of edges and regions to range image segmentation, Applications of Artificial Intelligence X: Machine Vision and ADavignon Editor Proc.SPIE 1708 KWRobotics Bowyer 1992 * ActiveOptical Range Imaging Sensors, General Motors Research Laboratories PaulBesl 1988 Michigan USA * Segmentation and symbolic description of range images, German association for pattern recognition Symposium FAde AYlä-Jääski 1990 254 * MDPE: A Very Robust Estimator for Model Fitting and Range Image Segmentation HanziWang DavidSuter 2004 Department of Electrical and Computer Systems Engineering, Monash University, Australie * Range Image Segmentation Into Planar and Quadric Surfaces Using an improved Robust estimator and genetic algorithm Paulo Fabiano UrnauGotardo Olga Regina PereiraBellon KimBoyer LucianoSilva ieee transactions on systems, man, and cybernetics december 2004 34