Dithering and Colour and Noise, Oh My!

Abstract

Spatial dithering, also known as digital halftoning, is a technique used to simulate a higher color depth in images using a limited color palette (Akarun, Yardunci, and Cetin 1997). It approximates shades of colour not available in the palette using a spatial distribution of available colours, taking advantage of the human eye’s tendency to average colours in a neighbourhood. This technique has its origins in the printing industry: halftoning is the process of rendering an image as a pattern of coloured dots, exchanging color resolution or bit depth for spatial resolution (Akarun, Yardunci, and Cetin 1997).

Common issues that are addressed by dithering are colour shift and false contours . When an image is quantized, the luma and chroma of the area covered by each pixel is classified into one of the available colors in the device’s palette, resulting in a shift that may be visible to the naked eye. When there are insufficient colours to represent an otherwise smooth transition, banding, or the formation of false edges may occur (Deshpande, Misra, and Narayanan 2011). Low level graphics libraries, image processing toolkits, as well as graphics drivers and output peripherals themselves, use dithering as a computationally cheap way to work around these issues.

Throughout its history, Krita used 8-bit resolution and the sRGB color space exclusively to render gradients, ignoring the color space and bit depth of the image. This resulted in very visible banding artifacts, a behaviour that was reported in bug 343864. During the last month of 2020 and the start of 2021, we implemented high dynamic range gradients by rendering the gradient in the image’s color space, with 16-bit as a minimum depth, and adding dithering in the gradient’s render step if the image’s depth is lower. This talk will analyze the technical aspects of this work. We will start by summarizing the available techniques for achieving perceptually similar images in monitors and their tradeoffs; in the second part, we will describe our work, its main features and the end results.

Deliverables

This project implemented HDR gradients throughout all our supported colorspaces. The backbone of the implementation was Basile Clement’s implementation of ordered dithering for Pixman/Cairo (commits: ddcc41b, cb2ec42). These treated dithering as the controlled addition of quantization noise in normalized floating point colour space. The dithering techniques involved were 16x16 Bayer and 64x64 blue noise dithering, with an included void-and-cluster generator (for our purposes, we reused the generated matrix of Pixman’s).

My implementation proposes the following changes:

• Addition of a new abstract colour space operator class, KisDitherOp
• Refactoring of the Pixman implementation as a templated KisDitherOp subclass, named KisDitherOpImpl
• Design and implementation of a triple-layered Russian doll template, that enables creation and initialization of all the operator instances at build time
• Refactoring of the Pixman code flow to improve compatibility with SIMD optimizations

This work was merged as !668, and is already available in our Krita Next nightly builds.

Media coverage

I gave a short talk about the porting effort at the Libre Computer Graphics 2021 conference.

References

1. Akarun, L., Y. Yardunci, and A. E. Cetin. 1997. “Adaptive Methods for Dithering Color Images.” IEEE Transactions on Image Processing 6 (7): 950–55. https://doi.org/10.1109/83.597270.
2. Deshpande, Aditya, Ishan Misra, and P. J. Narayanan. 2011. “Hybrid Implementation of Error Diffusion Dithering.” In 2011 18th International Conference on High Performance Computing, 1–10. https://doi.org/10.1109/HiPC.2011.6152714.