Ordered Dithering to 4 colors with JavaScript

Question

fellow devs!

I am trying to dither a 8-bit grayscale image to a 2-bit / 4 color image with an ordered dithering based on a Bayer 8×8 matrix. My result is somewhat there, but not quite. I kept banging my head at the problem but can't figure out where I went wrong so any help would be greatly appreciated.

Here's my code:

    // image_array_2d is a 2d array of grayscale values from 0-255
    // matrix is a 2d array with values normalized to be between 0.0 and 1.0
    // LUT is an array of 8-bit values, in this case [0, 85, 170, 255]

    const MAX = 255
    const image_height = image_array_2d.length
    const image_width  = image_array_2d[0].length
    for (let y = 0; y < image_height; y++)
    {
        for (let x = 0; x < image_width; x++)
        {
            const threshold = (matrix[y % 8][x % 8]) * MAX
            let pixel_value = image_array_2d[y][x];
            //pixel_value = gamma_correct(pixel_value)

            // find closest value to pixel in LUT
            let value_current, value_prev
            let closest = lut[0]
            for (let i = 0; i < lut.length; i++)
            {
                const closestDifference = Math.abs(closest - pixel_value);
                const currentDifference = Math.abs(lut[i]  - pixel_value);

                if (currentDifference < closestDifference)
                {
                    value_prev     = lut[i-1]
                    value_current  = lut[i]
                    closest        = value_current
                }
            }

            let new_value = 0
            new_value = pixel_value > threshold ? value_current : value_prev
            new_value = pixel_value >= MAX      ?           MAX : new_value
            
            image_array_2d[y][x] = new_value
        }
    }

Just for safety, that's my Bayer matrix before its values get normalized to 0.0 - 1.0

        [ 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]

(The following images have been scaled up by 400% for convenience)

This is the image I test my algorithm with:

And this is the intended target:

However, this is the result of the above code with the LUT array being [0, 85, 170, 255]

EDIT: Here's the code pen link:

► https://codepen.io/PixelProphet/pen/JjxLejZ
The function in question is ordered_dither()

Answer 1

I noticed a few issues with your code. The general theme is: you think of color values instead of color ranges.

1. You are searching for the closest value in lut, instead of searching for an interval your pixel falls into. Remember, you need two colors to dither, not just one.
2. You normalize your bayer matrix, and that is collapsing the last interval between 63-64.
3. The threshold calculation is weird, you are scaling the threshold for the whole luminance range instead of the current lut interval.

I fixed these issues in your code and it is now working.

const ctx_image  = image_canvas.getContext('2d');
const ctx_dither = dither_canvas.getContext('2d')
const img_w      = 256
const img_h      = 16

// generates a gradient for testing
function gradient()
{
  let data = new Uint8ClampedArray(img_w * img_h * 4)
  x = 0
  for (let i = 0; i < data.length; i =  i + 4)
  {
    data[i+0] = x
    data[i+1] = x
    data[i+2] = x
    data[i+3] = 255
    
    if (++x >= img_w)
      x = 0
  }
  
  return new ImageData(data, img_w)
}
ctx_image.putImageData(gradient(),0,0)

// runs the dithering test
function test()
{
  const test_data   = ctx_image.getImageData(0,0,img_w,img_h);
  const dither_data = dither_grayscale_canvas_ordered(test_data,4); // 4 = number of shades
  ctx_dither.putImageData(dither_data,0,0)
}


// ------ THIS is the function I am having problems with -------
function ordered_dither(image_array_2d, matrix, lut)
{
    // image_array_2d is a 2d array of grayscale values from 0-255
    // matrix is a 2d array with values normalized to be between 0.0 and 1.0
    // LUT is an arry of 8-bit values, in this case [0, 85, 170, 255]
    const MAX = 255
    const image_height = image_array_2d.length
    const image_width  = image_array_2d[0].length
    for (let y = 0; y < image_height; y++)
    {
        for (let x = 0; x < image_width; x++)
        {
            let pixel_value = image_array_2d[y][x];
            //pixel_value = gamma_correct(pixel_value)

            // find closest value to pixel in LUT
            let value_current = lut[lut.length - 1], value_prev = lut[lut.length - 2];
            for (let i = 1; i < lut.length; i++)
            {
                if (pixel_value < lut[i]) {
                    value_current = lut[i]
                    value_prev = lut[i - 1];
                    break;
                }
            }

            const threshold = value_prev + (value_current - value_prev) * matrix[y % 8][x % 8] / 64;
            let new_value = 0
            new_value = pixel_value > threshold ? value_current : value_prev
            
            image_array_2d[y][x] = new_value
        }
    }

    return image_array_2d
}
// -------------------------------------------------------------




function dither_grayscale_canvas_ordered(image_data, depth)
{
    const width = image_data.width
    const image_array_2d = canvas_to_grayscale_array2d(image_data)
    const matrix = bayer_8x8();
    const dithered_8bpp = ordered_dither(image_array_2d, matrix, create_lut(depth))
    return grayscale_array2d_to_canvas_data(dithered_8bpp, width)
}

function canvas_to_grayscale_array2d(image_data)
{
    const data  = image_data.data
    const width = image_data.width;

    let x = 0
    let out_array = []
    let line = []
    for (let i = 0; i < data.length; i += 4)
    {
        let r = data[i]
        let g = data[i+1]
        let b = data[i+2]
        let a = data[i+3]
        line.push(rgb_to_lightness(r,g,b))

        if (++x >= width)
        {
            x = 0
            out_array.push(line) 
            line = [];
        }
    }
    return out_array
}

function bayer_8x8()
{
    return [
        [ 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],
    ];
}



function create_lut(number_of_colors, max = 255, min = 0)
{
    const range = max - min
    const step = range / (number_of_colors - 1);
    let lut = []
    for (let i = 0; i < number_of_colors; i++)
    {
        lut[i] = Math.floor(step * i)
    }

    return lut
}

function rgb_to_lightness(r,g,b)
{
   // hey, that works pretty well!
    return Math.round( (r + r + g + g + g + b) / 6 )
}

function grayscale_array2d_to_canvas_data(image_array_2d, width)
{
    // assumes the values are 8-bit in a 2d-array
    const flat = image_array_2d.flat(Infinity)

    let index = 0
    let data = new Uint8ClampedArray(flat.length * 4)
    for (let i = 0; i < flat.length; i++)
    {
        const value = flat[i]
        data[index++] = value; // R
        data[index++] = value; // G
        data[index++] = value; // B
        data[index++] = 255;   // A
    }

    const image_data = new ImageData(data, width)
    return image_data;
}

<canvas id="image_canvas" width="256" height="16" style="image-rendering: pixelated; width: 512px; height: 32px;"></canvas><br/>
<canvas id="dither_canvas" width="256" height="16" style="image-rendering: pixelated; width: 512px; height: 32px"></canvas><br/>
<button onClick="test()">Dither!</button>

Answer 2

It appears that your approach is on the right track, but there are potential issues in your code. Here are some suggestions to enhance your Bayer matrix-based dithering algorithm:

1. Bayer Matrix Normalization: Ensure that your Bayer matrix is correctly normalized between 0 and 1. Currently, you haven't included the normalization process in the provided code. You need to divide each element of the matrix by the maximum value in the matrix (63 in this case).

// Bayer matrix normalization
const bayerMatrix = [
  // ... (your matrix here)
];

const MAX = 255;

// Normalization
const maxInMatrix = Math.max(...bayerMatrix.flat());
const normalizedMatrix = bayerMatrix.map(row => row.map(value => value / maxInMatrix));

2. Fixing the LUT Search Loop: The loop for searching in the Look-Up Table (LUT) seems to be offset. Ensure that you are not accessing negative indices in the LUT. Modify your loop to avoid this issue.

    let closest = lut[0];
    for (let i = 0; i < lut.length; i++) {
      const currentDifference = Math.abs(lut[i] - pixel_value);
    
      if (currentDifference < Math.abs(closest - pixel_value)) {
        closest = lut[i];
      }
    }

3. Applying Dithering: Make sure that you are applying dithering correctly by comparing the pixel value with the Bayer matrix threshold.

    const threshold = normalizedMatrix[y % 8][x % 8] * MAX;
    let new_value = pixel_value > threshold ? value_current : value_prev;
    new_value = pixel_value >= MAX ? MAX : new_value;
    image_array_2d[y][x] = new_value;

With these adjustments, your dithering algorithm should work more accurately. Remember to test it with different images and fine-tune the parameters as needed.