High quality anti-aliasing

• US 7,274,831 B2
• Filed: 04/03/2003
• Issued: 09/25/2007
• Est. Priority Date: 04/03/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Jian, Lin, Zhouchen, Chen, Haitao
• Primary Examiner(s): Kassa; Yosef
• Application Number:
  US10/406,517
• Publication Number:
  US 20040197028A1
• Time in Patent Office: 1,636 Days
• Field of Search: 382/260, 382/266, 382/269, 382/275, 382/279, 382/274, 382/79, 382/280, 382/282, 358/3.26, 358/3.27, 358/520, 358/463
• US Class Current: 382/279
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

An antialiasing method and apparatus suitable for antialiasing a variety of image types, including fonts, large images, and very small images. The antialiasing technique may represent the edge of a line, curve or region as a series of line segments. These line segments are then traversed to convolute the line segment approximating the contours of the image with a desired filter function. A filter function is also disclosed for antialiasing the edges of a line, curve or region, which may be employed when the edge is represented by a series of line segments. The antialiasing filter tends to centers the spectral energy of an image on the sampled area.

Claims

1. A method of rendering an image, comprising:

sampling actual image data for a contour to be rendered;

determining approximate image data for one or more line segments that approximate the contour to be rendered;

filtering the line segments by convoluting the approximate image data with a filter to cause the filter to optimally center spectral energy of the sampled image data on an area in a spectral domain corresponding to sample spacing of the sampled image data in the spatial domain, to produce filtered image data; and

rendering the contour using the filtered image data,

wherein the filter is the function h where

$h=\arg <br><br><br><br>\underset{h}{\max }<br><br>\frac{\int <br><br>{\int <br><br>}_{\mathrm{\Omega <br><br>}}<br><br>{<br><br>\left[F<br><br>\left(h\right)\right]<br><br>\left({\mathrm{\omega <br><br>}}_x,{\mathrm{\omega <br><br>}}_y\right)<br><br>}^2<br><br>d<br><br>{\mathrm{\omega <br><br>}}_x<br><br>d<br><br>{\mathrm{\omega <br><br>}}_y}{\int <br><br>\int <br><br>{<br><br>\left[F<br><br>\left(h\right)\right]<br><br>\left({\mathrm{\omega <br><br>}}_x,{\mathrm{\omega <br><br>}}_y\right)<br><br>}^2<br><br>d<br><br>{\mathrm{\omega <br><br>}}_x<br><br>d<br><br>{\mathrm{\omega <br><br>}}_y},$

[F(h)] denotes the Fourier transform of h and Ω

is the area in the spectral domain corresponding to sample spacing of the sampled image data in the spatial domain.

2. The method recited in claim 1, wherein the area Ω

=[−

Ω

, Ω

]×

[−

Ω

, Ω

] in the spectral domain, where Ω

=π

/T and T is the sample spacing for the sampled image data in the spatial domain.

3. The method recited in claim 1, wherein the filter is a revolutionary filter h(r, θ

), defined as

$<br><br>h<br><br>\left(r,\mathrm{\theta <br><br>}\right)=\underset{k=0}{\overset{M}{\sum <br><br>}}<br><br>h_k<br><br>r^k,$

wherein r ∈

[0, R].

4. The method recited in claim 3, wherein a mask of the revolutionary filter has a radius of 1 pixel.

5. The method recited in claim 1, wherein the filter is a square filter h(x) defined as

$$

h ⁡

( x ) = ∑

k = 0 M ⁢

h k ⁢

x 2 ⁢

k ,

where(|x|≦

R).

6. The method recited in claim 1, wherein a mask of the square filter has an area of 2 pixels by 2 pixels.

7. A method of rendering an image, comprising:

sampling actual image data for a contour to be rendered;

determining approximate image data for one or more line segments that approximate the contour to be rendered;

filtering the line segments by convoluting the approximate image data with filter to cause the filter to optimally center spectral energy of the sampled image data on an area in a spectral domain corresponding to sample spacing of the sampled image data in the spatial domain, to produce flitered image data;

rendering the contour using the filtered image data; and

determining if a width of the approximate image data is greater than a width of a mask of the filter; and

if the width of the approximate image data is greater than the width of the mask of the filter, filtering edges of the approximate image data.

8. The method recited in claim 7, farther comprising:

scan converting portions of the approximate image data outside of the width of the mask of the filter.

9. A method of rendering an image, comprising:

sampling actual image data for a contour to be rendered;

determining approximate image data for one or more line segments that approximate the contour to be rendered;

filtering the line segments by convoluting approximate image data with a filter to cause the filter to optimally center spectral energy of the sampled image data on an area in a spectral domain corresponding to sample spacing of the sampled image data in the spatial domain, to produce filtered image data;

rendering the contour using the filtered image data; and

determining if one or more line segments intersect within a mask of the filter; and

if one or more line segments intersect with the mask of the filter,

dividing an integral region defined by the mask of the filter and the intersecting line segments into two or more areas without intersections of the line segment, and

filtering each of the two or more areas separately.

10. A tool for rendering an image, comprising:

an original image data store that stores original image data;

a line segment determining module that determines line segment data approximating a contour of the original image data;

a convolution module that convolutes the line segment data with a filter to produce filtered image data wherein the filter is the function h where;

$<br><br>h=\arg <br><br><br><br>\underset{h}{\max }<br><br>\frac{\int <br><br>{\int <br><br>}_{\mathrm{\Omega <br><br>}}<br><br>{<br><br>\left[F<br><br>\left(h\right)\right]<br><br>\left({\mathrm{\omega <br><br>}}_x<br><br>{\mathrm{\omega <br><br>}}_y\right)<br><br>}^2<br><br><br><br>d<br><br>{\mathrm{\omega <br><br>}}_x<br><br>d<br><br>{\mathrm{\omega <br><br>}}_y}{\int <br><br>\int <br><br>{<br><br>\left[F<br><br>\left(h\right)\right]<br><br>\left({\mathrm{\omega <br><br>}}_x<br><br>{\mathrm{\omega <br><br>}}_y\right)<br><br>}^2<br><br><br><br>d<br><br>{\mathrm{\omega <br><br>}}_x<br><br>d<br><br>{\mathrm{\omega <br><br>}}_y},$

and

a scan conversion module that scan converts portions of the line segment data that are beyond a width of a mask of the filter from an edge of the line segment data.

11. The tool recited in claim 10, further comprising an accumulation buffer that stores the scan converted portions of the line segment data.

12. The tool recited in claim 10, further comprising an accumulation buffer that stores filtered image data.

13. The tool recited in claim 10, further comprising an integral look-up table that stores values for the convolution of image data with the filter.

14. A method of rendering an image, comprising:

obtaining actual image data for a contour to be rendered;

determining approximate image data for one or more line segments that approximate the contour to be rendered;

filtering the line segments by convoluting the approximate image data with a filter;

rendering the contour using the filtered image data;

determining if a width of the approximate image data is greater than a width of a mask of the filter; and

if the width of the approximate image data is greater than the width of the mask of the filter, filtering edges of the approximate image data.

15. The method recited in claim 14, further comprising:

scan converting portions of the approximate image data outside of the width of the mask of the filter.

16. A method of rendering an image, comprising:

obtaining actual image data for a contour to be rendered;

determining approximate image data for one or more line segments that approximate the contour to be rendered;

filtering the line segments by convoluting the approximate image data with a filter;

rendering the contour using the filtered image data; and

determining if one or more line segments intersect within a mask of the filter; and

if one or more line segments intersect with the mask of the filter,

dividing an integral region defined by the mask of the filter and the intersecting line segments into two or more areas without intersections of the line segment, and

filtering each of the two or more areas separately.

17. A method of rendering an image, comprising:

sampling image data;

filtering the image data by convoluting the image data with a filter to cause the filter to optimally center spectral energy of the sampled image data on an area in a spectral domain corresponding to sample spacing of the sampled image data in the spatial domain, to produce filtered image data; and

rendering the filtered image data,

wherein the filter is the function h where

$<br><br>h=\arg <br><br><br><br>\underset{h}{\max }<br><br>\frac{\int <br><br>{\int <br><br>}_{\mathrm{\Omega <br><br>}}<br><br>{<br><br>\left[F<br><br>\left(h\right)\right]<br><br>\left({\mathrm{\omega <br><br>}}_x<br><br>{\mathrm{\omega <br><br>}}_y\right)<br><br>}^2<br><br><br><br>d<br><br>{\mathrm{\omega <br><br>}}_x<br><br>d<br><br>{\mathrm{\omega <br><br>}}_y}{\int <br><br>\int <br><br>{<br><br>\left[F<br><br>\left(h\right)\right]<br><br>\left({\mathrm{\omega <br><br>}}_x<br><br>{\mathrm{\omega <br><br>}}_y\right)<br><br>}^2<br><br><br><br>d<br><br>{\mathrm{\omega <br><br>}}_x<br><br>d<br><br>{\mathrm{\omega <br><br>}}_y},$

[F(h)] denotes the Fourier transform of h and Ω

is the area in the spectral domain corresponding to sample spacing of the sampled image data in the spatial domain.

18. The method recited in claim 17, wherein the area Ω

=[−

Ω

, Ω

]×

[−

Ω

, Ω

] in the spectral domain, where Ω

=π

/T and T is the sample spacing for the sampled image data in the spatial domain.

19. A method of rendering an image, comprising:

sampling image data;

filtering the image data by convoluting the image data with a filter to cause the filter to optimally center spectral energy of the sampled image data on an area in a spectral domain corresponding to sample spacing of the sampled image data in the spatial domain, to produce filtered image data; and

rendering the filtered image data,

wherein the filter is a revolutionary filter h(r, θ

), defined as

$<br><br>h<br><br>\left(r,\mathrm{\theta <br><br>}\right)=\underset{k=0}{\overset{M}{\sum <br><br>}}<br><br>h_k<br><br>r^k,$

wherein r ∈

[0, R].

20. The method recited in claim 19, wherein a mask of the revolutionary filter has a radius of 1 pixel.

21. A method of rendering an image, comprising:

sampling image data;

filtering the image by convoluting the image data with a filter to cause the filter to optimally center spectral energy of the sampled image data on an area in a spectral domain corresponding to sample spacing of the sampled image data in the spatial domain, to produce filtered image data; and

rendering the filtered image data,

wherein the filter is a square filter h(x) defined as

$<br><br>h<br><br>\left(x\right)=\underset{k=0}{\overset{M}{\sum <br><br>}}<br><br>h_k<br><br>x^{2<br><br>k},$

where (|x|≦

R).

22. The method recited in claim 21, wherein a mask of the square filter has an area of 2 pixels by 2 pixels.