In this dissertation, we propose novel methods for vision-based localization of moving platforms by registering perspective camera images to satellite maps using a Bayesian tracking framework. We present separate localization methods for stereo and monocular imagery. We propose a novel framework for semantic segmentation and labeling of videos by propagating labeling information from satellite maps to video frames. This approach generates accurate labeling of semantic elements without doing any prior learning on the video itself. In order to achieve these, we also investigate algorithms for estimating semantic labels from satellite map images. We mainly focus on labeling roads, buildings, sidewalks, and crosswalks from satellite images and we propose a novel technique to estimate sidewalks in satellite images that are occluded by trees. We also propose a novel geometric hashing method for efficient coarse localization of given aerial images using relative building structures. We perform our tests on a building dataset for very large city environment with 300K buildings and show that this method very efficiently generates accurate localization results.