Grayscale character generator and method4851825Abstract 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 What is claimed is: 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.
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 the sum of all the entries of the original array 32 to the left of and below the entry. These summed area arrays are similar to the summed area texture arrays discussed in (1) Crow, F. C., "Summed-Area Tables for Texture Mapping," Computer Graphics, Volume 18, Number 3, July 1984, SIGGRAPH 1984 Proceedings, pp. 207-212; and (2) Ferrari, L. A. and J. Sklansky, "A Fast Recursive Algorithm for Binary-Valued Two-Dimensional Filters," Computer Vision, Graphics, and Image Processing, Volume 26, 1984, pp. 292-302. As will also be shown below, using a single summed area filter, the cost of extracting the sum of an arbitrary rectangular area of the summed array is four summed array accesses and three additions (actually, two subtractions and one addition). To convolve a summed area filter at each sampling point in an arbitrary rectangle, four intersections between the filter (centered at the sampling point) and the rectangle must be computed: one each for the left, right, bottom, and top of the intersecting subrectangle. Using the boundaries of the subrectangle as indices into the lower left summed area filter (such as array 34A in FIG. 3), the convolution is performed by computing the sum: F.sub.tr -F.sub.br -F.sub.tl +F.sub.bl (Eq. 1) where F.sub.tr is the summer area filter entry for the top-right intersection between the filter and the rectangle, F.sub.br is the bottom-right entry, F.sub.tl is the top-left entry, and F.sub.bl is the bottom-left entry. Similar equations could be used with other ones of the four summed area filter arrays 34B-34D, but for the purposes of this description the lower left summed area filter and Equation 1 will be used. Thus the convolution process for a single sampling point involves four filter accesses and three additions to extract the sum of the filter within the intersecting subrectangle. However, when the rectangle is large enough to span the full width and height of the filter array, the grayscale pixels corresponding to sampling points in the middle region of the rectangle--inside the rectangle's boundaries and at least f/2 pixels from the boundary--will always be black. This is because the intersecting subrectangle (formed when the filter is centered over the sampling point) is really the whole filter and we need only add the sum of the whole filter, which has been normalized 1.0. Although the cost of generating a summed area filter array is O(f.sup.2), it need be computed only once for each filter array that is needed (i.e., for each filter type and size combination), and can be stored in a file for retrieval when needed. Therefore, for r rectangles which fall within the filter support, the computational expense of rectangular convolution is O(r), or, more exactly, r.times.(4 comparisons+4 array accesses+3 additions) per sample. Another computational cost associated with the use of summed area filter arrays is the cost of determining which of the master rectangles fall within the filter support, when the filter is centered over a selected sampling point S.sub.xy. However, there is no cost involved whatsoever if, instead of looping on the sampling points and convolving the filter at each sample point to determine a grayscale pixel, we loop on the rectangles and add their "gray" contribution to each grayscale pixel affected by the rectangle. In this manner, a particular grayscale character pixel G.sub.ij may be computed in several stages, and when all of the master character rectangles which affect it have been processed, it will have the correct gray value. The basic process for generating a grayscale character from a master character, then, is as follows (see FIG. 4):
______________________________________
generate or access rectangular decomposition of master
(box 40)
generate or access summed area filter arrays
(box 42)
for each rectangle in the master character
(box 44)
determine area in master affected by rectangle
(box 46)
for each sampling point in affected area
(box 48)
determine intersection of filter
(when centered over sampling point)
(box 50)
add to sampling point's grayscale pixel
sum from summed area array (box 52)
______________________________________
In fact, as shown in FIG. 5, there are nine different areas of interest in a master character rectangle 55 which is large enough to span the width and height of the filter. For each of these nine regions, certain portions of the convolution computation shown in Equation 1, above, can be replaced by the use of one or more constant values. In both FIG. 5 and Table 2, these nine regions are labelled as follows: MM (middle), TM (above), BM (below), ML and MR (to either side), and TL, TR, BL, BR (in the corners). Table 2 shows which portions of the convolution computation (Equation 1) for each of these nine regions can be replaced by the use of a constant value, and which need to be performed. The first row of Table 2 shows that all of the computations noted in Equation 1 must be performed in the "generic" case--i.e., for convolving the filter with a sample point at an unknown location in a rectangle, or at any location in a rectangle which is smaller than half the size of the filter. For a rough estimate of the amount of computation saved by using a separate convolution formula for each of the nine rectangle regions, using the constant values noted in Table 2, consider the amount of computations which would be required for computing nine grayscale pixels--one in each of the nine regions.
TABLE 2
______________________________________
Size of Intersection
Filter Access
Region
Region 1 r b t tr -br -tl +bl
______________________________________
Gen- (w+f)(h+f) .sqroot.
.sqroot.
.sqroot.
.sqroot.
.sqroot.
.sqroot.
.sqroot.
.sqroot.
eric
BL f.sup.2 .sqroot.
f .sqroot.
f 1.0 .sqroot.
.sqroot.
.sqroot.
BM f(w-f) 0 f .sqroot.
f 1.0 .sqroot.
BR f.sup.2 0 .sqroot.
.sqroot.
f .sqroot.
.sqroot.
ML f(h-f) .sqroot.
f 0 f 1.0 .sqroot.
MM (w-f)(h-f) 0 f 0 f 1.0
MR f(h-f) 0 .sqroot.
0 f .sqroot.
TL f.sup.2 .sqroot.
f 0 .sqroot.
.sqroot. .sqroot.
TM f(w-f) 0 f 0 .sqroot.
.sqroot.
TR f.sup.2 0 .sqroot.
0 .sqroot.
.sqroot.
______________________________________
This Table shows the intersection calculations and summed area filter
accesses (as well as additions) needed for a single sampling point for a
generic rectangle (width .times. height) and for nine regions of interest
(BottomLeft, BottomMiddle, etc.), when the rectangle is larger than the
filter and only one summed area filter is used (with each entry
representing the sum of the lowerleft rectangle). A .sqroot. indicates
that the computation specified in that column must be performed. 0, f, an
1.0 are constant values which need not be computed. Empty entries mean no
work need be done. See text for further optimization when four summed
filters are computed.
When using Equation 1 without the benefit of the constants noted in Table 2, generating these nine grayscale pixels requires 36 index computations, 36 summed area filter array accesses, and 27 additions. Using the shortcuts and constants noted in Table 2, the same pixels are generated using only twelve index computations, twelve summed area filter array accesses, and seven additions suffice. Thus, the number of computations in this example is reduced by approximately a factor of three. The above analysis actually underestimates the benefits of the method of using Table 2 because it assumes there is a uniform distribution of sampling points within the nine rectangle regions. However, in many situations, rectangular decomposition of master fonts will result in a distribution of sample points in which the number of sample points in the central region (MM) is much greater than one ninth of the total number of sample points. Since sample points in the central region (corresponding to black pixels) require no computation at all, the efficiency of this method is typically even greater than a factor of three. Although the numbers of intersection calculations in each of the four corner regions (two) and four non-corner, non-central regions (one) are uniform, note that the order of summation used in producing a single summed area filter introduces a bias (in the direction of summation) regarding the extraction of the sum. One consequence of this can be seen in the top-right region (row TR), where only one table access is needed (and no additions), while the bottom-left region (row BL) requires three table accesses and three additions. Using Four Different Summed Area Filters. We can exploit this bias to our benefit, by precomputing four different summed area filters from the original filter, each one using a different order of summation. As shown in FIG. 3, the four summed area filter arrays 34A-34D represent summation of the lower-left, lower-right, upper-left and upper-right regions of the filter array 32, respectively. Thus each of the four summed area filter arrays 34A-34D corresponds to rectangular subsets of the filter array 32 formed by incremental changes in a corresponding direction in each of the two dimensions of the filter array 32. Note that for radially symmetric filter arrays, all four of the "different" summed area filter arrays will, in fact, contain the same values arranged in different orientations as shown in FIG. 3. Using four summed area filters allows for extracting the summed filter contribution in any of the regions of interest of a large rectangle in only one table access (except, of course, for the central region, which does not require any table accesses) and no additions, simply by using the appropriately biased summed area filter. Now, the computations for nine grayscale pixels, with one in each of the nine regions, requires only twelve intersection comparisons, only eight summed filter table accesses and zero additions. Note that one addition per sampling point is always needed to add to the current intermediate value of the grayscale pixel. It should also be noted that the number of computations can be further reduced by processing the sampling points affected by a rectangle in an order which reduces the number of intersection calculations, and reduces the computations required for selecting the appropriate summed area filter for each sampling point. For instance, one efficient order would be to process all of the sampling points in one region (e.g., region TL) before processing the sampling points in the next region. Smaller Rectangles. When a character is decomposed into rectangles, there will typically be a number of rectangles which are not large enough to span both the width and height of the filter. For those rectangles which only span the width or height of the filter, there are only six different regions of interest. For rectangles which do not span either the width or height of the filter, the different regions of interest are reduced to four. However, the optimizations just discussed still apply: as long as the rectangle crosses any of the boundaries of the filter support, the number of filter accesses and additions can be reduced. Finally, if the rectangle does not cross any filter support boundaries (i.e., a small rectangle inside the filter support), we are back to the general case which requires four intersection computations, four summed area filter table accesses, and three additions per sampling point. The inventor notes that the present invention provides a convenient mechanism for generating characters at different quality levels. In particular, lower quality characters can be generated (e.g., for showing the basic layout of the image or text being generated) by excluding rectangles of less than a certain size from the character generation process. The purpose of providing more than one quality level is to allow the user the flexibility of generating lower quality characters at a faster rate (by using less computations). For instance, the proposed rough cut mechanism could process all rectangles greater than N (e.g., two) pixels in size. If the rectangular decomposition of the characters being used is dominated by relatively large rectangles, the rough cut characters will be of sufficient quality to allow the user to read the generated text and to see its size, positioning and other layout aspects. After revision, the image can be regenerated using higher quality character generation, i.e., using all of the rectangles in the master characters. Thus, the present invention not only greatly reduces the asymptotic cost of computing gray pixels, but--given a "good" rectangular decomposition of the master character--the cost of generating the black pixels of the grayscale character becomes trivial, and the generation of white pixels comes frr free. This meets one of our original goals of reducing the amount of work for non-gray pixels. Cost of Rectangular Convolution The only limitations on filters to be used with the present invention are that each filter must be of finite width of support, and be space-invariant within a single rectangle. Note that it is possible without increased cost to switch filters between rectangles. This allows the implementation of a limited case of space-variant filters. The screen space can be divided into a grid where each cell has its own filter, and the rectangles of the decomposition of the characters are split at the boundaries of the grid cells as they are processed. Within each cell, the appropriate filter is selected by lookup using the cell indices. As mentioned above, the filters have been digitized at the resolution of the font masters, and the summed versions of the filters are computed. Both computations require O(f.sup.2) operations, but this only has to be done once per filter in the initializaton steps. Once generated, the cost of the algorithm is totally independent of the cost of the filter computation. Therefore, there is no penalty for using high quality filters. We already saw that for direct convolution the number of operations to filter an m.times.m master with an f.times.f filter to produce a g.times.g grayscale character is O(g.sup.2 .times.f.sup.2), assuming constant cost for access into the master. The convolution can also be computed using the discrete Fast Fourier Transform, whose cost is O(g.sup.2 +m.sup.2 .times.log m). However, this is an improvement only for large filters and large numbers of samples. Most of the efficient filtering techniques known in the field of computer graphics--in particular to filter textures--are aimed at quite different circumstances. Usually there are only a few images which must be repeatedly filtered--often with space variant filters--and they are all available in advance. In such applications, prefiltering the images is a good strategy. See Crow, F. C., "Summed-Area Tables for Texture Mapping," Computer Graphics, Volume 18, Number 3, July 1984, SIGGRAPH 1984 Proceedings, pp. 207-212; and Williams, L., "Pyramidal Parametrics," Computer Graphics, Volume 17, Number 3, July 1983, SIGGRAPH 1983 Proceedings, pp. 1-11. In the techniques described in these two papers, the cost after prefiltering is O(g.sup.2). However, the storage required is O(m.sup.2) per image, and both the type of allowable filters and the positioning of the filter are limited. Note the connection between the approach taken here and Crow's summed area tables: here the image is constrained to being a box signal (i.e., bi-level rectangles) and is convolved with an arbitrary summed area filter (which is, in general, smaller than the rectangles), while in Crow's system an arbitrary image is convolved with a box filter, and the textures are, in general, larger than the pixels. Although Heckbert generalized the summed area table technique to a class of filters that can be represented by repeated convolutions of box filters, again, the context is quite different. See Heckbert, P. S., "Filtering by Repeated Integration," Computer Graphics, Volume 20, Number 4, August 1986, SIGGRAPH 1986 Proceedings, pp. 315-321. In particular, the large number of character masters and the requirement of sub-pixel positioning makes the use of prefiltered masters quite impractical. In asymptotic terms, the cost of performing rectangular convolution to produce a grayscale character is ##EQU3## where r.sub.i is the number of subrectangles which fall under the filter centered over g.sub.i. In the worst case, r.sub.i =f.sup.2, and the cost for a grayscale character is O(g.sup.2 .times.f.sup.2). However, this would only occur when the decomposition results in rectangles which cover only one master pixel for each of the g.sup.2 sampling positions. In general, the number of rectangles in a decomposition is directly related to the number of reflex vertices in the outline, which, for characters, is usually very small. Therefore, a more useful bound is obtained by looking at the cost per master rectangle, rather than per grayscale pixel. From this point of view, the influence of the size of the filter is only felt because a larger filter increases, for each rectangle, the size of the regions where more operations are needed. In particular, for a w.times.h rectangle and an f.times.f filter, the cost of processing all the sampling points that fall under the support of the rectangle (including adding the gray contribution to the intermediate grayscale pixels) is 4f.sup.2 +2f(w+h) intersections and 2f(MAX(w,f)+MAX(h,f)) table accesses and additions. As the number of operations for each rectangle is O(f.sup.2 +f(w+h)), when the filter is large relative to the rectangle, the cost is proportional to the area of the filter; however, when the filter is small relative to the rectangle, the cost becomes proportional to the perimeter of the rectangle. For alphabetic characters, decomposition will generate O(m) rectangles because rectangular decomposition has an upper bound of run length encoding, which is O(m). Thus the cost of rectangular convolution is proportional only to the linear size of the characters. Restrictions Note that there are a few conditions which must be satisfied in order to exploit rectangular convolution: The filter F has to be computed at the resolution of the master character M. This is not a severe restriction however, since the filter is only computed once, before any convolution takes place, and can be easily computed from an analytical representation at the resolution of the master character (which in itself may have been generated at a specified resolution from an outline description). The grayscale character G must be randomly accessible. Since a grayscale pixel may be contributed to from several rectangles, one must be able to store partial gray sums for each pixel, and randomly access them to add the contribution when processing a rectangle. Given today's main memory capabilities, this poses no limitation at all. Even for a 128.times.128 grayscale character, only 16 Kbyte of memory are needed. Note that this technique does not need storage space proportional to the master character size (unlike previous techniques); therefore, very high resolution masters (e.g., 1024.times.1024) can be used even on relatively small computers. The master character must be bi-level (i.e., black and white). As the summed area table extraction method cannot weight the individual entries, each pixel in the master must be either on or off. However, other than in specialized texture fonts, characters are by nature bi-modal. Rectangular Decomposition The method of the present invention is dependent on the representation of the filter as a rectangular summed area table, and on the decomposition of the character into rectangles. While it is obvious that every bitmap character can be decomposed into either possibly overlapping (covering) or non-overlapping (partitioning) rectangles, we should worry about algorithms to do so, metrics to characterize the goodness of the decomposition for our purpose, and optimality according to these metrics. The most straightforward and immediately available decomposition is into scan segments, which are indeed rectangles, all of height one. These are commonly stored in run length encoded form. From these, the number of rectangles can be reduced by taking into account a replication count, that is, the count of how many times the same scan segment is repeated on successive scan lines without change. This is the representation which was initially used to test the present invention. The goal of any decomposition should be to minimize the "added edge length" of the rectangles generated, i.e., to minimize the total edge length of the rectangles minus the perimeter length of the original character. To prove this, consider a rectangle of dimensions w.times.h. With a filter of size f.times.f, the number of totally black pixels in the central region of interest is (w-f).times.(h-f) or 0 if w.ltoreq.f or h.ltoreq.f. The number of gray pixels to be processed is the total number of pixels to be processed (w+f).times.(h+f) minus the number of black pixels, that is, 2f(w+h). Considering now a decomposition into r rectangles, possibly overlapping, the total number of gray pixels is: ##EQU4## where 2(w.sub.i +h.sub.i) is the perimeter of rectangle i, and the sum in the above expression is the sum of the perimeters of all the rectangles. This sum can be divided into three terms: the initial perimeter p of the master character, which is independent of the decomposition, the sum of the lengths of the internal overlapping edges l.sub.o, and the sum of the lengths of the internal abutting edges l.sub.a, which counts double since these parts of edges are processed twice in the algorithm (once each for the two abutting rectangles). So the total number of gray pixels is: ##EQU5## Since f and p are constant, one has to minimize l.sub.o +2l.sub.a, which is the added edge length. Note that minimizing the added edge length of the rectangles is equivalent to minimizing the total edge length of the rectangles. Overlapping rectangles cannot be eliminated on the basis of non-optimality as far as added edge length is concerned. FIG. 6 shows an example where the decomposition into two overlapping squares leads to fewer intermediate gray pixels than any partition into three rectangles. Overlapping rectangles, however, will not be considered, because they cannot be processed independently of each other. Doing so would cause the pixels within the overlap to be given an incorrect weight by being found under the filter too many times (i.e., the number of times the pixel is covered by a rectangle). Therefore, we will consider only non-overlapping rectangles. Unfortunately, like many similar optimization algorithms, the general problem of decomposing a rectilinear polygon into rectangles such that the total perimeter is minimal is "NP-hard", i.e., belongs to a class of problems that take an unmanageable amount of time even for relatively small input sizes. If a polygon is without holes, the problem is solvable in polynomial time (O(n.sup.4)) for n corners, but, of course, many characters do have holes. See Lingas, A., R. Pinter, R. Rivest, and A. Shamir, "Minimum Edge Length Decompositions of Rectilinear Figures," Proceedings of the 12th Annual Allerton Conference on Communication, Control, and Computing, Ill., 1982. Lingas presents various heuristics for finding a rectangular decomposition within some constant factor of the minimum edge length when there are holes. See Lingas, A., "Heuristics for Minimum Edge Length Rectangular Partitions of Rectilinear Figures," in Theoretical Computer Science, Edited by A. B. Cremers and H. P. Kriegel, Springer-Verlag, Berlin, January 1983, pp. 199-219. The Lingas heuristics are theoretically interesting, but, for the relatively small number of holes involved in our application, the best approach seems to be to eliminate the holes by adding approximately minimum-length edges from the holes to the boundaries. This can be done in O(n.sup.2) time and gives a solution within a factor of two of the minimum length for this step. See Kou, L., G. Markowski and L. Berman, "A Fast Algorithm for Steiner Trees," Acta Informatica, Volume 15, 1981. Once the holes have been eliminated, the Lingas minimum edge length algorithm for rectilinear polygons with no holes can be run. An alternative way to deal with holes would be to decompose them into "negative contribution rectangles", that is, their gray value is subtracted from--rather than added to--the intermediate results. Although this will produce equivalent results, it must allow for intermediate values which could either overflow the maximum (1.0) or underflow the minimum (0.0), which may be impractical. It should be stressed that rectangular decomposition has only to be done once per master, and therefore the cost of this preprocessing is not an issue of efficiently generating grayscale characters. Exemplary Implementation In order to explore the quality of various filters in generating grayscale characters, the inventor implemented a subset of the rectangular convolution technique on a Motorola 68020 class machine (an HP 9000-320). Thus, as shown in FIG. 7, the computer used included a central processing unit 60 incorporating a Motorola 68020, a display 62, a printer 64, and memory 66. The memory 66, including both random access memory and disk storage, stored the master character data structures (i.e., rectangle decompositions of the master characters), a summed area filter, and grayscale character generation software. Grayscale characters are formed in an image buffer in the memory 66 before transmission to the display 62 or printer 64. In the exemplary implementation, the optimizations discussed above (concerning the reduced intersection calculations for the various regions of interest of a rectangle) were not used. Also only a single summed area filter array was used, in accordance with Equation 1, discussed above. 32-bit fixed-point integer representations of the filter entries were used, where the sum of all the filter entries was normalized to 1.0, and the grayscale pixels were computed in the range of 0 to 255 (where 255 was used to represent black pixels) using one byte to store each grayscale pixel. As mentioned above, the rectangular decomposition used was the repeating run length encoding method, which does not generate optimal rectangles for the rectangular convolution process, but does a fairly good job on the Swiss 721 Bold font. The Master font size was 256.times.256. Since the rectangular decomposition used was not optimal, the timings listed in Tables 3 through 6 should be considered for the relative improvement of rectangular convolution over direct convolution rather than as absolute benchmarks for generating grayscale fonts. Production (optimized) software should achieve at least another order of magnitude speedup over the two orders of magnitude already achieved in the exemplary implementation. Conservatively, this would result in a production rate on the order of 100-1000 characters per second for the filter/character size combinations listed in the Tables. The timings reported are the average of 52 convolution operations (once for each of the upper and lower case characters), do not include rectangular decomposition or display time, and were obtained with the UNIX profiling utility "prof" at a 20 millisecond resolution. (UNIX is a registered trademark of AT&T Bell Laboratories.) The timings reported in Tables 3 through 6 demonstrate that the rectangular convolution technique used in the present invention is effective, leading to a considerable speedup in the computation of grayscale fonts, without compromising the characteristics of the filters that can be used. This technique can be employed for realtime display of grayscale characters on systems with the computing power of a personal workstation. Several improvements described in this paper, but not included in the exemplary implementation used to generate the timings shown in Tables 3 through 6--such as optimal rectangular decomposition and the use of four summed area filters--would further reduce the cost of filtering.
TABLE 3
______________________________________
Single Phase Timings (in milliseconds)
Swiss 721 Bold
Grayscale Filter Convolution Time
Size Overlap Size Rectangular
Direct
______________________________________
16 1.0 16 46 930
32 1.0 8 69 1010
64 1.0 4 139 1340
16 1.25 20 49 1310
32 1.25 10 78 1520
64 1.25 5 153 1860
16 1.5 24 55 2040
32 1.5 12 87 2120
64 1.5 6 168 2510
______________________________________
Note that filtering inherently takes care of mismatched aspect ratios, whether they arise from the master character, grayscale character, or display device pixel shape. Furthermore, as in previous methods, the grayscale pixel value can be used as a weight for interpolating between colored text and a variegated background. Another aspect of the present invention is that the rectangles generated by the decomposition do not have to be stored in any particular data structure and can be processed independently of each other and in any order. This indicates that the present invention can be implemented with a straightforward implementation on multiprocessor systems, whether general purpose or specialized for this particular task. As mentioned earlier, precomputing all of the phases of all the characters needed is quite out of the question. With the technique of the present invention, many applications will be able to justify the cost of dynamically computing grayscale characters, and not have to rely on a small selection of poor quality fonts. Extensions and Applications One additional improvement in speed can easily be achieved by determining, for a given filter support, the pixels that will always be black, and separating them from the rest of the character, so that they are not included in the processing of the rectangles. Since these pixels are already processed very efficiently, this would result in only a modest improvement. In many applications there is a demand for rotated text. Bitmaps can of course be rotated, and there are clever algorithms to do so. See Guibas, L. J. and J. Stolfi, "A Language for Bitmap Manipulation", ACM Transaction on Graphics, Volume 1, Number 3, July 1982, pp. 191-214. The present invention, as described herein, is not well adapted to the use of rotated master characters, because the rectangular decomposition would have to be recomputed for every new rotated master. The best way to apply the present invention to generate rotated text is to rotate the sampling grid and apply it to the unrotated master. This rotation has to be done only for one point; the other grid points can be computed by incremental techniques. While the rectangular decomposition of the master is still valid, the filter and its summed area representation would have to be rotated, but this has to be done only once per rotation angle. In fact, for radially symmetric filters this does not even have to be done. The main loss in efficiency is in the computation of the intersection between the filter and the rectangles. For each rectangle, one has to find the sample point closest to one of its corners and then move along the grid points using some form of incremental technique. Each move would, in general, be in both the X and Y directions, and therefore also a little more costly than in the original case. Lastly, one can also put to good use the flexibility allowed in the choice of the filter. For instance, it may be useful to use different filters for different parts of a character (for example, to emphasize the serifs, or treat leading and trailing edges differently). To this end, one can mark the rectangles of the decomposition based on the parts of the character to which they belong (e.g., vertical stem, diagonal hairline) and use a filter appropriate to that type of shape when displayed on a particular device. It may also be useful to use different filters for different portions of a display. While the present invention has been described with reference to a few specific embodiments, the description is illustrative of the invention and is not to be construed as limiting the invention. Various modifications may occur to those skilled in the art without departing from the true spirit and scope of the invention as defined by the appended claims.
|
Same subclass Same class Consider this |
||||||||||