Approximate Subgraph Isomorphism for Image Localization (Author's Manuscript)
Abstract
We propose a system for user-aided image localization in urban regions by exploiting the inherent graph like structure of urban streets, buildings and intersections. In this graph the nodes represent buildings, intersections and roads. The edges represent logical links such as two buildings being next to each other, or a building being on a road. We generate this graph automatically for large areas using publicly available road and building footprint data. To localize a query image, a user generates a similar graph manually by identifying the buildings, intersections and roads in the image. We then run a subgraph isomorphism algorithm to find candidate locations for the query image. We evaluate our system on regions of multiple sizes ranging from 2km squared to 47km squared in the Amman, Jordan and Berkeley, CA, USA. We have found that in many cases we reduce the uncertainty in the querys location by as much as 90 percent.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 18, 2016
- Accession Number
- AD1040021
Entities
People
- Avideh Zakhor
- Christopher Dinh
- Jerry Chen
- Jordan Zhang
- Matthew Clements
- Vaishaal Shankar
Organizations
- University of California, Berkeley