JPEG Display Process page-2

JPEG Display Process

4 Octrees
The third method for quantization we like to introduce is an approach that is known under the name octree quantization. The idea here is to build a tree structure containing always a maximum of K different colors. If a further color is to be added to the tree structure, its color value has to be merged with the most likely one that is already in the tree. The both values are substituted by their mean.

The most important data structure is the nodes of the octree. Each inner node of the octree contain a maximum of eight successors, the leave nodes keep information for the color value (colorvalue), the color index (colorindex), and a counter (colorcount) for the pixel that are already mapped to a particular leave. Because each of the red, green and blue value is between 0 and 255 the maximum depth of the tree is eight. In level i Bit i of RGB is used as selector for the successors.

The octree is constructed during reading the image that is to be quantized. Only that parts of the octree are created that are really needed. Initially the first K values are represented exactly (in level eight). When the number of leaf nodes (current K) exceeds K, the tree has to reduce. That would mean that leaves at the largest depth are substituted by their predecessor:

children=0
for successor[i=1..8] do
{

if successor[i] != NULL then

{

children = children + 1

sum the colorvalues and colorcount

successor[i] = NULL

}
}

currentK = currentK - children + 1

In the end the octree for the entire image is generated. The K leaves are used as entries for the color look-up table. The representative color value for a leave is computed as the mean value of the color value and the color count. The color index is also stored in the octree.

The quantization of the image is performed in a second step. Again the image has to be read. The color values of each pixel are used for traversing the octree data structure. The search along a path through the tree is finished when a leave node is reached.

5. Error Distribution:

Applying quantization algorithms still result in errors. , Even the color value is as close to the color value as possible it is only an approximation of the true color value. This is especially visible to the viewer if a discontinuity appear. This effect appears when in the original image only small color changes exist (e.g. in a color shade) in the quantized image different color values appears. That is the reason why a quantized image has to be postprocessed in terms of error distribution.

5.1 Error Diffusion via a Dither Matrix:

The basic strategy of dithering is to trade intensity resolution for spatial resolution. Originally, dithering was developed to increase the apparent color resolution of a display without reducing the spatial resolution.

Applying a dither matrix to an image that is displayed on a monitor that has not the full color spectrum available but only a selectable subset. By averaging the intensities of neighboring pixels one can get the impression of colors that are not represented in the colormap. The human eye will do the spatial blending if the resolution of the display is high enough. Therefore a color value is compared to a threshold matrix. This fits as long as the spectator keeps a certain distance to the monitor, what is the normal case. Experiments with a monitor that has only a color look-up-table with 256 entries available show good results.

For the 2 x 2 size the dither matrix, called D (2) is

| 0 2|

| 3 1|

Larger dither matrices can be produced by applying a recurrence relation to compute D (2n) from D (n) . With the matrix U (n) defined as as an n x n matrix of 1s, that is,

| 1 1 1 ... 1 |

| 1 1 1 ... 1 |

| 1 1 1 ... 1 |

| . . . ...... |

| 1 1 1 ... 1 |

The recurrence relation is D(n) =

| 4*D(n/2)+D(2)00*U(n/2) 4*D(n/2)+D(2)01 * U(n/2)|

|4*D(n/2)+D(2)10*U(n/2) 4*D(n/2)+D(2)11*U(n/2) |

The entire algorithm looks like described below:
void set_color_palette( )
{
int r, g, b, colorindex = 0;
for (r=0; r<64; r+=9 )
for (g=0; g<64; g+=9 )
for (b=0; b<64; b+=21 )
{

setrgbpalette(colorindex, r, g, b);

colorindex = colorindex + 1;
}
}
void put_dither_pixel(int x, int y, unsigned char *pix)
{
unsigned char r,g,b;
unsigned char ri, gi, bi;
unsigned char DitherMatrix[4][4] = { { 0, 8, 2, 10 },{ 12, 4, 14, 6 },{ 3, 11, 1, 9 },

{ 15, 7, 13, 5 } };
unsigned char Ditherval;
Ditherval = DitherMatrix[x&3][y&3];
r = pix[0] >> 2;
g = pix[1] >> 2;
b = pix[2] >> 2;
ri = (r >> 3); if (ri != 0 && ((r&7)<<1) <= Ditherval ) ri--;
gi = (g >> 3);
if (gi != 0 && ((g&7)<<1) <= Ditherval ) gi--;
bi = (b >> 4);
if (bi != 0 && (b&15) <= Ditherval ) bi--;
putpixel(x,y, (255 & ((ri<<5)) | (gi<<2) | bi));
}

5.2 Floyd Steinberg:

The error, that is the difference between the exact pixel value and the approximated value actually displayed, is spread to the color values of the four pixels below and right to the pixel in question. 7/16 is added to the pixel to the right, 3/16 to the pixel below and the left, 5/16 immediately below, and 1/16 to the pixel below and the right. Figure XX was created using this method. To make sure that no unwanted effects appear in the image by diffusing the error over several pixels in the image, we have to ensure that the error term that is divided and spread to four pixels is exactly the appeared error. Therefore on the fourth pixel the error minus the sum of the already distributed error share:

fourtherror = error - 15/16 * error.

Even better results can be achieved by alternating the scan direction and the error diffusion form left to right and vice versa. The Floyd-Steinberg approach is a serial process and that any pixel value affects all the pixels to the lower right of that pixel in the image. Another approach, ordered dither techniques, localize the effect of any single pixel.

One big drawback of this approach is that the error made by approximating the accurate value is accumulated over the entire image. All errors that were made on the pixels on the left and up a pixel in question have to be considered again and lead to a significantly larger error. This error is more disturbing the impression on the complete image than making more but smaller errors in approximating the color values of a pixel.

Conclusion of Color Quantization:

The procedure of finding the best entries for the look up table is time and memory consuming. Better quantization results require more run time and memory (e.g. octree algorithm). It has also to be considered that in a larger context the best color quantization for a specific picture conflicts with the default color values of the system and maybe also with the optimized quantization of another picture.

If the algorithms are evaluated in terms of resource allocation (memory and computation time) and quality issues (what does the user realize when he/she views and compares the original image with the color reduced image?) with respect to the results based in the test image the following assessment can be given:

Octree algorithm
+ On the one hand the algorithm leads to the best results but on the other hand
- it is very memory and time consuming.

The algorithm is well suited for images that have to be displayed with the best quality and the quantization process is not considered. Artifacts may appear as local discontinuities in a color shade. A combination between the octree algorithm and the dithering technique is not appreciated because the color table entries are not equidistant. In comparison with the other algorithms this approach needs a larger implementation effort.

Static color table in combination with dithering
+ This approach gives very reasonable results with respect to quantization errors and
+ the relation between computation time and memory requirements and the available result is the best.

The combination of a static color table with dithering works well for interactive work and fast viewing of arbitrary images.

Static color table in combination with Floyd Steinberg

+ The combination of static color table and Floyd Steinberg Error diffusion is also fast.
- It but leads to visible artifacts especially on low display resolution that are very disturbing.

Median cut algorithm
- It leads to discontinuities.

Popularity algorithm

- This algorithm leads also to discontinuities.

- In comparison with a static color table solution that is combined with dithering it leads to extremely bad results. It especially does not map color values that are not very often used in the original image to another but similar color value (for example look at the butterfly in the test image).

Quantization can immensely be improved by applying error distribution techniques. Sometime efforts are made to speed up that process. The above mentioned methods are modified to improve computation time and/or reduce memory requirements:

Examples for this are:

· The Popularity algorithm can gain further speed when only pixels are considered that where selected from the image to be quantized randomly with stochastic methods (but this may reduce quality!).

· The Median cut algorithm can be improved when the algorithm stops making subcubes when the human eye is no longer able to differ between different color. The algorithm takes into consideration that human eye can differ more red colors than blue colors and so make more intersections along the red axis than along the axis in the color cube.

Raster Display and Interaction

In cases of rapid previewing of rendering and image processing results static color table combined with dithering seems to achieve good results even on display with low resolution.

It also allows working interactively with the system. The error distribution with Floyd Steinberg leads to visual artifacts (locally large errors).