Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1999-05-07
2003-05-13
Lee, Thomas D. (Department: 2724)
Image analysis
Image compression or coding
Quantization
C382S237000, C358S003030, C358S003040
Reexamination Certificate
active
06563957
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a tone dependent error diffusion halftoning method, and in particular to an efficient tone dependent error diffusion halftoning method with optimized thresholds and error weights that produce a high quality halftone image.
BACKGROUND
Continuous-tone images, such as charts, drawings, and pictures, may be represented as a two-dimensional matrix of picture elements (pixels). The spatial resolution and intensity level for each pixel are chosen to correspond to the particular output device used.
Digital halftoning is the process of transforming a continuous-tone image to a binary image, i.e., the pixel is either on or off. The low pass characteristic of the human visual system allows the binary texture patterns to be perceived as continuous-tones.
Hardcopy output devices, such as inkjet printers, are bi-level devices that eject droplets of ink to form dots on a medium. Such printers cannot print continuous-tone images and, thus, use digital halftoning so that the printed binary image on the medium will be perceived as the original image.
For printing applications, absorptance is used to represent a pixel value. A printing process typically puts absorptive dots on white paper. For an ideal device model, the colorant absorptance is 1 (a dot is printed); and the paper absorptance is 0 (no dot is printed). A pixel value in a general continuous-tone, i.e., gray scale, image is represented in units of absorptance between 0 and 1. It should be understood, of course, that the pixel value may be represented by a “near continuous-tone” range, e.g., from 0 to 255, as is used in conventional computer monitors. The binary tone level in such a case will be represented as either 0 (off) or 255 (on).
Halftoning methods are described in the book Digital Halftoning, by Robert Ulichney, The MIT Press, 1987, incorporated herein by reference. Generally, halftoning methods can be grouped into three categories. They are iterative optimization methods, screening, and error diffusion.
Iterative methods use a human visual system model to minimize the perceived error between the continuous-tone image and the halftone image. An iterative method is direct binary search, which can be used to create high quality halftone images. Unfortunately, iterative methods require a great deal of computation which makes real time image processing impractical.
Screening, on the other hand, is a low complexity halftoning method that does not provide very high quality halftone images. A screen is defined by a matrix of threshold values. To binarize a continuous-tone image, the threshold matrix is periodically tiled over the image. Pixels that are greater than the corresponding matrix threshold values are binarized to 1; otherwise they are binarized to 0.
Error diffusion halftoning methods use a feedback loop to subtract the past weighted diffused errors from an input pixel value to obtain a modified pixel value. The modified pixel value is then compared with a threshold value to determine the halftone output value. Thus, the decision about whether or not to print a dot at a particular pixel is based not only on the continuous-tone level for that pixel, but on what has happened before for previously processed pixels. The error to be diffused, i.e., the quantizer error, is obtained by subtracting the modified pixel value from the output value. The error is then diffused to a set of future pixel locations by subtracting the weighted error from the future pixel locations. The local tone will be preserved if the sum of the weights is 1.
Error diffusion is an efficient halftoning method compared with direct binary search, but is more complex than screening. However, halftone images produced by conventional error diffusion methods are typically of lower quality than images produced by direct binary search methods.
A well known error diffusion technique is described by R. Floyd and L. Steinberg in the paper Adaptive Algorithm for Spatial Grey Scale, SID Int'l. Sym. Digest of Tech. Papers, pp. 36-37 (1975), incorporated herein by reference.
A diagram of the conventional error diffusion system
10
is shown in FIG.
1
. As shown in
FIG. 1
, the input pixel value, which has continuous-tone value, is represented as f[m,n], where m and n are the pixel locations; the modified pixel value is represented by u[m,n]; and the output halftone value is represented by g[m,n], which is determined by a thresholding operation as follows:
g
[
m
,
n
]
=
{
1
,
if
u
[
m
,
n
]
≥
t
[
m
,
n
]
,
0
,
otherwise
,
equ
.
1
where t[m,n] is the threshold matrix 12.
The quantizer error d[m,n] is determined by subtracting the modified pixel value u[m,n] from the output halftone value g[m,n] at adder
14
as follows:
d[m, n]=g[m, n]−u[m, n].
equ. 2
The quantizer error d[m,n] is then diffused to neighboring, subsequently processed pixel locations through the error-weighting matrix
16
.
The modified pixel value u[m,n] is updated as:
u[m+k,n+
1
]←u[m+k,n+
1
]−w[k,l]d[m,n],
equ. 3
where w[k,l] is the error-weighting matrix
16
. To preserve the local tone,
∑
k
,
l
w
[
k
,
l
]
=
1
equ
.
4
Thus, the inputs to adder
18
may be represented as:
u
[
m
,
n
]
=
f
[
m
,
n
]
-
∑
k
,
l
w
[
k
,
l
]
d
[
m
-
k
,
n
-
1
]
=
f
[
m
,
n
]
-
c
[
m
,
n
]
equ
.
5
were c[m,n] is the modification term defined by:
c
[
m
,
n
]
=
∑
k
,
l
w
[
k
,
l
]
d
[
m
-
k
,
n
-
1
]
.
equ
.
6
Thus, the modification term c[m,n] is the diffused quantizer errors from previously processed pixels.
The conventional error diffusion system
10
binarizes an image in conventional raster scan order. The threshold t[m,n] in the threshold matrix
12
has a constant value, e.g., 0.5, for all m, n. The error weighting matrix
16
uses four non-zero weights w[0,1]=7/16, w[1,−1]=3/16, w[1,0]=5/16, and w[1,1]=1/6 which are used to diffuse the error as shown in FIG.
2
.
FIG. 2
is a diagram 20 showing the distribution of the error, where the current pixel 22 being processed is indicated by a “P.”
The conventional error diffusion system
10
has long been known to produce smooth and sharp halftone images.
FIG. 3
is a gray level halftoned image
30
generated using the conventional error diffusion system
10
. The image
30
of
FIG. 3
ranges from full black, i.e., a tone of 1, to full white, i.e., a tone of 0 (if using absorptance). As can be seen in
FIG. 3
, system
10
generates visible artifacts, such as worms
32
,
33
in the highlight and shadow areas and structured patterns
34
,
36
, and
38
in the mid-tone areas.
Many error diffusion variations and enhancements have been developed to improve the halftone quality. For example, some error diffusion systems modify the thresholds by replacing the fixed threshold with an ordered threshold matrix or by using a matrix which has sparse threshold values along one of its diagonals, the direction of the diagonal being perpendicular to the prevailing direction of worm artifacts. One method described in J. Sullivan, R. Miller and G. Pios, “Image Halftoning Using a Visual Model In Error Diffusion,” J. Opt. Soc. Am. A, Vol. 10, No. 8, pp. 1714-1724, August 1993, which is incorporated herein by reference, determines the quantizer threshold with past outputs using a visual system model that is incorporated directly into the architecture of the error diffusion system. The architecture in the system described by Sullivan et al., is complex because of extra filters used for the visual system model, which requires additional computation.
Some error diffusion methods use variable er
Allebach Jan P.
Li Pingshan
Hewlett--Packard Company
Lee Thomas D.
LandOfFree
Tone dependent error diffusion does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Tone dependent error diffusion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tone dependent error diffusion will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3069652