Basic 3D Scanner Software

The basis of the scan matching algorithms and the reliable robot control are algorithms for reducing points, line detection, surface extraction and object segmentation. Next we give a brief description of these algorithms. Details can be found in [16].

The scanner emits the laser beams spherically from one center, such that the data points close to the source are more dense. The first step is to reduce the data. Therefore, data points located close together are joined into one point. The number of these so-called reduced points is one order of magnitude smaller than the original one.

Second, a simple length comparison is used as a line detection algorithm. Given that the counterclockwise ordered data of the laser range finder (points $a_0, a_1, \ldots, a_n$) are located on a line, the algorithm has to check for $a_{j+1}$ if $\Vert a_i, a_{j+1} \Vert / \sum^j_{t=i}\Vert a_t,a_{t+1} \Vert < \epsilon(j)$ in order to determine if $a_{j+1}$ is on line with $a_j$. (Figure 2, left)

The third step is surface detection. Scanning a plane surface, line detection returns a sequence of lines in successive scanned 2D planes approximating the shape of surfaces. Thus a plain surface consists of a set of lines. Surfaces are detected by merging similar oriented and nearby lines. (Figure 2, middle)

The fourth and final step computes occupied space. For this purpose, conglomerations of surfaces and polygons are merged sequentially into objects. Two steps are necessary to find bounding boxes around objects. First a bounding box is placed around each large surface. In the second step objects close to each other are merged together, e.g., one should merge objects closer than the size of the robot, since the robot cannot pass between such objects (Figure 2, right). These bounding boxes are used for avoiding obstacles.

Data reduction, line, surface and object detection are real-time capable and run in parallel to the 3D scanning process.

Figure 2: Left: Line detection in every scan slice. Middle: Surface segmentation. Right: Bounding boxes of objects superimposing the surfaces