The ability to automatically acquire geometric models from example objects is useful in a growing number of application areas. In the field of computer graphics, the need for improvements in realism requires more complex models, but manual model construction is time-consuming and difficult. In industrial settings it is useful to capture the geometry of existing parts either for the purpose of inspection or to enable exact replicas to be manufactured automatically. For reasons which will be clarified shortly, current techniques are generally limited to constructing models of single rigid objects. In this paper we suggest how these algorithms might be augmented to allow the automatic construction of articulated objects, increasing the scope of this technology. For clarity we define articulated objects as those objects consisting of a number of rigid parts that are connected by non-rigid joints [ 1 ].
The established approach for automatic model construction begins by taking surface measurements from a number of viewpoints so that all of the object's surface is captured. Typically, this will be done with a range finder such as a laser striper or stereo vision system. Either of two different approaches can then be taken. In the first approach surface primitives are fitted to the raw data in each of the views of the object, and then the different views are registered by aligning similar primitives [ 2 ]. The second approach registers the raw data initially using local surface shape, see for example [ 3 , 4 ], and then surface primitives are fitted directly to the registered surface data [ 5 ]. The second approach is favoured because it makes maximum use of the raw data when surface fitting and avoids the problem of having to piece together possibly fragmented surface patches from different viewpoints that are not perfectly aligned.
Whichever approach is taken, the registration process assumes that the shape of the object does not change as the surface data is acquired. If, however, we wish to automatically capture the geometry and kinematics of an articulated object, then the object's shape must change from example to example. This means that current registration algorithms cannot be used directly. Rather than developing new registration algorithms we propose here that the raw measurement data is segmented into rigid subsets each corresponding to a rigid subcomponent of the object. This will enable models of each subcomponent to be constructed independently using existing technology and a final, articulated model to be formed by assembling each of the subcomponents.
The algorithm we have developed processes a pair of range images at a time and segments each of them into N sub-images, where N is the number of independently moving, rigid subcomponents which are present in the data. This processing is carried out in two distinct stages. In the first stage, the rigid transformation that aligns most of the data in the first image with corresponding data in the second is estimated. This is done by segmenting the range data into surface patches and then finding consistent transformations that align patches in the first image with potential correspondents in the second. In the second stage, the movement of each surface patch between the two images is compared to the estimated transformation and removed from the scene if it is in agreement. These two stages are then iterated until no surface data remains and the required segmentation is obtained.
We have already published a rigid part segmentation algorithm which utilises point-to-point as opposed to surface patch-to-surface patch correspondences between two range images [ 6 , 7 ]. In this approach the transformation that aligns object subcomponents are estimated by aligning rigid coordinate frames defined at corresponding surface points. This approach is, however, limited to non-developable surfaces on which an invariant, rigid coordinate frame can be uniquely defined. This limitation has motivated the development of the surface patch based algorithm presented here but it is our intention to eventually combine the two approaches to produce a general purpose, rigid subcomponent segmentation algorithm.
In the next section a detailed description of our rigid part segmentation algorithm is presented. This is followed by a demonstration of the algorithm applied to some real range image data. Finally we summarise the contribution made by this work and briefly discuss the aims of ongoing and future work.
Anthony Ashbrook