 |
Claims  |
|
|
We claim:
1. In a multi-level halftoning system, apparatus for generating a
multi-level pixel value for a halftone cell from a magnitude of an
intensity value, said apparatus comprising:
means, responsive to the magnitude of said intensity value, for producing a
modulation level as said multi-level pixel value, wherein said producing
means comprises a plurality of look-up tables each having values
representing a pre-defined transfer function, wherein said pre-defined
transfer functions are generated by apparatus comprising:
means for automatically producing said transfer functions using a
mean-preserving process such that a sum of the derivative of said transfer
functions equals the number of pixel values in said halftone cell;
preference matrix means connected to said producing means, for selecting
one of said plurality of look-up tables; and
means, connected to said selecting means, for controlling said selection
such that one look-up table is selected in a pre-defined manner to produce
a modulation level as said multi-level pixel value.
2. The apparatus of claim 1 wherein each said transfer function is
quantized into a plurality of levels, whereby each quantization level is a
modulation level.
3. The apparatus of claim 1 wherein said halftone cell comprises a
plurality of multi-level pixel values and wherein said controlling means
further comprises means for generating a plurality of multi-level pixel
values from said intensity value magnitude.
4. The apparatus of claim 3 wherein said generating means comprises means
for repetitively controlling said selection by said preference matrix
means of said plurality of look-up tables such that said intensity value
magnitude is applied to each selected look-up table to produce a plurality
of modulation values as said multi-level pixel values in said halftone
cell.
5. The apparatus of claim 1 wherein said preference matrix having a
plurality of matrix elements defines a number of pixel locations in said
halftone cell.
6. The apparatus of claim 1 wherein said means for producing said transfer
functions comprises means for generating knot points defining said
transfer functions in a piece-wise linear fashion.
7. In a multi-level halftoning system, a method for generating a
multi-level pixel value for a halftone cell from an intensity value having
a magnitude, said method comprising the steps of:
generating a plurality of pre-defined transfer functions wherein a sum of
the derivative of said transfer functions equals a number of pixel values
in said halftone cell;
selecting one of a plurality of look-up tables, wherein each said look-up
table contains values representing one of said pre-defined transfer
functions;
controlling said selection such that one look-up table is selected in a
pre-defined manner; and
producing, in response to the magnitude of said intensity value, a
modulation level as said multi-level pixel value.
8. The method of claim 7 wherein each said transfer function is quantized
into a plurality of levels, whereby each quantization level is a
modulation level.
9. The method of claim 7 wherein said halftone cell comprises a plurality
of multi-level pixel values and wherein said method further comprises the
step of generating a plurality of multi-level pixel values from said
intensity value magnitude.
10. The method of claim 9 wherein said generating step further comprises
the step of repetitively controlling said look-up table selection such
that the intensity value magnitude is applied to each selected look-up
table to produce a plurality of modulation levels as said multi-level
pixel values in said halftone cell.
11. The method of claim 7 wherein said step of generating said transfer
functions further comprises the step of generating knot points defining
said transfer functions in a piece-wise linear fashion.
12. In a multi-level halftoning system for converting an input intensity
value into a multi-level pixel value for a halftone cell, apparatus for
specifying matrix values used as modulation levels for converting said
intensity value comprising:
means for generating a plurality of transfer functions being mean
preserving such that a sum of the derivatives of said transfer functions
equals a number of pixel values in said halftone cell; and
means for specifying modulation levels from said mean preserving transfer
functions.
13. The apparatus of claim 12 wherein said specifying means further
comprises:
means for quantizing each said transfer function into a plurality of
quantization levels wherein each quantization level is a modulation level;
and
means for storing said modulation levels as look-up table values.
14. The apparatus of claim 12 wherein said specifying means further
comprises:
means for quantizing each said transfer function into a plurality of
quantization levels;
means for defining a plurality of modulation levels by comparing said
quantization levels to an intensity value that is increasing in value,
each intensity value at which an output from said transfer function
changes levels is a modulation level; and
means for storing said modulation levels as modulation level matrix
elements.
15. The apparatus of claim 12 wherein said transfers function generating
means generates a plurality of transfer functions corresponding to a
number of pixels in a halftone cell.
16. In a multi-level halftoning system having a predetermined number of
micro-output levels available in the system, a method for generating a
multi-level pixel value for a halftone cell, wherein said halftone cell
has a predetermined cell size, from an intensity value having a given
magnitude, comprising the steps of:
a. generating a plurality of pre-defined transfer functions wherein the sum
of the derivative of said transfer function equals a number of pixel
values in said halftone cell and further wherein each transfer function is
quantized into a plurality of modulation levels determined as a function
of the size of the halftone cell and the number of micro-output levels
available in the system; and
b. assigning said modulation levels as threshold matrix entries in a set of
modulation level matrices.
17. A method as set forth in claim 16 wherein said step of assigning is
performed by loading said modulation levels into said set of modulation
level matrices in ascending order at identical locations in each matrix.
18. In a multi-level halftoning system for converting an input intensity
value into a multi-level pixel value for a halftone cell, a method for
specifying matrix values used as modulation levels for converting said
intensity value, comprising the steps of:
a. generating a plurality of transfer functions being mean preserving such
that the sum of the derivatives of said transfer functions equals a number
of pixel values in said halftone cell; and
b. specifying modulation levels from said mean preserving transfer
functions.
19. A method as set forth in claim 18 wherein said step of specifying
further comprises the steps of:
a. quantizing each said transfer function into a plurality of quantization
levels wherein each quantization level is a modulation level; and
b. storing said modulation levels as matrix entries.
20. A method as set forth in claim 19 wherein said step of storing is
performed by loading said modulation levels into said set of modulation
level matrices in ascending order at identical locations in each matrix.
21. A method as set forth in claim 18 wherein said step of specifying
further comprises the steps of:
a. quantizing each said transfer function into a plurality of quantization
levels;
b. defining a plurality of quantization levels by comparing said
quantization levels to an intensity value that is increasing in value,
where each intensity value at which an output from said transfer function
changes level is a modulation level; and
c. storing said modulation levels as modulation level matrix elements.
22. A method as set forth in claim 18 wherein said step of generating is
operative to generate a plurality of transfer functions corresponding to a
number of pixels in a halftone cell. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
CROSS-REFERENCE TO RELATED APPLICATION
This application describes material in U.S. application Ser. No.
07/906,142, filed Jun. 29, 1992, having Kodak Docket No. 63,006, entitled
"Apparatus And Method For Generating Multi-Level Output Values For Pixels
In A Halftone Cell" (now U.S. Pat. No. 5,291,311 issued Mar. 1, 1994).
TECHNICAL FIELD OF THE INVENTION
The invention relates to apparatus, and an accompanying method, for use in
digital halftoning systems, and particularly, to a method and apparatus
for generating modulation levels that can be used to produce multi-level
halftone images.
BACKGROUND ART
Generally, digital halftoning is accomplished by either bi-tonal or
multi-tonal halftoning methods. Bi-tonal halftoning is widely used in the
art and is a basic digital halftoning method from which multi-tonal
halftoning methods are derived. Therefore, bi-tonal digital halftoning is
discussed below as a precursor to a discussion of multi-tonal halftoning.
In general, bi-tonal digital halftoning converts a continuous tone image
into a halftone image consisting of a pattern of equal intensity dots.
Each dot within the halftone image either exists (black) or does not exist
(white), i.e., a bi-tonal image. More specifically, bi-tonal digital
halftoning converts a plurality of digitized intensity values representing
a continuous tone image into a plurality of halftone cells, where each
halftone cell corresponds to each intensity value. Moreover, the number of
dots within each halftone cell is proportional to the magnitude of each
corresponding intensity value. The intensity values are typically
generated by periodically sampling a continuous tone image using an
optical scanner. Each intensity value represents the image intensity in an
immediate area surrounding the location within the continuous tone image
from which an intensity value sample was taken. Typically, each intensity
value is quantized into a plurality of levels known as gray scale levels.
Quantization permits each intensity value to be represented by a digital
value and processed by digital circuitry into a halftone image. For
instance, if the intensity value is quantized into 256 levels, i.e., a 256
level gray scale, the intensity value can be represented by an eight-bit
digital word.
During bi-tonal digital halftoning, each intensity value is spatially
mapped into a corresponding halftone cell. As noted above, each halftone
cell typically encompasses a plurality of pixels, each having a bi-tonal
value, i.e., either black or white. However, some applications require the
number of intensity values to equal the number of pixels in the halftone
cell, i.e., equal scanner and halftone resolutions. Generally speaking,
regardless of the application, the arrangement of bi-tonal pixels within
the halftone image is perceived by a viewer of the halftone image to have
a gray scale intensity commensurate with the magnitude of each associated
intensity value. The above described mapping process is generally known as
spatial modulation.
In operation, a bi-tonal digital halftoning system compares each intensity
value sample to a matrix of modulation levels and generates a halftone
cell corresponding to each intensity value. Typically, this matrix has a
number of elements equivalent to the number of pixels in the halftone
cell. To generate the bi-tonal halftone cell, a given intensity value is
compared to each modulation level in the matrix. Each pixel in the
halftone cell, that corresponds to a modulation level in the modulation
level matrix and is lesser in value than the intensity value, is made
black; otherwise, the pixel is white. Thus, the intensity value is mapped
into an area comprised of an arrangement of black and white pixels whose
overall intensity is commensurate with the magnitude of the intensity
value.
The arrangement of modulation levels within the modulation level matrix is
generally known as dithering, more specifically, in two common forms:
clustered dot dithering and dispersed dot dithering. In essence, through
dithering, the modulation levels are arranged to ensure that the resultant
halftone pixels that will be generated for a given cell will accurately
reflect the intensity of the input intensity value associated with that
cell. For a detailed discussion of dithering in bi-tonal systems, see
Ulichney, Digital Halftoning, pp. 71-171 (MIT Press, .COPYRGT.1987).
The matrix comparison process, as described above, is repeated for each
intensity value sampled from the original continuous tone image. As a
result, the entire image is spatially modulated into a halftone image
comprised of a tile-like arrangement of halftone cells each representing a
different corresponding intensity value sample.
As is well known in the art, the halftoning process thus far described is
useful in halftoning color images by repeating the bi-tonal process for
each primary color, i.e., red, blue, and green or cyan, magenta, and
yellow, and, subsequently, overlaying the resulting color halftone images
with proper registration.
Multi-level halftoning is an extension of bi-tonal halftoning. As its name
implies, multi-level halftoning replaces each black or white pixel in a
bi-tonal halftone cell with a pixel having a value selected from a number
of values available for each pixel. In essence, multi-level halftoning
redistributes the intensity of a single intensity value into a plurality
of intensity values within a halftone cell. Many display devices permit
multi-level pixel display; multi-level halftoning takes advantage of this
capability. For example, thermal printers are capable of printing dot
sizes that correspond to each pixel intensity level. Additionally, cathode
ray tube (CRT) displays can display various pixel intensities by altering
an electron beam strength incident upon each pixel within the CRT display.
Typically, display devices are limited as to the number of levels that they
can display. In contrast, sampling devices can produce many different
output levels. Therefore, multi-level halftoning is used to convert a
large number of output levels from a sampling device into a lesser number
of levels compatible with a display device. For instance, if a display
device can accurately display five levels while a scanner can provide a
256 level intensity value, a multi-level halftoning system must distribute
each single 256 level value into a halftone cell, containing a plurality
of five level pixels, that, when viewed, appears as the 256 level value.
To determine the appropriate level for each pixel in a multi-level halftone
cell, an input intensity value is compared to a number of modulation level
matrices, i.e., N-1 matrices are used to generate N levels. Generally, the
comparison process is similar to that used in bi-tonal halftoning except
the comparison process is repeated N-1 times for N-1 matrices. As in
bi-tonal halftoning, each matrix contains, as matrix elements, a number of
different modulation levels. The number of matrix elements is equivalent
to the number of pixels in the halftone cell. The output of each
comparison is a digital bit, i.e., a signal having a value of either a
logical "1" or logical "0". The output bit value indicates whether the
intensity value is greater than the modulation level, i.e., logical "1" or
less than the modulation level, i.e., logical "0". Each output bit is
stored in an intermediate matrix. Thus, a set of N intermediate matrices
containing digital bits is generated. An encoder combines the elements of
the intermediate matrices to generate the pixel values for a halftone
cell.
For example, an intensity value may be quantized by an 8-bit scanner to
have a value between 0 and 255. The intensity value is compared to four
matrices. Each matrix contains modulation levels arranged in a 4-by-4
matrix having various modulation levels ranging from 0 to 255. Comparing
each modulation level in each matrix to the intensity value results in
four intermediate matrices containing digital values. The elements of each
intermediate matrix are valued at a logical "1" whenever the intensity
value is larger than the corresponding modulation level; otherwise, a
logical "0" is used as the matrix element. In essence, the four
intermediate matrices are four bi-tonal halftone cells. The elements of
each intermediate matrix having the same coordinates are combined to form
a 4-bit word. Each 4-bit word is then encoded to generate a halftone
output value for a pixel in the multi-level halftone cell. The resulting
pixel value will range from 0 to 4, i.e., one level for each modulation
level matrix with one level to signify the absence of a pixel.
As in the case of bi-tonal halftoning, the modulation levels are placed in
a dither pattern within each modulation level matrix. The dither patterns
used are essentially the same as those used in bi-tonal halftoning, i.e.,
clustered-dot dither or dispersed-dot dither.
Currently, the modulation levels in each matrix of a multi-level halftoning
system are generated manually. These levels are then arranged using
empirical methods to achieve a desired intensity value to halftone cell
conversion. The number of modulation levels that needs to be specified is
(m.times.n)(N-1), where: N is the number of desired output levels, and m
and n are the dimensions in matrix elements of the modulation level
matrices. In practice, the number of modulation levels that must be
generated can be quite large. For example, a system having 12 output
levels with 8-by-8 element matrices requires that 64 modulation levels
must be specified and then properly arranged in each of 11 modulation
level matrices.
Moreover, to accomplish each intensity value comparison, N-1 comparator
circuits associated with N-1 modulation level matrices are necessary to
produce an N-level output. Thus, a conventional multi-level halftone
system requires a dedicated number of comparators and associated matrices
to generate each of the output levels. Consequently, each halftoning
system must be designed to accommodate a specific number of output levels
to drive a specific display device. Thus, a single multi-level halftone
image generating system cannot be readily altered to accommodate any
number of output levels and hence is rather inflexible.
Therefore, a specific need exists in the art for apparatus that generates
multi-level output values for pixels in a halftone cell in a manner which
readily accommodates any number of output levels. Specifically, a need
exists in the art for apparatus that generates multi-level values without
using an arrangement of comparators and modulation level matrices.
Additionally, a need exists in the art for apparatus that automatically
generates modulation levels for each of the modulation level matrices.
SUMMARY OF THE INVENTION
Accordingly, an object of the present invention is to provide apparatus for
performing multi-level halftoning of a continuous tone image.
A specific object of the present invention is to generate multi-level
pixels in a halftone cell without using a matrix and comparator
combination.
Another specific object of the present invention is to automatically
generate modulation levels for modulation level matrices used to perform
multi-level halftoning.
These and other objects are accomplished in accordance with the teachings
of the present invention by apparatus for generating a multi-level
halftone image using a look-up table selection technique operating in
conjunction with a method of automatically generating modulation levels as
elements in a plurality of look-up tables. In particular, the apparatus
includes a control circuit, a preference matrix having, as its matrix
elements, addresses of a plurality of look-up tables, and a plurality of
look-up tables in the form of a look-up table stack. Generally, the
control circuit instructs the preference matrix to select a look-up table
from the look-up table stack. The selected table is used to convert an
intensity value into a multi-level pixel value. Specifically, the control
circuit provides the preference matrix with an address of an element
within the preference matrix. The value of the chosen element selects a
look-up table from the stack. Subsequently, the chosen look-up table is
used to convert an intensity value into a pixel value in a halftone cell.
To accomplish the conversion, each look-up table contains a
one-dimensional quantized transfer function having, as an input, the
magnitude of the intensity value. Each transfer function is automatically
derived using a mean-preserving algorithm such that the sum of the
derivatives of all of the transfer functions is equivalent to the number
of pixels in the halftone cell. Through the transfer function, the
intensity value magnitude is mapped into one of a plurality of available
output levels. The resulting output level is assigned a pixel location in
the halftone cell. The look-up table selection is repeated for each
element of the preference matrix so that the magnitude of each intensity
value is mapped into the halftone cell. As successive intensity values are
| | |
