Computer graphics processing and selective visual display system – Computer graphics processing – Attributes
Reexamination Certificate
2000-02-25
2003-05-13
Brier, Jeffery (Department: 2779)
Computer graphics processing and selective visual display system
Computer graphics processing
Attributes
C345S589000, C345S426000
Reexamination Certificate
active
06563509
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to creating a seeding map from a coverage map of a graphical object. The seeding map can be used to seed a Euclidean distance map (EDM) operation to create an EDM of the graphical object.
Current image processing systems seed EDM operations on a grayscale image with a seeding map having integer seed values. One system uses a threshold step to classify all the pixels of the grayscale image as feature pixels or background pixels. For an 8-bit grayscale image, for example, each pixel having a value greater than or equal to a threshold value of 128 is classified-as a feature pixel; each pixel having a value less than the threshold value of 128 is classified as a background pixel. To create the seeding map, the system assigns the feature pixels a first seed value and assigns the background pixels a second seed value. Typically, the first seed value is a minimum integer seed value for the seeding map, and the second seed value is a maximum integer seed value for the seeding map. Once created, the seeding map can be used to seed an EDM operation—a one-pass direct convolution operation or a two-pass distance propagation operation, for example—to create an EDM of the object. Due to the loss of the gray-scaling information during the threshold step, the EDM of the object can reflect aliasing or faceting at the edges of the object.
SUMMARY OF THE INVENTION
In general, in one aspect, the invention provides a method and apparatus, including a computer program apparatus, implementing techniques for creating a distance map of an image including a graphical object. The techniques include providing a seeding map of seed pixels having seed values, and using the seeding map to generate a Euclidean distance map. Each seed pixel can correspond to a region of the image. The seed values can include at least three different seed values. A first seed value for a seed pixel can correspond to a region of the image covered by the graphical object by no more than a first threshold amount. A second seed value for a seed pixel can correspond to a region of the image covered by the graphical object by no less than a second threshold amount. Each intermediate seed value for a seed pixel can correspond to a region of the image partially covered by the graphical object by an amount between the first and second threshold amounts.
Each seed pixel can correspond to a coverage pixel of a coverage map of the graphical object, wherein each coverage pixel has a coverage value. The seed value for each seed pixel can be calculated from the coverage value of the corresponding coverage pixel of the coverage map. The coverage map can be an alpha channel. The first seed value can be a minimum value for the seeding map and the second seed value can be a maximum value for the seeding map. Alternatively, the first seed value can be a maximum value for the seeding map and the second seed value can be a minimum value for the seeding map. Each intermediate seed value can be between the minimum seed value and a value representing a pixel-to-pixel distance in the Euclidean distance map. Each intermediate seed value can be a fractional value.
The seeding map can be used to seed a Euclidean distance map operation to generate the Euclidean distance map. The Euclidean distance map operation can be a one-pass direct convolution operation or a two-pass distance propagation operation. The Euclidean distance map can be used to create a frame around the graphical object. Alternatively, the Euclidean distance map can be used to create a glow to the graphical object.
Advantages that can be seen in implementations of the invention include one or more of the following. The invention can be used to create a seeding map having intermediate seed values representing the grayscale values of the pixels in a coverage map of the object. In the coverage map, the value of each coverage pixel generally indicates a degree of overlap or a degree of transparency. The system can seed an EDM operation with intermediate seed values to create an EDM with little or no aliasing at the edges of the object.
The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features and advantages of the invention will become apparent from the description, the drawings, and the claims.
REFERENCES:
patent: 4646154 (1987-02-01), Shinohara et al.
patent: 5684895 (1997-11-01), Harrington
patent: 5731820 (1998-03-01), Broekhuijsen
patent: 5835634 (1998-11-01), Abrams
patent: 5839090 (1998-11-01), Zoraster
patent: 5974172 (1999-10-01), Chen
patent: 5986673 (1999-11-01), Martz
patent: 6040835 (2000-03-01), Gibson
patent: 6141442 (2000-10-01), Chen
patent: 6329977 (2001-12-01), McNamara et al.
John C. Russ, The Image Processing Handbook, CRC Press, Inc., pp. 321-328, 436, 441 (1992).
Azriel Rosenfeld and Avinash Kak, Digital Picture Processing, Second Edition, vol. 2, Academic Press, pp. 204-211 (1982).
J. Christian Russ and John C. Russ, “Improved Implementation of a Convex Segmentation Alogrithm”, Acta Stereologica, vol. 7, pp. 33-40 (1988).
P. E. Danielsson, “Euclidian Distance Mapping”, Computer Graphics Image Processing, vol. 14, pp. 227-248, (1992).
Adobe Systems Incorporated
Brier Jeffery
Chung Daniel J
LandOfFree
Seeding map having intermediate seed values does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Seeding map having intermediate seed values, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Seeding map having intermediate seed values will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3079055