HyperBF Networks for Real Object Recognition

1 Introduction

Shape-based visual recognition of 3D objects may be solved by first hypothesizing the viewpoint (e.g., using information on feature correspondences between the im­ age and a 3D model), then computing the appearance of the model of the object to be recognized from that view­ point and comparing it with the actual image ([6; 20; 9; 11; 21]). Most recognition schemes developed in com­ puter vision over the last few years employ 3D models of objects. Automatic learning of 3D models, however, is in itself a difficult problem that has not been much addressed in the past and which presents difficulties, es­ pecially for any theory that wants to account for human ability in visual recognition.

Recently, recognition schemes have been suggested that, relying on a set of 2D views of the object instead of a 3D model ([2; 5; 13]), offer a natural solution to the problem of model acquisition. In particular, Poggio and Edelman ([13]) have argued that for each object there exists a smooth function mapping any perspective view into a "standard" view of the object and that this mul­ tivariate function may be approximatevely synthesised from a small number of views of the object. Such a func­ tion would be object specific, with different functions corresponding to different 3D objects. Since synthesiz­ ing an approximation to a function from a small number of sparse data - the views - can be considered as learn­ ing an input-output mapping from a set of examples ([14; 15]), Poggio and Edelman used a scheme for the approxi­ mation of smooth functions which is equivalent to a class of multilayer networks called Regularization Networks and, in their more general form, HyperBasis functions. For each 3D object there exist a small network, which is "learned" directly from a small set of perspective views of the object. They demonstrated the successful perfor­ mance of such a scheme using computer simulated 3D wireframe objects similar to paperclips. Their experi­ ments assumed that the object had been isolated from the background and that features (such as the specific corners or angles between the segments) had been ex­ tracted and matched to the corresponding· features of the model views. Furthermore, their data were noise­ free and without any occlusions.

In this paper we extend their technique and experi­ ments to more realistic situations. Our ultimate goal is to implement a system for the recognition of human faces by applying the HyperBF technique to view vectors computed from the image by extracting features such as the position of the eyes and mouth and the color of the hairs.

Real 3D objects introduces several difficulties, namely the presence of noise in the feature data, the ignorance of the correspondence between the features of different views of the same object and finally the necessity to use incomplete feature vectors (due to the presence of occlu­ sions and/or to the inability to recover correctly some of the objects features). It seems reasonable to limit, at least in a first step, all of these difficulties to the recog­ nition ph-ase: the learning phase is supervised and uses "good" example views, where the problem of correspon­ dence has been removed and the noise reduced.

The main result of the paper is that the Hyperbf technique, suitably modified, can deal successfully with the problems of noise, occlusions and missing. correspon­ dences, at least for the simple 3D objects we consider here. One of the q1ost useful and interesting of our ex­ tensions of the techique is the use of negative examples in the training, that is in the model acquisition, phase.

The plan of the paper is as follows. The first section gives a brief review of the simple RBF technique. We then describe the experiments and compare the ·perfor­ mance of different version of the algorithm (including performance of a standard Nearest Neighbor classifier). The more general HyperBF network is then introduced and characterized in terms of experimental performance.

2 Radial Basis Functions

Radial Basis Functions can be regarded as a special case of Regularization Networks introduced in [14] as a gen­ eral approximation techniqu~ that. can be used in prob­ lems of learning from examples.

A scalar function can be approximated, given its value on a sparse set of points {z,}, by an expansion in radial functions:

where II · II represents the usual Euclidean norm. The computation of the coefficients co rests on the invertibil­ ity of matrix H,; = h(ll Zi- z; II) which has been proved (see Micchelli [12]) for functions such as:

It is possible to use fewer radial functions than ex­ amples, i.e. data points. The resulting overconstrained system can, be solved in a least square way under the conditions of Michelli's theorem and proves to be useful when many examples are available.

Poggio and Girosi ([14; 15]) have shown that the RBF technique is a special case of the regularization ap­ proach to the approximation of multivariate functions. In the regularization approach one seeks the approximat­ ing function which is closest to the data and smoothest, according to an appropriate criterion. The RBF tech­ nique described above, which is the simplest version of the HyperBF scheme described later, was used in the experiments described in the next section.

3 Experimental setup

The objects used in the experiments were five paper clips, randomly generated of the same length, rendered through ray-tracing techniques (see Fig. 1). The small number of objects used must be taken into account when the experimental results are considered. The small dif­ ference in performance among the different techniques is expected to increase if the number of objects to be classified increases. The clip was first isolated from the background ([1]) and the resulting binary image was skeletonized ([18]), giving essentially a line drawing. A polygonal approximation routine identified line segments which were then used to reconstruct the clip using an A* search ([1]). The same algorithms were applied to a real clip (images were taken with a CCD camera) and proven to perform equally well. The reconstructed clips were used to simulate different degrees of occlusions by as­ signing to each clip a finite radius (the bigger the radius the higher the occlusion percentage).

For each clip a set of 80 views were available among which the learning and testing sets could be chosen. The attitude was restricted to one octant of the view­ ing sphere. Each clip, having six vertices, was described as a vector of twelve coordinates, representing the po­ sition on the image plane of the vertices (expressed in the barycentric coordinate system identified by the ver­ tices to remove translational dependency). The use of the (z, y) coordinates of the vertices on the image plane is one of the many possible choices of features. For in­ stance, the angles between the clip segments could have been used ([13]). Broadly speaking, every feature that can be cast into numerical form and that maps smoothly into the output of the network, may be used in the recog­ nition process.

4 Experiments

The purpose of the experiments was to test the recogni­ tion performance of several strategies. For each rendered clip, from a set of 80 views, a learning set of given car­ dinality and a testing set of fixed cardinality (10 views) were extracted. The problem of feature correspondence was constrained by the nature of the objects. The clips could be present in the learning set in one of the two natural orientation (the reconstruction algorithm did not fix this ambiguity). In the recognition phase each clip was used in the two ways attempting recognition and choosing the best result. The order of the vertices was assumed to be correct but for this ordering ambiguity. The output representation used for recognition was the characteristic function of the clips:

where P(Cs) represents the space spanned by the per­ spective projections of the i-th clip. The synthesis of the characteristic function from the learning set is realised by what will be referred to as RBF module. The response of a module to an input vector (a clip to be classified) is the value of the RBF expansion at the given point, clipped to the interval [0,1]. The clip is then assigned to the module with the highest response.

Several groups of experiments have been performed:

• using only positive examples and complete vertex information;
• using only positive examples and occluded clips;
• using positive and negative examples with complete vertex information.

Positive examples are views of the correct clip and negative examples are views of other clips (therefore in­ correct clips for the module under training).

In the first group of experiments the number of cen­ ters in the RBF expansions matched that of the available positive examples for the given clip. The performance reflects how well the RBF scheme works with noise in the feature vector and in the specific task. As we men­ tioned before, real 3D objects exhibit occlusions (topo­ logical absence of features), unrecovered features ( defec­ tive feature extraction) and correspondence problems. The first two characteristics require the use of incom­ plete feature vectors. In the "vanilla" version of RBF described in section 2, the radial basis functions must be completely specified with their parameters before train­ ing. For Gaussian radial basis functions, the value for u must be chosen. Let {is}I be the learning set. To each example is a nearest neighbor can be associated, i.e. an example :i!; f i 1 such that

Since the theory ([14]) allows only for a global value of u (and not for a different one for each unit), the average nearest neighbor distance was used:

with n the number of examples in the learning set. If the learning set spans uniformly the space where the function is defined, no problems arise. If this is not the case over/under generalisation may be expected in this simple scheme.

During the classification task, incomplete feature vec­ tors may be presented to the RBF module. Two strate­ gies were investigated. The first one is probably the simplest: all possible combination of the available data are tested. Its major drawback is that the number of such combinations grows quite rapidly with the number of the available features. The second strategy is directly related to the idea of characteriltic view· of a three di­ mensional object (see [7]). It can be shown that the space of the possible perspective views of a three dimen­ sional object can be partitioned into subspaces with the following properties:

• all the views in a single subspace are topologically equivalent (their projected edge-structure exhibit a junction line identity);
• every view in a single subspace can be transformed into another view of the same subspace with a linear transformation (in homogeneous coordinates).

An equivalence relation can then be defined and the quotient space considered. The elements of the quotient space are called characteri1tic view1. The topological equivalence of the views in the same subspace implies that each view has the same number of features (such as vertices and faces), the reverse being not necessarily true. It is then natural to assign an RBF module to each characteristic view.

Let us focus on Gaussian RBFs. H a sufficiently dense learning set is available, the value returned by the RBF approximation quickly decays with the distance from the learning set. It is reasonable to consider the examples in the learning set as wire frame objects, so that there are no occlusions (somewhat like CAD models). We can then estimate the value of u on this virtual set. The learning set can be subdivided into subsets whose mem­ bers share the same number of visible (real) features. Of course, an equal number offeatures is necessary but not sufficient to share the same characteristic view. The di­ agram of Fig. 2 shows a possible scenario and how it can be mapped into different RBF modules, one for each dimensionality (instead of one for each characteristic view) of the learning examples.

The use of a reduced dimensionality implies the use of a modified CT. As CT is directly related to a distance, the following transformation rule was adopted:

where CTJ is the value at dimensionality j. Whenever a feature vector with a dimensionality that does not match any of the available examples is presented to the recog­ nition module, the first strategy can be employed. We must, however, solve the problem of how to compute the distance between points for which some coordinates may not be available. Let us define the metric in the following way:

where M is a symmetric, positive definite matrix in M,.x,. called the metric matriz. H the standard eu­ clidean metric is used and the learning set is complete the following metric can be used ([10]):

where 6ii is the Kronecker symbol, Ui = 1 if the i­ th coordinate is available in the point to be classified and Ui = 0 otherwise. A more useful metric can also be defined ([10]) whose diagonal elements take into ac­ count the number of missing coordinates. If we choose to preserve the trace of the (diagonal) metric matrix M E M,.x,., Tr(M) = n, the elements of the metric matrix are given by:

This corresponds to working in a reduced dimensional­ ity RBF module with an effective CT chosen according to the equation 7. The resulting mixed strategy proved to be quite effective, especially with high occlusions per­ centages. The use of multiple RBF modules with the mixed strategy and a weighted metric provides uniform results, so that the answer of the different modules can be compared to determine the best answer.

To gauge the performance of the RBF scheme, a Near­ est Neighbor classification scheme was used on the same data sets. Several additional experiments not reported here have also been performed ([3]).

For each experiment two quantities are shown in the figures:

MIN /MAX: the minimum error made by the module on a wrong clip divided by the maximum error on a right clip. When MIN/MAX > 1 the module can avoid false alarm through the introduction of a threshold (see [4]). The average MIN/MAX value over the different modules is reported in the graphs.

RECOGNITION: is computed assigning each clip to the module with the smallest error, ignoring any information from MIN /MAX.

5 Performance analysis

The comparison of "vanilla" RBF and Nearest Neighbor classification seems to favor the latter (see Fig. 3). This can be explained by some recent theoretical results. It can be shown ([2], see also [4]) that under ortographic projections, the view of a given object as defined earlier, spans a 6-dimensional subspace. H the viewer is at a reasonable distance from the object there is only a neg­ ligeable difference between perspective and ortographic projection. This imply that the views of each clip almost certainly span non-intersecting 6-manifolds, embedded in the R 12 representation space. In these experiments, the standard euclidean metrics was used. The use of Gaussians effectively corresponds to setting a volume "around" the 6-manifold. This volume is bigger when the number of examples is smaller (larger inter samples distances) and this can explain the inferior performance of the RBF recognition scheme, which is overgeneraliz­ ing. The average MIN /MAX error is better for RBF even if the worst case (worst MIN /MAX figure of the recognition modules) is usually slightly better for NN.

It is interesting to compare the performance of ex­ haustive matching and multiple modules matching ([3]). Whereas at low occlusion percentages the performance of the two strategies is very similar, the multiple modules approach performs definitely better with a large number of occlusions. The use of a weighted metric increases all the performance measures for both strategies. This improvement is due to the fact that when some features are missing we require a progressively closer match for those we have: this allows the reduction of false alarms and of overgeneralization.

Another possible output representation, which we did not use because it can be proved to yield an inferior per­ formance in this case ([3]), is that of a prototype view ([13]): every view of a given clip is mapped into a par­ ticular view of that clip, called its prototype view (this mapping is realized through a vector valued function). The clip is then assigned to the module exhibiting the smallest distance from the output of the RBF expansion to its prototype view.

The differences in performance using only positive ex­ amples, positive examples with information from neg&­ tive examples (RBF centers only on positive examples) and positive and negative examples (centers on both pos­ itive and negative examples) have been tested using r&­ dial Gaussian functions (see Fig. 4). Due to the decay­ to-zero of Gaussians negative examples are effective for the vanilla RBF scheme only when the number of exam­ ples is small.

-·-~----4-----+ -

6 Hyper Basis Functions technique

The "vanilla" RBF technique provides a basis for com­ parison with the extensions of the Regularization net­ work technique described by T. Poggio and F. Girosi in [14]. From a more general formulation of the variational problem of regularization they derive the following ap­ proximation scheme, instead of equation (1):

where the parameters t.,., that we call "centers," and the coefficients c.,. are unknown, and are in general much fewer than the data points (n ~ N). The term p(x) is a polynomial that often can be neglected, though it usually consists of the constant and linear terms. The norm is a weighted norm

where W is an unknown square matrix and the super­ script T indicates the transpose. In the simple case of diagonal W the diagonal elements w, assign a specific weight to each input coordinate, determining in fact the units of measure and the importance of each feature. In this formulation the learning stage is used to esti­ mate not only the coefficients of the RBF expansion, but also the metric (problem dipendent dimensionality reduction) and the position of the centers (optimal ex­ amples selection).

This more general optimization problem cannot be solved through matrix inversion and methods like gra­ dient descent ([17]) or random minimization techniques ([8; 19]) must be used (as the possibility of getting trapped in poor local minima is significant we opted for the latter approach) .

The possibility of moving the expansion centers, ini­ tially located on some of the learning examples, is useful in the presence of noise in the available data and for improving the repre1entativity of the center. The ad­ justable metric is even more important, since it allows to set a more specific dissimilarity measure between new views and centers than euclidean metric.

One of the most interesting results is that in the task of object recognition, and if an approach similar to ours is used, an adjustable metric requires necessarily nega­ tive examples. The argument, substantiated by experi­ ments, rests on the trivial observation that if only posi­ tive examples were used, it would be possible to obtain an optimal (in terms of quadratic error on the examples) approximation to the characteristic function of an object by mapping every possible input view to the value 1, that is by choosing W = 0. This is obviously a poor choice for the task of object discrimination. The use of negative examples is therefore essential. The added complexity is small since the computational complexity of the RBF

expansion depends linearly on the number of examples (for a fixed number of centers). This means that if mini­ mization techniques such as gradient descent or random minimization are used, the increase in the computation time is expected to be linear. In the case of object recog­ nition, negative examples allow to remedy in an elegant way what is the main problem in most learning tasks: the need of a large number of examples. Use of a large number of positive examples would make the whole ap­ proach of this paper quite moot: each object would be represented essentially as a look-up table of very many of its views with all the corresponding complexity of stor­ age and acquisition. Our proposal, supported by our ex­ periments, is, instead, to use a small number of positive views and a large number of negative examples, which are easily available if the data basis includes many ob­ jects.

The plots of Fig. 5 gives some information on how the generalization proceeds with the number of positive and negative examples available as well as a comparison with the nearest neighbor results on the same data sets. RBF(N) refers to a one center HyperBF expansion with movable coefficient, center and diagonal metric (N is the number of positive examples).

The experimental results allow us to rank the differ­ ent RBF approaches together with the Nearest Neighbor classification scheme providing a useful gauge. The RBF approaches can be sorted, by increasing performance, in the following way:

1. "vanilla" RBF: use of only positive examples with as many centers as available examples
2. RBF with negative examples: only the positive ex­ amples are used as centers but the information from the negative examples is used
3. Nearest Neighbor: the performance is nearly equal to that of RBF with negative examples
4. HyperBF with diagonal metric (negative informa­ tion must be used)
5. HyperBF with complete metric: again negative in­ formation must be used.

7 Conclusions

We have applied recently proposed networks for learning from examples (the vanilla RBF version as well as the more powerful HyperBF scheme) to the problem of 3D object recognition. Experimental results on recognition rate have been obtained for wire frame objects (paper clips represented as polylines, hence with no occlusions) and for more realistic objects (paper clips represented as a set of cilinders of varying radii, hence exhibiting different percentages of occlusions). We have extended the RBF technique in order to cope with the problem of feature occlusion through the introduction of a modified euclidean metric. A characteristic view representation has been compared to an exhaustive search for the best match in the case of self-occluded clips. Especially inter­ esting is the use of negative examples which yield some improvement in the vanilla RBF approach and are crit­ ically important for the more general HyperBF scheme, while reducing considerably the complexity of the tech­ nique in terms of representation and model acquisition. The HyperBF generalization of the basic technique, with the introduction of movable expansion centers and the synthesis of a task dependent metric, proved to be suc­ cessful in obtaining a compact representation of the ob­ jects that appears to work well in the - admittedly still very limited - recognition tasks described here.