How to Create an Application to Determine the Palette and Dominant Colors of an Image

A key technique in image editing applications is determining the dominant colors. The identification of these dominant colors is essential for creating an image's palette, which, in turn, accurately reflects the effect of selected tools and the results of editing.

This article will delve into how to determine an image's palette within a restricted color space, identify an image's dominant colors, and differentiate between a palette and dominant colors.

Palette
The image palette is typically a reference to all the colors present in the original image. In essence, it captures the entire range of color shades, based on the numerical scale of color stimulus signal values.

If we agree on modeling a signal with a certain level of accuracy, then the range of these signal values will represent our available color palette.

Each unique representation of an image and the mapping of an image's colors onto this space will be a subset of it. In digital signal processing (an image is also a signal), we often understand a variety of quantities through its discrete representation.

Thus, our image palette can be viewed as a subset of all the colors in the image represented by a discrete map. Each color can be indexed and assigned a specific value in one of the color spaces. For our purposes, we'll use the RGB color model.

A significant challenge in presenting the image palette in this way is the vastness of human visibility. It's unlikely we can manually analyze the entire image palette, and it often doesn't make sense to store an image represented by all the original colors. Instead, we reduce their number to a reasonable limit.

This process, known as color quantization, involves lowering the number of colors from the full subset that can be represented in an image to a smaller one. For instance, 14-bit raw color data might be represented in 8-bit JPEG or 16-bit TIFF converted to 8-bit PNG.

A straightforward solution to determine an image's primary colors is to envision the process of color quantization to a very limited set, such as 8 or even 3 colors. This gives us insight into the primary colors within the image, making them more noticeable and memorable.

Ideally, the colors in the final image should be harmonious, following the principles outlined by Johannes Itten or Mikhail Matyushin.

By identifying the dominant colors of an image, we can create a tool that allows us to visualize the image's "harmony." This can also apply to the harmony of the image after filtering, or "synthetic harmonization."

Below, we will make an attempt to develop such a tool.

Median Cut
A widely used and high-quality algorithm for compressing an image's palette is the Median Cut algorithm. It's incorporated into most major lossy image compression algorithms, such as JPEG, albeit with some modifications.

The fundamental principle of the Median Cut algorithm is to sequentially divide the image's cubic histogram into medians. Each resulting subcube contains approximately an equal number of bins, or pixels of the same color.

Once the division process reaches a predetermined number of subcubes, we calculate the average color of each cube and map it to the corresponding colors of the original image. This process effectively reduces the number of colors in the original image, allowing us to compress the image into a smaller file size.

It might seem at first glance that the initial part of this algorithm could solve our problem of identifying the primary or dominant colors of an image. However, a potential issue arises when the number of colors into which we divide the image is too few, and we're only analyzing a small number of colors.

We might end up identifying colors that don't actually exist in the image because the colors are excessively averaged. We could choose the color with the maximum bin from each cube and label it as dominant, but then it wouldn't constitute a palette anymore.

So, we'll reserve this approach for determining a compressed version of the image's palette, which can also be used as a tool for visually analyzing the image in terms of its "harmonious utility." To identify the dominant colors, we'll employ statistical analysis: searching for local maxima in the same cubic histogram.

Local Maxima
To identify the local maxima, we will implement a specific code. The author, who is also a skilled artist, provides an excellent description of the algorithm. Essentially, we first gather the image statistics into the same three-dimensional RGB histogram used in the Median Cut algorithm.

Each cell of the cubic histogram will contain color bins, and the sum of all values of each color included in the cell. Given the limited histogram dimension to a resolution of 32x32x32 (originally 30x30x30), accumulating the sum simplifies the calculation of the average cell color.

We then search for the local maximum by thoroughly exploring the entire space and comparing it with neighboring cells.

Following this, we iteratively reduce the number of local maxima to the required amount, discarding similar colors with less weight. For all remaining local maxima, we calculate the average colors of all values included in the list.

Since the color density in local maxima is higher, and the difference between pixel values is smaller than in cubes from the Median Cut, the colors will be more akin to those present in the main image and will more accurately represent its dominant colors.

This reveals the primary difference between the two models: acquiring a "compressed palette" versus searching for local maxima or dominant colors. By mapping the primary "compressed palette" image, we will create a new one that maintains the same color balance as the main image, albeit in a vastly truncated form.

On the other hand, dominant colors only describe the composition of the colors primarily present in the image. They cannot be transformed into anything new with a suitable color balance.

Implementation
Using this task as an example, we will demonstrate how straightforward it is to develop a ready-to-use application for image analysis and manipulation using the IMProcessing Framework. We will begin with functionalities that are absent in other engines.

For instance, the framework has the capacity to read Adobe .cube files with pre-existing CLUTs and can extract a three-dimensional cubic histogram from an image in real-time.

Capitalizing on this, we aim to create an application that can:

• Upload files in JFIF (jpeg) format.
• “Normalize” the original image.
• Control the intensity of the “normalizer.”
• Incorporate an arbitrary LUT from an Adobe .cube file into the processing.
• Manage the intensity of CLUT's impact.
• Display a linear histogram of the image.
• Exhibit the “compressed palette” and dominant colors of the image as well as their numerical representation in the form of a triplet (r,g,b)

The end product of our construction will resemble this interactive toy:

Here, it's clear how the image's simple “normalization” positively influences the diversity of the final palette, re-distributing dominant colors into a more varied and harmonious set.

"Normalizer"
We will assemble a filter from two pre-existing ones:

IMPContrastFilter - allows the stretching of the image histogram to specified boundaries

IMPAutoWBFilter - performs automatic white balance correction based on the search for the average color and the correction of spurious tones in the image. This is essentially a slight modification of an idea borrowed from Andrey Zhuravlev’s blog.

import IMProcessing

/// Image filter
public class IMPTestFilter:IMPFilter {

    /// We will use a contrast control filter through histogram stretching
    var contrastFilter:IMPContrastFilter!

    /// Auto white balance filter
    var awbFilter:IMPAutoWBFilter!

    /// Image Linear Histogram Analyzer
    var sourceAnalyzer:IMPHistogramAnalyzer!

    /// Solver of the histogram analyzer for calculating the lightness boundaries of the image
    let rangeSolver = IMPHistogramRangeSolver()

    public required init(context: IMPContext) {
        super.init(context: context)

        //  Initialize filters in context
        contrastFilter = IMPContrastFilter(context: context)
        awbFilter = IMPAutoWBFilter(context: context)

        // Add filters to the stack
        addFilter(contrastFilter)
        addFilter(awbFilter)

        // Initialize the histogram analyzer
        sourceAnalyzer = IMPHistogramAnalyzer(context: self.context)

        // Add a light boundary search solver to the analyzer
        sourceAnalyzer.addSolver(rangeSolver)

        // Add an observing handler to the filter for
        // to pass the current image frame to the analyzer
        addSourceObserver { (source) - Void in
            self.sourceAnalyzer.source = source
        }

        // Add an observing handler for updating analysis calculations to the analyzer
        sourceAnalyzer.addUpdateObserver({ (histogram) - Void in
        // set the lightness boundaries in the contrast filter each time the image changes
            self.contrastFilter.adjustment.minimum = self.rangeSolver.minimum
            self.contrastFilter.adjustment.maximum = self.rangeSolver.maximum
        })

    }
}

Palette Solver
The IMProcessing Framework stands out from many similar platforms due to its unique organization of calculations. It uses a dedicated group of filters that essentially are not processing filters.

The objects of these classes do not modify the image in the homogeneous and spatial domains. Instead, they perform certain calculations and representations of metrics for analysis in special expanders to solve specific problems.

For instance, an object of the IMPHistogramAnalyzer class can simultaneously add multiple solvers that calculate the average color of the image, the light range, zonal division, etc.

We use the solver to extend the analysis of IMPHistogramCubeAnalyzer to calculate the palette and the list of dominant colors. The calculation results are then displayed in an updated NSTableView.

import IMProcessing

///  Types of distribution of image color accents
///
///  - palette:   palette for quantizing image colors.
///               calculated using the median-cut transformation scheme:
///               http://www.leptonica.com/papers/mediancut.pdf
///  - dominants: calculation of dominant colors of an image by searching for local maxima
///               color distribution density functions:
///               https://github.com/pixelogik/ColorCube
///
public enum IMPPaletteType{
    case palette
    case dominants
}

/// Solver of the cubic color histogram analyzer IMPHistogramCubeAnalyzer
public class IMPPaletteSolver: IMPHistogramCubeSolver {

    /// Maximum number of palette colors for analysis
    public var maxColors = Int(8)

    /// List of found colors
    public var colors = [IMPColor]()

    /// Palette type
    public var type = IMPPaletteType.dominants

      /// Solver handler handler
    /// - parameter analyzer: link to the analyzer
    /// - parameter histogram: cubic histogram of the image
    /// - parameter imageSize: image size
    public func analizerDidUpdate(analizer: IMPHistogramCubeAnalyzer, histogram: IMPHistogramCube, imageSize: CGSize) {

        var p = [float3]()
        if type == .palette{
            p = histogram.cube.palette(count: maxColors)
        }
        else if type == .dominants {
            p = histogram.cube.dominantColors(count: maxColors)
        }

        colors.removeAll()

        for c in p {
            colors.append(IMPColor(color: float4(rgb: c, a: 1)))
        }
    }
}

We Assemble All the Components in the View Controller
The controller will need the main application filter, which we'll call IMPTestFilter, a CLUT filter named IMPLutFilter, the ready-to-use IMPHistogramView for displaying a "regular" histogram, the IMPHistogramCubeAnalyzer which is a cubic histogram analyzer to which we will attach our solver, the IMPPaletteSolver.

Lastly, we'll use IMPImageView as the main window for displaying the image, and the common IMPContext is the key class used by all constructors of the framework.

class ViewController: NSViewController {

    //
    // Processing context
    //
    let context = IMPContext()
    //
    // Window for presenting the loaded image
    //
    var imageView:IMPImageView!

    var pannelScrollView = NSScrollView()

    //
    // Window for displaying the image histogram
    //
    var histogramView:IMPHistogramView!

    //
    // NSTableView - views of a list of colors from the palette
    //
    var paletteView:IMPPaletteListView!

    //
    // Main filter
    //
    var filter:IMPTestFilter!

    //
    // CLUT filter from Adobe Cube files
    //
    var lutFilter:IMPLutFilter?

    //
    // Analyzer of a cubic histogram of an image in RGB space
    //
    var histograCube:IMPHistogramCubeAnalyzer!

    //
    // Our solver for finding colors
    //
    var paletteSolver = IMPPaletteSolver()

    var paletteTypeChooser:NSSegmentedControl!

    override func viewDidLoad() {

        super.viewDidLoad()

        configurePannel()

        //
        // Initialize the objects we need
        //

        filter = IMPTestFilter(context: context)

        histograCube = IMPHistogramCubeAnalyzer(context: context)
        histograCube.addSolver(paletteSolver)

        imageView = IMPImageView(context: context, frame: view.bounds)
        imageView.filter = filter
        imageView.backgroundColor = IMPColor(color: IMPPrefs.colors.background)

        //
        // Add another handler to monitor the original image
        // (another one was added in the main filter IMPTestFilter)
        //
        filter.addSourceObserver { (source) -> Void in
            //
            // to minimize calculations, the analyzer will compress the image to 1000px on the wide side
            //
            if let size = source.texture?.size {
                let scale = 1000/max(size.width,size.height)
                self.histograCube.downScaleFactor = scale.float
            }
        }

        // Add an observer to the filter to process the filtering results
        //
        filter.addDestinationObserver { (destination) -> Void in

            // pass the image to the histogram indicator
            self.histogramView.source = destination

            // pass the result to the cubic histogram analyzer
            self.histograCube.source = destination
        }

        //
        // The results of updating the analyzer calculation are displayed in the color list window
        //
        histograCube.addUpdateObserver { (histogram) -> Void in
            self.asyncChanges({ () -> Void in
                self.paletteView.colorList = self.paletteSolver.colors
            })
        }

        view.addSubview(imageView)

....

        IMPDocument.sharedInstance.addDocumentObserver { (file, type) -> Void in
            if type == .Image {
                do{
                    //
                    // Load the file and associate it with the filter source
                    //
                    self.imageView.source = try IMPImageProvider(context: self.imageView.context, file: file)
                    self.asyncChanges({ () -> Void in
                        self.zoomFit()
                    })
                }
                catch let error as NSError {
                    self.asyncChanges({ () -> Void in
                        let alert = NSAlert(error: error)
                        alert.runModal()
                    })
                }
            }
            else if type == .LUT {
                do {

                    //
                    // Initialize the CLUT descriptor
                    //
                    var description = IMPImageProvider.LutDescription()
                    //
                    // Load CLUT
                    //
                    let lutProvider = try IMPImageProvider(context: self.context, cubeFile: file, description: &description)

                    if let lut = self.lutFilter{
                        //
                        // If a CLUT filter has been added, update its LUT table from the file with the received descriptor
                        //
                        lut.update(lutProvider, description:description)
                    }
                    else{
                        //
                        // Create a new LUT filter
                        //
                        self.lutFilter = IMPLutFilter(context: self.context, lut: lutProvider, description: description)
                    }

                    //
                    // Add a LUT filter, if this filter has already been added nothing happens
                    //
                    self.filter.addFilter(self.lutFilter!)
                }
                catch let error as NSError {
                    self.asyncChanges({ () -> Void in
                        let alert = NSAlert(error: error)
                        alert.runModal()
                    })
                }
            }
        }

As you can see, photo processing is becoming simpler and more accessible to average users, making it possible for virtually anyone to master this process.

The entire project can be downloaded, assembled, and tested from the ImageMetalling project repository: ImageMetalling-08. For proper assembly, the mega-library for working with JPEG files (JFIF), libjpeg-turbo, must be locally installed.

Currently, this is the best implementation of support for this format.