javascriptimage-processingdithering

Ordered Dithering to 4 colors with JavaScript

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: Source at 400%

And this is the intended target: Target at 400%

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

EDIT: Here's the code pen link:

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

Solution

  • 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>