 |
Claims  |
|
|
What is claimed is:
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. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
The invention relates generally to grayscale display and printing systems
and methods, and more specifically to systems and methods for generating
grayscale character fonts for use in grayscale display and printing
systems.
BACKGROUND OF THE INVENTION
Until recently, most text on raster displays used characters represented as
binary matrices, with ones and zeros corresponding to the black and white
dots to be displayed. Typically, only one set of characters was provided,
simple and tuned to the characteristics of the display.
While bi-level matrix representations of characters work quite well when
high-resolution characters and display devices are available, at low
resolutions--such as on computer terminals and low cost laser
printers--the one-bit characters do not accurately resemble their analog
predecessors. FIG. 1 shows how two characters from the Latin 725 Medium
font look when printed using a low resolution bi-level font, and when
using a grayscale font at the same resolution. As shown in FIG. 1,
grayscale devices can increase the effective resolution of a character
with a fixed number of pixels by using gray pixels in the representation
of a character, as well as black and white ones. Note that for the
purposes of this specification, the term "display" refers both to monitor
type display devices, and to printers.
The terms "bi-level" and "bi-modal" are used synonymously with the term
"black and white" for describing displays and images defined by pixels
which are either on or off (i.e., white or black). For the purposes of
this description, white pixels form the background, while black pixels
form characters.
The term "master character font" refers to any high resolution, bi-level
character font which can be used as the basis for generating a "grayscale
character font", which is a lower resolution character font in which each
pixel is defined using a "grayscale" having a multiplicity (i.e., more
than two) of available values.
The terms "summed area filter", "summed area table", "summed area filter
array", and "summed area array" are used interchangeably herein, except
where otherwise indicated.
Using the present invention, master character fonts are decomposed into
rectangles, and each individual rectangle is efficiently convolved with a
summed area representation of a filter to construct the grayscale
character.
The use of grayscale fonts is based on the principle that, as objects
become too small to resolve spatially, size and intensity become
interchangeable. One of the principle functions carried out by the human
visual system is to find edges in the scene being viewed. When objects are
too small to resolve spatially--such as a pixel from a sufficient viewing
distance--the gray intensity of that object may be "misinterpreted" as
spatial components of light and dark; i.e., an "edge" will be inferred
where there really is an area of uniform illumination. It is this
perceptual effect which is exploited in the use of grayscale.
Note that grayscale pixels provide no information about the orientation of
the inferred edge; that information is deduced by the visual system based
on the intensities of the surrounding pixels. For example, assuming for
the moment that only the immediately adjacent pixels will influence the
perception of a selected grayscale pixel, if the pixels to the left are
black, the pixels to the right are white, and those above and below are
the same gray as the selected pixel, a vertical edge will be perceived
with a sub-pixel position (i.e., at a position between standard pixel grid
points) depending on the intensity of the gray pixels. On the other hand,
if the pixels above are white, the pixels below are black, and the pixels
to the left and right are gray, a horizontal edge will be perceived with a
sub-pixel position again depending on the intensity of the gray pixels.
Notice, therefore, that the same value of gray in a selected pixel will at
one time be interpreted as resolution in the hoizontal direction and at
another time in the vertical direction (or even some other orientation,
depending on the surrounding pixels). In other words, once orientation
information of the perceived edge is resolved with respect to the
surrounding pixels, the grayscale is utilized as resolution information.
Therefore, to a first approximation, the added number of grayscale levels
(not the added number of bits) is advantageously exploited regardless of
the orientation of the edge; it merely serves to position the edge more
precisely.
For many applications (such as text entry), it will be sufficient to
provide a single version of a grayscale font for each size and style which
is needed on a particular display device. However, since grayscale can be
used to achieve sub-pixel positioning of edges, one could generate many
grayscale versions of the same font at a particular size and for a
specific device, each differing only slightly from the next in terms of
the sub-pixel position of the character's edges. By using the particular
grayscale version which best approximates each character's specified
sub-pixel position, one could reduce the spacing error that would
otherwise result from positioning characters on whole pixel boundaries.
The standard method of generating grayscale fonts in the prior art is to
filter bi-level master character fonts. Unfortunately, most of the
previously known, efficient filtering techniques cannot directly be
applied. For example, prefiltering is impractical, due to the number of
character masters and the requirement of sub-pixel positioning.
The present invention concerns a fast filtering technique especially
adapted to the task of producing grayscale fonts from high resolution
bi-level master fonts. An important feature of the present invention is
that it is so efficient that filtering characters for grayscale displays
is feasible in realtime on personal computers and personal workstations.
Although grayscale text has gotten some limited commercial exposure lately
(e.g., IBM's Yoda terminal and Bitstream Inc.'s grayscale fonts), two
factors have combined to restrict its usage mainly to specialized
environments such as paint programs and slide preparation packages, where
the grayscale value is used as a weight for interpolating between the text
color and a variegated background.
First, the techniques previously discussed in the literature are
computationally expensive, and second, there has been little quality
control over the resultant fonts. Furthermore, a model of each device must
be incorporated into the font generation system because the generation of
gray pixels depends on the characteristics of the display device,
including pixel size, pixel shape (point spread function), overlap,
intensity gamma, and spatial inhomogeneities. Otherwise, good-looking
fonts produced for one monitor may not perform well on another. See
Kajiya, J. and M. Ullner, "Filtering High Quality Text for Display on
Raster Scan Devices," Computer Graphics, Volume 15, Number 3, SIGGRAPH
1981 Proceedings (August 1981) pp. 7-15.
Therefore a primary object of the present invention is to provide a font
production tool which is efficient and filter independent. With
appropriate parametrization of a display device's characteristics in the
form of an appropriate filter or set of filters, the invention will
efficiently produce device dependent grayscale fonts from a master font
library.
As will be described below, the present invention can efficiently produce
numerous fonts at numerous sizes, for various devices, and can use
different filters for different applications. In order for this task to be
feasible, fonts must be producible at rates far greater than have
heretofore been reported. The detailed description shows how, by meeting a
few reasonable assumptions, one can drastically reduce the computational
expense of generating grayscale fonts for both experimentation purposes,
and more generally for font production.
SUMMARY OF THE INVENTION
In summary, the present invention is a method and system for efficiently
generating grayscale character fonts from master fonts. The master
character fonts, which are bi-level arrays, are decomposed into
rectangles. For each filter array to be used for converting master
character fonts into grayscale characters there is generated, at least
one, and preferably four summed area filter arrays. Each element in each
summed area filter array represents the sum of the filter array elements
in a corresponding subarray of the filter array. To be more specific, when
the filter is overlapped with a rectangle, the sum of all the elements of
the filter in the overlap region is found by extracting one or more
elements from the corresponding summed area filter--as determined by the
intersection of the filter and the rectangle.
Each filter array is said to have "a filter support" corresponding to the
bounded area including all nonzero values of the filter array.
Each 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 (i.e., within half the extent of the filter support of the
perimeter of 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 a middle region of the
rectangle, which is offset from the perimeter of the rectangle by one half
of the extent of the specified filter's support; and otherwise
determining the intersection of the selected filter array, centered at the
sampling point corresponding to the grayscale pixel, and the rectangle,
and adding to the value of the grayscale pixel a value from the summed
area filter array corresponding to the determined intersection.
BRIEF DESCRIPTION OF THE DRAWINGS
Additional objects and features of the invention will be more readily
apparent from the following detailed description and appended claims when
taken in conjunction with the drawings, in which:
FIG. 1 depicts two characters from Latin 725 Medium, showing how these
characters look when printed using a low resolution bi-level font, and
when using a grayscale font at the same resolution.
FIG. 2 schematically depicts the direct convolution process for generating
grayscale characters.
FIG. 3 shows a filter array and four summed area array representations of
the filter.
FIG. 4 is a flow chart of the method of the present invention.
FIG. 5 shows nine areas of interest in a rectangle which spans the width
and height of the filter.
FIG. 6 shows one example where the minimal decomposition with overlapping
rectangles generates fewer intermediate gray pixels than a minimal
decomposition with disjoint rectangles.
FIG. 7 depicts a computer system incorporating the present invention.
DESCRIPTION OF THE PREFERRED EMBODIMENT
Filtering
Referring to FIG. 2, the common method for generating a grayscale character
is filtering, whereby a high-resolution raster-encoded master character is
convolved with a filter. In particular, a master character 22, is
convolved with a filter 24 at each of a predefined array of sample points
26, to generate a grayscale character 28. For each sample point 26 there
is generated one grayscale pixel 30 having a value equal to the sum of the
filter's values at the black pixels in the master character.
Filters can be defined in various ways, very often analytically (see, for
example, Pratt, W. K., Digital Image Processing, John Wiley and Sons, New
York, 1978). For the purposes of the present invention, values of the
filter are needed only at the locations of the master and therefore each
filter is represented by a digitized array of filter values at the
resolution of the master.
To simplify the description of the invention, all the two dimensional
arrays used will be square and the following notation will be used:
M is an m.times.m pixel array representing a high-resolution master
character, with each pixel having a binary (i.e., 0 or 1) value.
G is a g.times.g pixel array representing a low-resolution grayscale
character, with each pixel having a grayscale value between 0 and 1,
inclusive.
F is an f.times.f pixel array representing a filter for a given filter type
and filter overlap, .PHI.. The linear size, f, of the F array is equal to
.PHI.m/g, and the pixels in F are scaled (i.e., have differing values
between zero and one) so that F is normalized:
##EQU1##
S is an s.times.s sampling grid where s=g, with a spacing interval of
.sigma.=m/g (the ratio between the master and grayscale sizes) between
samples. The master font M is overlaid with S. Note that there are
.sigma..times..sigma. different phases at which S can be overlaid onto M:
if p.times.p different phases (i.e., grayscale character sub-pixel
positions) are needed, then s=pg with spacing interval .sigma.=m/pg
if all of the possible phases are needed, then s=m and .sigma.=1
F is centered at each of the sampling points S.sub.xy and convolved with M,
producing up to p.times.p different g.times.g grayscale characters.
The present invention assumes that its users will provide an appropriate
filter (or filters) for convolution with the character master, which
sufficiently models the display device so that it can regard it as a
linear device in both intensity and space. Filters to be used simply for
demonstrating the invention are easy to generate, for example, by using a
simple, two dimensional array of values representing a two dimensional
bell curve. It should be noted, however, that there is a large body of
prior art regarding numerous important issues affecting the quality of the
characters generated using grayscale fonts, including:
the appropriateness of particular filters; see, for example, Warnock, J.
E., "The display of Characters Using Gray Level Sample Arrays," Computer
Graphics, Volume 14, Number 3, SIGGRAPH 1980 Proceedings (July 1980) pp.
302-307, and Catmull, E., "A Tutorial on Compensation Tables," Computer
Graphics, Volume 13, Number 2, SIGGRAPH 1979 Proceedings (August 1979) pp.
1-7.
reconstruction of master character fonts from displayed (grayscale)
samples; see, for example, Kajiya, J. and M. Ullner, "Filtering High
Quality Text for Display on Raster Scan Devices," Computer Graphics,
Volume 15, Number 3, SIGGRAPH 1981 Proceedings (August 1981) pp. 7-15.
modeling of the characteristics of display devices; see, for example,
Shurtleff, D. A., How to Make Displays Legible, Human Interface Design, La
Mirada, Calif., 1980.
the number of grayscale bits necessary; see, for example, Leler, W. J.,
"Human Vision, Anti-Aliasing, and the Cheap 4000 Line Display," Computer
Graphics, Volume 14, Number 3, SIGGRAPH 1980 Proceedings (July 1980) pp.
308-313, and Bruckstein, A. M., "On Optimal Image Digitization,"
Electrical Engineering Publication Number 577, Faculty of Electrical
Engineering, Technion Israel Institute of Technology, Haifa, Israel,
February 1986, and
possible fatigue of the visual system; see, for example, Gould, J. D. and
N. Grischkowsky, "Doing the Same Work with Hard Copy and with Cathode-Ray
Tube (CRT) Computer Terminals," Human Factors, Volume 26, Number 3, June
1984, pp. 323-337.
The Problem With Direct Convolution
The straightforward solution to generating grayscale characters is direct
convolution, where the filter F is centered at each of the sampling points
S.sub.xy and all the elements of the master font M under F are multiplied
by the values of F and summed. Note that since, in our case, M is binary,
only a summing operation is necessary. Thus, direct convolution is defined
in this case to be:
##EQU2##
where S.sub.i and S.sub.j are the x and y positions in M corresponding to
the lower left hand corner of the filter for graysoale pixe G.sub.ij.
In this description, the notation O(), called big "O" notation in
theoretical computer science, refers to the general order of complexity
for solving a particular problem. For instance, the cost of direct
convolution as described above is O(s.sup.2 .times.f.sup.2)--i.e., the
cost, or number of computations, is on the order of the product of s.sup.2
and f.sup.2.
Not all of the work in the direct convolution method is necessary.
Specifically, using direct convolution, the same amount of computation is
performed to generate each grayscale pixel regardless of whether that
pixel turns out to be black, white, or gray.
However, if all of the f.times.f pixels of M within .+-.f/2 of S.sub.xy are
on (off), the grayscale pixel will be black (white). In other words, the
direct convolution operation generates a black (white) pixel at the same,
expensive cost of generating a gray one. Furthermore, much of the summing
operation in direct convolution is repeated over and over for the same
regions of F, especially when more than one phase is needed.
As shown in Table 1, the actual gray percentage of a character--the number
of gray pixels divided by the total number of pixels--is a function of
font, character, size, resolution, filter size, filter shape, and sampling
phase. Nevertheless, except for very low resolutions, a large majority of
the pixels will be either white or black for a wide variety of character
fonts.
Thus, it is disadvantageous to be performing the relatively expensive
direct convolution operation for each of these black or white pixels,
rather than a much cheaper operation which directly generates black or
white pixels. As will be seen, the present invention uses a method which
is extremely efficient for generating black and white pixels.
TABLE 1
______________________________________
Grayscale Percentage of Two Fonts
Swiss 721 Bold and Latin 725 Medium
at various grayscale character and filter sizes (in pixels)
using 256 .times. 256 master characters
Grayscale Filter Grayscale Percentage
Size Overlap Size Swiss 721
Latin 725
______________________________________
16 1.0 16 16 18
32 1.0 8 8 9
64 1.0 4 3 3
16 1.25 20 21 22
32 1.25 10 10 11
64 1.25 5 5 6
16 1.5 24 25 26
32 1.5 12 12 14
64 1.5 6 5 6
______________________________________
Positioning Accuracy
Positioning accuracy is a problem with both bi-level and grayscale
bitmapped displays (i.e., those in which a displayed image is represented
by a bitmap of discrete pixels). The simplest example of the positioning
problem is that if we want to position a vertical edge at a specified
sub-pixel position and can only position the edge on pixel boundaries,
then we may be off by as much as one half of a pixel in positioning
accuracy. To position an edge 25% of the way between two pixel positions,
the image (e.g., a character) with the edge can be prefiltered so that the
pixel column representing the edge has values interpolated 25% of the way
between the background (white) and foreground (black) colors. However, if
this prefiltered image is now our only representation of the edge, the
edge may still be off by as much as a half a pixel when one needs to
display the image at other sub-pixel positions.
The only methods of achieving improved positioning accuracy are (1) to
dynamically filter the edge (i.e., of the image) to the needed sub-pixel
position, and (2) to prefilter the edge for all of the possible sub-pixel
positions.
If filtering of the edge can be done for any of p equally spaced sub-pixel
positions, then our maximum positioning error is reduced to 1/2p.
In the context of displaying characters, such as a display of the text of
this specification, if we have a 1/2 pixel error in the positioning of a
character, one character pair may appear too closely set by 1/2 a pixel,
while the next pair seems too loosely set by 1/2 a pixel. Where the size
of a pixel is large relative to the size of the character, this can lead
to disastrous spacing problems. Even for state of the art monitors with a
resolution of approximately two pixels per typographer's point, when
setting 10-point text (0.1384 inches high, or about 0.35 cm), a 1/2 pixel
error is about 10% of the average inter-character spacing (one quarter of
the point size), which would result in variations in the spacing of pairs
of characters to be as much as 20%. By using eight different phases in
generating the grayscale characters, this error can be reduced to 1.25%
and 2.5%. For more common monitors with a resolution of about 1 pixel per
typographer's point, the inter-character spacing errors and variations are
20% and 40%, and eight phases can reduce these to 2.5% and 5%.
In some contexts, the use of a single phase for each gray-scale character
may be sufficient. However, because the accurate spacing of characters is
such an important part of generating high-quality text, the need for
utilizing the best possible phases is crucial. Furthermore, not only are
different phases needed in the horizontal dimension for accurate
positioning of proportionally spaced text, but in the vertical direction
as well, in order not to be restricted to leading (i.e., line spacing) of
an integral number of pixels and for the proper positioning of
superscripts, subscripts, equations, and tabular information.
For many applications, grayscale characters may be needed for several fonts
at numerous sizes and for each of, say, 8.times.8 phases. Since the user
may not know ahead of time exactly which characters will be called for, if
precomputing the fonts is deemed necessary, all of the possible phase
renditions must be generated. However, this may be impractical due to
limited storage space.
For example, if Roman, Bold, Italic, and Bold-Italic versions of a 128
character serif and sans-serif font are needed (not including special
characters and mathematical symbols) for a 72 pixels per inch, eight bits
per pixel screen, at five font sizes (e.g., 8, 10, 12, 14, and 18 points)
it will take approximately 51.75 Mb to store the 64 phases (without any
encoding):
______________________________________
4 font versions
x 2 serif/sans
x 128 characters
x 5 font sizes
x 64 phases
x 165.6 pixels (average grayscale font size)
x 1 byte/pixel
54,263,808 bytes = 51.75 Mb
______________________________________
Throw in a more generous selection of fonts (two families is very limited
for all but the most mundane tasks) and sizes (e.g., 6, 9, 11, 24, and 36
point), as well as a few monitors of different resolutions and filters of
varying suitability, and the storage requirements become astronomical.
Therefore, except for very common tasks such as text editing with fixed
pitch screen fonts of a single style, precomputing the grayscale
characters appears to be impractical. What we need, then, is the
capability to dynamically generate specified character fonts, at any
specified size, resolution, and phase, coupled with font caching software
to reduce the need to recompute already generated characters. See Fuchs,
D. R. and D. E. Knuth, "Optimal Font Caching," STAN-CS-82-901, Department
of Computer Science, Stanford University, Stanford, Calif., March 1982.
Rectangular Convolution
Let us reexamine where the work is being done during direct convolution.
For a particular sampling grid position S.sub.xy in the master character
corresponding to grayscale pixel G.sub.ij, the filter F is centered over
the sampling point and is convolved with the master; namely, for each
master pixel M.sub.S.sbsb.i.sub.+x,S.sbsb.j.sub.+y within the filter
support, the value in F.sub.xy is added to the output grayscale pixel
G.sub.ij, where S.sub.i and S.sub.j are the x and y positions in M
corresponding to the lower left hand corner of the filter for grayscale
pixel G.sub.ij. The term "filter support" is herein used to mean the
bounded area including all nonzero values of a filter.
Since the master pixels which fall within the filter support can form an
arbitrary pattern, each pixel must be examined to determine its
contribution from the filter. This is why the computational expense for
the direct convolution operation is O(f.sup.2) per sample.
Alternatively, if, instead of unrelated master pixels, we have a data
structure for the master character which describes it in terms of regions
of specific shapes, then the convolution operation for S.sub.i,S.sub.j
amounts to intersecting the filter array with the r regions of the master
character which fall within the filter support to produce O(r) subregions,
and extracting the contribution of each of those subregions to the
corresponding grayscale pixel G.sub.ij. Then the computational expense is
O(r.times.(cost of intersection+cost of extracting contribution)).
What we are looking for, then, is a shape which meets the following
criteria:
it is easy to generate from a bitmap;
it is compact in storage;
it is easy to intersect with the filter; and
it is simple to extract the filter contribution from the intersection.
Rectangles are a particularly appealing shape to use, since, for
characters, they fulfill each of these criteria.
Certainly, encoding a bitmap into 1.times.1 pixel rectangles is trivial.
(See the discussion below regarding optimal decomposition of bitmaps into
rectangles.) Although, in general, rectangular encoding may increase the
size of the representation (in the limit, there could be f.sup.2 1.times.1
pixel rectangles), since characters are very well connected objects--often
with rectilinearly oriented components--an encoding into rectangles is
likely to be very compact.
Summed Area Filter Arrays. To determine the contribution of a specified
rectangle--which represents a portion of a master character--to a
grayscale character, one must first determine for each sampling point in
that rectangle the overlap between the filter and the rectangle. This
overlap is sometimes called herein the "intersecting subrectangle".
Since the filters used in the preferred embodiment are stored in
rectangular arrays, the process of determining the intersection of a
rectangle with the filter (at a specified sampling point) requires four
comparisons to determine the rectilinear lines of intersection, and
generates at most one subrectangle. The process of determining the
contribution of the intersecting subrectangle to the corresponding
grayscale pixel would require, using direct convolution, summing all the
filter entries in the intersecting subrectangle.
However, the step of summing all the filter entries in the intersecting
subrectangles can be substantially reduced by using a summed area array
representation of the filter.
FIG. 3 shows a filter array 32 and four corresponding summed area filter
arrays 34A-34D. The entries of summed area filter array 34A are computed
as | | |
