NASA NTRS1993
The problem of recognizing and positioning of objects in three-dimensional space is important for robotics and navigation applications. In recent years, digital range data, also referred to as range images or depth maps, have been available for the analysis of three-dimensional objects owing to the development of several active range finding techniques. The distinct advantage of range images is the explicitness of the surface information available. Many industrial and navigational robotics tasks will be more easily accomplished if such explicit information can be efficiently interpreted. In this research, a new technique based on analytic geometry for the recognition and description of three-dimensional quadric surfaces from range images is presented. Beginning with the explicit representation of quadrics, a set of ten coefficients are determined for various three-dimensional surfaces. For each quadric surface, a unique set of two-dimensional curves which serve as a feature set is obtained from the various angles at which the object is intersected with a plane. Based on a discriminant method, each of the curves is classified as a parabola, circle, ellipse, hyperbola, or a line. Each quadric surface is shown to be uniquely characterized by a set of these two-dimensional curves, thus allowing discrimination from the others. Before the recognition process can be implemented, the range data have to undergo a set of pre-processing operations, thereby making it more presentable to classification algorithms. One such pre-processing step is to study the effect of median filtering on raw range images. Utilizing a variety of surface curvature techniques, reliable sets of image data that approximate the shape of a quadric surface are determined. Since the initial orientation of the surfaces is unknown, a new technique is developed wherein all the rotation parameters are determined and subsequently eliminated. This approach enables us to position the quadric surfaces in a desired coordinate system. Experiments were conducted on raw range images of spheres, cylinders, and cones. Experiments were also performed on simulated data for surfaces such as hyperboloids of one and two sheets, elliptical and hyperbolic paraboloids, elliptical and hyperbolic cylinders, ellipsoids and the quadric cones. Both the real and simulated data yielded excellent results. Our approach is found to be more accurate and computationally inexpensive as compared to traditional approaches, such as the three-dimensional discriminant approach which involves evaluation of the rank of a matrix. Finally, we have proposed one other new approach, which involves the formulation of a mapping between the explicit and implicit forms of representing quadric surfaces. This approach, when fully realized, will yield a three-dimensional discriminant, which will recognize quadric surfaces based upon their component surfaces patches. This approach is faster than prior approaches and at the same time is invariant to pose and orientation of the surfaces in three-dimensional space.