Repositorio Institucional de Documentos

2013 32 Dorian Gálvez López Place and Object Recognition for Real-time Visual Mapping Departamento Director/es Informática e Ingeniería de Sistemas Tardós Solano, Juan Domingo Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Autor Dorian Gálvez López PLACE AND OBJECT RECOGNITION FOR REAL-TIME VISUAL MAPPING UNIVERSIDAD DE ZARAGOZA Informática e Ingeniería de Sistemas Director/es Tardós Solano, Juan Domingo Tesis Doctoral 2013 Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es Departamento Director/es Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Ph.D Thesis Place and Object Recognition for Real-time Visual Mapping Dorian G´alvez-L´opez Supervised by Juan D. Tard´os Computer Science and Systems Engineering Department Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza January, 2013 Place and Object Recognition for Real-time Visual Mapping Dorian G´alvez-L´opez Supervisor Juan Domingo Tard´os Universidad de Zaragoza, Spain Dissertation Committee Patric Jensfelt Kungliga Tekniska H¨ogskolan, Sweden Jos´e Neira Parra Universidad de Zaragoza, Spain Juan Andrade Cetto Universitat Polit`ecnica de Catalunya, Spain Jos´e Luis Blanco Claraco Universidad de Almer´ıa, Spain Andreas N¨uchter Jacobs University, Germany Pedro Pini´es Rodr´ıguez Universidad de Zaragoza, Spain Ricardo V´azquez Mart´ın Centro Andaluz de Innovaci´on y Tecnolog´ıas de la Informaci´on y las Comunicaciones, Spain International Reviewers Margarita Chli Eidgen¨ossische Technische Hochschule Z¨urich, Switzerland Giorgio Grisetti Sapienza Universit`a di Roma, Italy Brian Williams Google, USA Submitted in fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science and Systems Engineering with “International Doctor” Mention in the Computer Science and Systems Engineering Department, Escuela de Ingenier´ıa y Arquitectura, Universidad de Zaragoza. January, 2013. Project framework The work in this thesis has been funded by the following institutions: •Pre-doctoral grants: –Ministerio de Educaci´on, Cultura y Deporte of Spain: FPU-AP2008-02272; –Diputaci´on General de Arag´on, Spain: DGA-2008-B013/09. •Other grants: –European Union, –Comisi´on Interministerial de Ciencia y Tecnolog´ıa (Spain), –Diputaci´on General de Arag´on – Fondo Social Europeo, group T04 (Spain). The work in this thesis has been developed with the Robotics, Perception and Real Time Group of the University of Zaragoza in the framework of the following projects: •RoboEarth: EU Seventh Framework Programme, FP7-2009-248942; •Rawseeds: EU Sixth Framework Programme, FP6-2005-IST-045144; •nSPLAM: CICYT, DPI2009-13710; •SLAM6DOF: CICYT, DPI2006-13578. i CONTENTS 5.4.4 Bag-of-words object recognition process . . . . . . . . . . . . . . . . . . . 97 5.4.4.1 Region of interest segmentation . . . . . . . . . . . . . . . . . . 97 5.4.4.2 Database query . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.4.4.3 Correspondence computation . . . . . . . . . . . . . . . . . . . . 101 5.5 3D Pose computation from corresponding points . . . . . . . . . . . . . . . . . . 102 5.5.1 Homography for planar objects . . . . . . . . . . . . . . . . . . . . . . . . 102 5.5.2 General perspective-n-point problem . . . . . . . . . . . . . . . . . . . . . 105 5.6 EKF monoSLAM augmented with objects . . . . . . . . . . . . . . . . . . . . . . 106 5.7 Experimental evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.7.1 Independent view recognition for monoSLAM . . . . . . . . . . . . . . . . 108 5.7.1.1 Hospital room environment . . . . . . . . . . . . . . . . . . . . . 108 5.7.1.2 Desktop environment . . . . . . . . . . . . . . . . . . . . . . . . 110 5.7.2 Bag-of-words recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5.7.2.1 Geometrical verification performance . . . . . . . . . . . . . . . 114 5.7.2.2 Detection performance . . . . . . . . . . . . . . . . . . . . . . . 114 5.7.2.3 Execution time . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.7.2.4 Comparison with previous approach . . . . . . . . . . . . . . . . 117 5.8 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 6 Conclusions 119 6.1 Loop closing detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.2 3D Object recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.3 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Appendixes 121 A Inference with conditional random fields 123 A.1 CRF model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 A.2 Parameter learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 A.3 Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Bibliography 125 ix CONTENTS x Chapter 1 Introduction 1.1 Visual simultaneous localization and mapping Science on robotics has remarkably evolved during the last few years, and its applications are little by little becoming part of our lives. From autonomous platforms that transport products in warehouses, passing through domestic robotic vacuum cleaners, to humanoids able to make pancakes (Beetz et al. 2011), these applications present substantial challenges that are being tackled through different lines of research. One of the most important ones is simultaneous localization and mapping (SLAM), which allows mobile robots to create a map of their area as they explore it. This provides self-localization and knowledge about the environment, which is basic for any robot that must interact with its surroundings. The simultaneous localization and mapping problem consists in estimating the position of a robot and the landmarks that it observes concurrently, as the robot moves around an unexplored area. In other words, it provides the location of the robot in a map that is created at the same time, and that changes as the robot moves. This well-founded problem has been an active research topic for the last 25 years, and it has also been tackled in a lot of different ways during this time. Durrant-Whyte and Bailey offer a comprehensive survey of the problem and its solutions (Durrant-Whyte & Bailey 2006, Bailey & Durrant-Whyte 2006). Addressing this problem involved a breakthrough in mobile robotics, since it has made it possible to provide mobile platforms with real autonomy. The spread of inexpensive cameras has permitted SLAM approaches to benefit from visual information. In these cases, local features such as points, segments or regions are extracted from video images and used as landmarks to build maps. Thus, maps comprise geometrical entities that are repeatable and recognizable among images, and hence, suitable for tracking. At every step, the observed features must be matched in a jointly consistent manner to estimate the motion of the robot; this process is commonly known as data association. Building long-term maps from imagery entails an increasing complexity problem due to the large amount of data to process. This is especially evident when a robot moves along a trajectory and revisits a place, occurring a loop closure. A moving robot must be able to detect loops by recognizing the current place as one of all the previously visited ones. Then, the estimated positions of the robot and the landmarks located at that place can be merged to close the loop, reducing their uncertainty, obtaining the correct map topology and improving the accuracy of the global map. Since the robot is locating itself along the whole trajectory, it does not seem difficult to tell whether two positions are close enough to fire a loop detection. Nevertheless, this approach is hardly feasible in practice due to the 1 Chapter 1. Introduction measurement error that accumulates over time, rising the uncertainty of the estimated location. Actually, the process has to go the other way around: the detection of loop closures is necessary to locate the robot and the landmarks better. Although conceptually similar, this is a special case of the data association stage; instead of associating observations obtained in consecutive steps, former measurements must be considered. This requires to inspect all the information acquired from the map so far, and visual imagery have proved to be a reliable source of data to perform independent loop closure detection for large-scale maps (Williams et al. 2009). Geometrical elements are very convenient for robot localization because they are easy to obtain accurately. However, these produce maps that provide little information about the real environment, from a human point of view. The lack of conceptual meaning of geometrical entities makes them unsuitable when human-robot interaction is required in complex tasks. So there is a need to move from geometrical maps to meaningful maps with semantic content. Semantics in mapping has been considered in terms of places (Pronobis et al. 2010), objects (Rusu et al. 2009) and relationships between them defined by ontologies (Tenorth et al. 2012). These approaches allow to answer questions such as where the kitchen is, where the dishwasher is, or where mugs are usually found. In this work, we limit the broad meaning of semantic maps to those that include, in addition to geometrical elements, real objects as high-level entities, since they have semantic information that is easily understood by a person in a natural way (we usually know what an object is and for what it is used). Under this point of view, visual 3D object detection and recognition gains importance in SLAM systems. Object detection and object (or instance) recognition attain different meanings in the object retrieval literature. Usually, object detection refers to the task of noticing the presence of a known object in an image and of locating it, so that it can be outlined. In addition, instance recognition verifies the detection and yields additional information about each instance of the detected object, e.g. a rigid-body transformation locating the object in the 3D space, if possible. Detection and recognition are very related because sometimes the detection does not occur until the object is recognized and, hence, verified. For this reason, these terms are used interchangeably in this work, with the meaning of locating and recognizing the object at the same time. Therefore, object recognition answers the question of what objects are present in an image, if any, and where they are. Locating the objects in the 3D space and not just in the image is beneficial for tasks like grasping, and especially in visual SLAM, because this allows to place them in the map for informative purposes, or to be used as landmarks. On the other hand, although people are able to recognize probably hundreds of objects at a glance, this is still an open problem in computer vision. The distance to the object, its orientation, the occlusion with other scene elements, etc. are some of the factors that do not entail any deal to us, but which hinder the labor of 3D object recognition algorithms. Simply considering the kind of surface of the objects completely changes the way of approaching the problem, since the distinctive properties of patterned, plain or transparent objects differ. Rigid textured objects, on which this work focuses, are a branch of this field of study. Although latest research has provided solutions along that line (Grundmann et al. 2011, Hsiao et al. 2010), it has usually been aside from visual SLAM, whose context imposes certain conditions to which no attention is paid, such as the low quality of video images and the short time available between acquired frames. Classical algorithms focus mainly on obtaining high recall and accurate object location in a single image basis, at the expense of increasing the execution time. However visual SLAM provides plenty of images to be exploited in order to achieve high recall and accurate object location if the sequence is exploited as a whole. In real sequences, there are frames where objects cannot be detected since they are hardly distinguishable (because of their pose, blur, distance, etc.), so spending time trying recognition is not worth it because other camera frames, where the detection may be possible, are missed. This suggests the need of a different approach 2 1.2. Two problems, a general framework to perform fast object recognition for visual SLAM. Nowadays, the SLAM problem as originally formulated is theoretically solved, but it still presents practical challenges that stop us from achieving robotic applications able to work in large-scale or long-term scenarios, and to share a minimum language with people. Looking toward the future of robotic mapping for human interaction, we can say that the way passes through counting on reliable and efficient methods to recognize places and objects, able to detect correct loop closures to refine maps, and to place real objects in them. 1.2 Two problems, a general framework Both visual place and object recognition problems have a common basis: a large amount of real images requires a compact representation that allows a fast processing, in order to meet visual SLAM conditions. Figure 1.1: Framework to address place and object recognition. Our proposed framework works in four steps: 1) local features are extracted from an input image; 2) with a visual vocabulary, these are converted into a bag-of-words vector, 3) which is used to query a database to select as candidate match the stored bag of words with the highest similarity. If necessary by the application, the acquired bag-of-word vector can be inserted into the database, so it can be retrieved later. Finally, 4) the candidate is checked for consistency to be accepted. 3 Chapter 1. Introduction Visual vocabularies (Sivic & Zisserman 2003) are able to play this role. These are mechanisms to represent images as bags of words, a data type that builds on local features and that summarizes the appearance of an image as a sparse numerical vector, or equivalently, as a histogram of frequent features, named words. This translates the task of comparing images into the bag-of-words space, reducing its complexity. The compact representation permitted by bags of words is usually complemented with the efficiency of inverted indexes. In the information retrieval domain, where text documents are searched for query words, an inverted index (or inverted file) is a structure that maps words with the documents where they are present. Analogously, an inverted index can also map visual words with the images that contain them. These enable a quick content-based retrieval of images, basic in order to manage a large amount of images and achieve scalability. Direct indexes are also useful for information retrieval, but are not widely spread in the vision area. Opposing to inverted indexes, direct ones map images to words, which can be arranged in different useful manners, depending on the task to solve. By using together visual vocabularies and inverted and direct indexes, we build a general mechanism that offers a solution to the image comparison problem in large image databases. We propose a framework that makes use of this mechanism to address both the place and object recognition problems, as depicted by Figure 1.1. Its pipeline works in four steps: 1. Local features are extracted from an input image. 2. These are converted into a bag-of-words vector (BoW vector) by means of the visual vocabulary. 3. A database containing bags of words (from places or objects) is queried to obtain the candidate matches that present the highest appearance similarity with the input bag of words. Internally, the database is constituted by inverted and direct indexes, ensuring a quick access. 4. The candidate matches are checked for geometrical or temporal consistency with their corresponding models in the database. If they are successful, the matches are verified as a recognized place or object. This general framework is not subjected to any specific implementation of visual vocabularies or image databases, and it can be easily adapted to the specific place and object recognition problems. In the case of place recognition, the input is every image acquired as the robot moves, and the database is composed of the bag-of-words vectors of all the acquired images along the trajectory. Therefore, it is necessary to extend the third step by inserting the current bag-of-words vector into the database. This way, it can be matched in a future detection of a loop closure. Loop detections must pass two consistency checks to be accepted. Firstly, temporal consistency has to be satisfied. For that, it is required that the candidate match is consistent with loops detected in some of the last video frames. The process of querying the database to obtain a candidate that satisfies temporal consistency is named loop candidate retrieval. Secondly, the geometry of the involved scenes must match; this is the loop verification. We check this condition by using epipolar geometry with one and two cameras, and with Cadena et al.’s (2012) probabilistic algorithm that makes use of conditional random fields. For object recognition, the input is the current frame acquired by a camera in which object detection is carried out. In this case, all the features extracted from the entire image in step one can be converted into a bag of words; otherwise, they can be separated into subsets and converted into several BoW vectors that result in individual queries. This second method is 4 1.3. Goals and contributions of this work useful to divide the image into smaller regions to avoid clutter while looking for small objects. The database contains models of objects that represent their appearance and geometry. Thus, when querying, the object candidate retrieval returns as candidate match the model with the most similar appearance to the input BoW vector. In the fourth and final step, the object verification checks the geometry between the candidate model and the input features for consistency. As we present along this thesis, our proposed framework is a capable system that yields successful results in the place and object recognition problems under several challenging circumstances. 1.3 Goals and contributions of this work Place and object recognition are topics widely studied by the robotics community, but although a great attention is paid to low-latency systems, video-rate performance, very beneficial for visual SLAM, had not been achieved. The main goal of this work is to propose novel solutions that are able to achieve reliable detections of loops and objects in heterogeneous and challenging cases, without false positives, and, at the same time, to result in video-rate performance suitable for real SLAM algorithms in large-scale scenarios. Aiming at this goal, the contributions of our work have been: •For the first time, we use binary features in the bags-of-words approach to solve place and object recognition, where floating-point features were usually utilized before. Binary features remove the bottleneck in these recognition problems, decreasing execution time from hundreds to tens of milliseconds. •We enhance the bag-of-words approach by incorporating novel direct indexes for visual words to speed up the computation of corresponding points in the verification stage. These allow a reduction of the execution time of this step from one hundred to a couple of milliseconds. •We present the benefits of exploiting in several ways the sequentiality of images gathered by a video camera to improve the reliability of detections in the loop detection problem. These novelties overcome the results of the state-of-the-art techniques. •Departing from most previous works, to avoid over-tuning, we present extensive results of the loop detection algorithm using a single vocabulary, obtained from independent data, and the same parameter configuration, obtained from a set of training datasets, without peeking on the evaluation datasets. Our loop detection system yields no false positives in a sequence with 26300 images, and requires 22ms per frame, being one order of magnitude faster than previous approaches. •We present the first real-time monocular SLAM system that performs recognition of 3D objects as creates the map. Objects are located in the map and their pose is refined over time. We then enhance the detection of 3D objects by using a comprehensive representation of their appearance in a single bag-of-words vector, allowing recognition to run in 28ms per image with medium-sized databases. 1.4 Publications, Videos and Software 1.4.1 Publications This work has resulted in the following publications: 5 Chapter 1. Introduction •Loop detection: 1. Pini´es P., L. M. Paz, D. G´alvez-L´opez & J.D. Tard´os (2010), ‘CI-Graph SLAM for 3D Reconstruction of Large and Complex Environments using a Multicamera System’, International Journal of Field Robotics 27(5), 561–586. 2. Cadena, C., D. G´alvez-L´opez, F. Ramos, J.D. Tard´os & J. Neira (2010), Robust place recognition with stereo cameras, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)’, pp. 5182–5189. 3. Cadena, C., D. G´alvez-L´opez, J.D. Tard´os & J. Neira (2012), ‘Robust place recognition with stereo sequences’, IEEE Transactions on Robotics 28(4), 871–885. •Loop detection with binary features: 1. G´alvez-L´opez, D. & J.D. Tard´os (2011), Real-time loop detection with bags of binary words, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems’, pp. 51–58. 2. G´alvez-L´opez, D. & J.D. Tard´os (2012), ‘Bags of binary words for fast place recognition in image sequences’, IEEE Transactions on Robotics 28(5), 1188–1197. •3D Object recognition: 1. Civera, J., D. G´alvez-L´opez, L. Riazuelo, J.D. Tard´os & J.M.M. Montiel (2011), Towards semantic slam using a monocular camera, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)’, pp. 1277–1284. 2. Waibel, M., M. Beetz, R. D’Andrea, R. Janssen, M. Tenorth, J. Civera, J. Elfring, D. G´alvez-L´opez, K. Haussermann, J.M.M. Montiel, A. Perzylo, B. Schiessle, O. Zweigle & R. van de Molengraft (2011), ‘Roboearth’, IEEE Robotics Automation Magazine 18(2), 69–82. 3. G´alvez-L´opez, D. & J.D. Tard´os (2013), Fast and scalable 3D object recognition with vocabularies of binary words for semantic SLAM, To be submitted to ‘IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)’. Although they are not tackled by this thesis, our work resulted in other research collaborations, and in turn, it was partly originated from the inspiration received from them: 1. G´alvez-L´opez, D., K. Sj¨o¨o, C. Paul & P Jensfelt (2008), Hybrid laser and vision based object search and localization, in ‘IEEE International Conference on Robotics and Automation’, pp. 2636–2643. 2. Sj¨o¨o, K., D. G´alvez-L´opez, C. Paul, P. Jensfelt & D. Kragic (2009), ‘Object search and localization for an indoor mobile robot’, Journal of Computing and Information Technology 17(1), 67–80. 3. Majdik, A., D. G´alvez-L´opez, G. Lazea & J.A. Castellanos (2011), Adaptive appearance based loop-closing in heterogeneous environments, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)’, pp. 1256–1263. 6 1.5. Structure 1.4.2 Videos The results presented in this work are complemented by the videos detailed next. These can be found in http://webdiis.unizar.es/~dorian/videos: 1. Real-time loop detection: 1.a. NewCollege dataset: GalvezTRO12_NewCollege.avi 1.b. Bicocca25b dataset: GalvezTRO12_Bicocca25b.avi 2. 3D Object recognition: 2.a. Visual SLAM, hospital room: CiveraIROS11_Hospital.avi 2.b. Visual SLAM, desktop: CiveraIROS11_Desktop.avi 2.c. Bag-of-words object recognition: Galvez13_ObjRec.avi 1.4.3 Software As a final contribution, all the implementation of our work is publicly available as open source software. It can be found in: •http://webdiis.unizar.es/~dorian •http://www.ros.org/wiki/roboearth 1.5 Structure The layout of this work is divided into 6 chapters. We start by introducing the problem and putting our work in context with respect to the state of the art in the current Chapter 1 and in Chapter 2. In Chapter 3 we describe the usage of visual vocabularies, bags of words and inverted indexes to present our image comparison framework used with generic image features. In Chapter 4 we look into the computational requirements of our loop detection approach, and propose a new configuration to work at video-rate with binary features and a direct index. Chapter 5 is devoted to the 3D object recognition problem. Here, we first present a monocular SLAM system that recognizes real 3D objects and places them in the map, by using a multiview object modeling approach. Later, we make use of our framework, introduced in previous chapters, to enhance the object recognition algorithm. Finally, in Chapter 6 we recapitulate the achievements made by our work, and discuss how it can be improved in a future research. 7 Chapter 1. Introduction 8 2.3. Object recognition for SLAM a user-outlined object in a video. The object is represented by a bag of words built on a set of viewpoint invariant region descriptors, so that recognition can proceed successfully despite changes in viewpoint, illumination and partial occlusion. The temporal continuity of the video within a shot is used to track the clusters and reject unstable regions reducing the effects of noise in the descriptors. The work by Sivic & Zisserman (2003) became a de facto standard to address single-view object recognition in large sets of images. As Szeliski (2010, Chapter 14) describes, it can be summarized in the following steps. First, a collection of features is acquired from a set of images; these are clustered in the descriptor space and the visual vocabulary is obtained. The image database is then created by computing the term frequency – inverse document frequency (tf-idf ) vector of each image. These are the bag-of-words vectors of the image stored in the database, which are indexed by an inverted index. The image retrieval is performed by extracting features from and input image and computing its bag-of-words vector with tf-idf values. It is compared with the other vectors in the database, accessed with the inverted index, by computing a similarity score. The top-ranked database images are selected as matching candidates and their spatial consistency is checked to select the final matches. Along this line, Nister & Stewenius (2006) used a hierarchical vocabulary to achieve successful detections in large object databases of three different applications. They retrieved objects by matching images depicting them under different points of view, that were stored in a database with 6376 images in total. They also performed recognition with 40000 planar CD covers and arbitrary objects in a one million movie shot database, showing that hierarchical vocabularies offer an even more scalable solution to this recognition problem. The larger the database, the more prone to mismatches the recognition is. To address this issue, Chum et al. (2007) used a query-expansion method to increase the recall when detecting objects by its appearance. For this, all initial candidates are re-ranked using an affine homography, so that the database is queried again with the best first candidates. Recognizing objects modeled as single images is useful from the point of view of computer vision; however, for visual SLAM it is more advantageous to deal with 3D objects that can be located in the 3D space. Nevertheless, all these approaches show the reliability of visual vocabularies to perform object recognition, which can be translated into the 3D domain. 3D Object models. A common approach to recognize objects in single images and compute its 3D pose requires modeling the object as a collection of local image features as SIFT or SURF associated to 3D coordinates in an object frame. Then, given an image, its local features are matched against those from the model, and the pose is obtained by solving with random sample consensus (RANSAC) (Fischler & Bolles 1981) the perspective-n-point (PnP) problem. This is a classical problem in photogrammetry consisting in determining the location in space from which an image was obtained by recognizing a set of control points (Fischler & Bolles 1981). Matching is usually speeded up by discretizing feature descriptors into clusters with some of the visual vocabulary techniques described above. Following the line of the current state of the art (Collet et al. 2011, Rublee et al. 2011, Sattler et al. 2011, Pangercic et al. 2011, Grundmann et al. 2011, Hsiao et al. 2010), we compare the similarity between images and object models composed of 3D points attached to image descriptors. We do it with two different approaches to model the appearance of the objects: with independent sets of SURF features, and with a single bag of binary words built on ORB features, applying a policy of allowing several descriptors per 3D point to capture richer viewpoint information. The later differs from previous works in that we use binary features with a visual vocabulary composed of several trees of binary nodes. Pangercic et al. (2011) build a large database by using a SIFT vocabulary tree trained with 15 Chapter 2. Related work the object images. They propose a method to build a vocabulary incrementally when new objects are added. In our approach, we use independent images to build a single vocabulary which does not need incremental building. In real scenarios, objects do not appear well separated from the background, but together with the rest of the scene clutter. To avoid background clutter, especially when detecting small objects, it is necessary to focus the recognition on salient areas in the images, named regions of interest (ROIs). To divide query images into ROIs, Pangercic et al. (2011) cluster the scene 3D point cloud provided by other devices, such as a Kinect camera, and back-project them into the image. To obtain ROIs, we rely on a novel combination of the clustering methods k-means++ (Arthur & Vassilvitskii 2007) and medoidshifts (Sheikh et al. 2007) which use the image as input only, consuming short time. Hsiao et al. (2010) discretize the SIFT descriptor space into three levels in a hierarchical manner. They show the benefits of computing feature matches at all the levels, obtaining more putative correspondences which yield a higher object recognition rate. However, they do not select an object candidate to match, so that the RANSAC step may be overburdened, leading to a large increase of the execution time when considering several objects. When using bags of words, we are able to retrieve the best candidate model when querying the database, avoiding an exhaustive comparison with all the models. The approach by Sattler et al. (2011) can also handle large databases. They quantize the SIFT descriptor space with k-d trees (Muja & Lowe 2009), and compute correspondences between those descriptors discretized as the same visual word only. In our case, we use a direct index to set the discretization level at which correspondences are computed, so we can consider coarser levels to be less restrictive. Their approach is not aimed at semantic mapping, but to recognition of buildings in high-resolution pictures. Thus, although they speed up feature matching, they do not focus on real-time performance with low-resolution cameras. Execution time. The works above do not provide recognition at video frequency due to the difficulties pointed out: extraction of regions of interest, selection of candidate model and computation of corresponding points to obtain a rigid-body transformation. We have to add to them the first time-consuming step: the extraction of robust features, such as SIFT or SURF, which can cope with scale, rotation and other changes. The computation of these features takes more than 100ms per image. Rublee et al. (2011) showed that their binary feature ORB can be used for object recognition at a fraction of the time required by SIFT or SURF, by performing simple feature matching with LSH tables with independent views of the objects. In this work, we make use of ORB in our 3D object recognition approach based on bags of words, obtaining successful and fast results using trees with a direct index instead of LSH tables. In addition, we comprise the multiple views of the object as a single bag-of-words vector, avoiding redundant comparisons with features seen from several points of view. There is usually a trade-off between the execution time spent to find the 3D pose of a recognized object in an image and its accuracy, so that an accurate pose has a higher computational cost. The works above focus mainly on accuracy for applications other than visual SLAM, such as grasping, so that execution time is not a priority. Their target is to obtain a precise location of the object from a single image. For that, they usually try lots of candidate locations to check which one matches the input image the best, requiring large execution time. On the other hand, visual mapping provides plenty of images to be exploited in order to achieve high recall and accurate object location if the sequence is exploited as a whole. Visual SLAM is able to refine a noisy pose of a 3D object inserted in the map over time as the SLAM algorithm reduces the uncertainty of the map landmarks. Furthermore, in real high-rate video sequences there are frames in which recognition cannot be successful because objects are not distinguishable at all due to their distance, their pose, image artefacts, motion blur, noise, etc. 16 2.3. Object recognition for SLAM Thus, it is desirable to reject those frames quickly and process the following ones, where the detection may be possible, instead of spending time trying recognition and missing frames. Our bag-of-words approach allows a scalable 3D object recognition. This is also achieved by Collet et al. (2011), who perform recognition at 300ms per 640 ×480 image with 91 objects by exploiting parallelism in a GPU/CPU architecture. Our proposal goes a step farther providing 3D object recognition at video frequency on a conventional CPU. This is very beneficial for robotic interaction tasks in general and for semantic mapping in particular, because although visual SLAM can be performed at video frequency (Klein & Murray 2009, Davison et al. 2007), this had not been achieved for object recognition. 17 Chapter 2. Related work 18 Chapter 3 Appearance-based loop detection 3.1 Image database An image codes a large amount of information. Even a low resolution 320 ×240 image contains dozens of thousands of pixels that are translated into a lot of kilobytes of computer memory. This entails a great difficulty when this information must be managed in real time. The way to ease this issue is to reduce the image to its most descriptive features doing without those pixels that provide little information, transforming later the features into bags of words, obtaining a sparse and compact representation of the image, suitable to be efficiently indexed in an image database. 3.1.1 Images as bags of words Although local image features describe the most salient areas of an image and put up with some image transformations, images represented by their local features can still take large memory. For example, it is very common to describe a small 640 ×480 image with 300–500 point-based features. When using SIFT or SURF features, their descriptors take between 75 and 250KB, which is a large amount of data. Figure 3.1: Example of text retrieval concepts applied to the visual domain. Images are visual documents whose local features are converted into visual words, allowing to represent their appearance as histograms of words. Credit: Nister & Stewenius (2006). 19 Chapter 3. Appearance-based loop detection In order to mitigate this, image features are reduced by means of a visual vocabulary (Sivic & Zisserman 2003), drawing an analogy with the vocabularies firstly used for information retrieval in text documents (Baeza-Yates & Ribeiro-Neto 1999). In text retrieval, documents were considered sets of unordered words and represented as histograms of word occurrence frequencies. Similarities between two documents were made in terms of how many similar words they contained and how descriptive they were. These concepts are transfered to the visual domain by considering images as documents composed of visual words that represent their features, as illustrated in Figure 3.1. As in the text case, a visual vocabulary is an structure to represent a set of image features as a more simple histogram, allowing a compact representation with low storage requirements and fast image comparison. The visual vocabulary consists of visual words, which are a set of predefined descriptors. Any other feature can be converted into that visual word which is closest in the descriptor space. Then, the conversion of a set of image features results in a vector of visual words called bag of words. Each entry of an image bag-of-words vector corresponds with the value that each vocabulary word is given in that image. Instead of frequency terms, visual bag-of-words values are set according to the descriptiveness of each word, depending on how often they are expected to occur in images. This information can be obtained by counting the times each word appears in a set of heterogeneous training images. Following the text retrieval example, words such as prepositions and articles would obtain a low weight because they are very common and do not provide salient information about the content of a certain text document. Visual vocabularies usually comprise between 10K and 1M words. Since this number is remarkably larger than the words extracted from an image, bag-of-words vectors use an sparse representation to avoid storing empty entries. As a result, the appearance of an image with 500 features will be represented with a sparse vector of fewer than 500 floating-point values. 3.1.2 Visual vocabularies from descriptor space clusters A visual vocabulary is created by dividing the descriptor space into a finite set of enumerated clusters, so that any point in the space can be represented by the cluster containing it. At the expense of approximating, this mechanism provides a twofold benefit: it allows to represent a multidimensional descriptor vector as a single integer (the index of its cluster), and facilitates the match between similar features, since those that are close in the descriptor space are likely to lie in the same cluster. The visual vocabulary is created offline by discretizing the descriptor space into Wclusters, the so-called visual words. Sivic & Zisserman (2003) present a single quantization of the space into Wclusters, but Nister & Stewenius (2006) proposes a hierarchical clustering which improves efficiency. In this case, the space is recursively clustered into kwregions that become finer and finer, up to Lwclustering levels, yielding the W=kLw wfinal clusters. This makes the vocabulary be structured as a tree, as the example shown in Figure 3.2. With the clustering done by Sivic & Zisserman (2003), a point in the descriptor space must check Wclusters to select the one to which it belongs. The advantage of the method proposed by Nister & Stewenius (2006) is that it permits decreasing the number of comparisons to kw·Lw, because only a subset of clusters are considered at each step. This results in a more efficient approach to convert features into words, which can deal with larger vocabularies to achieve higher retrieval quality. To build the hierarchical vocabulary tree, we extract a rich set of features from some training images, independently of those processed later. The descriptors extracted are first discretized into kwclusters by using the k-means++ algorithm (Arthur & Vassilvitskii 2007). This algorithm starts picking kwrandom and well-distributed samples as cluster candidates, which are represented as single points in the descriptor space. The rest of the samples are then associated 20 3.1. Image database Figure 3.2: Toy example of a vocabulary tree with branching factor kw= 3 and Lw= 2 depth levels. Each node represents a cluster in the descriptor space, and each level, a discretization factor, from coarse (closer to the root) to fine. Leaves are the words of the vocabulary. (a) Word example 1 (b) Word example 2 Figure 3.3: Example of image patches that create visual words. As a result of the descriptor space clustering, visual words represent similar featurue descriptors. Credit: Sivic & Zisserman (2003). to their closest cluster candidates, and new clusters are computed as the centroids of each group. This process is repeated iteratively until clusters converge. The final clusters form the first level of nodes in the vocabulary tree. Subsequent levels are created by repeating the k-means++ operation with the descriptors associated to each node, up to Lwlevels. We finally obtain a tree with W=kLw wleaves, which are the words of the vocabulary. Figure 3.3 illustrates the results that may be obtained after clustering the descriptor space. Words are obtained as the centroid of the descriptors of image patches with similar appearance. 3.1.3 Word weighting and image conversion Each word of the vocabulary is given a weight according to its relevance in the training corpus, decreasing the weight of those words which are very frequent and, thus, less discriminative. During the tree building, we weight each word wiwith its inverse document frequency (idf ): idf(i) = log N ni(3.1) where Nis the number of training images, and ni, the number of images which contain the word wi. To convert an image Iinto a bag-of-words vector v∈RW, the descriptors of its features traverse the tree from the root to the leaves, by selecting at each level the intermediate nodes 21 Chapter 3. Appearance-based loop detection Figure 3.4: Example of image database composed of a vocabulary tree and an inverted index. The inverted index stores the weight of the words in the images in which they appear. that minimize a distance function, such as the Euclidean one. This allows us to calculate the term frequency (tf ) of each word in this image: tf(i, I) = niI nI (3.2) where niI stands for the number of occurrences of word wiin image I, and nI, for the number of words in I. The i-th entry of vis then given the value vi= tf(i, I)×idf(i), obtaining the term frequency – inverse document frequency (tf-idf ) weight as proposed by Sivic & Zisserman (2003). Bag-of-words vectors are finally normalized to mitigate the effects of dissimilar number of words between vectors when these are compared (Nister & Stewenius 2006). We use the L1-norm since it yields better results than the L2-norm according to Nister & Stewenius (2006). Sivic & Zisserman (2003) analyze the relative merits of the tf and idf terms, and show the benefits of the complete tf-idf weight to increase retrieval accuracy in comparison with using just the term frequency factor or binary bag-of-words vectors, where entry values viare set either 1 or 0 to indicate the presence of a word in an image. In information retrieval, words which are very common among text documents (such as prepositions or articles) are ignored because they are hardly discriminative; these are named stop words. Sivic & Zisserman (2003) propose considering the most frequent visual words as stop words to suppress them and improve the image matching. However, as other authors (Yang et al. 2007), we did not obtain more accurate image matches when stopping the most frequent words in the vocabularies of our initial tests, so we do without stop words in this work. 22 3.2. Loop candidate retrieval 3.1.4 Image database for efficient indexing We build a database to index images collected when traversing a trajectory. Our image database relies first on a visual vocabulary, since the lightweight representation yielded by bags of words enables to manage a large number of images. The next step to perform loop detection in a video sequence is to store images efficiently. The database must provide quick image comparisons and retrieval when queried in order to be reliable in large-scale mapping. An inverted index structure, also known as inverted file, is used for this purpose, since it has proved advantageous for image retrieval in general (Sivic & Zisserman 2003) and for loop detection in particular (Cummins & Newman 2011). The inverted index is a structure that stores for each word wiin the vocabulary a list of images Itwhere it is present, being tthe timestamp at which the video frame is acquired. This is very useful when we must query the database to compare a given image with all those stored before, since it allows to perform comparisons only against those images that have some word in common with the query one. In addition to image references, we augment the inverted indexes to store also the weight of each word in those images to enable a quick access. Thus, an inverted index stores for each word wia list of pairs hIt, vi ti, where vi tis the value of the i-th word in image It. Each time an image is added to the database, a new pair is added to the inverted indexes of the words it contains; they are accessed when the database is queried. The composition of the image database results as shown in Figure 3.4. 3.2 Loop candidate retrieval To detect loop closures, we propose a method that we firstly presented in Pini´es et al. (2010) and later improved in Cadena et al. (2010) and Cadena et al. (2012). It is depicted in Figure 3.5 and follows these steps for each image acquired as the robot moves: 1. The image is converted into a bag of words. 2. We search the database for the current image to retrieve those scenes whose similarity is high enough. 3. The image is added to the database by updating the inverted index. 4. We compute a normalized score that adapts to the appearance of each image to obtain a similarity value. 5. The match with the highest score is checked for temporal consistency with previous scenes to obtain a loop closing candidate. 6. Finally, if the best candidate passes a geometrical verification, the loop detection is accepted. This step is addressed in Section 3.3. 3.2.1 Database query By means of the visual vocabulary we can measure the resemblance between images just by comparing their bag-of-words vectors. There are several statistical metrics one can apply to two vectors. Sivic & Zisserman (2009) make a comprehensive comparison between the properties of the statistical distances commonly used: L1-norm, L2-norm, Bhattacharyya coefficient (Bhattacharyya 1943), Kullback-Leibler (KL) divergence (Kullback & Leibler 1951) and χ2distance. Here, we use a score based on the L1-norm distance, denoted dL1, between two images to 23 Chapter 3. Appearance-based loop detection Figure 3.5: Scheme of our loop detection approach applied to each scene at time tin a sequence. detect loops, as done by Nister & Stewenius (2006). Given two normalized bag-of-words vectors vand w, the score sL1(v,w) is defined as sL1(v,w) = 1 −1 2dL1(v,w) (3.3) = 1 −1 2kv−wk1.(3.4) The score sL1(v,w) varies in [0..1]. It obtains its highest value for maximum similarity, and 0 when there is no resemblance at all. As noticed by Nister & Stewenius (2006), we can express the distance dL1in terms of common vector entries to take advantage of the inverted index later. Let V={i|vi6= 0},V={i|vi= 0}be the set of indexes of words of vwhich are non-empty 24 3.3. Loop verification Ci,i= 1,2,... Then, we compute the fundamental matrices Fibetween images Ii tand Ii t′with the SURF features, as explained in Section 3.3.1. If any of these matrices cannot be computed, the geometrical check fails. By means of Fi, we are able to search Ii tfor Harris corners that appeared in Ii t′and are still alive in the SLAM map, as shown in Figure 3.7. This search is performed by normalized cross-correlation of 15 ×15 patches extracted along the epipolar lines yielded by Fifor each Harris feature in Ii t′. If the loop candidate is valid, enough consistent features must be found. Since several cameras are available, we double-check the Harris features for pairwise consistency between cameras. Given any pair of cameras Ciand Cj, we check if those persistent Harris corners found in Ii tand Ij tappear in consistent locations in the image, according to the epipolar lines generated by Fij and Fji, computed in advance as explained above. This is illustrated by Figure 3.7 as well. The loop candidate images pass this geometrical check if the final number of corresponding features is high enough. The more pairs of cameras considered, the more restrictive check results. For CI-Graph SLAM, using just the pair of cameras that presented the widest baseline sufficed to obtain robust results without overburden the system, requiring 8 final correspondences. Note as well that when this geometrical check is passed, the data association between map features at time tand t′is obtained, allowing any SLAM system to add a constraint to correct the map. 3.3.3 Conditional random fields for stereo cameras When two calibrated cameras are mounted on a stereo rig, we can obtain a disparity image with 3D information by triangulation of points appearing in both images. This metric data can be incorporated to the loop verification to obtain a more robust geometrical check (Majdik et al. 2011, Konolige et al. 2010). In this work, we propose computing descriptors from 3D data in addition to image data to reason about them by means of conditional random fields (CRFs), a probabilistic undirected graphical model first developed for labeling sequence data (Lafferty et al. 2001). For that, we use Cadena’s (2011) CRF-Matching, an algorithm able to jointly reason about the association of features, presented working together with our loop detection approach in Cadena et al. (2012). CRF-Matching was recently proposed for matching 2D laser scans (Ramos et al. 2007) and matching image features (Ramos et al. 2008). Cadena (2011) extends CRF-Matching to reason about the association of data provided by the stereo camera system in both image space and in 3D space. This allows our system to consider all information provided by a stereo pair, coming from both near and far objects. Figure 3.8 shows the modified loop detection algorithm when including CRF-Matching as geometrical verification, with the new steps highlighted. The first modification takes place before applying the CRF-Matching. After verifying the temporal consistency of the loop candidate, its normalized similarity score ηL1is checked again to see if it is reliable enough not to perform any further verification, i.e. skipping the CRF-Matching. For that, we set a threshold α+ from which we directly accept the loop candidate by its appearance if ηL1≥α+. We do this because the computation of the CRF descriptors and likelihoods, which we explain later, can be time-consuming. If the similarity score ηL1is not trustworthy enough to confirm the loop candidate, we run the CRF-Matching algorithm proposed in Cadena’s (2011) Ph.D thesis. Given the two images Itand It′of a loop candidate, CRF-Matching is applied in three steps: 1. Two graphs G3D and GIare created from 3D points and image features of Itand It′. These are used to compute geometrical and appearance descriptors. 2. Conditional random fields infer the probability of those graphs matching. 31 Chapter 3. Appearance-based loop detection Figure 3.8: Scheme of our loop detection approach with the CRF-Matching verification (darker nodes). 32 3.3. Loop verification 3. Two normalized scores, η3D and ηI, are created from the matching probability obtained before, taking image sequentiality into account. The loop is verified by comparing η3D and ηIwith the control parameters α3D and αIand checking whether the desired level of similarity is reached. This step was firstly proposed together with our loop detection algorithm in Cadena et al. (2012). For the reader’s convenience, we detail the most relevant steps of the CRF-Matching algorithm as we use it in our work. For further detail, please see Appendix A. As graph structure for the CRFs in our problem, we propose the use of the minimum span- (a) Image features (b) MST over images coordinates for far features (GI) (c) MST over 3D metric coordinates for near features (G3D) (d) 3D visualization of G3D Figure 3.9: Scene from an outdoor environment. In each scene we get the features over one image of the stereo pair 3.9(a), and compute the two MSTs: one for features with 3D information (near features), and the other for the remaining ones (far features). On 3.9(b), we show the graph for far features (GI) in blue, in dark red the graph for near features (G3D) on 3.9(c). We apply the CRF-Matching over both graphs. The MST of G3D is computed according to the metric coordinates, here projected over the images only for visualization. On 3.9(d), we show G3D in metric coordinates with the 3D point cloud (textured) of each vertex in the tree. The MST gives us an idea of the dependencies between features in a scene, and enforce the consistency of the features association between scenes. 33 Chapter 3. Appearance-based loop detection ning tree (MST), where vertices are the features detected in the images, and edge weights are Euclidean distances between them. Because we code near information in the 3D metric space, and far information in image coordinate space, each type of visual information is represented in a separate graph, as shown in Figure 3.9: G3D models the near objects, i.e. those pixels with dense information from the stereo, and hence with 3D information; and GI, the far objects from pixels without disparity information. The nodes of the graphs are the feature locations, and the edges of the graphs result from computing the minimum spanning tree, according to the Euclidean distances between the pixel coordinates in the case of GI, and between the 3D metric coordinates in the case of G3D. The aim of the CRF-Matching algorithm is to compute the set of corresponding features between two scenes at tand t′with highest probability. This is denoted p(x|z), where zstands for the observed image features and their properties, and xis a vector of hidden states x= hx1,x2,...,xnithat codes for each of the nfeatures of Itthe matching feature out of the mones present in It′, i.e. xi∈ {0,1,2,...,m}, where the additional state 0 is the no-match state. This conditional distribution is written as a log-linear combination of descriptor functions f: p(x|z) = ρexp   X q∈Q wT·f(xq,z)  (3.20) where Qis a set of subgraphs of G3D and GI,wqa vector of weights of each descriptor function f, and ρis a normalization factor. The idea behind this equation is to exploit the information provided by features which are close in the image and the space, instead of treating each feature individually. For an extended explanation of this model, the reader is referred to Appendix A. The CRF matcher can employ arbitrary local functions to describe shape, image properties, or any particular aspect of the data. These are the descriptor functions f, which describe differences between shape (only for G3D) and appearance (for G3D and GI) of the features. The descriptor functions that we use are the following: 1. Shape difference: These functions capture how much the local shape of dense stereo data differs for each possible association. We use the geodesic, PCA and curvature distance. The geodesic distance, defined as the sum of Euclidean distances between points in the minimum spanning tree, provides information about the density of the neighborhood of each node of the graph. It can be calculated for different neighborhoods representing local or long-term shape information. Given 3D points z3D t,i ,z3D t′,j and a neighborhood k, the geodesic distance is computed as: fgeo(i, j, k, z3D t, z3D t′) =  i+k−1 X l=ikz3D t,l+1 −z3D t,l k− j+k−1 X l=jkz3D t′,l+1 −z3D t′,lk(3.21) where iand jcorrespond to the hidden state xithat associates the feature iof the scene t with the feature jof the scene t′. The neighborhood kof xiin the graph corresponds to all the nodes separated knodes from xi. In our implementation, this function is computed for k∈ {1,2,3}. A similar metric is used to match 3D laser scans by Anguelov et al. (2005). We also use Principal Component Analysis over the dense 3D point cloud that is contained within some spheres centered in the graph nodes (textured points in Figure 3.9(d)). The radius of these spheres is given by the key point scale provided by the feature extractor, such as the SURF detector. The PCA distance is computed as the absolute difference 34 3.3. Loop verification between the variances of the principal components of a dense point cloud zpca t,i in scene t and zpca t′,j in scene t′: fP CA(i, j, zpca t, zpca t′) = zpca t,i −zpca t′,j (3.22) Another way to consider local shape is by computing the difference between the curvatures of the dense point clouds. This value is computed as: fcurv(i, j, zc t, zc t′) = zc t,i −zc t′,j(3.23) where zc=3s3 s1+s2+s3 , and s1≥s2≥s3are the singular values of the point cloud of each node. 2. Visual appearance: These descriptor functions capture how much the local appearance from the points in the image differs for each possible association. We use the feature distance, i.e. the Euclidean distance between the descriptor vectors for each possible association: fdescr(i, j, zdescr t, zdescr t′) =  zdescr t,i −zdescr t′,j  (3.24) Ramos et al. (2008) also include as descriptor functions the distances between the individual dimensions of the descriptor space. We disregard this information because in our training and validations data we did not find a significant improvement in accuracy in spite of the great increase of the size of the weight vector. 3. Pairwise distance: All functions described above are unary, in that they only depend on a single hidden state xiin scene t. In order to generate mutually consistent associations it is necessary to define functions over the edges which relate the hidden states in the CRF to each other. The pairwise distance measures the geometrical consistency between the associations of two hidden states xiand xjand observations zt,i,zt,j from scene tand observations zt′,k and zt′,l in scene t′: f3D pair(i, j, k, l, z3D t, z3D t′) = kz3D t,i −z3D t,j k−kz3D t′,k −z3D t′,lk,(3.25) fI pair(i, j, k, l, zI t, zI t′) = kzI t,i −zI t,jk−kzI t′,k −zI t′,lk.(3.26) The z3D are in metric coordinates for G3D, and zIin pixels for GI. To check the geometrical consistency of the loop closing candidate, we compute the negative log-likelihood (Λ) from the most likely configuration of x(i.e., the maximum a posteriori, or MAP, estimation), as explained in Section A.3, between the scenes at time tand t′, Λt,t′, and compare it with that obtained from the scene in t−∆t, Λt,t−∆t. The negative log-likelihood Λ3D of the MAP association for G3D provides a measure of how similar two scenes are in terms of close range, and ΛIfor GIin terms of far range. Thus, in order to compare how similar the current scene is with the scene in t′, Λt,t′, with respect to how similar the current scene is with the scene in t−∆t, Λt,t−∆t, we use again a normalized similarity score: η3D =Λ3D t,t′ Λ3D t,t−∆t ,(3.27) ηI=ΛI t,t′ ΛI t,t−∆t .(3.28) 35 Chapter 3. Appearance-based loop detection Scores η3D and ηIare compared to α3D and αI, control parameters of the level of similarity demanded, where a smaller αmeans a higher demand. By choosing different parameters for near and far information we can reach a balance between the weight of each source of information. The loop candidates pass the geometrical check if the corresponding scores are below these thresholds. 3.4 Experimental evaluation We conducted different experiments to check the performance of our loop detection algorithm. For that, the first section of our experimental evaluation is devoted to explain the methodology to measure the quality of the results, and to introduce the datasets used. We start evaluating the ability of our proposal to retrieve pairs of image that are valid loop candidates. For that, we compare our system with a simple bag-of-words approach, where only the best candidate match is used, ignoring previous matches. We show the relative merits of using our normalized similarity score ηand the temporal consistency. We also check how different vocabulary configurations (size and source of training images) affect the results. Finally, we compare our approach with all our proposed techniques for geometrical verification with two versions of the state-of-the-art FAB-MAP algorithm (Cummins & Newman 2008, Cummins & Newman 2011). 3.4.1 Methodology In order to evaluate our loop detection system, there are some issues that have to be addressed first, such as how to measure the correctness of the results. Although these aspects are usually assumed to be of general knowledge, little detail is given in the literature. Here, we explain the methodology we followed to evaluate our system. 3.4.1.1 Datasets Dataset Description T (m) R (m) S (m/s) I (px ×px) Bicocca 2009-02-25b Indoors, static 760 113 0.5 640 ×480 Bovisa 2008-10-04 Outdoor, static 1718 208 0.75 640 ×480 Bovisa 2008-10-06 Mixed, dynamic 1892 268 0.88 640 ×480 Malaga 2009 Parking 6L Outdoors, dynamic 1192 162 2.8 1024 ×768 Table 3.1: Datasets used for evaluation. Legend: T, total dataset length; R, revisited length; S, average speed of the robot; I, image size. We evaluated our system with sequences of images taken 1 second apart from three public datasets from the Rawseeds Project (Rawseeds 2007-2009) and with the Malaga parking lot 6L dataset (Blanco et al. 2009), as shown in Table 3.1. We use the first three of them to tune the parameters of our algorithm, whereas the last one is used just for evaluating the final configuration. The Rawseeds data were collected by a robotic platform in different static, dynamic and mixed environments. The camera rig were formed by a stereo Videre Design STH-DCSG-VAR system (cameras on the left and right hand sides), with 18cm of baseline, and a third DCSG camera (on top) completing the trinocular system. These cameras acquired gray-scale images at 640 ×480px. Figure 3.10 shows some image examples. The indoor dataset, Bicocca25b, consists of 26335 trinocular image frames collected during 30 minutes at 15 FPS along a path of some 760m inside a university building where around 113m correspond to fragments of revisited 36 3.4. Experimental evaluation trajectory. We consider this dataset particularly challenging due to the intrinsic difficulty of extracting features in several places with lack of distinctive texture. In addition, the vehicle performs rough rotations in very narrow corners. In this dataset it is possible to identify 6 loops. The outdoor dataset, Bovisa04, consists of 34173 trinocular frames, acquired in 38 minutes. During this time the vehicle travels across the surroundings of a university campus describing a trajectory of 1.718km with 9 main loops identified (5 loops smaller than 50m and 4 loops larger than 100m). The difficulty of this dataset stems from the little variability of the image background. This causes most of the features to lie in distant objects. In addition, part of the trajectory is performed in a rough terrain. The mixed dataset, Bovisa06, contains 32240 trinocular frames acquired in 36 minutes across the same campus than the outdoor dataset, but with a different trajectory. In this dataset, the 1.892km long trajectory goes also inside buildings and describes 8 loop areas. The main difficulty of this dataset is due to the presence of people walking around, which produces some dynamic features which are not reliable to detect loop closures. The Malaga6L dataset (Blanco et al. 2009) is a public dataset with 3474 pairs of images of 1024 ×768px size, acquired at 7.5fps with a stereo AVT Marlin F-131C camera, with 86cm of baseline, mounted on a car. The sequence depicts a parking area with a lot of similar-looking (a) Bicocca25b (b) Bovisa04 (c) Bovisa06 (d) Malaga6L Figure 3.10: Examples of datasets 37 Chapter 3. Appearance-based loop detection trees in a sunny day, under illumination conditions that causes artifacts in the images, and some moving cars. This dataset presents 5 loop areas. 3.4.1.2 Ground truth To measure the correctness of our results we compare them with a ground-truth reference. The Rawseeds datasets are provided with robot trajectory ground truth both for indoor and outdoor scenarios. Indoors, the nature of the ground truth solution relies on a fixed system formed by a bunch of cameras located in the area where the vehicle starts its trajectory and which is several times revisited. From this initial solution, an extended ground-truth solution on the full trajectory was obtained using the pose-graph based optimization algorithm developed by Grisetti et al. (2009). Laser scans are used to build the pose based graph where manual inspection and selection of scans are performed to guarantee a high accurate solution that matches the initial ground truth. Further details are publicly available at Rawseeds (2007-2009). Outdoors, partial ground truth is available from a GPS device with a precision of 0.9m. The Malaga6L dataset also provides a a centimeter-level ground truth from three RTK GPS receivers and one consumergrade USB GPS receiver (Blanco et al. 2009). We use the ground truth trajectory to build a ground truth of images depicting the same place and hence loop closures. For that, we manually create a list of the actual loop closures by comparing the images visually. Since these datasets contain thousands of images taken at high frequency, it is unfeasible to establish a direct connection between single images. Thus, this list is composed of time intervals, where each entry in the list encodes a query interval associated with a matching interval. The matched images depict the same place but are taken some distance apart, which is usually short. When the robot traverses the same place several times, matching intervals may appear more than once in the ground truth. 3.4.1.3 Correctness measure We measure the correctness of the loop detection results with the precision and recall metrics. Precision is defined as the ratio between the number of correct detections and all the detections fired, and recall, as the ratio between the correct detections and all the loop events in the ground truth. Intuitively, precision summarizes the reliability of the answer yielded by the loop detector when it fires a loop closure detection, and recall, how likely it is to detect all the existing loops. A perfect loop detector, or any other classification system, would result in 100% precision and recall; i.e. all the loops, and only actual loops, are correctly detected. A match fired by the loop detector is a pair of query and matching timestamps. To check if it is correct, i.e. a true positive (tp), the ground truth is searched for an interval that contains, or is close to contain, these timestamps. If they are not present in the ground truth, the detection is a false positive (fp). The total number of loop events in the ground truth (#total) is computed as the length of all the query intervals in the ground truth multiplied by the frequency at which the images of the dataset are processed. When a query timestamp is associated to more than one matching timestamp in the ground truth because of multiple traversals, only one of them is considered to compute the amount of loop events. Precision (P) and recall (R) are defined as P=tp tp + fp,(3.29) R=tp tp + fn =tp #total,(3.30) where the false negatives (fn) are those loop events present in the ground truth but not detected as loops by the system. 38 3.4. Experimental evaluation 3.4.2 Loop candidate retrieval We started evaluating how each step of our loop candidate retrieval stage, hereafter “BoW”, affects the correctness of the resulting matching candidates. For this experiment, we created a bag-of-words vocabulary tree based on SURF features with kw= 9 branching factor and Lw= 6 depth levels, yielding around 530K words. For this, we used a small amount of training data: 200 images uniformly distributed in time from another Rawseeds dataset, Bovisa 2008-09-01 (Rawseeds 2007-2009). This is a static dataset that depicts a mix of indoor and outdoor areas. The trajectory of the robot in the Bovisa04 and Bovisa06 datasets has some overlap in location with the dataset used for training; this is not the case with the Bicocca25b dataset, which was collected in a different campus. However, training and testing datasets were acquired one month time apart. The rest of the parameters of the BoW detector are given in Table 3.2. We defined two algorithms to show the benefits of exploiting sequentiality: 1. Simple bag-of-words approach: the matching image that simply maximizes the similarity score is retrieved. 2. Our proposed BoW algorithm with temporal consistency. At the same time, we evaluate each of them both with the raw score sL1and the normalized similarity score ηL1, defined in Section 3.2.1 and Section 3.2.2. As explained earlier, the score sL1is based on the L1-norm distance between two bag-of-words vectors, whereas the score ηL1is the score sL1scaled to the expected value between each input image and their correct matches. In Figure 3.11 we show the precision-recall curves yielded by each configuration as varying the minimum required score α. We can see that our BoW with temporal consistency and score ηL1obtained the highest recall for 100% precision in the datasets. Our BoW with temporal consistency outperforms the simple bag-of-words approach. This is specially noticeable in the outdoor Bovisa04 dataset, where the simple one is not able to achieve 100% precision, so that final results would be hardly reliable. The simple bag-of-words approach failed in this dataset because distant objects, such as buildings, are visible in many images, causing incorrect matches. Requiring temporal consistency reduces these cases because it is unlikely to obtain several consecutive matches with the same wrong place. This makes clear the usefulness of the temporal consistency. Regarding the score, ηL1attained higher recall for full precision than the score sL1both indoors and outdoors. In the indoor dataset, the behavior of both scores with our BoW approach with temporal consistency was similar, but the advantage of ηL1is clear with the simple approach, when just the match with the maximum score is chosen. This shows that ηL1is able to provide more discriminative scores than sL1. Disallow local (τc) 20s Temporal constraint length (τl) 4s Distance between consecutive timestamps (τd) 2s Min. s(vt,vt−∆t) 0.1 Table 3.2: BoW detector parameters for the experiments 39 Chapter 3. Appearance-based loop detection 0.45 0.5 0.55 0.6 0.65 0.7 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 1 Recall Precision Simple (s) Simple (η) BoW (s) BoW (η) (a) Bicocca25b 0 0.05 0.1 0.15 0.2 0.25 0.3 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Recall Precision Simple (s) Simple (η) BoW (s) BoW (η) (b) Bovisa04 Figure 3.11: Precision and recall obtained by our proposed BoW approach and a simple algorithm to select loop candidates, with no further geometrical verification. 3.4.3 Results with CI-Graph SLAM 3.4.3.1 State-of-the-art comparison: FAB-MAP Our proposed loop detection method was compared with the first version of FAB-MAP (Cummins & Newman 2008), a well known state-of-the-art technique, thanks to an implementation made available by the authors. FAB-MAP has proved to be very successful detecting loops in long trajectories for which it delivers very few false positives. The FAB-MAP system represents images with a bag of words and uses a Chow Liu tree (Chow & Liu 1968) to learn offline the words’ co-visibility probability. FAB-MAP has become the gold standard regarding loop detection when using sequences of images with little overlap. Given the current image, FAB-MAP returns the probabilities of being in one of the previous locations or in a new one. The matched image is that which maximizes the probability as long as it reaches a threshold pthat must be set by the user. The FAB-MAP implementation available online provides two vocabularies: one was created from an indoor image sequence and consists of 10000 words; the other contains 10987 words calculated from an outdoor image sequence. As we do with BoW, we disallow local matches occurred to very recent images. For this experiment, we created two new vocabularies from richer training data with SURF features. The first one was created with 1300 images obtained from the same dataset used in Section 3.4.2, with a size of 58K words distributed in a tree of branching factor kw= 9 and Lw= 5 depth levels. Since this vocabulary differs from those used by FAB-MAP, both on size and origin of training images, we also built a second vocabulary. This is used to make a comparison between results yielded by BoW and FAB-MAP when they use vocabularies of similar characteristics. The size of this second vocabulary was kw= 10, Lw= 4, resulting in 10K words, and it was created from 1074 images collected in New College, Oxford, publicly available thanks to the authors of FAB-MAP (Cummins & Newman 2008). We ran both BoW and FAB-MAP in the indoor and outdoor datasets (Bicocca25b and Bovisa04). In order to compare their results, we did not apply any geometrical check to the calculated matches at this moment. Figure 3.12 shows the precision-recall curves obtained by varying the parameters αfor BoW (defined in Section 3.2.2) and pfor FAB-MAP. We also show the curve when using our second vocabulary. In both cases, the shape of the BoW precisionrecall curves is similar either using our Rawseeds vocabulary (kw= 9, Lw= 5) or the Oxford 40 3.4. Experimental evaluation 3.4.4.2 Verification with CRF-Matching and epipolar geometry We then added the geometrical verification stage to BoW and FAB-MAP 2.0 and compared the results of different systems: •BoW with CRF-Matching, described in Section 3.3.3, •FAB-MAP 2.0 with GC, •BoW with GC. We show an example of the results obtained by our BoW+CRF-Matching system in the Bicocca25b dataset in Figure 3.19. These were obtained by varying αand p, with α+fixed to 0.6. For the BoW+CRF-Matching system, we set the α3D and αIparameters of the CRF matcher in order to obtain 100% precision. We performed this test to compare recall with the state of the art. In view of results shown in Figure 3.18, we selected the working value α= 0.15 to accept loop closing candidates. Note that this value of αis far below the values of 0.3 and 0.5 we used in the previous experiments in Section 3.4.3. Our aim is to show that we can relax the loop detection threshold, and find a value suitable for heterogeneous datasets, that can detect more loops, whereas relying on a more robust geometrical verification to disregard the spurious detections that appear in such a case. The rest of the parameters are shown in Table 3.4. The results of FAB-MAP 2.0 over the datasets are shown in Figures 3.20(a), 3.21(a) and 3.22(a) for the default set of parameters plus the geometrical checking with the epipolar constraint, and in Figures 3.20(b), 3.21(b) and 3.22(b) for the modified set of parameters. Please, note that FAB-MAP 2.0 with the modified configuration does not need geometrical verification, since we selected the parameters aiming to obtain no false positives. Again, as expected with Outdoor Indoor Mixed default modified p0.99 0.96 0.5 0.3 P(obs|exist) 039 0.39 0.31 0.37 P(obs|¬exist) 0.05 0.05 0.05 0.05 P(newplace) 0.9 0.9 0.9 0.9 σ0.99 0.99 1.0 1.0 Motion Model 0.8 0.8 0.8 0.6 Blob Resp. Filter 25 25 25 25 Dis. Local 20s 20s 20s 20s Table 3.3: Parameters of FAB-MAP 2.0 for the experiments Indoor Outdoor Mixed Disallow local (τc) 20s 20s 20s Temporal constraint length (τl) 4s 4s 4s Distance between consecutive timestamps (τd) 2s 2s 2s Min. s(vt,vt−∆t) 0.1 0.1 0.1 Candidate min. threshold (α) 0.15 0.15 0.15 Candidate max. threshold (α+) 0.6 0.6 0.6 CRF 3D Likelihood threshold (α3D) 1 1.5 1.5 CRF ILikelihood threshold (αI) 1.3 1.7 1.7 Table 3.4: Parameters of BoW + CRF-Matching for the experiments 47 Chapter 3. Appearance-based loop detection 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.4 0.5 0.6 0.7 0.8 0.9 1 Recall Precision BoW FabMap 2.0, default FabMap 2.0, modified (a) Bicocca25b 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 BoW FabMap 2.0, default FabMap 2.0, modified (b) Bovisa04 0 0.1 0.2 0.3 0.4 0.5 0.8 0.82 0.84 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1 BoW FabMap 2.0, default FabMap 2.0, modified (c) Bovisa06 Figure 3.18: Precision and recall without geometrical check of BoW and FAB-MAP 2.0 with two parameter sets. the modified parameters, FAB-MAP 2.0 obtained greater recall at full precision than with the parameters by default, although, some loop closures were not detected. We detail some cases: in the indoor Bicocca25b dataset, Figure 3.20(a), the big area on the beginning of the map (startend), especially important in the experiment because if no loop is detected in that area, a SLAM algorithm could hardly build a correct map after having traversed such a long path (around 300 metres). Outdoors, in Bovisa04, as shown in Figures 3.21(a) and 3.21(b), the biggest loop was missed in the starting and final point of the experiment, in the marked area (O1) in the map. An example of a false negative in this area is shown in Figure 3.24(a). This dataset is challenging due to the illumination and blur present in the images. And this entails an added difficulty for FAB-MAP since the significant overlap of distant objects between consecutive images decreases its discriminative ability, as we showed in previous section. For the experiment in the dynamic mixed environment, Bovisa06, important loop closures were missed again, e.g. M1 and M2 areas in Figure 3.22(a). Examples of those false negative cases are shown in Figures 3.24(b) and 3.24(c). In the false negative cases that we show in Figure 3.24, both configurations of FAB-MAP 2.0 reported a probability of new place greater than 0.999. 48 3.4. Experimental evaluation 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.85 0.9 0.95 1 Recall Precision Our System BoW + GC FabMap 2.0, modified FabMap 2.0, default +GC Figure 3.19: Precision-recall curve of our BoW + CRF-Matching system for the Bicocca25b dataset. We also show FAB-MAP 2.0 and our BoW stage with epipolar constraint (GC) as verification. Note that FAB-MAP 2.0 with the modified configuration needs no GC. Working points are marked in each curve, according to Table 3.3 and Table 3.4. In order to show the improvements of the CRF-Matching verification stage, we checked the candidates given by BoW with the same GC technique we described in Section 3.3.1. The results are shown in Figures 3.20(c), 3.21(c) and 3.22(c). In Figure 3.20(c) all the loop closure areas were detected but with too many false positives due to the perceptual aliasing (see Figure 3.23); this is disastrous for any SLAM algorithm. As we previously showed in Figure 3.15, we can eliminate the false positive cases by imposing a more demanding value α= 0.5 and applying the epipolar constraint to more than one camera. In the outdoor and mixed datasets the precision was 100%, sacrificing recall and, more important, the detection of loop closure areas. As we can see in Figure 3.19 we can tune the parameters of BoW+GC to attain full precision, but at the cost of sacrificing recall. This also makes the performance of this system not good and stable across environments and conditions. The results of the BoW+CRF-Matching system over the datasets are shown in Figures 3.20(d), 3.21(d) and 3.22(d), and the comparative statistics of all experiments is made in Table 3.5. In the indoor experiment we can detect all the loop closure areas at 100% precision. In the outdoor and mixed datasets we keep full precision, higher recall level and most of the loop closure areas detected. Our system detected successfully the loops of Figure 3.24 as true positives. The three cases shown were verified by the CRF stage. Our CRF matcher reports the follow ηscores: in O1, Figure 3.24(a), η3D = 1.24 and ηI= 1.37, in M1, Figure 3.24(b), η3D = 0.4 and ηI= 1.67, and in M2, Figure 3.24(c), η3D = 1.29 and ηI= 1.24. Note that with the corresponding α3D and αI parameters for indoors, such cases would be rejected. Furthermore, our CRF matcher is robust against perceptual aliasing. For instance, the false positives obtained with the geometrical checking in the indoor sequence, see Figure 3.23, was correctly discarded. In the case of F1, Figure 3.23(a), our both graphs of the CRF matcher, G3D and GI, rejected it with η3D = 1.45 and ηI= 1.79. And in F2, Figure 3.23(b), our CRF matcher rejected it by the far information coded in GI, with η3D = 0.95 and ηI= 1.47. With the parameters by default of FAB-MAP 2.0 we cannot obtain full precision in the indoor dataset, even with p= 0.99. As explained in Figure 3.23(c), we have to verify the loop closures detected with the GC to attain full precision, obtaining lowest recall in the three datasets. With 49 Chapter 3. Appearance-based loop detection (a) FAB-MAP 2.0 (default) + GC (b) FAB-MAP 2.0 (modified) (c) BoW + GC (d) BoW + CRF-Matching Figure 3.20: Loops detected by each of the methods in the Bicocca25b dataset. Black lines and triangles denote the trajectory of the robot; light green lines, actual loops, deep blue lines denote true loops detected, and light red lines denote false loops detected. In Figure 3.23 we show the false positive cases F1 and F2. 50 3.4. Experimental evaluation (a) FAB-MAP 2.0 (default) + GC (b) FAB-MAP 2.0 (modified) (c) BoW + GC (d) BoW + CRF-Matching Figure 3.21: Loops detected by each of the methods in the Bovisa04 dataset. Black lines and triangles denote the trajectory of the robot; light green lines, actual loops, deep blue lines denote true loops detected. In Figure 3.24 we show the false negative case O1. 51 Chapter 3. Appearance-based loop detection (a) FAB-MAP 2.0 (default) + GC (b) FAB-MAP 2.0 (modified) (c) BoW + GC (d) BoW + CRF-Matching Figure 3.22: Loops detected by each of the methods in the Bovisa06 dataset. Black lines and triangles denote the trajectory of the robot; light green lines, actual loops, deep blue lines denote true loops detected. In Figure 3.24 we show the false negative cases M1 and M2. 52 3.4. Experimental evaluation (a) F1 (b) F2 (c) False positive of FAB-MAP 2.0 (default) rejected by the GC. Figure 3.23: False positive cases obtained by BoW plus GC in the Bicocca25b dataset in (a) and (b). In (c), two different corridors make FAB-MAP 2.0 produce a false positive (p= 0.9989) with the default parameters. However, it is correctly rejected by the geometrical check. 53 Chapter 3. Appearance-based loop detection (a) O1 (b) M1 (c) M2 Figure 3.24: False negatives in the Bovisa04 and Bovisa06 datasets that our method can successfully detect but FAB-MAP 2.0 misses. FAB-MAP 2.0 sets query image of case (a) as new place with a probability of 0.99947; of (b) with 0.99997 and 0.99902 with the default and modified set of parameters respectively, and of (c) with 1.0 and 0.9993. These scenes correspond to the biggest loops in the trajectories. 54 3.4. Experimental evaluation Precision Recall Loop zones found/actual Bicocca25b FAB-MAP 2.0 def. + GC 100% 14.1% 2/6 FAB-MAP 2.0 mod. 100% 30.6% 2/6 BoW + GC 79.8% 76.3% 6/6 BoW + CRF-Matching 100% 59.1% 6/6 Bovisa04 FAB-MAP 2.0 def. + GC 100% 0.7% 2/9 FAB-MAP 2.0 mod. 100% 3.3% 2/9 BoW + GC 100% 7.0% 3/9 BoW + CRF-Matching 100% 11.15% 6/9 Bovisa06 FAB-MAP 2.0 def. + GC 100% 3.7% 1/8 FAB-MAP 2.0 mod. 100% 19.9% 3/8 BoW + GC 100% 29.9% 4/8 BoW + CRF-Matching 100% 32.8% 5/8 Table 3.5: Results for Rawseeds datasets the modified configuration, we tuned the parameters of FAB-MAP 2.0 aiming to maximize the precision. With this approach we obtained 100% precision in the Bicocca25b, Bovisa04 and Bovisa06 datasets with 30.6% recall and 2/6 loop areas detected, 3.3% recall and 3/9 areas, and 19.9% recall and 3/8 areas, respectively. We also tried to tune the parameters of FAB-MAP 2.0 to maximize recall without paying attention to the precision, which can be improved later by using the geometrical constraint. With that approach, we could attain 100% precision in the Bovisa04 and Bovisa06 datasets, but false positives remained indoors, obtaining 75% precision only. As in the case of BoW+GC shown in Table 3.5, the geometrical check was not able to filter out all the incorrect loop candidates suffering from perceptual aliasing. In the mixed dataset, Bovisa06, the recall obtained, 15%, was lower than that observed with the other FAB-MAP 2.0 configuration. The same situation occurred outdoors, in Bovisa04, except for unrealistically low thresholds, like p= 0.3, that yielded a recall up to 5%. No hand-tuning test After obtaining the best results in the different datasets of the Rawseeds Project comparatively, we tested our BoW+CRF-Matching system over a different dataset, the Malaga parking lot 6 (Blanco et al. 2009). As in the previous case, we carry out the place recognition task at 1fps. This dataset, as the indoor one above, was collected in a completely different location from the Precision Recall Loop zones found/actual FAB-MAP 2.0 def. + GC 100% 67.9% 4/5 FAB-MAP 2.0 mod. 41.5% 81.2% 4/5 BoW + CRF-Matching 100% 41.8% 4/5 Table 3.6: Results for the Malaga6L dataset 55 Chapter 3. Appearance-based loop detection (a) BoW (b) BoW + CRF-Matching (c) FAB-MAP 2.0 (d) FAB-MAP 2.0 (default) + GC Figure 3.25: Loops detected by our system and FAB-MAP 2.0 in the Malaga6L dataset. Black lines and triangles denote the trajectory of the robot; light green lines, actual loops. In (a) high confidence detections (light blue) are accepted and unclear detections (magenta) are subject to verification. In (c) detections with p= 0.99 (default) are in dashed light blue, detections with p= 0.96 (mod.) are magenta. Detections with p= 0.99 which are verified with GC are shown in (d). In (b) and (d), deep blue lines denote true loops detected. 56 4.2. Bags of binary words according to the training data. This training is done in an offline stage and a static decision tree is used later. The cornerness of FAST key points is valued with a score defined as the maximum sum of the absolute difference between the set of brighter or darker pixels in the contiguous arc and the center pixel. Intuitively, this score conveys a sense of the persistence of the corner, and it is used to perform non-maxima suppression and ignore those corners that are adjacent to others expected to be more reliable. Since only a few pixels need checking, obtaining FAST key points requires very little time. Rosten & Drummond (2006) reported 1.33ms in a 2.6GHz computer to extract 500 features, including the non-maxima suppression step, proving successful for real-time applications (Gauglitz et al. 2011). 4.2.2 Binary robust independent elementary features We combine FAST key points with binary robust independent elementary features (BRIEF). For each FAST key point, we draw a square patch around them and compute a BRIEF descriptor. The BRIEF descriptor of an image patch is a binary vector where each bit is the result of an intensity comparison between two of the pixels of the patch. The patches are previously smoothed with a Gaussian kernel to reduce noise. Given beforehand the size of the patch, Sb×Sb, the pairs of pixels to test are randomly selected in an offline stage. In addition to Sb, we must set the parameter Lb: the number of tests to perform (i.e., the length of the descriptor). For a point pin an image, its BRIEF descriptor vector B(p) is given by: Bi(p) = 1 if I(p+ai)< I(p+bi) 0 otherwise ∀i∈[1, Lb] (4.1) where Bi(p) is the i-th bit of the descriptor, I(·) the intensity of the pixel in the smoothed image, and aiand bithe 2D offset of the i-th test point with respect to the center of the patch, with value in −Sb 2...Sb 2×−Sb 2. . . Sb 2, randomly selected in advance. Note that this descriptor does not need training, just an offline stage to select random points that hardly takes time. The original BRIEF descriptor proposed by Calonder, Lepetit, Strecha & Fua (2010) selects each coordinate of the test points aiand biaccording to a normal distribution N(0,1 25 S2 b). However, we found that using short test pairs, i.e. offsets which are close in the image space, yielded better results (Section 4.4.2). We select each coordinate jof these pairs by sampling the distributions aj i∼ N(0,1 25 S2 b) and bj i∼ N(aj i,4 625 S2 b). Note that this approach was also proposed by Calonder, Lepetit, Strecha & Fua (2010), but not used in their final experiments. For the descriptor length and the patch size, we chose Lb= 256 and Sb= 48, because they resulted in a good compromise between distinctiveness and computation time. The main advantage of BRIEF descriptors is that they are very fast to compute and to compare. For example, Calonder, Lepetit, Strecha & Fua (2010) reported 17.3µs per keypoint when Lb= 256 bits. Since one of these descriptors is just a vector of bits, measuring the distance between two vectors can be conveniently done with the Hamming distance: by counting the amount of different bits between them, which is implemented by counting the number of ones after an xor operation. This is more suitable in this case than calculating the Euclidean distance, as usually done with SIFT or SURF descriptors, composed of floating-point values. Note however that unlike SIFT or SURF, no key point orientation or scale is computed at any stage, so that these descriptors are not so robust before image transforms. As we show in our experiments, we can do without that invariance in many cases and still obtain a high recall at full precision regarding loop detection. 63 Chapter 4. Real-time loop detection 4.2.3 Hierarchical binary vocabulary tree Unlike the SURF case, with BRIEF descriptors we discretize now a binary descriptor space, creating a more compact vocabulary. This vocabulary is structured again as a tree by performing hierarchical k-medians clustering with the k-means++ seeding. This algorithm computes the median value of each dimension of the descriptor vectors individually to obtain centroids, which in the binary space is equivalent to set the most populated value of each dimension. When there is the same number of one and zero values, the resulting mathematical median is not binary, so that an arbitrary value of 0 is set. Unlike real spaces, the quantization of binary spaces is prone to produce several clusters which are equidistant to some points, as depicted in Figure 4.2. This is detrimental for the nearest neighbor problem, since near points in the space can be associated to different clusters, as Trzcinski et al. (2012) noticed. Nevertheless, our experimental evaluation shows that this performance loss is not relevant, even nonexistent in some cases, in the loop detection problem, when we compare the results with a SURF vocabulary. Binary words are also given an idf weight during the creation of the vocabulary. When a binary descriptor is converted into a word, it traverses the tree by selecting the nodes that minimize the Hamming distance, that is to say, by selecting at each level the node with fewest dissimilar bits. After the conversion, the weight of words obtained from an image are complemented to obtain the tf–idf weight (cf. Section 3.1.3). The tf-idf values allow bag-of-words vectors to be compared with the L1distance again, yielding the normalized similarity score ηL1 when exploiting video sequentiality during the loop candidate retrieval. Figure 4.2: Thick boundary problem in the binary space. Unlike Euclidean spaces, the borders between two clusters are not smoothly defined in a Hamming space. In this case, given clusters centered in uand v, all the points in the rectangular area are equidistant to both of them, so they may belong to any. Credit: Trzcinski et al. (2012). 64 4.3. Video-rate loop retrieval and verification 4.3 Video-rate loop retrieval and verification We improve our loop detection approach with the compact features that result by combining FAST key points with BRIEF descriptors. The basic aspects of the algorithm are those presented in Chapter 3, however, we define now a visual vocabulary with binary words, clustering a binary space, and introduce the notion of matching image grouping to avoid images acquired in the same place from clashing when the database is queried. Furthermore, we introduce a direct index to efficiently compute feature correspondences. All these additions allow us to increase the working frequency of our loop detector. 4.3.1 Temporal consistency for groups of matches The appearance model of an image is again represented with a bag-of-words vector v, and the resemblance between images in a sequence is measured with the normalized similarity score ηL1. One of the difficulties that arise when querying the image database to look for candidate images is that there is not a single peak in the set of matching ηL1scores, but several highscored matches. These are mainly due to consecutive images acquired in the same place when the robot moves slowly, or when far-off objects are present for a long time. Selecting the matching image that maximizes ηL1in those cases can cause the temporal constraint to fail. Consider the example given in Figure 4.3, supposing the acquisition of images at every ∆t= 1 second. Query images at timestamps tand t−1 are shown in the column on the left, and the matched images retrieved from the database, which are close in time, on the right. Matched images are from left to right in descending order of ηL1score. In this example, all the matched images are valid since they depict the same place as the query images, but obtain different scores Figure 4.3: Example of false rejection of the temporal constraint. Images are acquired at every ∆t= 1 second, and matches are from left to right in descending order of ηL1score. When matches that maximize the ηL1score for each query are selected, i.e. ht, tiiand ht−1, ti−3i, the temporal consistency condition fails, since ti−(ti−3) > τd= 2s. Nevertheless, if the match ht, ti−1iis selected instead, the temporal consistency condition holds and the loop candidate is not falsely rejected. 65 Chapter 4. Real-time loop detection because of slight variations in the image due to camera pose, illumination artifacts or other factors. According to our original algorithm, if we pick out just the match that obtains the highest ηL1score, we will consider matches ht, tiiand ht−1, ti−3i. However, the difference between the selected matches is not within the temporal constraint threshold, i.e. ti−(ti−3) > τd= 2s, and the temporal consistency test fails. On the other hand, if the match ht, ti−1iis selected instead, which is valid since images at tiand ti−1 depict the same scene, the temporal consistency condition holds and the loop candidate is not falsely rejected. Note that this problem is aggravated when the time between consecutive acquired images ∆tis lower. To solve this issue and to prevent images that are close in time to compete among them when the database is queried, we group them into islands and treat them as only one match. We use the notation Tito represent a set of timestamps {tni,...,tmi},Tifor the time interval [min (t∈ Ti),max (t∈ Ti)], and VTifor an island that groups together the matches with entries vtni, ..., vtmi. Therefore, several matches hvt,vtnii, ..., hvt,vtmiiare converted into a single match hvt,VTiiif the gaps between consecutive timestamps in tni, ..., tmiare small. The islands are also ranked according to a score H: H(vt,VTi) = mi X j=ni ηL1(vt,vtj) (4.2) The island with the highest score is selected as matching group and continue to the temporal consistency step. Besides avoiding clashes between consecutive images, the islands can help establish correct matches. If Itand It′represent a real loop closure, Itis very likely to be similar also to It′±∆t,It′±2∆t, . . . , producing long islands. Since we define Has the sum of scores ηL1, the Hscore favors matches with long islands as well. After obtaining the best matching island VT′, we check it for temporal consistency with previous queries, extending the temporal constraint applied in Section 3.2.2 to support islands. The match hvt,VT′imust be consistent with kprevious matches hvt−∆t,VT1i, ..., hvt−k∆t,VTki such that intervals T′,T1,T2, ..., Tkare close to overlap. In the example given above in Figure 4.3, the set T′is composed of timestamps {ti, ti−1, ti−4}, and T1, of {ti−3}; since there is overlap between T′= [ti−4, ti] and T1= [ti−3, ti−3], matches hvt,VT′iand hvt−1,VT1i are consistent. If an island passes the temporal constraint, we keep only the match hvt,vt′i, for the t′∈ T′that maximizes the score ηL1, and consider it a loop candidate, which has to be finally accepted by the geometrical verification stage. 4.3.2 Direct index The visual vocabulary and the inverted index are often the only structures used in the bag-ofwords approach for searching for images and performing loop detection. As a novelty in this general approach, we also make use of a direct index to conveniently store the features of each image. Complementary to the inverted index, which maps words with the images in which they are present, a direct index stores for each image the words it contains. The main functionality of a direct index is to retrieve the content of a database entry, but we use it for other purpose. We separate the nodes of the vocabulary tree according to their level lof clustering coarseness, starting at leaves, with level l= 0, and finishing in the root, l=Lw. For each image It, we store in the direct index the nodes at a certain level lthat are ancestors of the words present in It, as well as the list of local features ftj associated to each node. Thus, instead of words, we fill the direct index with pairs of any node of the vocabulary tree and lists of local image features. This is illustrated by Figure 4.4. We denote Dlthe direct index created for nodes at level l, and Dl(t) = {hi1,Ft,i1i,hi2,Ft,i2i, . . . }the direct index entry for image It, 66 4.3. Video-rate loop retrieval and verification Figure 4.4: Example of vocabulary tree and direct index for level l= 1. The direct index stores the features of the images in the database and their associated nodes at coarseness level lin the vocabulary tree. which is an ordered set of pairs of node indexes (i1< i2< . . . ) and sets of local features of It associated to those nodes (Ft,i1,Ft,i2, . . . ). We take advantage of the direct index and the bag-of-words tree to use them as a means to approximate nearest neighbors in the BRIEF descriptor space. This is useful during the geometrical verification stage, when corresponding points are needed. The direct index allows to speed up the geometrical verification by computing correspondences only between those features that belong to the same words, or to words with common ancestors at level l. The direct index is updated when a new image is added to the database, and accessed when a candidate matching is obtained and geometrical check is necessary. 4.3.3 Computation of corresponding points All the geometrical verification algorithms proposed in the previous chapter need to compute correspondences between images. The simplest method needs at least corresponding points between the loop candidate images Itand It′. To compute these correspondences, we must obtain all the pairwise distances between feature descriptors of the query image and those of the matched one. There are several approaches to perform this. The easiest and slowest one is the exhaustive search, that consists in measuring the distance of each feature of Itto the features of It′in the descriptor space, to select correspondences later according to the neighbor-ratio condition (Lowe 2004). This is a Θ(n2) operation in the number of features per image, where Θ stands for exact asymptotically bound. A second technique consists in calculating approximate nearest neighbors by arranging the descriptor vectors of images individually in randomized k-d trees (Silpa-Anan & Hartley 2008). A k-d tree (Friedman et al. 1977) is a binary tree that arranges k-dimensional data in a hierarchical manner by separating them by one of the dimensions at each tree level. In a randomized k-d tree the chosen dimension is a random one from those that present the greatest variance; in contrast, the original k-d tree algorithm selects the maximum always. In order to approximate neighbors to compute corresponding features, several randomized k-d trees are built with their descriptors, obtaining one leaf node per feature. Then, given an input descriptor, the trees are traversed from the root by selecting child nodes according to the corresponding dimension. This is done at the same time for all the trees, maintaining a priority queue of visited nodes to skip those with 67 Chapter 4. Real-time loop detection Algorithm 2: Correspondence computation with direct index Input : Timestamps of candidate loop images t,t′, Direct index Dlfor tree level l, s.t. Dl(t) = {hi1,Ft,i1i,hi2,Ft,i2i, . . . } Output: Set Cof corresponding features between images at tand t′ C ← ∅1 i←firstNode(Dl(t))2 j←firstNode(Dl(t′))3 while neither inor jreach the end of Dl(t) nor Dl(t′)do4 if i=jthen5 C ← C ∪correspondences(Ft,i,Ft′,j)6 i←nextNode(Dl(t), i)7 j←nextNode(Dl(t′), j)8 else if i < j then9 i←nextNode(Dl(t), i)10 else if i > j then11 j←nextNode(Dl(t′), j)12 end13 end14 return C15 higher distance than nodes in other trees. When a leaf node is reached, the feature represented by this leaf is taken as the first best neighbor. The search is then refined by checking for nearer neighbors in other leaf nodes. Following the k-d tree idea, we take advantage of our single bag-of-words vocabulary tree and reuse it to approximate nearest neighbors, for any image, by exploiting the role of the direct index. To obtain correspondences between Itand It′, we look up them in the direct index and perform comparisons only between those features that are associated to the same nodes at level lin the vocabulary tree. This condition speeds up the correspondence computation because we expect features that are close in the descriptor space to follow a similar path along the vocabulary tree when they are clustered as words. Since corresponding features do not always result in the same word, we use the parameter l, which is fixed beforehand and entails a trade-off between the number of correspondences obtained between Itand It′and the time consumed for this purpose. When l= 0, only features belonging to the same word are compared, so that the highest speed-up is achieved, but fewer correspondences can be obtained. This makes the recall of the complete loop detection process decrease due to some correct loops being rejected because of the lack of corresponding points. On the other hand, when l=Lw, recall is not affected but execution time is not improved either. Since direct index entries are implemented as sets ordered by node indexes, traversing the common nodes of two entries is very fast. Algorithm 2 outlines this process to compute correspondences between features of images Itand It′, where function correspondences accounts for equation (3.12). 4.4 Experimental evaluation We conducted several experiments of our current approach, including a detailed analysis of the relative merits of the different parts in our algorithm. We present comparisons between the effectiveness of BRIEF and two versions of SURF features, the descriptor most used for loop 68 4.4. Experimental evaluation closing. We also analyze the performance of the temporal consistency test when increasing the working frequency, and the impact of the direct index to compute correspondences for a simple geometrical verification based on the monocular epipolar constraint. We then present the results achieved by our technique after evaluating it in seven public datasets with 0.7–4Km long trajectories, and compare it with our previous proposal and the FAB-MAP 2.0 software. We demonstrate that we can run the whole loop detection procedure, including the feature extraction, in 52ms in 26300 images (22ms on average), outperforming previous techniques by more than one order of magnitude. 4.4.1 Methodology 4.4.1.1 Datasets Dataset Description C T (m) R (m) S (m/s) I (px ×px) Bicocca 2009-02-25b Indoors, static F 760 113 0.5 640 ×480 Bovisa 2008-10-04 Outdoor, static F 1718 208 0.75 640 ×480 Bovisa 2008-10-06 Mixed, dynamic F 1892 268 0.88 640 ×480 New College Outdoors, dynamic F 2260 1570 1.5 512 ×384 Ford Campus 2 Urban, ∼dynamic F 4004 280 6.9 600 ×1600 Malaga 2009 Parking 6L Outdoors, ∼dynamic F 1192 162 2.8 1024 ×768 City Center Urban, dynamic L 2025 801 - 640 ×480 Table 4.1: Datasets used for evaluation. Legend: C, (F)rontal or (L)ateral camera; T, total dataset length; R, revisited length; S, average speed of the robot; I, image size. We tested our enhanced loop detector in seven datasets, four of them already presented in the experimental evaluation section of the previous chapter. The three additional datasets used here are the New College campus (Smith et al. 2009), the Ford Campus 2 (Pandey et al. 2011) and the sequence City Center used by Cummins & Newman (2008). Table 4.1 summarizes them and Figure 4.5 shows some image examples. The Bicocca25b, Bovisa04 and Bovisa06 datasets belong to the Rawseeds project (Rawseeds 2007-2009), and the Malaga6L (Blanco et al. 2009) dataset was collected with a camera on a (a) NewCollege (b) Ford2 (c) CityCenter Figure 4.5: Examples of datasets 69 Chapter 4. Real-time loop detection car, in a parking area, as we detailed in Section 3.4.1. NewCollege (Smith et al. 2009) is a wellknown challenging dataset, composed of stereo images captured at 20Hz along a 2.2Km path through a college’s grounds and adjoining parks. It presents a long trajectory, with some people walking around and similar-looking places revisited several times whose appearance is likely to produce perceptual aliasing. The imagery of Ford2 (Pandey et al. 2011) was collected by a Point Grey Ladybug 3 omnidirectional camera system mounted on a car while driving around the Ford Research campus in Dearborn, Michigan during November-December 2009. We used the images from the frontal camera only. Its difficulty lies in the high speed of the platform and the restrictive horizontal field of view of the images, which produces views with mainly distant features. These six datasets provide images acquired at high frequency (between 7.5 and 20Hz). Unlike them, CityCenter (Cummins & Newman 2008) is a collection of images gathered along a 2Km path at low frequency and perpendicular to the motion of the robot. This makes consecutive images overlap very little, so they can be considered as a set of disjoint images instead of a sequence. This may be detrimental to the normalization of the score ηL1of our method when the database is queried. 4.4.1.2 Training and evaluation datasets The behavior of loop detection systems is sensitive to their parameters. It is common practice in the literature to tune system parameters according to the datasets where the system is evaluated. Nevertheless, to test our final loop detection system, we decided to use different data to choose the configuration of our algorithm and to evaluate it, in order to demonstrate the robustness of our approach. We then separate the datasets shown in Table 4.1 into two groups. We use five of them (Bicocca25b, Bovisa04, Bovisa06, NewCollege and Ford2) as training datasets to find the best set of parameters of our algorithm. These present heterogeneous environments with many difficulties: lack of natural features indoors, perceptual aliasing, dynamic entities, distant scenes, narrow field of view, etc. The other two datasets (CityCentre and Malaga6L) are used as evaluation data to validate our final configuration. In these cases, we only use our algorithm as a black box with a predefined configuration. 4.4.1.3 Settings To use our algorithm we defined some settings that remained the same throughout all our experiments. A single vocabulary tree was used to process all the datasets. This was built with kw= 10 branches and Lw= 6 depth levels, which yielded one million words. Its training was carried out with 9M features acquired from 10K images of another dataset from (Rawseeds 2007-2009) (Bovisa 2008-09-01). In all the experiments, we used a threshold of 10 units in the response function of FAST, and 500 in the Hessian response of SURF. For each processed image, we kept only the 300 features with highest response. 4.4.2 Selecting BRIEF parameters We ran several tests to compare the performance of BRIEF by varying the descriptor length Lb, the patch size Sband the method to select the test pairs aand bfrom equation (4.1). We tried two methods to choose the test pairs. The first one consisted in choosing both aand b∈R2 from a normal distribution N2(0,1 25 S2 b), and the second one, in choosing close pairs such that a=N2(0,1 25 S2 b), b=N2(a,4 625 S2 b). To do this test, we took several images (between 14 and 23) of three different scenes. By means of bundle adjustment (Triggs et al. 2000), we reconstructed the 3D geometry of the scenes 70 4.4. Experimental evaluation 0 100 200 300 400 500 600 700 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Descriptor length (bits) Precision / Recall (per one) Precision of BRIEF with close pairs Recall of BRIEF with close pairs Precision of BRIEF Recall of BRIEF (a) Scene 1 0 100 200 300 400 500 600 700 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Descriptor length (bits) Precision / Recall (per one) Precision of BRIEF with close pairs Recall of BRIEF with close pairs Precision of BRIEF Recall of BRIEF (b) Scene 2 0 100 200 300 400 500 600 700 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Descriptor length (bits) Precision / Recall (per one) Precision of BRIEF with close pairs Recall of BRIEF with close pairs Precision of BRIEF Recall of BRIEF (c) Scene 3 Figure 4.6: Precision and recall in 3 test scenes of BRIEF and BRIEF with close pairs for several descriptor length Lbvalues, with patch size Sb= 48. 71 Chapter 4. Real-time loop detection and obtained the ground-truth correspondences of every pair of images. We computed both versions of the BRIEF descriptor for patches of size Sb= 24, 48, 64 and 80 pixels around a dense set of FAST key points in each image, and matched them. A match was set if the distance between two descriptors was minimum, and the ratio between this and the distance to the second closest descriptor was lower than a threshold. Due to the random nature of the descriptor, we repeated this for 5 different test pair patterns. In Figure 4.6 we show the average precision and recall against the length of the descriptor when Sb= 48 of BRIEF and BRIEF with close pairs. The other patch sizes showed the same relation between both techniques, but Sb= 48 exhibited better results. We can see that the precision of BRIEF with close pairs is always higher than that of BRIEF with more general pairs for the same level of recall. This suggests the locality of the pairs provides more distinctiveness to the descriptor, and supports the idea behind new features such as the fast retina key points (FREAK) (Alahi et al. 2012), which build binary descriptors by comparing image intensities in areas which are smaller the closer to the key point center. We also see that precision and recall improve when the number of pairs increases, up to some length. We finally chose BRIEF with close pairs, descriptor length Lb= 256 and patch size Sb= 48 pixels, for the rest of the experiments. 4.4.3 BRIEF and SURF effectiveness SURF features are a common choice for loop detection (Cummins & Newman 2011, Paul & Newman 2010, Callmer et al. 2008). A BRIEF descriptor encodes much less information than a SURF descriptor, since BRIEF is not scale or rotation invariant. In order to check if BRIEF is reliable enough to perform loop detection, we compared its effectiveness with that of SURF. We started by comparing our current loop detection system with that we presented and evaluated with SURF in the previous chapter, on the same training datasets: Bicocca25b, Bovisa04 and Bovisa06. For that, we processed their image sequences at f= 1Hz, deactivated the geometrical verification, fixed the required temporal consistency matches kto 3 and varied the value of the normalized similarity threshold αto obtain the precision-recall curves shown in Figure 4.7. On the left, we show the results of our system with FAST+BRIEF features, and on the right, the results presented in Section 3.4.4 that we obtained with SURF. We see that our system with FAST+BRIEF features performed very well in these three datasets, even without (a) FAST + BRIEF (b) SURF Figure 4.7: Precision-recall curves for several values of αand without geometrical checking. On the left, our current method using FAST+BRIEF, with the working point α= 0.3 highlighted, and on the right, our previous algorithm using SURF on the same datasets. BRIEF features attain similar results than SURF, but require much less computational resources. 72 4.4. Experimental evaluation 4.4.6 Execution time To measure the execution time, we ran our system in the NewCollege dataset with k= 3, α= 0.3 and DI2. By setting the working frequency to f= 2 Hz, a total of 5266 images were processed, yielding a system execution time of 16 ms per image on average and a peak of less than 38 ms. However, in order to test the scalability of the system, we set the frequency to f= 10 Hz and obtained 26292 images. Even with k= 3, the system yielded no false positives. This shows that the behavior of the temporal consistency parameter kis stable even for high frequencies. The execution time consumed per image in that case is shown in Figure 4.13. This was measured on a Intel Core i7 @ 2.67GHz machine. We also show in Table 4.3 the required time of each stage for this amount of images. The features time involves computing FAST key points and removing those with low corner response when there are too many, as well as smoothing the image with a Gaussian kernel and computing BRIEF descriptors. The bag-of-words time is split into four steps: the conversion of image features into a bag-of-words vector, the database query to retrieve similar images, the creation and matching of islands, and the insertion of the current image into the database (this also involves updating the direct and inverse indexes). The verification time includes both computing correspondences between the matching images, by means of the direct index, and the RANSAC loop to calculate fundamental matrices. We see that all the steps are very fast, including extracting the features and the maintenance of the direct and inverse indexes. This allows to obtain a system that runs in 22ms per image, with a peak of less than 52ms. The feature extraction stage presents the highest execution time; most of it, due to the overhead produced when there are too many features and only the best 300 ones must be considered. Even so, we have achieved a reduction of more than one order of magnitude with respect to other features, such as SIFT or SURF, removing the bottleneck of these loop closure detection algorithms. In the bag-of-words stage, the required time of managing the islands and the indexes is negligible, and the conversion of image features into bag-of-words vectors takes as long as the database query. Its execution time depends on the number of features and the size of the vocabulary. We could reduce it by using a smaller vocabulary, since we are using a relatively big one (1M words, instead of 10–60K as used by other authors, as Paul & Newman (2010)). However, we found that a big vocabulary produces more sparse inverse indexes associated to words. Therefore, when querying, fewer database entries must be traversed to obtain the results. This reduces the execution time strikingly when querying, trading off, by far, the time required when converting a new image. We conclude that big vocabularies can improve the computation time when using large image collections. Furthermore, note that querying a database with more than 26K images takes 9 ms only, suggesting this step scales well with tens of thousands images. The geometrical verification exhibits a long execution time in the worst case, but as we saw in the previous section, this rarely occurs, whereas the 75% of the cases require less than 1.6ms. Our results show that we can reliably detect loops against databases with 26K images in 52ms (22ms on average). This represents an improvement of one order of magnitude with respect to the 300–700ms required by algorithms based on SIFT or SURF, as our system presented in Chapter 3, or the proposals by Cummins & Newman (2011), Paul & Newman (2010) or Angeli et al. (2008). For example, the state-of-the-art algorithm FAB-MAP 2.0 (Cummins & Newman 2011) needs 423ms for extracting SURF, 60ms for conversion into bag of words, 10ms for retrieving matching candidates against 25K images, and 120ms (worst case) for RANSAC geometric verification. Our algorithm also outperforms the extremely efficient loop detector developed by Konolige et al. (2010), based on compact randomized tree signatures. According to their figure 6, the method requires around 300ms to perform the complete loop detection against a database with 4K images. 79 Chapter 4. Real-time loop detection 5000 10000 15000 20000 25000 0 10 20 30 40 50 Images Execution time (ms) Whole system Features Bag of words Verification Figure 4.13: Execution time in NewCollege with 26292 images. Execution time (ms/query) Mean Std Min Max Features FAST 11.67 4.15 1.74 30.16 Smoothing 0.96 0.37 0.79 2.51 BRIEF 1.72 0.49 1.51 4.62 Bag of words Conversion 3.59 0.35 3.27 8.81 Query 3.08 1.91 0.01 9.19 Islands 0.12 0.04 0.08 0.97 Insertion 0.11 0.02 0.06 0.28 Verification Correspondences and RANSAC 1.60 2.64 0.61 18.55 Whole system 21.60 4.82 8.22 51.68 Table 4.3: Execution time in NewCollege with 26292 images 4.4.7 Performance of the final system In previous sections we showed the effect of the parameters of our system in the correctness of the results. For our algorithm we chose the generic parameters k= 3, α= 0.3, and the DI2method for computing correspondences, since they proved effective under several kinds of environments in the training datasets. We ran our complete system in all the datasets but those with some overlap with the training images (Bovisa04 and Bovisa06). A summary with the parameters of the algorithm and the vocabulary is shown in Table 4.4. In Figure 4.14 we show the precision-recall curves obtained in these datasets with these parameters, processing the sequences at f= 2Hz. In Table 4.5 we show the figures of those curves with the final configuration. We achieved a high recall rate in the three datasets with no false positives. The results obtained in datasets NewCollege and Bicocca25b are shown in Video 1.a. and Video 1.b., listed in Section 1.4.2. In order to check the reliability of our algorithm with new datasets, we used Malaga6L and CityCenter as evaluation datasets. For these, we used our algorithm as a black box, with the default configuration given above and the same vocabulary. For Malaga6L, we processed the sequence at f= 2 Hz, and for CityCenter, we used all the images, since these are already taken 80 4.4. Experimental evaluation FAST threshold 10 BRIEF descriptor length (Lb) 256 BRIEF patch size (Sb) 48 Max. features per image 300 Vocabulary branch factor (kw) 10 Vocabulary depth levels (Lw) 6 Disallow local (τc) 20s Min. score with previous image (s(vt,vt−∆t)) 0.005 Temporally consistent matches (k) 3 Normalized similarity score threshold (α) 0.3 Direct index level (l) 2 Min. matches after RANSAC 12 Table 4.4: General parameters of our system far apart. We also compared our algorithm with the state-of-the-art FAB-MAP 2.0 algorithm (Cummins & Newman 2011), configured by default as it is available in its authors’ website. Given a query image, FAB-MAP returns a vector with the probability pof being at the same place than some previous image. Only those matches with phigher than a threshold are accepted. This parameter must be set by the user. We chose p≥98% because it showed the highest recall for 100% precision in these datasets. Table 4.5 and Table 4.6 show the results in the evaluation datasets. For sake of fairness, we remark on how this comparison was performed: FAB-MAP 2.0 software does not apply any geometrical constraint to the returned matches by default, so we applied a verification stage similar to ours, consisting in computing a fundamental matrix with the exhaustive search method. The input for FAB-MAP 2.0 must be a sequence of disjoint images. For Malaga6L, we fed it with images taken at frequency 1Hz. We also tried 0.25 and 0.5Hz, but 1Hz yielded better results. For CityCenter, we used all the available images. Finally, FAB-MAP 2.0 provides a vocabulary of 11K words of 128 float values, built from outdoor disjoint images, whereas our vocabulary contains 1M words of 256 bits, created from a sequence of images. As shown in Table 4.5, our algorithm with the parameters by default is able to achieve large recall with no false positives in both evaluation datasets. Our recall level is similar to that yielded by FAB-MAP 2.0, but with lower execution time. In the Malaga6L dataset, all the 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.92 0.94 0.96 0.98 1 Recall Precision NewCollege Bicocca25b Ford2 α = 0.3 Figure 4.14: Final precision-recall curves in the training datasets with f= 2Hz, with the selected working point α= 0.3. 81 Chapter 4. Real-time loop detection Dataset # Images Precision (%) Recall (%) NewCollege 5266 100 55.92 Bicocca25b 4924 100 81.20 Ford2 1182 100 79.45 Malaga6L 869 100 74.75 CityCentre 2474 100 30.61 Table 4.5: Precision and recall of our system Dataset # Images Min. pPrecision (%) Recall (%) Malaga6L 462 98% 100 68.52 CityCentre 2474 98% 100 38.77 Table 4.6: Precision and recall of FAB-MAP 2.0 loops are correct in spite of the illumination difficulties and the depth of the views. The results in CityCenter differ between our method and FAB-MAP 2.0 because the change between loop closure images is bigger than that in other datasets. This hinders the labor of the DI2technique because features are usually more distinct and are separated in early levels in the vocabulary tree. Note that this highlights the little invariance of BRIEF, since others as SURF may be able to produce more similar features between the images. Anyhow, we see that our method is still able to find a large amount of loop events in this dataset, and that the normalized similarity score ηL1behaves correctly in spite of the little overlap between consecutive images. This test shows that our method can work fine out of the box in many environments and situations, and that it is able to cope with sequences of images taken at low or high frequency, as long as they overlap. We can also remark that the same vocabulary sufficed to process all the datasets. This suggests that the source of the vocabulary is not so important when it is big enough. We show in Figure 4.15 the detected loops in each dataset. No false detections were fired. The trajectory in NewCollege is based on partially corrected GPS data, so that some paths are inaccurately depicted. Note that part of the vehicle where the camera is mounted is present in all the images of Ford2; we removed the features that lay on it. We see that detecting 55.92% of the loop events is enough to, for example, widely cover all the loop areas in a long trajectory as that of NewCollege. On the right hand side of Figure 4.15, we show examples of correct loop detections in the training and evaluation datasets, with the final corresponding features. These examples make the limited scale invariance of BRIEF descriptors apparent. Most of the features matched are distant, as we noticed in Section 4.4.3. The scale change that BRIEF tolerates is shown in the correspondences that are close to the camera in NewCollege and Bicocca25b, and those on the cars in Malaga6L. However, BRIEF cannot handle such a large scale change as that produced on the car in CityCenter, where all correspondences were obtained from distant features. On the other hand, whenever features are matched in background objects, a loop can be detected despite medium translations. This is visible in CityCenter and Ford2, where the vehicle moved along different lanes of the road. 4.5 Discussion In this chapter, we presented several enhancements for our technique to detect loops in monocular sequences. The main conclusion of our work is that binary features are very effective and extremely efficient in the bag-of-words approach. 82 4.5. Discussion It is worth mentioning that our vocabulary tree is one method among others to discretize binary spaces, and that these have drawbacks due to the thick boundaries of binary Voronoi regions (Trzcinski et al. 2012). In short, the problem arises because in Hamming spaces, unlike Euclidean ones, the points which are equidistant to any other two points occupy a large part of the space, making clustering more difficult. In the next chapter, we modify our vocabulary tree to deal with this issue. Despite this difficulty, our results demonstrate that FAST+BRIEF features are as reliable as SURF (either with 64 dimensions or with 128 and without rotation invariance) for solving the loop detection problem with in-plane camera motion, the usual case in mobile robots. In addition, the execution time and memory requirements are one order of magnitude smaller, without requiring special hardware. We showed the reliability and efficiency of our proposal on seven very different public datasets depicting indoor, outdoor, static and dynamic environments, with frontal or lateral cameras. Departing from most previous works, to avoid over-tuning, we restricted ourselves to present all results using the same vocabulary, obtained from an independent dataset, and the same parameter configuration, obtained from a set of training datasets, without peeking on the evaluation datasets. So, we can claim that our system offers robust and efficient performance in a wide range of real situations, without any additional tuning. In particular, we concluded that a single big vocabulary (we used 1 million words) is enough to process very different datasets. In fact, a big vocabulary tree does lower the execution time when accessing large image databases with an inverse index. We also shown a novel way of using a direct index along with the vocabulary tree to speed up the geometrical verification stage. We decrease the execution time by computing correspondences only between features with common nodes in the vocabulary tree, trading off the execution time of this stage with the recall rate of our system. Furthermore, this technique performed better than an approximate nearest neighbor approach (Muja & Lowe 2009) for individual images. Our experiments showed that the quantitative loss of recall is small when using the direct index, but it is even less significant if we think of the meaning behind the figures. A lower execution time allows to increase the working frequency of the loop detector. Even if the number of loops correctly fired drops in relative terms, the total amount of detections can be higher than that of higher recall at a lower latency. In addition, acquiring images faster raises the chance of finding a challenging loop closure, since more images of the same place are queried. The main limitation of our technique is the use of features that lack rotation and scale invariance. It is enough for place recognition in indoor and urban robots, but surely not for allterrain or aerial vehicles, humanoid robots, wearable cameras, or object recognition. However, our demonstration of the effectiveness of the binary bag-of-words approach paves the road for the use of new and promising binary features such as FREAK (Alahi et al. 2012), ORB (Rublee et al. 2011), or BRISK (Leutenegger et al. 2011), which outperform the computation time of SIFT and SURF, maintaining rotation and scale invariance. A fast loop detector is not just useful for urban robots, but for other computer vision applications as well. For instance, hand-held camera SLAM can be performed in low-capability devices (Klein & Murray 2009); these algorithms can profit from real-time data association provided by a fast loop detector. A fast SLAM algorithm and loop detector, along with fast object recognition can provide real-time semantic mapping. Aiming at this purpose, in the next chapter, we propose a system to perform video-rate 3D object recognition. 83 Chapter 4. Real-time loop detection Figure 4.15: Loops detected by our system in the five datasets (from up to down: NewCollege, Bicocca25b, Ford2, Malaga6L, CityCentre), with some examples of correct loops detected in scenes with motion blur and slight scale and perspective change. On the right hand side, lines depict final corresponding features. On the left hand side, the trajectory of the robot is depicted with thin black lines in new places, and with thick red lines in revisited areas. There are no false positives in any case. 84 Chapter 5 3D Object recognition for visual SLAM 5.1 Object recognition pipeline In this chapter we present our object detection and recognition algorithm for visual SLAM. The goal of our work is to provide a reliable detector, able to achieve real-time performance to place objects as high-level entities in a monocular SLAM map, producing semantic maps. We make use of two approaches to address this problem. First we introduce a baseline technique in which different views of objects are modeled individually with SURF features. We presented this standard recognition approach used together with a monocular SLAM system to build 3D semantic maps in Civera et al. (2011). This baseline technique, although effective, has some lacks: it is not scalable before a large number of objects and views, and it does not achieve video-rate execution time. To overcome these shortcomings, we fit the object recognition problem in our large-scale image matching framework. For that, we propose a second technique in which all the views of the objects are modeled with a single bag of binary words, indexed and retrieved later from an efficient database with inverted and direct indexes. Our two approaches work in an appearance recognition basis, for which object surface must be textured to some extent. The appearance matching is performed by means of local images features, so that it is robust to partial occlusion and some image transforms. Objects are recognized from single gray-scale images. As a result of detecting an object in an image, its pose in the 3D space with respect to the camera is obtained. The 3D pose permits placing the object in a 3D SLAM map; furthermore, this information together with the camera calibration suffices to locate the bounds of the object in the 2D image. The algorithms of the two approaches can be outlined in a similar way, by defining two stages: first, batches of training images are processed offline to build models of individual objects, and second, input images gathered online from a video stream are searched for recognizable objects. This pipeline is illustrated in Figure 5.1 and detailed next: 1. Object modeling: (a) Training image processing: sets of training images depicting several points of view of an object are searched for local features, which are matched across views. (b) Geometric and appearance modeling: matching features are used to triangulate covisible points to obtain a 3D point cloud of the object. Points are associated to 85 Chapter 5. 3D Object recognition for visual SLAM Figure 5.1: Object recognition pipeline. There are two main stages: object modeling (top row), performed offline only once per object, and object recognition (bottom row), performed online for each video frame. appearance information acquired from image feature descriptors. (c) Object database: objects models are stored together in a single database. 2. Object recognition: (a) Input image: geometrical and appearance data, in form of image features, is obtained from a video frame. Optionally, features can be separated into regions of interest to focus on local regions individually. (b) Database query: the object database is queried with the appearance data of the input image, and one or several object models are returned as candidates according to their similarity with the input. (c) Model verification and 3D pose computation: the geometrical data of candidate models are checked for consistency with the location of the input features. If there is consistency, the pose of the object in the scene is obtained. Otherwise, the candidate is rejected. The two approaches we consider differ in how the appearance of the objects is modeled and, hence, in how the object retrieval is carried out when the object database is queried. After explaining how we segment regions of interest in the next Section 5.4.4.1, we introduce both modeling techniques in Section 5.2, and detail the two object retrieval algorithms in Section 5.3 and Section 5.4. 86 5.2. Object modeling (a) Cuboid model (b) Frames of reference Figure 5.2: A planar cuboid-shaped model is defined by six ordered views and the dimensions of the object in metric units, as shown in (a). The cuboid condition determines exactly the position of any pixel in the 3D space, expressed in the object frame of reference O, located in the center of the cuboid. 5.2 Object modeling Our object models are composed of geometrical and appearance data. The geometric information is given by the 3D coordinates of points belonging to the surface of the object. Appearance is related to local image feature descriptors associated to the 3D points, so that models are fully described by image descriptors with 3D coordinates attached to them. Depending on the recognition process, models can be further detailed, as we explain in the next section. 5.2.1 3D point cloud model The geometry of the object is extracted from sets of training images that depict different points of view of the object to model. As a result, the geometry information is represented as a cloud of 3D points of coordinates expressed in the local object frame of reference. We manage two different methods to create point clouds that determine the number and source of training images. The first method imposes a planarity restriction to the surfaces, so that just one image per planar view of the object suffices to determine the 3D coordinates of all its points. This method is suitable for planar or box-shaped objects, such as cards, posters, cartons, boxes, etc. The second method does not constrain the shape of the object and estimates it by multi-view geometry (Hartley & Zisserman 2004). In this case several unordered pictures of the object are necessary to capture as much structure as possible. This method is utilized to model non-planar and generic objects. 5.2.1.1 Planar geometry We define a planar object as that shaped as a cuboid hexahedron, i.e. with six planar views which are pairwise equally-sized, as illustrated in Figure 5.2(a). To create such a model we 87 Chapter 5. 3D Object recognition for visual SLAM Figure 5.3: A juice box modeled as a planar object require six training images, one per surface, from Ato F, and the width, height and depth of the final object, denoted W,Hand D, respectively, in metric units. By imposing the planarity restriction, we can compute the 3D coordinates of any pixel in the training images expressed in a local frame of reference, located in the center of the image, as shown in Figure 5.2(b). Later, using the cuboid condition, we can transform that point to the object frame of reference, denoted Oand located in the center of the cuboid. The cuboid condition fixes the location of views with respect to the object frame, so that the transformations TO A, ..., TO Fare known. Therefore, given a pixel p= (u, v)⊤from surface A, without loss of generality, its 3D point pOis given by pO=TO A·    sA 1wA0 0 0 0sA 2hA0 0 0 0 0 0 0 0 0 1        u−wA/2 v−hA/2 0 1    ,(5.1) where wAand hAstand for the width and height of the image in pixels, and s1and s2are two of the real dimensions of the object in metric units, W,Hor Ddepending on the surface index. For surface A,sA 1=Wand sA 2=H. All the pixels of the training images, transformed into the object frame of reference, form the point cloud that comprises the geometrical information of the object model. A juice box modeled planar is shown in Figure 5.3. We can also build cuboid models ignoring some views. This is useful if we cannot provide some training images of the object, as for example the back part of a wardrobe, or if the object is just a planar surface, as a postcard. In such a case, we can define the point cloud just with an image and the width and height of the object. 5.2.1.2 General geometry Objects that have an arbitrarily complex shape can be modeled with a general technique that triangulates points present in several images by means of multi-view geometry. For that, we require several images that cover different points of view of the object. The only condition to satisfy is that there is enough overlap between images to be able to obtain 3D points by triangulation. General images with background can be used. In that case, image masks are required to segment out the object. Note that the process of separating object and background could be performed in an autonomous way, for example by finding salient regions in the depth 3D points provided by a RGBD camera or a laser sensor, or by rotating the object on a calibrated 88 5.4. Real-time recognition based on a single surface point cloud Figure 5.8: The description of a 3D point is obtained from several ORB descriptors when creating the model. Top row: two training images of a juice box. Bottom row: zoom in showing the ORB features obtained at several scales from the same 3D point seen in the two training images. All these descriptors are converted into visual words. Descriptors that result in the same word are merged to disregard redundant information. The words used for this purpose are given the term-frequency – inverse document frequency (tf-idf) weight (cf. Section 3.1.3), so that we obtain the bag-of-words vector vthat represents the complete appearance of the surface of the object in a compact manner. This together with the set P={p1, p2,...}form the object model O, so we can write O ≡ hv,Pi.(5.4) This model provides information of all the object surface, so that a single comparison of its bag-of-words vector can yield a similarity measurement independently of the viewpoint and the scale of the object in the query image. 5.4.3 Visual vocabulary object database We define our object database similarly to the place database in Chapter 4. It is composed of a visual vocabulary, an inverted index and a direct index, as shown in Figure 5.9. As we introduced in Section 4.2.3, there is a thick boundary problem when discretizing binary spaces that causes a large amount of points to be equidistant to some clusters, so it is not possible to match them with a cluster unambiguously. This difficulty was pointed out by Trzcinski et al. (2012), who measured the loss of matching performance and proposed several structures to overcome this problem. One of them are parc-trees, which are a set of random k-means trees 95 Chapter 5. 3D Object recognition for visual SLAM w Figure 5.9: Components of the database to represent the whole surface of objects as single bags of binary words. that produces several hierarchical clusterization of the binary space, so that the discretization error produced by a tree is likely to be mitigated by other. Different types of tree collections are becoming popular to deal with binary matching (Muja & Lowe 2012). Following this idea, instead of relying on a single tree, our vocabulary builds Twrandom trees from a set of training ORB features obtained offline, with the k-medians technique. This increases the chances of finding a unique correct cluster for a given point in the descriptor space. The leaves of these trees compose the words of the visual vocabulary. We use 12M descriptors obtained from 30607 independent images from Caltech-256 (Griffin et al. 2007) to build a vocabulary of Tw= 12 trees with kw= 10 branches and Lw= 4 depth levels, which yields 120K words. When a ORB feature is given, its descriptor vector traverses each tree from the root to the leaves, selecting at each level the node which minimizes the Hamming distance. From the Twfinal leaves, the one with lowest distance is selected as word. By concatenating the corresponding words of a set of ORB features, we obtain a vector of words. When all the chosen descriptors d1, d2,... of training images are converted into words, these are weighted with the term frequency – inverse document frequency (tf-idf) value, and normalized with the L1-norm. This way, we obtain the bag-of-words vector vof an object model O. The inverted index stores for each word in the vocabulary the objects where it is present, along with its weight in those objects. When a query image is given, this structure allows to retrieve the objects that have some word in common with it, so that similarity must be computed only for these models. In addition, the inverted index provides fast access to the common words between the query bag-of-words vector and the model one. The direct index stores for each object model the words (or some other tree node) it contains and its features associated with that word. This is used to access fast to those features which belong to the same word when we have to compute correspondences between them for the geometrical check. As we showed in our previous chapter, we can increase the amount of correspondences if we use the direct index to store nodes at other tree levels (coarser discretization levels), without worsening the execution 96 5.4. Real-time recognition based on a single surface point cloud time. In this work, for each object and feature, we store in the direct index the node which is closest to the feature descriptor at the first discretization level of the vocabulary trees. 5.4.4 Bag-of-words object recognition process The bag-of-words recognition approach works in three steps: 1. ORB features are obtained at a single scale from a query image I. These are separated into regions of interest (ROIs) by its 2D location in the image. 2. The object database is queried with each region of interest individually. The inverted index is used to compute a similarity score for all the objects, by using the BC-matching algorithm (Naik et al. 2009). 3. Correspondences between 2D points from the region of interest in the query image and the 3D points of the best-scored object are computed by means of the direct index. These will be used later to verify the recognition of the object and compute its 3D pose. The process is detailed in the next sections and illustrated by Algorithm 4. It starts by obtaining all the ORB features FIfrom the query image I. The two-stage clustering returns a set of clusters Qcontaining subsets of features Fq⊆ FIthat belong to different regions of interest in the query image. Each subset of ORB features is converted into a bag-of-words vector vqby traversing the trees of the visual vocabulary V. This vector is compared with all the bag-of-words vectors of the objects in the database and a set of similarity scores Sis obtained. This is done efficiently by accessing directly the data stored by the inverted index I. The object Owith the highest score is retrieved and looked up in the direct index Dcreated for a certain tree level l. The entry D(O) is used to compute a set of correspondences Cbetween the 2D points Fqof the ROI, and the 3D points XOof the object in the object frame O. The correspondences Care finally used to compute the transformation TO Cbetween the camera and the object with a RANSAC process. The transformation, and hence the recognition, is accepted only if RANSAC successes with a minimum number of supporting correspondences (inliers). 5.4.4.1 Region of interest segmentation Unlike the sequential view detection, where all the objects are checked for correspondences with the query image, in the bag-of-words recognition approach correspondences are just computed for the best retrieved candidate. This leads cluttered background to hinder the detection of objects which occupy a small part of the image, since spurious similarity scores are produced when querying the database. To ease this difficulty, we propose to cluster the image features by their 2D position and consider each cluster as a region of interest, so that detection can be performed on each individually. Since the number of regions of interest in the image is not known, we use the nonparametric Medoidshifts technique (Sheikh et al. 2007) to obtain a varying number of clusters. The core of the Medoidshifts algorithm is based on the computation of the distances between each pair of features and on a two N×Nmatrix multiplication, being Nthe number of features. As this operation is O(N2.38) (Coppersmith & Winograd 1987), in practice it can take a long time when Nis around a few hundreds. In order to speed up this step, we use a two-stage clustering method. When the number of features is high, first we compute a fixed number of 2D clusters with k-means++ (Arthur & Vassilvitskii 2007). The seeding technique of k-means++ tends to produce 2D clusters which are well distributed around all the image area covered by the features. Then, we perform Medoidshifts using the initial clusters as input points. This produces a varying 97 Chapter 5. 3D Object recognition for visual SLAM Algorithm 4: Object recognition by bags of words Input : Query image I, Object database B={O1,O2,...}, Visual vocabulary V, Inverted indexes I(i) for each i-th word, Direct index Dlfor tree level l, s.t. Dl(O) = {hi1,Fi1,XO i1i,hi2,Fi2,XO i2i, . . . } Output: Objects recognized R=nhOi1,TOi1 Ci,hOi2,TOi2 Ci,...o R ← ∅;1 FI←features(I);2 Q ← two stage clustering(FI);3 foreach Fq∈ Q do4 vq←conversion(Fq, V )5 S ← query BC matching(vq,I)6 O ← argmax O sχ2(vq,vO)∈ S 7 C ← correspondences(Dl(O),Fq,vq);8 hinliers,TO Ci ← transformation(Fq,XO,C)9 if there are enough inliers then10 R ← R∪hO,TO Ci 11 end12 end13 return R14 number of final 2D clusters which fit the distribution of image features better than the initial clusters yielded by k-means++. Image features are associated to their nearest final cluster. This results in a good approximation of the clusters yielded by Medoidshifts, but at a reduced computational effort. Figure 5.10 shows the resulting clusters in an image with 400 features when we create 100 initial clusters with k-means++. Both produce similar results, the only noticeable difference between the techniques are the clusters on the rings of the notebook, on the left-hand (a) Medoidshifts (b) Two-stage clustering Figure 5.10: Clusters obtained by Medoidshifts and our two-stage clustering (best viewed in color). 98 5.4. Real-time recognition based on a single surface point cloud side of the image. Table 5.1 shows the time consumed by each method, measured in a Intel Core i7 @ 2.67GHz machine. We obtain an improvement of one order of magnitude in the execution time. 5.4.4.2 Database query After separating image features into regions of interest, we transform each image ROI into a bag-of-words vector and query the database to obtain object matching candidates. In our previous chapter, we used the L1-norm distance to match images of places when using the whole image as input, since Nister & Stewenius (2006) and our own results showed its reliability. However, a ROI contains just a fraction of the features of the input image, much fewer than the thousand of points comprised by an object model. We ran some initial tests and found out that the L1-norm distance was not so effective in this case, whereas the Bhattacharyya coefficient or the χ2distance obtained better results. This supports the observations by Sivic & Zisserman (2009), who found that the L1-norm distance performed poorly in their datasets when the bags-of-words vectors to compare had a few words in common only. A bag-of-words vector encodes an histogram of occurrences of words. This means each histogram bin can be modeled as a Poisson-distributed random variable. This enables the χ2 distance as a measurement of dissimilarity between bag-of-words vectors (Aherne et al. 1998). However, although this metric is accurate over short statistical distances, it is not well suited for large distances, where the Bhattacharyya coefficient is more convenient (Aherne et al. 1998). Thus, we use a variation of the BC-matching technique proposed by Naik et al. (2009), which makes use of both metrics together. This consists in using a Bhattacharyya-based score (sB) to obtain the best candidates and selecting from these the one which maximizes a χ2-based score (sχ2). Naik et al. (2009) selected a fixed number Nof top-ranked Bhattacharyya matches. In our case, we found that a single value of Ndoes not behave well for all the models, so we consider a variable number of Bhattacharyya candidates. We select those whose score is higher than the best Bhattacharyya score obtained multiplied by a factor β. As well as the L1-norm score sL1, the Bhattacharyya and χ2scores are very convenient because they can be formulated in terms of the common elements of two bag-of-words vectors, and this information is directly provided by our inverted index. Let vand wbe two vectors such that kvk1=kwk1= 1, where videnotes the i-th element of vector v. Let V={i|vi6= 0},V= {i|vi= 0}be the sets of indexes of words of vwhich are non-empty and empty respectively, and analogously for Wand W. The Bhattacharyya score is defined as the Bhattacharyya coefficient: sB(v,w) = X V∩W √viwi.(5.5) We expand the χ2distance to obtain the χ2score sχ2. The χ2distance is defined as χ2(v,w) = X vi+wi6=0 (vi−wi)2 vi+wi.(5.6) Medoidshifts Two stages k-means++ - 5.13 Distance computation 0.91 0.04 Medoidshifts 67.76 0.81 Total 70.60 6.24 Table 5.1: Clustering execution time (ms) 99 Chapter 5. 3D Object recognition for visual SLAM Algorithm 5: Query with BC matching Input : Vector v, Object database B={O1,O2,...}, Inverted indexes I(i) for each i-th word Output: Set of best similarity scores S={sχ2(v,vO)| O ∈ B} SB← {sB(v,vO)←0| O ∈ B}1 Sχ2← {sχ2(v,vO)←0| O ∈ B}2 foreach word i∈v do3 foreach hO, vi Oi ∈ I(i)do4 sB(v,vO)←sB(v,vO) + qvivi O 5 sχ2(v,vO)←sχ2(v,vO) + 2 vivi O vi+vi O 6 end7 end8 S ← {sχ2(v,vO)∈ Sχ2|sB(v,vO)≥β·max (sB∈ SB)}9 return S10 If we assume all the elements of the vectors are non-negative (this holds when using the tf-idf weight), we can write χ2(v,w) = X V∩W vi+X V∩W wi+X V∩W (vi−wi)2 vi+wi.(5.7) Given that X V∩W vi=X V vi−X V∩W vi,(5.8) X V∩W wi=X W wi−X V∩W wi,(5.9) we get χ2(v,w) = X V vi+X W wi+X V∩W (vi−wi)2 vi+wi−vi−wi.(5.10) Since vand ware normalized, we obtain the expression χ2(v,w) = 2 −4X V∩W viwi vi+wi.(5.11) We finally scale the χ2distance to obtain a value in the range [0,1]: sχ2(v,w) = 1 −1 2χ2(v,w) = 2 X V∩W viwi vi+wi.(5.12) Algorithm 5 depicts the process of querying the database applying the BC-matching technique. Given a query bag-of-words vector v, we look up its words in the inverted index Ito get the objects whose appearance vectors vOcontain them. These are retrieved together with their word values vi O, which allow to compute the Bhattacharyya and the χ2scores sBand sχ2. The 100 5.4. Real-time recognition based on a single surface point cloud Times objects are first candidates (%) Metric Segmented Erosion 25px Erosion 50px Bhattacharyya 57 50 43 χ267 73 73 BC matching N= 12 67 77 77 BC matching β= 0.5 77 77 77 Table 5.2: Accuracy of similarity metrics objects with a highest Bhattacharyya score are selected, and their corresponding χ2scores are returned in descending order. We ran an experiment to measure the accuracy of each metric when selecting matching candidate models. We selected 30 images from a real webcam-quality video sequence where some objects were shown. To avoid image clustering from influencing the results, we disabled it and masked the background manually. We extracted features and retrieved the nearest model from a database with 20 objects. The accuracy in this experiment is defined as the percentage of times the correct object model is retrieved in first position. The results are shown in Table 5.2. We show results for BC matching with the best Nwe obtained and the βwe selected. To check the effect of noise, we ran the same test after shrinking the background masks with morphological erosions of 25 and 50 pixels, making features from background be used as well. As noticed by Naik et al. (2009), noise in the measurements makes the Bhattacharyya score lose accuracy, while the χ2one behaves better. The combination of the two metrics together outperforms the results of them alone. Using βinstead of Nyields slightly better results. 5.4.4.3 Correspondence computation The candidate object of each image cluster is finally checked for geometrical consistency to achieve its 3D pose, or to discard the cluster if no transformation is obtained. This process, described in depth in Section 5.5, requires correspondences between features in the query image and 3D points in the object model. In this approach, corresponding descriptors are required to belong to the same vocabulary tree node and to satisfy the nearest neighbor ratio condition. This way, we take advantage of our vocabulary trees as a means to divide features into groups which are expected to be close in the descriptor space. This is efficiently done with our direct index. When an object is added to the database, one of the nodes its descriptors traverse is stored in the direct index. We select the closest node in the first discretization level l= 1 of all the trees. The same is done when the image features are converted into words, so that we can select features with share a common node. Although this can reduce the amount of correspondences obtained, as we shown in Section 4.4.5, the overall number of comparisons between descriptors is lowered, dropping the execution time remarkably. We show in Table 5.3 the average execution time of computing correspondences with our direct index (DI) and an exhaustive method, where all the distances between the image Method Execution time (ms/cluster) Exhaustive 105.2 DI 1.9 Table 5.3: Computation of correspondences 101 Chapter 5. 3D Object recognition for visual SLAM cluster and the model features are computed. These data were obtained by comparing 30 image clusters with some object models consisting in 700–17000 words. 5.5 3D Pose computation from corresponding points The object retrieval algorithms presented in the previous sections provide a set of correspondences between the features of an image and the 3D points of an object candidate. The recognition finally successes if the matched points are geometrically consistent, allowing us to compute the 3D pose of the detected object; otherwise, the candidate is rejected. We make use of two standard methods to fulfill this: we impose a homography-based restriction to planar objects and apply a perspective-n-point algorithm to those of arbitrary shape. For the reader’s convenience, we detail both techniques below. 5.5.1 Homography for planar objects A homography is a 3 ×3 non-singular homogeneous matrix that represents a projective transformation between two views (Hartley & Zisserman 2004). Given 3 collinear points in a view, a projective transformation is that which preserves their collinearity in the other view. This transformation is characterized for resulting from a rotating camera or for being induced by a 3D plane that is seen by two cameras, as illustrated by Figure 5.11. The intersection between the ray that goes from the optical center of a camera Cand a 3D point xπin a plane Π produces a 2D point in the image plane of the camera x. The projection of the xπin the image plane of a second camera C′, produces the 2D point x′. Then, the homography Hthat is induced by the plane Π results in a direct mapping between the corresponding projections x,x′of points that lie in the plane. With points in homogeneous coordinates, x=λ(x, y, 1)⊤,x′=λ′(x′, y′,1)⊤, we can write x′=Hx.(5.13) Figure 5.11: Homography induced by a plane. The ray corresponding to a point xin the image plane of camera Cis extended to meet the plane Π in the 3D point xπ. The projection of xπ in the image plane of camera C′yields point x′. The map from xto x′is the homography H induced by the plane Π. Credit: Hartley & Zisserman (2004). 102 5.5. 3D Pose computation from corresponding points Figure 5.12: A homography between the view of a planar object model and a query image is computed from a set of corresponding points selected with RANSAC. The recognition is accepted if enough inliers are obtained. Although the homography matrix contains 9 elements, it has 8 degrees of freedom because it is defined up to scale. This means that matrix Hmultiplied by any non-zero scalar value still provides the same 2D mapping between points xand x′. Homography as geometrical verification. Homographies present a very practical application in the object recognition pipeline when dealing with objects composed of planar surfaces. Regarding planar objects modeled as independent views V=hFV,XO V,KVi(cf. Section 5.3.1), we can consider the object present in a query image as the result of applying a projective transformation to one of the training images that defined the object. Thus, there must exist a homography that relates both views. If we are able to find a homography in such a case, we accept the recognition of the planar object; otherwise, we reject the candidate detection. Consider the example given in Figure 5.12. This depicts a real scene in which a postcard is attached to the wall in a desktop area. The postcard is modeled as a planar object with a single view, with the training image shown on the right hand side. The homography H describes the transformation from the view to the scene, locating the 2D area of the view in the query image. We can estimate the homography from 4 pairs of corresponding 2D points between the features FIof the query image and those of the model view FV. If there are not 3 collinear points, the solution is unique. These are obtained by running RANSAC over the set of initial correspondences Ccomputed during the view matching. In each RANSAC iteration, the direct linear transformation (DLT) algorithm (Hartley & Zisserman 2004) is used with 4 random points to compute a candidate homography matrix e H. Then, the reprojection error of each correspondence is computed and those below a threshold εrare considered inliers. The number of inliers is given by en={hfi, f′ ji ∈ C | kx′∗ j−e Hxi∗k ≤ εr},(5.14) being ∗the normalization operator. If we are able to find a homography that is supported by a reliable enough number of inlier correspondences, the recognition of the candidate object is accepted. 103 Chapter 5. 3D Object recognition for visual SLAM Figure 5.13: The perspective-n-point problem consist in finding the pose of a camera Cin the frame of reference Ogiven four 3D points and their projections in the image plane. 3D pose recovery. After a successful recognition, a final homography matrix His optimized by using all the inliers returned by RANSAC. This homography encodes the motion between the cameras that acquired the query image and the object training image (Hartley & Zisserman 2004). We can write H=R+1 dtn⊤,(5.15) where R∈SO(3) and t∈R3are the rotation and translation that define the spatial transformation between the cameras, and n= (nx, ny, nz)⊤and dthe normal vector and the distance to origin of the plane Π ≡nxx+nyy+nzz+d= 0 that induces the homography H. It is possible to extract the plane and the motion between the cameras from the homography matrix by using a numerical method based on its the singular value decomposition (Faugeras & Lustman 1988, Zhang & Hanson 1996), or analytically (Vargas & Malis 2005). However, as a consequence of the scale ambiguity, neither the distance coordinate dof the plane nor the translation between cameras tcan be extracted individually, but the relation t/d is obtained instead. We can solve this issue and find tby incorporating the real distance between two observed 3D points, available since we provide the dimensions of the planar views when creating the planar object model. From Hwe can obtain the transformation TT Cthat relates the query camera Cwith the camera Tthat created the training image of the recognized object view. To find the pose of the object TO Cwe just concatenate TT Cwith the transformation TV Tbetween the training camera and the object view, and the transformation TO Vbetween the view and the object frame, both of them computed when creating the object model: TO C=TT C·TV T·TO V.(5.16) 104 5.7. Experimental evaluation Figure 5.20: Evaluation objects cards, and the generic perspective-n-point algorithm for the rest of objects, requiring at least 6 corresponding points. The lighting conditions were particularly bad in this sequence, as can be observed in Figure 5.22. In spite of this fact, all the six objects that composed our database were detected along the sequence (with no false positives), inserted in the 3D map and tracked the rest of the sequence. Only the first object recognition was considered. Figure 5.21 shows the results for the recognition thread at the specific frames where the six objects were recognized. The top row shows the frame in the sequence where they were recognized; the middle row the object view that was recognized; and the colored lines stand for the correspondences between the two. In the bottom row it is displayed the reprojection of the dense point cloud model over the top row images. Figure 5.22 summarizes the results of this experiment for several steps of the estimation. For each step it is shown the current frame and a 3D view of the estimation. The 3D view show the uncertainty ellipses for each point in the 3D map, the dense point clouds modeling the objects and the camera trajectory as a yellow line. Figure 5.22(a) shows the estimation results at step #610, when no object has been inserted yet. Figure 5.22(b) shows frame #1359, just after bio is detected and inserted. Figures 5.22(c), 5.22(d) and 5.22(e) show respectively that van, orbit and card1 have been inserted in the map and are being tracked. Their correspondent frames in the sequence are #2764,#4062,#4725. Figure 5.22(f) shows the results at step #7102, when the two latest objects –lion and card2– have been inserted. In Figure 5.22(g) the camera has gone back to the starting point (frame #8538), imaging again objects bio and van. Finally, Figure 5.22(h) is the last frame of the sequence, showing only the objects in the SLAM map. The complete desktop experiment can be watched in Video 2.b., listed in Section 1.4.2. 5.7.2 Bag-of-words recognition To evaluate the bag-of-words object recognition, we applied this approach on the same desktop sequence used above. We focus our results on the recognition performance, so we do without the 111 Chapter 5. 3D Object recognition for visual SLAM Figure 5.21: Object recognition thread results, showing column-wise the specific frames where the six objects were detected. The top row shows the image in the monocular sequence input to the monocular SLAM, the middle row shows the view of the object model, and the colored lines are the matches. The object is inserted in the map based on those correspondences. The bottom row shows the dense point cloud of the object over the image, proving the correct alignment. visual SLAM system. We extracted 12M ORB descriptors from 30607 independent images from Caltech-256 (Griffin et al. 2007) to build a vocabulary of T= 12 trees with k= 10 branches and L= 4 depth levels, which yields 120K words. Apart from the 6 objects used before, shown in Figure 5.20, we inserted 14 more in the database, adding up to 20 objects in total for this experiment. The object models were created with a varying number of training images (from 11 to 25 for general 3D objects, 1 for two planar ones), obtained from different consumer cameras. These images were 640 ×480 px and showed the object occupying most of the image area. Ten of these objects were obtained from the dataset provided by Hsiao et al. (2010). All of them are objects which can be usually found in real scenarios (boxes, cans, mugs, toys). The produced models have a very different number of words, from 743 to 35077, depending on how rich their texture is and how much surface is covered by the training images. Only the six objects said above are present in the video sequence, while the rest of them were used as distractors. Since no SLAM is run in this experiment, we processed the video sequence at 15Hz. The results of this experiment can be watched in Video 2.c., listed in Section 1.4.2. Method Max. iterations Successful cases Execution time (ms/cluster) Exhaustive 2000 20 51.6 DI 2000 19 77.7 DI 1000 18 40.2 DI 100 17 4.3 DI 50 11 2.3 DI 30 7 0.8 Table 5.4: RANSAC and EPnP 112 5.7. Experimental evaluation Figure 5.22: Representative images (at the top) and 3D estimation at their respective times (at the bottom) for the desktop experiment. (a) Initial map, still with no recognized objects. (b) Bio has been recognized, inserted and is being tracked. (c), (d) and (e): van, orbit and card1 have been inserted. (g) The two remaining objects –card2 and lion– are inserted. (h) The camera moves back close to the starting position, revisiting all previous objects. (h) Final frame of the sequence and 3D view of the objects registered in a common reference frame. 113 Chapter 5. 3D Object recognition for visual SLAM 5.7.2.1 Geometrical verification performance After querying the database and obtaining the best object model that matches an image region of interest, we compute the 2D-3D correspondences to verify the recognition with RANSAC and EPnP . RANSAC computes iteratively candidate spatial transformations from random subsets of the available correspondences and selects the one which maximizes the number of consistent points. If no transformation with at least 6 inliers is found, we reject the detection. The execution time of RANSAC (and its effectiveness) can be reduced by limiting the number of iterations. We show in Table 5.4 the effect of limiting this parameter. We ran RANSAC and EPnP on 147 clusters obtained from 30 images. From 30 clusters containing objects, the database query returned the correct object as the first candidate in 22 cases, which is the maximum number of successful cases that could be obtained in Table 5.4. We show also the results when computing correspondences with the exhaustive method and running RANSAC with a high number of iterations. We consider this is the best result we can obtain in these images with ORB descriptors. Note that computing correspondences exhaustively takes around 105ms per cluster, as we shown in Table 5.3 in page 101, whereas the direct index reduces this to 2ms per cluster. We see in Table 5.4 that if we use the direct index instead, we miss one detection only (from 20 to 19), but halve the total average time per image cluster when taking into account the time of computing correspondences. We set the number of RANSAC iterations to 100 for the rest of experiments because it offers a balanced trade-off between detection rate and execution time. 5.7.2.2 Detection performance We measured the detection rate of our system. No false detections were fired all along the sequence. This means that those cases where a wrong object was returned after querying the database were successfully rejected in the geometrical check stage. Figure 5.23 shows two examples of successful recognitions of bio and the van. Detections are shown by projecting the points of the model in the image. Table 5.5 shows the times each object is recognized and the number of frames in which it is visible. Note that the presence of an object in a frame was decided by manual inspection of the video sequence, so that although it may be easy for a person to say whether an object is present in a frame, it may be a challenge for many computer vision algorithms. All the objects are correctly recognized several times, yielding a total average recall of 26%. We can see there are detections missing in some frames, specially in the case of objects lion and van. These two are particularly difficult to recognize because they present a lot of similar looking patterns, such as the striped white and red scarf and cap of the lion, and the similar picture which appears on top and on both sides of the van. This produces perceptual aliasing, making correspondences fail the neighbor ratio condition and be rejected. Most of the rest of missed cases are due to the Object Detections Occurrences Recall (%) Bio 251 471 53.3 Van 26 262 9.9 Orbit 193 464 41.6 Lion 2 483 0.4 Card1 183 681 26.9 Card2 141 590 23.9 Average 26.0 Table 5.5: Detection performance 114 5.7. Experimental evaluation Figure 5.23: Examples of correct recognitions of bio and the van (a) Detection missed (b) Incorrect transformation Figure 5.24: Examples of unsuccessful detections. In (a) the van and bio are not detected because of their small size in the image. In (b) an incorrect transformation is obtained because ill-conditioned point correspondences. small size of the object in the query image. These are challenging cases. Fewer features can be extracted on the object, which are more likely to be clustered together with background features. This may make database queries fail when retrieving the candidate model. This can happen as well if the scale change is bigger than the 2 octaves we considered when creating the models, since features will not be converted into the same word than the corresponding feature in the model. Figure 5.24(a) shows an example where the bio carton and the van were present but were not detected. As a future work, our system is due to be compared with the state-of-the-art approach to show the effects of the described difficulties. Although we obtained no false positives, in some cases the computed transformations were slightly inaccurate. The error in computing the transformation can be due to ill-conditioned point configurations for PnP , which makes it produce a imprecise transformation. Figure 5.24(b) shows an example of this case. RANSAC can also obtain an incorrect transformation if some correspondence produced by the background is considered as inlier. This could be ease by increasing the number of inliers to accept the transformation. In the general case, the features extracted from consecutive frames are not the same. This leads to obtain correspondences 115 Chapter 5. 3D Object recognition for visual SLAM Figure 5.25: Example of different consecutive detections of bio Per image Per cluster Median Max. Median Max. ORB 4.0 10.5 - - Clustering 2.9 10.4 - - Conversion 11.9 26.1 1.0 16.5 Query 0.3 1.9 0.0 1.6 DI 6.4 19.4 1.1 10.8 RANSAC 2.0 9.6 1.9 6.1 Total 27.9 60.8 8.0 27.0 Table 5.6: System execution time (ms) between different sets of model and image features which can produce different transformations. The effect of this is that the pose of an object found in consecutive frames varies, as in the example shown in Figure 5.25. This behavior does not entail a great drawback because this effect is mitigated by the SLAM algorithm which robustly tracks the features which belong to the object once it is recognized, as shown in our previous experiment. 5.7.2.3 Execution time The execution time of this experiment is detailed in Table 5.6. We show the median and the maximum execution time of each step per cluster and per image. The overall approach can be executed in less than 30 ms on average per image, so working with a SLAM algorithm at 30Hz would be feasible. All the steps require a low execution time, including the conversion of ORB features into bag-of-words vectors and the database query. The conversion execution time depends mainly on the number of trees of the vocabulary and their branching factor. We could reduce their number, obtaining fewer words in the vocabulary, to speed up this step, but this would affect the performance of the feature descriptor discretization. The time to query the database is remarkably low, less than 1 ms on average. This indicates our approach is scalable with regard to the amount of objects. Since this query time grows linearly with the number of elements in the database, as we could see in Figure 4.13 in page 80, we may have a one order of magnitude larger database with little impact in the execution time. The geometrical check, which comprises the computation of correspondences by using the direct index (DI) and the RANSAC loop to solve the PnP problem, presents also a low time consumption. 116 5.8. Discussion Bag-of-words approach Independent view approach Bio 34 51 Van 95 100 Orbit 152 147 Lion 238 237 Card1 169 171 Card2 229 243 Table 5.7: Elapsed time until first detection (s) 5.7.2.4 Comparison with previous approach The low execution time of our approach allows to process a higher number of images per unit of time, increasing the recall level shown in previous section when the image sequence is considered as a whole instead of in a per image basis. In order to show this and check the feasibility of our object detector for visual SLAM applications in comparison with usual approaches using floating-point features, we compared this approach with the previous one based on views of SURF features. In the previous experiment, the detector skipped objects after their first recognition, because once their features were detected, the SLAM algorithm kept track of them to locate the object in the visual map. Because of this, we show in Table 5.7 the elapsed time in the tested video sequence from the beginning until the first detection of each object. We can see that objects bio and card2 are found much earlier than in our previous work. The fast response of our system allows to perform recognition in a higher number of frames. Our previous system finds the object orbit 5 seconds before than our current approach. This case occurs because the SURF features obtain a successful match with a query image which present a scale change larger than the 2 octaves of our ORB features. In the rest of the cases there are no differences between both approaches. This shows that our current system with ORB features produces successful results, as a SURF-based system, but requiring much lower computation time, which allows to obtain a response in the same amount of time. 5.8 Discussion We presented two different approaches to solve the problem of recognizing 3D textured objects and estimating its pose in the space. We successfully tested them and showed results working with a real-time visual SLAM system. Object recognition based on independent view models constructed with structure-from-motion techniques and a state-of-the-art monocular SLAM algorithm were combined to allow the insertion of precomputed known objects into a standard point-based monocular SLAM map. The main input to the algorithm is visual information: a monocular sequence feeds the EKF SLAM algorithm; the appearance and geometric models for the known objects are precomputed from a set of sparse images; and also object recognition is driven by visual features. Experimental results show the feasibility of the algorithm and its real-time capabilities for room-sized scenarios. Taking advantage of our previous research on bags of words based on binary descriptors to solve the place recognition problem, we applied these techniques to the object recognition in our second approach. This allows us to address two drawbacks present in the previous recognition approach. Firstly, representing an object as disjoints sets of features can result in redundant information resulting from overlapping views, increasing the matching time. Secondly, accessing object models and views must be done sequentially. By using a single bag of words to repre117 Chapter 5. 3D Object recognition for visual SLAM sent the whole surface of an object, we eliminate redundant information, and with an efficient database with inverted and direct indexes we speed up the model retrieval. Furthermore, binary features strikingly reduces the execution time of managing image features. Overall, this approach, aimed at SLAM applications for semantic mapping, is fast and scalable to perform 3D object recognition. Our tests have shown that our approach can successfully recognize several objects without yielding any false positive detection, running at 30Hz, allowing it to run along with a SLAM algorithm. The average recall of 26% presented in our experiments usually suffices for a SLAM application working at video rate, as we showed by comparing this system with the previous approach based on SURF features. This recall means that a recognition, providing the object pose, could be fired every 120ms. We could improve the recall at the expense of increasing the execution time of the algorithm (e.g. by increasing the number of RANSAC iterations). However, the working frequency of the algorithm would decrease, so the recall per unit of time would remain similar. Regarding the cameras used: the camera used for building the models can be different from the one used to perform object recognition and visual SLAM. Any robot with a calibrated camera would be able to exploit then the precomputed models, what makes the system interoperable. The robot ends up with the location of the object it is supposed to interact with under quite general circumstances. We also showed that when using a SLAM algorithm, just by recognizing a part of an object once, the SLAM map can incorporate information about object regions that are not observed. This might be quite useful for tasks like robot navigation. The work presented here was the first one introducing general 3D objects in a geometric SLAM map in real-time. There is a potential value residing on the concept underneath this work. On the one hand recent research on visual object recognition allows to robustly recognize a wide extent of objects from visual input; but 3D information is rarely considered in those approaches. On the other hand, monocular SLAM and structure from motion currently offer real-time camera motion and 3D scene estimation but without a semantic meaning. The combination presented here, providing a partially annotated local map and the current robot position, could be of high value for certain robotic tasks like grasping (as demonstrated in the RoboEarth experiment). We pointed out our system always returns the correct object in the scene, but the transformation computed by the PnP algorithm may not be accurate enough. This could be enhanced in future work, for example, by performing query expansions (Chum et al. 2007) with the features matched when an object is detected. An expanded query may produce richer matches between the image and the model than a single query, resulting in more data to compute a more accurate object pose. Other interesting lines for future work arise from the point of view of semantic mapping. First, if would be very interesting to increase the quality and density of the semantic annotations. For example, the object recognition based on instances could be upgraded to category recognition (Ferrari et al. 2010). This would allow to recognize generic categories (e.g., the category chair) instead of specific instantiations of a category (e.g., a specific chair). Context-based object detection (Murphy et al. 2003) or image segmentation (Gould et al. 2010) could also help to augment the density of the annotated objects. Second, monocular SLAM algorithms providing with denser geometric maps (Newcombe & Davison 2010, Strasdat et al. 2010) could be used in order to help robotic tasks like navigation or path planning. 118 Chapter 6 Conclusions In this thesis we have presented our image matching framework in large-scale databases to address two related problems: place recognition for loop closing detection and object recognition for semantic mapping. We have shown how our pipeline can be adapted to these problems obtaining reliable results with video-rate efficiency. 6.1 Loop closing detection Along this work we have detailed our algorithm to solve the loop closing detection problem in visual SLAM. We started by presenting our initial technique with SURF features, a visual vocabulary and an inverted index. We have proposed several novelties with respect to other approaches and have also shown their advantages, overcoming the state of the art. Our work benefits from the sequentiality of the frames acquired with a camera. This is specially exploited during the database query and the process to obtain a candidate match, requiring consistency with previous loop detections. In contrast with other probabilistic algorithms, our technique successes working at low and high frequencies, despite the much or little overlap existing between consecutive images. We have concluded that a posterior geometrical verification is necessary to filter out the false positives yielded by loop detection based on appearance. We have made use of several techniques to robustly discard those cases, for single and multiple cameras, both considering epipolar geometry and probabilistic inference with geometrical properties of reconstructed 3D points. We have then shown how our algorithm is improved with binary features, which are clustered by a visual vocabulary of binary words. To the best of our knowledge, this has been the first time where the loop closing detection problem is addressed in such a way. We have also introduced direct indexes for visual words to speed up the computation of feature correspondences. We have evaluated our system keeping the same configuration and vocabulary settings throughout an extensive evaluation with heterogeneous datasets, separating evaluation data from training data. We have obtained a video-rate loop closing detection algorithm able to fire a detection in 22ms on average with more than 26000 images. Therefore, we can claim that our loop detection system offers robust and efficient performance in a wide range of real situations, without any additional tuning. 119 Chapter 6. Conclusions 6.2 3D Object recognition We have first presented a 3D object recognition algorithm that, together with a visual SLAM algorithm, have composed one of the first systems that can create 3D maps with 3D objects, overcoming the limitations of other state-of-the-art systems. We have shown how our framework can be adapted to carry out the recognition of 3D objects with visual vocabularies and binary features. This visual vocabulary approach allows objects to be modeled as a single bag of words representing the whole surface of the object, associating words with the 3D coordinates of a point cloud, allowing a very fast object candidate retrieval. Our final object recognition algorithm also makes use of a novel two-stage clustering process to segment regions of interest in the query image. This enables to perform object detection in small areas of the image without checking exhaustively the whole image by sliding a window. Putting all the pieces together, we obtain a 3D object recognition algorithm that is able to run at video-rate (around 28ms per image) with medium-sized object databases, so that it can run with any visual SLAM algorithm to take advantage of it to refine the pose of the recognized objects after inserting them in the map. 6.3 Future work In the near future, the next step to enhance this work is to put together both faces of our image matching framework, by joining the real-time place and object recognition algorithms. Technically speaking, they fit nicely because both of them are constructed on FAST key points, the same feature used by other monocular SLAM system, such as the parallel tracking and mapping algorithm (PTAM) (Klein & Murray 2009). Both approaches can benefit from each other, since the loop closing detection allows to improve the map that, at the same time, refines the pose of recognized objects. This is an immediate advantage; but others can be glimpsed. By recognizing objects we can notice image features that belong to objects and ignore them to perform SLAM or loop detection if we know those objects are movable. Semantic maps play an important role here by providing the necessary external information about objects. A video-rate object recognition also makes it possible to track objects by detection. A first detection can serve as a position cue for consecutive detections, so that next recognitions can be focused on a single object and on a certain region of the image. Tracking objects and separating their image features in the mapping stage would allow to create maps that deal with a mobile camera and mobile objects at the same time, a problem that has not been addressed yet. All this paves the road to new research for robotics and other areas as augmented reality, so that it is not difficult to imagine new applications. For example, in a factory environment, workers may wear a helmet or camera glasses where a 3D Object SLAM system is integrated to keep track of the motion of the user, whereas they obtain instructions and information about the places in which they are or the tools they use. 120 BIBLIOGRAPHY Civera, Javier, Dorian G´alvez-L´opez, Luis Riazuelo, Juan D. Tard´os & J. M. M. Montiel (2011), Towards semantic slam using a monocular camera, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)’, pp. 1277–1284. Civera, Javier, ´ Oscar G. Grasa, Andrew Davison & J. M. M. Montiel (2010), ‘1-point ransac for ekf filtering: Application to real-time structure from motion and visual odometry’, Journal of Field Robotics 27(5), 609–631. Collet, Alvaro, Manuel Martinez & Siddhartha S. Srinivasa (2011), ‘The MOPED framework: Object Recognition and Pose Estimation for Manipulation’, The International Journal of Robotics Research 30(10), 1284–1306. Coppersmith, Don & Shmuel Winograd (1987), Matrix multiplication via arithmetic progressions, in ‘Proceedings of the nineteenth annual ACM symposium on Theory of computing’, STOC ’87, ACM, New York, NY, USA, pp. 1–6. Cummins, Mark & Paul Newman (2008), ‘FAB-MAP: Probabilistic Localization and Mapping in the Space of Appearance’, The International Journal of Robotics Research 27(6), 647–665. Cummins, Mark & Paul Newman (2011), ‘Appearance-only SLAM at large scale with FAB-MAP 2.0’, The International Journal of Robotics Research 30(9), 1100–1123. DARPA (2007), ‘Darpa grand challenge’. URL: http://archive.darpa.mil/grandchallenge Davison, Andrew, Ian Reid, Nicholas D. Molton & Olivier Stasse (2007), ‘MonoSLAM: Real-time single camera SLAM’, Pattern Analysis and Machine Intelligence, IEEE Transactions on 29(6), 1052–1067. Douze, Matthijs, Herv´e J´egou, Harsimrat Sandhawalia, Laurent Amsaleg & Cordelia Schmid (2009), Evaluation of GIST descriptors for web-scale image search, in ‘ACM International Conference on Image and Video Retrieval’, CIVR ’09, ACM, New York, NY, USA, pp. 19:1– 19:8. Durrant-Whyte, Hugh & Tim Bailey (2006), ‘Simultaneous Localization and Mapping: Part I’, IEEE Robotics Automation Magazine 13(2), 99–110. Eade, Ethan D. & Tom W. Drummond (2008), Unified loop closing and recovery for real time monocular slam, in ‘Proceedings of the British Machine Vision Conference’, pp. 6.1–6.10. Ekvall, Staffan & Danica Kragic (2005), Receptive field cooccurrence histograms for object detection, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems’, pp. 84–89. Ekvall, Staffan, Patric Jensfelt & Danica Kragic (2006), Integrating active mobile robot object recognition and slam in natural environments, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems’, pp. 5792–5797. Faugeras, Olivier D. & Francis Lustman (1988), ‘Motion and structure from motion in a piecewise planar environment’, International Journal of Pattern Recognition and Artificial Intelligence 2(3), 485–508. Ferrari, Vittorio, Frederic Jurie & Cordelia Schmid (2010), ‘From images to shape models for object detection’, International journal of computer vision 87(3), 284–303. 127 BIBLIOGRAPHY Fischler, Martin A. & Robert C. Bolles (1981), ‘Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography’, Communications of the ACM 24(6), 381–395. Friedman, Jerome H., Jon Louis Bentley & Raphael Ari Finkel (1977), ‘An algorithm for finding best matches in logarithmic expected time’, ACM Transactions on Mathematical Software 3(3), 209–226. Furukawa, Yasutaka & Jean Ponce (2010), ‘Accurate, dense, and robust multiview stereopsis’, IEEE Transactions on Pattern Analysis and Machine Intelligence 32(8), 1362–1376. Galindo, Cipriano, Alessandro Saffiotti, Silvia Coradeschi, P. Buschka, Juan Antonio FernandezMadrigal & Javier Gonzalez (2005), Multi-hierarchical semantic maps for mobile robotics, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems’, pp. 2278–2283. G´alvez-L´opez, Dorian & Juan D. Tard´os (2011), Real-time loop detection with bags of binary words, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems’, pp. 51– 58. G´alvez-L´opez, Dorian & Juan D. Tard´os (2012), ‘Bags of binary words for fast place recognition in image sequences’, IEEE Transactions on Robotics 28(5), 1188–1197. G´alvez-L´opez, Dorian, Kristoffer Sj¨o¨o, Chandana Paul & Patric Jensfelt (2008), Hybrid laser and vision based object search and localization, in ‘IEEE International Conference on Robotics and Automation’, pp. 2636–2643. Gauglitz, Steffen, Tobias H¨ollerer & Matthew Turk (2011), ‘Evaluation of interest point detectors and feature descriptors for visual tracking’, International Journal of Computer Vision 94(3), 335–360. 10.1007/s11263-011-0431-5. Gionis, Aristides, Piotr Indyk & Rajeev Motwani (1999), Similarity search in high dimensions via hashing, in ‘25th International Conference on Very Large Data Bases’, VLDB ’99, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp. 518–529. Gould, Stephen, Richard Fulton & Daphne Koller (2010), Decomposing a scene into geometric and semantically consistent regions, in ‘12th IEEE International Conference on Computer Vision’, pp. 1–8. Grabner, Michael, Helmut Grabner & Horst Bischof (2006), ‘Fast approximated SIFT’, Asian Conference on Computer Vision pp. 918–927. Griffin, Gregory, Alex Holub & Pietro Perona (2007), Caltech-256 object category dataset, Technical Report 7694, California Institute of Technology. URL: http://authors.library.caltech.edu/7694 Grisetti, Giorgio, Cyrill Stachniss & Wolfram Burgard (2009), ‘Nonlinear constraint network optimization for efficient map learning’, IEEE Transactions on Intelligent Transportation Systems 10(3), 428–439. Grundmann, Thilo, Wendelin Feiten & Georg von Wichert (2011), A Gaussian measurement model for local interest point based 6 DOF pose estimation, in ‘IEEE International Conference on Robotics and Automation (ICRA)’, pp. 2085 –2090. Harris, Chris & Mike Stephens (1988), A combined corner and edge detector, in ‘In Proceedings of Fourth Alvey Vision Conference’, pp. 147–151. 128 BIBLIOGRAPHY Hartley, Richard I. (1997), ‘In defense of the eight-point algorithm’, IEEE Transactions on Pattern Analysis and Machine Intelligence 19(6), 580–593. Hartley, Richard I. & Andrew Zisserman (2004), Multiple View Geometry in Computer Vision, second edn, Cambridge University Press, ISBN: 0521540518. Heymann, S., K. M¨uller, A. Smolic, Bernd Froehlich & T. Wiegand (2007), SIFT Implementation and Optimization for General-Purpose GPU, in ‘International Conference in Central Europe on Computer Graphics and Visualization’. Horn, Berthold K. P., Hugh M. Hilden & Shahriar Negahdaripour (1988), ‘Closed-form solution of absolute orientation using orthonormal matrices’, Journal of the Optical Society of America A5(7), 1127–1135. Hsiao, Edward, Alvaro Collet & Martial Hebert (2010), Making specific features less discriminative to improve point-based 3D object recognition, in ‘IEEE Conference on Computer Vision and Pattern Recognition (CVPR)’, IEEE, pp. 2653–2660. Ke, Yan & R. Sukthankar (2004), PCA-SIFT: a more distinctive representation for local image descriptors, in ‘Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition’, Vol. 2, pp. II–506 – II–513 Vol.2. Klein, Georg & David Murray (2009), Parallel tracking and mapping on a camera phone, in ‘Proceedings of the Eigth IEEE and ACM International Symposium on Mixed and Augmented Reality (ISMAR’09)’, Orlando. Koller, Daphne & Nir Friedman (2009), Probabilistic Graphical Models: Principles and Techniques, MIT Press, ISBN: 9780262013192. Konolige, Kurt, James Bowman, J.D. Chen, Patrick Mihelich, Michael Calonder, Vincent Lepetit & Pascal Fua (2010), ‘View-based maps’, The International Journal of Robotics Research 29(8), 941–957. Kullback, Solomon & Richard A. Leibler (1951), ‘On Information and Sufficiency’, Annals of Mathematical Statistics 22(1), 79–86. Lafferty, John, Andrew McCallum & Fernando Pereira (2001), Conditional Random Fields: Probabilistic models for segmenting and labeling sequence data, in ‘Proceedings of the 18th International Conf. on Machine Learning’, Morgan Kaufmann, San Francisco, CA, pp. 282–289. Lepetit, Vincent, Francesc Moreno-Noguer & Pascal Fua (2009), ‘EPnP: An accurate O(n) solution to the PnP problem’, International Journal of Computer Vision 81(2), 155–166. Lepetit, Vincent & Pascal Fua (2006), ‘Keypoint recognition using randomized trees’, IEEE Transactions on Pattern Analysis and Machine Intelligence pp. 1465–1479. Leutenegger, Stephan, Margarita Chli & Roland Siegwart (2011), BRISK: Binary Robust Invariant Scalable Keypoints, in ‘IEEE International Conference on Computer Vision’, Barcelona, pp. 2548 –2555. L´opez-Nicol´as, Gonzalo, J.J. Guerrero & Carlos Sag¨u´es (2010), ‘Multiple homographies with omnidirectional vision for robot homing’, Robotics and Autonomous Systems 58(6), 773– 783. 129 BIBLIOGRAPHY Lowe, David G. (1999), Object recognition from local scale-invariant features, in ‘The Proceedings of the Seventh IEEE International Conference on Computer Vision’, Vol. 2, pp. 1150– 1157. Lowe, David G. (2004), ‘Distinctive image features from scale-invariant keypoints’, International Journal of Computer Vision 60(2), 91–110. Majdik, Andras, Dorian G´alvez-L´opez, Gheorghe Lazea & Jose A. Castellanos (2011), Adaptive appearance based loop-closing in heterogeneous environments, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)’, pp. 1256–1263. Meger, David, Per-Erik Forss´en, Kevin Lai, Scott Helmer, Sancho McCann, Tristram. Southey, Matthew Baumann, James J. Little & David G. Lowe (2008), ‘Curious George: An attentive semantic robot’, Robotics and Autonomous Systems 56(6), 503–511. Mikolajczyk, Krystian & Cordelia Schmid (2005), ‘A performance evaluation of local descriptors’, IEEE Transactions on Pattern Analysis and Machine Intelligence pp. 1615–1630. Muja, Marius & David G. Lowe (2009), Fast approximate nearest neighbors with automatic algorithm configuration, in ‘International Conference on Computer Vision Theory and Application’, pp. 331–340. Muja, Marius & David G. Lowe (2012), Fast matching of binary features, in ‘Ninth Conference on Computer and Robot Vision (CRV)’, pp. 404–410. Murillo, Ana C., J. J. Guerrero & Carlos Sag¨u´es (2007), SURF features for efficient robot localization with omnidirectional images, in ‘IEEE International Conference on Robotics and Automation’, pp. 3901–3907. Murphy, Kevin P., Antonio Torralba & William T. Freeman (2003), Using the forest to see the trees: a graphical model relating features, objects and scenes, Vol. 16, MIT Press, Vancouver, BC. Naik, Nikhil, Sanmay Patil & Madhuri Joshi (2009), A scale adaptive tracker using hybrid color histogram matching scheme, in ‘2nd International Conference on Emerging Trends in Engineering and Technology (ICETET)’, pp. 279–284. Newcombe, Ricahrd A. & Andrew Davison (2010), Live dense reconstruction with a single moving camera, in ‘IEEE Conference on Computer Vision and Pattern Recognition (CVPR)’, IEEE, pp. 1498–1505. Nister, David & Henrik Stewenius (2006), Scalable recognition with a vocabulary tree, in ‘IEEE Computer Society Conference on Computer Vision and Pattern Recognition’, Vol. 2, pp. 2161–2168. Oliva, Aude & Antonio Torralba (2001), ‘Modeling the shape of the scene: A holistic representation of the spatial envelope’, International Journal of Computer Vision 42(3), 145–175. Olson, Edwin (2008), Robust and Efficient Robotic Mapping, PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA. Olson, Edwin (2009), ‘Recognizing places using spectrally clustered local matches’, Robotics and Autonomous Systems 57(12), 1157–1172. 130 BIBLIOGRAPHY OpenCV (2009), ‘Open source computer vision library. URL: http://opencv.willowgarage.com’. URL: http://opencv.willowgarage.com Pandey, Gaurav, James R. McBride & Ryan M. Eustice (2011), ‘Ford campus vision and lidar data set’, The International Journal of Robotics Research 30(13), 1543–1552. URL: http://robots.engin.umich.edu/SoftwareData/Ford Pangercic, Dejan, Vladimir Haltakov & Michael Beetz (2011), Fast and robust object detection in household environments using vocabulary trees with sift descriptors, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Workshop on Active Semantic Perception and Object Search in the Real World’, San Francisco, CA, USA. Paul, Rohan & Paul Newman (2010), FAB-MAP 3D: Topological mapping with spatial and visual appearance, in ‘IEEE International Conference on Robotics and Automation’, pp. 2649– 2656. Paz, Lina M., Pedro Pini´es, Juan D. Tard´os & Jos´e Neira (2008), ‘Large-scale 6-DOF SLAM with stereo-in-hand’, IEEE Transactions on Robotics 24(5), 946–957. Pearl, Judea (1988), Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., ISBN: 0-934613-73-7, San Francisco, CA, USA. Pini´es, Pedro & Juan D. Tard´os (2008), ‘Large-scale SLAM building conditionally independent local maps: Application to monocular vision’, IEEE Transactions on Robotics 24(5), 1094– 1106. Pini´es, Pedro, Lina M. Paz, Dorian G´alvez-L´opez & Juan D. Tard´os (2010), ‘CI-Graph SLAM for 3D Reconstruction of Large and Complex Environments using a Multicamera System’, International Journal of Field Robotics 27(5), 561–586. Pretto, Alberto, Emanuele Menegatti & Enrico Pagello (2007), Reliable features matching for humanoid robots, in ‘7th IEEE-RAS International Conference on Humanoid Robots’, pp. 532– 538. Pronobis, Andrzej, ´ Oscar Martinez Mozos, Barbara Caputo & Patric Jensfelt (2010), ‘Multimodal semantic place classification’, The International Journal of Robotics Research (IJRR) 29(2-3), 298–320. Quinlan, J. Ross (1986), ‘Induction of decision trees’, Machine Learning 1(1), 81–106. Ramos, Fabio, Dieter Fox & Hugh Durrant-Whyte (2007), CRF-Matching: Conditional Random Fields for Feature-Based Scan Matching, in ‘Robotics: Science and Systems (RSS)’. Ramos, Fabio, Mohammed Waleed Kadous & Dieter Fox (2008), Learning to associate image features with CRF-Matching, in ‘The 11th International Symposium of Experimental Robotics (ISER)’, pp. 505–514. Rawseeds (2007-2009), ‘Robotics Advancement through Web-publishing of Sensorial and Elaborated Extensive Data Sets (Project FP6-IST-045144).’. URL: http://www.rawseeds.org/rs/datasets Rosin, Paul L. (1999), ‘Measuring corner properties’, Computer Vision and Image Understanding 73(2), 291–307. 131 BIBLIOGRAPHY Rosten, Edward & Tom Drummond (2006), ‘Machine learning for high-speed corner detection’, European Conference on Computer Vision (ECCV) pp. 430–443. Rublee, Ethan, Vincent Rabaud, Kurt Konolige & Gary Bradski (2011), ORB: An Efficient Alternative to SIFT or SURF, in ‘IEEE International Conference on Computer Vision’, pp. 2564–2571. Rusu, Radu B., Zoltan C. Marton, Nico Blodow, Andreas Holzbach & Michael Beetz (2009), Model-based and learned semantic object labeling in 3D point cloud maps of kitchen environments, in ‘IEEE/RSJ International Conference on Intelligent Robots and Systems’, pp. 3601–3608. Sattler, Torsten, Bastian Leibe & Leif Kobbelt (2011), Fast image-based localization using direct 2D-to-3D matching, in ‘IEEE International Conference on Computer Vision (ICCV)’, pp. 667 –674. Schaffalitzky, Frederik & Andrew Zisserman (2002), Multi-view matching for unordered image sets, or ”How do I organize my holiday snaps?”, in ‘7th European Conference on Computer Vision-Part I’, ECCV ’02, Springer-Verlag, London, UK, UK, pp. 414–431. Sheikh, Yaser A., Erum A. Khan & Takeo Kanade (2007), Mode-seeking by Medoidshifts, in ‘11th IEEE International Conference on Computer Vision’, pp. 1–8. Silpa-Anan, Chanop & Richard Hartley (2008), Optimised KD-trees for fast image descriptor matching, in ‘IEEE Conference on Computer Vision and Pattern Recognition (CVPR)’, pp. 1–8. Sivic, Josef & Andrew Zisserman (2003), Video Google: A text retrieval approach to object matching in videos, in ‘IEEE International Conference on Computer Vision’, Vol. 2, pp. 1470–1477. Sivic, Josef & Andrew Zisserman (2009), ‘Efficient visual search of videos cast as text retrieval’, IEEE Transactions on Pattern Analysis and Machine Intelligence 31(4), 591 –606. Sj¨o¨o, Kristoffer, Dorian G´alvez-L´opez, Chandana Paul, Patric Jensfelt & Danica Kragic (2009), ‘Object search and localization for an indoor mobile robot’, Journal of Computing and Information Technology 17(1), 67–80. Smith, Mike, Ian Baldwin, Winston Churchill, Rohan Paul & Paul Newman (2009), ‘The new college vision and laser data set’, The International Journal of Robotics Research 28(5), 595– 599. URL: http://www.robots.ox.ac.uk/NewCollegeData Snavely, Noah, Steven M. Seitz & Richard Szeliski (2006), ‘Photo tourism: exploring photo collections in 3d’, ACM Transactions on Graphics 25(3), 835–846. Steder, Bastian, Giorgio Grisetti & Wolfram Burgard (2010), Robust place recognition for 3D range data based on point features, in ‘IEEE International Conference on Robotics and Automation’, pp. 1400 –1405. Strasdat, Hauke, J. M. M. Montiel & Andrew Davison (2010), Scale drift-aware large scale monocular SLAM, in ‘Proceedings of Robotics: Science and Systems (RSS)’. Szeliski, Richard (2010), Computer vision: Algorithms and applications, Springer, ISBN 978-184882-934-3. 132 BIBLIOGRAPHY Tenorth, Moritz, Alexander Perzylo, Reinhard Lafrenz & Michael Beetz (2012), The RoboEarth language: Representing and exchanging knowledge about actions, objects, and environments, in ‘IEEE International Conference on Robotics and Automation’, pp. 1284–1289. Torralba, Antonio, Kevin P. Murphy, William T. Freeman & Mark A. Rubin (2003), Contextbased vision system for place and object recognition, in ‘IEEE International Conference on Computer Vision’, pp. 273–280 vol.1. Triggs, Bill, Philip McLauchlan, Richard Hartley & Andrew Fitzgibbon (2000), Bundle adjustment – A modern synthesis, in ‘Vision Algorithms: Theory and Practice’, LNCS, Springer Verlag, pp. 298–375. Trzcinski, Tomasz, Vincent Lepetit & Pascal Fua (2012), ‘Thick boundaries in binary space and their influence on nearest-neighbor search’, Pattern Recognition Letters 33(16), 2173–2180. Tuytelaars, Tinne & Krystian Mikolajczyk (2008), ‘Local invariant feature detectors: a survey’, Foundations and Trends in Computer Graphics and Vision 3(3), 177–280. Tuytelaars, Tinne & Luc Van Gool (2004), ‘Matching widely separated views based on affine invariant regions’, International Journal of Computer Vision 59(1), 61–85. Valgren, Christoffer & Achim J. Lilienthal (2010), ‘SIFT, SURF & seasons: Appearancebased long-term localization in outdoor environments’, Robotics and Autonomous Systems 58(2), 149–156. Vargas, Manuel & Ezio Malis (2005), Visual servoing based on an analytical homography decomposition, in ‘44th IEEE Conference on Decision and Control, and European Control Conference. CDC-ECC ’05.’, pp. 5379–5384. Vasudevan, Shrihari, Stefan G¨achter, Viet Nguyen & Roland Siegwart (2007), ‘Cognitive maps for mobile robots-an object based approach’, Robotics and Autonomous Systems 55(5), 359– 371. Viola, Paul & Michael Jones (2001), Rapid object detection using a boosted cascade of simple features, in ‘IEEE Computer Society Conference on Computer Vision and Pattern Recognition’, Vol. 1, pp. I–511 – I–518 vol.1. Waibel, Markus, Michael Beetz, Raffaello D’Andrea, Rob Janssen, Moritz Tenorth, Javier Civera, Jos Elfring, Dorian G´alvez-L´opez, Kai Haussermann, J.M.M. Montiel, Alexander C. Perzylo, Bjorn Schiessle, Oliver Zweigle & Rene van de Molengraft (2011), ‘Roboearth’, IEEE Robotics Automation Magazine 18(2), 69–82. Werner, Felix, Joaquin Sitte & Frederic Maire (2012), ‘Topological map induction using neighbourhood information of places’, Autonomous Robots 32(4), 405–418. Williams, Brian, Georg Klein & Ian Reid (2007), Real-time SLAM relocalisation, in ‘11th IEEE International Conference on Computer Vision’, pp. 1–8. Williams, Brian, Mark Cummins, Jos´e Neira, Paul Newman, Ian Reid & Juan D. Tard´os (2009), ‘A comparison of loop closing techniques in monocular SLAM’, Robotics and Autonomous Systems 57(12), 1188–1197. Yang, Jun, Yu-Gang Jiang, Alexander G. Hauptmann & Chong-Wah Ngo (2007), Evaluating bag-of-visual-words representations in scene classification, in ‘International Workshop on Multimedia Information Retrieval’, MIR ’07, ACM, New York, NY, USA, pp. 197–206. 133 BIBLIOGRAPHY Zender, H., O. Mart´ınez Mozos, P. Jensfelt, G.J.M. Kruijff & W. Burgard (2008), ‘Conceptual spatial representations for indoor mobile robots’, Robotics and Autonomous Systems 56(6), 493–502. Zhang, Zhongfei & Allen R. Hanson (1996), 3d reconstruction based on homography mapping, in ‘ARPA Image Understanding Workshop’, pp. 0249–6399. 134