Localization is the process of determining the pose of the robot in an environment from sensory information and some sort of map or representation of the environment. Localization systems have applications in mobile robotics, autonomous vehicles and driver assistance systems. This paper presents a vision based localization method suitable for use in large scale urban environments. The method builds upon existing Bag-Of-Words ~\cite{vgoogle, vocabTree} techniques to address specific challenges that arise in urban environments such as occlusions by vehicles and similarity in visual appearance between different locations. The method can be used as a local localization scheme if a priori information of pose is available or can be used as a global localization method.

In outdoor environments, GPS is widely used for localization as it provides a straightforward way to obtain fairly accurate position and velocity estimates. In urban environments buildings can block the visibility of satellites and reflect signals which can cause GPS localization to fail. Crowded urban spaces with many buildings and indoor environments where GPS is inaccurate or unusable tend to be rich in visual data. Thus vision based localization complements GPS well.

Vision based localization can be performed using image retrieval. An image taken from the robot's current pose is compared against a database of images taken from various poses in the environment to find the best matching image, as images coming from nearby poses in the environment tend to have similar content it can be inferred that the robot is near the pose at which the retrieved image was captured. One approach is to directly match local features (such as SIFT features ~\cite{Lowe04}) between the current view and each of the database images as done in ~\cite{ZhangKosecka06}. However, for large image databases this method is too slow and requires too much storage to be feasible.

Bag-Of-Words image retrieval techniques where images are modelled as collections of visual words can scale effectively to much larger image databases. In ~\cite{topo07} visual words are matched and verified geometrically for localization in an indoor environment. In ~\cite{Brown07City} BoW based image retrieval is used to perform localization from a side mounted camera in an urban environment. Instead of using a previously determined, fixed vocabulary, the visual vocabulary used is built by choosing words which are more informative for the localization process. This results in an increase in performance for a given vocabulary size but requires all the images to be available before the vocabulary is built. If images are added incrementally, the chosen vocabulary will be suboptimal. FABMAP ~\cite{fabmap} learns a generative model of the set of visual words  describing appearance of a scene. This model can be used to compute the similarity between the current view and database images and also determine the probability of the images having come from the same location which allows it to handle environments where spatially seperated locations are highly similar in appearance.

While navigating through an urban environment many dynamic objects such as other vehicles and pedestrians will be visible. These dynamic objects can occlude the scene and corrupt localization results. Our method uses geometric inferencing to detect moving objects and filter out the features they generate. The resulting filtered sets of visual words are used for localization. Urban areas also contain many structures and objects that appear repeatedly at different positions in the environment. Features in an image belonging to these common structures will be less informative for the purpose of determining robot pose. The method presented addresses this issue of non discriminative features by assigning weights to features on the basis of mutual information between robot pose and feature observation. Even though the current state of the art feature detectors generate good matches between image pairs, a large fraction of the features they detect are unstable to even small changes in viewpoint and are non repeatable. These unstable features will act like noise in the bag of words describing an image. They are unlikely to generate valid matches and could produce invalid matches with unrelated images in the image database. Our method addresses this problem by using closely sampled images instead of well seperated key images but only adding features that are stable to the database.   

The method presented was tested by attaching a camera to the top of a car recording a video sequence while driving along a path roughly 5km in length down city roads. Some examples of the images captured along the path are shown in figure ~\ref{fig:frame_traffic}. A localization database was built from the frames in this video and the algorithm was tested for both global localization and local localization by matching frames from two other runs along the same path to the database built from the training run. GPS readings were used to verify the correctness of the localization results. 

\subsection{Challenges and Solutions Adopted}


Large outdoor environments, urban environments in particular pose a number of challenges to a vision based localization system. The appearance of any outdoor environment will change over time. These changes could be short term changes caused by the changes in illumination conditions and movement of traffic or pedestrians or long term changes caused by alterations in buildings etc in the environment. Some of the challenges are illustrated in figure ~\ref{fig:frame_traffic}. The image on the left shows an example where a large portion of the robot's viewpoint is occupied by dynamic objects like vehicles. If these dynamic objects are treated in the same manner as dynamic elements of the scene they can corrupt localization results. Either the dynamic objects can occupy so much of the scene as to block out the actual scene causing localization too fail or they can be matched against similar dynamic objects seen in a different location resulting in incorrect localization. This problem can be tackled by using some method to detect dynamic objects and ignoring them while building an appearance model of the environment and/or during localization.

Another major challenge in urban environments is visual self similarity. Figure ~\ref{fig:frame_ambiguous} show two images that are highly similar in terms of content that were captured from poses that are widely separated. Such pairs of images will generate very similar sets of visual features. Under such circumstances it becomes important to focus on features that are unique to a location and will thus help differentiate between otherwise similar looking places. For example, in the image pair shown, the left image contains buildings on the horizon and the image on the right features a large spool. When attempting to discern between similar image pairs, features arising from objects like these that are visible in one image but not in the other are more informative for localization than common features shared by both images.

Although current state of the art feature detectors ~\cite{mser,Lowe04,surf06} generate features with good robustness to illumination variations and distortions resulting from changes in viewpoint, only a few features detected in an image will not be matched against those extracted from images taken from other nearby poses. The majority of the features will be unstable and non repeatable. These unstable features will act like noise in feature set extracted from an image. They are unlikely to generate valid matches and could produce invalid matches with unrelated images in the localization database. Removing these features would reduce database size and retrieval time while not negatively impacting localization performance.

In this chapter the motion of features in the video sequence is analyzed to detect dynamic scene elements like pedestrians and vehicles. Neighboring frames in the training video sequence are used to determine which features are stable to small changes in viewpoint. Only stable features which are determined to be from static parts of the scene are used for localization. Knowledge of the visual feature distributions acquired from the training sequence is used in conjunction with a prior estimate of the robot position (generated by previous localization results) to assign weights to features proportional to how informative they would be for localization. The weight generating scheme can also be used with a flat pose prior when no a priori information is available about robot pose. These weights help the robot localize even when the environment contains different locations that have similar visual appearance. 
 
\section{Related Work}

The use of visual data for robot localization has been studied extensively. One of the earlier successful implementations of a vision based localization is ~\cite{Fox99montecarlo} where a robot equipped with a camera pointed directly upwards was able to use ceiling illumination values to determine its location using Monte Carlo filtering methods.

Many vision based localization systems make restrictive assumptions about the environment. ~\cite{urbnavCipolla} which uses images of building facades to localize in an urban environment. The underlying assumption is that all images used contain a dominant plane, this makes it difficult to automate the process of building a visual database of an environment. 

Royer et al. ~\cite{Royer04} describe a monocular vision localization system which is presented as a preliminary vision based alternative to satellite based GPS localization. Keyframes are extracted from a video sequence of the robot's route / environment is used to build a three dimensional reconstruction of the environment. Localization is performed by extracting keypoints from the current camera view and matching them to each keyframe image. The frame with the largest number of matches is chosen and the exact position of the robot is determined from image point to 3D world point correspondences using Grunert's pose estimation algorithm. Although this method is effective and returns the metric pose of the robot it requires a computationally expensive reconstruction with complexity that is superlinear in the length of the video sequence. Also the current view needs to be matched against each of the keyframes which may not be feasible for use in real-time in large environments.

Qualitative localization methods have the advantage of not needing any metric modeling of the environment as they work directly upon the images themselves. Since qualitative localization involves finding previously seen images that are similar to the current view of the robot, methods for qualitative localization draw on those used for content based image retrieval. Features of some sort are extracted from the current view image and compared to those stored using a suitable similarity measure. The approaches can be divided into two broad classes depending on the type of features used, those that use global descriptors of the image as features and those that use local descriptors. Colour histograms ~\cite{histolocal} are simple global descriptors that have effectively been applied to robot localization, but they tend to give rather coarse results. The use of dimensionality reduction techniques to generate lower dimensional image representations that can be used for localization have also been studied. ~\cite{pcalocal} uses kernel principal component analysis to generate global features. In ~\cite{fourierlocal}, Fourier domain analysis of images captured by an omnidirectional camera was used to generate a Fourier signature that was used for localization.

Local features tend to be more robust to occlusions and changes in viewpoint. The successful use of local features in image retrieval applications motivated investigation of their applicability to qualitative robot localization. One approach would be to directly match local features (such as SIFT descriptors) between the current view and each of the stored images as done in ~\cite{ZhangKosecka06}. This provides accurate results but because the descriptors extracted from the current view need to be matched against descriptors from all the stored images, the method does not scale well to large sets of images.

The Bag-of-Words (BoW) approach ~\cite{vgoogle} of modeling an image as a collection of quantized local feature descriptors called visual words has made it possible to perform efficient and accurate image retrieval over large image sets. In ~\cite{topo07}, a BoW representation of the current view is built and the number of words it shares in common with each stored image is determined using an efficient inverted file data structure. For the images with the highest number of matches, geometric validation of the matches is performed by attempting to fit a homography. Any image with a large number of geometrically validated correspondences is returned as a good localization result.

In ~\cite{Brown07City} BoW based image retrieval is used to perform qualitative localization from a side mounted camera in an urban environment. Instead of using a fixed vocabulary, the visual vocabulary used is built choosing words which are more informative for the localization process. This results in an increase in performance for a fixed vocabulary size but requires all the images to be available before the vocabulary is built. If images are added incrementally, the chosen vocabulary will be suboptimal.

FABMAP ~\cite{fabmap} is a localization method designed to detect when a robot has returned to a previously visited location for loop closure. FABMAP handles sensory aliasing of visual data, the fact that two places separated by a large distance may be similar in appearance. A generative model for the bag of words extracted from an image is learnt. This model is used in a Bayesian framework to determine the probability of the current view coming from a pose near that of a previously captured image. Similar looking, highly distinctive views are given high probabilities of being from the same place while views that tend to appear frequently in the environment are given lower scores.
