An efficient implementation of decomposable parameter spaces

A methodology called the CIPS (cooperative independent parameter spaces) approach for reconstructing parametrized regular surfaces from range data is presented. The parametrizations are decomposed into subsets of parameters. The conjunction of the individual parameter detections in these subsets produces the full parametrization for a surface. The detections are accomplished using a multiwindow parameter estimation technique, multiresolution k-tree parameter space searching and voting, and a conflict resolution process that eliminates invalid parameter hypotheses and insures a single unique parametrization for each surface region. The overall decomposition of parameter detection spaces can be organized into a serial, parallel, or hybrid architecture without problems of parameter crosstalk between spaces. Many of the major shortcomings of the Hough transform and other parameter space voting approaches are directly addressed by these methods. An implementation that detects spheres and cylinders in real, low-resolution range images is presented, and it is shown to be fast and accurate.