Repositorio Institucional de Documentos

Abstract This thesis deals with the problem of indoor environment modelling using depth cameras. We propose a system that allows to traverse an environment with a hand held camera, and no other sensor, and compute a dense 3D textured geometric reconstruction. In the front-end, camera motion is computed by detecting interest points in the images and matching them across frames. We propose a loop closing or place recognition algorithm that is robust over time, and thus allows the system to reconsider past loop closing decisions once additional information becomes available. The backend of the system is the g2o graph optimization algorithm. We test our system both in simulations and with real data coming from a Kinect sensor. Results show that thus system is viable and precise. Our future goal is to incorporate robust outlier detection algorithms that will allow the system to ignore dynamic objects, such as people, and avoid the inclusion of these elements in the model. Contents 1 Introduction 2 1.1 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 StateoftheArt.......................... 3 2 The Proposed System 5 2.1 VisualOdometry ......................... 5 2.1.1 KeyFrames ........................ 7 2.2 Loop Closing over Time . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Hypothesis generation . . . . . . . . . . . . . . . . . . 8 2.2.2 Hypothesis verification . . . . . . . . . . . . . . . . . . 9 2.3 Global Pose Refinement . . . . . . . . . . . . . . . . . . . . . 12 3 Simulations 13 3.1 Simulations ............................ 13 4 Conclusions and Future Work 19 1 Chapter 1 Introduction 1.1 Problem Statement We live in a colorful and richly textured world. Our senses have evolved to make decisions about localization, navigation and recognition based on visual information perceived from our surroundings. Creating maps of the world for autonomous vehicles to enable them to make similar decisions has been an on going effort in the robotics community, where this problem is known as Simultaneous Localization and Mapping or SLAM for short. Efforts have been going on to create maps that make sense to robots and are therefore based on sparse features extracted from the environment such as laser scans or monocular cameras (Davison et al., 2007; Klein and Murray, 2009). On the other hand, techniques have been developed to create dense models of the environment (Newcombe et al., 2011; Henry et al., 2010). This project is an attempt at the second category. Building textured models of the world is an expensive task to undertake. While very precise 3D laser scanners are available, they are out of the reach of a normal person because of their cost. With the recent introduction of consumer grade depth cameras such as Microsoft Kinect (Microsoft, 2010), the task of building accurate 3D models is being explored by the robotics community both because of the affordable cost and the wide availability of the sensor. Building models of indoor environment presents a number of challenges. While nature is rich in texture, indoor environments tend to be planar and less textured. Moreover, due to artificial lighting, the illumination is not consistent even over a small distance. This makes local feature based algorithms very unstable. Visual similarity of structures makes the identification of previously visited places, known as loop closing, a difficult problem. A typical 2 case to consider is the hallways in a multi-storey building, which all may look the same. Only using visual information for loop closing can then lead to wrong loop closures that can adversely effect the accuracy of the model. 1.2 State of the Art Simultaneous Localization And Mapping (SLAM) is a well studied problem in the robotics community. Most of the initial algorithms were propose for a robot moving in a plane. More recently there has been a shift in the community towards vision based approaches and very robust system have been developed using monocular cameras as sensors. (Davison et al., 2007) developed a real-time SLAM system using a single camera. (Klein and Murray, 2009) developed a tracking and mapping system which works in real time but is limited to small work spaces. (Newcombe and Davison, 2010) proposed a dense mapping system using a single camera but it requires consistent illumination. Recently, a few systems have employed depth cameras for creating dense models. (Henry et al., 2010) proposed the first work utilizing such cameras. (Du et al., 2011) developed a mapping system that ensures coverage and robustness but requires user interaction. (Newcombe et al., 2011) proposed a dense mapping algorithm which works in real time using information from a depth camera. Very recently, (Izadi et al., 2011) demonstrated a real-time dense mapping system that takes into account the dynamic nature of the environment being mapped. One important aspect of SLAM is data association, the process to determine which features in the map correspond to each sensor measurement. For data association in general, (Neira and Tard´os, 2001) presented an algorithm that considers all the hypothesis jointly using an interpretation tree. (Civera et al., 2010) presented a hypothesis and test algorithm using one point in the dataset within a Kalman Filter framework. For loop closing in particular, (Olson, 2009) finds a subset of mutually consistent hypothesis from a set of proposed hypothesis using spectral clustering and (Sunderhauf and Protzel, 2011) detect and reject wrong loop closure using switch factors within a Pose Graph formulation while (Cadena et al., 2010) use Conditional Random Fields. In this work, we propose a system that can robustly model the 3D textured environment with the help of a customer grade depth camera. This work focuses on the problem of robust loop closing over time. Loop closing is an important module of any mapping system and helps in improving the accuracy of the map. We propose a method of selecting loop closure hypotheses that are consistent over time and therefore will get less “confused” in a 3 scenario stated above. The application of such a system is not restricted to efficient robotic navigation but can also be used to create models for object recognition and for making models of the environment for use in games and virtual worlds. 4 Chapter 2 The Proposed System Figure 2.1: System Overview Fig. 2.1 gives an overview of the complete system. As can be seen, we make a distinction between the front end and the back end of the system. The front end is responsible for providing the Visual Odometry and loop closure hypothesis. The back end selects loop closure hypothesis that are consistent with each other and incorporates them into the global pose refinement problem. In the following, we present a detailed account of the involved modules. 2.1 Visual Odometry Given motion commands, mobile robots provide an estimate of the actual motion carried out which is know as odometry. The estimation of motion with a visual sensor such as a camera is therefore termed visual odometry 5 (a) RGB Image (b) Depth Image (c) Resulting point cloud Figure 2.2: Data received from Kinect (Nist´er et al., 2004). For a robot restricted to a plane, the odometry consists of three degree of freedom (x, y, θ), while a handheld camera, has six degrees of freedom; three for rotation and three for translation. In monocular vision, visual odometry is a difficult problem to solve because of the scale ambiguity problem. A certain baseline needs to be traversed before we can calculate the depth of observed points for calculating the 3D rigid body transformation of the sensor. In case of depth cameras, this problem is readily solved because of the estimate of depth provided by the camera. The problem reduces to finding matching features between the two images, calculating the corresponding point in 3D and estimating the 3D rigid body transformation that reduces the reprojection error in the least square sense. This requires that the camera being used be calibrated. This work assumes that the camera being used to carry out VO is already calibrated. The information provided by Microsoft Kinect consists of two images, 6 one RGB and the other depth image as shown in fig. 2.2. The depth image contains the depth per pixel of the corresponding RGB image. Therefore, knowing the calibration parameters of the camera and the point in the RGB image, we can calculate the 3D location of a point. Given a point pi= [xi, yi,1]Tin an image and the calibration parameters fx, fy, cx, cywhere the depth of the point is di, the corresponding 3D point Pican be calculated using: Pi=di  1/fx−cx/fx 1/fy−cy/fy 1    xi yi 1  (2.1) Given at least three such points in two images, the 3d rigid body transformation can be calculated between the two images. Let P1,i be the point in the first image and P2,i be the corresponding point in the second image, with i= 1,2, . . . , n and n≥3. To calculate the rigid body transformation, we follow a hypothesis and test method based on (Horn, 1987). As a result we get a transformation T1 2= (R, t) consisting of rotation and translation such that P2,i ≈RP1,i +t. This rigid body transformation Tis the estimated motion between the two frames. For two consecutive such motion, T1 2and T2 3the overall pose of frame 3 is then given by T1 3=T1 2⊕T2 3. We assume the first frame to be the origin of the world and maintain all the poses with respect to the first frame. So the pose for any frame f is given by Tw fwhere wis the origin of the world. 2.1.1 KeyFrames Although visual odometry calculates the poses between every consecutive frames, we do not store all the frames, instead we take an approach commonly used in Keyframe based approach (Klein and Murray, 2008). We identify and store keyframes, i.e. intermediate frames from the image sequence where the number of tracked features fall below a certain threshold. When the system starts, we initialize new features in the image and track them in the subsequent images. As the camera moves along the trajectory, the number of tracked features decreases due to the change in the scene. When they fall below a threshold, this indicates the we have moved sufficiently far from our initial position and should now include this new information in the system. Therefore we initialize a new keyframe and introduce new feature into the system for tracking. The pose of this new keyframe is provided by the underlying visual odometry system. We also match features from this keyframe with the previous keyframe in order to use them in the global pose refinement step. 7 (a) All Hypothesis (b) Correct Hypothesis after optimization (c) Proposed Method (d) Proposed Method after optimization (e) Olson’s Method (f) Olson’s Method after optimization Figure 3.2: Lawn Mower Simulation - 50-50 14 (a) All Hypothesis (b) Olson’s Method (c) Proposed Method Figure 3.3: Lawn Mower Simulation - Needle in a hay stack 15 (a) Olson’s Method (b) Proposed Method Figure 3.4: Lawn Mower Simulation - 50-50 Statistics 16 (a) Olson’s Method (b) Proposed Method Figure 3.5: Lawn Mower Simulation - Needle in a hay stack Statistics 17 times with the same loop closure hypotheses to investigate the effect of noise on our method. In the first simulation, we generate the same number of correct and wrong loop closures. The simulated trajectory along with the generated loop closing hypothesis are shown in fig. 3.2a. Our method correctly identifies and rejects all the wrong loop closure hypothesis while (Olson, 2009) shows a tendency towards accepting false positives. Although it accepts all the correct hypotheses, at the same time, it accepts many false positives (fig. 3.2e. It has to be noted that in the case of a loop closing, a hypotheses wrongly accepted as being correct (false positive) is much more harmful than a correct hypotheses classified as being wrong (false negative). In that respect, our method is more robust to false positive, although we do reject some correct hypothesis 3.2c. The statistics for this scenario are given in fig. 3.4. All the plots represent ratios of the hypotheses accepted or rejected. In the second simulation (fig. 3.3), we simulate a very noisy front end hypothesis generator, that produces a lot of wrong hypotheses but very few correct hypotheses. We term this finding a needle in the hay stack. This would give us an idea of the performance of our algorithm in situations where only a few hypotheses are correct and drowned by a large number of wrong hypotheses. In this case as well, our method accepts no false positives and manages to find the few correct hypotheses most of the time (fig. 3.3c). Olson’s method either rejects all the hypotheses or accepts wrong hypotheses as being correct. Our method is able to correctly identify the two loop closures that are consistent with each other (encircled in fig. 3.3c). The statistics for the scenario are given in 3.5. These experiments show the superiority of our method in terms of robustness to false positives. Moreover, our method is able to discover the smallest possible consistent subset in a noisy set of loop closing hypothesis. 18 Chapter 4 Conclusions and Future Work We have presented a framework for mapping indoor environments using a depth camera and a state of the art graph optimization method as the backend with an effective loop closure verification system that can ensure the consistency of loop closures over time. We have also presented a comparison of our work with the start of the art loop closing over time method. Immediate future work is implementating the visual odometry system and a place detection algorithm to find loop closing candidates in the depth images and carry out an indoor experiment. We plan to submit the loop closing over time algorithm to the following conference: Twenty-Sixth AAAI Conference on Artificial Intelligence Special Track on Robotics Toronto, Ontario, Canada, July 22-26, 2012 In the planned system, the dense model of the environment is maintained as a point cloud, which is both inefficent in terms of memory and in its present state, can not be used for any decision making. For very large maps there will be a need to represent this point cloud in a more meaningful and effiecent way. One direction to take would be to represent the point clouds as voxels (Henry et al., 2010), which is a more efficent than point clouds. Another approach would be convert the point cloud into a mesh model and therefore reducing the number of point to be maintained in the map by a great factor. The current system makes the assumption that the environment being mapped is static and does not change over time. In future we would like to be able to deal with dynamic environment in the short term so the effects of people moving around or other dynamic agents can be detected and safely removed from the map. In the long term, we would like to detect the changes 19 the took place since the place was last seen. This could include removal or addition of objects in the scence. A typical case would be the constantly appearing or disappearing items on an office desk. Detecting such information would not only enable us to do better localization in a dynamic environment, but will also enable us to maintain accurate maps over long time. 20 Bibliography Angeli, A., D. Filliat, S. Doncieux, and J. Meyer (2008). Fast and incremental method for loop-closure detection using bags of visual words. Robotics, IEEE Transactions on 24(5), 1027–1037. Cadena, C., D. G´alvez-L´opez, F. Ramos, J. Tard´os, and J. Neira (2010). Robust place recognition with stereo cameras. In Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference on, pp. 5182– 5189. IEEE. Calonder, M., V. Lepetit, C. Strecha, and P. Fua (2010). Brief: Binary robust independent elementary features. Computer Vision–ECCV 2010, 778–792. Civera, J., O. Grasa, A. Davison, and J. Montiel (2010). 1-point ransac for extended kalman filtering: Application to real-time structure from motion and visual odometry. Journal of Field Robotics 27(5), 609–631. Davison, A., I. Reid, N. Molton, and O. Stasse (2007). Monoslam: Real-time single camera slam. Pattern Analysis and Machine Intelligence, IEEE Transactions on 29(6), 1052–1067. Du, H., P. Henry, X. Ren, M. Cheng, D. Goldman, S. Seitz, and D. Fox (2011). Interactive 3d modeling of indoor environments with a consumer depth camera. In Proceedings of the 13th international conference on Ubiquitous computing, pp. 75–84. ACM. Henry, P., M. Krainin, E. Herbst, X. Ren, and D. Fox (2010). Rgb-d mapping: Using depth cameras for dense 3d modeling of indoor environments. In the 12th International Symposium on Experimental Robotics (ISER). Horn, B. (1987). Closed-form solution of absolute orientation using unit quaternions. JOSA A 4(4), 629–642. 21 Izadi, S., R. Newcombe, D. Kim, O. Hilliges, D. Molyneaux, S. Hodges, P. Kohli, J. Shotton, A. Davison, and A. Fitzgibbon (2011). Kinectfusion: real-time dynamic 3d surface reconstruction and interaction. In ACM SIGGRAPH 2011 Talks, pp. 23. ACM. Klein, G. and D. Murray (2008). Improving the agility of keyframe-based slam. Computer Vision–ECCV 2008, 802–815. Klein, G. and D. Murray (2009). Parallel tracking and mapping on a camera phone. In Mixed and Augmented Reality, 2009. ISMAR 2009. 8th IEEE International Symposium on, pp. 83–86. Ieee. Kummerle, R., G. Grisetti, H. Strasdat, K. Konolige, and W. Burgard (2011). g2o: A general framework for graph optimization. In Robotics and Automation (ICRA), 2011 IEEE International Conference on, pp. 3607–3613. IEEE. Leutenegger, S., M. Chli, and R. Siegwart (2011, Nov.). Brisk: Binary robust invariant scalable keypoints. In Computer Vision (ICCV), IEEE International Conference on. Microsoft (2010). Microsoft kinect. http://www.xbox.com/en-US/kinect. Neira, J. and J. Tard´os (2001). Data association in stochastic mapping using the joint compatibility test. Robotics and Automation, IEEE Transactions on 17(6), 890–897. Newcombe, R. and A. Davison (2010). Live dense reconstruction with a single moving camera. In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, pp. 1498–1505. IEEE. Newcombe, R., S. Lovegrove, and A. Davison (2011). Dtam: Dense tracking and mapping in real-time. In Proc. of the Intl. Conf. on Computer Vision (ICCV), Barcelona, Spain, Volume 1. Nist´er, D., O. Naroditsky, and J. Bergen (2004). Visual odometry. In Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, Volume 1, pp. I–652. IEEE. Olson, E. (2009). Recognizing places using spectrally clustered local matches. Robotics and Autonomous Systems 57(12), 1157–1172. 22 Sunderhauf, N. and P. Protzel (2011, sept.). Brief-gist - closing the loop by simple means. In Intelligent Robots and Systems (IROS), 2011 IEEE/RSJ International Conference on, pp. 1234 –1241. Triggs, B., P. McLauchlan, R. Hartley, and A. Fitzgibbon (2000). Bundle adjustment a modern synthesis. Vision algorithms: theory and practice, 153–177. 23