 |
Claims  |
|
|
We claim:
1. A method for minimizing the contouring effects in a quantized digital
image, comprising the steps of:
a) quantizing an original image using a quantizer to produce a quantized
image;
b) determining, by a digital computer, the luminance value for each pixel
of the original digital image and the quantized version of the original
image;
c) determining, by the computer, busy and smooth regions in the original
digital image;
d) for smooth regions, determining, by the computer, luminance variations
(gradients) in the original digital image for each pixel by a first Sobel
operator;
e) for corresponding smooth regions, determining by the computer luminance
variations in the quantized digital image for each pixel by a second Sobel
operator;
f) determining, by the computer, the difference between the original
luminance variations and the quantized luminance variations for each pixel
by a differencer coupled to said first Sobel operator and coupled to said
second Sobel operator;
g) selecting, by the computer, a threshold value that when exceeded is
indicative of the existence of contours;
h) comparing, by the computer, the difference of step f) with the threshold
value of step g) and if the threshold is exceeded indexing the presence of
a contour at an associated pixel of the quantized image;
i) for each pixel (i,j) of the quantized image searching, by the computer,
for a contour index in a window of pixels around each pixel; and
j) when a contour index is found, computing a new color to be placed at
each pixel (i,j).
2. A method for minimizing the contouring effects in a quantized digital
color image, comprising the steps of:
a) generating an original digital color image;
b) quantizing the original digital color image using a quantizer to produce
a quantized digital color image of said original digital color image;
c) determining, by a digital computer, the luminance value for each color
pixel of the original digital image and the quantized digital color image;
d) determining, by the computer, busy and non-busy (smooth) regions of the
original digital color image;
e) for the smooth regions, determining, by the computer, the luminance
variations (gradients) in the original digital color image for each pixel;
f) for corresponding smooth regions, determining, by the computer,
luminance variations in the quantized digital color image for each pixel;
g) determining, by the computer, the difference between the original
luminance variations and the quantized variations for each pixel of the
smooth region;
h) selecting, by the computer, a threshold value indicative of contours;
i) comparing, by the computer, the difference of step g) with the selected
threshold value of step h) and when the threshold is exceeded marking the
presence of a contour at an associated pixel of the quantized digital
color image;
j) for each pixel (i,j) of the quantized digital color image, searching, by
the computer, for a contour mark in a window of surrounding pixels; and
k) when a contour mark is found, determining, by the computer, a new color
to place at each pixel (i,j).
3. The method for determining a new color for each pixel (i,j) according to
claim 2 wherein step k) is further comprised of the steps of:
i. determining the position of each pixel (i,j) containing the new color;
ii. determining a value of the new color; and
iii. replacing the value of each pixel (i,j) by the value of the new color.
4. The method for minimizing the contouring effects in a quantized digital
color image according to claim 2 wherein step d) is further comprised of
the steps of:
i. dividing the original digital image into blocks of pixels;
ii. determining the average luminance value of the pixels in each of the
blocks;
iii. determining a total difference of each individual pixel in the block
from the average luminance value; and
iv. comparing the total difference value against a threshold value to
determine when the threshold value is not exceeded indicating the block is
a smooth region.
5. The method according to claim 4 wherein in step iii) the total
difference is determined as the summation of the absolute value of the
difference of each individual pixel in the block from the average
luminance value.
6. The method for minimizing the contouring effects in a quantized digital
color image according to claim 4 wherein the average luminance value
(y.sub.p) of the pixels is determined by:
y.sub.p =a.sup.t C.sub.p
where a.sup.t is a weighting vector for the pixel and C.sub.p is a color
vector of the pixel.
7. The method according to claim 6 wherein a.sup.t is chosen to have the
value 1/4, 1/2, 1/4.
8. A system for minimizing the contouring effects in a quantized digital
image, comprising:
a) a quantizer quantizing an original digital image; and
b) a computer coupled to the quantizer, said computer comprising:
means for determining a luminance value for each pixel of an original
digital image and a quantized version of the original digital image;
means for determining busy and smooth regions in the digital image;
means for determining for smooth regions of the original digital image the
luminance variations (gradients), said means for determining original
image luminance variations including a first Sobel operator;
means for determining the luminance variations in the quantized digital
image for regions corresponding to the smooth regions of the original
digital image for each pixel, said means for determining quantized image
luminance variations including a second Sobel operator;
means for determining a difference between the original luminance
variations and the quantized luminance variations for each pixel of a
smooth region, said means for determining the difference including a
differencer coupled to said first Sobel operator and coupled to said
second Sobel operator;
means for establishing a threshold value that if exceeded is indicative of
an existence of contours;
means for receiving the difference and the threshold value and for
comparing the difference with the threshold value and when the threshold
is exceeded providing an index, reflecting a presence of a contour at an
associated pixel of the quantized image; and
search means for searching for a contour index in a window of pixels around
each pixel (i,j) of said quantized image and for computing a new color to
place at the pixel (i,j) if a contour index is found.
9. The system for minimizing the contouring effects in a quantized digital
color image according to claim 8 wherein said means for determining busy
and smooth regions is further comprised of:
i. means for dividing the original digital image into blocks of pixels;
ii. means for determining the average luminance value of the pixels in each
of the blocks;
iii. means for determining a total difference of each individual pixel in
the block from the average luminance value; and
iv. means for comparing the total difference value against a threshold
value to determine when the threshold value is not exceeded indicating the
block is a smooth region.
10. The system according to claim 9 wherein said means for determining busy
and smooth regions in the digital image determines a summation of the
absolute values of difference between the original luminance value of each
individual pixel in the block and the average luminance value of each
individual pixel in the block.
11. The system for minimizing the contouring effects in a quantized digital
color image according to claim 9 wherein said means for determining a
luminance value for each pixel of an original digital image and a
quantized version of the original digital image determines the luminance
value (Yp) for each pixel by:
Y.sub.p -a.sup.t C.sub.p
where a.sup.t is a weighting factor for each pixel and C.sub.p is a color
vector of each pixel.
12. The system according to claim 11 wherein a.sup.t is chosen to have the
value 1/4, 1/2, 1/4.
13. The system according to claim 8 and further comprising:
i. means for determining the position of a pixel (i,j) containing the new
color; and
ii. means for determining the value of the new color and for replacing the
value of the pixel (i,j) with the value of the new color. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
A portion of the disclosure of this patent document contains material which
is subject to copyright protection. The copyright owner has no objection
to the facsimile reproduction by anyone of the patent document or the
patent disclosure, as it appears in the Patent and Trademark Office patent
file or records, but otherwise reserves all copyright rights whatsoever.
TECHNICAL FIELD OF THE INVENTION
The present invention relates to the field of digital image processing and
more particularly to systems and methods for removing contouring effects
from a quantized digital image.
BACKGROUND OF THE INVENTION
A portion of the disclosure of this patent document contains material to
which a claim of copyright protection is made. The copyright owner has no
objection to the facsimile reproduction of any one of the patent documents
or the patent disclosure, as it appears in the U.S. Patent and Trademark
Office patent file or records, but reserves all other rights whatsoever.
When processing digital images, particularly color images, it is often
necessary to perform a quantizing operation upon the digital values that
represent each of the pixels forming the digital image. Color quantization
often gives rise to false contouring artifacts in an image formed with
these quantized digital values. Contouring occurs when colors of spatially
adjacent pixels, that are also close to each other in the color space, Get
mapped into different colors by the quantizing process. This contouring is
usually highly objectionable because it appears in smooth regions where
the human visual system has relatively low tolerance to noise. In
particular, the noise is of a correlated nature, taking the form of lines
and circles, and hence is easily noticed by the human eye.
The removal of contouring effects in images has been the subject of a
number of patents and papers. What the present solution to the problem
offers is a quicker way to identify the existence of contours and of
applying a correcting algorithm to only those regions of the image that
contain the contours.
SUMMARY OF THE INVENTION
In the preferred method of this invention for minimizing the contouring
effects in a quantized digital color image there is provided the steps of:
a) determining the luminance value for each color pixel of the original and
the quantized digital color image;
b) determining busy and non-busy (smooth) regions of the original digital
color image; and
c) for smooth regions determining the luminance variations (gradients) in
the original digital color image;
d) for the same smooth regions determining luminance variations in the
quantized digital color image;
e) determining the difference between the original luminance variations and
the quantized variations;
f) selecting a threshold value indicative of contours;
g) comparing the difference of step e) with the selected threshold value of
step f) and if the threshold is exceeded mark the presence of a contour at
the associated pixel;
h) for each pixel of the quantized digital color image, search for a
contour mark in a window of surrounding pixels; and
i) if a contour is found determine a new color to place at the pixel.
From the foregoing it can be seen that it is a preferred object of the
present invention to provide a system and an associated method for
removing contouring effects from a quantized digital color image.
It is another object of the present invention to provide a means for
quickly determining the contours of a quantized digital color image.
It is yet another object of the present invention to provide a method for
removing image contours composed of two or more colors in a quantized
digital color image.
These and other objects of the present invention will become more apparent
when taken in conjunction with the following description and drawings
wherein like characters indicate like parts and which drawings form a part
of the present invention.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1, illustrates in block diagram form a prior art quantizer that may be
used with the present invention to provide quantized input pixel values
Q.sub.p.
FIG. 2, illustrates in block diagram form a prior art dithering technique
incorporating a quantizer for providing input pixel values Q(i,j).
FIG. 3, illustrates in flow chart diagram form the comparison of the pixel
values of the original image against the pixel values from the quantized
version of the original image to determine the existence of a contour.
FIG. 4, is a chart illustrating a desired luminance transform for enabling
contour detection.
FIG. 5, is a block schematic diagram illustrating a system for generating
luminance gradients and luminance gradient differences.
FIG. 6 illustrates in flow chart form the operation of the pixel
replacement algorithm of the present invention.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
Referring to FIG. 1, a prior art quantizer system 10 that may be used with
the present invention to provide quantized input signals Q.sub.p
representing an original image is shown comprised of; a quantizer 20,
having as an input the signal C'.sub.p that is received from the output of
a summer 22. The summer 22 receives as inputs the original image signal
C.sub.p and the output from an error diffusion filter 28. A difference
node 26 receives as inputs the signals C'.sub.p and Q.sub.p and provides
on its output the difference between these two signals, the signal Np,
which is directed to the input of the error diffusion filter 28.
In operation, the pixels of an original image are scanned in a raster
fashion, to form an unquantized color vector C.sub.p =[R,G,B].sup.t at
pixel location p. The color vector C.sub.p is modified by adding to it a
weighted sum of previous quantization errors (the weights being applied by
the filtering action of filter 28) to form a modified color vector
C'.sub.p. The modified color vector C'.sub.p is then quantized to the
closest color Q.sub.p in a palette of color values and the resulting
quantization error N.sub.p is determined in the difference node 26 and
forwarded to other unquantized pixels C.sub.p via the error diffusion
filter 28 and the summing node 22. The error diffusion filter 28 provides
a high-pass characteristic to the signal N.sub.p. This is desirable, since
the human visual system is less sensitive to error components at high
frequencies. Hence, in smoothly varying regions, error diffusion adds a
high frequency noise pattern to the image that breaks up the correlated
nature of quantization errors and eliminates contouring. One potential
disadvantage with this approach is that if errors accumulated by the error
diffusion filter are not cancelled by other errors of opposite polarity,
the error diffusion filter may become unstable and yield undesirable
artifacts.
Referring to FIG. 2, in another prior art method, a periodic noise pattern
d(k,l) may be added to the image prior to quantization. The noise pattern
is generated by generator 30 and summed with the signal C(i,j) to form the
signal. C'(i,j) in the summer 32. The signal C'(i,j) is then directed to
the quantizer 20. The equation for that action is as follows:
C'(i,j)=C(i,j)+d(i mod N, j mod N)
where d(k,l) is an N.times.N dither matrix with vector entries. The color
C'(i,j) is then quantized to the closest color Q(i,j) in the palette. The
matrix d is chosen to have an average value of zero and an energy spectrum
with a high frequency characteristic. Regions of constant color are
quantized to a set of similar colors in the palette, hence breaking up
correlated contouring errors. FIG. 2 illustrates the process with the
quantizer 20 receiving the signal C'(i,j), that has been formed by the use
of a dithering matrix 30 providing its output signal to an input of a
summing node 32. A major difficulty in applying ordered dither to color
images with image-dependent palettes is that since the colors are not
uniformly distributed in the color space, the distance between neighboring
colors varies significantly throughout the space, and thus it is almost
impossible to obtain a constant dither matrix that will satisfactorily
dither all areas of constant color in the image. C. Bouman et al., in
their publication "Color Image Display With a Limited Palette Size", Proc.
of SPIE Conf. on Visual Comm. and Image Proc., vol. 1199, pp. 522-533,
Philadelphia, Pa., Nov. 8-10, 1989 suggest a method to locally dither a
pixel between only two palette colors, Q.sub.1 and Q.sub.2 that are
closest to the actual pixel color. The dither signal is then the vector
(Q.sub.2 -Q.sub.1,) modulated by a matrix of scalar dither values d(k,l)
that fall in the range [-1/2, 1/2]. The disadvantage of this approach is
that finding the two closest palette colors to a pixel is computationally
intensive. Further, the colors Q.sub.1 and Q.sub.2, and hence the
orientation of the dither matrix, may change rapidly in a small spatial
region. In such a situation, it is possible that contouring will not be
eliminated at all.
Selective Contour Removal
Both error diffusion and ordered dithering sacrifice spatial resolution for
an increased number of perceived colors. However, if error diffusion or
ordered dithering is performed on the entire image, there may be some loss
in spatial detail, especially around edges and other busy areas of the
image. The present invention provides an algorithm that performs selective
contour removal. The novelty in this approach is that the entire image
does not have to be examined for the presence of contours, and only
regions that are in the window of contours are involved in the contour
removal step. Furthermore, unlike conventional dithering, the contour
removal is not integrated with the pixel quantization step, i.e. no
remapping of input colors to palette colors is performed during the
contour removal. In fact., it is assumed that both the digitized original
and the quantized digital color images are available as inputs to the
algorithm. The procedure will be described in two steps: contour detection
and contour removal.
Contour Detection
Referring to FIG. 3, to detect the presence of contours in a quantized
color image, the image is examined for regions where the luminance values
vary smoothly in the original image, but in discrete steps in the
quantized image. Luminance variation is used, since the human visual
system is more sensitive to successive changes in luminance than to
changes in chrominance. The luminance value y.sub.p of a color vector
C.sub.p is given by y.sub.p =a.sup.t C.sub.p, where for simplicity, the
value of a.sup.t may be chosen to be =[1/4, 1/2, 1/4] for the R,G,B
components, respectively (a higher weight is assigned to the green
component as this signal contains the highest luminosity). The calculation
is performed in block 36. A transformation may also be performed such as a
transformation y.sub.p.sup.' =T [y.sub.p ], where T is a predetermined
transform that may be used to reflect the different sensitivities of the
human observer at different luminance levels. The transformation T is
performed in box 38. An example of a piecewise linear transform that may
be used is shown in FIG. 4. This transform accentuates luminance
differences at mid-tone levels, and suppresses those at the very high and
low end. For ease of notation, in subsequent discussions, it will be
assumed that y.sub.p is the transformed luminance value. In order to
restrict the search for contours to smooth regions of the image, the
original image is divided into blocks of 8.times.8 pixels and an activity
measure .alpha..sub.k is assigned to an associative block k to be the mean
absolute deviation of luminance values in the block:
##EQU1##
wherein y.sub.k is the average luminance value in block k and the
summation is over all pixels in the block k. Block 40 computes
.alpha..sub.k. Contours are determined to exist only in blocks where
.alpha..sub.k is below some predefined threshold t.sub..alpha.. As
compared in decision block 42, if .alpha..sub.k is greater than or equal
to the threshold, the block k is not a smooth region. If .alpha..sub.k is
smaller than the threshold, the block k is a smooth region. This
eliminates searching for contours around edges and other busy areas. The
threshold t.sub..alpha. may be varied depending on how strict a smoothness
criterion one wishes to establish. For simplicity, a fixed activity
threshold may be selected by observing output images generated with
selected values of t.sub..alpha.. As a measure of contouring, a
determination is made as to the differences between the luminance
gradients of the original image and the quantized image. With the
existence of luminance gradient differences above a predetermined
magnitude, indicating the existence of a contour, the blocked system 46,
illustrated in detail in FIG. 5 may be used to generate the luminance
gradients and the luminance gradient differences. The quantized image
Q.sub.p is directed through a median filter 44 to provide the input to the
compute .gamma..sub.p block 46.
Referring to FIG. 5, the digitized original color image is applied to a
Sobel operator function block 50 which provides at its outputs the
absolute values .gradient.y.sub.H. and .gradient.y.sub.V which in turn are
summed in a summer 52. In a like fashion the quantized digital color image
is applied to the Sobel operator function block 50' and the summer 52'. A
differencer 54 determines the difference .gamma. between the outputs from
summer 52 and summer 52'. The following equation is implemented in the
blocked system of FIG. 5:
.gradient.y=.vertline..gradient.y.sub.H
.vertline.+.vertline..gradient.y.sub.V .vertline.
where .gradient.y.sub.H, and .gradient.y.sub.V are the outputs of the Sobel
operator in the horizontal and vertical directions respectively. The Sobel
operator is described in the text, "Digital Image Processing" authored by
R. C. Gonzalez, P. Wintz and published by Addison-Wesley, 1987. If
.gradient.y.sub.p.sup.Q and .gradient.y.sub.p.sup.C are denoted as the
gradients of the quantized and original images at location p respectively,
then we define a measure of contouring, .gamma..sub.p as:
.gamma..sub.p =.gradient.y.sub.p.sup.Q -.gradient.y.sub.p.sup.C
Since, in practice, the Sobel operator yields smooth gradients the contour
maps are smeared and not well defined. Also, the edge maps are in general
noisy because quantization sometimes introduces graininess in flat
regions, and this yields high values of .gamma..sub.p. In order to obtain
a more accurate and cleaner contour map the quantized image is filtered
with the median filter 44 before computing gradients. This has the effect
of removing any graininess introduced by quantization and yields thinner
contour edges. To further refine the contours, the values of .gamma..sub.p
that are below a predetermined contour threshold t.sub..gamma., are
discarded. The operation is performed in the decision block 48. Again, the
contour threshold may be varied depending on how selective one would like
to be. Finally, contours at locations where the gradient in the original
image is less than 4.0 are discarded (i.e. where the image is virtually
flat or in other words smooth). After obtaining the final contour map,
there is no longer any need for the original image. The subsequent
processing operates only on the quantized image.
Contour removal
The basic idea of this step is for the value of each pixel p in the window
of a contour pixel to be replaced with the value of pixel q as determined
by two N.times.N offset matrices D.sub.x and D.sub.y. If p is not in the
window of any contour pixel, its value is left unchanged. To illustrate
this algorithm, let the position of p=(i,j) be in the window of a contour
pixel. The offsets x and y are extracted from the offset matrices D.sub.x
and D.sub.y, wherein x=D.sub.x (i mod N, j mod N) and y=D.sub.y (i mod N,
j mod N) and wherein N is the size of the offset matrices. The position of
the pixel q is given by (i+x, j+y). The flow chart of FIG. 6 illustrates
these steps operating upon the pixel values from a quantized image with
each pixel value represented by Q'.sub.p (i,j) replaced by Q'.sub.q (i+x,
j+y). In the decision block 62 the pixel value is examined to determine if
it is within the contour window, if not, the pixel value is left alone as
per box 60 and the unaltered pixel is forwarded to be part of the new
image. If the pixel value is within the window of a contour the
calculations of block 64 are performed to obtain the offset values x and y
as stated in box 66. With the offset values determined, the value of
Q'.sub.q (i+x, j+y) is substituted for Q'.sub.p (i,j) as per block 68 to
form the new image.
Implementation
In the implementation of this algorithm, several parameters are obtained
heuristically by looking at their effects on images. The median filter
used was a three point one-dimensional median filter applied first in the
horizontal and then in the vertical direction. This filter is both
computationally simple to implement and effective in removing noise and
providing thinner contour edges. It is interesting to note that although
filtering improves the contour detection, it only marginally improves the
final quality of the image. Also, in practice, the extra time taken to
perform the filtering is offset by the time saved at the end due to the
filter reducing the number of contour regions to be examined.
In the contour removal algorithm there are three parameters that are to be
considered. The first is the size of the window. In the preferred
embodiment of the invention a window size of 3.times.3 is used. The larger
the window, the smoother the ramp will become. The second parameter is the
entries in the offset matrix. The range of -3 to +3 was used in the
implementation. As an observation the larger the range of the entries, the
smoother the ramp will become. The third parameter is the size of the
offset matrices. The preferred embodiment used two 4.times.4 matrices in
the initial implementation. The larger the offset matrices, the less
structure there will be in the resulting image.
Appendix A is a listing of the computer programs that were used to
implement the invention. The contour detection program was run on a SUN
workstation with UNIX and the pixel replacement program was run on a MAC
IIci personal computer. Although a computer system is not shown in the
Drawings, for purpose of simplicity, it is understood that the present
invention requires a computer in order to perform the functional steps of
processing digital images with any speed that would have commercial value.
Results and Discussion
One of the advantages of the present approach is that since the method is
only performed around contours in smooth regions, the images do not suffer
a loss in spatial detail around edges and other busy regions. The
algorithm imposes no restrictions on the structure of the palette, since
no nearest neighbor searches in the color space are necessary. Finally,
unlike error diffusion, the present process is memoryless, and hence, it
is possible to select a desired portion of the image and apply the
rendering algorithm to it without introducing a patchy effect, as might be
the case with error diffusion when applied only to a portion of the image.
Since processing a small portion of the image is clearly faster than
processing the entire image, this could be useful from the standpoint of a
practical rendering application.
While there has been shown what is considered to be the preferred
embodiments of the invention, it will be manifested that many changes and
modifications may be made therein without departing from the essential
spirit of the invention.
##SPC1##
* * * * *
|
|
|
|
|
|
|
Description |
|
