Writing a Multithreaded Image Dithering Program with Rust 🦀🖼️

Check out the project here: https://github.com/NabeelAhmed1721/ordered-dithering/

I have been interested in the Rust programming language for the past couple of months. Coming from JavaScript, a weakly typed language, I find that Rust is much more strict and requires more thought when developing a control flow.

Just for the record, dithering isn't usually done on the CPU. It's a task best suited for a GPU, where it can take advantage of parallelism. I used this project as a way to learn about Rust and multithreading. If you want a guide for dithering done on a GPU, take a look at this.

Overview

Simply put, dithering is the process of adding noise to quantized data. To understand quantized data, think about omitting information needed to represent some data, for example, using less color to express an image.

It's important to note that dithering is a general term in information processing. With its use stretching far into audio, radar, weather, and many other applications, it isn't limited to images.

There are several image dithering techniques, my project uses Ordered or Bayer Dithering. Is it the most practical? Probably not. But if you ask me, I think it visually looks the most interesting.

Anyway, before we dive into the project itself, here are some results to entice you to continue reading:

Dithered Image of Apple (8-bit color)

Dithered Image of Sunlight through Leaves (8-bit color)

Dithered Image of Lava (8-bit color)

Ordered Dithering

To dither an image using ordered dithering, we must compare every pixel in the source image with an input palette and a threshold matrix (commonly referred as Bayer Matrix or Filter).

For the sake of consistency, our project will use an 8-bit color palette, which includes the following colors:

const PALETTE: [Color; 8] = [
    Color(0, 0, 0),          // black
    Color(255, 0, 0),        // red
    Color(0, 255, 0),        // green 
    Color(0, 0, 255),        // blue
    Color(255, 255, 0),      // yellow
    Color(255, 0, 255),      // magenta
    Color(0, 255, 255),      // cyan
    Color(255, 255, 255),    // white
];

You are free to use any assortment of colors, however, I find that the 8-bit color range has a reliable balance of colors that works for most images.

To generate a threshold matrix, we can use the following recursion formula to create a Bayer Matrix to the $n$ 'th level:

$$Bayer(n) = \begin{bmatrix} 4 \cdot Bayer(n - 1) + 0 & 4 \cdot Bayer(n - 1) + 2 \\ 4 \cdot Bayer(n - 1) + 3 & 4 \cdot Bayer(n - 1) + 1 \end{bmatrix}$$

where for every $n$ 'th level, the matrix is $2^{n+1} \times 2^{n+1}$ and contains numbers from $0$ to $2^{2n+2}$ .

Full credit of this equation and a special thanks goes to this wonderful article by Surma.

In practice, however, this type of computation quickly becomes expensive to generate during runtime, so it's more reasonable to reference from a pre-generated matrix. Hence, why my program uses a pre-generated $8 \times 8$ threshold matrix, which looks like the following:

$$\begin{bmatrix} 0 & 32 & 8 & 40 & 2 & 34 & 10 & 42 \\ 48 & 16 & 56 & 24 & 50 & 18 & 58 & 26 \\ 12 & 44 & 4 & 36 & 14 & 46 & 6 & 38 \\ 60 & 28 & 52 & 20 & 62 & 30 & 54 & 22 \\ 3 & 35 & 11 & 43 & 1 & 33 & 9 & 41 \\ 51 & 19 & 59 & 27 & 49 & 17 & 57 & 25 \\ 15 & 47 & 7 & 39 & 13 & 45 & 5 & 37 \\ 63 & 31 & 55 & 23 & 61 & 29 & 53 & 21 \\ \end{bmatrix}$$

The differences in matrix sizes reflect the complexity of the dithering pattern on the output image. A small $2 \times 2$ matrix produces an output with striking contrast and a rugged dithering pattern. While a larger $32 \times 32$ matrix results in smoother contrast with a granular dithering pattern. However, there are diminishing returns with larger matrix sizes— I find that an $8 \times 8$ matrix works best to smooth colors but also maintain that pixelated-dithered look.

To reduce complexity, I express the matrix as a 2D array, and through the calculations below, I can convert the x-y coordinates of the image to a value I can use to index the array:

// 8x8 Bayer Matrix
const MATRIX_WIDTH: u32 = 8;
const MATRIX: [u16; 64] = [
    0, 32, 8, 40, 2, 34, 10, 42, 48, 16, 56, 24, 50, 18, 58, 26, 12, 44, 4, 36,
    14, 46, 6, 38, 60, 28, 52, 20, 62, 30, 54, 22, 3, 35, 11, 43, 1, 33, 9, 41,
    51, 19, 59, 27, 49, 17, 57, 25, 15, 47, 7, 39, 13, 45, 5, 37, 63, 31, 55,
    23, 61, 29, 53, 21,
];

fn get_bayer(x: u32, y: u32) -> u16 {
    let pos = x % MATRIX_WIDTH
            + ((y * MATRIX_WIDTH) % (MATRIX_WIDTH * MATRIX_WIDTH));

    MATRIX[pos as usize]
}

We need to, however, map the threshold value from $[0, 2^{2n+2}]$ to $[0, 255]$ because the RGB color values of the input image will be between 0 and 255. To solve this, I used a simple range mapping formula:

pub fn map_range_value(
    value: u32,
    range_in: (u32, u32),
    range_out: (u32, u32),
) -> u32 {
    return (value - range_in.0) * (range_out.1 - range_out.0)
        / (range_in.1 - range_in.0)
        + range_out.0;
}

Combining what we know, we can calculate our threshold value for a given pixel at an x-y coordinate with the following expression:

let bay = utility::map_range_value(
    Dither::get_bayer(x, y),
    (0, 64),
    (0, 255),
);

To calculate the quantized value of a given pixel color, we multiply the bay value with a spread value. The product is then summed with the input color, which is adjusted by a gamma value:

let quantize_value = |c: u8| -> u8 {
    f32::min(
        255.0 * f32::powf(f32::from(c) / 255.0, self.gamma)
            + self.spread * f32::from(bay),
        255.0,
    ) as u8
};

let query_color =
    Color(quantize_value(r), quantize_value(g), quantize_value(b));

Finally, we use query_color to search for the closest match in the defined palette. The closest color match is then set as the pixel value at the given x-y coordinate on the output image. Repeating this process for every pixel in an input image will result in an dithered output image.

Multithreading

Since the dithering process itself can run on each pixel independently, in other words, an individual pixel doesn't need to know the state of another pixel, this creates an ideal opportunity for multithreading. Fortunately, because of Rust's borrow checker, multithreading is simple and intuitive. Common bugs such as data races, locks, and memory leaks, are harder to encounter.

Depending on the application, multithreading can get hard to manage. I find it helpful to visualize the control flow to prevent confusion when programming. The following is how I expect my program to run:

Dividing the image into separate even chunks allows for a convenient collection process. Since each thread is assigned an ID, we can use the following formulas to calculate the starting and ending locations of each chuck:

let thread_location_start =
    (area / self.thread_count) * thread_id;

let mut thread_location_end =
    (area / self.thread_count) * (thread_id + 1) - 1;

// looping through specific chunk
for i in thread_location_start..thread_location_end {
    // dithering logic...
}

To identify and manage threads, I created separate helper module called worker. Within the module, a struct called Manager stores all threads (individually called Worker) in a vec and executes a collect method when threads complete. Overall, this allowed me to abstract multithreading logic and keep my code more manageable.

let mut manager = worker::Manager::<DitherJob>::new(THREAD_COUNT);
let worker_count = manager.worker_count;

let dither = Arc::new(Dither::new(
    worker_count,
    reference_image,
    &PALETTE,
    GAMMA,
    SPREAD,
));

manager.set_workers(&|id| {
    let dither = Arc::clone(&dither);
    thread::spawn(move || dither.dither_section(id))
});

manager.collect(&mut output);

Notice how Dither is wrapped Arc::new. To safely share ownership of data across threads, an Atomic Reference Counter (Arc) needs to be used. It keeps count of the owners and drops the value when no threads are using it.

Conclusion

Overall, I’m pleased with how the program turned out. With me still learning Rust, this project has helped me to become more confident in using the language and allowed me to explore new ideas in image processing.

I hope you enjoyed reading my article, and again, feel free to check out the project below:

https://github.com/NabeelAhmed1721/ordered-dithering/

Thank you,
Nabeel Ahmed