Facsimile and static presentation processing – Static presentation processing – Attribute control
Reexamination Certificate
1999-01-21
2002-09-03
Lee, Thomas D. (Department: 2724)
Facsimile and static presentation processing
Static presentation processing
Attribute control
C382S251000
Reexamination Certificate
active
06445464
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an image processing method and apparatus for reducing the number of gradation levels of image data through performing error diffusion processing.
2. Description of the Related Art
For outputting an image with a multiple-level gradation obtained through a computer or an image input device, for example, through an image output device such as a printer with a fewer gradation levels, the number of gradation levels of the image data is required to be reduced. Pseudo halftone representation has been utilized for maintaining the quality of an original image while reducing the number of gradation levels. Among several methods of the pseudo halftone representation, an error diffusion method capable of producing a high-quality image has been widely used for printers that generate two levels of output gradation, for example. The error diffusion method is a method of diffusing a quantization error resulting from a target pixel into input image data of unquantized pixels near the target pixel.
The general principle of the error diffusion method will now be described in detail with reference to Hitoshi Takaie and Mitsuo Yae, ‘Gradation Conversion Technique of Digital Image Data with C’, in Interface, August 1993, pp. 158-171.
The error diffusion method is to represent pseudo halftones through modulating quantization errors into high frequencies to be less perceptible considering a characteristic of human visual perception.
FIG. 1
is a block diagram of an image processing apparatus for implementing typical error diffusion processing. The image processing apparatus comprises: a subtracter
111
for subtracting output data of a filter
114
described below from input image data x (i, j); a quantizer (shown as Q)
112
for quantizing output data of the subtracter
111
and outputting the result as output image data y (i, j); a subtracter
113
for subtracting output data of the subtracter
111
from output image data y (i, j); and the filter
114
for performing specific filtering on the output data of the subtracter
113
and outputting the result to the subtracter
111
. In the drawing, e (i, j) represents a quantization error produced through quantization at the quantizer
112
. Therefore the output data of the subtracter
113
is quantization error e(i, j). Coordinates of two directions intersecting each other are represented by ‘i’ and ‘j’, respectively. The two directions will be called i direction and j direction, respectively.
The filter
114
is a sort of linear filter. The transfer function thereof is determined to be G (z
1
, z
2
). Z
1
and z
2
are variables in z transformation in i direction and j direction, respectively. The overall configuration of the image processing apparatus shown in
FIG. 1
is regarded as a two-dimensional delta-sigma modulation circuit. Therefore expression (1) below is given for the relationship of input and output in the image processing apparatus.
Y
(z
1
, z
2
)=
X
(z
1
, z
2
)+H(z
1
, z
2
)
E
(z
1
, z
2
) (1)
In expression (1), Y(z
1
, z
2
), X(z
1
, z
2
) and E(z
1
, z
2
) are values produced through z transformation of y(i, j), x(i, j) and e(i, j), respectively. Transfer function H(z
1
, z
2
) of the filter for modulating quantization error E(z
1
, z
2
) is given by expression (2) below.
H
(z
1
, z
2
)=1
−G(z
1
, z
2
) (2)
The transfer function H(z
1
, z
2
) represents a high-pass filter of two-dimensional finite impulse response (FIR). The high-pass filter is a filter for modulating quantization errors which determines a modulation characteristic of quantization error E(z
1
, z
2
) modulated to a higher frequency. In the following description filters indicated with transfer functions H(z
1
, z
2
) and G(z
1
, z
2
) are shown as filter H(z
1
, z
2
) and filter G(z
1
, z
2
), respectively.
G(z
1
, z
2
) is given by expression (3) below.
G(z
1
, z
2
)=&Sgr;&Sgr;g(n
1
, n
2
) z
1
−n
1
z
2
−n
2
(3)
The first &Sgr; in expression (3) indicates a sum when n
1
is from −N
1
to M
1
. The second &Sgr; in expression (3) indicates a sum when n
2
is from −N
2
to M
2
. Each of N
1
, M
1
, N
2
and M
2
is a positive integer. A filter coefficient is given by g(n
1
, n
2
) and a target pixel by n
1
=0 and n
2
=0.
A typical filters as an example of g(i, j), the coefficient of G(z
1
, z
2
), is given by expression (4) below. The * in the expression represents a target pixel where g(
0
,
0
)=0.
g
(
i
,
j
)
:
(
*
7
5
3
5
7
5
3
1
3
5
3
1
)
/
48
(
4
)
FIG. 2
shows the frequency characteristic of error modulation filter H(z
1
, z
2
) using filter G(z
1
, z
2
) given by expression (4). A greater absolute value of frequency indicates a higher frequency in FIG.
2
. Filter G(z
1
, z
2
) and filter H(z
1
, z
2
) using filter G(z
1
, z
2
) given by expression (4) are called filters of Jarvis, Judice & Ninke (referred to as Jarvis' filter in the following description).
However, the error diffusion method of related art as described above has the following two problems. The first problem is that generation of dots is long delayed in the rising part of the highlight region (where dots are sparse) while generation of white dots (dot-like portions surrounded by dots where there is no dot) is long delayed in the rising part of the shadow region (where dots are dense). Such a phenomenon is called dot delay phenomenon in the present invention.
The second problem is that dots are missing like tailing in the portion near the interface between the region (the shadow region, for example) other than the highlight region and the highlight region. Similarly, white dots are missing like tailing in the portion near the interface between the region (the highlight region, for example) other than the shadow region and the shadow region. Such a phenomenon is called tailing phenomenon in the present invention.
Reference is now made to FIG.
3
and
FIG. 4
for describing a typical example of an image where the above-described dot delay phenomenon and tailing phenomenon occur.
FIG. 3
shows the original image. The range of gradation values of the original image is from ‘0’ to ‘255’. The gradation value is ‘253’ in the background highlight region and ‘2’ in the rectangular shadow region in the center in the original image. The gradation value of the light oblique line drawn in the bottom right portion of the shadow region is ‘210’ to ‘240’ in the original image.
FIG. 4
shows the image produced through performing the error diffusion processing on the original image shown in
FIG. 3
by the image processing apparatus shown in
FIG. 1
so that the gradation levels are reduced to two. A Jarvis' filter is used as the error modulation filter in the error diffusion processing. The processing is performed from left to right in the primary scanning direction and from top to bottom in the secondary scanning direction.
In the image on which the error diffusion processing has been performed shown in
FIG. 4
, no dot is generated in the top part and the left part of the background where dots are to be evenly generated. This is the dot delay phenomenon. Since the error diffusion processing has been performed from left to right in the primary scanning direction and from top to bottom in the secondary scanning direction in the example shown in
FIG. 4
, dot generation is delayed in the top part and the left part and there are regions with no dots. The same applies to the rectangular shadow region in the center where generation of white dots is delayed in the top end part and the left end part. In the example shown in
FIG. 4
, in particular, no white dot is generated in the region from the top end part and the left end part through the part near the bottom right portion in the shadow region.
In the image shown in
FIG. 4
, there is a region where dots are missing like tailing in the bottom right part of the rectangular shadow region in the center. This is the tailing ph
Brinich Stephen
Crosby, Heafey Roach & May
Lee Thomas D.
LandOfFree
Image processing method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image processing method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image processing method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2883339