FITTING A PIECEWISE PLANAR FUNCTION TO A RANGE IMAGE

Modeling entire cities automatically is now conceivable, since modern range scanners capture geometry on an unprecedented scale. While the volume of data is overwhelming, urban scenes can be approximated well by parametric surfaces such as planes. A piecewise planar representation not only dramatically reduces the size of the data, but this high-level representation lends itself easily to graphics rendering, registration, and object recognition algorithms. In this survey, we formulate the task of extracting a piecewise planar representation from a large urban range image as a segmentation problem, and we present three approaches to solving the problem. Region growing proceeds by classifying points based on local surface approximation, then merging connected regions of points from the same class. The greedy merging process is fast because it explores only local similarity relations between points that are close together in the image grid, but it is susceptible to ambiguous classification near corners, boundaries, and depth discontinuities. The normalized cut algorithm widens the scope of information used to classify a point in relation to the rest of the image by constructing a complete graph with edge weights that reflect the similarity between points on a global scale. Such global information promises to deliver more meaningful segmentations, but the resulting optimization problem is too large for current numerical solvers. A more practical approach to incorporate global information into the segmentation process is the parametric fitting algorithm called the Hough transform. By accumulating votes for sets of parameter values generated by local surface approximation, the Hough transform chooses likely planar pieces based on the frequency with which they appear in an image. However, in the process of incorporating global information, the Hough transform ignores local connectivity, and thus it does not produce connected components. Region growing and the Hough transform both represent partial solutions to the planar segmentation problem on range images, but currently there is no available method that can produce connected components that are guaranteed to be planar.