Modeling the Histogram of the Halftone Image to Determine
the Area Fraction of Ink

Yat-Ming Wong

Introduction:

The quality of printed halftone images is often effected by a phenomenon known as "dot gain" in which the dot of a halftone becomes bigger and more spread out than was intended by the system that printed it. This kind of phenomenon can usually be analyzed with image microdensitometry where the digital image of the halftone pattern is captured and ran through various types of image analysis to determine the quality of the printed halftone image.

One way to analyze these images is with a histogram. The histogram is a plot of the frequency against their matching reflectance values. Some particularly useful metrics could be yielded from this type of analysis. The location of the two peaks of this bimodal plot, Ri and Rp and the halftone dot area fraction, F, can simply be estimated from the histogram. This estimate can be gotten through visual analysis of the histogram. This visual approximation, however, does not always yield values that a certain degree of confidence in its accuracy could be placed on.

In the ideal case, visual approximation would not be a problem. The histogram that this case would yield would only be two spikes, each to represent either the ink or the paper population of the image. With the occurrence of "dot gain," however, these two spikes had spread out and sometimes merged, as shown in Figure 1 below. It is with these images that visual approximation begins to fail as a method of determining the halftone dot area fraction F.

The main goal here is to determine if computational models could be developed to match the histograms of halftone images where the area fraction of ink becomes hard to determine. These computational models are functions that, when manipulated, would give a graphical representation of a histogram that could match the histogram of a real halftone pattern.

Halftone images are made up of dots of ink variable size, density, and distance to other dots. Varying the attributes of these dots is how different tones of a color are created. A photo printed in a newspaper is an example of how variations in dots are able to create different greys and textures. Halftone images are generally created by such printing systems as electrophotography, laser and ink-jet.

In trying to measure optical quality of a halftone image, the image can be captured by a camera or scanner and sampled pixel by pixel. One way to use this sampled image in judging quality is by plotting its histogram. A reflectance value is measured for each pixel of the image and the frequency tallied of pixels with the same reflectance values. The histogram is a plot of the frequency against their matching reflectance values.

Since the reflectance values range from 0 (black or no reflectance) to 1 (white or total reflectance), the histogram in turn tells us how the image varies across the grayscale. Image histograms do not carry spatial information. They are only probability density functions for the occurrence of reflectance levels in the image, regardless of where in the image the gray level occurs.(5) However, by knowing the image represents a halftone, the properties of the histogram can be related to the spatial properties of the halftone. The area of the first peak can then be considered the ink population of the image. And the area of the second peak becomes defined as the population of paper.

The ideal histogram is one where the peaks are clearly separable so the area under each is easily attainable. The histogram would be bimodal with a delta function of area F and another of area 1-F for the ink and paper area fractions, respectively.

This is usually not the case as most printing systems do not produce such ideal halftone images. Electrophotography would deposit particles that conglomerate to look like a dot, while an ink-jet would create drops of ink that disperse into dots. In each case, the way in which the dots are created can cause a difference in the optical quality of the resulting halftone image. Noise and dot spreading of halftone dots causes the populations to spread. The peaks are often linked, making it hard to distinguish the area of either peak. It becomes hard to determine simply by examining the histogram which part of the histogram represents the population of ink and which of paper.

Visual approximation of the threshold has been the method used to determine the separation. This is a highly inaccurate method of determination however. Another method is needed to segment this histogram.

"The major applications, [however], have been concerned with output modalities whereby the image is continuous rather than discrete in nature, as for conventional halftones. There is only a limited amount of published work concerning the latter, while the need grows considerably with the advent electronic/digital imaging systems: digital halftones, laser writers and ink-jet printers are just a few examples of these."(1) There has been current research done on "extracting halftones from printed documents using texture analysis."(2) No research had been done so far on method to segment the histogram to extract such information as the area fraction of ink of a halftone image.

By finding a more efficient method to replace the use of visual approximation, there would be a better way to judge the optical quality of halftone images. In finding a model computationally, a histogram of the image could be matched to a function. Once the function matches the histogram, the area fraction of ink becomes easier to find.

Optical quality and efficiency is important to printing systems. Finding a metric rather than visual way of judging the optical quality will give a good comparative basis in determining how well a particular system works.

Experimental Designs & Methods:

Initial Imaging:

• Black and white halftone images is captured by a camera controlled by a computer running the IMLAB software
• Resolution can be neglected when image is captured as development of the computational model will not take it into account
• The sampled image will then be read for its reflectance values pixel by pixel by the IMLAB software and a histogram generated by plotting the number of pixels with the same reflectance value against the reflectance values
• Analyzation may be as easy as just looking at the histogram, or it may take a computational model.

Modeling the Bimodal Histogram Computationally through the Sum of Two Gaussians:

• When a histogram of a halftone image is plotted, most of time the result is bimodal. Since this bimodal had a tendency to look like two gaussian functions, a model was developed based on this idea.
• Each peak would be considered a separate gaussian function:

Eq.1&2  (4)

• The resulting function that is used to match the histogram is the sum of two gaussian function above:

Eq.3  (3)

By manipulating the variables in the three equations above, the Sum(R) can try and model the histogram of an actual halftone.

s1 = width of first peak s2 = width of second peak

R1 = location of first peak R2 = location of second peak

F = height of first peak1-F = height of second peak

The advantage of this model is that it will give a better estimate of the fractional value of ink in an image. The current method of visual approximation of the value will not always work. In ideal models, the guess would probably be just as accurate as values obtained from the computational model. In other models, where it is harder to judge the threshold of the two peak, the generated model would give the reasonable value.

Modeling the Bimodal Histogram Computationally through using the Straight-Edge Concept:

• A halftone image is made up of collection of edges:

• Consider the image as a single "equivalent" straight edge:

The straight edge above shows the ideal case that would give a histogram showing two delta functions. The straight edge's characteristics could be changed by manipulating different variables as shown below:

The equivalent straight edge of a halftone could be like the example shown below where the plot of the reflectance across the edge can be expressed by the reflectance equation below.

Eq.4

The histogram represents the frequency of occurrence of a given value of R. Since the frequency is inversely proportional to the slope of the R versus x curve, the histogram of a halftone should be represented by equation (5).

Eq.5

The resulting curve, however, only somewhat resemble the histogram sought. The function is one that did not take variation in halftone dots and granularity into consideration. By convolving the resulting curve with a noise metric, such as equation (6), the curve will be smoothed out.

Eq.6  (4)

• The functions H and S are convolved by multiplying the Fourier transform of the functions and taking the inverse Fourier transform of the product.

Eq. 7.0

G(R) = x Eq. 7.1 (4)

g(R) = F-1{G(R)} Eq. 7.2

• The resulting function, g(R), looks much more like the halftone histograms sought. By manipulating the variables in equation (4) and equation (6) above, the g(R) can try and model the histogram of an actual halftone.

Rmin = the location of the first peak Rmax = the location of the second peak

F = height of the first peak1-F = height of the second peak

s = width of entire functiona = height of the trough of the function

Fit Evaluation:

• In evaluating the fit of each model to the histogram, there are two different methods that can be used: the RMS deviation and a plot of the deviation against the value of reflectance.

Eq.8

Results:

Sum of Two Gaussians Model:

The algorithm, having been developed, was written in a math software program, MathCad. This model was tested against real halftone images by trial and error. Each variable was shifted back and forth across a range of values to find the set of variables that would yield the lowest root mean square deviation. Below in Table 1 is the set of variables found for each image that yielded the lowest root mean square deviation.

Table 1. Sum of two Gaussians Model results through MathCad.

The root mean square deviation values may seem low but when the computational model was placed through another fit evaluation, the fit was found to be lacking in specifically one area. Figure 15 and Figure 16 illustrate a common problem found with most of the halftone images that were matched computationally. In cases where there is a high trough, the algorithm developed invariably failed to meet that trough. The value of where the two Gaussians merge together to form the sum of two Gaussians is not high enough in comparison to the halftone data.

Equivalent Straight Edge Model:

Like the sum of two Gaussians model, the straight edge algorithm was developed in a math software program, MathCad. This model was tested against the same halftone images by trial and error. Each variable was shifted back and forth across a range of values to find the set of variables that would yield the lowest root mean square deviation. Below in Table 2 is the set of variables found for each image that yielded the lowest root mean square deviation.

Table 2. Equivalent Straight Edge Model results through MathCad

The root mean square deviation presented in Table 2 is good deal lower than the values presented for Table 1. Unlike the sum of two Gaussian functions though, when the computational model of the equivalent straight edge was put through another fit evaluation the results did not show the disparity evident in the former model. Figure 17 and Figure 18 illustrate how well the equivalent straight edge model matches with most halftones.

Comparison of the sum of two Gaussians model to the equivalent straight edge model:

The lowest root mean square deviation values for both models were compared in Table 3. The equivalent straight edge model has a lower deviation by a factor of 0.1. The difference is great between the two models. It is clear that the equivalent straight edge model is the better algorithm for determining the area fraction of ink.

Table 3. The root mean square deviation results from both the sum of two Gaussians model and the equivalent straight edge

Where the Equivalent Straight Edge Model fails:

The equivalent straight edge may indeed be the better of the two algorithms developed. It also seems to match halftone data fairly well. While the root mean square deviation is fairly low, it would be feasible to look more closely at the match between the model and the real data. In enlarging the areas where discrepancies could be seen as shown in Figure 19, the match could clearly be seen to fit poorly in certain areas; Figure 20 and Figure 21.

Conclusions:

It is easy to see how well the equivalent straight edge model works and completely brush aside any problems that the model may have. Afterall, the visual and numerical evidence was there to say that the algorithm matched correctly. This, however, would be a tragic mistake. When the slight disparities were enlarged in an equivalent straight edge model match to real halftone data, the difference, shown in Figure 20 and Figure 21 between the functions became obvious. Even without enlarging portions of this match, it can become quite clear that the algorithm has problems.

In trying to match approximately 20 halftone images to their computational counterpart by trial and error, difficulties began to arise when the model had to match any real data with a histogram where the bimodal peaks were far apart. With each consecutive image that exhibited this same histogram characteristic, it became increasingly clear that the root of the problem was the one s variable controlling the width of the computational model. The s originates from the Gaussian noise metric that was convolved with the model to smooth out the function. The Gaussian function used to smooth out the model compensates for the entire function. It does not allow for cases where the histogram begins to resemble two delta functions. In this aspect, the model begins to fail. The model does a better job at matching halftones where the distinction between ink and paper populations in less clear. It is ironic that the equivalent straight edge model should work so well for degraded halftones than ones that come closer to matching the ideal, where the populations of ink and paper are shown as two distinct delta functions in the histogram.

While the sum of two gaussians model did not fair so well under inspection as the straight edge model may have, it does bear a look at. The major problem with this model is easily seen. The sum of the two gaussians has a problem in matching up to the halftone data where the two gaussians should merge. The trough of the computational model would invariably be lower than that of the halftone's histogram. This failure in the sum of two gaussians model indicates that the algorithm can not be used for the purpose it was developed; to find the area fraction of ink within a histogram. It is, however, not to say that the model does not have its uses and good characteristics.

In trying to match approximately 20 halftone images to their computational counterpart by trial and error, difficulties only arose when the model had to match any real data with a histogram where the bimodal peaks were close together. The root problem for this model was in its inability to control the height of where the Gaussian functions met. The model, however, also has its merits. It modeled each peak well in width, height and location.

The equivalent straight edge model compensated for the one thing that had been lacking in the sum of two Gaussians model, and subsequently is the better model. But the sum of two Gaussians model has the characteristics that the equivalent straight edge model, upon closer inspection, is lacking in. It seems ironic that the one thing lacking in one model is the strong suit of the other model. Perhaps by combining the two models, a better model may be developed where the model has control of the height of the trough and minimizes the disparities of having bimodal peaks far apart.