Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1995-08-30
2001-01-09
Tadayon, Bijan (Department: 2721)
Image analysis
Pattern recognition
Feature extraction
C382S164000
Reexamination Certificate
active
06173075
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to computer-based systems that scan hand-drawn drawings into a computer and process them. More particularly, it relates to systems that scan hand-drawn cartoon animation and prepare the scanned drawings for computer-performed processing, including inking, painting, and camera tasks.
2. Background
The traditional manual process for preparing cartoon animation begins with hand-drawn animation, typically pencil on paper. The drawings then go through a three-step process before they appear on film.
The first step is “ink”. The lines of the pencil drawings are traced onto the front of clear plastic acetate sheets (called cels) with one or more colors of ink. If a completely black line is acceptable, the drawings are often photocopied onto the cel. In either case, the result is a solid, opaque line.
The second step is “paint”. After the front of the cel is inked, the drawing is filled in on the back of the cel with various colors of paint.
The third step is “camera”. All the painted cels for a particular frame are stacked and photographed to generate the final frame.
This traditional, three-step, manual process of inking and painting cels has a number of drawbacks. It is very labor intensive. It is difficult to avoid painting errors, such as painting a region the wrong color on one cel, and painting errors are time consuming to fix. It is very labor intensive to make a widespread color change. The cels are not completely transparent, so colors on lower cels in a final frame appear darker and desaturated. And a cel will get dusty and dirty, and that dirt appears visually in the final frame if the cel is not cleaned each time it is used.
In recent years, several computer-based systems have been developed to address the drawbacks of the manual ink-and-paint process. One such system is the USAnimation System, available from USAnimation, Inc. of Hollywood, Calif. Generally, such systems scan the original pencil drawings into the computer, and then perform the ink, paint, and camera tasks on the computer. The USAnimation product reduces the line art to vectors representing the center of the line art. These vectors—the “color art” —are found by pixel operations, using three separate copies of the image pixmap. With a drawing on standard 16 by 12 inch paper scanned at 300 dots per inch, the size of each pixmap exceeds 17 million bits. The line art polygons are then formed as a set of vector polygons, each polygon being formed around one unbroken, branchless section of the color art. The result of this process is illustrated in
FIG. 1A
, which shows a drawn “Y” digitized into a bitmap, and
FIG. 1B
, which shows the three regions of line art
102
,
104
, and
106
created by the USAnimation product from the bitmap of FIG.
1
A.
Many such systems scan the pencil drawing as a pixmap with various levels of gray, so the scanned line has a soft edge. A “pixmap” is a data structure storing an image in pixel representation. A pixel is a picture element; if one thinks of a picture as a raster of points, a pixel is a point. In a pixmap, a pixel will have one or more bits of information, the number of bits being referred to as the “depth”, which bits may represent gray scale or color information.
Generally, the lines of the pencil drawing in the pixmap are recolored to reflect the required ink color, and the appropriate regions of the pixmap are painted. Then, these digital cels are layered in the computer through a digital compositing process and written to an appropriate medium, such as video tape or film.
Such a digital process has a number of advantages over the manual process. It is less labor-intensive because computer paint programs allow for greater productivity than processes using physical ink and paint. Fixing paint errors on a computer is quick and easy. Widespread color changes in ink or paint can be implemented with minimal labor. Digital cels are completely transparent, so there are no problems with color shifts, and therefore no inherent limit in the complexity of the cartoon. Dirt specks picked up in the scanning process are easily eliminated from the digital cels and never reappear.
However, in such systems, a new set of issues arises and some old problems still exist.
First, the resolution of the pixmap is determined at scanning time. In order to avoid digital artifacts, it is necessary that the scanning resolution for a cel be as large or larger than the output resolution multiplied by the most extreme truck (or amount of zoom in) for that cel.
Second, the effort and computer resources required to ink and to paint increase with the scanning resolution.
Third, painting errors are still difficult to prevent and detect. The pixmap for a digital cel is relatively large, requiring a significant amount of computer memory in the paint program. If there is not enough memory available to store more than a few cels at a time in the paint program's memory, it may be difficult to see the cartoon animate in order to detect painting errors.
And fourth, the ink may retain the variable density of the original pencil line in subsequent digital processing, a departure from the look of traditional animation.
SUMMARY OF THE INVENTION
In general, in one aspect, the invention provides a computer-implemented method for converting a pixmap representing a drawing into a set of vectors representing the drawing. The method includes forming or tracing closed loops of points or vectors around boundaries between edge and non-edge pixels in the pixmap; identifying each loop as defining an outer perimeter or as defining a hole associated with some particular outer perimeter; and for each outer perimeter, identifying as an ink art region an are a defined by an outer perimeter minus any areas defined by any holes associated with the outer perimeter. In another aspect, the method includes creating a color art graph of vectors within an ink art region, the color art graph extending substantially to all extrema of the ink art region and separately enclosing all holes within the ink art region. In another aspect, the method includes creating a central ink art region at the join of a “Y” shape where a part of an ink art region forms such a shape. In another aspect, the central ink art region is formed by calculating the Delaunay triangulation of points defining the boundary of the ink art region and then defining the central ink art region as corresponding to a Delaunay triangle all of whose sides are interior to the original ink art region. In another aspect, the method includes closing gaps between dangling ends of the color art graph. In another aspect, the method includes extending a dangling end of the color art graph to join a nearby section of the same or a different color art graph. In another aspect, the method includes distinguishing loops by their clockwise or counterclockwise orientation. In another aspect, the method includes distinguishing loops by the signs of their areas.
In another aspect, the method includes creating a color art graph by creating a set of interior vectors and taking a non-end point of each interior vector as an end point to a color art vector within an ink art region. In another aspect, the method includes creating a pixmap by scanning a drawing into a computer with an optical scanner to obtain a scanned raster of pixels representing the drawing. In another aspect, the method includes removing pixels.
In another aspect, the method includes smoothing a closed loop and, in another aspect, doing the smoothing by moving end points of closed loop vectors toward a weighted average of their positions and their neighboring points' position. In another aspect, the method includes means for filtering vectors by replacing sequential and approximately colinear vectors with a resultant vector.
In another aspect, the method includes smoothing a color art graph, including, in another aspect, smoothing by moving points of color art vectors toward a weighted average of their positions and their neighboring points&a
Fish & Richardson P.C.
Tadayon Bijan
USAnimation, Inc.
LandOfFree
Drawing pixmap to vector conversion does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Drawing pixmap to vector conversion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Drawing pixmap to vector conversion will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2448413