Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1998-07-31
2003-10-28
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C382S197000, C382S202000
Reexamination Certificate
active
06639593
ABSTRACT:
BACKGROUND
The invention relates to converting digital computer graphics involving the processing of raster and vector data.
In computer graphics, two basic forms of representation are used to define an image: raster and vector. In a raster representation, a bitmap specifies a set of pixel values at a set of raster positions to define an image. In this document, the term bitmap will include structures that have a bit depth greater than one in which pixels are defined by more than one bit of data; however, the bitmap will always be treated as binary, that is, each pixel position will be treated as being either on or off, image (foreground) or background. A bitmap generally has a rectangular structure. In a vector representation, resolution-independent vectors and their properties (such as fill pattern and color) define an image.
It is sometimes convenient or necessary to obtain a vector representation of one or more regions in a bitmap, for example to manipulate the shape of a bitmap region, to scale a bitmap region, to trap an object, or to clip a vector object against a bitmap mask. One method for obtaining a vector representation is to trace around the boundary of the bitmap object from pixel to pixel to create a closed contour, or polygon, corresponding to the bitmap object. However, such methods typically use the centers of traced pixels to generate the vertices of the polygon enclosing the region, and therefore can introduce as much as a half-pixel error in the conversion to a polygon. In many applications, this is an acceptable error. However, if a purpose of conversion is to use the polygon to clip another vector object, for example, and the polygon must be mapped to a new coordinate system, the half-pixel error can become several pixels in the new coordinate system. This several-pixel error may not be acceptable.
SUMMARY
In general, in one aspect, the invention provides methods, and apparatus implementing the methods, that provide useful resolution-independent representations of the perimeter of a bitmap object, that is, an object defined by pixels in a bitmap. In these methods, pixels are treated as having extent and edges that separate them from other pixels, and not as dimensionless points on a raster. In one implementation, the methods find the boundary pixels in a bitmap and identify each boundary pixel edge that actually contributes to the object perimeter. The contributing pixel edges will be one or more of the top, bottom, left, or right edges of the boundary pixels. Boundary pixels are non-object, or background, pixels that have one or more edges in common with object pixels. The methods distinguish objects that appear to share a common edge because they share boundary pixels, when in fact the objects are separated by a pixel width.
Implementations of the invention can include one or more of the following advantageous features. The polygon is encoded in a digital, compact, compressible format and stored on a computer-readable medium. The polygon is used to define traps in a vector-based trapping environment. The bitmap object has a hole and the invention provides a perimeter polygon enclosing the hole. Polygon edges are found using a finite state machine.
In general, in another aspect, the invention defines a polygon from a bitmap object by tracing around the bitmap; for each boundary pixel, identifying a pair of adjacent boundary pixels and determining the edges of the boundary pixel that contribute to the perimeter from the location of the pair of adjacent boundary pixels relative to the location of the boundary pixel; and accumulating the edges to define a polygon.
In general, in another aspect, the invention defines a polygon from a bitmap object by computing a sequence of direction codes based on tracing around a bitmap object; inputting sequentially each direction code to a finite state machine having a current state, each input causing the finite state machine to compute one or more edges of a polygon based on the current state and the direction code input, and each input causing the finite state machine to transition to a new state; and accumulating the identified object pixel edges to define the polygon.
In general, in another aspect, the invention generates a polygon from a bitmap object by tracing around the bitmap object along boundary pixels and generating a chain direction code for each boundary pixel, the chain direction code defining a direction from a current to a next boundary pixel around the bitmap object; using the chain direction codes generated, identifying the edges that contribute to the perimeter; and accumulating the identified perimeter edges to define a polygon corresponding to the perimeter of the bitmap object.
In general, in another aspect, the invention encodes a bitmap object by calculating a sequence of direction codes based on tracing around the bitmap object along the boundary, where each direction code represents a direction from an eight-connected pixel to an adjacent eight-connected pixel; inputting sequentially each direction code to a finite state machine having a current state, each input causing the finite state machine to calculate one or more boundary pixel edges that contribute to the perimeter based on the current state and the direction code input, and each input causing the finite state machine to transition to a new state; and storing the states to define a polygon.
In general, in another aspect, the invention provides a system, and a computer program, for converting a bitmap object to a polygon, the bitmap object having a boundary defining the perimeter of the bitmap object, where the system and program include a tracing module including instructions for causing a computer to trace around the boundary of the bitmap object and generate a plurality of chain direction codes where each chain direction code defines a direction from a boundary pixel to an adjacent boundary pixel; and a polygon generating module including instructions for causing the computer to identify for each boundary pixel one or more edges of the boundary pixel that contribute to the boundary based on two or more of the chain direction codes generated by the tracing module and to produce as output a polygon having an outline defined by the edges.
In general, in another aspect, the invention provides a system, a method, and a computer program implementing a technique for trapping mixed bitmap and vector objects in a vector-based trapping process. In the technique, the bitmap objects on a page (or a tile or band of a page) are converted to perimeter polygons, the polygons are planarized with the vector objects of the page (or tile or band), and the resulting planar structures are trapped.
In general, in another aspect, the invention provides a method of trapping an imagemask that includes identifying all of the perimeter edges of the imagemask; accumulating the identified perimeter edges to define a polygon; and defining traps for the polygon. The method can further include mapping the defined polygon to a device space, by applying an affine transform to one-unit vectors (X,
0
) and (
0
, Y) in a two-dimensional coordinate system and for each identified perimeter edge, accumulating one or more of the transformed vectors based on the identified perimeter edge.
In general, in another aspect, the invention provides a method for printing a page that includes an imagemask. The method includes defining the imagemask as a polygon, including identifying all of the perimeter edges of the imagemask and accumulating the identified perimeter edges to define the polygon, a perimeter edge being a pixel edge contributing to the perimeter of the imagemask; mapping the polygon to device space; filling the polygon; and rendering the page using the filled polygon.
In general, in another aspect, the invention provides a method of trapping a bitmap object having a perimeter against a vector object in a vector-based trapping system. The method includes constructing a polygon congruent to the perimeter of the bitmap object, including identifying pixels in the object
Adobe Systems Incorporated
Cao Huedung X
Vo Cliff N.
LandOfFree
Converting bitmap objects to polygons does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Converting bitmap objects to polygons, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Converting bitmap objects to polygons will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3143309