WIXLIB

INTERNATIONAL JOURNAL OF INTELLIGENT CONTROL AND SYSTEMSi is in A , otherwise xi -1. Let diw(i, j ) be thejtotal connection from node i to all other nodes. With theabove definition, Ncut ( A, B) in (1) can be calculated.According to [19] an approximate discrete solution tominimize Ncut ( A, B) can be obtained by solving thefollowing equation:yT (D W ) ymin x Ncut ( x ) min y,(2)y T Dywhere Dw(i, j ) Wdiag ( d1 , d 2 ,., d n ), di11NERI into a number of segments. Second, the LSP to eachsegment’s data points is computed and the plane-fittingstatistics are used to label each segment into a planar ornon-planar one. Third, adjacent planar surfaces with thesame orientation are merged.To simplify the description, we only consider theextraction of vertical and horizontal planes in 3D space. Asshown in Fig. 3, a vertical plane is defined as one whosenormal direction is along the –Y axis (Fig. 3a) and ahorizontal plane is one whose normal direction is along theZ axis (Fig. 3b).[ wij ],jand y(1 x ) (1 x )di . Ifdixi 0y(is a setxi 0of real numbers), then (2) can be minimized by solving thefollowing generalized Eigen value system:(3)(D W ) yDyB. Grouping AlgorithmThe grouping of pixels in an image I consists of thefollowing steps:a) Consider image I as an undirected graph G (V , E )and construct a PSM. As stated before, each element ofthe PSM is the weight of edge w(i, j ) and is calculatedby w(i, j ) expb)c)d)e) F (i ) F ( j ) 222I*expX ( j ) 22 X (i )2Xif X (i) X ( j) 2 r , otherwise w(i, j ) 0 . Here, X (i)is the spatial location of node i and F (i) I (i) is thebrightness value of pixel i . It is noted that w(i, j ) 0for any pair of nodes i and j that have a distance greaterthan r pixels. The reason for calculating w(i, j ) insuch a manner is substantiated by the followingargument: any two pixels that have similar brightnessvalue and are spatially nearer belong to the same objectmore possibly than two pixels with different brightnessvalues and are distant from each other.Solve (3) for the eigenvectors with the smallest eigenvalues.Use the eigenvector with the second smallest eigenvalue to bipartition the image by finding the splittingpoints such that its Ncut value is minimized.Recursively re-partition the segments (go to step a)Exit if Ncut value for every segment is over somespecified threshold.III. THE PROPOSED METHODIn this work, we adopt the method in [20] for rangeimage enhancement. In our previous work [18], we havedemonstrated that the use of surface normals of theSR-3000’s range data makes the surfaces and edges of anobject more distinct. Following the same approach, we firstconstruct a tri-band color image where each pixel’s RGBvalues represent the x and y components of its surfacenormal and its depth information, respectively. The tri-bandimage is then converted to a gray image, called aNormal-Enhanced Range Image (NERI). The proposedsegmentation method is divided into three steps. First, theNC algorithm is applied to the NERI and partitions the(a)(b)Fig. 3. Diagram of vertical and horizontal planesFor the N segments resulting from the NC method, weneed to identify those that best describe either vertical orhorizontal planes. To do this, we perform an LSP fit to thedata points associated with each of the N segments andcalculate the normal direction and the fitting error. Let thenormal to the LSP be denoted by N (nx, ny, nz) and theresidual of the fit, also known as Plane Fitting Error (PFE),Pdk 1 kis computed byP , where P denotes thenumber of pixels in the segment and d k is the distancebetween the kth data point (xk, yk, zk) and the LSP. The LSP. The minimization can beis found by minimizingobtained by the Singular Value Decomposition (SVD)method. First, the following matrix is constructed by usingthe data points of the segment:Mx1 x0y1 y0 z1 z0x2 x0y2y0 z2 z0x1 x0x2 x0 . . x p x0.y1 y0y2z1 z0z 2 z0.x p x0ypy0 z p z 0where y0 . . y py0. . z p z0 isthe centroid of the data points. Then the eigen values 1, 2,, and p of M and their corresponding eigenvectors arecomputed. It can be proved that N equals the eigenvectorcorrespondingtotheminimumeigenvaluemin( 1 , 2 ,., p ) andequal to min P . Themindeviation of the normal direction from Y and Z axes arecomputed byand,respectively. The value of the PFE determines whether thesegment forms a planar surface while the values of y anddetermine if the plane is vertical or horizontal. To bespecific, the data points of a segment whose PFE issufficiently small form a planar surface; and the planarz

12INTERNATIONAL JOURNAL OF INTELLIGENT CONTROL AND SYSTEMSsegment is vertical/horizontal if the value ofy/zissufficiently close to 0º.Extracting an entire plane from the scene involvesmerging of two or more planar segments. In our work,merging is performed only if two segments areneighboring. Fig. 4 shows three typical configurations oftwo close-by segments. The common boundary betweenthem is highlighted in green. Any two segments areconsidered as neighbors if there exists at least twoconsecutive common points (i.e., they belong to bothsegments and are continuous in space) on their boundaries.Thus the segments in Fig. 4(a) do not qualify as neighborssince they have a single common point whereas the twosegments in Figs. 4(b) and Fig. 4c are considered asneighbors.(a)(b)(c)Fig. 4. Definition of neighboring segments: for simplicity the segments aredrawn as rectangles: (a) Two non-neighboring segments. (b)-(c) Twoneighboring segments.The proposed method for extracting vertical andhorizontal planes from a range image is as follows:1) Construct the NERI and apply the NC algorithm topartition the NERI into N segments ci for i 1,., N .2) The planar segments ci for i 1,., N that satisfyiare selected to form a set of planar segmentsS {s1, s2 , s3 ,., sn } , i.e., a segment with a PFE smallerthan is taken as a planar surface. Here n N and isa suitable threshold.3) Each s j S is then labeled as vertical or horizontalbased on the normal direction of its LSP.4) A pair of vertical or horizontal segments is merged ifthey are neighbors.5) Terminate the process when all the neighbors aremerged.IV. EXPERIMENTS AND RESULTSWe have validated our planar surface extraction methodthrough experiments in various indoor environments thatcontain most commonly occurring structures. Our currentmethod requires a pre-specified number of clusters N. In allour experiments, we use N 100 that is bigger than theactual number of planar segments each NERI contains. Thereason for choosing such a large N is to ensure a correctsegmentation. This can be demonstrated by the example inFig. 5. The test scene is shown in Fig. 5(a) and its NERI isdepicted in Fig. 5(c). Apparently the NERI has 5 segmentsthat are hand-labeled and shown in Fig. 5(c). We now applythe NC algorithm to Fig. 5(c) using the actual number ofsegments (N 5). The result is shown in Fig. 5d. We canobserve that cluster 5 is a misclassification as it containstwo regions (with different brightness), each of whichrepresents a planar surface that is perpendicular to oneanother in 3D space. To avoid such a misclassification, weneed to assign N a number that is much bigger than theactual segment number of a scene.In all our segmentation results hereafter, we label avertical and a horizontal plane in blue and green,respectively. In the first experiment, we consider an indoor(a)(b)(c)(d)Fig. 5. Misclassification of the NC method using the exact segmentnumber a scene: (a) Actual scene. (b) Raw range image of (a). (c) NERIwith labeled segments. (d) Segmentation result of the NC over the NERI.scene with a stairway as depicted in Fig. 6(a). The rawrange image of the SR-3000 camera is shown in Fig. 6(b)and the NERI representation of the range data in Fig. 6(c).The NC algorithm partitions the NERI into 100 segments asshown in Fig. 6(d). Fig. 6(e) displays selected planarsegments. A token in blue indicates that the correspondingsegment belongs to a vertical plane and a token in greenmeans that the segment lies on a horizontal plane. Finally,the extracted planes are shown in Fig. 6(f). We can see thatthe majority of the planar surfaces are correctly extracted.We can also observe in Fig. 6(f) that region P (marked inred) is under-extracted because its adjacent regions (circledin yellow) are misclassified. As we can see from Fig. 6e thatthe pixels inside region A or B are classified as ones in thesame segment by the NC algorithm. However, either of Aand B contains data points on different planar surfaces thatare perpendicular one another in the 3D space. They aredetermined as non-planar segments due to the large PFEs. Itshould be noted that the misclassification will not have bigimpact in recognizing the stairway and guiding the robot.This is because there are enough number of treads andrisers indentified and the misclassification occurs at alocation far away from the robot. We can also see that thereare minor misclassifications at the right or left ends of someextracted planar segments. This suggest for future researcheffort that goes beyond the scope of this paper. Fig. 6grenders the segmentation result in a 3D point cloud wherethe unclassified points are represented in black.The 2nd experiment shows plane extraction of a hallwayscene. The result is depicted in Fig. 7. We can see that thefloor, door and the wall regions have been properlyextracted. Fig. 8 displays the result of our experiment in thelobby in the ETAS building at the University of Arkansas atLittle Rock. The result demonstrates a satisfactory plane

INTERNATIONAL JOURNAL OF INTELLIGENT CONTROL AND SYSTEMS13extraction of the proposed method.(a)(a)(b)(b)(c)(c)(d)(d)(e)(f)Fig. 7. Segmentation of a hallway scene: (a) Actual scene. (b) Rangeimage from SR-3000. (c) NERI of (b). (d) Initial clustering result of theNC. (e) Segmentation result after merging clusters. (g) Segmented datashown as a 3D point cloud.(e)(a)(f)(g)Fig. 6. Segmentation of the scene with a stairway scene: (a) Actualscene. (b) Raw range image. (c) NERI of (b). (d) Initial clustering resultof the NC. (e) Labeling of vertical and horizontal planar segments. (f)Segmentation result after merging the homogeneous segments in (e). (g)Segmented data shown as a 3D point cloud.(c)(b)(d)V. DISCUSSIONWe have seen in the previous section that some segments(mainly in the boundary regions) fail to qualify as planarones due to misclassification in the initial clustering phase.In this section, we put forward a recursive approach thatmay identify planar pixels from the non-planar segment andhence can extract a plane to its entirety.Consider Fig. 9(a) which is a magnified view of region Ain Fig. 6(f). Our objective is to extract the part of A thatbelongs to the adjacent vertical plane P (as shown in Fig.6(f)). To achieve this, we apply our proposed methodrecursively as follows:a) The NC algorithm is applied to A with N 2. Thisbreaks A into two sub-segments.(e)(f)Fig. 8 Segmentation results of a lobby scene: (a) Actual scene. (b) Rangeimage from SR-3000. (c) NERI of (b). (d) Initial clustering result of theNC. (e) Segmentation result after merging clusters. (f) Segmented datashown as a 3D point cloud.b) For each sub-segment, compute the PFE and normalof its LSP.c) A sub-segment is then merged with P or discardedbased on the criterion we set forth in Section IV.

14INTERNATIONAL JOURNAL OF INTELLIGENT CONTROL AND SYSTEMSd) If none of the sub-segments is merged with P, the NCis again applied to A with N N 1, i. e., repeat theprocess with N N 1.In this example, we are unable to make a merger with N 2.But with N 3, we obtain three sub-segments (C, D and E inFig. 9(a)). Through steps b and c, a larger segment (Fig.9(b)) is formed with C joining P (see Fig. 6(f)). From this,we can see that a finer segmentation can be achieved byfurther splitting the non-planar segments that are adjacentto the extracted plane segments.N-Cuts method fails, we will have to use the tri-band colorimage to represent an NERI and develop a new method tosegment the color NERI. We will carry out moreexperiments to test this idea in our future work.REFERENCES[1][2][3][4][5][6](a)(b)Fig. 9. Refinement of the segmentation result: (a) Enlarged view of amisclassified cluster. (b) Segmentation result after extracting planar regionfrom (a).The proposed plane segmentation method is currentlyimplemented in Matlab by using the Normalized Cutslibrary [21]. As a consequence, it is not real-time. Weexpect that a C/C implementation of the method willsignificantly reduce the runtime.VI. CONCLUSION AND FUTURE WORKWe have presented a method that may reliably extract thevertical and horizontal planes from a range image capturedby the SwissRanger SR-3000 camera. We use a split andmerge approach to achieve this. In the proposed method,surface normal information is used to convert the rangeimage into an NERI for range image enhancement. To dealwith noise-induced surface normal errors, we apply the NCalgorithm over the NERI to obtain homogenous segments.They are then merged to form larger segments (horizontaland vertical planes) based on the LSP fitting data statistics.Our method works efficiently without the need of a priorknowledge of the range image. We have also demonstratedthat under-extraction due to a misclassified non-planarsegment can be resolved by using the proposed method tosplit the segment and merge the resulting planarsub-segment(s) with the neighboring planar segment(s).We have validated the method’s efficacy by realexperiments in various indoor environments. Although wehave only described the segmentation of vertical andhorizontal planes, the proposed method indeed works forsegmentation of planes with arbitrary orientations.It is noted that we use a gray image for the NERI in orderto use the Normalized Cuts library. The mapping of atri-band image pixel to an NERI pixel is multiple-to-one. Iftwo non-parallel planes happen to have such orientationsthat their pixels have the same brightness in theirs NERIrepresentations, the distinctness of the planes in the NERIwill be small. This may potentially add difficulty to theN-Cuts method. Fortunately, in this case the intersection ofthe planes (a straight line segment) has a different normaldirection from both planes. This will likely help the N-Cutsmethod locate correct planar segments. In case that 9][20][21]N. Pezeshkian, et al., “Automatic payload deployment system,” inProc. SPIE 7692: Unmanned Systems Technology XII, 2010.Brian M. Yamauchi, “PackBot: a versatile platform for militaryrobotics,” in Proc. SPIE 5422, Unmanned Ground VehicleTechnology VI, 2004.P. Rudakevych, et al., “Integration of the Fido explosives detectoronto the PackBot EOD UGV,” in Proc. SPIE 6561, UnmannedSystems Technology IX, 2007.R. R. Murphy, “Human-Robot Interaction in Rescue Robotics,”IEEE Transactions on Systems, Man and Cybernetics-Part C:Applications and Reviews, vol. 34, pp. 138-153, 2004.A. I. Mourikis, et al., “Autonomous Stair Climbing for TrackedVehicles,” International Journal of Robotics Research, vol. 26, no.7, pp. 737-758, 2007.R. Unnikrishnan and M. Hebert, “Robust extraction of multiplestructures from non-uniformly sampled data,” in Proc. IEEE/RSJInternational Conference on Intelligent Robots and Systems, 2003,pp. 1322-1329.R. Triebel, W. Burgard and F. Dellaert, “Using hierarchical EM toextract planes from 3d range scans,” in Proc. IEEE InternationalConference on Robotics and Automation, 2005, pp. 4437-4442.V. Don and H. Maarten Uijt de, “Near real-time extraction of planarfeatures from 3d flash-ladar video frames,” in Proc. SPIE 6977,Optical Pattern Recognition XIX, 69770N, 2008.I. Stamos and P. E. Allen, “3-D model construction using range andimage data,” in Proc. IEEE International Conference on ComputerVision and Pattern Recognition, 2000, pp. 531-536.A. Bab-Hadiashar and N. Gheissari, “Range image segmentationusing surface selection criterion,” IEEE Transactions on ImageProcessing, vol. 15, no. 7, pp. 2006-2018, 2006.A. D. Sappa, “Automatic extraction of planar projections frompanoramic range images,” in Proc. International Symposium on 3DData Processing, Visualization and Transmission, 2004, pp.231-234.G. M. Hegde and C. Ye, “Extraction of planar features fromSwissRanger SR-3000 range images by a clustering method usingnormalized cuts,” in Proc. IEEE/RSJ International Conference onIntelligent Robots and Systems, 2009, pp. 4034-4039.T. Oggier, et al., “An all-solid-state optical range camera for 3Dreal-time imaging with sub-centimeter depth resolution,” in Proc.SPIE 5249, Optical Design and Engineering, 2003, pp. 534-545.T. Oggier, B. Büttgen and F. Lustenberger, “SwissRanger SR3000and first experiences based on miniaturized 3D-TOF Cameras,”Swiss Center for Electronics and Microtechnology TechnicalReport, 2005.C. Ye and J. Borenstein, “Characterization of a 2-D laser scanner formobile robot obstacle negotiation,” in Proc. IEEE InternationalConference on Robotics and Automation, 2002, pp. 2512-2518.S. A. Guomundsson, H. Aanaes and R. Larsen, “Environmentaleffects on measurement uncertainties of time-of-flight cameras,” inProc. International Symposium on Signals, Circuits and Systems,2007, pp. 1-4.K. Young Min, et al., “Design and calibration of a multi-view TOFsensor fusion system,” in Proc. IEEE Computer Society Conferenceon Computer Vision and Pattern Recognition Workshops, 2008, pp.1-7.G. M. Hegde and C.Ye, “Swissranger sr-3000 range imagesenhancement by a singular value decomposition filter,” in Proc.IEEE International Conference on Information and Automation,2008, pp. 1626-1631.S. Jianbo and J. Malik, “Normalized cuts and image segmentation,”IEEE Transactions on Pattern Analysis and Machine Intelligence,vol. 22, no. 8, pp. 888-905, 2000.K. Pulli, “Vision methods for an autonomous machine based onrange imaging,” Master’s Thesis, University of Oulu.http://www.cis.upenn.edu/ jshi/software/.

INTERNATIONAL JOURNAL OF INTELLIGENT CONTROL AND SYSTEMSCang Ye received the B. E. and M. E.degrees from the University of Scienceand Technology of China, Hefei, Anhui,in 1988 and 1991, respectively, and thePh.D. degree from the University of HongKong, Hong Kong in 1999.He was a Research Fellow with theSchool of Electrical and ElectronicEngineering, Nanyang TechnologicalUniversity, Singapore, fro

C. Ye is with the Department of Systems Engineering, University of Arkansas at Little Rock, Little Rock, AR 72204 USA (phone: 501-683-7284; fax: 501-569-8698; e-mail: cxye@ualr.edu). G. Hegde was with the Department of Systems Engineering, University of Arkansas at Little Rock, Little Rock, AR 72204 USA. He is now with