Fractal-dithering technique for image display

[0001] 1. Field of the Invention

[0002] The present invention relates generally to display of computer graphics. In particular, the present invention is directed towards a dithering technique for quickly displaying images at reduced color depth without significant quality loss.

[0003] 2. Description of the Related Art

[0004] There is frequently a need to display an image on a display device that has insufficient color depth to display the image at its original color level. For example, a computer capable of an eight-bit color map will not accurately render a 16-bit image; a computer with a 24-bit color depth cannot display an image with 48-bit color, etc.

[0005] One way of displaying such an image is to cut off the lower-order bits of each pixel in the image. This, however, leads to the well-known problem of Mach banding, in which the human eye exaggerates the contrast between two surfaces with different luminance, making the image look unattractive.

[0006] Another attempt at solving the problem is the use of blue noise filtering. This is a collection of techniques in which pixels of different color are placed in some random fashion, in such a way that low frequency noise is suppressed and one is left with high spatial frequencies in the placement of the different colors. However, this technique causes clumps and gaps which, while minimized, are typically still visible. Secondly, so-called error diffusion, where some statistic propagates lexicographically across the image is not local—that is, the dither algebra depends on the environment of the pixel, which can require looking at each pixel several times in addition to being computationally expensive. Blue noise filtering is an error diffusion technique in which the color error and pixel placement is randomly distributed over an image.

[0007] A need remains for a technique for efficiently dithering an image that results in a high quality output image and does not require extensive computational power.

[0008] The present invention enables rapid dithering of an RGB image from a higher order to a lower order number of bits while introducing fewer undesirable artifacts than are visible in conventional dithering technology. The present invention is compact and deterministic, and enables the elimination of banding, for example as is seen in 24-bit monitors when viewing color images with greater color depth.

[0009] A system of the present invention includes a fractal dithering engine, which selects a threshold matrix appropriate for an input stream, and using the threshold matrix, dithers images of the input stream to output images having a lower order number of color bits. In one embodiment, the threshold matrix is obtained by traversing 2-by-2 sub-regions of an N-by-N matrix according to a traversal pattern, and then applying a reverse binary function to the values in the original matrix to yield the threshold matrix. The threshold matrix preferably tessellates the pixel plane, subject to certain constraints.

[0010] In addition to a general algorithm for an N-by-N matrix, the present invention also includes an algorithm particularly suited for 48-bit input and 24-bit output.

[0011] Preferably, the present invention has no effect on standard 24-bit RGB input. That is, a channel at 24 bits is dithered to be itself. This allows, for example, a 48-bit image to be composited on top of a 24-bit background, while ensuring that the 24-bit background will not change regardless of the changes the dither makes to the 48-bit image.

[0016] The figures depict various embodiments of the present invention for purposes of illustration only. One skilled in the art will readily recognize from the following discussion that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the invention described herein.

[0017] Referring now to FIG. 1, there is shown a block diagram of a system 100 in accordance with an embodiment of the present invention. System 100 includes a fractal dithering engine 104, which takes as input an input stream 102 and a threshold matrix 106, and produces an output stream 108. Images in the input stream 102 have a high order of color bits and fractal dithering engine 104 creates a stream 108 of dithered images having a lower order of color bits. The selection of an appropriate threshold matrix is detailed further below.

Using a Threshold Matrix

[0018] When dithering using a two-by-two threshold matrix represented by A, for a gray level g—a real number in (0, 1)—a pixel p_xy at location (x, y) is turned on, e.g., to white, when
A_xy<Round(4g),
where the entire pixel plane is tesselated by A. In this way, (x,y,g) determines a white or black value depending on the Round inequality, so that regions of grey level g have some pixels turned on and some pixels turned off. In practice, one actually tests inequality for A_{x mod 2,y mod 2}, because the matrix tessellates the plane. Such a prescription involving Round can be shown via standard Lloyd-Max theory to minimize the RMS error due to the dither. For example, for gray level g=½, only the 0 and 1 matrix elements are activated—giving an exact checkerboard dither, as tight as can be for such a g at exact midlevel.
Determining a Threshold Matrix

[0019] Each matrix of size 2^N-by-2^N can be conceptualized as comprising four smaller matrices of size 2^N−1-by-2^N−1. In a recursive fashion, each matrix can therefore be said to comprise some number (4^N−1) of 2-by-2 matrices. A threshold matrix of size 2^N-by-2^N is preferably determined as follows:

[0020] Given a starting index value s, a 2-by-2 matrix is assigned the following entries:

[0021] $\left(\begin{array}{cc}s& s+3\\ s+1& s+2\end{array}\right)\hspace{1em}$
Given a starting index value t, a 4-by-4 matrix is assigned entries by assigning entries to its four constituent 2-by-2 matrices. The four 2-by-2 matrices are assigned s values of t, t+4, t+8 and t+12, respectively, with increasing s values allocated to the constituent 2-by-2 matrices according to the same traversal pattern in which the entries of the 2-by-2 matrices increase. In the example above, that direction is down, to the right, and up. Propagating this pattern to the 4-by-4 matrix yields the following:

[0022] $(\begin{array}{cccc}s& s+3& s+12& s+15\\ s+1& s+2& s+13& s+14\\ s+4& s+7& s+8& s+11\\ s+5& s+6& s+9& s+10\end{array})\hspace{1em}$

[0023] By extension, in the general case a matrix can have its cell contents allocated by allocating the sub-matrices contained within it, recursively reducing the size of the matrix until it is a 2-by-2 matrix and beginning the allocation with an appropriate s value. Each sub-matrix is visited according to the established traversal pattern. For example, for a 2^N-by-2^N matrix, matrix cell values are allocated first to the top-left 2^N−1-by-2^N−1 sub-matrix, then to the bottom-left, then to the bottom-right, and finally to the top-right.

[0024] Although in a preferred embodiment the direction of travel, as described above, is from the top-left, down, to the right, and up (such as in the shape of the English letter “U”), other traversal patterns can be selected in other embodiments. In each case, the direction of traversal of matrices is preferably the same as the direction of increasing index value within a 2-by-2 matrix.

[0025] After each cell has been visited and assigned an initial value, a function rev(n, b) is applied, which reverses the last b bits of n. Applying the rev function to the cells of the 2-by-2 matrix 200 depicted in FIG. 2 yields the following results:
rev(00₂,2)=0,
rev(01₂,2)=2,
rev(10₂,2)=1
rev(11₂,2)=3.

[0026] As can be seen in FIG. 3, entry 202 is assigned the binary value 00; 204 is 10; 206 is 01 and 208 is 11.

[0027] Consider, by way of example, the determination of a 4-by-4 threshold matrix in accordance with an embodiment of the present invention as described above. Begin with a 4-by-4 matrix, and number its constituent 2-by-2 matrices by traversing them in the pattern described above, which yields:

[0028] $(\begin{array}{cccc}0& 3& 12& 15\\ 1& 2& 13& 14\\ 4& 7& 8& 11\\ 5& 6& 9& 10\end{array})\hspace{1em}$
expressed in 4-bit binary representation, the above matrix becomes:

[0029] $(\begin{array}{cccc}0000& 0011& 1100& 1111\\ 0001& 0010& 1101& 1110\\ 0100& 0111& 1000& 1011\\ 0101& 0110& 1001& 1010\end{array}).$
Next, reverse the bits of each entry to obtain:

[0030] $(\begin{array}{cccc}0000& 1100& 0011& 1111\\ 1000& 0100& 1011& 0111\\ 0010& 1110& 0001& 1101\\ 1010& 0110& 1001& 0101\end{array}).$
Translating back to base 10:

[0031] $A=(\begin{array}{cccc}0& 12& 3& 15\\ 8& 4& 11& 7\\ 2& 14& 1& 13\\ 10& 6& 9& 5\end{array}),$
which is a 4-by-4 threshold matrix in accordance with the present invention.

[0032] An algorithm to obtain a 4^k-by-4^k matrix A can be described as follows. Assume the matrix A is N-by-N matrix, with N=4^k for sake of illustration. Recall the bit-reversal function rev( ) described above. Denote by x_j the j-th bit of x, so that x=( . . . x₂x₁x₀)₂, and establish a Gray-order function, as gray(n)=n XOR (n>>1).

[0033] Next, the entries of matrix A are filled with values determined according to the following loop:

for(x=0; x<N; x++){

[0034] for(y=0; y<N; y++){

• • [0035] for(j=0; j<2k−1; j++){
    • [0036] r_j :=gray(2·x_j+y_i);
    • [0037] A_xy :=rev(Σ_j=0^2k−1r_j4^j,2log₂ N);
  • [0038] }

[0039] }

}

Note that A preferably tessellates the entire pixel plane, so that the actual access of matrix elements will be of A_{x mod N,y mod N}. Following completion the loop, A is returned.

[0040] Referring now to FIG. 4, there is a flowchart illustrating a method for dithering images in accordance with an embodiment of the present invention. System 100 receives 402 an input image that is to be dithered. Based on an empirical determination related to visual quality, and in one embodiment a four-by-four matrix, an appropriate threshold matrix 106 is retrieved 404 by fractal dithering engine 104. Using the threshold matrix values and the pixel values in the input stream 102, fractal dithering engine 104 dithers 406 the image by evaluting the pixel values against the threshold matrix values to determine whether each pixel should be illuminated. Finally, the resulting dithered image 108 is output 408 from fractal dithering engine 104.

48-Bit to 24-Bit Dithering

[0041] The above algorithm provides a solution in the general case for an N-by-N matrix. In the specific case of 48-bit RGB input that is to be displayed with 24-bit RGB output, the following algorithm can be used by system 100. When a 16-bit color channel c, which may be a red (R), green (G), or blue (B) channel, has “excess value”, eε[0,255], defined as
e:=c mod 256,
define a coordinate-dependent bit:
B(x,y)=1 if A_x%4,y%4<└e/16┘
B(x,y)=1 if A_x%4,y%4=└e/16┘ and R(x,y)<e%16, and
B(x,y)=0 otherwise
where R(x, y) is a suitable function with values in [0,15]. This avoids the need to use a 16-by-16 matrix as would be used by the general algorithm described above. Instead, a 2-by-2 matrix can be used, choosing R to be a random function (equally distributed), or in an alternative embodiment, different scalings of the pixel plane can be used to access R values from the matrix itself. For each 16-bit color channel cε{r, g, b}, do:
c_low=c>>8;
c_high=(c_low+1)−(c_low>>8);
e_c=c&255.
The color channel at (x, y) is then set to the 8-bit value
c′(x,y)=c_low(1−B(x,y,e_c))+c_highB(x,y,e_c).

[0042] Note that using the above algorithm, pixel neighborhood becomes irrelevant, since only point(x, y) is input. The dither is entirely deterministic and point-local. Note also that a stream of 48-bit color values can be jammed in the respective high-bytes with the dithered channel values. In addition, original 24-bit colors (having channels c=(byte)00000000 will be dithered just to the value (byte). This means that for 24-bit color originals, nothing is perturbed by the algorithm.

[0043] The present invention has been described in particular detail with respect to a limited number of embodiments. Those of skill in the art will appreciate that the invention may additionally be practiced in other embodiments. First, the particular naming of the components, capitalization of terms, the attributes, data structures, or any other programming or structural aspect is not mandatory or significant, and the mechanisms that implement the invention or its features may have different names, formats, or protocols. Further, the system may be implemented via a combination of hardware and software, as described, or entirely in hardware elements. Also, the particular division of functionality between the various system components described herein is merely exemplary, and not mandatory; functions performed by a single system component may instead be performed by multiple components, and functions performed by multiple components may instead performed by a single component. For example, the particular functions of the fractal dithering engine 104 and so forth may be provided in many or one module.

[0044] Some portions of the above description present the feature of the present invention in terms of algorithms and symbolic representations of operations on information. These algorithmic descriptions and representations are the means used by those skilled in the computer graphics arts to most effectively convey the substance of their work to others skilled in the art. These operations, while described functionally or logically, are understood to be implemented by computer programs. Furthermore, it has also proven convenient at times, to refer to these arrangements of operations as modules or code devices, without loss of generality.

[0045] It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the present discussion, it is appreciated that throughout the description, discussions utilizing terms such as “processing” or “computing” or “calculating” or “determining” or “displaying” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system memories or registers or other such information storage, transmission or display devices.

[0046] Certain aspects of the present invention include process steps and instructions described herein in the form of an algorithm. It should be noted that the process steps and instructions of the present invention could be embodied in software, firmware or hardware, and when embodied in software, could be downloaded to reside on and be operated from different platforms used by real time network operating systems.

[0047] The present invention also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer readable storage medium, such as, but is not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, application specific integrated circuits (ASICs), or any type of media suitable for storing electronic instructions, and each coupled to a computer system bus. Furthermore, the computers referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability.

[0048] The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various general-purpose systems may also be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear from the description above. In addition, the present invention is not described with reference to any particular programming language. It is appreciated that a variety of programming languages may be used to implement the teachings of the present invention as described herein, and any references to specific languages are provided for disclosure of enablement and best mode of the present invention.

[0049] Finally, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the inventive subject matter. Accordingly, the disclosure of the present invention is intended to be illustrative, but not limiting, of the scope of the invention.