Abstract:
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 or 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 APQi 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.

Description:
TECHNICAL FIELD 
       [0001]    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 
       [0002]    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 
       [0003]    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 ΔPQ i  metrics, reflective of differences in character-to-character distance distributions between one input character c i  and the set of input characters c k , a cumulative computed relative entropy ΔPQ, 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 
         [0004]      FIGS. 1 and 2  illustrate an overall methodology employed in various method embodiments of the present invention. 
           [0005]      FIGS. 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. 
           [0006]      FIG. 4  illustrates a general approach to character dilation and/or character erosion. 
           [0007]      FIGS. 5A-B  illustrate erosion and dilation operations, respectively. 
           [0008]      FIGS. 6A-B  show an eroded character “a” and a dilated character “a” corresponding to printed character “a” shown in  FIG. 3B . 
           [0009]      FIGS. 7A-B  show two different distance distributions for a particular character c i . 
           [0010]      FIGS. 8A-C  illustrate computation of the distance-distribution-based metric ΔPQ for a small, exemplary character set. 
           [0011]      FIGS. 9A-C  use identical illustration conventions as used in  FIGS. 8A-C  to show computation of the distance-distribution-based metric ΔPQ for a set of output characters that differ from a set of input characters. 
           [0012]      FIGS. 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. 
           [0013]      FIG. 11  is a control-flow diagram that illustrates one method embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0014]    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. 
         [0015]      FIGS. 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  FIG. 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  FIG. 2 , the output characters  108  are computationally aligned and registered with the input characters  110  so that the digital map that constitutes each input character c i  can be matched with a corresponding digital output character map ĉ i  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  112  and stored in various types of computer-readable medium and/or output to a user. 
         [0016]    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 i  and corresponding output character ĉ i .  FIGS. 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  FIG. 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. 
         [0017]      FIG. 3B  shows the digital encoding of an output character responding to the input character shown in  FIG. 3A . 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.  FIG. 3C  illustrates a superposition of the input character, shown in  FIG. 3A , and the output character shown in  FIG. 3B . In  FIG. 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  FIG. 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.  FIG. 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) IO, the number of pixels with low intensities in the output character and high intensities in the input character; (2) OO, 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: 
         [0000]    
       
         
           
             
               d 
               
                 ( 
                 
                   input 
                   , 
                   output 
                 
                 ) 
               
             
             = 
             
               IO 
               + 
               OO 
             
           
         
       
       
         
           
             
               d 
               
                 ( 
                 
                   input 
                   , 
                   output 
                 
                 ) 
               
             
             = 
             
               
                 
                   IO 
                   2 
                 
                 + 
                 
                   OO 
                   2 
                 
               
               T 
             
           
         
       
       
         
           
             
               d 
               
                 ( 
                 
                   input 
                   , 
                   output 
                 
                 ) 
               
             
             = 
             
               
                 IO 
                 + 
                 OO 
               
               T 
             
           
         
       
       
         
           
             
               d 
               
                 ( 
                 
                   input 
                   , 
                   output 
                 
                 ) 
               
             
             = 
             
               
                 IO 
                 2 
               
               + 
               
                 O 
                 2 
               
             
           
         
       
     
         [0018]    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.  FIG. 4  illustrates a general approach to character dilation and/or character erosion. As shown in  FIG. 4 , a kernel  402  is superimposed over each pixel in a pixel-based map  404  of a character. In  FIG. 4 , the kernel  402  is a 3×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  FIG. 4 ). Thus, as shown by the curved line  406  in  FIG. 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. 
         [0019]      FIGS. 5A-B  illustrate erosion and dilation operations, respectively. In  FIG. 5A , 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  FIG. 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.”  FIGS. 6A-B  show an eroded character “a” and a dilated character “a” corresponding to rendered character “a” shown in  FIG. 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. 
         [0020]    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. 
         [0021]    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. 
         [0022]    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. 
         [0023]    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 ΔPQ, is computed as a relative entropy from character-to-character distributions.  FIGS. 7A-B  show two different distance distributions for a particular character c i . The first distribution  702  is a distribution of computed differences between the input character c i  and all input characters in a test pattern c k . As can be seen in  FIG. 7A , the input character c i  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 i  is at a distance of “50”  706  and the most dissimilar character to character c i  is at a distance of about “200”  708  from character c i .  FIG. 7B  shows a distribution of the distances between rendered character ĉ i  and all of the input characters ĉ k . When the rendered character ĉ i  is not rendered exactly according to the input character c i , then the rendered character ĉ i , is at a distance from the input character c i , represented by the first column in the histogram  710 . Note that the distributions of distances between the rendered character  3 , and the remaining input characters  3 , has changed with respect to the distribution of distances between the input character c i  and input-character-set c k . The ΔPQ metric i  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 i  is the same character as input character c k  can be computed as: 
         [0000]    
       
      
       P 
       ik 
       =Ae 
       −distance(input 
       
         i 
       
       ,input 
       
         k 
       
       )  
      
       
         
           
             wherein distance(input i , input k ) is the distance between input character c i  and input character c k ; and
           A is a constant.
 
Similarly, the probability that output character ĉ i  is equal to input character c k  is computed as:
   
         
           
         
       
     
         [0000]    
       
      
       Q 
       ik 
       =Be 
       −distance(output 
       
         i 
       
       ,input 
       
         k 
       
       )  
      
       
         
           
             wherein distance(output i , input k ) is the distance between output character ĉ i  and input character c k ; and
           B is a constant.
 
A character-to-character-distance-distribution difference for the input character/output character pair c i /{tilde over (c)} i  can then be computed as a relative entropy:
   
         
           
         
       
     
         [0000]    
       
         
           
             
               Δ 
                
               
                   
               
                
               
                 PQ 
                 i 
               
             
             = 
             
               
                 ∑ 
                 
                   k 
                   - 
                   1 
                 
                 N 
               
                
               
                 
                   P 
                   ik 
                 
                  
                 
                   ( 
                   
                     
                       log 
                       2 
                     
                      
                     
                       ( 
                       
                         
                           P 
                           ik 
                         
                         
                           Q 
                           ik 
                         
                       
                       ) 
                     
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    Finally, a cumulative distance-distribution-based metric ΔPQ can be computed as the average of the ΔPQ, metrics over the input character set, as follows: 
         [0000]    
       
         
           
             
               Δ 
                
               
                   
               
                
               PQ 
             
             = 
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   N 
                 
                  
                 
                   Δ 
                    
                   
                       
                   
                    
                   
                     PQ 
                     i 
                   
                 
               
               N 
             
           
         
       
     
         [0028]    wherein N is the number of characters in the input-character set. 
         [0029]      FIGS. 8A-C  illustrate computation of the distance-distribution-based metric ΔPQ for a small, exemplary character set.  FIG. 8A  shows five simple input characters  801 - 805  and five corresponding output characters  811 - 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  FIG. 8B , a table of distances between each input/output character pair and all of the remaining input characters is computed, using the distance metric: 
         [0000]    
       
         
           
             
               d 
               ik 
             
             = 
             
               
                 ( 
                 
                   
                     IO 
                     2 
                   
                   + 
                   
                     OO 
                     2 
                   
                 
                 ) 
               
               T 
             
           
         
       
     
         [0030]    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 i  and another input character c k  and between the output character ĉ i , and the other input character c k  are equal, in the table shown in  FIG. 8B .  FIG. 8C  shows the probabilities P ik  and Q ik  computed for each character pair of the character set shown in  FIG. 8A , using the conversion formulas, discussed above, for converting distances to probabilities. Finally, at the bottom of  FIG. 8C , calculation of the distance-distribution-based metric ΔPQ is shown. Because the expression for ΔPQ i  includes the term 
         [0000]    
       
         
           
             
               
                 log 
                 2 
               
                
               
                 ( 
                 
                   
                     P 
                     ik 
                   
                   
                     Q 
                     ik 
                   
                 
                 ) 
               
             
             , 
           
         
       
     
         [0000]    in any case where P ik  is equal to Q ik , the term k th  of ΔPQ i  is “0,” since log 2 (1) is equal to “0.” Because all of the P ik  are equal to Q ik  in the example shown in  FIG. 8A , all the terms are “0,” and the final ΔPQ metric has the value “0.” Thus, when the output character is exactly equal to the input character set, ΔPQ has the value “0.” 
         [0031]      FIGS. 9A-C  use identical illustration conventions as used in  FIGS. 8A-C  to show computation of the distance-distribution-based metric ΔPQ for a set of output characters that differ from a set of input characters. In this case, ΔPQ 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 ΔPQ also generally increases. Thus, ΔPQ is a scaler 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 ΔPQ is inversely proportional to character-rendering quality. Of course, the range of magnitudes of computed ΔPQ values depends on the constants chosen for the distance-to-probability conversions and the particular distance metrics employed. 
         [0032]    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.”  FIGS. 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.  FIG. 10A  shows the four versions of a particular character employed in the outline metrics.  FIG. 10A  shows the outline of input character “a” shown in  FIG. 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  FIG. 10B , 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 1 =an input character of the input-character set with index  1 , considered as the set of pixels with character-intensity values within the pixel-based map of c i      {tilde over (c)} i =dilation (c i )     c   i =erosion (c i )   ĉ i =output character corresponding to c i , considered as the set of pixels with character-intensity values within the pixel-based map of c i      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(a)=the standard deviation of the pixel-intensity values of the pixels in the set of character-intensity pixels that represent character “a”       
 
         [0040]    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 i  as: 
         [0000]    
       
         
           
             
               stroke_irregularity 
               i 
             
             = 
             
               
                 num 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     
                       
                         c 
                         ^ 
                       
                       i 
                     
                     - 
                     
                       
                         c 
                         ~ 
                       
                       i 
                     
                   
                   ) 
                 
               
               
                 num 
                  
                 
                     
                 
                  
                 
                   ( 
                   
                     c 
                     i 
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    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. 
         [0041]    A contrast measure metric can be computed for input character c i  as: 
         [0000]    
       
         
           
             
               contrast_measure 
               i 
             
             = 
             
               
                 
                   sum 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         
                           c 
                           ^ 
                         
                         i 
                       
                        
                       
                         in 
                          
                         
                           ( 
                           
                             
                               
                                 c 
                                 _ 
                               
                               i 
                             
                             ⋂ 
                             
                               
                                 c 
                                 ^ 
                               
                               i 
                             
                           
                           ) 
                         
                       
                     
                     ) 
                   
                 
                 
                   num 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         
                           c 
                           _ 
                         
                         i 
                       
                       ⋂ 
                       
                         
                           c 
                           ^ 
                         
                         i 
                       
                     
                     ) 
                   
                 
               
               ÷ 
               
                 
                   sum 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         
                           c 
                           ^ 
                         
                         i 
                       
                        
                       
                         in 
                          
                         
                           ( 
                           
                             
                               
                                 c 
                                 ^ 
                               
                               i 
                             
                             - 
                             
                               
                                 c 
                                 ~ 
                               
                               i 
                             
                           
                           ) 
                         
                       
                     
                     ) 
                   
                 
                 
                   num 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         
                           c 
                           ^ 
                         
                         i 
                       
                       - 
                       
                         
                           c 
                           ~ 
                         
                         i 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    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. 
         [0042]    A sharpness metric can be computed for input character c i  as: 
         [0000]    
       
         
           
             
               sharpness 
               i 
             
             = 
             
               
                 
                   sum 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         
                           c 
                           ^ 
                         
                         i 
                       
                        
                       
                         in 
                          
                         
                           ( 
                           
                             
                               
                                 c 
                                 _ 
                               
                               i 
                             
                             ⋂ 
                             
                               
                                 c 
                                 ^ 
                               
                               i 
                             
                           
                           ) 
                         
                       
                     
                     ) 
                   
                 
                 
                   num 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         
                           c 
                           _ 
                         
                         i 
                       
                       ⋂ 
                       
                         
                           c 
                           ^ 
                         
                         i 
                       
                     
                     ) 
                   
                 
               
               ÷ 
               
                 
                   sum 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         
                           c 
                           ^ 
                         
                         i 
                       
                        
                       
                         in 
                          
                         
                           ( 
                           
                             
                               ( 
                               
                                 
                                   
                                     c 
                                     ~ 
                                   
                                   i 
                                 
                                 ⋂ 
                                 
                                   
                                     c 
                                     ^ 
                                   
                                   i 
                                 
                               
                               ) 
                             
                             - 
                             
                               
                                 c 
                                 _ 
                               
                               i 
                             
                           
                           ) 
                         
                       
                     
                     ) 
                   
                 
                 
                   num 
                    
                   
                       
                   
                    
                   
                     ( 
                     
                       
                         ( 
                         
                           
                             
                               c 
                               ~ 
                             
                             i 
                           
                           ⋂ 
                           
                             
                               c 
                               ^ 
                             
                             i 
                           
                         
                         ) 
                       
                       - 
                       
                         
                           c 
                           _ 
                         
                         i 
                       
                     
                     ) 
                   
                 
               
             
           
         
       
     
         [0000]    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. 
         [0043]    Finally, a background-uniformity metric can be computed for input character c i  as: 
         [0000]      background_uniformity i =std ({circumflex over ( c )} in ({circumflex over ( c )} i −{tilde over ( c )} i )) 
         [0000]    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. 
         [0044]    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: 
         [0000]    
       
         
           
             metric 
             = 
             
               
                 
                   ∑ 
                   
                     i 
                     = 
                     1 
                   
                   N 
                 
                  
                 
                   metric 
                   i 
                 
               
               N 
             
           
         
       
     
         [0000]    Additionally, the individual outline metrics can be combined to produce a composite outline metric. 
         [0045]    A large variety of different composite metrics may be computed from the above-described metrics and the cumulative metric ΔPQ. In certain embodiments of the present invention, various cumulative metrics are computed. In other embodiments of the present invention, the individual metrics ΔPQ i , stroke_irregularity i , contrast_measure i , sharpness i , and background_uniformity i  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. 
         [0046]      FIG. 11  is a control-flow diagram that illustrates one method embodiment of the present invention. In step  1102 , the identity and characteristics of the character-rendering to be tested are received. In step  1104 , a suitable set of test characters is devised. Then, in step  1106 , 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  1108 , 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  1110 , the output characters are tone mapped and are then, in step  1112 , registered with the input characters. Various input-character/output-character difference metrics are computed, in step  1114 , as discussed above. These metrics may include one or more of ΔPQ i s and ΔPQ, 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  1116 . 
         [0047]    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. 
         [0048]    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: