Alpha regions

Details Alpha regions Alpha regions

1999-08-24

2002-11-12

Brier, Jeffery (Department: 2672)

Computer graphics processing and selective visual display system

Computer graphics processing

Attributes

C345S631000, C382S245000

Reexamination Certificate

active

06480201

ABSTRACT:

TECHNICAL FIELD
The invention relates to image storage and processing in computers, and more specifically relates to storing and processing images of arbitrary 2-dimensional shapes in a graphics system that supports anti-aliasing.
BACKGROUND OF THE INVENTION
Most modern computer graphics systems today use raster graphics to display images. A raster graphics system displays an image as a raster grid, where each line of the grid is composed of a row of pixels. The image may be stored as a 2-dimensional array of values, where each row of the array corresponds to a grid line of pixels, and each value of the array represents the data associated with a particular pixel. The image can then be processed via the array, and converted back into scan lines for display on the raster grid. As the capability of graphics systems increase, more complex images are created, with a corresponding increase in the complexity of storing and processing those images.
Most operating systems, therefore, have specially designed graphics subsystems that have been developed to address the problems inherent in creating, manipulating (define, clip, fill, draw and combine), and storing images as files in computer memory. For example, in the Microsoft Windows, operating systems, the subsystem that controls the display of text and graphics is called the Graphics Device Interface (GDI). GDI functionality is provided through an application programming interface (API) that includes functions to create graphical objects and manipulate those objects in memory. GDI draws lines, curves, closed figures, text, and bitmapped images on display devices and printers. There are a number of methods that have been developed in GDI and in other graphics subsystems for manipulating complex images. None, however, have all of the desirable characteristics of a method for storing and processing images of arbitrary 2-dimensional shapes, including compact storage requirements, scan-conversion efficiency and support for anti-aliasing.
Compact storage of the image is desirable since images of arbitrary 2-dimensional shapes tend to be very large collections of data. One way to represent an image of an arbitrary 2-dimensional shape in memory is with a binary mask, which is a 2-dimensional array of binary values that simply indicate the presence or absence of the shape. This type of representation requires a relatively small amount of memory by today's standards (only 128,000 bytes with a resolution of 1024×1024 pixels). For anti-aliased images, however, the data representing an image of an arbitrary 2-dimensional shape is more complex, requiring non-binary values to be stored for each pixel. These non-binary values represent the opacity of the pixel, and are referred to as alpha values. Storing alpha values requires significantly more bits per pixel to accurately represent the image in memory.
Scan-conversion efficiency is desirable since scan-conversion of an image stored in memory is computationally intensive. Moreover, every time an image is moved or re-sized on the drawing surface, the entire primitive comprising the image must be scan-converted anew.
Lastly, support for anti-aliasing is desirable because most graphics subsystems today employ anti-aliasing techniques. Aliasing results in the appearance of “jaggies” or “staircasing”, usually at the edges of the primitives of the image. These undesirable characteristics are common because most shapes can only be approximated with pixels on the raster grid. Although the use of anti-aliasing techniques improves the appearance of the image, it does so by altering the opacity of pixels at the image's boundaries. The alpha values associated with those pixels can range from fully transparent to fully opaque. A fully transparent pixel is represented by a value of 0, whereas a fully opaque pixel may be represented by a value of 255 for 8-bit alpha values, or, more generally, by a value of 2
n
−1 for n-bit alpha values. A range of alpha values may even be represented as floating values between 0 and 1. A semi-transparent pixel is represented by those values in between. The presence of a range of alpha values associated with the image not only increases the image's complexity, but makes it more difficult to process using existing methodology.
For example, one method of storing image data that is well-known in the art is run-length encoding. As described in Foley, et al., Computer Graphics Principles and Practice, Second Edition, run-length encoding is used for images having a great deal of repetition. It consists of encoding a count of the number of contiguous pixels having the same value, and the value itself. One example of an improvement on this basic idea is the assignment of a negative count to indicate that n-pixels' worth of unencoded data follow.
Another method of storing image data is to use a Region. A Region is a graphical object that subdivides an arbitrary 2-dimensional shape into a series of rectangular areas. The notion of a Region was developed for the graphics subsystems in the Macintosh and Microsoft Windows® operating systems to more easily store and process arbitrary 2-dimensional shapes.
An example of a prior art Region (
150
) is illustrated in FIG.
1
. Since a Region was originally designed to accommodate only shapes displayed as simple opaque images, the image data structure of Region is based on an image of an arbitrary 2-dimensional shape expressed as a grid of binary values, e.g. 0 and 1, where the value 0 represents a transparent pixel (absence of the shape), and the value 1 represents an opaque pixel (presence of the shape). In the example shown in
FIG. 1
, an arbitrary 2-dimensional shape is subdivided into an 8×8 grid of pixels (
110
). Instead of using a 2-dimensional array to literally store the value of each pixel, or using run-length encoding to store the counts and values of the pixels, a Region stores the image data according to the rectangular coordinates of the shape on the grid (
110
). The rectangular coordinates consist of the number of rows, e.g. Y
1
, Y
2
, etc. (
120
), having identical patterns of 1s and 0s in the x-direction, the start and stop locations of those patterns in the x-direction, e.g. X
1
, X
2
, etc. (
130
) and the height of the rows having identical patterns, e.g. H
1
, H
2
, etc (
140
) (where height is equal to the number of rows). Thus, a great deal of the redundancy in storing the image is eliminated, and enables a Region (
150
) to store an arbitrary 2-dimensional shape in a more compact form. A Region also provides for efficient scan-conversion of the stored image.
A major drawback to using a Region, however, is the inability to store and process images having non-binary values associated with the pixels of the image. For example, anti-aliased images typically have non-binary alpha values associated with the pixels at the edges of the arbitrary shape. These non-binary alpha values represent the semi-transparent pixels in the boundaries between the fully transparent and opaque areas present in anti-aliased images. But a Region can only store the fully opaque and fully transparent areas. Thus, the structure of a Region makes it incapable of storing the semi-transparent areas. Moreover, the proper functioning of the combination operations provided for Regions depend upon limiting the representation of a shape to only fully opaque or fully transparent areas. Thus, the combination operations provided for Regions are unavailable for use with anti-aliased images.
As graphics subsystems advance, support for anti-aliased images is critical. Hence, a new approach to storing and processing images is desirable, but without sacrificing the compactness in storage requirements or the efficiency in scan-conversion rates achieved by using a Region.
SUMMARY OF THE INVENTION
The invention provides an improved method for storing and processing images of arbitrary 2-dimensional shapes in a graphics subsystem that supports anti-aliasing. The method employs a novel graphics object implemented as an AlphaRegion.

Affiliated with

Also associated with

Rating

Alpha regions does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Alpha regions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Alpha regions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2984043