Instace-Based AMN Classification for Improved Object Recognition in 2D and 3D Laser Range Data

1 Introduction

In this paper, we consider the problem of identifying objects in 2D and 3D range measurements. We believe that the segmentation of these data into known object classes can be useful in many different areas, such as map registration, robot localization, object manipulation, or human-robot interaction. For example, a robot that is able to classify the 3D data acquired by a range sensor has a better capability of finding corresponding data points in different measurements. In this way, the scan registration can be carried out more reliably. Other application areas, in which object recognition is important, include seek-and-rescue tasks such as the one aimed by the RoboCup rescue initiative.

What makes the object detection especially hard is the fact that it involves both, the segmentation and the classification of the segments. To simultaneously solve this segmentation and classification problem, recently collective classification approaches have become a popular approach. They are based on the assumption that in many real-world domains spatial neighbors in the data tend to have the same labels. For example, Anguelov et al. [2005] formulate the problem of segmenting 3D range data into known classes as a supervised learning task and apply collective classification to solve the task. They use a technique called associative Markov networks (AMNs), which combines the concept of relational learning with collective classification.

So far, AMNs have been used only based on the log-linear model, which means that there is only a linear relationship between the extracted features and the weight parameters learned by the algorithm. This results in classification algorithms that learn hyper-planes in the feature space to separate the object classes. However, in many real-world applications the assumption of the linear separability of the features is often not justified. One way to overcome this problemmay be to extend the log-linear model, but this is still subject to ongoing research. In this paper, we propose a different approach. By combining the ideas of instance-based classification with the AMN approach, we obtain a classifier that is more robust against the error introduced by the linear-separability assumption. We present a way to compute new feature vectors from a given set of standard features, i.e., we transform the original features, and show that these features are better suited for classification using the AMN approach.

This paper is organized as follows. The next section gives an overview of the work that has been presented so far in this area. Then we summarize the concepts of collective classification using associative Markov networks and describe shortly how learning and inference is done in AMNs. Then, a detailed description of our approach is presented. Finally, we present the results of experiments, which illustrate that our method provides better classifications than previous approaches.

2 RelatedWork

The problem of recognizing objects from 3D range data has been studied intensively in the past. Most of the approaches can be distinguished according to the features used. One popular approach are spin images [Johnson, 1997; de Alarc´on et al., 2002; Frome et al., 2004], which are rotationally and translationally invariant local descriptors. Spin images are also used as features in the work presented here. Other types of 3D features include local tensors [Mian et al., 2004], shape maps [Wu et al., 2004], and multi-scale features [Li and Guskov, 2005]. Osada et al. [2001] proposed a 3D object recognition technique based on shape distributions. Whereas this approach requires a complete view of the objects, our method can deal with partially seen objects. Additionally, Huber et al. [2004] present an approach for parts-based object recognition. This method provides a better classification because nearby parts that are easier to identify than others help to guide the classification. A similar idea of detecting object components has been presented by Ruiz-Correa et al. [2003], who introduced symbolic surface signatures. Another approach to object recognition proposed by Boykov and Huttenlocher [1999] is based on Markov random fields (MRFs). They classify objects in camera images by incorporating statistical relationships between nearby object parts. A relational approach using MRFs has been proposed by Limketkai et al. [2005]. The idea here is to exploit the spatial relationship between nearby objects, which in this case consist of 2D line segments. The work that is mostly related to the approach described in this paper is presented by Anguelov et al. [2005], in which an AMN approach is used in a supervised learning setting to classify 3d range data. In this paper, we combine this approach with techniques from instance-based classification to obtain improved classification results.

3 Range Scan Classification

Suppose we are given a set of N data points p1, . . . , pN taken from a 2D or 3D scene and a set of K object classes C1, . . . ,CK. A data point in this context may be a 3D scan point or a 2D grid cell of an occupancy grid. The following formulations are identical in these two cases.

For each data point pi, we are also given a feature vector xi. Later we will describe in detail how the features are defined in the context of this paper. The task is to find a label yi ∈ {1, . . . , K} for each pi so that all labels yi, . . . , yN are optimal given the features. The notion of optimality in this context depends on the classification method we choose. In the standard supervised learning approach, we define a likelihood function Pω(y | x) of the labels y given the features x. Then, the classification problem can be subdivided into two tasks: first we need to find good parameters ω ∗ for the likelihood function Pω(y | x). Then we seek for good labels y ∗ that maximize this likelihood. Assuming we are given a training data set, in which the labels ˆy have been assigned by hand, we can formulate the classification as follows:

• learning step: find ω ∗ = argmax ω Pω(ˆy | x)
• inference step: find y ∗ = argmax y Pω ∗(y | x)

3.1 Collective Classification

In most standard classification methods, such as Bayes classification, Nearest Neighbor, AdaBoost etc. the classification of a data point only depends on its local features, but not on the labeling of nearby data points. However, in practice one often observes a statistical dependence of the labelings associated to neighboring data points. For example, if we consider the local planarity of a scan point as a feature, it may happen that the likelihood P(y | x) of the class label 'wall' is higher than that of the class label 'door', although all other scan points in the vicinity of this point belong to the class 'door'. Methods that use the information of neighboring data points are denoted as collective classification techniques (see Chakrabarti and Indyk[1998]). Recently, a collective classification approach to classify 3D range scan data has been presented by Anguelov et al. [2005]. The authors propose the use of associative Markov networks (AMNs), which are a special type of Relational Markov Random Fields, described in Taskar et al.[2002]. In the following we will briefly describe AMNs.

3.2 Associative Markov Networks

An associative Markov network is an undirected graph in which the nodes are represented by N random variables y1, . . . , yN. In our case, these random variables are discrete and correspond to the labels of each of the data points p1, . . . , pN. Each node yi and each edge (yi, yj) in the graph has an associated non-negative value ϕ(xi, yi) and ψ(xi j, yi, y j) respectively. These are also known as the potentials of the nodes and edges. The node potentials reflect the fact that for a given feature vector xi some labels are more likely to be assigned to pi than others, whereas the edge potentials encode the interactions of the labels of neighboring nodes given the edge features xi j. Whenever the potential of a node or edge is high for a given label (yi) or a label pair (yi, yj), the conditional probability of these labels given the features is also high. The conditional probability that is represented by the network can be expressed as

Here, Z denotes the partition function which by definition is given as Z = ∑y ′ ∏N i=1 ϕ(xi, y ′ i ) ∏(i j)∈E ψ(xi j, y ′ i , y ′ j ).

It remains to describe the node and edge potentials ϕ and ψ. In Taskar et al.[2004], the potentials are defined using the log-linear model. In this model, a weight vector w k is introduced for each class label k = 1, . . . , K. The node potential ϕ is then defined so that logϕ(xi, yi) = w k n · xi where k = yi. Accordingly, the edge potentials are defined as logψ(xi j, yi, yj) = w k,l e · xi where k = yi and l = yj. Note that there are different weight vectors w k n ∈ R dn and w k,l e ∈ R de for the nodes and edges.

For the purpose of convenience we use a slightly different notation for the potentials, namely

where y k i is an indicator variable which is 1 if point pi has label k and 0, otherwise.

In a further refinement step of our model, we introduce the constraints w k,l e = 0 for k nequal l and w k,k e ≥ 0. This results in ψ(xi j, k, l) = 1 for k nequal l and ψ(xi j, k, k) = λ k i j , where λ k i j ≥ 1. The idea here is that edges between nodes with different labels should be penalized over edges between equally labeled nodes. This last specification of AMNs makes it possible to run the inference step efficiently using graph cuts (see [Boykov et al., 1999; Taskar, 2004]).

4 Learning and Inference with AMNs

In this section, we describe how learning and inference can be carried out with AMNs. First, we reformulate Equation (1) as the conditional probability Pw(y | x) where the parameters ω are expressed by the weight vectors w = (wn, we). By plugging in Equations (2) and (3) we obtain that log Pw(y | x) equals

Note that the partition function Z only depends on w and x, but not on the labels y.

4.1 Learning

As mentioned above, in a standard supervised learning task the goal is to maximize Pw(y | x). However, the problem that arises here is that the partition function Z depends on the weights w. This means that when maximizing log Pw(ˆy | x), the intractable calculation of Z needs to be done for each w. However, if we instead maximize the margin between the optimal labeling ˆy and any other labeling y defined by

the term Zw(x) cancels out and the maximization can be done efficiently. This method is referred to as maximum margin optimization. The details of this formulation are omitted here for the sake of brevity. We only note that the problem is reduced to a quadratic program (QP) of the form:

Here, the variables that are solved for in the QP are the weights w = (wn, we), a slack variable ξ and additional variables αi, αi j and αji. We refer to Taskar et al.[2004] for details.

4.2 Inference

Once the optimal weights w have been calculated, we can perform inference on an unlabeled test data set. This is done by finding the labels y that maximize logPw(y | x). As mentioned above, Z does not depend on y so that the maximization in equation (4) can be carried out without considering the last term. With the constraints imposed on the variables y k i this leads to a linear programof the form

Here, we introduced variables y k i j representing the labels of two points connected by an edge. The last two inequality conditions are a linearization of the constraint y k i j = y k i ∧ y k j .

In our current implementation, we perform the learning and inference step by solving the quadratic and linear program from Equations (6) and (7). The implementation is based on the C++ library OOQP [Gertz and Wright, 2003]. As mentioned above, the inference step can be performed more efficiently using graph-cuts. However, in our application, in which the data sets were comparably small, the linear program solver turned out to be fast enough.

5 Instance-based Extension

The main drawback of the AMN classifier, which is based on the log-linear model, is that it separates the classes linearly. This assumes that the features are separable by hyperplanes, which is not justified in all applications. This does not hold for instance-based classifiers such as the nearestneighbor (NN) classifier. In NN classification, a query data point ˜p is assigned to the label that corresponds to the training data point p whose features x are closest to the features ˜x of ˜p. In the learning step, the NN classifier simply stores the entire training data set and does not compute a reduced set of training parameters, which is why it is also called lazy classification.

The idea now is to combine the advantage of instancebased NN classification with the AMN approach to obtain a collective classifier that is not restricted to the linear separability requirement. This will be presented in the next section.

5.1 The Transformed Feature Vector

Suppose we are given a general K-class classification problem where for each training data point ˆp we are given a feature vector ˆx of length L and a label ˆy ∈ {1, . . . , K}. Now, if we assume that the correct label for a new query feature vector ˜x corresponds to the label ˆy ∗ of its closest training example x ∗ in feature space, then the NN algorithm yields the optimal classification. Of course, this assumption is not valid in general, but we can at least say that the label ˆy ∗ will be more likely than any other label. As an example, consider the two-class problemwith two features depicted in the left part of Fig. 1. The two-dimensional feature space is defined by the training data shown as boxes. Now, the true labels of an arbitrary test data set, here shown as triangles, will be related to the labels of their closest training feature points. In our example, the probability of the label ˜y ∈ {1, 2} corresponding to ˜x is proportional to a Gaussian distribution N(μk, σ) with μk = d(˜x, ˆxk) and k ∈ {1, 2}. Here, ˆxk denotes the training example with label k that is closest to ˜x and d(· , ·) the distance in feature space. The variance σ is set to 0.03.

From the left side of Fig. 1, we can see that any attempt to separate the classes using hyperplanes (in this case lines) will lead to severe classification errors. However, if we introduce a feature transform τ : R L → R K in such a way that τ(˜x) = (d(˜x, ˆx1), . . . , d(˜x, ˆxK)), then the transformed features ˜t := τ(˜x) are more easily separable by hyperplanes. This is illustrated on the right side of Fig. 1. The reason for this is that the NN classifier always chooses the label corresponding to the smallest component of ˜t. This means, that the set Tk of all transformed feature points t = (t1, . . . , tK) that will be assigned the label k can be described by

As can be seen from this equation, the border of the set Tk is described by K - 1 hyperplanes passing through the origin. In the case of our two-class example, the only separating hyperplane (line) is described by the equation t1 = t2.

5.2 M Nearest Neighbors

One problem of the NN classifier is that the assignment of a label to a query point ˜p only depends on the labeling of one instance in the training set, namely the one whose feature vector is closest to ˜x. However, it is possible that the features of other training instances are also very close to ˜x, although they are labeled differently. For example, suppose that the distances of ˜x to the two closest training features ˆx 1 and ˆx 2 are very similar, and the corresponding labels ˆy 1 and ˆy 2 are different, the decision of assigning the label ˆy 1 to ˜p may be wrong, especially in the presence of noise. Therefore we proceed as follows: For the feature vector ˜x that corresponds to ˜p we compute the M nearest training instances in each of the K classes C1, . . . ,CK and the corresponding distances d(˜x, ˆx m k ) where k = 1, . . . , K and m = 1, . . . , M. These are used to define the transformed feature vector τM(˜x) as

Experiments show that higher values of M increase the classification rate, but for large M the improvement is very small. In our experiments, M = 5 turned out to be a good choice.

6 Experimental Results

We performed a series of experiments with 2D and 3D data to compare our instance-based AMN (iAMN) algorithm with the NN and the AMN classifier. The results of these experiments demonstrate that the iAMN outperforms the two other algorithms, independent of the features used.

6.1 Implementation Details

To speed up the learning process, we need to represent all feature vectors such that the nearest neighbor search in the feature space can be performed efficiently. To this end, we use kD-trees K1, . . . ,KK to store the training feature vectors of each class C1, . . . ,CK. This way, the computational effort of the nearest neighbor lookup becomes logarithmic in the number of the stored instances.

Thus, the training step consists of computing the features for the training data, transforming these features according to Eq. 8 and assigning the transformed features to the nodes of the AMN. The edge features of the AMN consist of a constant scalar value, as described by Anguelov et al. [2005]. After solving the quadratic program we obtain the weight vectors w k . Then, in the inference step, we use the transformed features τM(x) of the test data as node features for the AMN. Again, the edge features are constant.

Feature Computation Depending on the input data used, we computed different types of features for the data points. In the case of the 2D grid data, each point in the map is represented by a set of geometrical features which are extracted from a laser range scan covering 360 o field of view. Each laser is simulated and centered at each point in the map representing a free space [Mozos et al., 2005]. Because the number of geometrical features is huge (more than 300) we select the best ones using the AdaBoost algorithm.

For the 3D data set we computed spin images [Johnson, 1997] with a size of 5 × 10 bins. The spherical neighborhood for computing the spin images had a radius between 10 and 15cm, depending on the resolution of the input data.

Data Reduction When classifying data sets with many points, e.g., 3D scans with over 10, 000 scan points, the time and memory requirements of the AMN classifier grows very large. In these cases, we perform a data set reduction, again using kD-trees: after inserting all data points into the tree, we

(c) AMN

(d) iAMN

Figure 3: Classification results for one scene from the Multi data set

prune the tree at a fixed level λ. All points in the subtrees below level λ are then merged into one mean point. The spin image features, however, are still computed on the whole data set to provide a high density in the feature extraction.

6.2 2DMap Annotation

For the 2D classification experiment we used an occupancy grid map of the interior of a building. The map was annotated with three different labels, namely 'corridor', 'room' and 'lobby'. Then the map was divided into two non-overlapping submaps, one for training and one for testing. Fig. 2(a) shows the submap used for training and Fig. 2(b) the ground truth for the classification. The results obtained with the NN and the standard AMN approach are shown in Figs. 2(c) and 2(d), while Fig 2(e) shows the result of our iAMN algorithm. It can be seen that the iAMN approach gives the best result. The classification rate of the NN is with 92.2% higher than that of the standard AMN, which was 89.8%, but the classification is very noisy. In contrast, the iAMN result is more consistent wrt. neighboring data points and has the highest classification rate with 95.5%.

6.3 3D Scan Point Classification

Furthermore, we evaluated the classification algorithms on three different 3D data sets with an overall number of 38 scanned scenes. The scans were obtained with a 3D laser range scanner. The first data set is called Human and consists of 11 recorded scenes with two humans in varying poses. The scans were labeled into the four classes 'head', 'torso', 'legs', and 'arms'. The second data set named Single consists of 20 different 3D scans of the object classes 'chair', 'table', 'screen', 'fan', and 'trash can'. Each scan in the Single data set contains just one object of each class, apart from tables, which may have screens standing on top of them. The last data set is named Multi and consists of seven scans with multiple objects of the same types as in the Single data set.

The Human and Single data sets were evaluated using cross validation. For the Multi data set we used the object instances from the Single set for training, because those were not occluded by other objects. The classification was performed on the complete scans.

Fig. 3 shows a typical classification result for a scan from the Multi test set. We can see that NN assigns wrong labels to different points while their neighbors are classified correctly. The AMN results show that areas of points tend to be classified with the same label. However, due to the restriction to linearly separable data, many object parts are misclassified, especially in complex objects like chairs and fans. The results obtained with iAMN are better even in these complex objects, because the transformed feature vectors computed by iAMN are better suited for a classification based on separating hyper-planes. Table 1 shows the resulting classification rates. We can see that the iAMN classifier outperforms both of the others in all three data sets.

A statistical analysis using a t-student test with a significance level of 0.05 is shown in Fig. 5. As can be seen, for the Multi set our algorithm performs significantly better than both the NN and the standard AMN. A detailed analysis of the classification results is depicted in Fig. 4 wchich demonstrates that our iAMN yields highly accurate results for all three data sets.

7 Conclusions

In this paper we proposed an algorithm that combines associative Markov networks with an instance-based approach similar to the nearest neighbor classifier for identifying objects in 3D range data. In contrast to the approach suggested by Anguelov et al. [2005], our method is able to classify more complex objects with a diverse set of features per class. By using the distances of features to their nearest neighbors, the transformed feature space becomes more easily linearly separable. Accordingly, it improves the performance of the AMN training step. While the AMN inference task can be solved using graph-cuts, the drawback of our approach is, that by storing instances the resulting classifier becomes a lazy classification method. The inference step requires to compute the distance between the instance to be classified and the known training instances. This is computational expensive in general. However, by utilizing efficient data structures like kD-Trees the computational effort becomes logarithmic in the number of stored instances.

Despite these encouraging results, there are several aspects that warrant future research. One way to improve the approach presented here could be to classify the objects on a lower complexity level, i.e., by classifying object parts following the idea by Huber et al. [2004]. As features of less complex objects are distributed more compactly in the feature space, they might be easier to separate.

Acknowledgments

This work has partly been supported by the German Research Foundation under contract number SFB/TR8 and by the European Union under contract number FP6-004250-CoSy.