Thomas Howard and Dr. Bryan S. Morse, Computer Science
Introduction
When performing image quantization, palette selection has always been a difficult problem. All methods, although they may produce acceptable result for some images, perform poorly on others. The problem lies in deciding which colors are best to include in the quantized palette. For example, when quantizing an image that has a large gradient sky and multiple colors, a computer scientist is faced with a difficult choice. Either he can choose to allocate the colors of the palette to have a wide range of colors or he can give most of the colors to the gradient areas. The first will produce a brighter and more colorful image but leave the color gradients (e.g., sky) with few colors and a grainy look. The latter will produce beautiful gradients but the image will tend to be dull and washed out. We provide an algorithm that creates a balance in quantized palettes between color gradients and unique colors.
Procedure
Dithering, or interleaving two different colors to give the appearance of one uniform color, was key in our approach to solve this problem. All quantization algorithms use some form of dithering as a necessary secondary step to reduce the amount of visual error in the quantized image but none of them take this into account when initially selecting the palette. We asked the following question: “Can we take palette colors away from the gradient areas which could be dithered and use them to get a wider range of colors without introducing a visual difference in the gradient areas?”
In our research, we found three innovations that helped to accomplish this goal:
1. A new error metric that provides an adjustable balance between per-pixel and per-unique-color error.
2. Use of a bounding hull that guarantees that all colors in the image can be dithered from the selected palette.
3. Use of a ditherability-based approach that calculates quantization error based on a combination not only of the nearest palette color but also the most ditherable combination of palette colors.
The new cost function allows the palette selection to adapt to the number of unique colors in an image. As palette selection begins, the algorithm will begin by selecting many different colors thus ensuring that the image will have a wide range of colors. But, as the process continues, more and more colors will be allocated to the gradient areas, so that the change of color in the gradient areas will be moderate and not look grainy. The change to gradient allocation is gradual and controlled by a value that can be changed by the user. As a result, if the user is not pleased with the resulting image, he can adjust the value and rerun the program.
The use of a bounding hull guarantees that the colors will be able to be dithered because there are no color points that are not between two or more palette colors. Besides this, the initial hull makes the color selection more diverse and spread out over a wider range. This hull is especially effective when the desired number of colors is low.
The main problem faced with the ditherability-based approach is the large number of computations required to compute the most ditherable combination of palette colors for each color point. This problem is solved using the Delaunay Tetrahedralization of the currently selected palette points. Using the Deluanay Tetrahedralization allows us to quickly determine the closest, and most ditherable pallete points to any color point.
Like the new cost function, the dither-based implementation relies on a value that controls the ratio between the ditherability of each color point and the point-distance used to measure cost. This also allows the user, through trial and error to find an optimal result image.
Results
We found that considering dithering when making palette selection did improve quantized image quality. The images that were quantized using these advancements were less dull, had very little degradation in the gradient areas (sometimes even better), allowed user interaction, and adapted to a wide variety of images.
Experimentation showed that the images that used this new cost function had comparable gradients, brighter colors, and a larger number of unique colors. The value used to balance the number of colors for each image was different depending, on each user’s preferences.
In tests against traditional algorithms, using a hull resulted in generally brighter and more accurate colors, especially when the desired number of palette colors was low. The wider the range of unique colors was in the image, the more effective the hull tended to be. Even algorithms that split on the number of unique colors did not do as well in these tests.
The ditherability-based implementation shows promising results. Like the new cost function, the resulting images tended to be brighter and have comparable gradient areas.
A paper has been accepted for publication in IASTED Signal and Image Processing ’99 describing the new cost function and using a bounding hull. Further research on the ditherability-based approach will be submitted this coming winter for publication. Adobe, which also funded in part this research, has provided for another year of funding.
Future Research
There are many opportunities for future research in this area. When computed the Delaunay Tetrahedralization, we use a program called qhull. This program must be called externally and recomputed for each iteration. This causes the program to be slow as the number of allocated color points rises. It is believed that an decremental/incremental algorithm would not only be possible but also faster.
Currently, we are using a basic Floyd-Steinberg algorithm to do the dithering. A different, or modified algorithm might produce a more visually pleasing image.
When we are using the new cost function or ditherability-based algorithm we use two “sliders” to control the number of colors taken away from the gradients. It would be useful to investigate a way to automatically choose an optimal value based upon image content.
Finally, we have shown that each of the algorithms works well alone but we have done little research in combining the methods to see if the results can or cannot be improved.