Back to EveryPatent.com
United States Patent |
5,333,260
|
Ulichney
|
July 26, 1994
|
Imaging system with multilevel dithering using bit shifter
Abstract
Disclosed is an image processing system which relies upon quantization and
dithering techniques to enable an output device, which has a given number
of output levels, to accurately reproduce a image which is generated by an
input device, which has a greater or equal number of input levels.
Generally, neither the number of input nor output levels need to be a
power of two. The present invention is implemented in a number of
different embodiments. These embodiments generally rely upon an image
processor which, depending on the particular implementation, includes
memory devices and an adder, a comparator, or a bit shifter. Additional
embodiments use an image adjustment system to refine the raw input levels
of the input device, in order to create an improved output image. Also,
the particular embodiments of the image processors can be used in
connection with imaging systems having hi-tonal, monochromatic, or color
input and output devices.
Inventors:
|
Ulichney; Robert A. (Stow, MA)
|
Assignee:
|
Digital Equipment Corporation (Maynard, MA)
|
Appl. No.:
|
961601 |
Filed:
|
October 15, 1992 |
Current U.S. Class: |
358/448 |
Intern'l Class: |
G06F 015/20 |
Field of Search: |
395/128,132,138,162-166,109,115,116
364/DIG. 1,DIG. 2
358/443,444,447,448,455-458,450
382/49,50,54,56
345/147,149,185,155,199-201,153
|
References Cited
U.S. Patent Documents
H996 | Nov., 1991 | McWaters et al. | 345/149.
|
4835599 | May., 1989 | Sigel | 358/30.
|
4975786 | Dec., 1990 | Katayama et al. | 358/457.
|
4975861 | Dec., 1990 | Fujimoto | 345/199.
|
5014333 | May., 1991 | Miller | 358/466.
|
5130701 | Jul., 1992 | White et al. | 345/199.
|
5170152 | Dec., 1992 | Taylor | 345/155.
|
Other References
Stuart C. Wells, Grant J. Williamson, Susan E. Carrie "Dithering for 12-Bit
True-Color Graphics", IEEE Computer Graphics & Applications. Sep. 1991,
pp. 18-29.
Frattarola, G. and S. Edelson, "Images as Opcodes", Edsun Laboratories,
1990, pp. 1-14.
Glass, L. B., "Digital Video Interactive", BYTE, May 1989, pp. 283-289.
Luther, Arch, Digital Video in the PC Environment, New York: Intertext
Publications, McGraw-Hill, 1989, pp. 192-195.
Sigel, C., R. Abruzzi, J. Munson, "Chromatic Subsampling for Display of
Color Images", Digital Equipment Corporation Albuquerque, N.M. 1989, pp.
158-161.
Wan, S. J., K. M. Wong, and P. Prumsinkiewicz, "An Algorithm for
Multidimenmsional Data Clustering", ACM Trans. on Math. Software, Jun.
1988, vol. 14, No. 2, pp. 153-162.
Heckbert, P. S., "Color Image Quantization for Frame Buffer, Display",
Computer Graphics, Jul. 1982, vol. 16, No. 3, pp. 297-307.
Ulichney, R., Digital Halftoning, MIT Press, 1987, Ch., 6 & 8, pp. 340 &
341.
Ulichney, R. "Imaging System with Multilevel Dithering Using Two Memories",
Patent Application, Attorney Docket #PD92-0026, Oct. 1992, 179 pages.
Ulichney, R. "Imaging System With Two Level Dithering Using Comparator",
Patent Application, Attorney Docket #PD93-0076, Oct. 1992, 176 pages.
Ulichney, R., Bahl, P., "Imaging System With Multilevel Dithering Using
Single Memoryu", Patent Application, Attorney Docket #PD93-0077, Oct.
1992, 181 pages.
Ulichney, R., "Imaging System With Image Adjustment System", Patent
Application, Attorney Docket #PD93-0079, Oct. 1992, 180 pages.
Ulichney, R., "Void and Cluster Apparatus and Method for Creating Dither
Templates", Patent Application, Attorney Docket #PD92-0295, Oct. 1992.
Lawrence, Gilman, Roberts, "Picture Coding Using Pseudo-Random Noise", IRE
Transactions on Information Theory, Feb. 1962, pp. 145-154.
|
Primary Examiner: Shaw; Dale M.
Assistant Examiner: Tung; Kee M.
Attorney, Agent or Firm: Cefalo; Albert P., Hudgens; Ronald C., Young; Barry N.
Claims
What is claimed is:
1. An apparatus for translating input levels of an imaging system to
corresponding output levels, said apparatus comprising:
memory means for storing dither template values, said memory means being
responsive to an address of an input cell of an input device to provide a
dither template value which corresponds to the address of the input cell;
means for adding an input level of the input cell to the dither template
value provided by said memory means to provide a sum (S), said adding
means producing a finite number of unique S values which map to a single,
given output level;
shifter means for bit shifting the S value provided by said adding means;
and
both the number of input levels and the number of output levels produced by
the imaging system being any number, provided the number of input levels
in equal to or greater than the number of output levels, and further
provided that an average number of unique S values, determined by
averaging the number of unique S values which map to each of the given
output levels, is equal to an integer power of two.
2. The apparatus as in claim 1, wherein the dither template values are
normalized by symmetrically distributing the dither template values
between 0 and the average number of unique S values.
3. The apparatus as in claim 2, wherein the normalized dither template
values (D<x',y'>) are related to a number of input levels (NIL); a number
of output levels (NOL); a .DELTA..sub.Q ; a .DELTA..sub.d ; a dither
template (T<x',y'>); and a number of template levels of the imaging system
(NTL) by:
.DELTA..sub.Q =(NIL-1)/(NOL-1);
.DELTA..sub.d =.DELTA..sub.Q /(NTL); and
D<x',y'>=int {.DELTA..sub.d (T<x',y'>)+0.5}.
4. The apparatus as in claim 3, wherein the dither template values are
phase adjusted by spatially shifting the values within the dither
template.
5. The apparatus as in claim 4, wherein the phase adjusted dither template
values (d<x',y'>) are related to a number of input levels (NIL); a number
of output levels (NOL); a .DELTA..sub.Q ; a .DELTA..sub.d ; a dither
template (T<x',y'>); a number of template levels of the imaging system
(NTL); a phase value of the x,y address of an input cell (phase.sub.-- x,
phase.sub.-- y); and the dimensions of said memory means (M.sub.mm,
N.sub.mm) by:
.DELTA..sub.Q =(NIL-1)/(NOL-1);
.DELTA..sub.d =.DELTA..sub.Q /(NTL);
D<x',y'>=int {.DELTA..sub.d (T<x',y'>)+0.5}; and
d<x',y'>=D<(x'+phase.sub.-- x)modulo(M.sub.mm), (y'+phase.sub.-
y)modulo(N.sub.mm)>.
6. The apparatus as in claim 1, wherein said shifter means shifts the S
value R bits to the right, where
R=int{log.sub.2 (2.sup.B -1)/(NOL-1)};
B=the number of bits of the input level; and
NOL=the number of output levels.
7. An apparatus for translating input levels of an imaging system to
corresponding output levels, said apparatus comprising:
Look Up Table (LUT) generator means for generating dither template values
for the input levels of an imaging system;
memory means for storing the dither template values generated by the LUT
generator means, said memory means being responsive to an address of an
input cell of an input device to provide a dither template value which
corresponds to the address of the input cell;
means for adding an input level of the input cell to the dither template
value provided by said memory means to provide a sum (S), said adding
means producing a finite number of unique S values which map to a single,
given output level;
shifter means for bit shifting the S value provided by said adding means;
and
both the number of input levels and the number of output levels produced by
the imaging system being any number, provided the number of input levels
is equal to or greater than the number of output levels, and further
provided that an average number of unique S values, determined by
averaging the number of unique S values which map to each of the given
output levels, is equal to an integer power of two.
8. The apparatus as in claim 7, wherein the dither template values are
normalized by symmetrically distributing the dither template values
between 0 and the average number of unique S values.
9. The apparatus as in claim 8, wherein the dither template values are
phase adjusted by spatially shifting the values within the dither
template.
10. An apparatus as in claim 9, further comprising an image adjustment
system, said image adjustment system being responsive to a raw input level
produced by an input device to provide an input level to said adding
means.
11. The apparatus as in claim 7, wherein said shifter means shifts the S
value R bits to the right, where
R=int {log.sub.2 (2.sup.B -1)/(NOL-1)};
B=the number of bits of the input level; and
NOL=the number of output levels.
12. An imaging system comprising:
an input device for producing input levels;
an output device for producing output levels;
an image processor, coupled between said input and output devices, for
translating the input levels to corresponding output levels, said image
processor including:
Look Up Table (LUT) generator means for generating dither template value
for the input levels of an imaging system;
memory means for storing the dither template values generated by the LUT
generator means, said memory means being responsive to an address of an
input cell of an input device to provide a dither template value which
corresponds to the address of the input cell;
means for adding an input level of the input cell to the dither template
value provided by said memory means to provide a sum (S), said adding
means producing a finite number of unique S values which map to a single,
given output levels;
shifter means for bit shifting the S value provided by the adding means;
and
both the number of input levels and the number of output levels produced by
the imaging system being any number, provided the number of input levels
is equal to or greater than the number of output levels, and further
provided that an average number of unique S values, determined by
averaging the number of unique S values which map to each of the given
output levels, is equal to an integer power of two.
13. The imaging system as in claim 12, wherein the dither template values
are normalized by symmetrically distributing the dither template values
between 0 and the average number of unique S values.
14. The imaging system as in claim 13, wherein the dither template values
are phase adjusted by spatially shifting the values within the dither
template.
15. The imaging system as in claim 12, further comprising a second image
processor, and wherein the input levels of the input device are components
of a color system.
16. A method of translating input levels of an imaging system to output
levels, said method comprising the steps of:
generating dither template values for the output levels of an imaging
system;
storing the dither template values in a memory means, said memory means
being responsive to an address of an input cell of an input device to
provide a dither template value which corresponds to the address of the
input cell;
adding the dither template value output by a memory means in response to an
address of the input cell to an input level of the input cell to produce a
sum (S), said adding step being accomplished with an adding means which
produces a finite number of unique S values which map to a single given
output level; and
bit shifting the S value to produce an output level for an output device,
both the number of input levels and the number of output levels produced
by the imaging system being any number, provided the number of input
levels is equal to or greater than the number of output levels, and
further provided that an average number of unique S values, determined by
averaging the number of unique values which map to each of the given
output levels, is equal to an integer power of two.
17. The method as in claim 16, wherein said generating step includes:
normalizing the dither template values by distributing the dither template
values between 0 and the average number of unique S values.
18. The method as in claim 17, wherein said generating step includes:
phase adjusting the dither template values by spatially shifting the values
within the dither template.
19. The method as in claim 16, wherein said shifting step includes shifting
the S value R bits to the right, where
R=int{log.sub.2 (2.sup.B -1)/(NOL-1)};
B=the number of bits of the input level; and
NOL=the number of output levels.
Description
FIELD OF THE INVENTION
This invention relates to an apparatus and method for translating an input
image to an output image in an imaging system using quantization and
dithering techniques.
BACKGROUND OF THE INVENTION
As is known in the art, an image processing system is often used to
translate and feed input signals representative of an image in an input
device to output signals representative of that same image in an output
image. For example, a video camera may register a given input image, which
is subsequently transferred to an output device, such as a video screen,
or a printer. Often the input device may have a greater capacity to
represent the different colors or gray scale shades of the input image
than the output device. If the input device can represent more colors than
the output device, an image processing system may be employed for
converting the greater number of input colors to a lesser number of output
colors, to make the output image appear as visually similar to the input
image as possible. Four such methods of converting input images to output
images are 1) histogram based methods, 2) chrominance subsampling, 3)
hardware color mixing, and 4) dithering.
With a histogram based technique, a processor is used to collect histogram
statistics on the input image data, and the statistical information is
used to compensate the image data. Thus, the histogram technique requires
two passes of the entire input image data; the first to acquire the
histogram statistics and the second to compensate the data. This results
in a system which has the drawback of being too slow for those
applications in which speed is important. In addition, in cases where the
colors change gradually over a wide area, considerable contouring of the
image can occur, resulting in a less desirable output image.
Chrominance subsampling, on the other hand, typically requires specialized
hardware, such as unconventional frame buffers and very fast and expensive
upscaling and color space conversion hardware. Due to the unique hardware
requirements of the chrominance subsampling technique, it is not practical
to implement in a general computing environment. In addition, the image
quality suffers in areas of high chrominance detail.
The third technique, hardware color mixing, requires that the image data
must be preprocessed off line with a multiple pass algorithm. Thus, like
the histogram based technique, this approach is also slow. Additionally,
the resulting image file is device dependent, resulting in the requirement
of unique hardware, a drawback similar to that of the chrominance
subsampling technique.
The fourth technique for converting the greater number of input colors to a
lesser number of output colors, dithering, is based on using the available
set of output colors in a judicious arrangement so that the illusion of a
greater number of output colors is provided. Additionally, the arrangement
of the output colors through the dithering technique is designed to assure
that a pleasing output image is produced.
One such dithering technique is reported in Ulichney, R. "Digital
Halftoning". The MIT Press (1987), hereinafter referred to as "Ulichney".
In Ulichney, equation 9.5 provides the following:
I.sub.k <x,y>=<1/(2.sup.k -1)><int}<(2.sup.k -1) J<x,y>>+D<x,y>}>
where:
I.sub.k <x,y> is the output value of the image at position x,y of the
output image;
K is the number of bits used to represent the output value I<x,y>;
J<x,y> is the input value of the image at position x,y of the input image,
normalized to a range between 0 and 1;
D<x,y> is the dither matrix value at position x,y of the dither matrix,
normalized to a range between 0 and 1;
int{x} is a truncate function in which after any mathematical operations
within the brackets are performed and a final value is determined, any
amount remaining after the decimal point is truncated so that the
remaining value is an integer. For example, int{5.3}=5, and
int{27,999}=27;
One drawback to this dithering approach is that the equation only permits
dithering to powers of 2, rather than any number. Also, the equation
requires that the input must be scaled to a range between 0 and 1, but
does not give any indication of how that scaling is to be done, or how the
values of the dither matrix are to be spaced to achieve symmetric
dithering.
SUMMARY OF THE INVENTION
This invention relates to an apparatus and method for processing images in
an imaging system, which translates the input levels of an input device to
corresponding output levels of an output device. The image processing
apparatus includes a memory device for storing dither template values. The
memory device is responsive to an x,y address of a given input cell of the
input device, such that the address causes the memory device to output a
stored, dither template value which corresponds to the address of the
input cell.
The image processor apparatus further includes an adder. The adder adds the
given dither template value, output by the memory device, to the actual
input level of the given input cell to produce a sum (S). That S value is
then bit shifted by a shifter device, and the bit shifted result is
provided by the image processor to the output device of the imaging system
as the output level which corresponds to the input level.
In accordance with the invention, both the number of input levels and the
number of output levels of the imaging system may be any number, provided
the number of input levels is equal to or greater than the number of
output levels, and further provided that the average number of unique S
values that map to a single output level is equal to an integer power of
two.
Alternate embodiments of the invention include an image processing system
which includes the image processor using the memory device, the adder, and
the bit shifter. Yet another embodiment of the invention includes the
method of processing input and output levels using the memory device, the
adder, and the bit shifter.
One advantage of the invention is that any number of input levels and
output levels can be used, provided that the number of input levels is
equal to or greater than the number of output levels, and further provided
that the average number of unique S values that map to a single output
level is equal to an integer power of two.
Another advantage of the invention is that the implementation of the
invention is accomplished with commonly available computer hardware; no
specialized hardware is required. In one embodiment, the image processor
uses only the memory device, the adder, and the shifter.
Yet another advantage of the invention is that the apparatus operates very
fast, insofar as the production of the corresponding output level by the
image processing apparatus requires the memory look up, the addition, and
the bit shifting to translate the input levels to output levels.
Other objects, features, and advantages of the present invention will be
further appreciated and better understood upon consideration of the
following detailed description of the preferred embodiments, presented in
conjunction with the accompanying drawings.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram illustration of an imaging system, in accordance
with an embodiment of the present invention, including an input device, an
image processor, and an output device.
FIG. 2A is a graph showing one method of quantizing input levels with
respect to output levels.
FIG. 2B is a graph showing a method of quantizing input levels with respect
to output levels which is in accordance with an embodiment of the present
invention.
FIGS. 3A-3G illustrate a number of dither templates of varying sizes and
levels.
FIG. 4 includes two, correlated graphs showing a number of input levels
mapped to two output levels.
FIG. 5 includes two, correlated graphs showing a number of input levels
mapped to four output levels.
FIG. 6 is a block diagram of the image processor of FIG. 1, including a LUT
generator and a two memory run time system (TMRTS).
FIG. 7 is a block diagram of the LUT generator shown on FIG. 6, coupled to
a quantizer LUT and a dither template memory.
FIG. 8 is a flow diagram describing the process by which quantized values
and dither template values are produced by the quantizer LUT of FIGS. 6
and 7.
FIGS. 9A-9C show the modification of the dither template values of a
particular dither template as it is processed through the quantizer LUT of
FIGS. 6 and 7.
FIG. 10 is a flow diagram describing the process by which input levels are
used by the image processor of FIG. 6 to produce corresponding output
levels.
FIG. 11 is a table of exemplary input levels processed by the image
processor of FIG. 6, and their corresponding total number of perceived
output levels, and an indication whether the given, perceived output level
is a true level, or a dithered average.
FIG. 12 is a block diagram of an alternate embodiment of an image
processor, in accordance with the present invention, which includes a LUT
generator and a comparator run time system (CRTS).
FIG. 13 is a flow diagram describing the process by which dither template
values are produced by the quantizer LUT of FIG. 12.
FIG. 14 is a flow diagram describing the process by which input levels are
used by the image processor of FIG. 12 to produce corresponding output
levels.
FIG. 15 is a block diagram of yet another alternate embodiment of an image
processor, in accordance with the present invention, which includes a LUT
generator, an address/level generator, a single memory table value
determiner (SMTVD), and a single memory run time system (SMRTS).
FIG. 16 is flow diagram describing the process by which quantized values
and dither template values are produced by the quantizer LUT of FIG. 15.
FIG. 17 is a block diagram of the address/level generator shown in FIG. 15.
FIG. 18 is a flow diagram describing the process by which input levels are
used by the image processor of FIG. 15 to produce corresponding output
levels. D FIG. 19 is a block diagram of still another alternate embodiment
of an image processor, in accordance with the present invention, including
a system data generator and a bit shifter run time system (BSRTS).
FIG. 20 is a block diagram of the system data generator shown on FIG. 19
coupled to a shifter and a dither template memory.
FIG. 21 is flow diagram describing the process by which an R value, an NIL
value, and dither template values are produced by the system data
generator of FIGS. 19 and 20.
FIGS. 22A-22C show the modification of the dither template values of a
particular dither template as it is processed through the system data
generator of FIGS. 19 and 20.
FIG. 23 is a flow diagram describing the process by which input levels are
used by the image processor of FIG. 19 to produce corresponding output
levels.
FIG. 24 is a table of exemplary input levels processed by the image
processor of FIG. 19, and their corresponding total number of outputs,
perceived output levels, and an indication whether that perceived output
is a true level, or a dithered average.
FIG. 25 is an imaging system, similar to the one in FIG. 1 and in
accordance with the present invention, including within the image
processor an image adjustment system.
FIG. 26 is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing the
identity transform function.
FIG. 27 is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing multiple
transform lines for the purpose of defining the variable "Steepness".
FIG. 28 is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing a
particular example of the Steepness variable, as well as defining the
variables "Top", "Low", and "High".
FIG. 29A is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing multiple
transform lines for the purpose of defining the variable "Xoffset".
FIG. 29B is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing a
particular example of the Xoffset variable.
FIG. 30A is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing multiple
transform lines for the purpose of defining the variable "Yoffset".
FIG. 30B is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing a
particular example of the Yoffset variable.
FIG. 31 is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing two
transform lines for the purpose of defining the variable "ReverseIn".
FIG. 32 is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing two
transform lines for the purpose of defining the variable "ReverseOut".
FIG. 33 is a table of exemplary values showing a two's-compliment
representation, a binary code, an unsigned interpretation, and a shifted
representation.
FIG. 34 is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing a
transform line for defining the variable "Sign Shift".
FIG. 35 is a graphical illustration of the adjustment of raw input levels
to adjusted input levels by an image adjustment system, showing a
transform line which illustrates the adjustment of a given number of raw
input levels to a lesser number of adjusted input levels.
FIG. 36 is a block diagram of the image processor of FIG. 25, showing a
variables determiner, data assignor, data store, sign converter, and an
adjust LUT.
FIG. 37 is a flow diagram illustrating the process by which the variables
determiner of FIG. 36 computes the variables "b", "m", "High", "Low", and
"Top".
FIG. 38 is a flow diagram illustrating the process by which the data
assignor of FIG. 37 generates the adjusted raw input levels and stores
them in the data store of FIG. 37.
FIG. 39 is a flow diagram illustrating the process by which the sign
convertor of FIG. 37 generates adjusted input levels and stores them in
the adjust LUT of FIG. 37.
FIGS. 40A-40D are alternate embodiments of the image processors shown in
FIGS. 6, 12, 15 and 19, respectively, each such image processor including
an image adjustment system in accordance with the present invention.
FIG. 41 is a block diagram of an imaging system, in accordance with an
embodiment of the present invention, including an input device coupled to
an output device through multiple image processors.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
A. General
FIG. 1 presents a block diagram illustration of the general environment in
which one embodiment of the image processing apparatus and technique of
the present invention is applied. Imaging system 20 includes input device
22 which has an input image array 24 with a dimension M.sub.in
.times.N.sub.in. Input array 24 is made up of a number of individual input
cells 26, represented by the small rectangles of input array 24, and each
such input cell 26 is addressable by an x.sub.in (column) and y.sub.in
(row) coordinate.
Still referring to FIG. 1, imaging system 20 also includes output device
30, which likewise has an output image array 32 having dimensions
M.sub.out .times.N.sub.out. Also, output array 32 is made up of a number
of individual output cells 34, represented by the small rectangles within
output array 32, and each such output cell 34 is addressable by an
x.sub.out (column) and y.sub.out (row) coordinate.
In this detailed description, a number of input and output devices will be
discussed. First, an input or output device may be one which is capable of
producing only a bi-tonal image. By definition, a bi-tonal image is one in
which there is only one component for representing the image, and that
component has only two shades. Typically the shades are black and white,
though they need not be.
Second, an input or output device may be a monochrome device, which is
characterized by having one component used for defining the luminance of
the image. This type of system may have black and white shades, as well as
intermediate shades of a gray.
Third, an input or output device may classified as color system, a
classification which can be further divided into two sub groups. The first
sub group is made up of luminance/chrominance systems, which have one
component which defines the luminance of the image, and two components
which together define the characteristics of the hue and saturation of the
image. The second sub group of color systems are so-called "RGB" systems,
representing the color primaries, red, green, blue. In such a system there
is a first component which defines the amount of red of the image, a
second component defining the amount of green, and a third component
defining the amount of blue. Together these three components define the
luminance and chrominance of the image.
It should be noted that in imaging systems generally it is possible to
couple one type of input device with a different type of output device. In
other words, a luminance/chrominance type color input device may be
coupled to an RGB type output device, for example. Techniques for
modifying the data, which is in one format in the input device, for
presentation in a different format in the output device are shown in U.S.
Patent Application of Robert Ulichney, entitled "Method and Apparatus for
Mapping a Digital Color Image From a First Color Space to a Second Color
Space", filed on Jun. 26, 1990 and having the Ser. No. 07/545,384, now
U.S. Pat. No. 5,233,684, which is hereby incorporated by reference.
Referring back to FIG. 1, input cells 26 and output cells 34 are the cells
in which the black and white, gray scale shades, and colors of the input
or output images are represented. However, having noted the different
types of input and output devices, in order to discuss these devices
generally, it is convenient to use the term "level" in place of the use of
the terms "black and white", "gray scale shades", or "colors". Thus,
except where the discussion requires distinction, this detailed
description shall use the term "level(s)" to identify the input or output
images of bi-tonal, monochrome, or color systems.
The input levels of input device 22 are designated "IL", where IL can range
from 0 to <the number of input levels ("NIL") -1>Likewise each output cell
34 is capable of outputting a level which is designated "OL", where OL can
range from 0 to <the number of output levels ("NOL") -1>.
In a particular implementation of the multi-level imaging system of the
present invention, input device 22 could be a video camera, which detects
an image. That image is registered in input array 24, with the IL of each
input cell 26 being represented by "IL<x,y>", where IL<x,y> is the input
level at a particular x.sub.in, y.sub.in address in input array 24. In
such an application, input cells 26 are the individual pixels of the input
image. In this same implementation, output device 30 could be a video
monitor in which output cells 34 of output array 32 represent the output
pixels of the video screen on which the input image is viewed. That image
is represented in output array 32, with the OL of each output cell 34
being represented by "OL<x,y>", where OL<x,y> is the output level at a
particular x.sub.out, y.sub.out address in the array. Likewise output
cells 34 are the individual output pixels of the output image.
Still referring to FIG. 1, the dimensions of input array 24, M.sub.in X
N.sub.in, and the output array 32, M.sub.out .times.N.sub.out, are
identical. Accordingly, there is a one to one correspondence between each
input cell 26 and each output cell 34. Although in some imaging systems
the input images may be initially registered into an input array, the
dimensions of which are different than the dimensions of the output array,
there are known cropping and scaling techniques which can be used to alter
the input image so that the dimensions of the input and output arrays are
identical. Accordingly, the application of the embodiment of the present
invention is in an environment in which the size of M.sub.in
.times.N.sub.in is the same as the size of M.sub.out .times.N.sub.out.
Additionally the input address, x.sub.in, y.sub.in is the same as the
output address x.sub.out,y.sub.out, and will hereinafter simply be
referred to as x,y.
The multi-level image processing system of the present invention is
typically applied in an environment in which the NOL is fewer than the
NIL; however, it may also be applied in an environment in which NOL is
equal to NIL. In those instances in which NIL is greater than NOL, the
purpose of the system is to map the greater NIL to the lesser NOL. Except
with respect to certain embodiments of the invention discussed below,
neither NIL nor NOL need to be a power of 2. This affords the imaging
system with a greater degree of flexibility.
To accomplish the mapping of input levels to output levels, input device 22
is coupled to output device 30 through image processor (IP) 40, which
translates all IL<x,y> values to corresponding OL<x,y> values. This
translation involves quantization and dither templates, both of which will
be further discussed below. Before focusing upon a specific embodiment of
the invention, it is helpful to first consider how an image processor,
such as IP 40, can generally map input levels to output levels.
Referring to FIG. 2A, a graph having any number of input levels, IL, and 4
output levels is provided. In this example, the smallest output level,
OL=0, is mapped directly to the smallest input level, which on the graph
is designated 0.DELTA..sub.Q. Additionally, the largest output level,
OL=3, is mapped directly to the largest input level, which on the graph is
designated 3.DELTA..sub.Q. By virtue of the direct mapping of smallest to
smallest and largest to largest, there are no input levels less than
0.DELTA..sub.Q that also map to OL=0, and no input levels greater than
3.DELTA..sub.Q that map to also map to OL=3. Having made this assignment
at the two extremes of the graph, the interior portion of the axis on
which the input levels are graphed is then evenly divided by
1.DELTA..sub.Q and 2.DELTA..sub.Q, with 1.DELTA..sub.Q being assigned a
direct mapping to OL=1 and 2.DELTA..sub.Q being assigned a direct mapping
to OL=2.
Moreover, in the quantization approach shown in FIG. 2A, when determining
the input levels which are mapped to a given output level, there is no
adjustment of the NIL and NOL by any factor in order to provide an even
distribution so that all input levels are mapped to their closest output
level. Rather, quantization is achieved by simply dividing NIL by NOL.
Accordingly, each range of input levels mapped to a given output level is
equal, and in this instance those ranges are equal to NIL/4 as shown on
the graph.
Although it may appear that this quantizer approach is symmetric, because
all ranges of input levels are equal, the approach will actually result in
quantization error, because certain input levels will not necessarily be
mapped to their closest assigned output level. For example, referring to
IL.sub.(a) it would be mapped to OL=0, even though it is apparent from the
graph that it is actually closer to 1.DELTA..sub.Q, which is the input
level assigned to OL=1. Likewise, referring to IL.sub.(b) it would be
mapped to OL=3, even though it closer to 2.DELTA..sub.Q, which is the
input level assigned to OL=2.
Thus this straight quantization approach, in which the number of input
levels which are mapped to a given output level is determined by a direct
division of NIL by NOL, provides an uneven distribution of input levels
around the assigned output levels resulting in quantization error. An
imaging system based on this quantization error will produce a less
desirable output image than one which evenly distributes the input levels
around the assigned output levels. The image processing system of the
present invention does evenly distribute the input levels around the
assigned output levels to reduce the quantization error.
Referring to FIG. 2B for a general description of the method by which this
is done, a graph is provided in the same basic format as shown in FIG. 2A.
In FIG. 2B, the smallest output level, OL=0, is mapped directly to the
smallest input level, which on the graph is designated 0.DELTA..sub.Q, and
the largest output level, OL=3, is mapped directly to the largest input
levels the axis is evenly divided by 1.DELTA..sub.Q and 2.DELTA..sub.Q,
with 1.DELTA..sub.Q assigned to OL=1 and 2.DELTA..sub.Q assigned to OL=2.
Unlike the approach taken in connection with FIG. 2A, the image processing
technique of the present invention adjusts the NIL and NOL by a factor
that eliminates the quantization error and provides an even distribution
of input levels with respect to output levels. In this approach, NIL and
NOL are both reduced by one before the division which determines the
number of input levels which are mapped to a given output level.
Accordingly, quantization is accomplished by first calculating
.DELTA..sub.Q, where:
.DELTA..sub.Q =(NIL-1)(NOL-1) (Equation I).
Through this equation, .DELTA..sub.Q =(NIL-1) / (4-1)=(NIL-1)/3, in the
given example.
Next, the image processing technique refines the distribution of the input
levels which appear at either end of the x axis, so that there is symmetry
of all input levels around their related .DELTA..sub.Q assignment,
0.DELTA..sub.Q through 3.DELTA..sub.Q. This is accomplished by dividing
.DELTA..sub.Q in half, and using that quotient to determine the span of
the first and last range of input levels which are mapped to the smallest
and largest output levels, respectively. In between the two end ranges,
.DELTA..sub.Q determines the span of the range of input levels which are
mapped to output levels falling between the smallest and largest output
levels.
Supposing, for example that the NOL in FIG. 2B was 256. Using Equation I,
.DELTA..sub.Q is equal to (256-1)/(4-1), or 85. Thus, in FIG. 2B, the
resulting mapping of input levels to output levels would be:
TABLE A
______________________________________
IL OL
______________________________________
0 through 42
maps to 0
43 through 127
maps to 1
128 through 212
maps to 2
213 through 255
maps to 3
______________________________________
As seen from Table A with NIL=256, IL can range from 0 through 255; and
with NOL=4, OL can range from 0 through 3. Also in Table A it can be seen
that .DELTA..sub.Q /2, or 85/2=42.5, determines the span of input levels,
rounding to 43, that are mapped to the smallest output level, namely 0
through 42 map to OL=0. In between this first range and the last range,
which is 213 through 255, are spans of input levels which are equal to
.DELTA..sub.Q, such as 43 through 127 being mapped to OL=1 and 128 through
212 being mapped to OL=2. In this respect, the value of .DELTA..sub.Q will
determine the range of input levels which are covered by any given output
level, except that at the ends of the full range of input levels, the
number of levels covered is equal to .DELTA. .sub.Q /2, as shown in graph
segments 42 and 44 of FIG. 2B.
This adjustment of NIL and NOL before quantization provides a symmetric
distribution of input levels around their respective output levels. As
shown in FIG. 2B, IL.sub.(a), which is in the same
position on the graph as it is on FIG. 2A, is mapped to OL=1 because it is
closer to 1.DELTA..sub.Q, which is assigned to OL=1. Likewise, IL.sub.(b),
is mapped to OL=2 given that it is closer to 2.DELTA..sub.Q, which is
assigned to OL=2. Accordingly, the quantization technique assures both
that there is a direct mapping of the smallest output level to the
smallest input level, and the largest output level to the largest input
level, and that there is a symmetric distribution of the input levels
around the closest assigned output level.
Thus far the multi-level, image processing technique of the present
invention has relied upon a quantization method for mapping a greater
number of input levels to the lesser number of output levels. The
technique of the present invention further combines quantization with the
use of a dither template so that even though output device 30 can only
output a given number of "true" levels, output device 30 provides the
illusion that it is capable of outputting "intermediate" levels, as well
as the true levels. The meaning of "true" and "intermediate" levels will
be further discussed below.
Referring now to FIGS. 3A through 3F, a number of dither templates are
illustrated. A dither template is a grouping of elements arranged in a
particular order, with each such element being taken from the set of whole
numbers that range from 0 to <the number of template levels ("NTL")-1>.
Each such template can be defined by reference to: its size, which is
given as an M.sub.tmp .times.N.sub.tmp array; its NTL; and the order of
elements in the array. For example, referring to FIG. 3C, the size of the
array is M.sub.tmp =N.sub.tmp =4, which is a 4.times.4 array. The NTL is
8, meaning that the value of the elements in the array range from 0
through <8-1>, or 0 through 7. And the order of the elements is as shown
in FIG. 3A. "T<x',y'>" will hereinafter be used as the term which defines
a given dither template by reference to the order of its elements,
understanding that once the order of the elements is known the M.sub.tmp
.times.N.sub.tmp size and the NTL can be easily determined by reference to
the row-column arrangement and the actual value of the elements.
Although a given dither template has a certain M.sub.tmp .times.N.sub.tmp
size array, in many instances it is possible to map that array into a
larger memory array, M.sub.mm .times.N.sub.mm, by "tiling", or repeating,
the smaller template pattern across the larger memory array. For example,
FIG. 3B includes a dither template having a size M.sub.tmp =N.sub.tmp =2,
NIL=4, with the elements ordered as shown. Even though this template is
arranged as a 2.times.2 it can be mapped into a larger memory array, such
as an 8.times.8 array. Referring now to FIG. 3G, it can be seen how the
smaller, 2.times.2 dither template of FIG. 3B is tiled into the larger
8.times.8 memory array so that the larger array preserves the basic dither
template pattern.
It should be noted that one limitation to the ability to tile a smaller
dither template into a larger dither template memory is that the size of
the dither template must divide evenly into the size of the dither
template memory. Stated differently, M.sub.mm must be evenly divisible by
M.sub.tmp and N.sub.mm must be evenly divisible by N.sub.tmp. For example,
the 2.times.2 template evenly divides into the 8.times.8 memory array;
however, a 3.times.3 template would not. The significance of tiling the
dither pattern into a larger memory array will be discussed below.
Finally with respect to dither templates, it should also be noted that the
term "T<x',y'>" will be used to define not only the order of an original,
small, dither template, but also the order of a dither template which is
the result of tiling the small dither template into a larger memory array.
Having discussed quantization and dither templates, it can now be shown how
these two techniques are combined in image processor 40 to provide the
visual impression that output device 30, shown in FIG. 1, is able to
output a greater number of output levels than it actually can. In other
words, through the image processing technique, output device 30 can
produce the illusion that it can output more levels than simply the "true"
levels that it is actually capable of outputting. In this manner, output
device 30 can render an output image which is closer in fidelity to the
original input image. Furthermore, output devices employing the image
processing technique will produce a more visually pleasing output image.
Referring now to FIG. 4, quantization and dither templates are combined to
produce perceived output levels using dither template 50 where M=N=2 and
NTL=4 is used. In FIG. 4 are two graphs, Graph 53 and Graph 54, each
having the x axis segment including a number of input levels ranging from
IL.sub.a through IL.sub.b. The y axis segment includes two output levels,
OL.sub.a and OL.sub.b. For the purpose of this example, it is assumed that
OL.sub.a is dark gray, and OL.sub.b is light gray, in which case OL.sub.a
and OL.sub.b are defined as the two, true, output levels which output
device 30 is capable of providing. However, it will be clear to those
skilled in the art that OL.sub.a and OL.sub.b can be any levels, and that
dark gray and light gray are used here only to provide a simple example of
how the multi-level image processing technique works.
Included also in FIG. 4 are representations of five different dither
patterns, 52a through 52e, that can be achieved using the two input levels
and dither template 50. Even though output device 30 can only output two
levels, through shading the individual cells with dark gray or light gray
in a pattern which is determined by the dither template, intermediate
levels are effectively produced. In other words, even though output device
30 can only truly output dark gray and light gray, the technique of the
present invention achieves the illusion of intermediate colors by causing
the eye to perceptually average the two true colors because they are
judiciously distributed across the dither template.
It should be noted that although in the examples discussed in connection
with FIGS. 4 and 5 it will be stated that the dither template itself is
shaded, in actual implementations of the present invention in an imaging
system it is the output array, such as a video monitor screen, and not the
dither template, that is shaded. On the other hand, in connection with the
more detailed discussion of IP 40 below, it will be explained that the
specific values that appear in the cells of the dither template are
indirectly mapped to specific cells in an output array, such as output
array 32 of FIG. 1. And, those cell values are instrumental in determining
the shading of the output array. Given this association, for the purpose
of a simplified explanation in connection with FIGS. 4 and 5, the cells of
the template will be treated as if they can be shaded, while the more
specific explanation of the role of the template will be presented below.
Still referring to Graph 53, the input levels falling between IL.sub.a and
IL.sub.b are themselves divided into ranges, .DELTA..sub.d, which are
determined on the basis of the NIL, the NOL, and the NTL of a particular
implementation. Each of these variables are instrumental in determining
the division of input ranges which are necessary for the faithful
reproduction of the output image. In one embodiment, the division of
ranges, .DELTA..sub.d, is:
.DELTA..sub.d =.DELTA..sub.Q /(NTL) (Equation II).
Accordingly, in Graph 53 .DELTA..sub.d is shown to span groups of
intermediate input values which fall between IL.sub.a and IL.sub.b. At
either end of the input levels, however, there is an Offset which is
applied in order to assure that there is a symmetric distribution of input
levels around output levels. In the embodiment shown on FIG. 4,
Offset=.DELTA..sub.d /2 (Equation III).
This offset is similar to the offset discussed above in connection with the
apportioning of input levels around a given .DELTA..sub.Q at either end of
the full range of input levels.
Still referring to FIG. 4, the first dither pattern 52a is one in which all
of the cells of the dither template are shaded dark gray, Accordingly,
section 56a of Graph 53 shows 4 cells shaded dark gray, and 0 of the cells
shaded light gray. The second dither pattern 52b is one in which 3 of the
cells are dark gray, while 1 of the cells is light gray; therefore,
section 56b of Graph 53 shows 3 dark gray cells and 1 light gray cell. The
third dither pattern 52c shows 2 cells shaded dark gray and 2 shaded light
gray, with a corresponding representation in section 56c of Graph 53. The
other two dither template patterns, and their corresponding graphic
representations are likewise shown in FIG. 4.
Also included on FIG. 4 is Graph 54, which is associated with Graph 53, as
indicated by the dashed lines connecting the graphs. Like Graph 53, Graph
54 includes the same input levels, IL.sub.a through IL.sub.b, on the x
axis. The full range of input levels are covered by .DELTA..sub.Q, and the
intermediate levels are subdivided into smaller .DELTA..sub.d ranges, as
shown. In addition, the y axis of 20 Graph 54 includes the two true output
levels of output device 30, OL.sub.a (dark gray) and OL.sub.b (light
gray).
From FIG. 4 it is graphically shown how intermediate levels are produced by
the combination of quantization and the dither template. Namely, in
between the true output levels, OL.sub.a (dark gray) and OL.sub.b (light
gray), there are three intermediate levels. These levels are what would be
seen by one looking at the dither template if it is shaded in the various
patterns, 52a through 52e, discussed in connection with FIG. 4.
Dark gray and light gray are the result of the shading of all of the
template cells with the two true colors, respectively. On the other hand,
when 3 template cells are shaded dark gray and 1 is light gray, the
intermediate level perceived by one looking at the template will be a
shade of gray falling between dark gray and light gray, but visually
closer to dark gray. On the other hand, when 3 cells are shaded light gray
and 1 is shaded dark gray, the intermediate level will also be a shade of
gray falling between dark gray and light gray, but will be visually closer
to light gray.
As shown in Graph 54, the intermediate levels between dark gray and light
gray are represented by the gradual stair step progression of the graph
from dark gray to light gray. Furthermore, Graph 54 shows how the full
range of input levels, IL.sub.a through IL.sub.b, map into either the true
output levels, OL.sub.a and OL.sub.b, or the perceived intermediate
levels.
Generally, the number of perceived output levels ("NPOL") that a particular
output device 30 is capable of outputting, is determined by the NOL that
the system is able to output, and the NTL of the dither template. The
relationship is:
NPOL=<(NTL)(NOL-1)+1>, when .DELTA..sub.d >1; and
NPOL=NIL, when .DELTA..sub.d .ltoreq.1 . (Equation IV).
Therefore, for the example shown in FIG. 4 in which .DELTA..sub.d >1, the
NPOL=<4(2-1)+1>=5, which is confirmed by the total number of perceived
output levels shown on the x-axis segment of Graph 54.
Referring now to FIG. 5, a more complete example of the multi-level image
processing system of the present invention is shown, combining
quantization, a dither template, and the use of a greater NOL than was
illustrated in FIG. 4. Similar to FIG. 4, FIG. 5 includes Graphs 55 and 57
on which the x axis of each includes a number of input levels, ranging
from 0 to (NIL -1), which are the input levels which input device 22 is
capable of registering. The y axis of each includes four true output
levels, 0, 1, 2, and 3. As discussed above, the present invention can be
applied with any number of input or output levels. The numbers chosen for
purposes of this illustration, however, are relatively small so that the
explanation of the principles of the embodiment of the invention can be
less complex. Those principals, however, would be applied the same if a
greater number of input and output levels are used.
Like FIG. 4, FIG. 5 has dither template 60 where M.sub.tmp =N.sub.tmp =2
and NTL=4. Each input level is included within the span of a given
.DELTA..sub.Q, which is determined in accordance with Equation I, above.
Likewise, each of the input levels is included within the span of a given
.DELTA..sub.d, which is determined in accordance with Equation II, above.
At either end of the full range of input levels, it can be seen that the
width of the first section 62 and the last section 64 of Graph 55 is only
.DELTA..sub.d /2. This offset is consistent with the Offset which is
determined in accordance with Equation III. Although at the two ends of
the range of input levels, IL.sub.a and IL.sub.b, the span of the two end
sections are only .DELTA..sub.d /2 wide, from Graph 55 it can be seen that
in the middle portions of the graph, adjoining half sections of
.DELTA..sub.d, together form full sections which are .DELTA..sub.d wide.
Consequently, the combined half sections succeed in providing a
symmetrical distribution of input levels around their perceived, output
levels.
As shown in Graph 55, the four true levels which output device 30 is
capable of outputting are: 013 black; 1--dark gray; 2--light gray; and
3--white. As with the two levels discussed in connection with FIG. 4,
these levels have been arbitrarily chosen to illustrate a particular
embodiment of the present invention, and any other levels could have been
chosen.
Referring first to graph segment 62 on Graph 55, if the 4 cells of the
dither template 60 are all shaded black, then the true level black would
be visible to one looking at dither template 60. Furthermore, with the 4
cells shaded black, output array 32 would be outputting a true level,
namely black. In graph segment 64, if 3 of the 4 cells are shaded black,
and 1 of them is shaded dark gray, than a visually intermediate level will
be perceived by looking at the shaded dither template 60. That
intermediate level will be visually close to black, but will be slightly
lighter than solid black, because one of the cells will be shaded dark
gray. Thus the eye of the person looking at the template averages the
appearance of the individual cells to perceive the intermediate level.
Progressively the illusion of lighter, intermediate levels can be provided
on dither template 60 as more cells are turned onto dark gray and fewer
onto black, as shown in segment 70. As shown on segment 72, if all of the
pixels in the template 60 are turned to dark gray, then dither template 60
would project the true level, dark gray.
Considering one other example at the far right of Graph 55, in segment 74
three cells have been shaded light gray and one has been shaded white,
thereby providing the visual illusion in dither template 60 of a level
that is between light gray and white. At the very end of the range of
input levels, input levels within .DELTA..sub.d /2 of (NIL-1), are mapped
to the level white. As shown on Graph 55, in segment 64, the four cells of
dither template 60 have been shaded white, which is another one of the
four, true, input levels.
FIG. 5 further includes Graph 57, which is associated with Graph 55 as
shown by the dashed lines through the graphs. On the x axis, Graph 57
includes the same input levels ranging from 0 to (NIL-1), which are
divided into .DELTA..sub.Q and .DELTA..sub.d segments. Similar to Graph
54, the stair step progression of Graph 57 graphically shows that although
output device 30, shown on FIG. 1, is capable of outputting only four true
levels, - - - 0--black; 1--dark gray; 2--light gray; and 3--white through
the multi-level image processing technique of the present invention,
output device 30 is capable of outputting a total of 13 perceived levels,
four of which are true levels, and 9 of which are the intermediate levels
which fall between the true levels. As stated above, Equation IV
determines the total number of perceived levels which output device 30 is
capable of outputting, which, when applied to the exemplary output device
of FIG. 5 confirms that the total number of levels is 13.
To the extent that the NPOL is influenced by the NTL, as well as the NOL,
there may be a motivation to choose a dither template with a very high NTL
to increase the NPOL. The higher the NTL the greater the size of the
M.times.N array of the template, which requires a larger size memory.
Therefore, there is a cost associated with having a higher NTL, which must
be balanced against the benefits of having more perceived levels.
B. Multilevel Dithering System with Two Memories
Having explained how quantization and dither templates are generally used
in IP 40, shown on FIG. 1, to provide the illusion of output device 30
being capable of outputting more levels than the number of true levels
which it can actually output, a specific embodiment of IP 40 will now be
discussed.
Referring momentarily back to FIG. 1, the overall objective of imaging
system 20 is to take the IL<x,y> value of a given input cell 26 in input
device 22, and translate it to an OL<x,y> value in the corresponding
output cell 34 in output device 30. As shown in FIG. 1, coupled between
input device 22 and output device 30 is IP 40, which accomplishes this
translation.
Referring now to FIG. 6, a block diagram of IP 40 is shown to include two
major block components, Look Up Table ("LUT") generator 80, and a two
memory run time system 81 ("TMRTS"), which is shown in dashed lines. TMRTS
81 includes a dither template memory 82, which is initialized with values
d<x',y'> by LUT generator 80. TMRTS 81 further includes an address
modifier circuit 87, which is used to convert addresses x,y of an input
cell 26 of input device 22, shown on FIG. 1, to addresses x',y' which are
applied as an address to access the values stored in dither template
memory 82. The output of dither template memory 82, d<x',y'>, are fed to
an adder 85. Adder 85 is also fed an input level, IL<x,y>, for the given
input cell 26, and the two values are added by adder 85 to produce a sum
value, S. S is used as an address to quantizer LUT 86 to produce output
values OL<x,y>, which are fed to the output device 30 of FIG. 1. As with
dither template memory 82, quantizer LUT 86 is initialized with values
Q<S> from LUT generator 80.
In this particular embodiment of the invention, LUT generator 80 determines
values which are stored in the dither template memory 82 and quantizer LUT
86. LUT generator 80 does not necessarily need to run at any particular
speed since it computes these values before imaging system 20 starts
translating input pixels to output pixels during real time operation.
Instead, after LUT generator 80 determines and stores the values in the
memory and look up tables, it will resume activity only if some of the
imaging system 20 parameters change.
On the other hand, in this particular implementation, TMRTS 81 is the
portion of IP 40 which does operate in real time, and during operation it
is constantly receiving input values, IL<x,y>, from input array 24, shown
in FIG. 1, and processing them into corresponding output values, OL<x,y>
in output array 34.
IP 40, and in particular, LUT generator 80 is fed by signals corresponding
to: the number of input levels, NIL; the number of output levels, NOL; the
number of dither template levels, NTL; the dither template order T<x',y'>
phase.sub.-- x and phase.sub.-- y values; and the dimensions of the dither
template memory M.sub.mm .times.N.sub.mm. Address modifier 87 of IP 40 is
fed the x and y address values for a given input cell, x,y, and adder 85
is fed the actual input level of the given input cell at the x, y address,
IL<x,y>. With this information IP 40 will compute the appropriate OL<x,y>
for the corresponding IL<x,y>.
It should be noted that one of the sets of variables input into IP 40,
namely phase.sub.-- x, phase.sub.-- y, has not yet been discussed.
Briefly, phase.sub.-- x and phase.sub.-- y are the variables which define
the two dimensional spatial shift of the dither matrix relative to a
particular dither matrix arrangement immediately prior to the shift. The
method by which these variables determine the shift and the importance of
the shift will be further detailed below.
Referring now to FIG. 7, LUT generator 80 is shown to include a variables
determiner circuit 90 which is fed by signals corresponding to NOL, NIL,
and NTL to provide data signals representing: .DELTA..sub.Q, the number
quantization levels, and {.sub.d, the subdivisions of the quantization
levels. The variables determiner circuit 90 uses any conventional
arithmetic circuit to provided these values by solving Equations I and II,
above.
The signals corresponding to NOL and .DELTA..sub.Q are fed to quantizer
generator 92. Quantizer generator 92 uses these signals to produce a table
of values Q<S> which is stored in quantizer LUT 86, shown in FIG. 6.
The LUT generator 80 is shown to further use a memory device, which could
be the same memory device used for dither template memory 82, for the
temporary storage of a suitable dither template. One embodiment of the
invention, incorporates the dither template shown in a copending patent
application Ser. No. 07/961,244, filed Oct. 15, 1992, entitled "Void and
Cluster Method for Generating Dither Arrays", the inventor of which is
Robert Ulichney the contents of which is hereby incorporated by reference.
The referenced application was filed on the same date as this application
and it has also been assigned to the same assignee, Digital Equipment
Corporation, as this application.
Dither template values, T<x',y'>, are shown on FIG. 7 as reference numeral
94. They are fed to dither normalizer 96 which adjusts the dither template
values so that they are made to be symmetrically distributed in a manner
which is detailed below.
The output from the dither normalizer 96 as stored is shown by reference
numeral 97, and these values are fed into phase adjuster circuit 100 along
with phase.sub.-- x, phase.sub.-- y, and M.sub.mm .times.N.sub.mm signals.
Phase adjuster 100 processes the values by spatially shifting the elements
within the dither matrix. Thus, the elements of the dither matrix which
have a particular location within the matrix prior to phase adjustment,
are adjusted to a different location within the dither matrix on the basis
of the phase.sub.-- x and the phase.sub.-- y values The resulting values
d<x',y'> are then stored in dither matrix memory 82, shown on FIG. 6.
In order to illustrate how LUT generator 80 operates, a simple example will
be developed through which actual values will be assigned to the various
input signals to see how those values are processed through IP 40. As
discussed above, relatively small numbers are used for the purpose of
illustrating the principles underlying the embodiment of this invention;
however, larger input values would work in the same manner illustrated. In
addition to FIG. 7, FIG. 8 includes a flow diagram showing the steps of
the process, and the flow diagram of FIG. 8 will be referred to in
conjunction with the discussion of FIG. 7.
In this example, it will be assumed that the following input signals are
provided to LUT generator 80 by imaging system 20.
TABLE B
______________________________________
NIL = 256
NOL = 4
NTL = 4
Element ordering is:
1 2
3 0
M.sub.mm = 8
N.sub.mm = 8
Phase.sub.-- x = -1
Phase.sub.-- y = -1
______________________________________
It should be noted that although a preferred dither template was referred
to above, a relatively simple dither template has been used in this
particular example for purposes of providing a less complicated discussion
of the principles underlying the embodiment of the invention. However, the
use of the more complex dither template would be in accordance with the
same principles.
Referring back to FIG. 7, variables determiner 90 receives NIL, NOL, and
NTL and uses that information to compute the values for .DELTA..sub.Q and
.DELTA..sub.d. The computation of .DELTA..sub.Q is accomplished in
accordance with Equation I, such that in this particular example,
.DELTA..sub.Q =(256-1)/(4-1)=85 (Step 110, FIG. 8). Similarly, the
computation of .DELTA..sub.d is accomplished in accordance with Equation
II, such that .DELTA..sub.d =85/4=21.25 (Step 112, FIG. 8).
As shown in FIG. 7, the .DELTA..sub.Q value is output by variables
determiner 90 to quantizer generator 92, which determines the values which
are then stored in quantizer LUT 86. Quantizer generator 92 uses
.DELTA..sub.Q to determine the different values of Q<S>, where particular
Q<S> values are output by quantizer LUT 86 in response to any "S" value
input into quantizer LUT 86 by adder 85, as shown in FIG. 6 (Step 116,
FIG. 8). The generation of S by adder 85 will be further discussed below.
The equation employed by quantizer generator 92 to produce Q<S> is:
For each OL={0 through (NOL-1)}, Q<S>=OL, for those values of S that
satisfy:
int {(OL)(.DELTA..sub.Q)+0.5}.ltoreq.S<int
{(OL+1)(.DELTA..sub.Q)+0.5}(Equation V).
Using the values given in Table B and Equation V, quantizer generator 92
would compute and store the following values in quantizer LUT 86.
TABLE C
______________________________________
For S from: 0 through 84, OL<x,y> = 0;
85 through 169,
OL<x,y> = 1;
170 through 254,
OL<x,y> = 2;
255 through 339,
OL<x,y> = 3.
______________________________________
In this particular implementation, quantizer LUT 86 has address locations
from 0 through 339. The storage of the OL values at those particular
address locations is in accordance with Table C, such that at address
locations 0 through 84, the output value 0 is stored. Thus, the number of
unique S values that map to the given output level 0 is 85. At address
locations 85 through 169, the value 1 is stored, so that the number of
unique S values that map to the given output level 1 is also 85. The same
is true of the other two sets of values, in which the number of unique S
values that map to the output levels 2 and 3 are likewise 85.
Although the method by which adder 85 produces the S values has not yet
been detailed, it will be shown through the discussion below that, in a
given implementation, adder 85 will produce a finite number of unique S
values. This is because in a given implementation the number of possible
values which are summed together by adder 85 are finite. Understanding
this fact in combination with the Equation V, the definition of
.DELTA..sub.Q can now be refined.
More particularly, .DELTA..sub.Q is the average value of the number of
unique S values which can be produced by adder 85 in a given
implementation and which map to a single, given output level. In order to
determine what that average value is in any particular implementation, it
is necessary to determine the finite numbers of possible addends to be
added by adder 85, and compute all of the possible S values. After the
total number of possible, unique S values are determined, then they must
be mapped to their respective output levels. In any given implementation
there is also a finite number of output levels, and each possible, unique
S value will map to one of those output levels. Therefore, the definition
of .DELTA..sub.Q is refined to represent the average value of the number
of unique S values that map to a single, given, output level, if all
possible S values were produced by adder 85 and mapped to their
corresponding output level in quantizer LUT 86.
Additionally, .DELTA..sub.Q is a real number, and Equation V shows that the
number of unique S values that map to any single, given, output level does
not differ by more than 1. In the particular example provided in
connection with Table C, .DELTA..sub.Q, as the average value of the number
of unique S values that map to a single, given output level, is equal to
85. Although in this particular example all such numbers were equal to 85,
such that the average is 85, in other implementations, the number of
unique S values that map to different, given output levels may not always
be the same. As indicated by Equation V, however, they will differ by no
more than one.
During the operation of IP 40, as an S value is sent to quantizer LUT 86 by
adder 85, shown in FIG. 6, the S value provides an address to the memory
device of quantizer LUT 86, and the corresponding output value at that
address is then provided as OL<x,y>. For example, if S is equal to 273,
quantizer LUT 86 would output an OL equal to 3. On the other hand, if S is
equal to 93, quantizer LUT 86 would output an OL equal to 1. Having
OL<x,y> output as soon as the appropriate address is accessed in quantizer
LUT 86 contributes substantially to the speed of the overall imaging
system.
Continuing with the discussion of the block components, FIG. 7 shows the
order of the dither template, T<x',y'>, as another input into LUT
generator 80. As explained in connection with the discussion of FIG. 3G,
above, in those instances in which the dimension of the dither template is
smaller than the dimension of the memory, it is possible to tile the
dither template into the memory so that the entire memory space is filled
with the dither pattern (Step 120, FIG. 8).
In this particular instance, the dither template, shown in Table B, has a
2.times.2 dimension, while the dither template memory is 8.times.8 .
Therefore, imaging system 20 would have tiled the smaller dither template
into the larger dither template memory so that in the embodiment shown,
the T<x',y'> presented as an input to LUT generator 80 is the fully
expanded dither pattern. On the other hand, if instead of using the
2.times.2 dither template shown in Table B, an 8.times.8 dither template
was used, no such tiling would be necessary, as the dither template would
fit within the dither template memory without repetition.
As shown on FIG. 7, the numerical values of the elements in the dither
template, T<x',y'> are next processed by dither normalizer 96 (Step 122,
FIG. 8). Through dither normalizer the dither matrix values are adjusted
to be symmetrically distributed between 0 and the average value of the
number of unique S values which can be produced by adder 85 and which map
to a single, given output level. As discussed above, that average is equal
to .DELTA..sub.Q, which is determined in accordance with the method
discussed above.
As shown on FIG. 7, dither normalizer 96 uses the values .DELTA..sub.d,
which is output by variables determiner 90. Dither normalizer 96 combines
the values for T<x',y'> and .DELTA..sub.d, and Offset in the following
equation for the purpose of outputting normalized values, D<x',y'>, where:
D<x',y'=int{.DELTA..sub.d (T<x',y'>+1/2)} (Equation VI )
It should be noted that Equation VI is derived from the equation:
D<x',y'>=int{<(T<x',y'>)(.DELTA..sub.d)>+Offset}. This equation, however,
can be simplified into Equation VI using the expression for Offset
provided in Equation III. Accordingly, dither normalizer uses the
simplified Equation VI, and does not need to have Offset separately
computed.
Using the specific values of this example, when the given T<x',y'> values
shown in FIG. 9A are processed by dither normalizer 96 using Equation VI,
the resulting D<x',y'> values are shown in FIG. 9B. As seen by comparing
the values in FIG. 9A and 9B, each of the original dither template values
has been adjusted so that they are symmetrically distributed within the
range that extends from 0 through the value of .DELTA..sub.Q, which in
this example is 85. Thus the value 0 is adjusted to 10; the value 1 is
adjusted to 31; the value 2 is adjusted to 53; and the value 3 is adjusted
to 74.
Next, the D<x',y'> values are processed by phase adjuster 98, which uses
the values for phase.sub.-- x, phase.sub.-- y, N.sub.mm, and N.sub.mm, to
provide a two dimensional, spatial shift of the elements within the dither
matrix (Step 124, FIG. 8). Thus, each of the elements of the dither matrix
which have a particular location within the matrix prior to phase
adjustment, are adjusted to a different location within the dither matrix
on the basis of the phase.sub.-- x and the phase.sub.-- y values.
In the embodiment shown on FIG. 7, the D<x',y'> values, phase.sub.-- x,
phase.sub.-- y, M.sub.mm, and N.sub.mm are combined in the following
equation for the purpose of outputting d<x',y'>, which is the final value
that is stored in dither template memory 82, shown on FIG. 6. The equation
is:
d<x',y'>=D<(x'+phase.sub.-- x)modulo(M.sub.mm), (y'+phase.sub.--
y)modulo(N.sub.mm)>,
where:
A modulo(B)=the remainder resulting from A/B (Equation VII)
After the values for D<x',y'>, as shown in FIG. 9C, are processed by phase
adjuster 98 along with the values for phase.sub.-- x, phase.sub.-- y,
M.sub.mm, and N.sub.mm, the final values, d<x',y'>, are stored in dither
template memory 82 (Step 126, FIG. 8). FIG. 7 shows phase adjuster 98
inputting d<x', y'> into dither template memory 82, and FIG. 9C shows what
those stored values would be for the given example.
As seen by comparing FIG. 9B and 9C, through the phase adjustment process
the elements in FIG. 9B, which is the arrangement of the dither matrix
elements immediately prior to the phase adjustment step, have been shifted
down and to the right by one. This is because phase.sub.-- x=(-1) and
phase.sub.-- y=(-1). If phase.sub.-- x=(2) and phase.sub.-- y=(3), for
another example, then the dither template values would have been shifted
up 2 and to the right 3.
Given that the dither matrix is designed to "wrap around", during the phase
adjustment process, the elements along the right side and bottom are
simply adjusted to the left side and the top, respectively. The phase
adjustment process is particularly useful in connection with the
implementation of dithering systems which involve color primaries, such as
red, green, and blue, as will be discussed below.
Having reviewed the internal operation of LUT generator 80, and having
shown how the specific values are generated and stored in dither template
memory 82 and quantizer LUT 86, reference can now be made back to FIG. 6
for a further explanation of the operation of IP 40. This explanation will
be provided in conjunction with the flow diagram of FIG. 10. As stated
above, after table value determiner 41 fills dither template memory 82
with the d<x',y'> values and quantizer LUT 86 with Q<s> values (Step 130,
FIG. 9), TMRTS 81 is prepared to determine the output levels of pixels in
output device 30 which correspond to input levels of pixels in input
device 22 during real time operation.
As shown on FIG. 6, during real time operation address modifier 87 receives
the x,y address of a specific input cell 26 from input device 22. In
response to that x,y address, address modifier 87 will adjust the x,y
address because the dimension of the input array 24 is likely to be much
larger than the dimension of the dither template memory (Step 132, FIG.
10). Accordingly, address modifier 87 uses the following equation to
convert x to x', and y to y'.
x'=x modulo M; y'=y modulo N (Equation VIII).
It should be noted that for the likely case that M.sub.mm and N.sub.mm are
powers of 2, address modifier 87 would simply use the low order bits of x
and y. After this conversion, address modifier 87 will feed a modified
address x', y' into dither template memory 82, in which d<x',y'> values
have already been stored by phase adjuster 98.
In response to the x',y' address, dither template memory 82 will output the
corresponding d<x',y'> value stored in the row-column address
corresponding to x',y' (Step 134, FIG. 10). That d<x',y'> value is sent to
adder 85, which adds d<x',y'> to IL<x,y>, which is the specific input
level value of the input cell 26 in input array 24, shown on FIG. 1, at
address x,y (Step 136, FIG. 10). The sum of those two values is S which is
forwarded to quantizer LUT 86 (Step 138, FIG. 10). As discussed above, LUT
generator 80 will have already stored OL values in the locations for which
S operates as an address. Accordingly, S will access a particular address
location depending on the specific S value resulting in quantizer LUT 86
outputting the appropriate OL<x,y> value (Step 142, FIG. 10) to the output
device 30 on FIG. 1.
At this point it can be noted that the two addends of adder 85 - - - namely
the dither template values, d<x',y'>, and the input levels, IL<x,y>- - -
are finite numbers. In other words, in a particular implementation, there
will be a finite number of possible, dither template values, and a finite
number of possible input levels. Correspondingly, the addition of all
possible dither template values with all possible input levels would yield
a finite number of unique, possible S values.
Referring now to FIG. 11, a table is provided which shows the range of
input levels for the example discussed in connection with FIGS. 6 through
11, the total number of input levels falling within those ranges, and the
corresponding perceived output levels. The perceived output levels are the
ones which are achieved by passing every input level from IL=0 to IL=255
in combination with every address from <x,y>=<0,0> to <7,7> through IP 40.
As shown in FIG. 11, there are 4 true levels, and 9 intermediate levels
which are the effective results of the dithered average. These numerical
averages are meaningful in that a person viewing output device 30 would
visually average the output patterns and perceive an image level
equivalent to the average value indicated.
Referring back to the discussion of FIGS. 4 and 5, in those examples the
cells of the dither templates are discussed as if they could actually be
shaded. As stated in that portion of the discussion, this is not so.
Rather, it is the cells of the output device, such as cells 34 of output
array 32 shown on FIG. 1 that are actually shaded in order to produce an
output image. On the other hand, through the image processing technique
discussed in connection with FIGS. 6 through 11, it has been explained how
the values in the dither template are indirectly mapped to the determined
output levels in the output array. In other words, through the technique
of the present invention, the value in a given cell in the dither template
will indirectly determine the output level in a given cell in the output
array. As seen by following the processing of the values, T<x',y'> is made
up of the original dither template values, which eventually get modified
in dither normalizer 96 and phase adjuster 98 before storage in dither
template memory 82. The values stored in dither template memory 82 are
then added to the input levels, IL<x,y>, and the sum, S, then operates as
an address to quantizer LUT 86. Quantizer LUT 86 then outputs the
appropriate level for the output cell which corresponds to the level of
the input cell from which IL<x,y> originated. In this regard, although the
cells of the dither template are themselves not shaded, the values in the
cells of the dither template do indirectly determine the levels, or
shading, of the cells of the output array in the manner discussed.
C. Two Level Dithering System with Comparator
Although first embodiment of the present invention has been discussed in
connection with a system which can dither to any number of output levels,
in the event that the number of output levels equals 2, i.e. NOL=2, a
different implementation of the multi-level processing system is possible.
As discussed above, an output device which is capable of representing only
two levels is a bi-tonal device. In this particular embodiment, there may
be any number of input levels provided they are greater than two. In other
words, the output device is bi-tonal, but the input devices are
monochromatic, or color devices.
Referring now to FIG. 12 for the alternate embodiment of the image
processor portion of the imaging system, IP 140 receives the same basic
inputs, has similar components, and processes those inputs in a similar
manner as IP 40, discussed in connection with FIGS. 1, and 6 through 11.
Thus, FIG. 1 provides an overview of the implementation of IP 140 in an
imaging system provided IP 140 was substituted in place of IP 40.
Given that the operation of IP 140 of FIG. 12 is similar to the operation
of IP 40 of FIGS. 6 and 7, the discussion of FIG. 12 will not repeat the
detailed discussion of FIGS. 6 and 7, but will focus upon the differences
between IP 40 and IP 140. The major differences are that in place of an
adder 85, there is a comparator, and the quantizer LUT 86 has been
eliminated. Also, in FIG. 12, the block elements are numbered so that they
correspond to their respective block elements in FIG. 6; however, the
corresponding block elements in FIG. 12 are numbered in the 100's to
distinguish them.
In addition to the block diagram of FIG. 12, flow diagrams of the method of
implementing the technique in conjunction with the comparator are provided
on FIGS. 13 and 14.
In FIG. 12, LUT generator 180 outputs the d<x',y'> values which are stored
in dither template memory 182, and it also computes .DELTA..sub.Q, (Step
310, FIG. 13), and .DELTA..sub.d (Step 312, FIG. 13), as explained above
in connection with LUT generator 80 of FIGS. 6 and 7. Given that there is
no quantizer LUT in this particular implementation, LUT generator 180 does
not need to compute quantized values and fill a quantizer LUT 86, as
discussed in connection with FIGS. 6 and 7.
After LUT generator 180 computes .DELTA..sub.Q and .DELTA..sub.d , it tiles
the dither template into the dither template memory 182, if necessary
(Step 316, FIG. 13). LUT generator 180 normalizes the dither template
values (Step 320, FIG. 13), phase adjusts the dither template values (Step
322, FIG. 13), and stores the results in dither template memory 182 (Step
324, FIG. 13). This is, of course, the same as the procedure discussed in
connection with FIGS. 6 through 11.
Next, after the values are stored in dither template memory 182, the run
time portion of the system, comparator run time system (CRTS) 181, is
prepared to operate. With the dither template values stored in dither
matrix memory 182 (Step 330, FIG. 14), address modifier 287 receives the
x,y address of the input cell. Like address modifier 87 of FIG. 6, address
modifier 187 will translate the address to x',y' (Step 332, FIG. 14). In
response to the address, dither template memory 182 will output the
accessed d<x',y'> value to comparator 190 (step 334, FIG. 14). The value
is transferred to comparator 190 from another part of imaging system 20,
such as input device 22 shown in FIG. 1. Comparator 190 then performs the
following comparison and outputs the appropriate OL<x,y> value on the
basis of that comparison (Step 336, FIG. 14). The operation performed by
comparator 190 is as follows:
If IL<x,y>>d<x',y'>,
then OL<x,y>=1,
else OL<x,y>=0. (Equation IX.)
Depending upon the results of the comparison, IP 140 will output the
corresponding OL<x,y> (Step 340, FIG. 14).
Thus, IP 140 achieves the same output as the generally applicable IP 40,
discussed in connection with FIGS. 6 through 11, provided the output image
is bi-tonal, or NOL=2.
D. Multilevel Dithering System with Single Memory
In yet another embodiment of the image processor, the run time portion of
the system uses a single memory device. This single memory approach is
faster than the embodiments which two memory devices in the run time
system, as discussed above; however, the size of the memory requirements
are considerably greater. This particular implementation requires that the
row dimension, M.sub.mm, and the column dimension, N.sub.mm, of the dither
template memory 482, as shown in FIG. 15, must each be a power of 2.
Referring now to FIGS. 15 and 16, IP 440 includes LUT generator 480, which
receives the same inputs and operates in the same manner as LUT generator
80, discussed in connection with FIGS. 6 through 11. As discussed above,
FIG. 1 could provide the overview of the implementation of IP 440 in an
imaging system 20, provided IP 440 is substituted in place of IP 40. IP
44O includes single memory table value determiner (SMTVD) 481, which
contains the same block elements as TMRTS 81, discussed above. The block
elements of FIG. 15 are numbered so that they correspond to their
respective block elements in FIG. 6; however, the corresponding block
elements in FIG. 15 are numbered in the 400's to distinguish them.
To the extent that the operation of LUT generator 480 and SMTVD 481 operate
the same as the respective block elements discussed above, the details of
their manner of operation will not be repeated. Rather, it will be
understood that LUT generator 480 outputs d<x',y'> values which are stored
in dither template memory 482, and LUT generator 480 outputs Q<S> values
which are stored in quantizer LUT 486. The method by which these values
are generated is identical to the process detailed in connection with the
discussion of FIGS. 6 through 11. It should also be understood that the
values for d<x',y'> and Q<S> would have been generated by LUT generator
prior to the processing and outputting of values by address/level
generator 490, the operation of which is to be detailed next.
After d<x',y'> and Q<S> have been stored (Step 510, FIG. 16), FIG. 15 shows
address/level generator 490 receiving the inputs NIL, M.sub.mm, N.sub.mm
from imaging system 20 and address/level generator 490 outputs x', y' and
IL. The function of address/level generator 490 is to produce all of the
possible combinations of x', y' and IL values, so that the single memory
device of the run time portion of the system is able to store all possible
combinations of row/column addresses of dither template memory 482 and all
possible input levels at those addresses.
Referring now to FIG. 17, an address/level generator 490 is shown including
a counter set-up circuit 492. Counter set-up 492 is a circuit device which
is responsive to signals which correspond to the values for M.sub.mm,
N.sub.mm, and NIL. Counter set-up 492 makes sure that the individual
counters, 493 through 495, are large enough to count to the maximum values
given by M.sub.mm, N.sub.mm, and NIL. Also, counter set-up 492 initializes
the individual counters in the beginning of the operation so that their
respective initial values are zero. After initialization of the counters,
counter set up 492 starts clock 496 which will begin incrementing the
counters.
A simple example will show how address/level generator 490 operates. Assume
that dither template memory is an 8.times.8 array and there are 256 input
levels. Accordingly, x-counter 493 will need 3 address bits for
representing the 8 columns, M.sub.m ; y-counter 494 will need 3 address
bits for representing the 8 rows, N.sub.mm ; and IL-counter 495 will need
8 bits for representing the 256 input levels, IL. After initialization,
counters 493, 494, and 495 will output their respective values; namely
x-counter 494 outputs x', y-counter 495 outputs y', and IL-counter 496
outputs IL. All such values are output to SMTVD 481, shown on FIG. 15,
prior to the first incrementation by clock 496, and thereafter these
values are output after each incrementation by clock 496.
Before the first incrementation by clock 496, x'=000, y'=000, and
IL=00000000. Also before incrementation, address/level generator 490 would
then transfer these values to SMTVD 481 so that it could use the inputs to
compute the values to be stored in single LUT 491, shown on FIG. 15. Next,
clock 496 will increment x-counter 493 by one, so that the values output
by address/level generator 490 are: x'=001, y'=000, and IL=00000000.
Likewise, these values are transmitted to SMTVD 481, as are all of the
values for x', y', and IL after they are changed. After the second
incrementation by clock 496, the outputs of address/level generator 290
are: x'=010, y'=000, and IL=00000000. Thus, the incrementation will
continue until x-counter 493 reaches an output of 111, at which point it
will overflow (OF) for the first time.
As shown on FIG. 15, the overflow signal of x-counter 493 is the increment
signal for y-counter 495. Therefore, when x-counter overflows for the
first time, it then increments y-counter 495 for the first time. At that
point the outputs will be x'=000, y'=001, and IL=00000000. As clock 496
continues to increment x-counter 493, it will eventually overflow for a
second time, once again incrementing y-counter 495, at which point the
outputs will be x'=000, y'=010, and IL=00000000.
Through the incrementation process y-counter 495 will eventually overflow
and increment IL-counter 496 for the first time, the overflow of y-counter
495 being the input for IL-counter 496 as shown in FIG. 17. After the
first overflow, the outputs will be x'=000, y'=000, and IL=00000001.
Finally, after IL-counter 495 is made to overflow through incrementation,
its overflow will stop clock 496, and the incrementation process will be
completed.
As indicated, at each stage of the incrementation process, x', y' and IL
are transferred to SMTVD 481 for processing. Therefore, through the
operation of address/level generator 290, all of the possible combinations
of row-column addresses and all possible input levels at those addresses
can be generated and forwarded to SMTVD 281 for processing (Step 512, FIG.
16.)
Referring back to FIG. 15, x' and y' are transferred to address modifier
487 by address/level generator 490. As discussed above, in connection with
address modifier 87 shown in FIG. 6, the purpose of address modifier 87 is
to adjust the x,y address of the input from input device 22 in the event
that input array 24 of FIG. 1 is larger than the dimension of the dither
template memory. In the embodiment of the image processor shown in FIG.
15, IP 440, address/level generator 490 already outputs x', y' (Step 514,
FIG. 16), thereby eliminating the need for a separate address modifier. In
response to x', y' dither template memory 482 outputs d<x',y'> values
which are transmitted to adder 485 (Step 516, FIG. 16).
Address/level generator 490 also outputs the IL<x,y> value associated with
x', y', and together the values are transmitted to adder 285 (Step 520,
FIG. 16). In response, adder 285 adds the given d<x',y'> values to their
corresponding IL values to form the sum, S (Step 521, FIG. 16). Similar to
the discussion of FIGS. 6 through 11, S is output as the address to the
look up table of quantizer LUT 486 (Step 522, FIG. 16). Accordingly, as
address/level generator 490 transmits each x', y', and IL value to SMTVD
481, SMTVD 481 will output OL values, which correspond to each IL<x,y>
value transmitted.
As shown in FIG. 15, the OL values output by quantizer LUT 486 of SMTVD 481
are transmitted to single LUT 491, which is a memory device. As OL values
are transmitted they are stored in sequential addresses in single LUT 481
(Step 524, FIG. 16). For example, the first set of values output by
address/level generator 490, before clock 496 incremented the counters, is
x'=000, y' =000, and IL=00000000. Thus, the OL computed by SMTVD 481 in
connection with this set of values would be stored in the first address
location of single LUT 491, having a binary address of 00000000000000, for
example. When the second set of values output by address/level generator
490 is transmitted to SMTVD 481, the computed OL would be stored in the
second memory location, having a binary address of 00000000000001, and so
on.
Thus far, the operation of IP 440 has addressed the computation and storage
of values in the single memory device of the run time portion of the
system, which is a look up table, single LUT 491. In this single memory
implementation, all of the operations prior to the computing and filling
of single LUT 491 with the OL values does not need to be done at any
particular speed. Rather all the block elements compute the values and
fill single LUT 491 prior to the time that imaging system 20, shown in
FIG. 1, translates the input pixels to output pixels during real time
operation. After the values are computed and stored in single LUT 491,
imaging system 20 is then in a position to translate the input pixels to
output pixels through the real time operation of single memory run time
system (SMRTS) 497, shown as a dashed line block on FIG. 15.
Along with the block elements of FIG. 15, FIG. 18 provides a flow diagram
illustrating the method by which the operation of SMRTS 497 results in the
outputting of output levels which correspond to the input levels
transmitted to SMRTS 497. SMRTS 497 includes single LUT 491 and collective
address generator 498. As discussed above, single LUT 491 is a memory
device which stores all of the output levels computed by SMTVD 481 (Step
530, FIG. 18). On the other hand, collective address generator 498
receives x, y addresses and their corresponding IL<x,y> from input device
22 during real time operation. Collective address generator 498 converts
this information into an address that is then used to access single LUT
491 (Step 532, FIG. 18).
More particularly, collective address generator 498 uses only the least
significant bits of the x, y address which are necessary to identify an
address location. For example, in the embodiments discussed above, the
dither template memory is an 8.times.8 array, which therefore requires 3
bits for column addressing, and 3 bits for row addressing. In such a
configuration, collective address generator 498 would use only the 3 least
significant bits of the x address value coming from an input device, such
as input device 22 shown on FIG. 1, and the 3 least significant bits of
the y address value coming from the input device. In other implementations
in which the dither template memory has a different size, that size would
correspondingly determine the number of least significant bits of the x, y
address used by collective address generator 498.
Collective address generator 498 bundles the necessary least significant
bits of the x, y address together with the actual input level at that
address, IL<x,y>, to produce a collective address which is then
transmitted to single LUT 491 (Step 534, FIG. 18). Given that LUT
generator 480, address/level generator 490, and SMTVD 481 would have
collectively generated and computed output levels for all possible
combinations of x, y addresses and input levels, and stored those values
in single LUT 491, the address output by collective address generator 498
need only access the particular address in single LUT 491 to have it
output the OL<x,y> which corresponds to IL<x,y,> (Step 536, FIG. 18) .
Using one implementation as an example, if the least significant bits of
the x and y address are respectively 010 and 101, and IL<x,y> is 00001111,
collective address generator 498 will access address 01010100001111 in
single LUT 491. In addition, the storage of values in single LUT 491 will
be such that at that particular address location will be the OL value
computed by SMTVD 281 when address level generator 490 had transmitted to
it the values: x'=010, y' =101, and IL=00001111.
Comparing the single memory implementation to the two memory implementation
discussed above, the single memory system can operate faster than the two
memory system. During real time operation, SMRTS 497, shown on FIG. 15,
requires only the generation of a collective address by collective address
generator 498, which then operates as an address to single LUT 491. That
address causes single LUT 491 to then output OL<x,y>. With respect to the
two memory device implementation, during real time operation TMRTS 81,
shown on FIG. 6, requires the generation of the modified address, through
address modifier 87. That address accesses dither template memory 82,
which in turn outputs d<x',y'> to adder 85. Adder 85 adds d<x',y'> to
IL<x, y> to generate the sum, S, which accesses a memory location in
quantizer LUT 86, which finally outputs OL<x,y>. Accordingly, the
generation of OL<x,y> values during real time operations involves more
steps, and therefore takes longer, for the two memory implementation,
shown on FIG. 6, than for the single memory implementation, shown on FIG.
15.
On the other hand, the single memory implementation requires considerably
more memory than the two memory implementation. For example, if in the
single memory implementation, shown in FIG. 15, the x value required 3
bits of data, y required 3 bits, IL<x,y> required 8 bits, and 4 bits of
data are required for the number of output levels, the memory required for
single LUT 491 would be 2.sup.14 .times.4 bits=65536 bits total. Assuming
the same parameters for the two memory implementation, shown in FIG. 6,
dither template memory 82 would require 2.sup.6 .times.8 bits and
quantizer LUT 86 would require 2.sup.9 .times.4 bits, for a total of 2560
bits.
Thus, for the values of the example discussed above, the memory
requirements for the two memory implementation are approximately 25 times
smaller than the memory requirements for the single memory implementation;
however, the two memory implementation is slower than the single memory
version.
E. Multilevel Dithering System with Bit Shifter
Thus far the embodiments of the multi-level image processing systems and
techniques of the present invention have been premised upon the
understanding that the input device could have any number of input levels.
In such embodiments, the number of input levels are a fixed parameter
given to the image processor by the imaging system, and that information,
along with other information, is processed by the image processor to
determine the output levels.
In yet another embodiment of the image processor, it is possible to use a
bit shifter in place of the quantizer LUT. The embodiment is based on
having the average number of unique "S" values which can be produced by an
adder, such as adder 85 shown in FIG. 6, and which `map to` a single
output level, as the meaning of the term `map to` is hereinbelow refined,
equal to an integer power of two.
Referring momentarily back to the discussion surrounding Equation V, there
it was determined that the average number of unique S values which can be
produced by adder 85 and which map to a single, given output level could
be determined by computing the average number of unique S values that
address the same output level stored in quantizer LUT 86.
In the bit shifter implementation there is no quantizer LUT; however, there
is a bit shifter which operates in place of the quantizer LUT. As will be
detailed below, the output of the bit shifter is the output level produced
by the image processor. Accordingly, in the bit shifter embodiment a
unique S value is considered to map to a single, given output level if,
after that S value is produced by the adder and processed by the bit
shifter, the resulting value of S is equal to the given output level.
For example, assume a given bit shifter is programmed to shift incoming
binary data four bits to the right. The results of that bit shifter
processing five S values are shown in Table D.
TABLE D
______________________________________
S value Shifted S value
______________________________________
00110101 0011
00111111 0011
00110000 0011
11000101 1100
11001111 1100
______________________________________
In this particular example, three of the unique S values would be
considered to map to the output level 0011 because their resulting value,
after processing by the bit shifter, is equal to the given output level,
0011. On the other hand, two of the unique S values would be considered to
map to the output level 1100 because their resulting value is equal to
output level 1100.
As discussed in connection with the embodiment of the invention shown in
FIG. 6, in order to determine what the average number of unique S values
that map to a given, unique output level are, it is necessary to determine
the finite numbers of possible addends to be added by the adder, and
compute all of the possible S values. After the total number of possible,
unique S values are determined, they must be processed by the bit shifter
to determine the number of S values that map to a given output level.
Therefore, in the bit shifter implementation, .DELTA..sub.Q is understood
to represent the average value of the number of unique S values that map
to a single, given, output level, if all possible S values were produced
by an adder and shifted by the bit shifter.
Accordingly, the term map to in the context of the bit shifter
implementation is somewhat refined relative to the other specific
embodiments discussed above.
Recalling that .DELTA..sub.Q is defined as being equal to the average
number of unique S values which can be produced by the adder and which map
to a single, given output level and further recalling that the average
number of unique S values which can be produced by the adder and which map
to a single, given output level is equal to an integer power of two, these
two features of the bit shifter implementation can be summarized in the
expression:
.DELTA..sub.Q =2.sup.R, (Equation X).
where R is the number of bits the bit shifter shifts to the right.
In light of Equation X, in particular embodiments of the bit shifter
implementation, the bit shifter may have to have the freedom to assign the
range of input levels which will be transmitted to the image processor by
other components within the imaging system, such as input device 22 shown
in FIG. 1.
It should be noted that although most imaging systems are designed so that
the number of input levels are fixed, in the case of some imaging systems
that generate synthetic graphics, the number of input levels can be set to
any number. In addition, even conventional imaging systems which have a
fixed number of input levels can be made to have any number of assignable
levels through the implementation of an image adjustment system. As will
be detailed below in the section heading "Image Adjustment System", an
image adjustment system can translate any number of raw input levels to a
greater or lesser number of adjusted input levels, as needed.
Before proceeding with the more detailed discussion of the bit shifter
embodiment, it should be noted that if in a given imaging system Equation
X can be satisfied, possibly through the implementation of an image
adjustment system, then a bit shifter can substitute in place of quantizer
LUT 86, shown on FIG. 6. This is because it has been found that if
quantizer LUT 86 is segmented so that the number of unique S values that
map to each output level is equal to a power of 2 (i.e. 2.sup.R), then an
equivalent way to achieve quantization is by shifting each given S value R
bits to the right. This shifting will produce the appropriate output level
value. Thus, if the system has the capabilities discussed above, the bit
shifter embodiment simplifies the overall system, especially if
implemented in hardware.
Referring momentarily back to FIG. 1, the objective of the bit shifter
implementation is the same as the previous implementations of the image
processing technique. Namely, in FIG. 1 during operation input device 22
will transfer to IP 40 the input level occurring at a given input cell,
IL<x,y> and IP 40 will translate that input level to a corresponding
output level occurring at a given output cell OL<x,y>. That output level
is then transmitted to an output device 30.
Now referring to FIG. 19, an alternative IP 740 is shown which could be
substituted in place of IP 40 shown in FIG. 1. IP 740 includes a system
data generator 720 and bit shifter run time system 781 (BSRTS), which is
shown in dashed lines. As in previous embodiments of the present
invention, in those instances in which there is a correlation between the
reference numbers of block elements in FIGS. 19 and 20, and previously
described embodiments of the invention, the reference numbers will
correlate except that the reference numbers in FIGS. 19 and 20 are in the
700's. One notable difference is that the quantizer LUT 86 of FIG. 6 has
been replaced with shifter 722 in FIG. 19.
BSRTS 781 includes a dither template memory 782, which is initialized with
values d<x',y'> by data system generator 720. In addition, data system
generator 720 also furnishes a signal "R" to shifter 722, in which R
corresponds to the number of bits that numbers transmitted to shifter 722
should be shifted. In this particular embodiment, shifter 722 will shifter
data R bits to the right.
BSRTS 781 further includes an address modifier circuit 787, which is used
to convert addresses x,y of an input cell 26 of input device 22, shown on
FIG. 1, to addresses x',y' which are applied as an address to access the
values stored in dither template memory 782. The output of dither template
memory 782, d<x',y'>, are fed to an adder 785. Adder 785 is also fed an
input level, IL<x,y>, for the given input cell 26, and the two values are
added by adder 785 to produce a sum value, S. In this particular
implementation, S is then processed by shifter 785, in particular, the
number S is shifted R bits to the right. The bit shifted number is then
output by shifter 722 as the output level OL<x,y> which corresponds to
IL<x,y>. As in prior implementations, OL<x,y> is fed to the output device
30 of FIG. 1.
In this embodiment, system data generator 720 determines the d<x',y'>
values which are stored in the dither template memory 782, and the values
of R and NIL. Data system generator 720 does not need to run at any
particular speed since it computes these values before imaging system 20
starts translating input pixels to output pixels during real time
operation. Thus, after data system generator 720 determines and stores
these values, it will resume activity only if some of the imaging system
20 parameters change.
BSRTS 781 is the portion of IP 740 which operates in real time, and during
operation it is constantly receiving input values IL<x, y>, from input
array 2 4, shown in FIG. 1, and processing them into corresponding output
values, OL<x,y>, in output array 34.
IP 740, and in particular, data system generator 720 is fed by signals
corresponding to: the number of output levels, NOL; the number of dither
template levels, NTL; the dither template order, T<x',y'>; phase.sub.-- x
and phase.sub.-- y values; the dimensions of the dither template memory,
M.sub.mm .times.N.sub.mm ; and the number of bits of the input level, B.
Address modifier 787 is fed the x and y address values for a given input
cell, x,y, and adder 785 is fed the actual input level of the given input
cell at the x, y address, IL<x,y>.
It should be noted that unlike prior implementations, in this embodiment IP
740 is not fed a signal which corresponds to the number of input levels,
NIL, of the input device. Instead, data system generator 720 uses the
inputs provided to it to compute the NIL, which is fed back to input
device 20 of FIG. 1. With the assignment of NIL by IP 740, input device 20
will then transmit the correct range of input levels to IP 740 during real
time operation.
Although it may appear initially that there are no system parameters
affecting the number of input levels which the data system generator 720
may assign, in fact the number of bits, B, of the input level does force a
type of limitation. More particularly, imaging system 20 of FIG. 1 will
assign a number of input levels such that:
2.sup.B-1 <NIL.ltoreq.2.sup.B (Equation XI).
Accordingly, IP 740 will assign a number of input levels which, at a
minimum, takes advantage of all of the bits allocated for the input
levels, but does not exceed the maximum number of levels which can be
represented by the given number of bits.
By combining Equation I with Equation X it is seen that:
.DELTA..sub.Q =2.sup.R =(NIL-1)(NOL-1).
Using this relationship, and Equation XI, a solution for R is provided by:
R=int}log.sub.2 (2.sup.B -1)/(NOL-1)} (Equation XII).
Referring now to FIG. 20, data system generator 720 is shown to include a
variables determiner circuit 790 which is fed by signals corresponding to
NOL, NTL, and B to provide data signals representing: R, the number of
bits shifter 722 will shift incoming data to the right's .DELTA..sub.d,
the subdivisions of the quantization levels; Offset, the dimension of the
offset at the endpoints of the input levels; and NIL, the number of input
levels transmitted to IP 740 by input device 20 of FIG. 1. The variables
determiner circuit uses any conventional arithmetic circuit to provided
these values by solving the equations discussed below.
System data generator 720 is shown to further use a memory device, which
could be the same memory device used for dither template memory 782, for
the temporary storage of a suitable dither template. An exemplary template
will be discussed in conjunction with FIG. 22A. Dither template values,
T<x'y'>, are shown stored on FIG. 20 as reference numeral 753. They are
fed to dither normalizer 796 which adjusts the dither template values so
that they are made to be symmetrically distributed between 0 and the
average value of the number of unique S values that map to a single, given
output level, if all possible S values were produced by adder 785 and
shifted by shifter 722.
The output from the dither normalizer 796 as stored is shown by reference
numeral 797, and these values are fed into phase adjuster circuit 798
along with phase.sub.-- x, phase.sub.-- y, and M.sub.mm .times.N.sub.mm
signals. Phase adjuster 798 processes the values by spatially shifting the
elements within the dither matrix. Thus, the elements of the dither matrix
which have a particular location within the matrix prior to phase
adjustment, are adjusted to a different location within the dither matrix
on the basis of the phase.sub.-- x and the phase.sub.-- y values. The
resulting values, d<x',y'> are then stored in dither matrix memory 782,
shown on FIG. 6.
In order to illustrate how system data generator 720 operates, a simple
example will be developed through which actual values will be assigned to
the various input signals to see how those values are processed through IP
740. As with previous examples, small numbers are used for the purpose of
illustrating the principles underlying the embodiment of this invention.
In addition to FIG. 20, FIG. 21 includes a flow diagram, showing the steps
of the process, which can be read in conjunction with FIG. 20.
In this example, it will be assumed that the following signals are provided
to IP 740 by the imaging system 20 of FIG. 1.
TABLE E
______________________________________
NOL = 4
NTL = 4
Element ordering is:
1 2
3 0
M.sub.mm = 8
N.sub.mm = 8
Phase.sub.-- x = -1
Phase.sub.-- y = -1
B = 9
______________________________________
As shown in FIG. 20 variables determiner 790 receives NOL and B and uses
that information to compute R (Step 810, FIG. 21) using Equation XII,
above. The signal representing the R value is then forwarded to shifter
722 so that it will be able to shift the numbers forwarded to it by adder
785 by R bits to the right (Step 811, FIG. 21).
In addition to determining R, variables determiner 790 also computes
.DELTA..sub.d (Step 812, FIG. 21), which is the range of input levels
which are covered by a given output level. Variables determiner 790
computes .DELTA..sub.d using the equation:
.DELTA..sub.d =2.sup.R /NTL (Equation XIII.
)
Finally, variables determiner 790 computes the NIL for input device 22 of
the imaging system 20 of FIG. 1 (Step 814, FIG. 21). This is accomplished
using the equation:
______________________________________
NIL = (NOL - 1)2.sup.R, if .DELTA..sub.d > 1, and
(NOL - 1)2.sup.R + 1, if .DELTA..sub.d .ltoreq. 1.
(Equation XIV.)
______________________________________
After this computation by variables determiner 790, NIL is transmitted back
to input device 22 so that it is able to provide input levels consistent
with the limits assigned by IP 740 (Step 816, FIG. 21).
Using the specific values provided in Table D and Equations XII, XIII, and
XIV variables determiner 790 would compute the following values:
R=7;
.DELTA..sub.d =32.00; and
NIL=384, where the input levels range from 0 through 383.
Still referring to FIG. 20, system data generator 720 also receives as an
input the dither template, T<x',y'>, which can be expanded to fill the
entire dimension of the dither matrix memory 782, in the manner discussed
above (Step 820, FIG. 21). FIG. 22A shows the dither template of Table E
in its fully expanded form. As shown in FIG. 20, dither template,
T<x',y'>, is combined with .DELTA..sub.d in dither normalizer 796 to
normalize the dither template values by symmetrically distributing the
dither template values between 0 and the average value of the number of S
values that map to a single, given output level, if all possible S values
were produced by adder 785 and shifted by shifter 722. (Step 822, FIG.
21). In this particular embodiment dither normalizer uses the equation:
D<x',y'>=int{.DELTA..sub.d (T<x',y'>+1/2)} (Equation XV.)
The resulting dither template values after they are run through dither
normalizer 796 are shown on FIG. 22B.
Finally, in phase adjuster 798 the D<x',y'> values are spatially shifted
within the dither template memory, including the wrapping of the right
side with the left and the bottom with the top, discussed above (Step 824,
FIG. 21). Phase adjuster 798 uses the values for phase.sub.-- x,
phase.sub.-- y, M.sub.mm, and N.sub.mm. At this stage of the technique,
there is a two dimensional, spatial shift of the elements within the
dither matrix. Thus, the elements of the dither matrix which have a
particular location within the matrix prior to phase adjustment, are
adjusted to a different location within the dither matrix on the basis of
the phase.sub.-- x and the phase.sub.-- y values.
In the embodiment shown on FIG. 20, the D<x',y'> values, phase.sub.-- x,
phase.sub.-- y, M.sub.mm, and N.sub.mm are combined in the following
equation for the purpose of outputting d<x',y'>, which is the final value
that is stored in dither template memory 782 (Step 826, FIG. 21). The
equation is:
d<x',y'>=D<(x'+phase.sub.-- x)modulo(M.sub.mm), (y'+phase.sub.--
y)modulo(N.sub.mm) (Equation XVI).
FIG. 223 shows what the values stored in dither template memory 782 would
be for the exemplary values of Table E.
With the values for R, NIL, and d<x',y'> having been computed, transmitted,
and stored in their respective locations within imaging system 20 (Step
840, FIG. 23), BSRTS 781 is in a position to begin receiving input levels
from input device 22, shown in FIG. 1, and translating them to output
levels for registration by output device 30 during real time operation.
Referring back to FIG. 19, a more detailed explanation of the real time
operation of IP 740 can now be provided.
During operation address modifier 787 receives the x,y address of a
specific input cell 26 from input device 22, and it adjusts that address
to x',y', using Equation VIII, discussed above, to access dither template
memory 782 (Step 832, FIG. 23). In response to the x',y' address, dither
template memory 782 will output the corresponding d<x',y'> value stored at
x',y' to adder 785. (Step 834, FIG. 23). That d<x',y'> value gets added to
IL<x,y> by adder 785 (Step 836, FIG. 23), and the resulting sum, S, is
forwarded to shifter 722 (Step 840, FIG. 23). As indicated above, shifter
722 will then shift the binary number S, R bits to the right (Step 842,
FIG. 23). The resulting shifted binary number is then output by shifter
722 as OL<x,y> (Step 844, FIG. 23). OL<x,y> is then output to output
device 30 as the output level, OL<x,y>, which corresponds to the input
level, IL<x,y>.
Referring now to FIG. 24, a table is provided which shows the range of
input levels for the example discussed in connection with FIGS. 19 through
23. FIG. 24 shows the range of input levels, the total number of inputs,
and the perceived output levels achieved by passing every input level from
IL=0 to IL=383 in combination with every address from <x,y>=<0,0> to <7,7>
through IP 740. As shown on FIG. 24, there are 4 true levels, and 9
intermediate levels which are the effective results of the dithered
average. Similar to the discussion in connection with FIG. 11, above,
these numerical averages indicate that a person viewing output device 30
would visually average the output patterns and perceive an image level
equivalent to the average value indicated.
F. Image Adjustment System
In the embodiments of the imaging system 20 discussed thus far, the image
processor, such as IP 40 shown on FIG. 1, receives input levels, IL<x,y>,
which are translated into output levels, OL<x,y>. In yet a further
embodiment of the imaging system 20 of the present invention, an image
adjustment system (IAS) circuit may be used in conjunction with the
previously discussed image processors, such as IP's 40, 140, 440 and 740.
The purpose of the IAS is to take the "raw" input levels, RIL<x,y>, of an
input device, such as input device 22 shown on FIG. 1, and translate those
raw input levels into "adjusted" input levels, simply referred to as
IL<x,y>. In this context, the term "raw" refers to the input level which
is input into the IAS, and the term "adjusted" refers to the input level
output by IAS. Through this approach, an improved output image can be
produced by the imaging system 20. Due to the method by which the IAS is
implemented, the translation of the raw input levels to adjusted input
levels is accomplished very quickly, as will be detailed below.
Additionally, the raw input levels are the levels that are fixed by other
parameters of imaging system 20, such as the number of actual input levels
produced by input device 22. On the other hand, adjusted input levels are
assigned by imaging system 20, and are not dictated by other system
parameters. Therefore, the adjusted input levels may be varied by imaging
system 20, and the significance of this feature will be further discussed
below.
Referring to FIG. 25, which is based on FIG. 1, an imaging system 20 is
shown to include an input device 22 coupled to an output device 30 through
an IP 40. In FIG. 26, IP 40 includes IAS 1020. IAS 1020 has a number of
adjustment interfaces 1021, which, in one embodiment, can be manually
adjusted by an operator to refine the output image of output device 30.
For example, interfaces 1021 may be manipulated by a person to affect the
way in which IAS 1020 transforms raw input levels to adjusted input
levels. Changes in the settings of the user interfaces, would result in
changing the output image produced in output device 30, shown on FIG. 25.
In addition to the user interfaces, IAS 1020 also receives signal
information from other sensors or switches in imaging system 20. Together
the information provided through those signals and the signals provided by
the user interfaces are used to translate RIL<x, y> values to IL<x, y>
values in the manner detailed below.
Before detailing an embodiment of IAS 1020, it is necessary to first
generally address the various ways by which IAS 1020 can be used to refine
the raw inputs which it receives. This
explanation is best provided by beginning with a graphical representation
of the way in which IAS 1020 converts raw input levels to adjusted input
levels. As will be detailed below, the values that are computed in the IAS
1020 are eventually stored in an adjust LUT. The adjust LUT is structured
such that the input to the LUT is an RIL<x,y>, which operates as an
address to the LUT. Thus, each RIL<x,y> transmitted to the adjust LUT will
result in the outputting of a corresponding IL<x,y> by the adjust LUT.
FIGS. 26-35 provide graphical representations of how an input of RIL<x,y>
value, shown on the x-axis, will produce an output of a corresponding
IL<x,y> value, shown on the y-axis. In these graphical representations,
the correspondence is determined by the positioning of the transform line
shown on each of the graphs in the respective figures. Consistent with the
conventional method of reading x--y graphs, the transform line determines
the exact IL<x,y> value on the y-axis which corresponds to a given
RIL<x,y> value on the x-axis. As will be detailed through FIGS. 26-35,
changes in the positioning of the transform line have the consequence of
changing the mapping of RIL<x,y> values to IL<x,y> values.
For example, FIG. 26 provides a graph in which the x-axis represents a
number of raw input levels (NRIL) ranging from 0 to (NRIL-1), and the
y-axis represents a number of adjusted input levels (NIL), ranging from 0
to (NIL-1). The x-axis is bisected by (NRIL-1)/2, and the y-axis is
likewise bisected by (NIL-1)/2. In this particular illustration, NRIL is
equal to NIL.
The graph of FIG. 26 further includes identity transform line 920, which
diagonally extends across the graph and, by definition, has a "Steepness"
equal to 0. Identity transform line 920 reflects that at the particular
setting of the image adjustment system each RIL<x,y> value is translated
to an identical IL<x,y> value. For example, RIL.sub.a equals IL.sub.a,
showing that each raw input level has the exact same value as its
corresponding adjusted input level. Thus, this particular setting of
transform line 920 defines the identity function, in which each RIL<x,y>
value is translated to an identical IL<x,y> value.
Referring now to FIG. 27, a graph similar to FIG. 26 is provided. In
addition to identity transform line 920, however, vertical line 922 and
horizontal line 924 are provided with vertical line 922 defined as having
a Steepness of (+1), and horizontal line 924 having a Steepness of (-1).
The dashed transform lines 925, 927 show intermediate positive and
negative Steepnesses, with identity transform line 920 being the reference
line against which positive and negative Steepness is determined. As
shown, the intermediate positions are achieved by pivoting transform line
920 about point 929.
In several of the Figures, such as FIGS. 27, 29A, and 30A, there are a
number of transform lines that appear on one single graph. Consequently,
from the graph it appears that a given RIL<x,y> value will map to multiple
IL<x,y> values. It should be noted that IAS 1020 will assign only one
IL<x,y> value to any given RIL<x,y> value. Those graphs on which multiple
transform lines are included are not for showing the mapping of a given
RIL<x,y> value, but rather for illustrating and defining the properties of
the transform line, especially by means of contrasting one line on the
graph to another.
FIG. 28 includes a graph which is similar to the graph of FIG. 27; however,
FIG. 28 includes transform line 926, alone. As shown, because the
Steepness setting is not in the identity position, the RIL<x,y> values are
not necessarily mapped to identical IL<x,y> values. For example, on the
graph RIL<x,y> values ranging from 0 to RIL, are all mapped to IL=0. Also,
RIL<x, y> values ranging from RIL.sub.b to (NRIL-1) are all mapped to
(NIL-1). Consequently, a narrower range of values, namely RIL.sub.a to
RIL.sub.b, will encompass all of the IL<x,y> values from 0 to (NIL -1).
FIG. 28 also graphically shows how the adjustment of the Steepness setting
affects the translation of RIL<x,y> values to IL<x,y> values by IAS 1020.
In order to describe the purpose of the Steepness variable, and other
variables which are discussed below, reference will be made to a number of
different imaging systems which use monochrome or color input or output
devices. Before doing so, it should first be noted that in color systems,
the color images are made up of a number of components. For example, in a
luminance/chrominance color system, such as a YUV system, Y is one of the
components, which is used to represent a luminance value. Additionally,
there are two chrominance components, namely U and V, which are each used
to represent saturation values. Thus, the YUV color system includes three
components. In another example, such as a color system in which data is
represented in the RGB format, there are likewise three separate
components, namely, red (R) , green (G) , and blue (B) . Such color
systems which have multiple components will have a separate image
adjustment system, such IAS 1020, implemented for each one of the
components. Using the YUV as an example, the Y component will have its own
IAS 1020, the U component will have its own IAS 1020, and the V component
will have its own IAS 1020.
Referring now to more detailed embodiments, if imaging system 20 uses a
monochrome input device, the Steepness adjustment of IAS 1020 could be
used to alter the contrast of the output image. For example, an input
image which has low contrast because the range of all, raw input values is
relatively small, may visually appear to be dull or flat. When projected
on an output device, the image can be improved by adjusting the Steepness
setting so that the small range of raw input levels are expanded to a
wider range of adjusted input levels to give the output image a richer,
sharper appearance. Thus, in the monochrome input device, the Steepness
setting gives a greater or lesser degree of contrast.
On the other hand, in another example, the imaging system may use a color
input device which produces data in a luminance/chrominance format, such
as the YUV format discussed above. As stated, Y represents a luminance
value and U and V each represent chrominance values, and each such
component has its own IAS 1020. In such a color system, the Steepness
setting of the image adjustment system of Y can be used to determine the
contrast of the output image. On the other hand, the Steepness settings of
the image adjustment systems of U and V can be used to adjust the
saturation of the output image. Although the image adjustment systems for
U and V are independent of one another, and therefore may have different
Steepness settings, it has been found that a desirable output image is
produced from having the Steepnesses of the U and V values set the same.
In still another embodiment of a color system which produces data in the
RGB format, the Steepness settings for the image adjustment systems for
the three components, R, G, and B, can be used to adjust the contrast of
the output image. Again, although the three image adjustment systems may
have separate Steepness settings, a desirable output image is produced
with all three Steepnesses set the same.
Referring momentarily back to FIG. 28, three additional terms which will be
significant in connection with the method by which the IAS 1020 determines
the translation of raw input levels to adjusted input levels are defined.
In particular, the point at which RIL<x,y> is first mapped to a non-zero
number, moving from 0 to (NRIL-1) is defined as "Low". Additionally the
point at which RIL<x,y> is first mapped to (NIL-1), moving from 0 to
(NRIL-1) is defined as "High". For ease of reference, (NIL-1) is also
referred to as "Top". The significance of these terms will be detailed
below.
FIG. 29A includes a graph which is similar to the graph of FIG. 27. FIG.
29A includes identity transform line 920, and includes the positioning of
other transform lines on the graph for the purpose of defining "Xoffset".
The graph of FIG. 29A shows Xoffset adjustments to the right of identity
are defined as positive (+), and Xoffset adjustments to the left of
identity are defined as negative (-). As shown, as Xoffset is adjusted the
positioning of point 929 moves parallel to the x-axis, but retains a
constant y-axis value equal to (NIL-1)/2.
As shown on FIG. 29A, identity transform line 920 is moved parallel to the
x-axis to illustrate two, new transform lines 930, 932. When point 929 of
transform line 930 has an x-axis value equal to (NRIL-1), transform line
930 is defined to have an Xoffset=(+1). Similarly, when point 929 of
transform line 932 has an x-axis value equal to 0, transform line 932 is
defined to have Xoffset=(-1). The dashed transform lines 934, 936 show
intermediate positive and negative Xoffset positions.
FIG. 29B includes a graph, which is similar to FIG. 28, showing the single
transform line 940. Transform line 940 is the result of adjusting the
Xoffset of identity transform line 920, of FIG. 26, in the positive
direction. In this instance, the RIL<x,y> values from 0 to RIL.sub.a are
mapped to IL=0 while the remaining RIL<x, y> values, from RIL.sub.a to
(NRIL-1) are mapped to the values between 0 and IL.sub.y. Again, FIG. 29B
provides a graphical illustration of how adjustments to Xoffset affect the
transformation of RIL<x, y> values to IL<x, y> values.
In an imaging system 20, which uses a monochrome input device 22 for
example, the Xoffset is redundant if the image adjustment system has a
Yoffset. As will be discussed below, in such a system, the Yoffset is used
to adjust the brightness of the monochrome image, and the Xoffset would
serve no particular function. Likewise, if imaging system 20 produces data
in an RGB format, Xoffset is also superfluous. In such image adjustment
systems, a variable which is not needed can be set to zero.
On the other hand, as discussed above, if the input device 22 of imaging
system 20 produces data in a luminance/chrominance format, such as the YUV
format, then there will be a separate IAS 1020 for Y, U, and V. The
Xoffset setting of the image adjustment system for the luminance, or Y
value, is superfluous; however, the Xoffset settings of the image
adjustment systems for U and V can be used for the purpose of achieving so
called "white balance control" of the output image.
As is known in the imaging art, certain input devices are calibrated based
on the assumption that the input image recorded under particular lighting
conditions. For example, if a given video camera is calibrated for
daylight, but is used to record an input image illuminated by an
incandescent light, the image may appear too reddish. In a color system,
the Xoffset settings of the image adjustment systems of the chrominance
components are used to correct such color errors by adjusting the location
of point 929 relative to the x-axis. Given that the chrominance components
of the raw input levels are transformed on the basis of the location of
point 929, Xoffset thereby determines the color translation, and is used
to achieve the proper white balance control.
Similar to the foregoing graphs, FIG. 30A shows identity transform line
920, and a number of other transform lines used to define Yoffset. As
shown, Yoffset adjustments upward on the graph are defined as positive
(+), and Yoffset adjustments downward are defined as negative (-). As
shown, as Yoffset is adjusted the positioning of point 929 of identity
transform line 920 moves parallel to the y-axis, but retains a constant
x-axis value equal to (NRIL-1)2.
As shown on FIG. 30A, identity transform line 920 is moved parallel to the
y-axis to illustrate two, new transform lines 944, 946. When point 929 of
transform line 944 has a y-axis value equal to 0, transform line 944 is
defined to have a Yoffset =(-1). Similarly, when point 929 of transform
line 946 has a y-axis value equal to (NIL-1), transform line 946 is
defined to have a Yoffset=(+1). The dashed transform lines 950, 952 show
intermediate positive and negative Yoffset positions.
FIG. 30B includes a graph which is similar to FIGS. 28 and 29B, including
the single transform line 954. Transform line 954 is the result of
adjusting the Yoffset of identity transform line 920, of FIG. 26 in the
positive direction. The RIL<x,y> values on FIG. 30B ranging from 0 to
RIL.sub.x are mapped to IL<x,y> values ranging from IL.sub.a to (NIL-1).
The remaining RIL<x,y> values, from RIL.sub.x to (NRIL-1) , are mapped to
(NIL-1) . FIG. 30B also provides a graphical illustration of how
adjustments to the Yoffset setting affect the transformation of RIL<x,y>
values to IL<x, y> values .
In an imaging system 20 having the exemplary monochrome input device, the
Yoffset could be used to adjust the brightness. This is because in the
monochrome system as point 929 is adjusted along the y-axis, a greater or
lesser number of raw input levels are mapped to the lighter or darker
adjusted input levels. Thus the brightness of the image may be adjusted by
the Yoffset.
On the other hand, if imaging system 20 includes an input device 22 based
on the luminance/chrominance color system, the Yoffset settings of the two
image adjustment systems for the chrominance components would be
superfluous, given that white balance control is achieved by adjusting the
Xoffset, as described above. However, the Yoffset of the image adjustment
system used for the luminance component can be used to control the
brightness of the output image.
Referring again to an imaging system 20 in which color is produced in the
RGB data format, the Yoffset settings of the image adjustment systems of
each of the three components can be used to adjust the brightness of the
output image. Again, a uniform setting for all three is preferred.
One of the features of input device 22 and output device 30 of imaging
system 20, shown on FIG. 1, is that they may each have their own
respective "sense". By definition, the "sense" of an input or output
device is the logical meaning that the given device ascribes to the binary
value 0. For example, the given "sense" of a monochrome input device will
determine whether that particular input device treats the value 0 as
representing the highest or lowest value, such as black or white for
example. Likewise, the sense of a bi-tonal or monochrome output device
determines whether it treats the value 0 as representing the highest or
lowest value. A similar meaning relating to the assignment of values
applies to the components of a color system.
Also, in any given imaging system 20 it is not necessarily the case that
the sense of the input device is the same as the sense of the output
device. In the event that the senses of the input and output devices are
not coordinated in a given imaging system, the output images may be
projected in the manner opposite to the manner in which they should be
projected. Consequently, under such circumstances the output images may
look like a photographic negative, for example.
Accordingly, IAS 1020 determines from both the input device 22 and the
output device 30 what their respective senses are. In response, IAS 1020
will then determine whether it needs to reverse the sense of the input
device, thereby activating a "ReverseIn" operation. IAS 1020 will also
determine whether it needs to reverse the sense of the output device,
thereby activating a "ReverseOut" operation.
It should be noted that the transform line modifiers discussed up to this
point - - - Steepness, Xoffset, Yoffset - - - are modifiers which are
manipulated through user interfaces, such as interfaces 1021 shown on FIG.
25. ReverseIn and ReverseOut, on the other hand, are responsive to
instruction signals provided by components within imaging system 20, such
as input device 22 or output device 30. Additionally, these signals could
be provided in a file header of the data being processed by imaging system
20. ReverseIn and ReverseOut can only have one of two states, those being
either an asserted (on) or de-asserted (off) state. As discussed, whether
the state is asserted or de-asserted is determined on the basis of the
sense of input device 22 or output device 30.
Referring now to FIG. 31, the effect ReverseIn has on transforming RIL<x,y>
values to IL<x,y> values is graphically shown. Transform line 960 first
defines a given transform expression for mapping RIL<x,y> to IL<x,y>. FIG.
31 shows a dashed, vertical line 962 running through (NRIL-1)/2. By
definition, when "ReverseIn" is asserted, transform line 960 is
effectively rotated 180 degrees about vertical line 962. In this manner
the sense of the data from input device 22 is reversed by the assertion of
ReverseIn. In other words, through the switching of ReverseIn the binary
values of the data forming the input image is reversed such that 0 becomes
1 and 1 becomes 0.
A similar function is shown in FIG. 32, in which the effects of ReverseOut
on transforming RIL<x,y> values to IL<x,y> values is graphically shown. In
FIG. 32, transform line 960 defines the same transform expression as shown
in FIG. 31 for mapping RIL<x,y> to IL<x,y>. FIG. 32 shows a dashed,
horizontal line 970 running through (NIL-1)/2. By definition, when
"ReverseOut" is asserted, transform line 960 is effectively rotated 180
degrees about horizontal line 970. In this manner the sense of the data of
output device 30 is reversed by the assertion of ReverseOut. Similar to
the effect of the ReverseIn function, through the switching of ReverseOut
the binary values of the data forming the output image is reversed such
that 0 becomes 1 and 1 becomes 0.
In certain imaging systems 20, it may be necessary to alter the
representation of signed raw input levels to provide adjusted input
levels. For example, FIG. 33 provides two methods by which signed
information may be represented. In many YUV color systems, for example,
the chrominance component of the image, namely the U and V information, is
presented in a twos complement format. On FIG. 33, next to the twos
complement representation of a given number is the binary code
designation, with the unsigned representation and the sign shifted
representation of the number shown beside the corresponding binary code.
In the event that the representation of the RIL<x,y> value needs to be
changed to provide IL<x,y>, IAS 1020 includes a sign conversion function,
which is operated by "Sign Shift".
Similar to the ReverseIn and ReverseOut functions discussed above, Sign
Shift is either asserted or de-asserted. Also like ReverseIn and
ReverseOut, Sign Shift is not determined by a user interface, but rather
is determined by an instruction signal provided by other components within
imaging system 20, or by a signal provided in the file header of the data
that is being processed by the system.
FIG. 34 provides a graphical representation of the manner by which Sign
Shift transforms RIL<x,y> values to IL<x,y> values. More particularly,
line 974 of FIG. 34 shows the effects of applying the Sign Shift function
to the identity transform line 920 shown on FIG. 26 . Thus, with respect
to the identity transform line 920, the Sign Shift function serves to map
the RIL<x,y> values from 0 to (NRIL-1)/2 to IL<x,y> values from (NIL-1)/2
to (NIL-1). Additionally, RIL<x,y> values from (NRIL-1)/2 to (RNIL-1) are
mapped to IL<x,y> values from 0 to (NIL-1).
Finally, with respect to the translation of raw input levels to adjusted
input levels, FIG. 35 shows the method by which a lesser number of raw
input levels are mapped to a greater number of adjusted input levels.
Unlike the transform function which was illustrated in FIG. 26 in which
NRIL is equal to NIL, in FIG. 35, NRIL is less than NIL. The diagonal
established by transform line 980 shows an identity-like translation of
the raw input levels to adjusted input levels. Even though there are fewer
raw input levels than adjusted input levels, FIG. 35 shows how the raw
input levels would be mapped to a given adjusted input level.
For example, on FIG. 35 RIL.sub.a maps to IL.sub.y, indicating that the raw
input level does not necessarily map to an identical adjusted input level.
This mapping is accomplished in IAS 1020 by means of further adjusting the
transformation line by increasing or decreasing the range of adjusted
input levels. As discussed above, although NRIL is a fixed system
parameter, NIL is variable, and can be assigned by imaging system 20 to
IAS 1020. To the extent that the value of NIL is assignable by imaging
system 1020, IAS 1020 can be used to transform a greater number of raw
input levels to a lesser number of adjusted input levels, or a lesser
number of raw input levels to a greater number of adjusted input levels.
Also, the discussion of the bit shifter implementation, shown in FIGS. 19
and 20 above, was is based on the understanding that IP 740 could assign
the range of input levels it would receive for processing. For those
systems that do not have that inherent capability, it was indicated that
an imaging system with a given, fixed number of input levels could have
that number of input levels adjusted by means of image adjustment system.
As discussed in connection with FIG. 35, IAS 1020 can be used to translate
a given number of raw input levels to either a greater or lesser number of
adjusted input levels. Accordingly, IP 740 of FIG. 19 could be coupled to
IAS 1020 in the manner shown in FIG. 40D, so that when IP 740 determines
the NIL, IAS 1020 will insure that only input levels falling within the
assigned range are sent to IP 740 for processing.
Having discussed the types of adjustments that can be made through the
transform functions so that raw input levels are translated into adjusted
input levels, an embodiment of IAS 1020 can now be addressed. Referring
now to FIG. 36, IAS 1020 includes variables determiner circuit 1120, data
assignor circuit 1122, data store memory 1124, and sign converter circuit
1126. IAS 1020 is shown to include adjust LUT memory 1130, in which values
are ultimately stored.
In FIG. 36, variables determiner 1120 is fed by signals corresponding to:
Steepness, Xoffset, Yoffset, ReverseIn, Reverseout, NRIL, and NIL. As
indicated above, in one implementation the signals for Steepness, Xoffset,
and Yoffset would be furnished by a user interface, such as interface 1021
shown on FIG. 25. These may be similar to the brightness or contrast dial
on a standard video monitor. The other signals for variables determiner
1120, ReverseIn, Reverseout, NRIL, and NIL would be furnished by imaging
system 20, or provided in a file header of data being processed. In
particular, NIL is the variable discussed above which is assigned by
imaging system 20, and which determines whether the number of raw input
levels will be transformed to a greater or lesser number of adjusted input
levels.
Variables determiner 1120 provides values corresponding to m and b, which
are discussed below, and High, Low, and Top to data assignor 1122. Data
assignor 1122 outputs intermediate values, which are collectively referred
to as "A.sub.1 ", which are stored in a memory device, such as data store
1124. The A.sub.1 values in data store 1124 are then transferred to sign
converter 1126. If the Sign Shift signal is asserted, sign converter 1126
will convert the representation of signed values stored in data store
1124. If the Sign Shift signal is not asserted, then the A.sub.1 values
stored in data store 1124 pass through sign converter 1126 without
modification.
Whether sign converter 1126 converts the A.sub.1 values or not, sign
converter 1126 outputs the final table of adjusted values, A<IL>, for
storage in adjust LUT 1130. Once the values A<IL> are stored in adjust LUT
1130, the raw input levels, RIL<x,y>, are used to address the LUT.
Accordingly, a given RIL<x,y> will cause a corresponding, adjusted IL<x,y>
to be produced by adjust LUT 1130.
As indicated above, in certain implementations involving color systems, a
number of IAS's 1020 were used together so that each component of the
color image had its own image adjustment system. In another embodiment, it
is possible to have a single variables determiner 1120, a single data
assignor 1122, and a single sign converter 1126 for processing data that
is stored in an adjust LUT 1130 for the Y component, another adjust LUT
1130 for the U component, and yet another adjust LUT 1130 for the V
component, for an input device based on the luminance/chrominance format.
The same can be done with respect to an input device based on the RGB
format. In other words, instead of duplicating the components of IAS 1020
which process the values that are stored in the LUT's, it is possible to
have one set of components which compute and fill a separate adjust LUT's
1130 for each or the color components.
For example, a single variables determiner 1120, data assignor 1122, and
sign converter 1126 can first process the adjusted input levels that are
stored in an adjust LUT 1130 for the Y component, based on the desired
contrast and brightness of the output image, as well as the senses of the
input and output devices, the representation of signed raw input levels,
and the desired range of input levels. Then those same components can
process the adjusted input levels stored in an adjust LUT 1130 for the U
component, based on the desired saturation and white balance control of
the output image, as well as the senses, the representation, and the
range. And finally, the same components can process adjusted input levels
stored in an adjust LUT 1130 for the V component, again on the basis of
the desired saturation and white balance control of the output image, and
the senses, the representation, and the range.
In yet another example, a single set of variables determiner 1120, data
assignor 1122, and sign converter 1126 can be used to process and store
adjusted input levels in an adjust LUT 1130 for the R component, an adjust
LUT 1130 for the G component, and an adjust LUT for the B component, in an
imaging system in which the input device represents data in the RGB
format.
With this general background on the operation of IAS 1020, reference can
now be made to the flow diagrams which detail how the various signals are
used by the components of IAS 1020 to fill adjust LUT 1130.
Referring now to FIG. 37, the steps of the process are shown to include a
decision step 1150 with variables determiner 1120 testing the Steepness of
the transform line setting to determine if it is greater than zero. If
yes, the process advances to step 1152 in which the variable "m" is made
equal to 1/(1-Steepness). It should be noted that although "m" has not
been previously described, it is a variable which defines the slope of the
transform line, such as the transform lines discussed in connection with
FIGS. 26 through 32, and m is determined by variables determiner 1120.
After the value of m is determined, data assignor 1122 uses that variable
in the manner described herein.
Referring back to decision step 1150, if Steepness is not greater than
zero, then the process advances to step 1154 and m is set as equal to
(1+Steepness). From both steps 1152 and 1154 the process advances to step
1156.
In step 1156 a new variable, b, is made equal to
(NRIL-1)(1+Yoffset-m<1+Xoffset>)/2. Similar to the variable m, b is a
variable which defines the y-intercept of the transform line and its value
is determined by variables determiner 1120. Also like m, b is used by data
assignor 1122 in the manner detailed below.
From step 1156, the process advances to decision step 1160 in which
variables determiner 1120 tests the ReverseIn value to determine whether
it is asserted. If yes, the process advances to step 1162 and b is set
equal to m(NRIL-1)+b, and m is set equal to (-m). If ReverseIn is not
asserted, or after step 1162 resets the value of b and m, the process
advances to decision step 1164.
In decision step 1164, variables determiner 1120 tests the ReverseOut value
to determine whether it is asserted. If yes, the process advances to step
1166 in which b is set equal to NRIL -1-b, and m is set equal to (-m). If
ReverseOut is not asserted, or after step 1166 resets the value of m and
b, the process advances to decision step 1170.
In decision step 1170, variables determiner 1120 tests whether m is equal
to zero. If yes, the process advances to decision step 1172 at which point
the variable "High" is set as equal to NRIL, and the variable "Low" is set
as equal to (-1). Both High and Low were shown and described in
conjunction with the discussion of FIG. 28. In the other hand, if m is not
equal to zero, then the process advances to step 1174 and High is made
equal to max {(NRIL-1-b)/m, (NRIL-1)}, and Low is made equal to max
{(-b/m), (NRIL-1)}, where "max {A,B}" is defined as being equal to the
greater of A or B.
After the setting of the High and Low values in either step 1172 or 1174,
the process advances to step 1176 in which b is set as equal to b
(NIL-1)/(NRIL-1) , m is set equal to m (NIL-1)/(NRIL-1). It should be
noted that this is the point of the process in which the number of input
levels, NIL, assigned by imaging system 20, is factored into the shaping
of the transform line. This number determines how raw input levels are
transformed to adjusted input levels. In particular, the actual value of
NIL will determine whether the raw input levels are transformed to a
greater or lesser number of adjusted input levels.
Additionally, in Step 1176 "Top" is set as equal to NIL. Like the variables
High and Low, Top was also shown and discussed in connection with FIG. 28.
After step 1176, the process advances to step 1180 in which the values for
m, b, High, Low, and Top are transferred to data assignor 1122, which is
shown in FIG. 37.
It is notable that at this point of the process all of the variables which
are needed for the purpose of translating RIL to IL have been produced by
IAS 1020. In particular, for a monochrome imaging system, variables
determiner 1120 has produced a set of variables which take account of the
senses of the input and output devices, the number of input levels to be
processed by the image processor, and the desired contrast and brightness
of the output image. On the other hand, for a color system, variables
determiner 1120 has produced a set of variables which take account of the
senses of the input and output devices, the number of input levels to be
processed by the image processor, and the desired saturation, luminance,
and white balance control of the output image. Having computed these
variables, IAS 1020 is now in a position to rapidly produce the variables
which are inserted in adjust LUT 1130. This is accomplished in data
assignor 1122.
Referring now to FIG. 39, at the beginning of the process, step 1190 shows
that signals corresponding to the values for m, b, High, Low and Top have
been transmitted to data assignor 1122. The process then advances to
assigning the value zero to the variable "x" in step 1192. After this, the
process advances to decision step 1194 in which data assignor 1122 tests
the value of m to determine if it is less than zero. As seen by looking at
the flow diagram provided in FIG. 38, if m is not less than zero, then the
process advances through the left branch of the flow diagram. If m is less
then zero then the process advances through the right branch of the flow
diagram. These two branches are separate, and do not reunite until the
bottom of the flow diagram, therefore each complete branch will be
discussed independently of the other.
If decision step 1194 is answered in the negative because m is not less
then zero, the process advances to decision step 1196, at which point data
assignor 1122 tests x to determine whether x is greater than Low. If not,
then A<x>, which at this stage of the process is A<0>, is set equal to
zero. In other words, referring back to FIG. 36, the address location 0 of
data store 1124 is loaded with the value 0 by data assignor 1122.
Additionally, x is incremented by one in step 1220.
From step 1220 the process returns to the test of decision step 1196. To
the extent that x is incremented in step 1120 it may no longer be less
than Low. If it is still less then Low, then the process will continue to
cycle through steps 1196 and 1220. As long as the cycling continues, the
various values of x will determine the address locations of data store
1124 at which a 0 value is stored. For example, if when x=1, it is still
not greater than Low, then A<1> will be set equal to 0, or address
location 1 of data store 1124 will have the value 0 stored therein. Also,
if when x=2, it is not greater than Low, then A<2> will also be set equal
to 0, and address location 2 will have the value 0.
Due to the incrementation of x, it will eventually be greater than Low. At
that point, decision step 1196 will be answered in the affirmative, and
the process advances to step 1222. In step 1222 the variable "y" is set
equal to (mx+b+1/2) .
After step 1222, the process advances to decision step 1224 in which data
assignor 1122 tests the value of x to determine if it is greater than
High. If x is not greater than High, then the process advances to step
1226 in which A<x> is set equal to int{y}. As discussed above, at this
stage of the process, the actual value of int{y} is stored in the x
address of data store 1124.
After the computation of the value of int{y} and the storage of that value
in data store 1124, step 1226 further includes setting y equal to y+m, and
x is set equal to x+1. After these settings the process cycles back to
decision step 1224 to determine if x is greater than High. Until x is
greater than High, the process continues to cycle back through step 1226
and the values of int{y} are stored in there corresponding address
locations in data store 1124. Again, due to the incrementation in step
1226, the answer to decision step 1224 will eventually be in the
affirmative, at which point the process will advance from decision step
1224 to decision step 1230.
In decision step 1230 data assignor tests x to determine if it is less than
NRIL. If yes, the process advances to step 1232 in which A<x> is set equal
to Top. As in the previous steps, 1220 and 1226, this value is stored in
the x address of data store 1124. After the storage of that value, x is
set equal to x +1.
From step 1232 the process returns to decision step 1230. The process
continues to cycle through steps 1230 and 1232 until x is not less then
NRIL, which must eventually occur as a result of the incrementation of x
in step 1232. During this cycling, the address locations of data store
1124, A<x> are filled with the value Top.
When decision step 1230 is answered in the negative the process advances to
step 1234 in which shows that all A.sub.1 values have been loaded in data
store 1124.
Returning to decision step 1194 on FIG. 38, if data assignor 1122 tests m
to determine if it is less then zero and the answer is yes, then the
process advances to decision step 1240 at which point data assignor 1122
tests x to determine whether x is greater than High. If not, then A<x> is
set equal to Top, and x is incremented by one in step 1242. As previously
discussed, the Top value is stored in the x address location of data store
1124.
From step 1242 the process returns to the test of decision step 1240. If x
is still not greater than High, the process will continue to cycle through
steps 1240 and 1242. During the cycling the corresponding address
locations of data store 1124 are filled. Due to the incrementation of x,
it will eventually test greater than High and decision step 1240 will be
answered in the affirmative, advancing the process to step 1244. In step
1244 the variable "y" is set equal to (mx+b+1/2).
After step 1244, the process advances to decision step 1246 in which data
assignor 1122 tests the value of x to determine if it is less than Low. If
x is not less than Low, then the process advances to step 1250 in which
A<x> is set equal to int{y}, and that value is stored in data store 1124.
Then, y is set equal to y+m, and x is set equal to x+1. After these
settings the process returns to decision step 1246 to determine if x is
less than Low. Due to the incrementation in step 1250, the answer to
decision step 1246 will eventually be in the affirmative, at which point
the process will advance from decision step 1246 to decision step 1252.
During the cycling, the address locations of data store 1124 are filled
with values corresponding to int{y}.
In decision step 1252 data assignor tests x to determine if it is less
NRIL. If yes, the process advances to step 1254 in which A<x> is set equal
to zero, and that value is stored in data store 1124 Also, in step 1254 x
is set equal to x+1. From step 1254 the process returns to decision step
1252. The process continues to cycle through steps 1252 and 1254 until x
is not less then NRIL, which must eventually occur as a result of the
incrementation of x in step 1254. During that cycling, the address
locations in data store 1124 corresponding to A<x> are filled with the
value 0.
When decision step 1252 is eventually answered in the negative the process
advances to step 1234, discussed above, showing that all A.sub.1 values
have been loaded in data store.
Referring momentarily back to FIG. 36, sign converter 1126 is responsive to
the signal for Sign Shift and NIL. In the event that Sign Shift is
asserted, sign converter 1126 will shift the sign representation of all of
the A.sub.1 values transmitted to it by data store 1124.
Now referring to FIG. 39, a flow diagram is provided which describes the
process by which sign converter 1126 operates. At the beginning of the
process, step 1260 shows that the A.sub.1 values are stored in data store
1224, shown on FIG. 36. From this step, the process advances to decision
step 1262, which tests whether the Sign Shift signal is asserted. If no,
then the signs of the values do not have to be converted, and the A.sub.1
values effectively pass through sign converter 1126 unchanged. Thus, the
process advances to step 1264, and the values A<IL>, which are the fully
adjusted values, are stored in adjust LUT 1130.
On the other hand, if the Sign Shift signal is asserted, and decision step
1262 is answered in the affirmative, the process advances to step 1266. In
step 1266 the variable "i" is set equal to zero, and the variable "j" is
set equal to NRIL/2.
From step 1266 the process advances to decision step 1270 in which sign
converter 1126 tests i to determine if it is greater than NRIL/2. If no,
the process progresses to step 1272 in which the variable "Hold" is set
equal to A(i), then A(i) is set equal to A(j), then A(j) is set equal to
Hold, then i and j are each incremented by one. Through this step, sign
converter 1126 is effectively swapping the values of A.sub.1 between
memory locations. For example, during the first swap, the value at A<O> is
swapped with the value at A<NRIL/2>. This is accomplished by first making
Hold equal to the value at address location 0, then the value at address
location 0 is made equal to the value at address location NRIL/2, and
finally the value at address location NRIL/2 is made equal to Hold, which
was the original value at address location 0.
After this, step 1272 returns to decision step 1270 in which i is tested to
determine if it is greater than NRIL/2. If it is not, then step 1272 is
repeated, resulting in the swapping two more values of A.sub.1.
Given that i is incremented by one each time the process cycles through
step 1272, i will eventually test greater than NRIL/2. At that point, all
of the sign converted A.sub.1 have been stored in adjust LUT 1264.
After the adjusted input levels are stored in adjust LUT 1264, they are
input levels which can be processed by an image processor. More
particularly, as shown on FIG. 36, adjust LUT 1130 is adapted for having
the raw input level, RIL<x,y>, provided by the input device 22 shown on
FIG. 25, operate as the address to adjust 1130. Accordingly, RIL<x,y> will
be transmitted to adjust LUT 1130, and in response adjust LUT 1130 will
output a corresponding input level, IL<x,y>. Thereafter, IL<x,y> is
processed by the image processors in the manner discussed above.
FIGS. 40A, 40B, 40C, and 40D provide illustrations of alternate embodiments
in which an image adjustment system has been implemented in the image
processors discussed above. In connection with each, there is shown an
IAS, respectively numbered 1020a, 1020b, 1020c, and 1020d. Excepting only
IAS 1020c , each IAS is shown to receive a signal which corresponds to a
raw input level, RIL<x,y>, and responds to that signal by outputting a
corresponding adjusted input level, IL<x,y>. With respect to IAS 1020c
address/level generator 490 produces a raw input level, RIL, which
operates as an address to an adjust LUT 1130 in IAS 1020c so that IAS
1020c outputs an input level, IL. As detailed above IL is then used by
SMTVD 481 to provide signals to SMRTS 497. Other than this minor
variation, IAS 1020c operates the same as the general IAS 1020 discussed
above.
As seen in FIGS. 40A-40D, with IAS 1020 implemented in the four embodiments
of the image processors discussed above, the adjusted input level,
IL<x,y>, output by IAS 1020 would then be processed by the four different
run time systems, in the manner described in connection with the detailed
description of each of those systems.
G. Color Implementation
As discussed in the beginning of the detailed description, the embodiments
of the above described image processors and image adjustment system were
presented in the context of "levels", as opposed to "colors". This was to
illustrate how these systems and image processing techniques are generally
applicable bi-tonal, monochrome and color systems. On the other hand,
another embodiment of the present invention can be readily adapted to an
imaging system which specifically includes color systems of the
luminance/chrominance, or RGB variety.
Referring now to FIG. 41, an embodiment of an imaging system 1320 which
processes color images is provided. Imaging system 1320 includes input
device 22 which registers an input image which is to be mapped to output
device 30. Once again the objective of the embodiments of the present
invention is to take the input levels and map them to the output levels.
Typically, NOL will be greater than NIL; however, as stated above, it is
also possible to use this system when NIL=NOL.
In the particular embodiment shown in FIG. 41, input device 22 registers
three primary input levels: IL.sub.a <x,y>, IL.sub.b <x,y>, and IL.sub.c
<x,y>. For the purpose of illustration, the three input levels may be
three color primaries, such as red, green, and blue (RGB), for example. In
such an example, IL.sub.a <x,y> could represent the level of the red color
at the pixel address x,y; IL.sub.b <X,y> could represent the level of the
green color at the pixel address x,y; and IL.sub.c <x,y> could represent
the level of the blue color at the pixel address x,y.
In imaging system 1320 each of the three primary colors has multiple levels
ranging from 0 to (NIL-1). In other words, just like the range of input
levels discussed in connection with FIGS. 4 and 5, involving only one
color, in this instance each of the three color primaries has its own
range of input levels. For example, there may be multiple levels, or
shades, of the colors red, green or blue. Moreover, the implementation of
the imaging system 1320 does not require the three color primaries to have
the same number of input levels as each other.
As shown in FIG. 41, the three input levels are each coupled with their own
IP, respectively IP 1340a , IP 1340b , and IP 1340c . In imaging system
1320, each IP can be any one of the implementations of the IP devices
discussed above. Namely, each IP 1340a , 1340b , or 1340c could be
implemented using IP 40, 140, 440, 740, or the alternate embodiments of
those image processors, such as IP 40a , 140b , 440c 740d, which include
and image adjustment system. Additionally, as discussed in connection with
IAS 1020, each image processor may be used together with an IAS 1020.
Thus, for color images that are made up of multiple components, such as
YUV or RGB, the image processors, such as IP 1340a , 1340b , and 1340c ,
could each include an IAS 1020 for each of the components of the color
image, as discussed above. Finally, given that each IP operates
independently of the others, they do not necessarily need to be the same
type of implementation.
Although the specifics of the operation of the system will depend upon the
particular implementation chosen, in general IP 1340a , 1340b , 1340c will
each process and store dither template values and quantized values. And,
consistent with the discussion provided above in connection with the
implementation of each IP, the incoming address of a given input pixel and
its corresponding input level will be used as an address by the image
processor to output a corresponding output level.
For example, in FIG. 41 input device 22 transmits an input level IL.sub.a
<x,y> to IP 1340a , or input device 22 could transmit RIL<x,y> if an image
adjustment system is used. In one implementation, this could be the level
of the red color component of the input pixel at the given address, x,y.
That input level is treated by IP 1340a in the same manner as has been
described in connection with the image processors discussed above.
Ultimately, IP 1340a outputs a corresponding output level, OL.sub.a <x,y>,
which is then sent to output device 30.
In this particular example, input device 22 would also output the input
levels of the green and blue color components of the same input pixel at
the same address, respectively IL.sub.b <x,y>, IL.sub.c <x,y>. Those input
pixels are likewise processed by their respective image processors, IP
1340b and 1340c . And, each IP outputs a corresponding output level
OL.sub.b <x,y>, OL.sub.c <x,y>, to output device 30.
When the three output levels - - - RGB - - - are combined in the same
output pixel in output device 30, the color of the output image will be
reproduced with pleasing results, even if output device 30 has a narrower
range of output levels for representing the three color primaries than
input device 20.
One consequence of the approach described is that the dithered color image
effectively has 3 dither matrices overlaid on top of one another. If the
source image is in a highly correlated color space, such as RGB, and the
number of output colors is small, then dithering with the same in-phase
dither matrix can produce harsh patterns in neutral density (no
chrominance) image areas.
These harsh patterns can be mitigated by offsetting the dither matrices
slightly relative to one another. This is precisely the reason for the
phase adjustment process through which the dither matrix values are
adjusted by a phase adjuster, such as phase adjuster 98, shown in FIG. 7,
or phase adjuster 798, shown in FIG. 20. It may be recalled, in connection
with the discussion of FIGS. 7 and 20 in particular, the image processors
received as one of the inputs a phase.sub.-- x and a phase.sub.-- y value.
In one implementation, the user of the imaging system 20 may select the
actual phase.sub.-- x and phase.sub.-- y values, provided:
0.ltoreq.phase.sub.-- x<M.sub.mm ; and
0.ltoreq.phase.sub.-- y<N.sub.mm.
Also, each pair of phase.sub.-- x, phase.sub.-- y values for a given color
component should be different from the pairs for the other color
components.
For example, with respect to RGB images, the following phase.sub.-- x,
phase.sub.-- y settings work well for 8.times.8 dither matrices:
______________________________________
Phase.sub.-- x
Phase.sub.-- y
______________________________________
Red 0 0
Green 3 3
Blue 0 3.
______________________________________
Finally, although FIG. 41 shows three image processors linked to implement
the color system, in other implementations any different number of image
processors could be similarly assembled to link input device 22 with
output device 30 depending on the number of colors to be represented in
the imaging system 1320.
H. Summary
It will be clear to those skilled in the art that the embodiments of the
image processing systems and techniques of the present invention can be
implemented in either hardware or software. In other words, the
embodiments discussed can be implemented using software code with a
general purpose computing device to accomplish the processing of data to
determine quantization and dither template values, as well as to determine
the actual computation of the output levels. Additionally, more
specialized computer hardware could be used to compute specific equations
which yield the data necessary for the implementation of the embodiments
discussed. AS is well know in the computer art, there is constant tension
between performing operations with specialized hardware, which increases
the speed of the system, but requires valuable chip space, and performing
operations in software, which takes up virtually no valuable chip space,
but may take longer.
One of the significant advantages of the imaging systems discussed is that
in certain implementations the hardware requirements are so minimal. Such
implementations rely upon having memory devices, adders, comparators, and
bit shifters. This type of hardware is commonly available in general
computing devices.
The present invention in its broader aspects is therefore not limited to
the specific details, representative apparatus. and illustrative examples
shown and described herein. Departures hay be made from such details
without departing from the spirit or scope of the invention.
Top