USING MONOCULAR VISION AND IMAGE CORRELATION TO ACCOMPLISH AUTONOMOUS LOCALIZATION A Thesis Presented to the Faculty of California Polytechnic State University San Luis Obispo In Partial Fulfillment of the Requirements for the Degree Masters of Science in Computer Science By Matthew P. Schlachtman June 2010 © 2010 Matthew P. Schlachtman ALL RIGHTS RESERVED ii COMMITTEEE MEMBERSHIP TITLE: Monocular Vision and Image Correlation to Accomplish Autonomous Localization AUTHOR: Matthew P. Schlachtman DATE SUBMITTED: June 2010 COMMITTEE CHAIR: Christopher M. Clark, Ph.D. COMMITTEE MEMBER: Franz Kurfess, Ph.D. COMMITTEE MEMBER: Saeed Niku, Ph.D. iii Abstract Monocular Vision and Image Correlation to Accomplish Autonomous Localization Matthew P. Schlachtman For autonomous navigation, robots and vehicles must have accurate estimates of their current state (i.e. location and orientation) within an inertial coordinate frame. If a map is given a priori, the process of determining this state is known as localization. When operating in the outdoors, localization is often assumed to be a solved problem when GPS measurements are available. However, in urban canyons and other areas where GPS accuracy is decreased, additional techniques with other sensors and filtering are required. This thesis aims to provide one such technique based on monocular vision. First, the system requires a map be generated, which consists of a set of geo-referenced video images. This map is generated offline before autonomous navigation is required. When an autonomous vehicle is later deployed, it will be equipped with an on-board camera. As the vehicle moves and obtains images, it will be able to compare its current images with images from the pre-generated map. To conduct this comparison, a method known as image correlation, developed at Johns Hopkins University by Rob Thompson, Daniel Gianola and Christopher Eberl, is used. The output from this comparison is used within a particle filter to provide an estimate of vehicle location. Experimentation demonstrates the particle filter's ability to successfully localize the vehicle within a small map that consists of a short section of road. Notably, no initial assumption of vehicle location within this map is required. iv Contents List of Figures ............................................................................................................................. vii 1 INTRODUCTION..................................................................................................................... 1 2 BACKGROUND ....................................................................................................................... 2 3 PROBLEM DEFINITION & SOLUTION ............................................................................ 9 3.1 Map Creation ............................................................................................................... 9 3.1.1 Video Capture ............................................................................................. 11 3.1.2 Grey Scale ................................................................................................... 11 3.1.3 Edge Detection ............................................................................................ 12 3.1.5 Map Image Selection .................................................................................. 13 3.2 Localization ................................................................................................................ 14 3.2.1 Video Capture ............................................................................................. 15 3.2.2 Grey Scale .................................................................................................... 16 3.2.3 Edge Detection ............................................................................................ 16 3.2.4 Correlation .................................................................................................. 16 3.2.6 Map Image Match Determination ............................................................... 16 3.2.8 Particle Filter ............................................................................................... 17 4 IMPLEMENTATION ........................................................................................................... 19 4.1 Implementation of Map Creation ................................................................................19 4.1.1 Video Capture ............................................................................................. 19 4.1.2 Video Editing .............................................................................................. 21 4.1.3 Grey Scale & Edge Detection ..................................................................... 22 4.1.4 Converting Video Format ............................................................................ 24 v 4.1.5 Image Extraction ......................................................................................... 25 4.1.6 Map Image Selection .................................................................................. 25 4.2 Localization ................................................................................................................ 26 4.2.1 Video Capture ............................................................................................. 27 4.2.2 Video Editing .............................................................................................. 27 4.2.3 Grey Scale & Edge Detection ..................................................................... 28 4.2.4 Converting Video Format ............................................................................ 28 4.2.5 Image Extraction ......................................................................................... 28 4.2.6 Image Correlation ....................................................................................... 29 4.2.7 Map Image Match Determination ............................................................... 34 4.2.8 Particle Filter ............................................................................................... 35 5 RESULTS ................................................................................................................................ 36 6 CONCLUSION ........................................................................................................................41 7 FUTURE WORK & POTENTIAL APPLICATIONS ........................................................ 42 Bibliography ............................................................................................................................... 43 Appendix A: ‘smooth_try3.m’ ................................................................................................... 45 Appendix B: ‘IP_PF_0.m’ ......................................................................................................... 46 vi List of Figures Figure 1: City Vs. Street Map ....................................................................................................... 10 Figure 2: Map Creation block diagram ......................................................................................... 10 Figure 3: Top down view of camera mounting configuration ...................................................... 11 Figure 4: Localization block diagram ........................................................................................... 15 Figure 5: Camera Mounted ........................................................................................................... 20 Figure 6: Route Map ..................................................................................................................... 21 Figure 7: Trim Tool ...................................................................................................................... 22 Figure 8: Grey scale Effect ........................................................................................................... 23 Figure 9: Canny Edge Detection ................................................................................................... 23 Figure 10: WinAVI Convert WMV to MPEG-2 .......................................................................... 24 Figure 11: IrfanView used to extract all frames ........................................................................... 25 Figure 12: Geo-Located Image Locations .................................................................................... 26 Figure 13: Geo-Located Image Four …........................................................................................ 26 Figure 14: Google Street View Map Image 4 ............................................................................... 26 Figure 15: Start of Driving Run .................................................................................................... 27 Figure 16: Visual Compare, 3rd Geo-located frame on left, Frame 587 from Localization Video on right ............................................................................................................................... 28 Figure 17: Pointing to the first image in a series .......................................................................... 29 Figure 18: Saving file list .............................................................................................................. 30 Figure 19: Select grid type ............................................................................................................ 31 Figure 20: Grid Selection .............................................................................................................. 31 Figure 21: Grid Resolution ........................................................................................................... 32 Figure 22: Automate Image Running ........................................................................................... 33 Figure 23: Visualize Data Menu ................................................................................................... 34 Figure 24: Image Correlation Strain ............................................................................................. 36 Figure 25: K(t) results for each geo-located image ....................................................................... 37 Figure 26: Initial State of Particle Filter ....................................................................................... 38 Figure 27: First Grouping at t = 95 ............................................................................................... 38 Figure 28: A bit of random dispersion at t = 955 ......................................................................... 39 Figure 29: Particle Filter Right after a good set of matches at t = 1055....................................... 39 Figure 30: Error Graph.................................................................................................................. 40 vii Chapter 1 INTRODUCTION One of the design objectives of computer vision localization is to provide a low cost method for outdoor localization using a single camera. [3] This relaxes the need for global positioning system (GPS), which may experience degraded reliability in urban settings like in downtown settings with more tall buildings that could block the signals from the GPS satellites from getting to the GPS receiver. It is possible to imagine TomTom or Garmin, both commercial GPS manufacturers, implementing a small camera on the GPS system that could be looking out in front of the car and perform the kind of visual localization that has been discussed. Moreover, this type of localization could be useful in the operation of future autonomous vehicles. The goal of this thesis is to demonstrate that by using a combination of existing technology, autonomous localization can be accomplished with a single camera obtaining images of the view outside of the car. This thesis intends on demonstrating that through the use of image processing, edge detection, and image correlation and comparison, one image can be compared with another, image from a database of geo-located images to determine the location of a vehicle. While only a proof of concept, the idea could be expanded on and can be adapted to serve real world purposes and potentiality a profitable idea or product. 1 Chapter 2 BACKGROUND Localization is the act of determining the location of an (autonomous) agent within a map given a priori. In almost every type of mobile robot system localization is necessary. Regardless of the size of the robot, the system will most likely need to know where it or something else is. Various aspects to robotics count on this ability, including but not limited to, robotic navigation. Success in navigation requires success at the four building blocks of navigation:  Perception - the robot must interpret its sensors to extract meaningful data from its environment  Localization - the robot must determine its position in the environment, or the position of some element of interest in the environment.  Cognition - the robot must decide how to act to achieve its goals.  Motion Control - to robot must modulate its motor outputs or other actuators to achieve the desired trajectory [2]. Autonomous vehicle localization can be accomplished with various different hardware and software components. There are several different families of hardware that can be used to accomplish localization. There are also algorithms to facilitate the localization using the various localization hardware types [1]. Some of the most popular are Markov Localization, Particle Filter Localization, and Kalman Filter Localization [1]. Markov localization uses an explicitly specified probability distribution across all possible robot positions [2]. Instead of maintaining a single hypothesis as to where in the world a robot might be, Markov localization maintains a probability distribution over the space of all such hypotheses. The probabilistic representation allows it to weigh these different hypotheses in a mathematically sound way [10]. For the sake of simplicity, let‟s assume that the space of robot positions is one-dimensional, that is, the robot can only move horizontally (it may not rotate). Now suppose the robot is placed somewhere in this environment, but it is not told its location. 2 Markov localization represents this state of uncertainty by a uniform distribution over all positions. Now let‟s assume the robot queries its sensors and finds out that it is next to a door. Markov localization can modify the belief by raising the probability for places next to doors, and lowering it anywhere else. Now let‟s assume the robot moves a meter forward. Markov localization incorporates this information by shifting the belief distribution accordingly. To account for the inherent noise in robot motion, which inevitably leads to a loss of information, the new belief more evenly distributes likelihoods across all robot states (and less certain) than the previous one. Finally, let‟s assume the robot senses a second time, and again it detects another door. At this point, the belief is updated to again increase likelihoods of all states next to the doors [10] [11]. The particle filter is an implementation of the Baye‟s filter using a finite number of particles in the continuous state space to describe the belief state probability density distribution. The algorithm propagates particles through time using the survival of the fittest concept [3]. The main objective of particle filtering is to track a variable or interest as it evolves over time, typically with a non-Gaussian and potentially multi-modal probability density function. The basics of the method are to construct a sample-based representation of the entire probability density function. A series of actions are taken, each one modifying the state of the variable of interest according to some model. Moreover, certain observations can constrain the state of the variable of interest at that time [9]. Multiple particles of the variable of interest are used, each one with an assigned weight that signifies the likelihood of that specific particle. An estimate of the variable of interest can be obtained by the weighted sum of all of the particles. Like most localizations algorithms, the particle filter algorithm is recursive in nature and operates in two phases; prediction and correction. After each action, each particle is modified according to the existing model (prediction stage), including the addition of random noise in order to simulate the uncertainty in the model. Then, each of the particle‟s weight is evaluated based on the latest sensory information available (update/correction stage). Particles with high weights have a higher likelihood of remaining when the resampling occurs [9]. 3