Back to results
US 2003/0193497 A1Published application
Converting bitmap objects to polygons
AssigneeAdobe Systems Incorporated
InventorStephan R. Yhann
Life of this patent
Estimating the term…
Loading patent…
Loading patent…
AssigneeAdobe Systems Incorporated
InventorStephan R. Yhann
Estimating the term…
Methods, and apparatus implementing the methods, that provide useful resolution-independent representations of the perimeter of a bitmap object. The methods find the boundary pixels in a bitmap and identify each boundary pixel edge that actually contributes to the object perimeter. 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. The polygon can be encoded in a digital, compact, compressible format, and can be used to define traps in a vector-based trapping environment. A finite state machine for generating the polygon is disclosed. A bitmap object is encode 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. In another aspect, the invention provides a technique for trapping mixed bitmap and vector objects in a vector-based trapping process. The bitmap objects on a page are converted to perimeter polygons, the polygons are planarized with the vector objects of the page, and the resulting planar structures are trapped.
A method for generating a polygon from a bitmap object defined by object pixels, each of the object pixels having edges shared with adjacent pixels, the method comprising:
A computer-implemented method of defining a bitmap object as a polygon, the bitmap object having a boundary defining the perimeter of the bitmap object where the boundary includes one or more boundary pixels having one or more edges that contribute to the perimeter, the method comprising:
A method of defining a polygon from a sequence of direction codes, each direction code representing a direction from an eight-connected pixel to an adjacent eight-connected pixel, comprising:
A method for generating a polygon from a bitmap object, the bitmap object having a boundary defining the perimeter of the bitmap object where the boundary includes one or more boundary pixels having one or more edges that contribute to the perimeter, the method comprising:
A method of encoding a bitmap object, the bitmap object having a boundary defining the perimeter of the bitmap object where the boundary includes one or more boundary pixels having one or more edges that contribute to the perimeter, the method comprising:
A computer program tangibly stored on a computer-readable medium for converting a bitmap object to a polygon, the bitmap object having a boundary defining the perimeter of the bitmap object where the boundary includes one or more boundary pixels having one or more edges that contribute to the perimeter, the program comprising:
A computer-implemented method of trapping an imagemask, comprising:
A computer-implemented method of trapping a bitmap object, the bitmap object having a boundary defining the perimeter of the bitmap object where the boundary includes one or more boundary pixels having one or more edges that contribute to the perimeter, the method comprising:
A method for printing a page including an imagemask, comprising:
A method of trapping a bitmap object having a perimeter against a vector object in a vector-based trapping system, comprising:
Dependencies are inferred from the claim text.
Drawings are temporarily unavailable. Open the PDF at USPTO
From the US filing history. Foreign family members aren’t listed.
Backward citations are indexed for grants only.
Segmentation; Edge detection: edge detection
Segmentation; Edge detection: involving edge growing; involving edge linking
Image data processing or generation, in general
Term end not estimated
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.
FIGS. 1A and 1B are illustrations of objects in a bitmap including object, boundary, and background pixels.
FIGS. 2A through 2B are a flow chart of a method for converting a bitmap object to a polygon.
FIG. 3 is an illustration of a pixel with directional arrows corresponding to the eight chain directions to adjacent pixels.
FIGS. 1A and 1B show bitmap objects 102 and 104 (object 104 is defined to be all of the object pixels, or “on” pixels, in the bitmap) in a bitmap that includes object or foreground pixels 108, 116 that contribute to an object and background pixels 110, 118 that are not part of any object. The background pixels 110, 118 include boundary pixels 112, 120 at the boundary of bitmap objects 102 and 104, respectively. Each boundary pixel 112 has one or more edges 114 in common with an object pixel and contributing to the perimeter of the object.
As shown in FIGS. 2A and 2B, a process 202 implements methods in accordance with the invention for converting a bitmap object to one or more polygons in which the edges of pixels contributing to a perimeter of the bitmap (interior or exterior) object are identified and accumulated to produce a polygon that is identical to the perimeter of the bitmap object.
The process receives a bitmap object, such as object 102 of FIG. 1A (step 204). The process finds a starting boundary pixel on the perimeter of the object (step 206) and then traces around the boundary of the object by following the boundary pixels. At each boundary pixel, the process determines the direction to the next boundary pixel and what edges of the boundary pixel contribute to the perimeter of the object, as will now be described.