Abstract:
Method and apparatus for rasterizing a resolution-independent page description for printing. A peeker (gap between two visible edges in vector representation that is narrower than a printer pixel) is identified between a first visible edge and a second visible edge, and a color adjustment is made to at least one of the edges. In one embodiment, a side of the second visible edge facing a side of the first visible edge is identified. The color of the identified side of the first visible edge is changed based on the color of the identified side of the second visible edge. The color adjustment is advantageous in connection with methods of trapping.

Description:
BACKGROUND OF THE INVENTION 
     The invention relates to modifying a color page described in a page description language so that the page can be correctly trapped. 
     In the printing industry, press registration is the accurate positioning of two or more colors of ink on a printed sheet. When the colors on a sheet are in register, all colors appear precisely where intended, without gaps between colors or overlap of colors. Misregistration can be caused by a number of factors, including errors in platemaking and film handling prior to platemaking, poorly-maintained printing presses or poorly-trained operators, paper inaccuracy or instability, and lack of environmental controls. One result of misregistration is unprinted paper showing through between colors, where no unprinted area was intended. Even a small registration error can result in a thin white line showing between colors on a sheet. 
     Trapping is the process of compensating for press misregistration by intentionally overlapping colors prior to printing. For example, a spread expands the color of a foreground image to overlap with the background color. Conversely, a choke enlarges the background color to overlap with the foreground image. The area of color added to create overlap, called a trap, provides a degree of protection against gaps created by misregistration. Although the trap color may be the same as the background or foreground color, it need not be. Trapping involves deciding where to place traps, and setting the size and color of traps so as to correct for possible misregistration while being minimally noticeable to the human eye. 
     It is conventional in the electronic publishing industry to design pages using a page description language (PDL), such as the Adobe® PostScript® language, to describe a page using resolution-independent elements. In PostScript, a path is a collection of ordered directed connected straight line segments, referred to as edges. A path, which appears as a shape on the page, must be closed. Each edge in a path has a “from point” and a “to point” which define the position and direction of the edge. The to point of an edge in a path is the same point as the from point of the subsequent edge in the path, and the to point of the last edge in the path is the same point as the from point of the first edge in the path. Edges in a path may intersect. 
     An object may consist of one or more paths, all filled or stroked in a single color. An object has a unique sequence number, also referred to as a z-order or paint order, that is shared by each of the paths in the object. The sequence number of an object specifies when the object will be drawn on the page in relation to other objects. The object with the lowest sequence number will be drawn first, followed by the object with the next lowest sequence number. This sequential drawing of objects may result in one object being partially or entirely occluded by other objects with higher sequence numbers. 
     To render a PostScript page (by which is meant a PostScript language description of a page) on an output device such as a printer, the page must first be rasterized, that is, the vector representation of the page must be converted into a two-dimensional array of pixels. The resolution of an output device is defined by the number of pixels on the output medium of the output device per unit distance or per unit area. 
     A PostScript page description may be analyzed to produce a new PostScript page description which contains traps. The new PostScript page description may then be used to render the page, with traps, according to conventional methods. Alternatively, the PostScript page may first be rasterized, after which traps are generated in rasterized form by analyzing the rasterized page. 
     SUMMARY OF THE INVENTION 
     A peeker is a gap between two edges in vector representation that is narrower than a device pixel at the resolution of the output device on which the vectors are to be rendered. The invention modifies a vector image to be rendered in rasterized form, so that traps may be correctly generated wherever peekers exist. In particular, the invention corrects vector space color transitions so that they match color transitions in rasterized form. 
     In one aspect, the invention prepares a resolution-independent representation of a region for trapping. Specifically, a peeker is found between a first edge in the region and a second edge in the region, and an abutting color that will abut a side of the first edge between the first edge and the second edge when the first edge is rendered in rasterized form is identified. The color of the first edge on the side of the first edge between the first edge and the second edge is then changed to the abutting color. The region is then trapped and rendered on an output device, such as a printer. 
     In another aspect, the invention identifies an exterior color of a resolution-independent edge in a path based on information derived from the interior colors of other edges in other paths. The exterior color so identified may then be advantageously used in peeker detection and color correction, and in trapping. 
     Among the technical advantages of the invention are one or more of the following. 
     One advantage of the invention is that it performs peeker color correction on objects while they are in vector form, prior to rasterization. This provides a basis for more accurate positioning of traps than trapping based on the rasterized page by itself. Also, because the invention provides a basis for resolution-independent trapping, pages which are trapped according to the invention may be rendered at a number of resolutions without the need for re-trapping. 
     A further advantage of the invention is that use of the vector representation preserves information about objects that is lost during rasterization, allowing more complete and varied processing of the edge table. 
     Furthermore, vector space is a more efficient representation of the rendered appearance of an area than raster space; a color transition many hundred pixels in length can be described in one small data structure in vector form. This storage efficiency is critical to obtaining high throughput and efficient trapping performance. 
     Other features and advantages of the invention will become apparent from the following description and from the claims. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a flow diagram of a method of the invention. 
     FIGS. 2 a - 2   b  are diagrams of PostScript paths. 
     FIG. 2 c  is a diagram of a PostScript path partially occluding another PostScript path. 
     FIG. 2 d  is a diagram of the visible and invisible edges resulting from the application of a hidden line removal algorithm to two PostScript paths within one tile. 
     FIG. 2 e  is a diagram of a PostScript path within a tile, and of a vector used to identify the exterior color of the PostScript path. 
     FIGS. 3 a - 3   c  are flow diagrams of methods used to identify the exterior colors and exterior sequence numbers of edges within a tile. 
     FIG. 4 a  is a diagram of two PostScript paths between which a peeker exists. 
     FIG. 4 b  is a diagram of a rasterization of parts of the two objects in FIG. 2 a  at the location of the peeker. 
     FIG. 5 is a flow diagram of Phase One of peeker detection and correction. 
     FIG. 6 a  is a diagram of a first peeker rectangle drawn around a first edge according to the method of FIG.  4 . 
     FIG. 6 b  additionally shows a second edge originating in the first peeker rectangle, and a resulting split point generated on the first edge. 
     FIGS. 7 a-f  are flow diagrams of Phase Two of peeker detection and correction. 
     FIG. 8 a  is a diagram of two peeker squares drawn around the endpoints of an edge longer than twice the peeker distance. 
     FIG. 8 b  additionally shows two additional edges, each of which has an endpoint in each peeker square. 
     FIG. 8 c  is a diagram of a peeker rectangle drawn around an edge whose length is less than or equal to twice the peeker distance. 
     FIG. 8 d  additionally shows an additional edge having both endpoints within the peeker rectangle. 
     FIG. 9 illustrates a computer and computer elements suitable for implementing the invention. 
    
    
     DETAILED DESCRIPTION 
     Referring to FIG. 1, a method for trapping a PDL page detecting and correcting peeker colors of the invention first obtains a resolution-independent description of a page (e.g., in PostScript format) (step  2 ), and then transforms the page description into a list of objects (step  4 ). The method then identifies and removes hidden edges from the page (step  6 ), and identifies the exterior color and exterior sequence number of each edge on the page (step  8 ). The method next identifies peekers using the vector representation of the objects on the page and information about the resolution at which the page will be rendered in rasterized form on an output device (step  10 ). 
     Then, the method changes the exterior color of each edge at which a peeker exists to the color which will abut the exterior side of the edge when rendered on the output device (step  12 ). This changes the color transitions between edges in vector space so that they match the color transitions between edges in rasterized form. 
     Finally, trapping is performed on the page, using the corrected color information, using any of a variety of trapping methods (step  14 ). 
     The method of FIG. 1 is now described in more detail. 
     Referring to FIG. 2 a,  a PostScript path  16  has ordered edges E 1 , E 2 , E 3 , E 4 , E 5 , E 6 , and E 7 . The first edge E 1  has a from point P 1  and a to point P 2 . The remaining edges, similarly, have from and to points which define the shape of the path  16  in a counter-clockwise direction, ending at point P 1 . As each edge of path  16  is traced from its from point to its to point, the interior of path  16  is defined to be on the left side of the edge; the exterior of path  16  is defined to be on the right side of the edge. Each edge in path  16  has an interior color that specifies the color on the interior (left) side of the edge. The interior color of each edge of path  16  is yellow, causing the interior of path  16  to appear yellow when rendered on an output device. 
     Referring to FIG. 2 b,  a PostScript path  18  has ordered edges E 8 , E 9 , E 10 , Ell, and E 12 . The first edge E 8  has a from point P 3  and a to point P 4 . The remaining edges, similarly, have from and to points which trace the path  18  in a counter-clockwise direction, ending at point P 3 . The interior color of each edge is magenta, causing the interior of path  18  to appear magenta when rendered on an output device. 
     Objects on a PostScript page may overlap. Therefore, some object edges may be obscured by other objects and may therefore not be visible when the page is rendered on an output device. If path  18  has a higher sequence number than path  16 , then the paths will appear as shown in FIG. 2 c  when rendered by an output device. As shown in FIG. 2 c,  part of the interior region of path  16  is occluded by part of the interior region of path  18 . Edges E 3 , E 4 , E 5 , and E 6  of path  16  are entirely occluded by path  18 , and parts of edges E 2  and E 7  of path  16  are occluded by path  18 . 
     A PostScript page is transmitted to a PostScript-capable device, such as a PostScript printer or imagesetter. A trapping engine transforms the PostScript page into a set of objects appearing on the page, using conventional methods. Each object consists of one or more paths sharing a common unique sequence number. 
     Each edge in a path has a number of attributes. Each edge has a from point and a to point, which define the position and direction of the edge. The original interior color and effective interior color of an edge are initialized to the value of the interior color of the edge. The owning or interior sequence number of an edge is the sequence number of the path to which the edge belongs. The original exterior color, effective exterior color, and exterior sequence number of an edge are described below. A child edge (described below) also contains a reference to the child edge&#39;s parent edge. 
     After the trapping engine transforms the PostScript page into a set of objects, the page is divided into small rectangular tiles. Although the invention will be described as operating on such tiles, it may also operate on a page which has not been divided into tiles. Each tile boundary has a from point, a to point, and an interior color. 
     The edges in a tile which will be visible when the page is rendered are recorded in an edge table. Referring to FIG. 3 a,  the trapping engine creates an empty edge table for a tile and adds the tile boundaries of the tile to the edge table (step  20 ). Next, the object o with the lowest sequence number in the tile is selected (step  21 ), and the original exterior colors of object o&#39;s edges are initialized to a value of unknown. The edges of object o are then added to the edge table (step  23 ). 
     A hidden line removal method is then applied to the edge table. The hidden line removal method splits each edge in the edge table into two smaller edges at each point at which the edge intersects an edge of another object. Each edge resulting from a split inherits the original interior color and interior sequence number of the edge from which it was derived. 
     For example, referring to FIG. 2 d,  edge E 2  of object  16  is split into edge E 13  (with endpoints P 2  and P 7 ) and edge E 14  (with endpoints P 7  and P 5 ), because edge E 2  crosses a boundary of object  18  at point P 7 . Similarly, edge E 7  of object  16  is split into edge E 15  (with endpoints P 6  and P 8 ) and edge E 16  (with endpoints P 8  and P 1 ) because edge E 7  crosses the boundary of object  18  at point P 8 . 
     A complex point is a point at which more than two visible edges intersect. Referring to FIG. 2 d,  for example, point P 7  is a complex point. A spline is a contiguous series of connected edges which do not cross an object boundary. A spline either begins and ends at a complex point or begins and ends at a single point. The hidden line removal method divides each object into splines, and identifies each of the edges of each object as being either visible or invisible. The edges of each invisible spline are then removed from the edge table. 
     For example, as a result of applying the hidden line removal method to the tile containing object  16  and object  18 , object  16  is divided into two splines: one spline (S 1 ) consisting of edges E 13 , E 1 , and E 16 , and one spline (S 2 ) consisting of edges E 14 , E 3 , E 4 , E 5 , E 6 , and E 15 . Similarly, object  18  is divided into two splines: one spline (S 3 ) consisting of edges E 21  and E 17 , and one spline (S 4 ) consisting of edges E 18 , E 19 , and E 20 . Splines S 1 , S 3 , and S 4  are visible, as shown in FIG. 2 c.  Spline S 2  is not visible. 
     After the hidden line removal method has identified the visible and invisible edges in a tile, the first visible edge e in object o is selected (step  26 ). If the original exterior color of edge e is unknown (step  30 ), then it is determined whether either endpoint of edge e is at a complex point (step  32 ). If either endpoint of edge e is at a complex point, then the exterior color and exterior sequence number of edge e are assigned values, according to the method of FIG. 3 b  (step  50 ). Steps  26 - 50  are then then repeated for each remaining visible edge in the tile. 
     Referring to FIG. 3 b,  the original exterior color and exterior sequence number of an edge e that intersects with a complex point p are assigned values as follows. During hidden edge removal, a list of all visible edges connected to point p is maintained. First, the visible edges connected to point p are sorted (step  52 ). Edges are sorted in order of increasing angular direction (in a clockwise direction) with respect to point p. For purposes of sorting, the direction of each edge is treated as if the edge points away from point p. For example, the edges at point P 8  (FIG. 2 d ) are sorted as follows: E 20 , E 21 , E 16 . Note that edge E 15  is not included in the list because it was previously identified as invisible by the hidden line removal method. Next, if e points into point p, then ee is selected as the edge previous to e in the sorted list, with wraparound (step  53 ). If e points away from point p, then ee is selected as the edge following e in the sorted list, with wraparound (step  54 ). In other words, the edge previous to the first edge in the list is the last edge in the list, and the edge after the last edge in the list is the first edge in the list. For example, the edge previous to E 21  is E 20 , and the edge, in the sort order, after E 16  is E 20 . 
     Next, the original exterior color of e is set to the original color of ee on the side of ee facing the exterior of e, and the exterior sequence number of e is set to the sequence number of ee on the side of ee facing the exterior of e (step  55 ). For example, referring to to FIG. 2 d,  if p is point P 8  and e is edge E 21 , then ee is edge E 7 . The interior of edge E 7  faces the exterior of edge E 21 . Therefore, the original exterior color of edge E 21  is set to the original interior color of edge E 7  (yellow), and the interior sequence number of edge E 7  is copied into the exterior sequence number of edge E 21 . 
     The original exterior color and exterior sequence number of edge e are then propagated to the other edges in edge e&#39;s spline (step  57 ). The method then proceeds to step  34  in FIG. 3 a  (step  60 ). 
     After the method of FIG. 3 a  has completed operation, the method of FIG. 3 c  is applied to all edges whose exterior color is still unknown. Referring to FIG. 2 e,  object  16  is the sole object within tile  19 , with tile boundaries TBE 1 , TBE 2 , TBE 3 , and TBE 4 . Because none of the edges of object  16  intersects with the edges of any other objects or with any tile boundaries, the exterior color of all of the edges of object  16  will remain “unknown” after applying the method of FIG. 3 a.    
     Referring to FIG. 3 c,  for each edge e with an unknown original exterior color (step  100 ), a vector v is constructed perpendicular to e, emanating from the midpoint of e, pointing towards the exterior of e (step  105 ). For example, referring to FIG. 2 e,  vector v is constructed perpendicular to edge E 1  of path  16 . The method next follows v until it intersects either an edge or a tile boundary (referred to as the intersected edge ie) (step  110 ) that is not in the same object as e (step  115 ). For example, referring to FIG. 2 e,  vector v intersects tile boundary TBE 2 . If v intersects the exterior of ie, then the original exterior color of e is assigned the value of the original exterior color of ie, and the exterior sequence number of e is assigned the value of the exterior sequence number of ie (step  125 ). Otherwise, the original exterior color of e is assigned the value of the original interior color of ie, and the exterior sequence number of e is assigned the value of the interior sequence number of ie (step  120 ). The original exterior color and exterior sequence number of e is then propagated to the other edges in e&#39;s spline (step  130 ). For example, referring to FIG. 2 e,  vector v intersects the interior of TBE 2 . The original exterior color of edge E 1  is therefore assigned the value of the original interior color and the original interior sequence number of tile boundary TBE 2 , both of which are then propagated to edges E 2 , E 3 , E 4 , E 5 , E 6 , and E 7 . 
     Referring to FIG. 4 a,  in their resolution-independent vector representations, object  200  and object  300  approach each other, but do not touch or overlap, near the top edge  240  of object  200 . The interior color of object  200  is cyan, the interior color of object  300  is magenta, and the background color is green. Although not shown, the curve of object  300  is represented in vector form by a number of straight connected edges. 
     FIG. 4 b  shows a possible rasterization of the portions of objects  200  and  300  within the box  310 , when rasterized on a device with a resolution smaller than the distance between the top edge  240  of object  200  and the bottom of object  300 . 
     As shown in FIG. 4 b,  the pixels representing object  300  touch the pixels representing object  200 , even though in their vector representations the objects do not touch or overlap. Therefore, although in the vector representation in FIG. 4 a  the color on the exterior of edge  240  is green (the background color), in rasterized form the color part of the exterior of edge  240  is magenta. Trapping edge  240  based solely on an exterior color of green will therefore lead to incorrect results. The methods and apparatus of the present invention provide proper trapping in this case, i.e., in the case where the raster representations of two objects touch even though their vector representations do not touch. 
     A peeker is a gap between two edges in vector representation that is narrower than a device pixel at the resolution of the output device on which the vectors are to be rendered. If a peeker exists between two edges, the color inside the gap between the two edges will not be visible when the page is rendered in rasterized form. If a peeker exists, the color between the two edges needs to be set to an appropriate color so that correct traps can be generated. 
     The peeker distance PD is defined as the maximum distance between two edges for which a peeker will be considered to exist. Trap width is the distance that a trap projects into the darker of two objects between which a trap is required. For a trap width of 0.25 points, PD is advantageously chosen to be twice the length of the shortest axis (highest dpi) of a pixel on the output device on which the page is to be rendered. PD may also be fixed as (max(h, v)/1200)*l, where h is the horizontal resolution of the output device in dots per inch, v is the vertical resolution of the output device in dots per inch, and 1 is the length of the shortest axis of a pixel on the output device. Other methods for calculating PD may also be used. For example, PD may be equal to 1 for resolutions of 0 through 900 dpi, 1.5*l for resolutions of 900 through 1800 dpi, and (max(h, v)/1200)*l for resolutions greater than 1800 dpi. For narrower trap widths, PD should be appropriately scaled down. 
     Referring to FIG. 5, Phase One  600  of peeker detection and correction processes each of the edges in a tile as follows. First, an edge e is chosen from the tile&#39;s edge table (step  605 ). Edges may be chosen in any order. If edge e is less than two peeker distances long, then edge e does not need to be processed by Phase One (step  610 ). Otherwise, a rectangle r is constructed around edge e as shown in FIG. 6 a  (FIG. 5, step  620 ). Edge e has a from point  800  and a to point  805 . Rectangle r has corners  820 ,  825 ,  835 , and  840 . Rectangle r is constructed so that PD is the distance between two points in each of the following pairs of points: ( 810 ,  820 ), ( 810 ,  825 ), ( 815 ,  835 ), ( 815 ,  840 ), ( 810 ,  800 ), and ( 815 ,  805 ). 
     Next, all edge endpoints falling within rectangle r, excluding any endpoints created in step  680 , are added to a point list (step  630 ). Next, for each endpoint ep in the point list, a split point  870  on e is identified by drawing a line  860  from ep to e, in a direction perpendicular to e (step  660 ), as shown in FIG. 6 b.    
     After split points for e have been identified, selected split points are eliminated so that no two split points are separated by a distance less than PD (step  670 ). Then, edge e is split into child edges at each split point (step  680 ). A reference to edge e is stored in each of edge e&#39;s child edges. Edge e&#39;s interior and exterior color are stored in each of edge e&#39;s child edges as the original interior color and original exterior color, respectively, of the child edge (step  690 ). After being split into child edges, edge e is removed from the edge table and is referred to as a parent edge. For example, referring to FIG. 6 b,  edge e is split into two child edges. One child edge has a from point at point  800  and a to point at point  870 . The other child edge has a from point at point  870  and a to point at point  805 . 
     If edge e was not the last edge in the tile, (step  700 ), the method of Phase One  600  is repeated for the remaining edges in the tile. After Phase One  600  has been completed, the method proceeds to Phase Two (step  1000 ). 
     Phase Two processes each of the edges in the edge table of a tile as follows. Referring to FIG. 7 a,  first a visible edge referred to as a test edge is selected from the edge table (step  1010 ). Visible edges may be selected as test edges in any order. If the length of the test edge is greater than twice the peeker distance (step  1015 ), then an edge object pointer te 1  is set to point to the test edge (step  1025 ). Referring to FIG. 8 a,  te 1  has a from point  1330  and a to point  1340 . A square referred to as a from peeker square  1310 , with width 2*PD, is drawn with its center on the from point  1330  of edge te 1  (step  1030 ). Two parallel edges of the from peeker square  1310  are parallel to edge te 1 ; the other two parallel edges of the from peeker square  1310  are perpendicular to edge te 1 . 
     Next, a from point list is created by examining the endpoints of each of the edges in the edge table (not including the endpoints of te 1 ), and filling the from point list with each such endpoint which is within the from peeker square  1310  (step  1040 ). Then, all of the edges to which the points in the from point list belong are stored in a from edge list (step  1050 ). The steps  1030 - 1050  are then repeated for the to point  1340  of edge te 1 , using a to peeker square  1320  (steps  1060 - 1080 ). 
     After the from edge list and to edge list have been created, a list of candidate peeker edges (the candidate list) is created (steps  1090 - 1092 ). First, edges which are members of both the from edge list and the to edge list are added to the candidate list (step  1090 ). Next, parent edges with a child edge in the from edge list and another child edge in the to edge list are added to the candidate list (step  1092 ). For example, referring to FIG. 8 b,  edge  1360  has a from point  1362  in the to peeker square  1320  of edge te 1  and a to point  1364  in the from peeker square  1310  of edge te 1 . Edge  1360  is therefore added to edge tells candidate list at step  1150 . Edge  1366  is a parent edge. One child of edge  1366  has a from point  1368  in the from peeker square of edge te 1  and a to point  1370 . The other child of edge  1366  has a from point  1370 , and a to point  1372  in the to peeker square of edge te 1 . The parent edge  1366  is therefore added to edge te 1 &#39;s candidate list at step  1160 . Next, the candidates are processed according to the method of FIG. 7 c  (step  1094 ). 
     Referring to FIG. 7 b,  if the length of a test edge is less than or equal to 2*PD (step  1020 ), then an edge object pointer te 2  is set to point to the test edge (step  1100 ). A single peeker rectangle  1350  is drawn around te 2 , as shown in FIG. 8 c  (step  1102 ). The width of the peeker rectangle  1350  is equal to the length of te 2 , and te 2  divides the peeker rectangle  1350  into equal rectangular halves, each with height PD. A single point list of all endpoints in the peeker rectangle  1350 , including the endpoints of te 2 , is created (step  1104 ), and a single edge list containing all edges with one or both endpoints in the point list is created (step  1106 ). The candidate list is then filled with all of the edges in the edge list (step  1108 ). For example, referring to FIG. 8 d,  edge  1380  has a from point  1382  and a to point  1384  in the peeker square  1350  of edge te 2 . Edge  1380  is therefore added to edge te 2 &#39;s candidate list at step  1108 . Next, the candidates are processed according to the method of FIG. 7 c  (step  1094 ). 
     When an edge is placed in the candidate list, the following information about the edge is stored in a data structure: (1) a pointer to the candidate edge in the edge table; (2) the position of the candidate edge&#39;s from point in relation to the test edge (left, right, or colinear); (3) the position of the candidate edge&#39;s to point in relation to the test edge (left, right, or colinear); and (4) the difference in direction between the candidate edge and the test edge, as measured in radians. 
     Referring to FIG. 7 c,  after the peeker candidate list has been created, each candidate edge in the candidate list is processed. First, candidate edges with at least one endpoint on the left side of the test edge and neither endpoint on the right side of the test edge are processed (step  1120 ). Specifically, referring to FIG. 7 d,  the effective interior color of the test edge is set to the interior color of the candidate edge with the highest owning sequence number, from among the candidate edges being processed (step  1140 ). 
     Next, candidate edges with at least one endpoint on the right side of the test edge and neither endpoint on the left side of the test edge are processed (step  1125 ; FIG. 7 e ). First, candidate edges from the same object as the test edge are excluded from consideration if they do not point in a direction nearly opposite to the test edge; specifically, they are excluded if the difference in direction is less then 3π/4 radians or greater than 5π/4 radians (step  1150 ). From the remaining candidate edges, the candidate edge with the highest interior sequence number is identified (step  1155 ). If the directional difference between the test edge and the identified candidate edge is greater than or equal to π/2 radians, then the effective exterior color of the test edge is set to the original interior color of the identified candidate edge (step  1160 ). If the directional difference between the test edge and the identified candidate edge is less than π/2 radians, the effective exterior color of the test edge is set to the original exterior color of the identified candidate edge (step  1170 ). 
     Next, referring to FIG. 7 f,  candidate edges which are coterminal with the test edge at both endpoints are processed (step  1130 ). First, variables MLSN (representing the highest candidate left sequence number encountered so far) and MRSN (representing the highest candidate right sequence number encountered so far) as initialized to −1 (step  1200 ). Variable TLSN is a pointer to the test edge&#39;s left sequence number, and TRSN is a pointer to the test edge&#39;s right sequence number (step  1200 ). 
     A candidate c is chosen (step  1202 ). Variable CLSN is assigned c&#39;s left sequence number, and variable CRSN is assigned c&#39;s right sequence number (step  1204 ). If c points in the same direction as the test edge (step  1206 ), CLSN&gt;TLSN, and CLSN&gt;MLSN, then the test edge&#39;s effective left color is assigned c&#39;s original left color, and MLSN is assigned the value of CLSN (steps  1220 - 1224 ). If c points in the same direction as the test edge (step  1206 ), CRSN&gt;TRSN, and CRSN&gt;MRSN, then the test edge&#39;s effective right color is assigned c&#39;s original right color, and MRSN is assigned the value of CRSN (steps  1226 - 1230 ). 
     If c points in the opposite direction as the test edge (step  1206 ), CLSN&gt;TRSN, and CLSN&gt;MLSN, then the test edge&#39;s effective right color is assigned c&#39;s original left color, and MLSN is assigned the value of CLSN (steps  1208 - 1212 ). If c points in the opposite direction as the test edge (step  1206 ), CRSN&gt;TLSN, and CRSN&gt;MRSN, then the test edge&#39;s effective left color is assigned c&#39;s original right color, and MLSN is assigned the value of CLSN (steps  1214 - 1218 ). 
     After peeker detection and correction has been performed, trapping can be performed using the effective interior and effective exterior colors of the edges on the page. Trapping will include deciding whether and where to place traps, and, if a trap is to be set, deciding what the color of the trap should be. Typically, a trap engine will examine the effective colors on both sides of each edge in an edge table to determine whether a trap is needed. If a trap is needed, the trap engine will then decide what color the trap should be. Trapping may be performed when the edges are in vector form, or it may be performed on the rasterized page. 
     Referring to FIG. 9, the invention may be implemented in digital electronic circuitry or in computer hardware, firmware, software, or in combinations of them. Apparatus of the invention may be implemented in a computer program product tangibly embodied in a machine-readable storage device for execution by a computer processor; and method steps of the invention may be performed by a computer processor executing a program to perform functions of the invention by operating on input data and generating output. 
     Suitable processors  1480  include, by way of example, both general and special purpose microprocessors. Generally, a processor will receive instructions and data from a read-only memory (ROM)  1520  and/or a random access memory (RAM)  1510  through a CPU bus  1500 . A computer can generally also receive programs and data from a storage medium such as an internal disk  1430  operating through a mass storage interface  1440  or a removable disk  1410  operating through an I/O interface  1420 . The flow of data over an I/O bus  1450  to and from I/O devices  1410 ,  1430 ,  1460 ,  1470  and the processor  1480  and memory  1510 ,  1520  is controlled by an I/O controller. User input is obtained through a keyboard  1470 , mouse, stylus, microphone, trackball, touch-sensitive screen, or other input device. These elements will be found in a conventional desktop or workstation computer as well as other computers suitable for executing computer programs implementing the methods described here, which may be used in conjunction with any digital print engine  1475  or marking engine, display monitor  1460 , or other raster output device capable of producing color or gray scale pixels on paper, film, display screen, or other output medium. 
     By way of example, a printing device  1475  implementing an interpreter for a page description language, such as the PostScript® language, includes a microprocessor  1550  for executing program instructions (including font instructions) stored on a printer random access memory (RAM)  1560  and a printer read-only memory (ROM)  1570  and controlling a printer marking engine  1580 . The RAM  1560  is optionally supplemented by a mass storage device such as a hard disk (not shown). 
     Storage devices suitable for tangibly embodying computer program instructions include all forms of non-volatile memory, including by way of example semiconductor memory devices, such as EPROM, EEPROM, and flash memory devices; magnetic disks such as internal hard disks  1030  and removable disks  1410 ; magneto-optical disks; and CD-ROM disks. Any of the foregoing may be supplemented by, or incorporated in, specially-designed ASICs (application-specific integrated circuits). 
     Although elements of the invention are described in terms of a software implementation, the invention may be implemented in software or hardware or firmware, or a combination of any of the three. 
     The present invention has been described in terms of an embodiment. The invention, however, is not limited to the embodiment depicted and described. Rather, the scope of the invention is defined by the claims.