W2A-036 Object recognition-0.txt
Chapter 9 3-D Object Recognition. Kenneth M. Dawson.

"There are not facts, only interpretations." Friedrich Neitzsche

Object recognition is the process of identifying material things by associating what is sensed with what is known. A wide diversity of approaches have been taken to object recognition; however, "there is no existing system that comes close to solving the general object recognition problem"[11]."
This chapter presents a new method of addressing the problem of three-dimensional object recognition of rigid objects on the basis of comparisons between viewed three-dimensional models (i.e. which are extracted from imaged data at runtime) and known object models (which are generated using Computer Aided Design data) 1
. It addresses the problem in terms of sub-problems (i.e. the determination of orientation and the determination of position), as Ikeuchi does in [10], and provides a framework for comparing the object models using several different secondary representations of the models (which may be regarded, in the complex of the framework described, as forms of complex scalar transform descriptors).
This technique overcomes the dependency of comparing models on the basis of primitive components (such as individual edges, vertices or surfaces), and provides a measure for evaluating the reliability of any determined match on the basis of a comparison of complete views of the models. The approach has been tested with theoretical models and models extracted from range data and is shown to work well as long as the models extracted are reasonably accurate.

The model comparisons are performed indirectly using several different secondary representations which are derived from the models. Hence, as models are matched implicitly, rather than explicitly (using model components), the method developed herein has been dubbed 'implicit model matching'."

When considering any object recognition strategy, it is necessary to address eight main issues: 1. The domain of objects to be recognised. 2. The allowed complexity of the scenes. 3. The representations to be used for both the viewed, and the known objects. 4 The method(s) of obtaining the known object representations. 5 The method(s) of obtaining the viewed object representations. 6 The model invocation strategy (i.e. which known objects to consider for matching). 7 The model matching strategy. 8 The method of hypothesis verification. Each of these issues is considered in turn in the sections which follow.

9.1 Object Domain and Scene Complexity.

The problem being addressed is that of the automatic recognition of three-dimensional non-articulate rigid objects. In this context, the problem is equated to the matching of a view of a solitary 3-D object model (the viewed model) with known object models in order to recognise the view of the observed object model. Recognition is taken to imply determination of the position and orientation of a known object model which best matchs the viewed model (along with an associated a measure of its reliability).

9.2 Methods or representing and obtaining object models.

The issue of representation has already been addressed in chapter 8, but a brief summary is order. There are two distinct classes of object representation used: 1. The first class of representation details 3-D objects so that they may be symbolically manipulated and considered from any viewpoint. The representation used here is a simple planar-surface based model similar to that of Roberts[13]. However, it should be noted that the recognition strategy employed is independent of the type of representation used to detail the objects. 2. The second class of representation is derived from the first and, hence, the various different representations used from this class may be regarded as secondary representations of the detailed object models. They may also be regarded as complex scalar transform descriptors, as each representation is composed of a fixed-size array of scalars. These representations depend only on certain object parameters (e.g. orientation) and are used to guide the recognition system efficiently through the potentially exhaustive search for the correct position and orientation of the correct model.

The four secondary representations which are used include: 1 Extended Gaussian Images. 2 Directional Histograms. 3 Needle Diagrams. 4 Depth Maps.

Detailed known object models are specified using a CAD specification technique and detailed viewed models are derived from range images. Both of these methods (and all of the representations) are described in the previous chapter.

9.3 Model invocation.

Model invocation is the selection of known models with which to attempt matching. However, with the approach presented in this chapter, matching is performed between views of object models. Hence, rather than just invoke object models, it is necessary to invoke approximate views of models. This inherently addresses model invocation (in the strict sense of the term); if no view of a particular model is invoked, then the model itself is not invoked.

Model view invocation is performed by determining the possible orientations from which each known model could be viewed in order to result in a view similar the viewed model. The focal axis of the camera with respect to the known model's frame of reference is first determined, and subsequently possible values for the roll of the camera with respect to its own frame of reference (i.e. around the focal axis) are calculated; see figure 9.1.
>
It was noted above that the task of model invocation is to determine orientations from which each known model could be viewed, so that the resultant view might be similar to that of the viewed model. This is an important point, as it is indicative of the fact that, rather than compute transformations which theoretically map known models to the same 3-D space as the viewed model, the task of model invocation and model matching in this method is to determine potential orientations from which to view the known models, with respect to the individual known models frames of reference (much as Goad does in [8]).

The viewed model should have a camera model of some sort associated with it (i.e. that which which represents the original viewing device). The camera model used with known models is similar, in that it uses the same internal parameters, although it is defined with respect to a different coordinate frame (i.e. that of the known object model).

9.3.1 Determining potential orientations of the focal axis.

In order to determine potential orientations of the camera with respect to a known model's frame of reference, a sample of all possible orientations is used. This sampling of orientation space is defined by the tesselations of a Gaussian sphere.

Using each of the directions associated with the sphere tesselations as possible orientations of the camera focal axis, directional histograms of the tilts visable from the known model are determined. These directional histograms are compared with a directional histogram of tilt determined from the viewed model, resulting in a degree-of-fit for each possible orientation. A degree-of-fit is calculated using normalised cross correlation for each invocation and gives a measure of likelihood that the model is at an orientation within the range defined by the relevant sphere tessalation is that which must be recognised. The orientations which possibly correspond to a match are defined by those tessalations of the sphere which exhibit local maximum values for the degree-of-fit of tilt (as they change slowly from tessalation to tessalation) and the likelihood is defined by the degree-of-fit.

An example of the comparison of tilts from each possible orientation is shown in Figure 9.2. The known model is considered from all possible viewpoints as defined by each tesselation of sphere, and each tesselation of the sphere is shown encoding the degree-of-fit determined through the comparison of tilt histograms.

9.3.2 Determining possible values of roll.

Having determined potential orientations for the camera focal axis, potential values for roll, around that focal axis, must be calculated. This is accomplished by comparing (using normalised cross correlation) the directional histogram of roll defined by the viewed model with that derived from the known model in an arbitrary roll, as viewed using the previously determined focal axis. The comparison is performed at all possible values of roll (of the theoretical model), simply rotating the roll histogram of the theoretical model in order to define each possible roll. Smoothing of the histograms before comparison again provides a smoothly changing degree-of-fit, and once again the local maxima define the potential matches. An example of the comparison of roll histograms is given in Figure 9.3.

The result of this operation is the determination of viewing orientation frames of reference, defined with respect to known models frames of reference, which may provide views of those known models which are similar to the viewed model.

9.4 Model matching strategy.

Model invocation, in this method, supplies potential orientation frames of reference for known models. These, however, are only approximations as the orientation space is quite coarsely sampled. One task of model matching is, then, to fine tune these orientation frames and to determine the position of the viewing camera relative to the known model.

Model matching consists of a number of steps, during which the orientation frames will either be accepted (and their updated versions passed to the model verification stage) or rejected. These steps are: 1 Determination of approximate object position. 2 Fine tuning of object orientation. 3 Fine tuning of viewed object position. 4 Fine tuning of object depth. 5 Fine tuning of viewed object position to sub-pixel accuracy. Each of these steps is discussed in turn.

9.4.1 Determining approximate object position.

In order to allow the position of the object to be fine tuned (and in order to allow the object to be viewed during tuning operations in general), the position of the camera with respect to the known model must be estimated. To do this, the position of the viewed model with respect to its viewing camera is used (refer to figure 9.4). The imaged centroid of the viewed model and an approximate measure of the distance of the viewed model from the viewing camera are both very easily computed. The position of the camera which views the known model is then approximated by placing the camera in a position relative to the known model's 3-D centroid, such that the centroid is at the correct approximate distance from the camera (as determined from the viewed model), and is imaged by the camera in the same position as the viewed model's imaged centroid.

9.4.2 Fine tuning object orientation.

Fine tuning object orientation is performed in a similar way to the approximate determination of object roll. Pitch, yaw and roll histograms derived from the theoretical model are compared to those derived from the viewed model. The differences between them indicate the amount by which the orientation may best be fine tuned (e.g. see figure 9.5) This is done within a limited range of angles (the range being defined by the sampling of the sphere which was used for sampling orientation space during the model invocation stage), and at reasonably high angular resolutions (i.e. 1/4), in order to ensure accurate tuning.

Additionally it should be pointed out that the individual fine tuning operations affect not only the current directional histogram (e.g. roll), but also, in a small way the other directional histograms (e.g. pitch, yaw). Hence the fine tuning is performed by calculating a specific directional histogram, tuning the relevant component of orientation, and then moving on to the next directional histogram. This is done until the amount of tuning for all components of orientation falls below the required accuracy, or until the total tuning on any of the orientations exceeds the range allowed (in which case the invoked model view is rejected).

9.4.2 Fine tuning viewed object position.

Fine tuning of the viewed object position may be formally defined as tuning of the relative position of the viewing camera with respect to the known models reference frame, by translation in the plane which is orthogonal to the focal axis of the camera (i.e. in the directions parallel to the image plane).
