Range data segmentation of a 3D imaging sensor with applications to mobile robot navigation

The primary goal of this research is to develop range data segmentation method for a new class of 3D imaging sensors---Flash LADARs. The imaging sensors are compact in size and provide dense range data at high frame rates which makes them suitable for autonomous navigation of small mobile robots. However, they have relatively large measurement errors in range data. This issue has hindered their applications to mobile robots.;Most of the existing methods for segmenting range data are based on local features such as surface normals that are too sensitive to the noise of the range data. Therefore they are insufficient for processing the data of a Flash LADAR. To overcome this deficiency, we propose to develop a segmentation method that utilizes both the global spatial information and local features of range data. The use of the global information makes the segmentation process less susceptible to the range-noise induced inconsistencies in local features and hence produces a better segmentation result. The segmentation method is based on the normalized cuts technique that partitions a graph consisting of nodes and edges.;In the proposed method, the nodes of the graph are the homogenous regions known as super pixels obtained from the range data by a clustering method and the edge weight between each pair of node is computed based on their similarity. To this end we develop a novel similarity function that embodies the global and local information of the nodes to compute the edge weight. The edge weights, representing the similarities of two nodes, are used to determine how to partition the graph. We then develop a new method that recursively partitions the graph into two sub-graphs until an exit condition is met. The combination of the similarity measure and the recursive graph partitioning method produces reliable segmentation of the range data. The findings of this research can be used in various robotic applications such as navigating mobile robots, symbolic map building and range data understanding.