This paper describes a visual localization approach for mobile robots. Robot localization is performed as location recognition. The approach uses global visual features (e.g. GIST) for image similarity and a geometric veri cation step using vanishing points. Location recognition is an image search to nd the most similar image in the database. To deal with partial occlusions, which lower image similarity and lead to ambiguity, vanishing points are used to ensure that a matching database image was taken from the same viewpoint as the query image from the robot. Our approach will assign a query image to a location learned from a training dataset, to an "Unknown" location or in case of too much uncertainty the algorithm would refrain from a decision. The algorithm was evaluated under the ImageCLEF 2010 RobotVision competition1. The results on the datasets of this competition are published in this paper.
Recent approaches to visual robot localization using local image features and
visual words proved to work very well [
the similar overall structure but di er on the ne details. Fig. 1 illustrates this
concept. The two images show two meeting rooms from the di erent oors. The
table, chairs and pictures on the wall are di erent but the overall structure is
similar. There is a table in the center of the room, which creates a strong
horizontal edge feature. The outline of the room walls itself creates also strong edge
features converging in a similar manner. These are the features that we would
like to capture. To achieve this our approach uses GIST [
In the experiments using the dataset of the ImageCLEF 2010 RobotVision
competition [
The GIST descriptor used in our approach was rst introduced by Oliva et
al. in [
Before presenting our pipeline for semantic labeling of space, we rst discuss the
GIST descriptor which was introduced by Oliva et al. in [
The GIST descriptor was proposed by Oliva et al. in [
The premise to nd vanishing points are man-made environments containing
parallel straight lines. When looking at the perspective projection of three
dimensional parallel lines, they intersect in one common point in the image plane,
the so called vanishing point (VP) [
To estimate the vanishing points, we rst detect edges using canny edge detection and extract long straight lines from the edge segments. The straight lines are used as input for our RANSAC (random sample consensus) algorithm, which estimates multiple vanishing points in a single image. The algorithm rst randomly selects two lines and computes their intersection point P . If at least 20 of the lines passes through the intersection point P , the point is re-estimated using a non-linear optimization, where all supporting lines are included in the optimization process. The supporting lines are then removed from the input set and the procedure is repeated until either no further lines are available or no further vanishing point is found. The proposed pipeline for semantic labeling of space is illustrated in Fig. 3. The method classi es an image into one of the following three categories, which is either a label learned from a training dataset, the "Unknown" label or in some cases the algorithm would make no decision.
In a rst step a database of GIST descriptors is build from the training dataset. Our database consists of 4780 images and is represented by a kd-tree for fast k-nearest neighbors search, we chose k to be 10 in our experiments. In a rst step we query the database with the query image q, for its 10 nearest neighbors stored in the result set r. Images in the result set r with a L2 distance to the query image q, greater than a given threshold (0:6 in our experiments) are removed from r. If r is empty, the image q is labeled as "Unknown". Otherwise the set r is further matched to a set of ambiguous images, which were previously learned from the training dataset, see Fig. 4. If the set of ambiguous images in the set r is greater than the set of non-ambiguous images, the algorithm refrains a decision on the image q, due to lack of con dence. Otherwise, a geometric veri cation is applied to the remaining set of non-ambiguous images. The geometric veri cation compares the angular distance of vanishing points between the query image and the non-ambiguous images. Images with a large angular distance (0:34 in our experiments) are removed from the set r. Finally, the query image is assigned the label of the image with the smallest angular distance or is assigned the label "Unknown" if the set r is empty.
To nd vanishing point matches between two images, we rst normalize the VP vector to unit length, such that the VP lays on the surface of a Gaussian sphere. Then, for each VP in one image we do an exhaustive search for the closest VP in the other image i.e., the VP with smallest angular distance. We assume that two similar scenes match, if their appearance is similar i.e., similar GIST descriptor and similar vanishing points, meaning the camera has a similar point of view of the 3D scene being observed.
GIST descriptor
GIST descriptor training data k-nearest neighbor search
Filter GIST descriptor
GIST descriptor of ambiguous places Filter ambiguous
places Filter vanishing points
No decision
Match Unknown Our algorithm was evaluated at the 3rd edition of the Robot Vision challenge, held in conjunction with IROS 2010. The challenge addresses the problem of classifying rooms and functional areas based on a pair of stereo images. Three image sets were provided, one training set for learning, one validation set for the participants to validate their algorithm and one testing set used for the competition. All three sets were captured in the same building, but on di erent oors. All three oors have a set of common rooms, such as O ces, Toilet, Printer Area, Corridor, etc. and rooms which are only present in one of the dataset such as Kitchen, Lab, Elevator, etc.. Sample images of the training sets are provided in Fig. 5.
Task 1 of the competition asked to build a system which can answer the question "Where am I?", given one pair of stereo images. The answer can either be a previously learned label, the "Unknown" label if the system is presented with a new location not contained in the training set or it can refrain a decision by leaving the image unclassi ed. The performance of the algorithm was evaluated using the following scoring scheme: { +1.0 point for each correctly classi ed image. { -1.0 point for each misclassi ed image. { 0.0 point for each image that was not classi ed. { +2.0 points for a correct detection of unknown category. { -2.0 points for an incorrect detection unknown category.
Our system ranked rst, with 677 points in the 3rd edition of the Robot Vision challenge. The winning run used the following con guration: a search window size of 10 images, a minimum GIST distance threshold of 0:6, and a minimum mean angular distance threshold of 0:34. Door frames, walls and whiteboards were learned and added to the ambiguous location set as well as the following four rooms Kitchen, Small O ce and Large O ce.
Bellow we further discuss the bene t of the geometric veri cation. The evaluation is based on the validation set, which contains 2069 images, where 14:4% of the image labels are unknown to the training set. Without geometric veri cation an image match is obtained by searching the training set for the image with the smallest L2 GIST distance. Using the geometric veri cation an image match is obtained by choosing the image with the smallest mean angular distance between the query image and the images obtained from the k-nearest neighbors, with k = 30. Table 1 lists the recognition rate of each category known to the training set. Overall, the geometric veri cation performed slightly superior (recognition rate of 43:15%) to the pure GIST based method (recognition rate of 42:03%). The Meeting Room category achieved an improvement of over 8%.
For the label Corridor and Large O ce the pure GIST method performs better. The reason our method provides a lower performance on the Corridor Corridor a)
Corridor b)
Meeting Room c) category is that many images are misclassi ed at transitional places, where the robot moves from the corridor into a room. Fig. 6 illustrates such a misclassi cation. In the Large O ce category the misclassi ed images are mainly classi ed as Kitchen or as Small O ce. Fig. 7 illustrated a misclassi cation based on the GIST method, which is corrected by the geometric veri cation.
Our unoptimized Matlab implementation takes 51:21 seconds on a 2:66GHz Core2 Quad CPU, to classify 2069 images using precomputed GIST descriptors and precomputed vanishing points. Extracting GIST descriptors takes in average 1:91 seconds on a 487 487 pixel image. We make use of the freely available Matlab code provided by Antonio Torralba2. We use our own Matlab implementation to extract vanishing points. In average it takes 0:65 seconds to extract the vanishing points of one image.
We have presented a system for visual localization using global visual features (GIST) and a geometric veri cation based on vanishing points. We have shown that the geometric veri cation can indeed improve the recognition rate when used together with global visual features. The evaluation on the ImageCLEF 2010 RobotVision dataset showed that the approach manages to recognize similar locations despite of di erences on the small scale. The evaluation however also revealed that the approach has di culties in handling 'Unknown' locations. 'Unknown' locations are sometimes matched with locations from the training set and known locations are sometimes classi ed as 'Unknown' locations. Acknowledgments. We would like to thank Georges Baatz for sharing his vanishing point detection code.