METHOD AND SYSTEM FOR MEASURING TEXT-RENDERING

QUALITY

TECHNICAL FIELD The present invention is related to assessing the quality of text rendered by character-rendering devices and, in particular, to methods that can be incorporated into partially or fully automated systems for measuring the quality of text output by text-rendering devices.

BACKGROUND OF THE INVENTION

Designers and manufacturers of printing devices need to be able to evaluate the quality of text and graphics printed by the printing devices. In the past, designers and manufacturers of printing devices have relied on visual assessment of the quality of printed text and graphics as well as on a number of standard measurements of printed-text quality. However, visual-inspection-based assessment of printing quality may be quite subjective, and, when a large number of printing- quality assessments need to be made, can be tedious, expensive, error prone, and exhibit high variation. Unfortunately, many of the standard metrics currently applied to evaluate the quality of printing do not closely correspond to human assessment of print quality based on visual inspection of printed materials, and may often be quite scale dependent, as well as dependent on the particular text and graphics used for assessing printing quality, background colors and shades on which the text and graphics are printed, and other such parameters and characteristics. For this reason, developers and manufacturers of printing devices and other character-rendering devices, including display devices, as well as vendors, retailers, and, ultimately, users of printing devices and other text-rendering devices may all have need for deterministic, reliable, and automatable character-rendering-quality measurement methods that are relatively independent of scale of the rendered text and graphics, background colors and shades, and other such parameters and characteristics.

SUMMARY OF THE INVENTION

Method embodiments of the present invention provide for semi- automated or fully automated assessment of the quality of device-rendered text, including graphical symbols, characters, and other printable and displayable patterns. Method embodiments of the present invention employ one or more metrics that involve the comparison of input characters, including text characters, symbols, and character-like graphics, with corresponding digital output characters obtained by capturing images of characters rendered by a character-rendering device. The one or more metrics include individual computed relative entropy APQ, metrics, reflective of differences in character-to-character distance distributions between one input character c, and the set of input characters c*, a cumulative computed relative entropy APQ, stroke irregularity, contrast measure, sharpness, and background uniformity. These individual metrics can be computed and stored separately as well as output to a user of a character-rendering-quality measurement system, or may be combined together in various ways to produce one or more comprehensive, cumulative metrics for storage and output.

BRIEF DESCRIPTION OF THE DRAWINGS Figures 1 and 2 illustrate an overall methodology employed in various method embodiments of the present invention.

Figures 3A-C illustrate an input character, a corresponding output character, and various measurements that may be used to compute a distance metric for the input character/output character pair. Figure 4 illustrates a general approach to character dilation and/or character erosion.

Figures 5A-B illustrate erosion and dilation operations, respectively. Figures 6A-B show an eroded character "a" and a dilated character "a" corresponding to printed character "a" shown in Figure 3B. Figures 7A-B show two different distance distributions for a particular character c,.

Figures 8A-C illustrate computation of the distance-distribution-based metric /SJ ³ Q for a small, exemplary character set.

Figures 9A-C use identical illustration conventions as used in Figures 8A-C to show computation of the distance-distribution-based metric APQ for a set of output characters that differ from a set of input characters.

Figures 10A-B shows four versions of a particular character employed in outline metrics and superposition of a rendered character with a dilated-character outline and with an eroded-character outline.

Figure 11 is a control-flow diagram that illustrates one method embodiment of the present invention.

DETAILED DESCRIPTION OF THE INVENTION

Method and system embodiments of the present invention are directed to a determination of rendered-text quality to enable assessment of the quality and/or functional state of character-rendering devices, including various types of electromechanical text-rendering and text-display devices. Method embodiments of the present invention may be semi-automated, with certain steps carried out computationally and other steps carried out manually, or may alternatively be incorporated into a fully automated system. Method embodiments of the present invention produce useful and tangible results that may be stored in various computer- readable media, output to a user, or employed as input to various types of quality- control systems, design systems, and monitoring systems.

Figures 1 and 2 illustrate an overall methodology employed in various method embodiments of the present invention. A test pattern of characters is first devised in order to measure printed-text quality. In Figure 1, the test pattern 102 is a very short sequence of eight lower-case characters. In a practical system, the test pattern may include many hundreds of different characters, each character or sequence of characters repeated at different sizes and in different positions within the test pattern. The set of test characters is input to a printing device 104 for printing onto a sheet of paper 106 or rendering on some other medium. In alternative embodiments of the present invention, the test characters may be input to other types

of character-rendering devices and media, including text-display devices, electronic paper, and other chemical/mechanical/electronic character-rendering devices and media. Printing devices are described, below, as a familiar and important example of character-rendering devices, but are, in no way, intended to limit the scope of the current invention. The test characters are generally converted to digital, pixel-based maps or templates prior to printing. These digital maps or templates can be electronically intercepted to serve as digital input characters. In other words, for the purposes of discussing the present invention, the phrases "input character" and "digital input character" refers to a digital, pixel-based map of a character that is used, internally, by a character-rendering device to render a test-pattern character, either by displaying characters or by imparting character images to a sheet of paper, another such printable medium, a display medium, and other character-image display or receiving devices and/or media. In the currently described embodiment, the printed characters are then scanned, by a scanning device 106, to produce digital output characters 108 corresponding to the input characters. In alternative embodiments, images of rendered characters may be captured by photography or by any of various other ways to capture the images of rendered characters. Next, as shown in Figure 2, the output characters 108 are computationally aligned and registered with the input characters 1 10 so that the digital map that constitutes each input character c, can be matched with a corresponding digital output character map c, to facilitate computation of a variety of different quality metrics. Once the input characters are aligned and registered with the output characters, quality metrics are computed 1 12 and stored in various types of computer-readable medium and/or output to a user.

A variety of different primitive metrics are employed in computing the quality metrics that represent embodiments of the present invention. The first primitive metric is a distance metric that measures the distance between, or similarity/dissimilarity of, an input character c, and corresponding output character c, .

Figures 3A-C illustrate an input character, a corresponding output character, and various measurements that may be used to compute a distance metric for the input character/output character pair. In Figure 3A, an exemplary input character "a" is shown as a pixel-based template. The input character 302 is a pattern of relatively

dark, or low, pixel-intensity values within a rectangular pixel grid 304 that includes relatively light, or high, background pixels. In many cases, the non-character pixels, or background pixels, have higher intensities than the input-character pixels, as is the case for familiar black-character-on-white-background printing or display. In other cases, the input-character pixels may have higher intensities than the background pixels. In general, pixel-intensity values are expressed as integer values selected from a range of grayscale values, often the range [0,255]. However, the methods of the present invention can also be employed to measure the quality of color printing or color rendering, with scanned or otherwise captured digital output characters encoded as three integer values associated with each pixel. Colored-text encodings can be transformed to monochrome encodings in which each pixel is associated with a single integer intensity value. Alternatively, each different color-encoding value associated with a pixel may be separately analyzed, by methods of the present invention, only a single color-related value among the three color-related values associated with pixels may be analyzed, or the color-related values associated with each pixel may be mathematically combined to produce a single, composite value. For the purposes of the present invention, single-valued pixels are assumed, either directly obtained by monochrome scanning or computationally obtained from colored-text encodings.

Figure 3B shows the digital encoding of an output character responding to the input character shown in Figure 3 A. In this case, the quality of the character-rendering device that rendered the output character appears to be relatively low, with several regions 306-307 in the output character having high intensity values, while corresponding regions of the input character have low intensity values, and with a number of pixels 308-310 in the output character having low intensity values, while corresponding pixels in the input character template have high intensity values. Figure 3C illustrates a superposition of the input character, shown in Figure 3A, and the output character shown in Figure 3B. In Figure 3C, a downward-slanted crosshatching 320 is used to indicate those pixels with low intensities in the output character, but high intensities in the input character, an upward-sloped crosshatching 322 is used to indicate pixels with low intensities in the input character but high intensities in the output character, and a double-cross hatching 324 that indicates

pixels with low intensities both in the input character and the output character. Pixels without crosshatching in Figure 3C have high intensities both in the output character and in the input character. Again, a low intensity pixel appears to be dark, and a high-intensity pixel appears to be white or light. Figure 3C shows, in addition to the superposition 316 of the output character and input character, counts of the various types of character pixels. These counts include (1) 10, the number of pixels with low intensities in the output character and high intensities in the input character; (2) 00, the number of pixels with low intensities in the input character and high intensities in the output character; (3) B, the number of pixels with low intensities in both the input character and output character; and (4) T, the total number of pixels with low intensities in either or both of the output character and input character. Armed with these values, any of a variety of different distance metrics can be computed and subsequently used to compute the quality metrics that represent embodiments of the present invention. A distance between two characters reflects the similarity/dissimilarity of the two characters, with a smaller distances corresponding to greater similarity and larger distances corresponding to greater dissimilarity. A few exemplary distance metrics are provided below: d _{{mpul,ouφul)} ^{= I} O+ OO

IO ² + OO ² d (.input , output) rp

10 + 00 d [input , output) ji d, (input .output ,) = IO ² + O ²

Two operations that are employed to compute the quality metrics that represent embodiments of the present invention include character dilation and character erosion. These two operations are similar, and both involve a conceptual application of a kernel, or small neighborhood, to each intensity value within the pixel-based representation of an input character or output character. Figure 4 illustrates a general approach to character dilation and/or character erosion. As shown in Figure 4, a kernel 402 is superimposed over each pixel in a pixel-based map

404 of a character. In Figure 4, the kernel 402 is a 3 x 3 matrix. The center of the kernel 406 is overlaid on a pixel in the pixel-based character map 404 to compute a

replacement value for the pixel value of the pixel in the pixel-based character map that is then entered into a result character map (not shown in Figure 4). Thus, as shown by the curved line 406 in Figure 4, the kernel is successively superimposed over each of a series of successive pixel values within the character map in order to generate either a dilated character map or an eroded character map. The kernel cannot be fully superimposed over border pixels, such as pixel 410. In such cases, either a truncated kernel may be used, or, since the border regions generally are high-intensity pixels, they can simply be omitted from the computation of a dilated character map or eroded-character map. Figures 5A-B illustrate erosion and dilation operations, respectively.

In Figure 5 A, the kernel 502 is positioned over pixel 504 of the original image 506 to create a neighborhood of pixel values about pixel 504. The pixel-intensity values of the original image within the neighborhood are then considered to determine a pixel value 508 of the eroded-character map corresponding to the considered pixel 504 in the original character map. As one example, for a monochrome, binary map in which pixel values are either "0" or "1," with "0" indicating low intensity and "1 " indicating high intensity, when the number of 0-valued neighborhood pixel values is greater than or equal to a threshold value, then the resulting pixel value for the eroded image 508 corresponding to the central pixel 504 of the original character map is set to "0." In certain embodiments, the threshold may be "1," so that if even a single "0" value is observed in the neighborhood of the considered pixel 504, then the corresponding value for that pixel in the eroded character map is "0." Dilation, shown in Figure 5B, is essentially opposite to erosion. In the case of dilation, when the number of low- intensity pixel values within the superposition neighborhood of the considered pixel 504 of the original character map are equal to, or exceed a threshold value, then the corresponding pixel value 512 is also low. In certain embodiments, in which pixel values are either "0" or "1," when even a single neighborhood pixel in the superposition of the kernel with the original character map has the value "1," then the corresponding value 512 of the currently considered pixel 54 is "1." Figures 6A-B show an eroded character "a" and a dilated character "a" corresponding to rendered character "a" shown in Figure 3B. In this case, the original character map and the

eroded and dilated character maps are binary, with "0" indicating background and "1 " indicating a character pixel, with the erosion threshold equal to "1," and with the dilation threshold equal to "1." Various alternative types of erosion and dilation may be employed, including use of different thresholds, or multiplication of kernel values with corresponding original-character-map values and summing of the products as a basis for computation of a composite value from which to determine a resultant- character-map value corresponding to a currently considered pixel in an original image.

In order to avoid complexities and non-uniformities in quality-metric computation arising from different background shades and different contrasts in scanned output character maps, the scanned output character maps may be tone mapped as a first step in the methods that represent embodiments of the present invention. Tone mapping essentially maps pixel values within a first range of pixel values to corresponding pixel values in a second range of pixel values. For example, a low-contrast output character map may have intensity values ranging from 100 to 150. Tone mapping can be used to map the low-contrast range to the range [0,255]. Alternatively, binary images, with only the pixel values "0" and "1," are convenient for various image-processing tasks, and an output-character map can be transformed from pixel values in the grayscale range [0,255] to [0,1], with high-intensity pixels above a threshold value represented by "0" and low-intensity pixels below or equal to the threshold represented by "1," in essence inverting the magnitudes as well as truncating the range of values. In many method embodiments of the present invention, output-character maps are initially tone mapped to a particular range of pixel-intensity values to facilitate computation of various intermediate results and, finally, the quality metrics that represent embodiments of the present invention. Pixels are generally characterized as background-intensity pixels and foreground- intensity or character-intensity pixels. In some cases, binary images may be most useful, and, in others, grayscale ranges are most useful.

As a second step, the output-character test pattern needs to be aligned, oriented, and registered with the input-character test pattern. There are a variety of approaches to accomplish this task. In many approaches, the positions and

orientations of the output-character test pattern with respect to the input-character test pattern can be varied over ranges of positions, orientations, and scales in order to find an orientation, position, and scale that produce the smallest overall distance between the output-character test pattern and the input-character test pattern. Then, individual output characters corresponding to individual input characters can be located by translation of the input-character map to a region of the output-character test pattern that provides a best correspondence, as measured by distance between the input character and proposed corresponding output character. In certain embodiments, the orientation and/or scale may be computable, based on known character-rendering- device characteristics.

Armed with the primitive metrics, discussed above, erosion and dilation operations, and a tone mapped and registered set of output characters corresponding to the input characters, the rendered-character-quality metrics that represent embodiments of the present invention can be computed by methods of the present invention. A first metric, referred to as APQ, is computed as a relative entropy from character-to-character distributions. Figures 7A-B show two different distance distributions for a particular character c,. The first distribution 702 is a distribution of computed differences between the input character c, and all input characters in a test pattern c*. As can be seen in Figure 7A, the input character c, is identical to itself, so that a first position in the histogram has a column of height "0" 704, and varies from other, dissimilar characters by a variety of different distances. For example, the most similar character to character c, is at a distance of "50" 706 and the most dissimilar character to character c, is at a distance of about "200" 708 from character c,. Figure 7B shows a distribution of the distances between rendered character c, and all of the input characters c _k . When the rendered character c, is not rendered exactly according to the input character c,, then the rendered character C ₁ is at a distance from the input character c,, represented by the first column in the histogram 710. Note that the distributions of distances between the rendered character c, and the remaining input characters c _k has changed with respect to the distribution of distances between the input character c, and input-character-set c*. The

APQ metric, that represents one embodiment of the present invention, seeks to quantify the difference in distributions of each input character/output character pair with respect to the set of input characters. First, the probability that input character c, is the same character as input character c* can be computed as: n _ A -distance(input, .input, ) wherein distance(input,, input*) is the distance between input character c, and input character c*; and A is a constant.

Similarly, the probability that output character c, is equal to input character c* is computed as: β — D ₀ -distance(output, , input, ) ik - ^Dβ wherein distance(output,, input*) is the distance between output character c, and input character c*; and B is a constant.

A character-to-character-distance-distribution difference for the input character/output character pair CjIc ₁ can then be computed as a relative entropy: Finally, a cumulative distance-distribution-based metric APQ can be computed as the average of the APQ ₁ metrics over the input character set, as follows:

∑δfβ APQ = -

* N wherein N is the number of characters in the input-character set.

Figures 8A-C illustrate computation of the distance-distribution-based metric APQ for a small, exemplary character set. Figure 8A shows five simple input characters 801-805 and five corresponding output characters 81 1-815. In this case, the character-rendering device is 100% accurate, so that the output characters exactly

match the input characters. Next, as shown in Figure 8B, a table of distances between each input/output character pair and all of the remaining input characters is computed, using the distance metric:

(IO ² + OO ² ) d _ιk = ± L

The top figure in each cell is the distance between the input character with index equal to the row index of the cell and the input character with index equal to the column of the cell. The lower figure in each cell is the distance between the output character with index equal to the row index of the cell and the input character with index equal to the column index of the cell. Because the input characters and output characters are identical, the distance between each input character c, and another input character C _k and between the output character c, and the other input character c* are equal, in the table shown in Figure 8B. Figure 8C shows the probabilities P, _k and Q, _k computed for each character pair of the character set shown in Figure 8A, using the conversion formulas, discussed above, for converting distances to probabilities. Finally, at the bottom of Figure 8C, calculation of the distance-distribution-based metric APQ is shown. Because the expression for APQ, includes the term

log L in any case where P, _k is equal to Q, _k , the kf ^h term of APQ, is "0," since

Iog ₂ (l) is equal to "0." Because all of the P, _k are equal to Q, _k in the example shown in Figure 8A, all the terms are "0," and the final APQ metric has the value "0." Thus, when the output character is exactly equal to the input character set, APQ has the value "0."

Figures 9A-C use identical illustration conventions as used in Figures 8A-C to show computation of the distance-distribution-based metric APQ for a set of output characters that differ from a set of input characters. In this case, APQ is computed to have the value of "0" 4364. Thus, as the differences between the input characters and output characters increase, the magnitude of the metric APQ also generally increases. Thus, APQ is a sealer value that takes into account the differences in pairs of distance distributions between each input-character/output- character pair and all of the input characters in the input-character set. The magnitude

of APQ is inversely proportional to character-rendering quality. Of course, the range of magnitudes of computed APQ values depends on the constants chosen for the distance-to-probability conversions and the particular distance metrics employed.

Additional useful metrics that represent embodiments of the present invention employ superpositions of eroded and dilated input characters and corresponding output characters, and are referred to as "outline metrics." Figures 10A-B shows four versions of a particular character employed in outline metrics and superposition of a rendered character with a dilated-character outline and with an eroded-character outline. Figure 1OA shows the four versions of a particular character employed in the outline metrics. Figure 1OA shows the outline of input character "a" shown in Figure 3A 1002, the outline of input character "a" following erosion 1004, the outline of input character "a" following dilation 1006, and the outline of the output character "a" corresponding to the input character "a" 1008. As shown in Figure 1OB, the output character can be superimposed with the dilated input character 1010 and can be superimposed with the eroded input character 1012. These two superpositions form the basis of the additional outline metrics. The input character, dilated input character, eroded input character, and output character can each be viewed as sets of character-intensity pixels, allowing various subsets of the input and output characters can be obtained by familiar set operations, such as union, intersection, and set subtraction. In general, the union of two characters is the pixel locations of pixels in either one or both characters. These outline metrics are next discussed using the following notation for the particular input character, the dilated input character, the eroded input character, the output character, and three functions num, sum, and std on sets of pixels:

c, = an input character of the input-character set with index /, considered as the set of pixels with character-intensity values within the pixel- based map of c,

C ₁ = dilation (c,) ε, - erosion (c,)

C ₁ = output character corresponding to C ₁ , considered as the set of pixels with character-intensity values within the pixel-based map of c, num(a) = the number of pixels in the set of character-intensity pixels that represent character "a" sum(a) = the sum of the pixel-intensity values of the pixels in the set of character-intensity pixels that represent character "a" std{&) = the standard deviation of the pixel-intensity values of the pixels in the set of character-intensity pixels that represent character "a"

Four metrics for the particular character index i of the character set have been found to particularly useful for character-rendering-quality assessment, although many additional outline metrics may find utility. A stroke irregularity metric can be computed for input character c, as:

, . num (c -cλ strokejrregulaπty, = , _\ num (c, ) Stroke irregularity is a ratio of the number of character-intensity pixels of the output character outside the border of the dilated input character superimposed on the output character divided by the number of character-intensity pixels within the input character.

A contrast measure metric can be computed for input character c, as: sum(c, in (c, Dc ₁ )) sum (c, in (c, -C ₁ )) contrast_measure, = ,_ ' _A í ^v ' num [C ₁ C[C ₁ ) num [C ₁ -C ₁ )

Contrast measure is the mean value of pixels within the output character that are also within the boundary of the eroded input character superimposed over the output character divided by the mean value of the pixels of the output character outside the boundary of the dilated input character superimposed over the output character. A sharpness metric can be computed for input character c, as: sum(c, in (ς He,)) sum(c, in((c, Oc ₁ ) -C ₁ )) sharpness, = ^v ,_ ^v '' í _// - _n - _\ - _\ num (c, Dc,) num((c ₍ rk,)-c,)

Sharpness is the mean value of pixels of the output character within the eroded- character boundary superimposed over the output character divided by the mean value of the pixels of the output character between the eroded-character boundary and dilated-input-character boundary, both superimposed over the output character. Finally, a background-uniformity metric can be computed for input character c, as: background_uniformity, = s/d(c in(c, -S ₁ ))

Background uniformity is the standard deviation of the pixel values of the output character outside of the dilated-input-character boundary superimposed over the output character.

For each of the four above-described metrics, a cumulative metric can be computed for the metrics computed for each of N character of the character set by: metric. metric = —

N

Additionally, the individual outline metrics can be combined to produce a composite outline metric.

A large variety of different composite metrics may be computed from the above-described metrics and the cumulative metric APQ. In certain embodiments of the present invention, various cumulative metrics are computed. In other embodiments of the present invention, the individual metrics APQ ₁ , stroke irregularity,, contrast measure,, sharpness,, and background jmiformity, metrics are stored and output to a user. In all cases, these metrics may be used to assign an overall quality to rendered text characters and other graphics analyzed by method embodiments of the present invention. Methods of the present invention may be incorporated into any of a number of different types of systems, including rendered-character-quality-measuring systems and in printing devices and other character-rendering devices with self-monitoring subsystems.

Figure 11 is a control-flow diagram that illustrates one method embodiment of the present invention. In step 1 102, the identity and characteristics of the character-rendering to be tested are received. In step 1 104, a suitable set of test

characters is devised. Then, in step 1 106, the test characters are transmitted to the identified character-rendering device for rendering, with the input character maps used by the character-rendering device intercepted as input characters. Then, in step 1 108, images of the characters rendered by the character-rendering device are captured and digitally encoded in order to generate a set of output characters. In step 11 10, the output characters are tone mapped and are then, , in step 1 1 12, registered with the input characters. Various input-character/output-character difference metrics are computed, in step 1 1 14, as discussed above. These metrics may include one or more of APQ ₁ S and APQ, stroke irregularity, contrast measure, sharpness, background uniformity, and various cumulative and collective metrics based on these. Finally, the computed metrics are output to a user or device, in step 11 16.

Although the present invention has been described in terms of particular embodiments, it is not intended that the invention be limited to these embodiments. Modifications within the spirit of the invention will be apparent to those skilled in the art. For example, method embodiments of the present invention may be implemented in many different ways, depending on selection of various computational parameters, including modular organization, control structures, data structures, programming languages, and program-execution environments, including operating-system platforms. Method embodiments of the present invention can be used to evaluate the quality of text and graphics printed by any of the many different kinds of printing devices. In addition, method embodiments of the present invention can be used to evaluate the quality of text rendered for display, printing, communication to remote devices, and otherwise rendered for use and perception by humans and by automated systems. While, in the disclosed embodiment, printed text is scanned to generate digitally encoded output characters, any number of different image-capture methods and devices can be used to obtain digitally-encoded output characters, including photography using film or digital cameras, intercepting electronic signals, and by other such methods and devices. As discussed above, many variations of the methods of the present invention are possible, including alternative computation of different types of distances, distance-based probabilities, distance- distribution-difference based metrics, and other metrics. The method embodiments of

the present invention may be incorporated into any number of different types of printing devices and printing-quality-measuring devices and systems.

The foregoing description, for purposes of explanation, used specific nomenclature to provide a thorough understanding of the invention. However, it will be apparent to one skilled in the art that the specific details are not required in order to practice the invention. The foregoing descriptions of specific embodiments of the present invention are presented for purpose of illustration and description. They are not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations are possible in view of the above teachings. The embodiments are shown and described in order to best explain the principles of the invention and its practical applications, to thereby enable others skilled in the art to best utilize the invention and various embodiments with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalents: