Writing a Multithreaded Image Dithering Program with Rust 🦀🖼️

Try the challenge right here: https://github.com/NabeelAhmed1721/ordered-dithering/

I’ve been within the Rust programming language for the previous couple of months. Coming from JavaScript, a weakly typed language, I discover that Rust is rather more strict and requires extra thought when creating a management move.

Only for the report, dithering is not normally achieved on the CPU. It is a process greatest fitted to a GPU, the place it will probably reap the benefits of parallelism. I used this challenge as a technique to find out about Rust and multithreading. If you would like a information for dithering achieved on a GPU, take a look at this.

Overview

Merely put, dithering is the method of including noise to quantized knowledge. To know quantized knowledge, take into consideration omitting info wanted to symbolize some knowledge, for instance, utilizing much less shade to specific a picture.

It is vital to notice that dithering is a normal time period in info processing. With its use stretching far into audio, radar, climate, and lots of different functions, it is not restricted to photographs.

There are several image dithering techniques, my challenge makes use of Ordered or Bayer Dithering. Is it essentially the most sensible? In all probability not. However if you happen to ask me, I feel it visually seems essentially the most fascinating.

Anyway, earlier than we dive into the challenge itself, listed below are some outcomes to entice you to proceed studying:

Ordered Dithering

To dither a picture utilizing ordered dithering, we should examine each pixel within the supply picture with an enter palette and a threshold matrix (generally referred as Bayer Matrix or Filter).

For the sake of consistency, our challenge will use an 8-bit shade palette, which incorporates the next colours:

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’re free to make use of any assortment of colours, nevertheless, I discover that the 8-bit shade vary has a dependable steadiness of colours that works for many photographs.

To generate a threshold matrix, we are able to use the next recursion method to create a Bayer Matrix to the

n

‘th degree:

the place for each

n

‘th degree, the matrix is

2n+1×2n+1

and comprises numbers from

0

to

22n+2

.

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

In apply, nevertheless, the sort of computation shortly turns into costly to generate throughout runtime, so it is extra cheap to reference from a pre-generated matrix. Therefore, why my program makes use of a pre-generated

8×8

threshold matrix, which seems like the next:

The variations in matrix sizes mirror the complexity of the dithering sample on the output picture. A small

$2 occasions 2$

2×2

matrix produces an output with placing distinction and a rugged dithering sample. Whereas a bigger

$32 occasions 32$

32×32

matrix ends in smoother distinction with a granular dithering sample. Nonetheless, there are diminishing returns with bigger matrix sizes— I discover that an

$8 occasions 8$

8×8

matrix works greatest to clean colours but in addition keep that pixelated-dithered look.

To scale back complexity, I categorical the matrix as a 2D array, and thru the calculations beneath, I can convert the x-y coordinates of the picture to a price 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 have to, nevertheless, map the brink worth from

[0,22n+2]

to

[0,255]

as a result of the RGB shade values of the enter picture shall be between 0 and 255. To unravel this, I used a easy vary mapping method:

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

Combining what we all know, we are able to calculate our threshold worth for a given pixel at an x-y coordinate with the next expression:

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

To calculate the quantized worth of a given pixel shade, we multiply the bay worth with a unfold worth. The product is then summed with the enter shade, which is adjusted by a gamma worth:

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

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

Lastly, we use query_color to seek for the closest match within the outlined palette. The closest shade match is then set because the pixel worth on the given x-y coordinate on the output picture. Repeating this course of for each pixel in an enter picture will end in an dithered output picture.

Multithreading

Because the dithering course of itself can run on every pixel independently, in different phrases, a person pixel does not must know the state of one other pixel, this creates an excellent alternative for multithreading. Thankfully, due to Rust’s borrow checker, multithreading is easy and intuitive. Widespread bugs comparable to knowledge races, locks, and reminiscence leaks, are more durable to come across.

Relying on the appliance, multithreading can get onerous to handle. I discover it useful to visualise the management move to forestall confusion when programming. The next is how I count on my program to run:

Dividing the picture into separate even chunks permits for a handy assortment course of. Since every thread is assigned an ID, we are able to use the next formulation to calculate the beginning and ending places of every chuck:

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

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

// looping by way of particular chunk
for i in thread_location_start..thread_location_end {
    // dithering logic...
}

To determine and handle threads, I created separate helper module referred to as employee. Inside the module, a struct referred to as Supervisor shops all threads (individually referred to as Employee) in a vec and executes a acquire technique when threads full. Total, this allowed me to summary multithreading logic and maintain my code extra manageable.

let mut supervisor = employee::Supervisor::<DitherJob>::new(THREAD_COUNT);
let worker_count = supervisor.worker_count;

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

supervisor.set_workers(&|id|  dither.dither_section(id))
);

supervisor.acquire(&mut output);

Discover how Dither is wrapped Arc::new. To soundly share possession of knowledge throughout threads, an Atomic Reference Counter (Arc) must be used. It retains depend of the house owners and drops the worth when no threads are utilizing it.

Conclusion

Total, I’m happy with how this system turned out. With me nonetheless studying Rust, this challenge has helped me to change into extra assured in utilizing the language and allowed me to discover new concepts in picture processing.

I hope you loved studying my article, and once more, be at liberty to take a look at the challenge beneath:

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

Thanks,
Nabeel Ahmed