Image analysis – Image compression or coding – Quantization
Reexamination Certificate
1998-05-21
2001-01-30
Lee, Thomas D. (Department: 2724)
Image analysis
Image compression or coding
Quantization
C382S270000, C358S451000, C358S451000
Reexamination Certificate
active
06181827
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an image processing method and apparatus for reducing gradation levels of image data through performing an error diffusion process with multiple levels.
2. Related Prior Art
When an image with a multiple-level gradation obtained through a computer or an image input device, for example, is outputted through an image output device such as a printer with fewer gradation levels, the gradation levels of the image data must be reduced. Pseudo halftone representation has been utilized for maintaining the quality of an original image while reducing levels of gradation. 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. A multiple-level error diffusion method with quantization levels of three or above has been offered for an image output device capable of representing gradation levels of three or above.
However, the quality of an image is reduced with the multiple-level error diffusion method with fewer quantization levels. For example, when tones of an original image are close to the quantization levels, texture variations are conspicuous and pseudo contours are produced. This is caused by an absence of a random pattern specific to the error diffusion method, which is partly found in an output image. When a tone of original image data is close to a quantization level, the output level is a single quantization level, causing an absence of a random pattern.
In order to effectively prevent image quality reduction due to texture variations, a method is known for superimposing a regular pattern or random noise on image data. However, the method increases errors in every gradation level in the original image data. This sacrifices the best feature of the error diffusion method for producing minimized errors. Consequently the texture of the regular pattern does not match the texture of the error diffusion method. Another problem is, for example, enhanced roughness in an image output.
A method has been proposed for step-by-step error diffusion processing with levels of two to three, then to five as disclosed in Hiroshi Ochi, “High Quality Multiple-level Error Diffusion Method using Gradation Level Processing”, Proceeding of Image Electronics Institute, 24, 1, pp.10-17, 1995. However, it takes longer in performing computation required by the step-by-step processing. Another problem is that roughness is greater since four output levels or above may be used for representing a particular gradation level. A compensation process thereof is required, too.
A 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. Problems of the multiple-level error diffusion method will be described as well.
With the error diffusion method pseudo halftones are represented by modulating quantization errors into high frequencies to be less perceptible, considering a characteristic of human visual perception.
FIG. 11
is a block diagram of an image processing apparatus for implementing the general error diffusion method. The image processing apparatus comprises: a subtracter
111
for subtracting output data of a filter
114
described below from image input data x(i, j); a quantizer (shown as Q)
112
for quantizing output data of the subtracter
111
for outputting as image output data y(i, j); a subtracter
113
for subtracting output data of the subtracter
111
from the image output data y(i, j); and the filter
114
for filtering the output data of the subtracter
113
for outputting to the subtracter
111
. In the figure, 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 referred to as the i direction and the 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 the i direction and the j direction, respectively. The overall configuration of the image processing apparatus in
FIG. 11
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.
[Expression 1]
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 of z transformation of y(i, j), x(i, j) and e(i, j), respectively. Transfer function H(z
1
, z
2
) of a filter for modulating quantization error E(z
1
, z
2
) is given by expression (2) below.
[Expression 2]
H(
z
1
, z
2
)=1−G(
z
1
, z
2
) (2)
The transfer function H(z
1
, z
2
) indicates 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 referred to 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.
[Expression 3]
G(
z
1
, z
2
)=&Sgr;&Sgr;G(
n
1
, n
2)
z
−n1
(3)
The first &Sgr; in expression (3) indicates a sum when n1 is from −N
1
to M
1
. The second &Sgr; in expression (3) indicates a sum when n2 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(n1, n2) and a target pixel by n1=0 and n2=0.
Typical filters as examples of g(i, j), the coefficient of G(z
1
, z
2
) are given by expressions (4) and (5) below. The * in the expressions represents a target pixel where g(0, 0)=0.
[Expression 4]
g
(
i
,
j
)
:
(
*
7
3
5
1
)
/
16
(
4
)
[Expression 5]
g
(
i
,
j
)
:
(
*
7
5
3
5
7
5
3
1
3
5
3
1
)
/
48
(
5
)
FIG. 12
shows a frequency characteristic of error modulation filter H(z
1
, z
2
) using filter G(z
1
, z
2
) given by expression (4).
FIG. 13
shows a frequency characteristic of error modulation filter H(z
1
, z
2
) using filter G(z
1
, z
2
) given by expression (5). A greater absolute value of frequency indicates a higher frequency in FIG.
12
and FIG.
13
. 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 Floyd & Steinberg (referred to as Floyd's filter in the following description). Filter G(z
1
, z
2
) and filter H(z
1
, z
2
) using filter G(z
1
, z
2
) given by expression (5) are called filters of Jarvis, Judice & Ninke (referred to as Jarvis' filter in the following description).
FIG. 14
is an image outputted through the error diffusion method with two levels applying a Floyd's filter to an image input of continuous tone.
FIG. 15
is an image outputted through the error diffusion method with two levels applying a Jarvis' filter to an image input of continuous tone.
FIG. 12
indicates that gains are low in low frequencies and high in high frequencies for the Floyd's filter. As a result, a fine texture is obtained in the image outputted through the two-level error diffusion method as shown in FIG.
14
.
FIG. 13
indicates that gains are higher in some degree in low frequencies and low in high frequencies. As a result, a coarse but uniform texture is obtained in the image outputted through the two-level error diffusion method as shown in FIG.
15
.
The problem of the multiple-level erro
Crosby, Heafey Roach & May
Lee Thomas D.
Shaw, Jr. Philip M.
Sony Corporation
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-2481819