Grayscale character generator and method

• US 4,851,825 A
• Filed: 07/24/1987
• Issued: 07/25/1989
• Est. Priority Date: 07/24/1987
• Status: Expired due to Fees

• Current Assignee: Abraham C. Naiman
• Original Assignee: Abraham C. Naiman
• Inventors: Naiman, Abraham C.
• Primary Examiner(s): Brigance, Gerald L.
• Application Number:
  US07/077,791
• Time in Patent Office: 732 Days
• Field of Search: 340/728, 340/793, 340/750, 340/748, 340/798, 340/735, 364/518, 364/521
• US Class Current: 345/596
• CPC Class Codes: G06K 15/02 using printers
• CPC Class Codes: G06K 2215/0045 Converting outline to bitmap
• CPC Class Codes: G06K 2215/006 Anti-aliasing raster data
• CPC Class Codes: G09G 5/28 for enhancement of character form, e.g. smoothing

Abstract

A method and system for efficiently generating grayscale character fonts from bi-level master character fonts decomposed into rectangles. For each filter array to be used for converting master character fonts into grayscale characters there is generated at least one summed area filter array. Each element in each summed area filter array represents the sum of the filter array elements in a corresponding subarray of the filter array. A grayscale character is generated by performing, for each rectangle in the corresponding decomposed master character, the steps of:

specifying a filter array, and its corresponding summed area filter arrays;

determining the pixels in the grayscale character affected by the rectangle and a set of corresponding sampling points located inside and near the rectangle;

for each grayscale character pixel affected by the rectangle, performing the steps of:

assigning the pixel a predefined value corresponding to a black pixel if the corresponding sampling point is located inside the rectangle, and is offset from the perimeter of the rectangle by at least one half of the extent of the filter'"'"'s support; and otherwise

adding to the value of the grayscale pixel a value from the summed area filter array corresponding to the intersection of the selected filter array, centered at the sampling point corresponding to the grayscale pixel, and the rectangle.

Claims

1. A method of generating grayscale characters from bi-level master characters, the steps of the method comprising:

providing a multiplicity of high resolution bi-level master characters, each said bi-level master character comprising a high resolution grid of bi-level pixel values;

said providing step providing a set of rectangles representing the rectangular decomposition of each said bi-level master character;

providing at least one filter array for converting said high resolution master characters into lower resolution grayscale characters, each filter array having a designated center and an array of elements with a resolution corresponding to the resolution of said master characters, the values of said filter elements representing the contributions of corresponding bi-level master pixel values to a grayscale pixel located at the center of said filter array;

specifying a sampling grid of grayscale pixels having a lower resolution than the resolution of said selected bi-level master character; and

generating each grayscale character by performing, for at least a multiplicity of said rectangles in said set of rectangles representing the decomposition of a corresponding one of said master characters, the steps of;

specifying the location of said rectangle with respect to said sampling grid of grayscale pixles;

specifying a filter array to be used;

determining the grayscale pixels in said sampling grid affected by said rectangle by determining the sampling grid pixels for which at least one nonzero element of said specified filter array will overlap said reactangle when said specified filter array is centered on said pixels;

for each said sampling grid grayscale pixel affected by said rectangle, performing the steps of;

assigning said grayscale pixel a predefined value corresponding to a black pixel if the nonzero elements of said specified filter array are all inside said rectangle when said filter array is centered at said grayscale pixel; and

otherwise

determining the intersection of said specified filter array, centered at said grayscale pixel, and said rectangle, and adding to the value of said grayscale pixel a value equal to the sum of said specified filter array'"'"'s elements in said intersection.

2. The method set forth in claim 1, wherein said set of rectangles representing the rectangular decomposition of each said bi-level master character excludes rectangles less than a certain specified size.

3. The method set forth in claim 1, wherein said first providing step provides a set of nonoverlapping rectangles for each said master character.

4. The method set forth in claim 1, wherein said second providing step provides a plurality of filter arrays, and said generating step includes the step of specifying one of said plurality of filter arrays to be used with each of said multiplicity of rectangles;

whereby different filter arrays can be used with different rectangles when generating grayscale characters.

5. A method of generating grayscale characters from bi-level master characters, the steps of the method comprising:

providing a multiplicity of high resolution bi-level master characters, each said bi-level master character comprising a high resolution grid of bi-level pixel values;

said providing step providing a set of rectangles representing the rectangular decomposition of each said bi-level master character;

providing at least one filter array for converting said high resolution master characters into lower resolution grayscale characters, each filter having a designated center and an array of elements with a resolution corresponding to the resolution of said master characters, the values of said filter elements representing the contributions of corresponding bi-level master pixel values to a grayscale lixel located at the center of said filter array;

each said filter array having a filter support corresponding to the extent of said filter array'"'"'s nonzero elements; and

providing, for each filter array, at least one summed area filter array, wherein each element in said summed area filter array represents the sum of the filter array elements in a corresponding rectangular subarray of said filter array;

specifying a sampling grid of grayscale pixels having a lower resolution than the resolution of said selected bi-level master character; and

generating each grayscale character by performing, for each said rectangle in said set of rectangles representing the decomposition of a corresponding one of said master characters, the steps of;

specifying the location of said rectangle with respect to said sampling grid of grayscale pixels;

specifying a filter array to be used;

determining the grayscale pixels in said sampling grid affected by said rectangle by determining the sampling grid pixels for which at least one non-zero element of said specified filter array will overlap said rectangle when said specified filter array is centered on said pixels;

for each said grayscale pixel in said sampling grid affected by said rectangle, performing the steps of;

aasigning said grayscale pixel a predetermined value corresponding to a black pixel if the filter support for said specified filter array is totally inside said rectangle when said filter array is centered at said grayscale pixel; and

otherwise

determining te intersection of a selected filter array, centered at said grayscale pixel, and said rectangle, and adding to the value of said grayscale pixel a value from an element of the summed area filter array corresponding to said specified filter, said element corresponding to the subset of said filter array in said determined intersection.

6. The method set forth in claim 5, wherein

each said filter array is a two dimensional array of elements, including four corner elements;

said third providing step provides four different summed area filter arrays for at least one said fitler array, the elements in each said summed area filter array representing the sum of corresponding rectangular subsets of said filter array when a corresponding one of said four corner elements is included in said rectangular subset; and

said adding step includes, when said determined intersection includes at least one of said four corner elements of said specified filter array, the steps of selecting the corresponding one of said four different summed area filter arrays, selecting from said selected summed area filter array a single element which corresponds to the rectangular subset of said filter array in said determined intersection, and adding the value of said selected single element to the value of said grayscale pixel.

7. A method of generating grayscale characters from bi-level master characters, the steps of the method comprising:

providing a multiplicity of high resolution bi-level master characters, each said bi-level master character comprising a high resolution grid of bi-level pixel values;

said providing step providing a set of rectangles representing the rectangular decomposition of each said bi-level master character;

providing at least one filter array for converting said high resolution master characters into lower resolution grayscale characters, each filter array having a designated center and an array of elements with a resolution corresponding to the resolution of said master characters, the values of said filter elements representing the contributions of corresponding bi-level master pixel values to a grayscale pixel located at the center of said filter array;

each said filter array having a filter support corresponding to the extent of said filter array'"'"'s nonzero elements;

providing, for each filter array, a summed area filter array, wherein each element in said summed area filter array represents the sum of the filter array elements in a corresponding subarray of said filter array;

specifying a sampling grid of grayscale pixels having a lower resolution than the resolution of said selected bi-level master characters; and

generating a grayscale character by performing, for at least a multiplicity of said rectangles in said set of rectangles representing the decomposition of a corresponding one of said master characters, the steps of;

specifying the location of said rectangle with respect to said sampling grid of grayscale pixels;

specifying a filter array to be used with said rectangle;

determining the grayscale pixels in said sampling grid affected by said rectangle by determining the sampling grid pixels for which said filter support of said specified filter array overlaps said rectangle when said specified filter array is centered on said pixels;

for each said grayscale pixel in said sampling grid affected by said rectangle, determining the intersection of said rectangle and said specified filter array, centered at the grayscale pixel corresponding to said grayscale pixel, and said rectangle, and then adding to the value of said grayscale pixel the value of an element in said summed area filter array corresponding to said specified filter array, said element corresponding to the subset of said filter array in said determined intersection.

8. The method set forth in claim 7, wherein said generating step includes the step of assigning to each said grayscale pixel a predefined value corresponding to a black pixel if the filter support for said specified filter array is totally inside said rectangle when said filter array is centered at the said grayscale pixel in said sampling grid.

9. The method set forth in claim 8, wherein each said filter array is a two dimensional array of elements including four corner elements, and said third providing step provides a set of four different summed area filter arrays for at least one said filter array, the elements in each said summed area filter array representing the sum of corresponding rectangular subsets of said filter array when a corresponding one of said four corner elements is included in said rectangular subset;

and

said adding step includes selecting a summed area filter array from said set of four different summed area filter arrays, in accordance with the ones of said four corner elements in said determined intersection.

10. The method set forth in claim 7, wherein said second providing step provides a plurality of filter arrays, and said generating step includes the step of specifying one of said plurality of filter arrays to be used with each of said multiplicity of rectangles;

whereby different filter arrays can be used with different rectangles when generating grayscale characters.

11. Apparatus for generating grayscale characters from bi-level master characters, comprising:

first storage means for storing master font data representing a multiplicity of high resolution bi-level master characters, each said bi-level master character comprising a high resolution grid of bi-level pixel values;

said master font data including a set of rectangles representing the rectangular decomposition of each bi-level master character to be used;

second storage means for storing filter data, including at least one filter array for converting master characters into grayscale characters, each filter array having a designated center and an array of elements with a resolution corresponding to the resolution of said master characters, the values of said filter elements representing the contributions of corresponding bi-level master pixel values to a grayscale pixel located at the center of said filter;

each said filter array having a filter support corresponding to the extent of said filter array'"'"'s nonzero elements;

said filter array being stored in the form of a summed area filter array, wherein each element in said summed area filter array represents the sum of the filter array elements in a corresponding rectangular subarray of said filter array; and

data processing means for generating a specified grayscale character, including software means for processing at least a multiplicity of said rectangles in said set of rectangles representing the decomposition of a corresponding one of said master characters, said software means including;

means for specifying a filter array to be used with said rectangle;

means for specifying a sampling grid of grayscale pixels having a lower resolution than the resolution of said selected bi-level master character;

means for specifying the location of said rectangle with respect to said sampling grid of grayscale pixels;

means for determining the grayscale pixels in said sampling grid affected by said rectangle by determining the grayscale pixels for which said filter support of said specified filter array overlaps said rectangle when said specified filter array is centered on said grayscale pixels; and

grayscale value assigning means for assigning values to each said grayscale pixel affected by said rectangle, including;

intersection determining means for determining the intersection of said rectangle and said specified filter array, centered at said grayscale pixel; and

adding means for adding to the value of said grayscale pixel the value of an element in said summed area filter array corresponding to said specified filter array, said element corresponding to the subset of said filter array in said determined intersection.

12. The apparatus set forth in claim 11, wherein said grayscale value assigning means further includes black pixel assigning means for assigning to a grayscale pixel a predefined value corresponding to a black pixel if the filter support for said specified filter array would be totally inside said rectangle when said filter array is centered at said grayscale pixel in said sampling grid.

13. The apparatus set forth in claim 11, wherein said second storage means stores a plurality of filter arrays, and said data processing means includes means for specifying one of said plurality of filter arrays to be used with each of said multiplicity of rectangles;

whereby different filter arrays can be used with different rectangles when generating grayscale characters.

14. The apparatus set forth in claim 11, wherein each said filter array is a two dimemsional array of elements including four corner elements, and said second storage means stores a set of four different summed area filter arrays for at least one said filter array, the elements in each said summed area filter array representing the sum of corresponding rectangular subsets of said filter array when a corresponding one of said four corner elements is included in said rectangular subset;

and

said adding means includes means for selecting a summed area filter array from said set of four different summed area filter arrays, in accordance with the ones of said four corner elements in said determined intersection.