Patent ID: 6173075
Filing Date: 2001-01-09
Classification: G06K

Abstract:
A computer-implemented method for converting a raster of pixels representing a drawing into a set of vectors representing the drawing, where each pixel in the image has a color of either non-white or white, comprising the steps of:(a) creating closed loops by considering the pixels in the image in a scan order, and performing the following steps in substantially the following order:(1) if a current pixel is not an edge pixel, advancing to the next pixel in the scan order and either repeating this step (a)(1) or, if the scan order is exhausted, terminating step (a);(2) otherwise, beginning a stroke from the current pixel, the stroke having a head end and a tail end;(3) finding the direction of the counterclockwise-most white neighbor of the current pixel beginning from an initial direction;(4) selecting as the edge direction the direction resulting from one advance counterclockwise from the direction found in the preceding step;(5) marking the current pixel as not edge and visited in general, and as visited from the edge direction;(6) turning the edge direction one step clockwise;(7) if a neighbor pixel in the edge direction is white, adding a vector connecting the current pixel and the white neighbor pixel to the tail end of the stroke and returning to step (a)(5);(8) if the neighbor pixel in the edge direction is not an edge pixel and has not been marked as visited, returning to step (a)(5);(9) if the neighbor pixel in the edge direction has not been marked as visited, making the neighbor pixel the current pixel, turning the edge direction 180.degree., and returning to step (a)(5);(10) connecting the head end and the tail end of the stroke to form a closed loop; and(11) adding the closed loop to an ordered loop list;(b) starting at the beginning of the loop list, performing the following steps to build ink art regions:(1) for each loop in the loop list, computing the signed area defined by the current loop, and if the area is positive, adding the current loop to an ordered ink art list as an ink art region;(2) otherwise, marking the current loop as a hole and searching the ink art list for the first ink art region that contains any point of the current loop and adding the current loop as a hole to such first ink art region;(c) for boundary points of the ink art regions, generating a set of links, one link between each pair of nearest neighbor boundary points;(d) from the set of links, generating a set of interior links, being those links that pass through an interior portion of some ink art region;(e) identifying as joint triangles those triangles formed entirely of interior links;(f) generating a set of connected color art vectors from a set of points consisting of at most one interior point of each interior link; and(g) generating color art vectors to join an interior point of a joint triangle to an interior point of each interior link that forms the joint triangle.