One of the first steps needed to extract information from images for most machine vision applications is the segmentation of the image. We present a new segmentation algorithm for color images that combines both color space and spatial information. The algorithm is oriented to images that should exhibit clustering of the color space data, such as images of paper-based maps. The algorithm separates edge pixels from those in smooth regions and applies different segmentation algorithms to each group. The pixels in smooth regions are used to segment the color space using a histogram analysis technique. These regions are then grown into the edge regions to classify the edge pixels. The algorithm is robust and fast, as verified by experimental results.