While watermarking algorithms have been developed for many types of digital content, little work has been done to develop watermarking algorithms for the class of map and chart images, despite their relative value. These images are generally of high resolution, have large areas of homogeneous pixels and are color-mapped or binary. These characteristics impede the use of watermarking algorithms designed for continuous-tone photographic images. This paper presents a novel blind watermarking algorithm designed for map and chart images. The algorithm segments the image into homogeneous regions and adds multiple watermark signals to the locations of the pixels on the boundary of several regions. The presence of these signals in the watermarked image is determined using a correlation-based detector. The watermarks can be detected in the presence of synchronization errors such as those incurred by cropping the image, or shifting by several columns or rows, and in the presence of noise. The algorithm is designed to efficiently process typical map images, which can have resolutions on the order of several 100 million pixels.