Antialiasing with grey masking techniques

• US 5,737,455 A
• Filed: 12/12/1994
• Issued: 04/07/1998
• Est. Priority Date: 12/12/1994
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Klassen, R. Victor, Harrington, Steven J.
• Primary Examiner(s): Coles, Sr., Edward
• Assistant Examiner(s): WALLERSON, MARK E
• Application Number:
  US08/353,763
• Time in Patent Office: 1,212 Days
• Field of Search: 358/296, 358/448, 358/455, 358/451, 358/461, 358/462, 358/464, 358/456, 358/534, 358/535, 358/536, 358/537, 358/538, 395/102, 395/109, 395/128, 395/162, 395/101, 395/141, 395/126, 395/131, 395/132, 395/133, 395/135, 382/284, 382/268, 382/269, 382/266, 382/283, 345/43, 345/44, 345/113, 345/114, 345/136, 345/137
• US Class Current: 382/284
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: H04N 1/4092 Edge or detail enhancement

Abstract

A method of combining antialiased edges for printing or display at a grey level reproduction device, wherein pixels have shade values determined as a function of their neighbor'"'"'s shade values and mask values. Shade values are determined by processing each pixel in terms of subpixels forming the pixel. Each of a plurality of subpixels are assigned mask and shade values as a function of their position in the pixel and with respect to the nearest neighbors. The resulting values for each subpixel are averaged to determine a final output value for the pixel.

Claims

1. A method of combining continuous tone foreground and background images, said images comprised of pixels each assigned a mask value and a shade value, including:

1) providing a background image including pixels having a shade value, and at least one foreground image including pixels having a mask value and a shade value, wherein said received background and foreground images are received at a common resolution;

2) providing a high resolution version of a pixel of interest in the foreground image and the background image, including a plurality of subpixels;

3) assigning a mask value and a shade value to each subpixel as a function of its position in the pixel of interest and the values of nearest neighbors of the pixel of interest;

4) combining the assigned values for each subpixel in the pixel of interest to determine a final output value for the pixel of interest, whereby the combined image has an improved edge between the foreground and background images.

2. A method of combining continuous tone foreground and background images, said images comprised of pixels each assigned a mask value and a shade value, including:

1) providing a background image including pixels having a shade value, and at least one foreground image including pixels having a mask value and a shade value, wherein said received background and foreground images are received at different resolutions;

2) providing a high resolution version of a pixel of interest in the foreground image and the background image, including a plurality of subpixels, wherein said high resolution version of said pixel of interest is at a resolution selected to be a multiple of each of the different resolutions;

3) assigning a mask value and a shade value to each subpixel as a function of its position in the pixel of interest and the values of nearest neighbors of the pixel of interest;

4) combining the assigned values for each subpixel in the pixel of interest to determine a final output value for the pixel of interest, whereby the combined image has an improved edge between the foreground and background images.

3. The method as described in claim 2, wherein the multiple of each of the different resolutions is an integer value.

4. The method as described in claim 2, wherein one of said received background and foreground images is received at the high resolution, and the other is received at a substantially lower resolution, treating each high resolution received image pixels as a subpixel.

5. The method as described in claim 4, wherein,

said function applied in said step of assigning a mask value and a shade value to each subpixel operates to set the subpixel value equal to the received pixel value for the high-resolution image.

6. A method of processing an image displayable or printable at a number of grey levels G greater than about 2, and providing antialiasing for edges in such an image, the method comprising:

a) receiving mask and shade values for an antialiased image edge, for a pixel of interest and a plurality of neighbors thereto in an image;

b) subdividing the pixel of interest into a predetermined number of subpixels;

c) determining from the mask value for the pixel of interest a number p of subpixels that should be permeable;

d) determining a fractional permeability value for each subpixel as a function of the mask value of the pixel of interest, the mask value of at least one neighbor and the relative position of the subpixel in the pixel of interest and the at least one neighbor;

e) sorting the determined fractional permeability values by magnitude, and identifying subpixels having the p largest magnitudes as permeable;

f) determining for the pixel of interest and the plurality of neighboring pixels a minimum background shade value and a maximum background shade value;

g) determining from the shade value of the pixel of interest a number q of subpixels that should be set to the maximum background shade value;

h) determining a shade value for each subpixel as a function of the shade value of the pixel of interest, the shade value of at least one neighbor and the relative position of the subpixel in the pixel of interest and the at least one neighbor;

i) sorting the determined shade values by magnitude, assigning the maximum shade value to subpixels having the q largest shade values and assigning the minimum shade value to the remaining subpixels;

j) for each subpixel identified as permeable, resetting the shade value of that subpixel equal to an object shade;

k) averaging the shade values of all the subpixels to obtain the antialiased value of the pixel.

7. The method as defined in claim 6, wherein for the plurality of neighbors includes 8 adjacent pixels.

8. The method as defined in claim 6, wherein the predetermined number of subpixels is about 25.

9. The method as defined in claim 8, wherein p is determined by the function:

space="preserve" listing-type="equation">p=SM/.sub.N

where M is the mask value of the pixel of interest, S is the number of subpixels and N is the value of a fully permeable pixel.

10. The method as defined in claim 8, wherein q is determined by the function:

space="preserve" listing-type="equation">q=S(X-MN)/.sub.(MX-MN)

where

MN is said determined minimum shade value,

MX is said determined maximum shade value

S is the number of subpixels; and

X is the shade value of the pixel of interest.

11. The method as described in claim 6, and including:

comparing the mask value of the pixel of interest with the minimum and maximum mask values for the system;

immediately setting the pixel shade value to a background shade value if the mask value is a minimum mask value; and

immediately setting the pixel shade value to the object image value if the mask value is a maximum value.

12. The method as described in claim 6, and including:

comparing the determined background value of the pixel of interest with the minimum and maximum shade values for the system;

setting each pixel determined to have the minimum or maximum shade value to a value given by

space="preserve" listing-type="equation">(X.sub.M i+(N-X.sub.M)Xb)/.sub.N.

where

X_M is the mask value of pixel X

X_b is the background value of pixel X

i is the shade value of pixel X

N is the maximum possible mask value.

13. The method as described in claim 6, and including:

comparing the maximum value to the minimum value for the neighborhood of the pixel of interest;

setting each pixel determined to have the maximum value match the minimum value (MX=MN) to a value given by;

space="preserve" listing-type="equation">(X.sub.M i+(N-X.sub.M)Xb)/.sub.N.

where

X_M is the mask value of pixel X

X_b is the background value of pixel X

i is the shade value of pixel X

N is the maximum possible mask value.

14. A method of processing an image displayable or printable at a number of grey levels greater than about 2, and providing antialiasing for edges in such data, the method comprising:

a) for a foreground image defined in terms of pixels having mask values and shade values with an antialiased edge, to be combined with a background image defined in terms of pixels having shade values, receiving a pixel of interest and a plurality of neighboring pixels thereto in the image;

b) subdividing the pixel of interest into a predetermined number of subpixels;

c) determining, from the pixel of interest and a plurality of neighboring pixels thereto, which subpixels should be considered as permeable;

d) determining, from the pixel of interest and a plurality of neighboring pixels thereto, which subpixels should be considered to have the maximum shade values of said pixel of interest and said plurality of neighboring pixels thereto and which subpixels should have the minimum shade values of said pixel of interest and said plurality of neighboring pixels thereto;

e) setting any subpixels to the object shade if such pixels are determined permeable;

f) setting any subpixels that are not determined to be permeable to the determined one of the minimum or maximum shade values;

g) setting the pixel equal to the average shade value of all the subpixels.

15. The method as defined in claim 14, wherein the plurality of neighbors includes 8 adjacent pixels.

16. The method as defined in claim 14, wherein the predetermined number of subpixels is about 25.

17. The method as described in claim 14, and including:

comparing the mask value of the pixel of interest with the minimum and maximum mask values for the system;

immediately setting the pixel shade value to a background shade value if the mask value is a minimum mask value; and

immediately setting the pixel shade value to the foreground object shade value if the mask value is a maximum value.

18. The method as described in claim 14, and including:

comparing the determined background value of the pixel of interest with the minimum and maximum shade values for the system;

setting each pixel determined to have the minimum or maximum shade value to a value given by

space="preserve" listing-type="equation">(X.sub.M i+(N-X.sub.M)Xb)/.sub.N.

where

X_M is the mask value of pixel X

X_b is the background value of pixel X

i is the shade value of pixel X

N is the maximum possible mask value.

19. The method as described in claim 14, and including:

comparing the maximum value to the minimum value for the neighborhood of the pixel of interest;

setting each pixel determined to have the maximum value match the minimum value (MX=MN) to a value given by;

space="preserve" listing-type="equation">(X.sub.M i+(N-X.sub.M)Xb)/.sub.N.

where

X_M is the mask value of pixel X

X_b is the background value of pixel X

i is the shade value of pixel X

N is the maximum possible mask value.

20. A method of antialiasing edges for printing or display of an image at a grey level reproduction device, comprising:

a) for a foreground image defined in terms of pixels having mask values and shade values with an antialiased edge, to be combined with a background image defined in terms of pixels having shade values, receiving a pixel of interest and a plurality of neighboring pixels thereto in the image;

b) subdividing the pixel of interest into a predetermined number of subpixels;

c) assigning a mask value and a shade value to each subpixel as a function of the subpixel position in the pixel and with respect to the neighboring pixels, and the respective mask and shade values thereof;

d) setting any subpixels to an object shade if subpixels have a mask value indicating permeability;

e) setting remaining subpixels to one of the minimum and maximum shade values of the neighboring pixels;

f) setting the pixel of interest equal to the average shade value of all the subpixels.

21. The method as described in claim 20, and including:

comparing the mask value of the pixel of interest with the minimum and maximum mask values for the system;

immediately setting the pixel shade value to a background shade value if the mask value is a minimum mask value; and

immediately setting the pixel shade value to the object image value if the mask value is a maximum value.

22. The method as described in claim 20, and including:

comparing the determined background value of the pixel of interest with the minimum and maximum shade values for the system;

setting each pixel determined to have the minimum or maximum shade value to a value given by

space="preserve" listing-type="equation">(X.sub.M i+(N-X.sub.M)Xb)/.sub.N.

where

X_M is the mask value of pixel X

X_b is the background value of pixel X

i is the shade value of pixel X

N is the maximum possible mask value.

23. The method as described in claim 20, and including:

comparing the maximum value to the minimum value for the neighborhood of the pixel of interest;

setting each pixel determined to have the maximum value match the minimum value (MX=MN) to a value given by;

space="preserve" listing-type="equation">(X.sub.M i+(N-X.sub.M)Xb)/.sub.N.

where

X_M is the mask value of pixel X

X_b is the background value of pixel X

i is the shade value of pixel X

N is the maximum possible mask value.