XIL Programmer's Guide - Sun Microsystems

Skip to ContentJava Solaris Communities About Sun How to Buy My Account CartUnited StatesWorldwide

Sun Microsystems Documentation

docs.sun.com

Browse Documentation Titles

Browse Product Documentation

Help

View this Book Download this Book

A dither operation is an inverse lookup operation. As Figure 7-2 indicates, the dither operation matches a value (or values) in the source image--the image to be dithered--with a value from the output side of the lookup table being used, and then writes the corresponding value from the input side of the lookup table to a single-band destination image.

Note - Since the values in the source image don't actually match values in the output side of the table, each source-image value is paired with the value in the table closest to it.

The purpose of this dithering operation is to produce an image that when mapped forward through the lookup table will produce an image as similar as possible to the original source image. Another way to state this is that the dithering operation produces an image that when displayed using the lookup table as its colormap will look as much like the original as possible.

Such dithering operations have many applications, but a couple of them are by far the most common. One common use of dithering is to convert a true-color (3-band XIL_BYTE) image to a pseudocolor (1-band XIL_BYTE) image. Another common use is to convert a grayscale (1-band XIL_BYTE) image to a monochrome (1-band XIL_BIT) image.

Methods of Dithering

This section contains information about the three functions the XIL library provides for performing dithering operations: xil_nearest_color(), xil_error_diffusion(), and xil_ordered_dither().

`xil_nearest_color()`

The function xil_nearest_color() is the simplest of the dithering functions in that its algorithm for performing the inverse lookup described above is the most straightforward. This algorithm includes no provision for eliminating unwanted contours in the dithered image.

The function prototype for xil_nearest_color() is shown below.

Solaris XIL 1.2 AnswerBook >> XIL Programmer's Guide >> 7 Presentation Functions >> Dithering an Image

Previous: Casting an Image from One Data Type to Another

Dithering an Image

The XIL library provides several functions you can use to prepare images for display by dithering them. Before looking at these individual functions, though, the section explains what it means to dither an image in an XIL application.

What Is Dithering?

First, you need to know that the XIL library gives you the ability to pass a single-band image of any data type through a lookup table to produce a single-band or multiband image of the same or another data type. The lookup table used for this operation is a data structure of type XilLookup and has (among others) the following attributes:

An input data type
An output data type
A number of bands on the output side

Figure 7-1 shows a single-band XIL_BIT image being passed through a lookup table to produce a three-band XIL_BYTE image.

Figure 7-1 XIL Lookup Operation Figure 7-2 Dithering an Image


  void xil_nearest_color(XilImage src, XilImage dst,  
      XilLookup lookup);

The parameters src and dst are handles to the source image--the image to be dithered--and the destination image. The parameter lookup is a handle to the lookup table through which the source image will be passed to produce the destination. There are actually two types of lookup tables that can be referred to here. One is the generic lookup table that is used for lookup operations, and the other is a special type of lookup table called a colorcube. The basic difference between the two types of lookup tables is this: when you create a generic lookup table, you specify the dimensions of the table and the data to be stored in the table; when you create a colorcube, you specify the dimensions of the colorcube, and the function you use to create the colorcube fills in the data in the table for you. The sections below provide additional information about these two types of lookup tables.

Lookup Tables You can create a generic lookup table in one of two ways: using the function xil_lookup_create() or using the function xil_choose_colormap(). In either case, xil_nearest_color() pairs the values in your source image with values on the output side of the lookup table by searching for nearest matches. This means that for each pixel in your source image, xil_nearest_color() must examine each entry in the lookup table. This is a time-consuming process. However, generic lookup tables do give you the best control over the contents of your lookup table and, therefore, over the quality of the dithered image.

The function prototype for xil_lookup_create() is shown below.


  XilLookup xil_lookup_create(XilSystemState state,  
      XilDataType input_datatype, XilDataType output_datatype,  
      unsigned int output_nbands, unsigned int num_entries,  
      short first_entry_offset, void *table_data);

Here's an example of a time when you might want to use this function to create your lookup table. You have a true-color image that you want to dither to a single-band XIL_BYTE image, and you want to be able to display the dithered image using the currently installed X colormap. The code you use to create this lookup table might look like this:


  /* Read the color values stored in the X colormap and write them  
     to an array of Xil_unsigned8. The values should be written  
     in the following order: b , g , r , b , g , r , and so on. 000111  
     Let's say the array is called table_data */  
  
  xil_lookup_create(state, XIL_BYTE, XIL_BYTE, 3, 256, 0,  
      table_data);

Using this table for your dither operation enables you to produce a dithered image that contains the maximum number of unique values (256) and to display the image without having to write anything to the X colormap. You won't have to worry about colormap flashing. The disadvantage of this method is that there may be few or no exact matches between the RGB values in your source image and the RGB values on the output side of the lookup table. Clearly, this can affect how accurately the dithered image, when displayed, will reflect the original source image.

The other function you might use to create a lookup table for dithering the true-color image mentioned above to a pseudocolor image is xil_choose_colormap(). This function returns the best lookup table of a particular size to use in dithering the image. The best lookup table is defined to be the one that contains as many as possible of the most frequently used colors in the source image.

The function prototype for xil_choose_colormap() is shown below.


  XilLookup xil_choose_colormap(XilImage src, unsigned int size);

When you use this function to create your lookup table, there are two basic approaches you might take to dithering your true-color image. One approach is to use xil_choose_colormap() to create a lookup table that contains 256 entries. This strategy will produce a dithered image that looks very much like the original source image when displayed because the 256 most frequently used colors in the original will be reproduced exactly. However, you also have to get 256 specific colors into a hardware colormap to display your image. This will lead to colormap flashing on most displays.

A second approach is to use xil_choose_colormap() to create a lookup table with fewer than 256 entries, say 240 entries. You will still have most of the colors you need to display your image, and you can write those colors to your hardware colormap (if you only have one) without overwriting the first 16 entries in that colormap. This should prevent your application from contending with the OpenWindows^(TM) tools for colors.

Note - xil_choose_colormap() accepts only 3-banded XIL_BYTE source images.

Colorcubes You create a colorcube using the function xil_colorcube_create(). The prototype for this function is shown below.


  XilLookup xil_colorcube_create(XilSystemState state,  
      XilDataType input_type, XilDataType output_type,  
      unsigned int nbands, short offset, int multipliers[],  
      unsigned int dimensions[]);

Note that the parameters to this function are similar to those for xil_lookup_create(). However, you don't specify a number of entries in the lookup table or the data to be loaded into the table. Instead you provide arrays called dimensions and multipliers. The number of elements in both of these arrays must equal the number of bands in the image being dithered.

To understand the roles of dimensions and multipliers, consider the situation where you want to dither an XIL_BYTE RGB image to a 1-band XIL_BYTE image. To handle this case, you might declare and initialize dimensions and multipliers as follows:


  unsigned int dimensions[] = {4, 9, 6};  
  int multipliers[] = {1, 4, 36};

These values would lead to the creation of a colorcube that would dither blue values in the source image to one of 4 blue levels, green values to one of 9 green levels, and red values to one of 6 red levels. You could picture this colorcube as a cube with dimensions of 4, 9, and 6, but it's probably more helpful to think of it as a lookup table with three bands on the output side. Figure 7-3 shows what the first 22 elements of the 216-element table would look like.

Figure 7-3 Colorcube for Dithering a True-Color Image to a Pseudocolor Image

This illustration should help clarify the significance of the three elements of multipliers. The element multipliers[0] indicates the distance between changes in blue levels on the output side of the table, multipliers[1] indicates the distance between changes in green levels, and multipliers[2] indicates the distance between changes in red levels. That is, the blue level changes with each entry, the green level changes every fourth entry, and the red level changes every thirty-sixth entry.

Note - The elements of multipliers can be negative numbers. Negative numbers indicate that the values in a color ramp should appear in decreasing as opposed to increasing order.

The values in the table are calculated by xil_colorcube_create() based on the dimensions and multipliers you supply. This means that when you dither an image using a colorcube, the dither function does not need to search the output side of a lookup table to find a set of values. Instead, it can calculate the value to be written to the dithered image using the values stored in the dimensions and multipliers arrays. As a result, dithering operations that use a colorcube are much faster than those that use a generic lookup table. What you give up is control over the exact contents of the colorcube.

One other note about colorcubes. Although they are called colorcubes, colorcubes need not have three dimensions. As mentioned earlier, a colorcube has a number of dimensions equal to the number of bands in the image to be dithered. Therefore, to create a colorcube suitable for dithering a grayscale image to a monochrome image, you might define dimensions and multipliers as follows.


  unsigned int dimensions[] = {2};  
  int multipliers[] = {-1};

Note - The XIL library creates two colorcubes when you initialize the library. One of these has the dimensions 4:9:6 and is useful for dithering RGB images to 216 colors. The other has the dimensions 8:5:5 and is useful for dithering YCbCr images to 200 colors. To get a handle to one of these colorcubes, use the function xil_lookup_get_by_name().

In addition to xil_colorcube_create(), the XIL library contains the colorcube-related functions shown in Table 7-3.

***Table 7-3*** Functions for Managing Colorcubes
Function Name	What the Function Does
`xil_lookup_get_colorcube`	Determines whether a lookup table is a colorcube or a generic lookup table
`xil_lookup_get_colorcube_info`	Determines whether a lookup table is a colorcube and, if it is, returns the dimensions and multipliers used to create the colorcube and the colorcube's origin

`xil_error_diffusion()`

The function xil_error_diffusion() is similar to xil_nearest_color(), but in addition to performing an inverse lookup, it uses a process called error diffusion to deal with any difference between a source-image pixel value and a value on the output side of a lookup table with which that pixel value is matched. The difference (or error) is distributed to the source-image pixels immediately to the right of and below the last pixel processed.

The function prototype for xil_error_diffusion() is shown below:


  void xil_error_diffusion(XilImage src, XilImage dst,  
      XilLookup lookup, XilKernel distribution);

The first three parameters are the same as the parameters to xil_nearest_color(). The parameter src is a handle to your source image, and dst is a handle to your destination image. The parameter lookup can be either a generic lookup table or a special type of lookup table called a colorcube. For information about these lookup tables, see the sections "Lookup Tables" on page 108 and "Colorcubes" on page 110. The final parameter, distribution, is an error-distribution kernel.

Note - XIL kernels (data structures of type XilKernel) are used primarily for convolution operations, which are discussed in the section "Filtering an Image" on page 187. The utility functions that affect kernels are also discussed in that section.

You create the error-distribution kernel using the function xil_kernel_create(), whose function prototype is shown below.


  XilKernel xil_kernel_create(XilSystemState system_state,  
      unsigned int width, unsigned int height, unsigned int keyx,  
      unsigned int keyy, float *data);

The parameters width and height determine the size of the kernel, keyx and keyy determine the kernel's origin, and data is a pointer to the floating-point values to be stored in the kernel. For example, the code below creates a 3-by-3 kernel with an origin of 1,1.


  XilKernel kernel;  
  float kernel_data[] = {  
      0/16.0, 0/16.0, 0/16.0,  
      0/16.0, 0/16.0, 7/16.0,  
      3/16.0, 5/16.0, 1/16.0  
  };  
  
  kernel = xil_kernel_create(state, 3, 3, 1, 1, kernel_data);

Note - The library provides a special shorthand method of creating the kernel shown above because it is used so commonly in error-diffusion operations. This method is to call the function xil_kernel_get_by_name() using a name of "floyd-steinberg".

Figure 7-4 shows what this kernel looks like.

Figure 7-4 Error-Distribution Kernel

Note - The value of the kernel's origin and of the elements above and to the left of the origin must be 0 when you're calling xil_error_diffusion().

Here's how xil_error_diffusion() uses the kernel. Say that you're dithering a grayscale image with values in the range 0 to 255 to a grayscale image with values in the range 0 to 4. This situation is shown in Figure 7-5.

Figure 7-5 Using xil_error_diffusion() to Dither an Image

When the pixel in the middle of the top scanline of the source image (31) is passed through the lookup table, it is matched with a 26, so a 0 is written to the destination image. When the destination is displayed using the lookup table as its colormap, this pixel will have the value 26. Thus, in the dither-and-reconstruction process, there will be an error of 5 (31 - 26). To counteract the loss of data inherent in this process, xil_error_diffusion() distributes this error before passing the next pixel (219) through the lookup table. The way in which the error is distributed depends on the kernel created earlier. See Figure 7-6 for an example.

Figure 7-6 Error Diffusion

The kernel is laid on top of the source image so that its origin aligns with the last pixel to be passed through the lookup table. Before the next pixel is passed through, the following processing will take place:

The pixel at 0,2 will be set to 219 + (5 * (7 / 16.0))
The pixel at 1,0 will be set to 187 + (5 * (3 / 16.0))
The pixel at 1,1 will be set to 121 + (5 * (5 / 16.0))
The pixel at 1,2 will be set to 73 + (5 * (1 / 16.0))

This processing is fairly time-consuming, but can greatly reduce contouring in the dithered image.

`xil_ordered_dither()`

The XIL library's third dithering function is xil_ordered_dither(). Like xil_nearest_color() and xil_error_diffusion(), xil_ordered_dither() processes an image by performing an inverse lookup. However, two characteristics distinguish xil_ordered_dither() from the other dithering functions. One is that the lookup table the function uses to do its job must be a colorcube; it cannot be a generic lookup table. (For information about the differences between colorcubes and generic lookup tables, see the sections "Lookup Tables" on page 108 and "Colorcubes" on page 110.) Second, xil_ordered_dither() makes use of an XIL data structure called a dither mask to help eliminate contouring in the dithered image.

The function prototype for xil_ordered_dither() is shown below.


  void xil_ordered_dither(XilImage src, XilImage dst,  
      XilLookup lookup, XilDitherMask mask);

The parameters src and dst are handles to the source and destination images, and lookup is the lookup table to be used for the dither operation. As mentioned above, this lookup table must be a colorcube; that is, it must have been created with the function xil_colorcube_create()--or xil_lookup_get_by_name(). The final parameter, mask, is the dither mask, a data structure of type XilDitherMask.

You create the dither mask using the function xil_dithermask_create(), whose prototype is shown below.


  XilDitherMask xil_dithermask_create(XilSystemState state,  
          unsigned int width, unsigned int height,  
          unsigned int nbands, float *data);

The parameters width and height define the width and height of the dither mask in pixels. These values are user defined. The next parameter, nbands, determines the number of bands in the dither mask. This number must match

the number of bands in the image being dithered. Finally, data is a pointer to the data to be stored in the dither mask. All the values in the mask must fall in the range 0.0 to 1.0. For example, the code below creates a 1-band, 4-by-4 dither mask.


  XilDitherMask mask;  
  float mask_data[] = {  
       0/16.0, 8/16.0, 2/16.0,10/16.0,  
      12/16.0, 4/16.0,14/16.0, 6/16.0,  
       3/16.0,11/16.0, 1/16.0, 9/16.0,  
      15/16.0, 7/16.0,13/16.0, 5/16.0  
  }  
  
  mask = xil_dithermask_create(state, 4, 4, 1, mask_data);

Note - When you initialize the XIL library, four standard dither masks are created: 1- and 3-band 4-by-4 masks and 1- and 3-band 8-by-8 masks. To get a handle to one of these masks, you use the function xil_dithermask_get_by_name().

Here's how the mask is used. Assume that you're dithering a grayscale image with values in the range 0 to 255 and that the destination is to contain values in the range 0 to 15. First, think of the 4-by-4 dither mask as having been replicated over the entire source image, as depicted in Figure 7-7.

Figure 7-7 Dither Mask Replicated over a Source Image

At this point, each pixel in each 4-by-4 block of the image has been associated with (in this case) a unique dither-mask value. The xil_ordered_dither() function then performs the following steps for each pixel in the image:

Passes the value through the lookup table.
In this step, the function is actually dividing values in the source image by 17 (the number of values that can be represented in 8 bits divided by the length of the colorcube minus one). That is, if no further processing were to take place, a 200 in the source image would map to an 11 since 200 divided by 17 equals 11.76.
Considers the dither-mask value associated with the source-image pixel value.
The dither function now compares the fractional part of the quotient from the division operation with the source pixel's dither-mask value. If the fractional part is greater than the dither-mask value, the dividend shown above (11) is incremented by one, so a 12 is written to the destination image. Otherwise, an 11 is written to the image.

When you use the dither mask in this way, you're essentially performing averaging. This averaging helps prevent undesirable contours from appearing in the dithered image.

Table 7-4 below lists the XIL utility functions that affect dither masks and indicates what these functions do.

***Table 7-4*** Utility Functions for Dither Masks
Function Name	What It Does
`xil_dithermask_destroy`	Deallocates the memory used by a dither mask
`xil_dithermask_get_height`	Returns the height of a dither mask in pixels
`xil_dithermask_get_width`	Returns the width of a dither mask in pixels
`xil_dithermask_get_nbands`	Returns the number of bands in a dither mask
`xil_dithermask_create_copy`	Returns a copy of a dither mask
`xil_dithermask_set_name`	Sets the name of a dither mask
`xil_dithermask_get_name`	Returns a copy of a dither mask's name

When to Use Each Dithering Function

When you're trying to decide on the best way to perform a dither operation, it's helpful to think of the matrix shown in Table 7-5:

***Table 7-5*** Review of Dithering Operations
	Generic Lookup	Colorcube
xil_nearest_color()	v	v
xil_error_diffusion()	v	v
xil_ordered_dither()		v

If you look at the right column--labeled "Colorcube"--you'll see that each of the dithering functions can perform its inverse lookup using a colorcube. If you compare the functions used with a colorcube, you'll see that choosing one over another involves a trade-off between speed and quality. The function xil_nearest_color() is the fastest, but produces the poorest quality image, and xil_error_diffusion() is the slowest, but produces the best quality image. The function xil_ordered_dither() is somewhat faster than xil_error_diffusion(), but does not produce quite as nice an image.

Similarly, if you compare operations that use generic lookup tables, the trade-off is one between speed and quality. The guidelines mentioned in the preceding paragraph apply, except that xil_ordered_dither() cannot work with a generic lookup table.

Now, if you read the table from left to right, you can compare operations that use generic lookup tables with corresponding operations that use colorcubes. Operations that use colorcubes are much faster than their counterparts because operations that use colorcubes do not need to search a lookup table. On the other hand, when you use a colorcube for dithering, you lose some of your control over the quality of the dithered image, because you cannot specify the exact values in the colorcube. You also lose the ability to use the colors in the currently installed colormap, again because you don't specify the values to be written to the lookup table.

	Search all books for
		Search only this book
	Search Tips