Reduce the an image to fixed numbers of given colors in JAVA

Question

I want to edit images in a special way:

I have given a List of 40 Colors. Now i have an image with every possible color. I want to reduce the image to only 12 colors (of the 40 possible colors) and get the best result. Is there a good library to archive that (JAVA).

You can filter every pixel and calculate which one of the predefined colors it is closest to. I don't know if there is a library for that where you can define your own colors. Maybe you can find inspiration [here](https://github.com/gitgraghu/image-processing/tree/master/src/Effects) or [here](https://stackoverflow.com/questions/27071351/change-the-color-of-each-pixel-in-an-image-java) — HomeIsWhereThePcIs, Mar 17 '20 at 11:15
The Problem is not finding the closest color. Its more i have given 40 Colors - but i want use only 12 of them. These 12 should be optimal — MullisS, Mar 17 '20 at 11:33
Go through the pixels and determine how many colors are in the image. With each of your 40 colors, go through the pixels and determine how much you would have to change the red, green, and blue for each pixel. Sum the changes for each of the 40 colors. Pick the 12 with the lowest sum. Look up color correcting to get the formula to use in the summation process. — Gilbert Le Blanc, Mar 19 '20 at 13:31
@MullisS Do you want the code to actually modify the image, or just return/print the 12 solution colors? I already posted an answer, but I'd be happy to modify it if you're also looking to modify the actual image with the solution colors. — Jacob G., Mar 19 '20 at 23:00
Could you explain why you need to do such a thing? What kind of image is it? How many colors does it have? — Olivier, Mar 20 '20 at 08:30
I want to do some pixel arts. Every image i possible. I found here a working example: : pixel-beads.net — MullisS, Mar 20 '20 at 08:38

Jacob G. · Accepted Answer · 2020-03-20T18:47:55.523

In this answer, I'm making the following assumptions:

Your list contains 40 distinct colors.
Each color contains 24 bits of information (8 bits for red, 8 bits for green, and 8 bits for blue).
The 12-color solution should be the optimal combination in which humans perceive color.

Because your goal is to determine which 12 colors (of the 40 provided) are closest to all colors in the image, you can use the following algorithm:

Iterate over all 40 of your input colors.
For each color, iterate over all pixels in the input image.
For the current pixel, calculate the difference between its color and our current color.
- This is probably the most difficult portion of the algorithm, as we need a function that returns the difference between two colors.
- I believe the most effective way to achieve this is to first convert the RGB color to the XYZ color space, and then convert the XYZ color to the CIELAB color space.
- We can then use this formula to calculate the difference between two CIELAB colors.

Map the color to the sum of differences for that respective color.
Sort the Map<Integer, Double> by value (ascending); the solution is the first 12 keys.

Here's the Java code to achieve this:

import javax.imageio.ImageIO;
import java.awt.Color;
import java.awt.image.BufferedImage;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.nio.file.Paths;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class ColorDifference {

    public static void main(String[] args) {
        ConcurrentMap<Color, Double> colorDifferenceMap = new ConcurrentHashMap<>();
        ExecutorService executorService = Executors.newFixedThreadPool(
            Runtime.getRuntime().availableProcessors());

        BufferedImage inputImage;

        try {
            // Read in the input image
            inputImage = ImageIO.read(Paths.get("input.png").toFile());
        } catch (IOException e) {
            throw new UncheckedIOException("Unable to read input image!", e);
        }

        generateInfiniteColors().distinct().limit(40).forEach(color -> {
            executorService.execute(() -> {
                CIELab cieLabColor = CIELab.from(color);

                double sum = 0d;

                for (int y = 0; y < inputImage.getHeight(); y++) {
                    for (int x = 0; x < inputImage.getWidth(); x++) {
                        Color pixelColor = new Color(inputImage.getRGB(x, y));
                        CIELab pixelCIELabColor = CIELab.from(pixelColor);
                        sum += cieLabColor.difference(pixelCIELabColor);
                    }
                }

                colorDifferenceMap.put(color, sum);
            });
        });

        executorService.shutdown();

        try {
            executorService.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // The 12 solution colors are held in this list
        List<Color> colorSolutions = colorDifferenceMap.entrySet()
            .stream()
            .sorted(Map.Entry.comparingByValue())
            .limit(12)
            .map(Map.Entry::getKey)
            .collect(Collectors.toList());

        colorSolutions.forEach(System.out::println);

        for (int y = 0; y < inputImage.getHeight(); y++) {
            for (int x = 0; x < inputImage.getWidth(); x++) {
                CIELab cieLabColor = CIELab.from(new Color(inputImage.getRGB(x, y)));

                int finalX = x;
                int finalY = y;

                colorSolutions.stream()
                    .min(Comparator.comparingDouble(color -> 
                        cieLabColor.difference(CIELab.from(color))))
                    .ifPresent(closestColor -> 
                        inputImage.setRGB(finalX, finalY, closestColor.getRGB()));
            }
        }

        try {
            ImageIO.write(inputImage, "png", new File("output.png"));
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    // Inspiration taken from https://stackoverflow.com/a/20032024/7294647
    private static Stream<Color> generateInfiniteColors() {
        return Stream.generate(() -> 
            new Color(ThreadLocalRandom.current().nextInt(0x1000000)));
    }

    static class CIELab {

        private final double L, a, b;

        public CIELab(double L, double a, double b) {
            this.L = L;
            this.a = a;
            this.b = b;
        }

        public double difference(CIELab cieLab) {
            return Math.sqrt(Math.pow(cieLab.L - L, 2) + Math.pow(cieLab.a - a, 2) +
                Math.pow(cieLab.b - b, 2));
        }

        public static CIELab from(Color color) {
            int sR = color.getRed();
            int sG = color.getGreen();
            int sB = color.getBlue();

            // Convert Standard-RGB to XYZ (http://www.easyrgb.com/en/math.php)
            double var_R = ( sR / 255d );
            double var_G = ( sG / 255d );
            double var_B = ( sB / 255d );

            if ( var_R > 0.04045 ) var_R = Math.pow( ( var_R + 0.055 ) / 1.055, 2.4 );
            else                   var_R = var_R / 12.92;
            if ( var_G > 0.04045 ) var_G = Math.pow( ( var_G + 0.055 ) / 1.055, 2.4 );
            else                   var_G = var_G / 12.92;
            if ( var_B > 0.04045 ) var_B = Math.pow( ( var_B + 0.055 ) / 1.055, 2.4 );
            else                   var_B = var_B / 12.92;

            var_R = var_R * 100;
            var_G = var_G * 100;
            var_B = var_B * 100;

            double X = var_R * 0.4124 + var_G * 0.3576 + var_B * 0.1805;
            double Y = var_R * 0.2126 + var_G * 0.7152 + var_B * 0.0722;
            double Z = var_R * 0.0193 + var_G * 0.1192 + var_B * 0.9505;

            // Convert XYZ to CIELAB (http://www.easyrgb.com/en/math.php
            double var_X = X / 96.422;
            double var_Y = Y / 100.000;
            double var_Z = Z / 82.521;

            if ( var_X > 0.008856 ) var_X = Math.pow( var_X, 1D / 3D );
            else                    var_X = ( 7.787 * var_X ) + ( 16D / 116 );
            if ( var_Y > 0.008856 ) var_Y = Math.pow( var_Y, 1D / 3D );
            else                    var_Y = ( 7.787 * var_Y ) + ( 16D / 116 );
            if ( var_Z > 0.008856 ) var_Z = Math.pow( var_Z, 1D / 3D );
            else                    var_Z = ( 7.787 * var_Z ) + ( 16D / 116 );

            double L = ( 116 * var_Y ) - 16;
            double a = 500 * ( var_X - var_Y );
            double b = 200 * ( var_Y - var_Z );

            return new CIELab(L, a, b);
        }
    }
}

To test the code, I grabbed the following 473x356 picture from the link that you sent in your comment:

You can see in the code that all 40 colors were randomly generated, and this was the output of the program:

java.awt.Color[r=182,g=176,b=32]
java.awt.Color[r=201,g=201,b=55]
java.awt.Color[r=142,g=149,b=6]
java.awt.Color[r=223,g=158,b=36]
java.awt.Color[r=226,g=143,b=63]
java.awt.Color[r=144,g=83,b=39]
java.awt.Color[r=119,g=153,b=117]
java.awt.Color[r=50,g=136,b=72]
java.awt.Color[r=244,g=118,b=59]
java.awt.Color[r=69,g=79,b=52]
java.awt.Color[r=149,g=78,b=76]
java.awt.Color[r=62,g=190,b=28]

One possible output image is the following:

The above code can run on Java 8+, and it finishes in under a second for the image posted above.

This looks very good but i think the result should contain some green and blue as well, because you wanna have the best result and not the 12 closted colors? How about iterating over all 40 colors and and pixels and find the most used color. Put this color into a result set. Now iterate over all 40 colors again and all pixels and find the most use color, but ignore the pixel if it’s closet color is in the result set. But the next color in the resultset. — MullisS, Mar 20 '20 at 07:18
@MullisS The solution contained no colors that were mostly green or blue because I purposely included `12` colors that were mostly red, and the image itself contained mostly red pixels. If you want to see more green/blue in the solution, then you have two options: evenly distribute the `40` input colors to contain less red, or choose an image that's more green/blue. I'll edit my answer to work with the sunflower image that's contained in the link you posted. — Jacob G., Mar 20 '20 at 17:20
Thank you. Ill try to check my results with your code on this weekand and give feedback — MullisS, Mar 20 '20 at 22:02

Olivier · Answer 2 · 2020-03-20T10:21:00.643

0

The solution is not as simple as the one given (see Jacob's answer). To understand why, let's say we have 10 pixels in the image: 9 red and 1 green. Suppose we have 39 reddish and 1 green in the palette. The optimal answer is 11 reddish and 1 green (perfect match). The proposed algorithm will select 12 reddish.

To find the real best result, you need to iterate over all possible 12-color palettes to find one that minimizes the total error (sum of color distances, or sum of squared distances, because it's common practice to minimize the sum of squared errors).

The number of 12-color palettes from a 40-color palette is:

C(40,12) = 40! / (12! * 28!) = 5,586,853,480

That's a lot so it will take some processing time. Of course it will depend on the image size.

edited Mar 20 '20 at 10:21

answered Mar 20 '20 at 09:20

Olivier

13,283
1
8
24

Generating all 5.5 billion combinations was actually the first answer I had come up with, but then I did the math and realized that the solution is the same regardless of how it's calculated (so combinations don't need to be generated). I'll admit that my answer does fall apart for input images that are less than or equal to 12 pixels in size, but the input images will **never** be that small (OP stated they want to use the code to generate pixel art), so I'd still argue that my solution is optimal. – Jacob G. Mar 20 '20 at 14:39
@JacobG. I took 10 pixels in my example but the issue remains the same whatever the size. If you take a one-million pixel image with a majority of red and a minority of green, your solution still omits green. – Olivier Mar 20 '20 at 14:52

Reduce the an image to fixed numbers of given colors in JAVA

2 Answers2