Patent ID: 7809165

Claim:
A method for generating a distance map from an image, the method comprising the steps of: arranging a set of pixels in the image in a Euclidian n-space, the set of pixels including a subset of background pixels and a subset of foreground pixels; storing the distance map, wherein the distance map includes a distance value for every corresponding background pixel to a nearest foreground pixel; defining a set of scan lines having different directions, in which the different directions are effected by rotating the image; and scanning the set of pixel along each scan lines by moving from a current pixel to a next pixel along the scan line, the scanning for each scan line further comprising the steps of: making the next pixel the current pixel; initializing a counter to zero when the current pixel is one of the foreground pixels; incrementing the counter by one when the current pixel is one of the background pixels only if the counter has been initialized; and assigning the counter as the distance corresponding to the current pixel if the current pixel is one of the background pixels, and repeating beginning with the making step.