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

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).

Solution

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.