Image color restriction

This article explores an image processing technique called dithering. Dithering can be applied when performing color pallete restriction of an image in order to improve the restricted image quality.

Here we will implement one of the most common image dithering algorithms in Python and compare its result with an original image and with the color restricted image without dithering.

Dithering

Dithering is the process of intentionally applying a form of noise used to randomize quantization error, in order to prevent the appearance of large-scale patterns such as color banding in images.

A common use of dither is converting a grayscale image to black and white, such that the density of black dots in the new image approximates the average gray level in the original. Dithering is also commonly applied when converting an image or video to the GIF format. GIF only supports 256 colors, thus a color pallete reduction is required, and dithering can improve the final image quality.

Reducing the color depth of an image can have significant visual side effects. If the original image is a photograph, it is likely to have thousands or even millions of distinct colors. The process of constraining the available colors to a specific color palette effectively throws away a certain amount of color information.

If the original pixel colors are simply translated into the closest available color from a constrained palette, no dithering occurs. However, this approach will result in flat areas (contours) and a loss of detail and may produce patches of color that are significantly different from the original. Shaded or gradient areas may produce color banding which may be distracting. The application of dithering can help to minimize such visual artifacts and usually results in a better representation of the original image. Dithering helps to reduce color banding and flatness.

There are several algorithms designed to perform dithering. One of the earliest, and still one of the most popular, is the Floyd–Steinberg dithering algorithm.

Implementing Floyd-Steinberg dithering

Floyd-Steinberg dithering is a dithering algorithm proposed in 1976 and still commonly used in image processing software. The algorithm uses error diffusion, effectively pushing (adding) the residual quantization error of a pixel onto its neighboring pixels, to be dealt with later.

To manipulate images in Python we will use the Python Imaging Library or Pillow. Once installed we import the necessary functions with:

from PIL import Image, ImageDraw

Let's start by defining some parameters. We will use Python dataclasses to create a Color object that we will use to define colors in terms of RGB triplets. We will then use this to define color palletes as a list of Color objects. Bellow we define a black and white pallete (2 colors) and another pallete, this one covering the full RGB domain, with 24 colors. Here is the color pallete we will use:

Pallete1

from dataclasses import dataclass

@dataclass
class Color:
    r: int
    g: int
    b: int

PALLETE = {
    'B&W': [
        Color(0, 0, 0),
        Color(255, 255, 255)
    ],

    'Pallete1': [
        Color(190, 0, 57),
        Color(255, 69, 0),
        Color(255, 168, 0),
        Color(255, 214, 53),
        Color(0, 163, 104),
        Color(0, 204, 120),
        Color(126, 237, 86),
        Color(0, 117, 111),
        Color(0, 158, 170),
        Color(36, 80, 164),
        Color(54, 144, 234),
        Color(81, 233, 244),
        Color(73, 58, 193),
        Color(106, 92, 255),
        Color(129, 30, 159),
        Color(180, 74, 192),
        Color(255, 56, 129),
        Color(255, 153, 170),
        Color(109, 72, 47),
        Color(212, 215, 217),
        Color(156, 105, 38),
        Color(0, 0, 0),
        Color(137, 141, 144),
        Color(255, 255, 255),
    ]
}

To apply the color restriction we will loop over each pixel in the original image, extract its color, and find the nearest color available in the selected color pallete.

If we want to perform a simple color restriction, with no dithering, our job is done. We simply need to draw this new color onto the image. To apply the Floyd-Steinberg dithering we start by calculating the quantization error, meaning the distance between the original color and the new color in the RGB color space. We will distribute this error to the nearest, not yet analyzed pixels according to the algorithm.

To perform perform this changes we will have to create function to perform some color operation, namely the multiplication of colors and the addition of colors.

Finally, we save the resulting image.

def render(image, img_path, pallete_name, dithering=True):
    for y in range(image.height):
        for x in range(image.width):
            pixel = image.getpixel((x, y))
            color = pixel_to_color(pixel)
            new_color = get_nearest_color(color, pallete=PALLETE[pallete_name])

            draw = ImageDraw.Draw(image)
            draw.point((x, y), color_to_pixel(new_color))

            if dithering:
                # Calculate quantization error
                quant_error = Color(
                    color.r - new_color.r,
                    color.g - new_color.g,
                    color.b - new_color.b
                )

                # Apply Floyd-Steinberg dithering
                if (x + 1 < image.width and y + 1 < image.height):

                    temp_pixel = image.getpixel((x + 1, y))
                    temp_color = pixel_to_color(temp_pixel)
                    draw.point(
                        (x + 1, y), 
                        color_to_pixel( add_colors(temp_color, multiply_color(quant_error, 7/16)) )
                    )

                    temp_pixel = image.getpixel((x - 1, y + 1))
                    temp_color = pixel_to_color(temp_pixel)
                    draw.point(
                        (x - 1, y + 1), 
                        color_to_pixel( add_colors(temp_color, multiply_color(quant_error, 3/16)) )
                    )

                    temp_pixel = image.getpixel((x, y + 1))
                    temp_color = pixel_to_color(temp_pixel)
                    draw.point(
                        (x, y + 1), 
                        color_to_pixel( add_colors(temp_color, multiply_color(quant_error, 5/16)) )
                    )

                    temp_pixel = image.getpixel((x + 1, y + 1))
                    temp_color = pixel_to_color(temp_pixel)
                    draw.point(
                        (x + 1, y + 1), 
                        color_to_pixel( add_colors(temp_color, multiply_color(quant_error, 1/16)) )
                    )

    image.save(output-img.png)

The get_nearest_color() function above finds the the nearest color to the original color present in the selected color pallete. To do this we run through each color in the pallete and calculate its distance to the original color.

I initiate the distance with the value of 500 since the maximum distance between two colors in the RGB space is 441.6 (between black and white). Whenever we find a smaller distance, we update this value. The smallest value corresponds to the nearest color.

def get_nearest_color(old_color, pallete):
    distance = 500
    nearest_color = Color(0, 0, 0)

    for color in pallete:
        new_distance = calc_distance(old_color, color)

        if new_distance < distance:
            distance = new_distance
            nearest_color = color

    return nearest_color

The distance between two colors (or color difference) is a metric of interest in color science. The euclidean distance can be calculated as a function of the R, G, and B values such that:

$$\text{distance}=\sqrt{(R_2-R_1)^2 + (G_2-G_1)^2 + (B_2-B_1)^2}$$

Implementing this in our code:

def calc_distance(color1, color2):
    return ( (color1.r - color2.r)**2 + (color1.g - color2.g)**2 + (color1.b - color2.b)**2 )**0.5

We will also create some utility functions to facilitate conversion between a pixel, as provided by Pillow, and our Color object.

def pixel_to_color(pixel):
    return Color(pixel[0], pixel[1], pixel[2])


def color_to_pixel(color):
    return (color.r, color.g, color.b)

As stated above, to apply the Floyd-Steinberg algorithm we need to perform some operation with colors. We create a function to add two colors, by adding each RGB values. We also need to multiply a Color by a fraction in order to distribute the quantization error.

def add_colors(color1, color2):
    return Color(
        color1.r + color2.r, 
        color1.g + color2.g, 
        color1.b + color2.b
    )


def multiply_color(color, value):
    return Color(
        round(color.r * value), 
        round(color.g * value),
        round(color.b * value)
    )

To run the program we open an image file with Pillow and pass the resulting image to our render function.

with Image.open('path/to/image.png') as image:
    render(image, 'Pallete1', dithering=dithering)

Examples

So, what's the result of our color restriction script? Below there are several examples. Check the Github repository for more.

Color pallete restriction with dithering:

Original image With dithering
original dithering

Color pallete restriction without dithering:

Original image Without dithering
original no dithering

Color restriction to black and white:

Without dithering With dithering
b&w no dithering b&w dithering

Other samples:

Original image With dithering
original dithering
original dithering
original dithering

Code

The complete code used in this article can be found on Github as well as further examples.

References