Element Generator for Dither Matrix and a Dithering Apparatus Using the Same

The present invention relates to an element generator for a dither matrix and a dithering apparatus using the same, and more particularly to a dithering apparatus to be used for improving the image quality in an image outputting device having a low gray-scale characteristic.

Generally speaking, image outputting devices can be classified into a static image outputting device and a dynamic image outputting device. The static image outputting device, e.g., a plotter, ink jet printer, dot printer or laser printer generates a motionless image, while the dynamic image outputting device, e.g., a television receiver and computer monitor, generates a time-variant image. For various reasons, the above image outputting devices are restricted in terms of gray scale. For example, the gray scale of a liquid crystal monitor is severely restricted due to the characteristics of the liquid crystal itself. Similarly, the gray scale of a dot printer is determined by the number of dots which can be represented in the unit area. Thus, most image outputting devices are restricted in terms of gray scale, due to a correlation between their own characteristics and the resolution required. In addition, the gray scale may also be restricted based on the limitations of an image signal processor for outputting. For example, if an original image signal to be processed is represented by eight bits but the image signal processor is limited to only four bits, the gray scale is thereby restricted.

It is apparent that a lower gray scale diminishes image quality accordingly. Specifically, false contour generation and mach band effects are prevalent phenomena in systems having a low gray scale and lead to reduced image quality. Therefore, various algorithms have been proposed for overcoming these phenomena; for example, dithering, which prevents image quality reduction by adding randomly distributed noise to the original image.

Conventional dithering, however, is performed by software, which leads to the reduction of the processing speed. In particular, when a dither element to be used in the dithering process is generated by software, the reduction of the image processing speed is significant. This reduction in processing speed is quite remarkable in the field of computer graphics and results in unacceptably slow processing speeds. Hence, for increasing the image processing speed, the look-up table technique is employed as a hardware implementation of the dither matrix. However, the cost involved with such a look-up table, which is generally implemented by ROM memory elements, is excessive.

Accordingly, the object of the present invention is to provide an element generator for a dither matrix, which has a simple hardware structure and can be operated at high speed.

The other object of the present invention is to provide a dithering apparatus which includes the above element generator and can be operated at high speed.

To attain the above objects, the present invention provides a dithering apparatus for converting an M-bit original image into N-bit dithered data, comprising:

a dither-matrix element generator for performing a logic operation on a row address and a column address related to the original image so as to produce a corresponding element of the dither matrix;

a comparator for comparing the output of the element generator with the data composed of the (M-N)th bit through (M-N--L+1)th bit of the original image data, provided that the output of the element generator is composed of L bits;

an adder for adding a predetermined number to the upper N bits of the original image data; and

a selector for selecting one between the upper N bits of the original image data and the output of the adder, in accordance with the output of the comparator, so as to produce the selected one as the N-bit dithered image data.

Also, the dithering apparatus further comprises a mask circuit for converting the output of the adder into the maximized N-bit value, when an overflow occurs in the adder. The mask circuit is composed of a plurality of logic OR gates each for performing a logic OR operation with a carry signal and one bit of the output of the adder.

The above objects and advantages of the present invention will become more apparent by describing in detail a preferred embodiment thereof with reference to the attached drawings in which:

FIG. 1 is a logic circuit diagram of a dither-matrix element generator according to one embodiment of the present invention, which represents the logic circuit for generating the elements for a 4.times.4 dither matrix;

FIG. 2 is a logic circuit diagram of a dither-matrix element generator according to another embodiment of the present invention, which represents the logic circuit for generating the elements for an 8.times.8 dither matrix;

FIG. 3 is a block diagram of a dithering apparatus of the present invention; and

FIG. 4 is a detailed logic diagram of the mask circuit shown in FIG. 3.

First of all, for better comprehension of the present invention, a dither matrix will be simply explained.

A dither matrix D.sup.(n) is defined by the following equation (1). ##EQU1##

For example, a 4.times.4 dither matrix (or D.sup.(4)) is represented thus: ##EQU2##

In the above dither matrix, provided that X represents the row address and Y represents the column address, the elements D.sup.(4) (X,Y) of the 4.times.4 dither matrix are represented as: ##EQU3##

When a look-up table is adopted for generating the elements of the above dither matrix, a 16.times.2.sup.4 memory is required.

FIG. 1 is a logic circuit diagram of the dither-matrix element generator according to one embodiment of the present invention, which represents the logic circuit for generating elements for a 4.times.4 dither matrix. Here, the element generator includes two XOR gates 101 and 102. Referring to FIG. 1, the binary representation of the inputs (row address and column address) and the output are shown in Table 1.

Based on the binary representation of Table 1, the output bits can be represented by a function of input bits. These relationships are as follows.

Based on the above equations (2) through (5), the dither-matrix element generator is implemented by XOR gates 101 and 102. That is, XOR gate 101 performs the logic exclusive-OR operation corresponding to the above equation (5) and XOR gate 102 performs the logic exclusive-OR operation corresponding to the above equation (3).

For instance, if the row address (X.sub.1 X.sub.0) is "00" and the column address (Y.sub.1 Y.sub.0) is "01," then the following statements are true.

That is, a binary "8" is generated, i.e., "1000."

FIG. 2 is a logic circuit diagram of a dither-matrix element generator according to another embodiment of the present invention, which represents the logic circuit for generating elements for an 8.times.8 dither matrix. The dither-matrix element generator of FIG. 2 includes three XOR gates 201, 202 and 203.

The 8.times.8 dither matrix constructed based on Equation (1) is as follows. ##EQU4##

If the consideration of the relationship between the row address, the column address and its corresponding element of the above matrix is made based on the their binary representation, elements bits D.sub.5, D.sub.4, D.sub.3, D.sub.2, D.sub.1 and D.sub.0 of the dither matrix can be represented as the following.

In FIG. 2, XOR gate 201 performs the logic exclusive-OR operation related to the equation (6), XOR gate 202 performs the logic exclusive-OR operation related to the equation (8), and XOR gate 203 performs the logic exclusive-OR operation related to the equation (10).

Similarly, the element generators for higher-order dither matrices (e.g., D.sup.(16), D.sup.(32) and D.sup.(64)) can be implemented.

As shown in the above description, the dither-matrix element generator can be implemented by very few logic devices (i.e., XOR gates), which results in cutting down on the cost for hardware implementation and increasing the operation speed.

FIG. 3 is a block diagram of a dithering apparatus of the present invention, wherein the dithering apparatus includes a dither-matrix element generator 301, a comparator 302, an adder 303, a mask circuit 304 and a selector 305.

Here, for the convenience of explanation, we will consider the case that 10-bit original image data is changed into 4-bit image data by dithering.

Referring to FIG. 3, dither-matrix element generator 301 receives a row address and a column address and then produces its corresponding element of the 8.times.8 dither matrix (hereinafter referred to as the dither element). Here, the row address and column address to be applied to dithering matrix element generator 301 are obtained by modulating an image row address and an image column address corresponding to the original image data. For example, provided that the image row address and the image column address are denoted as IX and IY, respectively, the row address X and the column address Y related to the dither-matrix element generator 301 may be produced by the following method.

Though this modulation can be performed using software, it is also possible to use the three lower bits of the image row address and the three lower bits of the image column address as the inputs of dither-matrix element generator 301.

The dither element produced from dither-matrix element generator 301 is applied to comparator 302. Comparator 302 compares the six lower bits of the original image data with the dither element, and the compared result is applied to selector 305 as a selecting control signal. For example, if the value of dither element is higher than that composed by the six lower bits of the original image data, comparator 302 produces a logic "1," and otherwise produces a logic "0." Here, the image data applied to comparator 302 is composed of L bits, which corresponds to the (M-N)th bit to the (M-N-L+1)th bit of the original image data, provided that the original image data is composed of M bits, the dithered image data is composed of N bits and the output of dither-matrix element generator 301 is composed of L bits.

Meanwhile, the four upper bits of the original image data are applied to both adder 303 and selector 30.5. Adder 303 adds a predetermined number (for example, one) to the received four upper bits of the original image data so as to produce an output. Mask circuit 304 modulates the output of adder 303 into the maximum 4-bit value, when an overflow is generated in adder 303. In other words, when the carry is generated from adder 303, the output of mask circuit 304 is "1111." Thus, mask circuit 304 may be implemented as shown in FIG. 4.

Referring to FIG. 4, OR gates 401, 402, 403 and 404 each perform a logic OR operation with regard to one bit of the adding result (A.sub.3, A.sub.2, A.sub.1 or A.sub.0) and a carry signal produced from adder 303, so as to produce the result thereof.

Referring back to FIG. 3, selector 305 selects one between the output (B.sub.3, B.sub.2, B.sub.1 or B.sub.0) of mask circuit 304 and the four upper bits of the original image data, in accordance with the output of comparator 302.

If the dithering apparatus is by the above hardware, the processing speed thereof is increased. In particular, the dithering is operation related to the image outputting device and is performed not once but is repeated many times. In addition, in the field of computer graphics, increasing the processing speed is essential for interface with a user. Accordingly, the element generator for a dither matrix and the dithering apparatus using the same have a more remarkable effect in the field of computer graphics than other fields. Particularly, the dither-matrix element generator can be implemented by only a few logic elements, which leads to a reduction in cost while greatly increasing the processing speed beyond that achieved with ROM memory elements.

Though explained in terms of detailed embodiments, the present invention is not limited to the above-described embodiments, but can be modified and improved within the scope of knowledge of the ordinarily skilled artisan in this field.