Upscaling of anti-aliased graphical elements

Upscaling of an anti-aliased graphical element in a raster image includes generating a grid of pixels. Resolution of the grid is higher than resolution of the graphical element. Each pixel in the anti-aliased graphical element corresponds to a group of pixels in the higher resolution grid. The upscaling further includes distributing coverage of each transition pixel in the anti-aliased graphical element to the corresponding pixels in the higher resolution grid. The coverage is distributed unevenly.

BACKGROUND

Anti-aliasing is used to improve the appearance of graphical elements on computer screens. Without anti-aliasing, edges of graphical elements can appear jagged. Anti-aliasing can reduce the perceived jaggedness of the edges.

When an image is upscaled to a higher resolution, anti-aliased elements in the upscaled image can become blurred and artifacts can become visible. Consider an image of a road map that contains a number of anti-aliased graphical elements (e.g., streets, street names). While maps provided by leading Internet sites have sufficient resolution (72 ppi) to look fine on a computer screens, this resolution is not high enough for printing on standard printers, even with standard paper. Therefore, when viewed on a computer screen, edges of these anti-aliased elements appear sharp. When the elements are printed, however, edges in the print appear blurred. Many people mistakenly assume that their printers are of low quality, because their printers are “unable” to reproduce the visual quality perceived on the computer screens. In fact, the difference in perceived quality on the screen and quality of the print is due to the combination of the usually higher resolution power of the printer and paper media with the relatively low resolution of the map content.

It would be desirable to upscale anti-aliased graphical elements, while retaining perceived image quality.

SUMMARY

According to one aspect of the present invention, upscaling of an anti-aliased graphical element in a digital image includes generating a higher resolution grid of pixels, whereby each pixel in the anti-aliased graphical element corresponds to a group of pixels in the higher resolution grid; and distributing coverage of each transition pixel in the anti-aliased graphical element to the corresponding pixels in the higher resolution grid. The coverage is distributed unevenly.

DETAILED DESCRIPTION

As shown in the drawings for the purpose of illustration, the present invention is embodied in a method of increasing the resolution of graphical elements in digital images. Examples of graphical elements include text, geometric shapes, and lines. The graphical elements may be generated by word processing programs, CAD programs, etc. Graphical elements are typically computer-generated, but could be formed in other ways.

In many graphical databases, the graphical elements are stored as vectors. A vector graphical element (also called a graphical element in vector format) is characterized by geometric information. For instance, a vector rectangle may be characterized by its corner coordinates. The vector rectangle may also describe foreground and background colors.

Reference is made toFIG. 1a, which illustrates an edge100of a vector graphical element. The edge100is superimposed on a pixel grid110of a certain resolution. Those pixels completely contained within the graphical element (dark area) are said to have 100% coverage, and are called foreground pixels120. Those pixels completely excluded from the graphical element (white area) are said to have 0% coverage, and are called background pixels130. Other pixels have partial coverage by the graphical element: pixels A, B, and C have 25% coverage, and pixels D, E, F and G have 75% coverage.

The coverage may be computed as the area of the graphical element inside the pixel region, divided by the total area of the pixel region. In mathematical terms, if A(X) is the area of a region X, P is the pixel region, and GE is the region occupied by the graphical element, then the coverage may be computed as
Cov=100*A(P∩GE)/A(P),
where Cov denotes the coverage in percentage.

Reference is made toFIG. 1b, which illustrates a raster image of the vector graphical element without anti-aliasing. Pixels in this non- anti-aliased graphical element may be formed by rounding each coverage to 0% or 100%, whatever is closest, and setting the corresponding color to the pixels. Thus, the non-anti-aliased graphical element has foreground pixels150set against background pixels160. Without anti-aliasing, the edge appears jagged.

Reference is made toFIG. 1c, which illustrates a raster image of the vector graphical element with anti-aliasing. The anti-aliased element contains foreground pixels150, background pixels160and “transition” pixels170aand170b. The colors represented by the transition pixels170aand170bmay be somewhere between the foreground and background colors (e.g., different shades of gray). The actual color of a transition pixel170aor170bmay depend on a specific anti-aliasing algorithm being used. In general, the intensity of the transition pixel represents the pixel coverage by the ideal graphical element. For example, the color (t) of a transition pixel170aor170bmay be computed as a function of the coverage (Cov):
t=Cbac+(Cfor−Cbac)*Cov/100.
where Cforis the foreground color and Cbacis background color.

InFIG. 1c, the transition pixels170aand170bhave a darker shade than the background pixels160. Some of the transition pixels170ainFIG. 1cwere created by lightening foreground pixels, while other transition pixels170bwere created by darkening background pixels.

Even though the examples inFIGS. 1a,1b, and1c, involve black and white colors only for the foreground and background, the foreground and background colors could be any pair of colors (i.e., any pair of points in a generic three-dimension or higher-dimension color space). For instance, the background color could be pink, and the foreground color brown. The foreground pixels could be lighter than the background pixels.

Reference is made toFIG. 2. When the anti-aliased element is displayed on a low resolution display device (e.g., a video display)210, the transition pixels create an illusion of smooth edges. However, when that same anti-aliased element is displayed on a higher resolution display device (e.g., a printer)220, the edges may appear blurred. A processor230according to the present invention can process the anti-aliased element so its edges don't appear blurred on the higher resolution display device220.

Reference is made toFIG. 3a. Upscaling of an anti-aliased graphical element in a digital image includes generating a higher resolution grid of pixels (block300). Each pixel in the anti-aliased graphical element corresponds to a group of pixels in the higher resolution grid. The upscaling further includes unevenly distributing coverage of each transition pixel in the anti-aliased graphical element to the corresponding pixels in the higher resolution grid (block305).

Reference is made toFIG. 3b, which illustrates a method used by the processor230to upscale an anti-aliased graphical element. Since the graphical element has been anti-aliased, it is represented as a raster image, not in vector form. Vector information (if any) about graphical element is assumed to be unavailable. Upscaling according to the present invention uses information in the raster image.

At block310, a higher resolution grid of pixels is generated. Each pixel in the anti-aliased graphical element corresponds to a group of pixels in the higher resolution grid. For example, each pixel in the anti-aliased graphical element corresponds to a 2×2 block of pixels in the higher resolution grid. The pixels in the higher resolution grid will be referred to as “hi-res pixels.” The pixels in the anti-aliased element will be referred to as “lo-res” pixels.

At block320, the coverage of each pixel in the anti-aliased graphical element is estimated. Those lo-res pixels having partial coverage (i.e., coverages different from 0% and 100%) are identified as transition pixels.

At block330, the coverage of each lo-res transition pixel is unevenly distributed among its corresponding hi-res pixels in the higher resolution grid. The uneven distribution will create the illusion of a smooth, sharp edge at the higher resolution when the higher resolution grid is displayed on the higher resolution display.

At block340, colors are assigned to the hi-res pixels that correspond to the lo-res transition pixels. The colors are assigned as a function of the unevenly distributed coverage. Typically, but not necessarily, a hi-res pixel having a higher coverage will have a darker shade than a hi-res pixel having a lower coverage.

At block350, the color of each non-transition pixel is assigned to its corresponding hi-res pixels in the higher resolution grid. Pixel replication could be performed on the foreground and background pixels. This step may be performed before, after, or with the steps at blocks330and340.

FIG. 4illustrates three pixels150,160and170aof an anti-aliased graphical element and corresponding pixels450,460and470a1-470a4that are upscaled by a factor of two. Each lo-res pixel of the anti-aliased graphical element corresponds to a 2×2 block of hi-res pixels in the higher resolution grid.

The lo-res pixel150having full coverage corresponds to a block of four full coverage hi-res pixels450in the higher resolution grid. The lo-res pixel160having zero coverage corresponds to a block of four hi-res pixels460having zero coverage.

For the transition pixel170aof the anti-aliased graphical element, all hi-res pixels470a1-470a4of the corresponding 2×2 block do not have the same color. The coverage is distributed such that the hi-res pixels470a3and470a4have higher coverages than the hi-res pixels470a1and470a2since hi-res pixels470a3and470a4are spatially closer to the full coverage pixels450and hi-res pixels470a1and470a2are spatially closer to zero coverage pixels460. However, the average coverage of the hi-res pixels470a1-470a4is roughly identical to the coverage of the corresponding transition lo-res pixel170a.

Reference is now made toFIG. 5, which illustrates a method of unevenly distributing the coverage of a transition pixel. At block510, coverage of the transition pixel is estimated. Background and foreground colors are estimated from a local neighborhood of lo-res pixels (block510a). The local minimum (e.g., the darkest pixel) and the local maximum (e.g., the lightest pixel) within a 3×3 neighborhood of the transition pixel may be used as the estimated background and estimated foreground colors. Neighborhoods larger than 3×3 could be used instead. Alternatively, more complex methods for estimating the foreground and background colors could be employed (e.g., by searching for local minimum and maximum iteratively or within an adaptive neighborhood).

In certain instances, it might not be necessary to compute the local maximum and the local minimum in order to estimate the background and foreground colors. For instance, a set of possible foreground and background colors associated with a specific image type (such as road maps provided by a specific web site) may have been previously stored in memory. In this case, estimation of foreground and background colors may be performed by matching neighboring low-res pixels to this set of possible foreground and background colors.

The estimated coverage may be computed as a function of transition pixel color, an estimated foreground color, and an estimated background color (block510b). For example, the estimated coverage (covest) of a transition pixel may be computed as
covest=100*(t−Cbac,est)/(Cfor,est−Cbac,est)
where t is the color of the transition pixel, Cbac,estis the estimated background color, and Cfor,estis the estimated foreground color.

At block520, each hi-res pixel in the corresponding high resolution grid is assigned a weight. Pixels whose neighbors have higher coverage are assigned higher weights than hi-res pixels whose neighbors have lower coverage. The sum of the weights should be about equal to the number of hi-res pixels that correspond to one low-res pixel. In one embodiment, the hi-res pixels are assigned weights that are proportional to the average coverage of their neighboring pixels. Other policies for weight determination may be used.

Applying this step to the pixels inFIG. 4a, the sum of the weights should be equal to four. The transition pixel170ahas two adjacent neighbors: the North neighbor160has 0% coverage, and the South neighbor150has 100% coverage. Therefore, the hi-res pixels470a1and470a2that are adjacent to the North pixel160are assigned a weight of zero, and the two hi-res pixels470a3and470a4that are adjacent to the South pixel150are assigned a weight of two.

At block530, the coverage is distributed to the hi-res pixels according to the weights. Higher coverage is assigned to hi-res pixels having higher weights. The coverages may be assigned by multiplying the weights by the coverage of the transition pixel. If a hi-res pixel is assigned a coverage greater than 100%, then the coverage of that pixel is set to 100%, and the remaining coverage is distributed between the remaining hi-res pixels according to the respective weights. The latter is repeated until all hi-res pixels have coverages lower or equal to 100%.

Applying this step to the pixels inFIG. 4a, the hi-res pixels470a1and470a2that are adjacent to the North pixel160get a coverage of 75%×0=0% each, whereas the two hi-res pixels470a3and470a4that are adjacent to the South pixel150get a coverage of 75%×2=150% each. Because these two pixels470a3and470a4are assigned a coverage greater than 100%, they are each set to 100% coverage, and the remaining 100% (i.e., 50%×2) are redistributed to the remaining hi-res pixels470a1and470a2.Because these two pixels470a1and470a2have the same weight, the 100% balance is redistributed equally between them. Thus, each pixel470a1and470a2is assigned 50% coverage.

At block540, colors are assigned to the hi-res pixels as a function of the redistributed coverage. For example,
t=Cbac,est+(Cfor,est−Cbac,est)*Covest/100
where t is pixel color, Cbac,estis the estimated background color, and Cfor,estis the estimated foreground color.

FIG. 4bis another illustration of pixels in an anti-aliased graphical element and their corresponding upscaled pixels. Consider the central lo-res pixel170c. After the steps at blocks310and320are applied, a 2×2 block470cof hi-res pixels corresponds to the central lo-res pixel170c, and the coverage of the central lo-res pixel170cis estimated at 75%. In addition, the E low-res pixel is estimated to have a coverage of 25%, the NW, W, SW, S, and SE low-res pixels (relative to the central pixel470c) all have 100% coverage, and N and NE low-res pixels have 0% coverage.

Weights can be assigned to the hi-res pixels of the block470cby applying the method ofFIG. 5. Consider the high-res NW pixel. It is spatially adjacent to the N, NW, and W low-res pixels (even though the high-res pixels are shown separately from the low-res pixels, they occupy the same spatial position as the central low-res pixel). The sum of the coverage percentage of the N, NW, and W low-res pixels is computed as 200%. Repeating this procedure for the NE, SW, and SE high-res pixels, the sums 25%, 300% and 225% are computed. After normalizing these sums to get a total weight of four, the weights 1.066666 . . . , 0.13333333 . . . , 1.6, and 1.2 are obtained for the NW, NE, SW, and SE hi-res pixels, respectively. By multiplying the coverage of the central low-res pixel (75%) by the above weights, the coverages 80%, 10%, 120%, and 90%, are obtained for the hi-res pixels in block470c. The SW hi-res pixel has coverage higher than 100%; therefore, its coverage is set to 100% and the remaining 20% is distributed to the other pixels, according to their weights. The NW, NE, and SE hi-res pixels get additional 8.8888 . . . %, 1.11111 . . . %, and 10% coverages. Thus, the revised coverages of the NW, NE, SW, and SE hi-res pixels are now: 88.8888 . . . %, 11.1111 . . . %, 100%, and 100%. These coverages are not further revised, since they are all smaller than 100%. The average coverage of the block470cis 75%, which is the same as the coverage of the lo-res pixel170c.

Reference is made toFIG. 6, which illustrates a method of upscaling an input image that contains only graphical elements. Some or all of the graphical elements may be anti-aliased.

The processing is based on the following two assumptions:a. Transition pixels are the only pixels with partial coverage and the partial coverage is due to anti-aliasing.b. Foreground elements are darker than background elements.
However, other embodiments can be based on different assumptions.

At block610, all non-anti-aliased elements are identified and converted to anti-aliased elements. This is done without the benefit of vector information. At block610a, corners of the non-anti-aliased elements are identified. Local background and foreground colors are estimated. In one embodiment, this includes determining whether each pixel is a local maximum or a local minimum. In another embodiment, a set of possible foreground and background colors for a given image type is stored in memory, and pixels that match any of these colors are estimated as foreground or background colors. If the pixel is a foreground pixel, and a group of neighbors forming a corner are background pixels, then that pixel is marked as a corner pixel. There might be different types of corner pixels. The different types depend on the group of corner pixels used in the above determination. For instance, if the pixel is a foreground pixel and its North, West, and North-West neighbors are all background pixels, then the pixel may be identified as a North-West corner pixel. Or, if the pixel is a foreground pixel and its North, East and North-East neighbors are background pixels, then that pixel may be identified as a North-East corner pixel.

At block610b, imaginary lines are constructed. If a second corner pixel of the same type and same color is detected in an adjacent line or column, and if the corner pixels are connected by adjacent pixels of the same color (as the corners), then an imaginary line is constructed from the first corner pixel to the second corner pixel. At block610c, all pixels traversed by the imaginary line are marked as transition pixels, and their values are replaced by transition values.

Referring toFIG. 7, the transition values may be replaced as follows.FIG. 7shows first and second South-West corners710and720, connected by pixels of the same color, thus forming a non anti-aliased element. An imaginary line (L) extends between the two corner pixels710and720, connecting the middle-point of the West side of corner pixel710to the middle-point of the West side of corner pixel720. Those pixels crossed by the imaginary line (L) are identified as transition pixels. These pixels are marked with dots. Coverage of each transition pixel with respect to the line (L) is computed, background and foreground colors are estimated, and transition colors are assigned to these marked pixels according to the coverages.

FIG. 7depicts one of eight possible configurations, which are listed below in Table 1. The eight configurations are distinguished by their corner pixels and their adjacency, namely, line or column adjacency. The procedure described with respect to block610bis basically the same for all eight configurations, except for the selection of the side of the corner pixel, the middle-point of which should be crossed by the imaginary line (L). In the configuration ofFIG. 7, the corner type is South-West, adjacency is line, and middle-point side is West.

Reference is once again made toFIG. 6. At block620, all anti-aliased elements are identified. At block630, each anti-aliased element is upscaled according to the method ofFIG. 3b.

At block640, the upscaled image is outputted. For example, the upscaled image may be sent to an image rendering device, transmitted to another machine, stored in a storage device, etc.

Pre-processing and post-processing could be performed (blocks605and650), depending upon whether the upscaling is part of a larger image processing pipeline. For example, image pipeline processing could include RIP, compression, transmission (pre-processing), layer-removal, sharpening, color modification, and decompression. If the upscaling is part of a stand-alone module, no pre-processing or post-processing would be performed. Instead, the upscaled image would be outputted right after upscaling.

The input image may contain more than one background color and more than one foreground color. However, the upscaling assumes that each local neighborhood has only one background color and one foreground color.

A method according to the present invention is not limited to performing anti-aliasing on non-anti-aliased elements and then upscaling all of the anti-aliased elements together. The non-anti-aliased elements could be upscaled separately from the anti-aliased elements.

Reference is now made toFIG. 8, which illustrates the upscaling and anti-aliasing of a non-anti-aliased element. At block810, corner pixels of non anti-aliased element are identified. The approach of block610bmay be used

At block820, imaginary lines L are constructed between corner pixels. Here too, the approach of block610bmay be used.

At block830, a high resolution grid is created. At block840, transition pixel colors are assigned to corresponding hi-res pixels in the higher resolution grid. a higher resolution grid is generated. The imaginary lines L identify transition pixels and their coverages in the higher resolution grid. The colors of the transition pixels are determined, according to their coverages. The approach of block610cmay be used here, but on the higher resolution grid instead of a graphical element.

Reference is once again made toFIG. 2. A method according to the present invention is not limited to any particular hardware implementation.FIG. 2illustrates a general hardware implementation.

In a specific hardware implementation, element210could be a video monitor, element230could be part of a personal computer, and element220could be part of a printer or other image rendering device. The method could be performed in a printer, in a printer driver, in a web-browser toolbar, or in a computer program.

For example, a personal computer runs a web browser that downloads a raster image of a map. The map contains anti-aliased elements. If displayed on the video monitor, edges of the map appear sharp.

Before the image of the map is printed, the image is upscaled to a higher resolution. A printer driver or browser toolbar may upscale the image according to the present invention. When the upscaled image is printed, the printed elements also appear sharp.

In other specific implementations, elements220and230could both be a part of an image-rendering device such as a printer or high definition television, or other machine that increases the resolution of a signal.

A system according to the present invention is not limited to the embodiments just described. The system could include a processor, but not the video display or image rendering device. Or, the system could include an image capture device (e.g., a scanner) that captures images and processes the captured images, where the processing includes upscaling graphical elements. The system could include memory to store a set of possible background and foreground colors, or any other known data.

Design of the processor230is application-specific. In some hardware implementations, the processor230could include a general-purpose processor and memory programmed with code that, when executed, causes the general purpose processor to perform a method according to the present invention. In other hardware implementations, the processor could be a specific purpose processor (e.g., a digital signal processor) that is programmed to perform a method according to the present invention.

Although specific embodiments of the present invention have been described and illustrated, the present invention is not limited to the specific forms or arrangements of parts so described and illustrated. The present invention is construed according to the following claims.