Approximate Subgraph Isomorphism for Image Localization (Author's Manuscript)
University of California, Berkeley Berkeley United States
Pagination or Media Count:
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.
- Theoretical Mathematics