Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1998-02-20
2001-11-13
Boudreau, Leo (Department: 2621)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C345S530000, C345S611000, C345S613000
Reexamination Certificate
active
06317525
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the display or printing of images formed by discrete pixels.
BACKGROUND OF THE INVENTION
Computers are known to include processors, memory, and display devices. With ever increasing advances in computer applications, the need for improved display quality continues. Computer displays must be able to present high resolution, high quality images at rapid refresh rates. Video graphic circuits and systems must be able to provide the data for such displays efficiently and effectively, often within highly competitive cost and compatibility constraints.
Computer displays, and other high resolution display devices such as high definition televisions (HDTV), projectors, printers, plotters, and the like, present an image to the viewer as an array of individual picture elements, or pixels. The individual pixels are each given a specific characteristic, such as the color of the image at the particular pixel's location. The pixels are closely spaced, and the viewer's visual system performs a filtering of the individual pixel color values to form a composite image. If the partitioning of the image into individual pixel elements is performed properly, and the pixels are close enough together, the viewer perceives the displayed array of pixels as a virtually continuous image. Despite the viewer's visual filtering, the viewer remains sensitive to aberrations in the image, and video graphic systems must be designed to minimize these aberrations.
If the image is insufficiently sampled, visual aberrations will be produced. A highly detailed image with numerous changes within a short span of points will have a high frequency of change; a blank image has a zero frequency of change. If the frequency of pixel value sampling is less than half the image's frequency of change, aliasing will occur, and visual aberrations will be introduced into the image. That is, not only will the displayed image not contain the detail of the original image, but additional components, not contained in the original image, will be added. In addition to being visually disturbing, the introduction of sampling artifacts, not contained in the original image, can be particularly problematic if the display is used for mapping or medical applications (x-rays, MRI scans, etc.)
Aliasing will occur whenever the sampling rate is less than half the highest frequency change in the image. Traditionally, the pixel sampling rate is equal to the pixel spatial frequency. That is, if there are 640 pixels per line of display, a full screen image will be sampled at 640 points across its horizontal dimension. If the image being sampled has a highest frequency that is greater than twice the pixel sampling rate, then either the image highest frequency must be reduced, or the pixel sampling rate must be increased. These techniques, of reducing the image frequency, or increasing the pixel sampling frequency, are termed “anti-aliasing” techniques. Filtering the image to remove the high frequency components before the image is sampled for display reduces the image highest frequency. The pixel sampling rate can be increased by increasing the number of pixels per line of display, i.e. by increasing the display resolution, or, by sampling the image at greater than the pixel spatial frequency. High resolution displays are significantly more costly than lower resolution displays, and therefore a preferred alternative is to increase the sampling frequency by obtaining multiple samples of the image for each pixel; that is, by sampling at a subpixel resolution. The value presented to the display as the pixel value corresponding to the image will be the average of the multiple sample values obtained within each pixel.
Two schemes can be used to perform subpixel resolution sampling. Conventionally, in a non-subpixel sampled scheme, the center of the pixel is used as the point at which to sample the pixel value. To effect subpixel sampling, multiple points within each pixel are selected as sampling points, and the image is sampled at each of these points. For example, if the image comprises an object having a particular value, the sampled value will be the value of the object if the pixel lies within the object, or the value of the background if the pixel lies outside the object. To display the pixel, a single value must be assigned. Typically, the single value assigned to a pixel will be the average of the values assigned at each sampled point within the pixel, although other means of forming a representative statistic may be employed, such as the root mean square (RMS) of the sampled values. In this way, pixels which lie on the border of objects, such that some of the sub-pixel sampled values contain the object value, and some contain the background value, will be assigned an average value of the subpixel sampled values, producing a smoothing, or blending, at the transition, thereby effectively reducing the high frequency components of the image.
Another method of subpixel sampling is to repeatedly place the image at slightly different locations relative to the pixels; typically the locations are offset by a fraction of the pixel size from the original placement of the object. The image is sampled at each of these offset placements using the conventional technique of obtaining a single sample per pixel. Each pixel will then have one sample value for each offset placement. These pixel values corresponding to each offset placement are averaged to form a single pixel value to be displayed. This averaging based on multiple offset placements will produce the same smoothing, or blending, of edges within the image as discussed above.
Sampling at a subpixel resolution, using either the direct subpixel sampling or the object offset sampling provides an effective anti-aliasing solution, but requires additional processing and memory resources. To minimize memory requirements, an accumulated value of the multiple values per pixel is stored, rather than the individual sampled values. To provide an average pixel value having the same quality of a non-subpixel sampled value, each of the subpixel sampled values must have the same level of precision as the non-subpixel sampled value. If the non-subpixel sampled value has a precision of 8 bits, each of the subpixel samples must have 8 bits. If two samples are taken per pixel, the accumulated pixel value must have 9 bits to contain the sum of the two 8 bit values; if four samples are taken, 10 bits; etc.
For example, in conventional computer display technology, the pixel value comprises a set of values (16, 24, or 32 bit words) corresponding to the value of the Red, Green, and Blue (RGB) components of each pixel. These pixel values are stored in a portion of memory termed the rendering plane. Because the degree of precision for the accumulated pixel value is greater than the degree of precision for the rendered pixel value, more memory is required to contain the accumulated pixel value than that required to contain the actual pixel value for each pixel comprising the display. That is, if the pixel value is a 16 bit word, the accumulated pixel value will require an even larger word for each pixel. If two megabytes are required to store each pixel value in a rendering plane, then more than 2 megabytes will be required to store the accumulated pixel value.
In addition to the significant memory resources required to contain the accumulated pixel values, a significant amount of processing resources will be required to average the accumulated pixel value and store the resultant into the rendering plane. Consider, for example, a common 640×480 pixel display. For each of the 307,200 (640*480) pixels, the accumulated pixel value must be recalled from the accumulated pixel value memory area, then divided by the number of samples taken per pixel, then stored to the rendering plane memory area. With an ever increasing need to improve video graphic processing, such a large amount of processing limits the application of this sub-pixel sampling anti-aliasing technique
Aleksic Milivoje M.
Doyle James
Laksono Indra
ATI Technologies Inc.
Boudreau Leo
Patel Kanji
Vedder Price Kaufman & Kammholz
LandOfFree
Method and apparatus for full scene anti-aliasing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for full scene anti-aliasing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for full scene anti-aliasing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2603788