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.
Background and Significance:
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.
Table of Contents|References|Symbols|Appendix