The purpose of image-map registration is to revise the digital map included in Geographic Information System (GIS) with aerial image. The traditional method for this task requires the manual selection of tie points in both image and map. In this study, we propose a distance measure named Voting Weighted Modified Hausdorff Distance (VWMHD) for this task. In order to overcome the differences in representations between image and map in urban area, after several times of edge extraction through multiscale space, we give weights to each edge point in the initial scale based on its voting times and then compute the VWMHD for registration. The experimental results implicate that our VWMHD can provide sufficient information for automatic image-map registration and is robust to noises.