Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1999-02-23
2003-01-21
Tran, Phuoc (Department: 2621)
Image analysis
Image compression or coding
Quantization
C358S001900, C358S003040, C345S616000
Reexamination Certificate
active
06510252
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 by performing error diffusion processing.
2. Description of the Related Art
For example, when an image with a multiple-level gradation obtained through a computer or an image input device, is outputted through an image output device such as a printer with a fewer gradation level, the number of gradation levels of the image data is required to be reduced. Pseudo halftone representation has been conventionally utilized to maintain the image quality of an original image as high as possible, 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 with two levels of output gradation, for example. It is to be noted that the error diffusion method is a method of diffusing a quantization error caused from each of target pixels into input image data of unquantized pixels near each of target pixels.
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 a method to represent pseudo halftones by 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: subtracter
111
for subtracting output data of filter
114
described below from input image data x(i, j); quantizer(shown as Q)
112
for quantizing output data of the subtracter
111
and outputting the result as output image data y(i, j); 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 processing on the output data of the subtracter
113
and outputting the result to the subtracter
111
. In the drawing, a quantization error caused through quantization at the quantizer
112
is represented by e(i, j). Therefore, the output data of the subtracter
113
equals the quantization error e(i, j). Coordinates of two directions intersecting each other at right angles 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 with respect to i direction and j direction, respectively. The overall configuration of the image processing apparatus shown in
FIG. 1
is regarded as a two-dimensional sigma-delta modulation circuit. Therefore, the relationship of input and output in the image processing apparatus is given by expression (1) below.
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 caused 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 represented by 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
−n1
z
2
−n2
(3)
The first &Sgr; in expression (3) represents a sum when n
1
is from −N
1
to M
1
. The second &Sgr; in expression (3) represents 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 prescribed positive integer. A term g(n
1
, n
2
) represents a filter coefficient, and n
1
=0 and n
2
=0 represents a target pixel.
A coefficient of G(z
1
, z
2
), namely g(i, j), of a typical filter is given by expression (4) below, for example. 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 a filter H(z
1
, z
2
) for modulating errors, using filter G(z
1
, z
2
) given by expression (4).
FIG. 2
shows that as for frequency, the greater the absolute value is, the higher the frequency is. 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, performing the conventional error diffusion method as described above has a problem that in highlight area (where dots are sparse) and in shadow area (where dots are dense), a pattern called “worm”, characteristic of the error diffusion method, occurs, caused by the poverty of the dispersion of dots, resulting in the deterioration of the image quality.
One example of the image with the “worm” pattern caused by the poverty of the dispersion of dots is shown in FIG.
3
. The figure shows the highlight part of the image, obtained by performing error diffusion processing using the above-mentioned common Jarvis' filter on the image of which gradation values differ gradually in vertical direction( referred to as lamp image in vertical direction in the following description). It is obvious in the image shown in the figure that dots are dispersed unevenly, causing a row of dots such as the mark of worm creeping, “worm” pattern, resulting in the deterioration of the image quality.
The consideration of the reason why the dispersion of dots becomes poor by performing conventional error diffusion method will now be made, by focusing on the frequency characteristic of a filter for modulating quantization errors. The frequency characteristic of Jarvis' filter shown in
FIG. 2
is represented with contour lines in FIG.
4
. The three-dimensional form(characteristic) of the frequency characteristic of the filter becomes clear by the representation. First, according to
FIG. 4
, it is obvious that the frequency characteristic of the filter is three-dimensionally asymmetrical, caused by a fact that the coefficient of the filter for modulating quantization errors is three-dimensionally asymmetrical as is shown in expression (4). Second, three-dimensional distortion is large, especially in the middle part of the frequency characteristic shown in
FIG. 4
, namely the characteristic part with respect to the low frequency band of quantization errors. Because the deterioration of the dispersion of dots is most remarkable in flat part, such as in highlight area or in shadow area, it is possible to be concluded that the three-dimensional distortion of the middle part of the frequency characteristic shown in
FIG. 4
, causes the three-dimensional inclination in the frequency characteristic of output image data, resulting in the deterioration of the dispersion of dots causing “worm” pattern.
Therefore, it is possible to be concluded that the problem of the dispersion of dots will be solved, when the characteristic with respect to the low frequency band of the filter for modulating quantization errors is improved to be more three-dimensionally symmetrical.
However, when the characteristic with respect to the low frequency band of the filter for modulating quantization errors is improved, then the distortion of the
Crosby, Heafey Roach & May
Sherali Ishrat
Sony Corporation
Tran Phuoc
Wigert, Jr. J. William
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-3070446