Pillarland by Nabeel Ahmed

Check out the project here: 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. Ordered dithering is results in a more checkerboard-like which can make it harder to preserve details in the image. However, it is much faster to compute and 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:

rust

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}$ power:

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

where for every $n^{th}$ power, 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 &\quad 32 &\quad 8 &\quad 40 &\quad 2 &\quad 34 &\quad 10 &\quad 42 \\ 48 &\quad 16 &\quad 56 &\quad 24 &\quad 50 &\quad 18 &\quad 58 &\quad 26 \\ 12 &\quad 44 &\quad 4 &\quad 36 &\quad 14 &\quad 46 &\quad 6 &\quad 38 \\ 60 &\quad 28 &\quad 52 &\quad 20 &\quad 62 &\quad 30 &\quad 54 &\quad 22 \\ 3 &\quad 35 &\quad 11 &\quad 43 &\quad 1 &\quad 33 &\quad 9 &\quad 41 \\ 51 &\quad 19 &\quad 59 &\quad 27 &\quad 49 &\quad 17 &\quad 57 &\quad 25 \\ 15 &\quad 47 &\quad 7 &\quad 39 &\quad 13 &\quad 45 &\quad 5 &\quad 37 \\ 63 &\quad 31 &\quad 55 &\quad 23 &\quad 61 &\quad 29 &\quad 53 &\quad 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 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:

rust

// 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:

rust

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:

rust

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:

rust

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:

Multithreading Control Flow

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:

rust

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.

rust

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.

Writing a Multithreaded Image Dithering Program

Overview

Ordered Dithering

Multithreading

Conclusion