Color palette generator

ColorPalette.cpp

#include "ColorPalette.h"

#include "cinder/CinderAssert.h"
#include "cinder/Rand.h"

#include <algorithm>
#include <numeric>

using namespace ci;
using namespace col;

/////////////////////////////////////////////////////////////////////////////////
///////////////////////////// MEDIAN CUT VEC CUBE ///////////////////////////////
/////////////////////////////////////////////////////////////////////////////////

RgbCube::RgbCube( const std::vector<ivec3>& colors )
: mColorVecs( colors )
{
	// Here we set the bounds of the cube
	mBounds[0] = { 255, 0 };
	mBounds[1] = { 255, 0 };
	mBounds[2] = { 255, 0 };
	for( auto color : mColorVecs ) {
		// Iterate over all 3 color channels
		for( int i = 0; i < 3; ++i ) {
			if( color[i] < mBounds[i].first )
				mBounds[i].first = color[i];
			if( color[i] > mBounds[i].second )
				mBounds[i].second = color[i];
		}
	}
}

int RgbCube::getSize( ColorChannel channel ) const
{
	size_t idx = static_cast<size_t>( channel );
	int s = mBounds[idx].second - mBounds[idx].first;
	CI_ASSERT( s >= 0 );
	return s;
}

std::pair<uint8_t, uint8_t> RgbCube::getBounds( ColorChannel channel ) const
{
	return mBounds[static_cast<size_t>( channel )];
}

ColorChannel RgbCube::getLongestAxis() const
{
	int sr = getSize( RED );
	int sg = getSize( GREEN );
	int sb = getSize( BLUE );
	
	int m = math<int>::max( math<int>::max( sr, sb ), sb );
	if ( m == sr ) return RED;
	if( m == sg ) return GREEN;
	return BLUE;
}

ci::Color8u RgbCube::calcMeanColor() const
{
	vec3 sum( 0 );
	for( auto& c : mColorVecs ) {
		sum += c;
	}
	sum /= (float) mColorVecs.size();
	
	return Color8u( sum.x, sum.y, sum.z );
}

std::pair<RgbCube, RgbCube> RgbCube::splitAtMedian()
{
	ColorChannel longest = getLongestAxis();
	// Sort the colors according the the specified color channel
	switch( longest ) {
		case RED:
			std::sort( mColorVecs.begin(), mColorVecs.end(), []( const ivec3& c0, const ivec3& c1 ) -> bool { return c0.x < c1.x; } );
			break;
		case GREEN:
			std::sort( mColorVecs.begin(), mColorVecs.end(), []( const ivec3& c0, const ivec3& c1 ) -> bool { return c0.y < c1.y; } );
			break;
		case BLUE:
			std::sort( mColorVecs.begin(), mColorVecs.end(), []( const ivec3& c0, const ivec3& c1 ) -> bool { return c0.z < c1.z; } );
			break;
	}
	
	// Separate at median & subdivide into two new cubes
	CI_ASSERT( mColorVecs.size() >= 2 );
	
	size_t medianIdx = mColorVecs.size() / 2;
	auto cube0 = RgbCube{ std::vector<ivec3>{ mColorVecs.begin(), mColorVecs.begin() + medianIdx } };
	auto cube1 = RgbCube{ std::vector<ivec3>{ mColorVecs.begin() + medianIdx, mColorVecs.end() } };
	return std::pair< RgbCube, RgbCube>{ cube0, cube1 };
}

/////////////////////////////////////////////////////////////////////////////////
/////////////////////////// COLOR PALETTE GENERATOR /////////////////////////////
/////////////////////////////////////////////////////////////////////////////////

PaletteGenerator::PaletteGenerator( ci::Surface8u surface )
{
	Surface8u::ConstIter iter = surface.getIter();
	while( iter.line() ) {
		while( iter.pixel() ) {
			mColorsVecs.emplace_back( iter.r(), iter.g(), iter.b() );
		}
	}
}

Color8u PaletteGenerator::randomSample() const
{
	size_t idx = (size_t) math<float>::floor( Rand::randFloat() * mColorsVecs.size() );
	auto cv = mColorsVecs.at( idx );
	return Color8u( cv.x, cv.y, cv.z );
}

float getLuminance( const glm::ivec3& c )
{
	return ( c.r + c.r + c.g + c.b + c.b + c.b ) / ( 255.0f * 6.0f );
}

float getLuminance( const Color8u& c )
{
	return float( c.r + c.r + c.g + c.b + c.b + c.b ) / ( 255.0f * 6.0f );
}

std::vector<ci::Color8u> PaletteGenerator::randomPalette( size_t num, float luminanceThreshold ) const
{
	std::vector<ci::Color8u> samples;
	while ( samples.size() < num ) {
		Color8u sample = randomSample();
		if( getLuminance( sample ) >= luminanceThreshold ) {
			samples.emplace_back( sample );
		}
	}
	return samples;
}

std::vector<Color8u> PaletteGenerator::medianCutPalette( size_t num, bool randomize, float luminanceThreshold ) const
{
	std::list<RgbCube> cubes;
	if( luminanceThreshold > 0.0f && luminanceThreshold < 1.0f ) {
		std::vector<ivec3> trimmedColorVecs = mColorsVecs;
		
		auto newEnd = std::remove_if( trimmedColorVecs.begin(), trimmedColorVecs.end(),
									  [luminanceThreshold]( const ivec3& c ) {
										  float luminance = getLuminance( c ) - 0.5f;
										  return( ( 0.5f - math<float>::abs( luminance ) ) < luminanceThreshold );
									  } );
		
		trimmedColorVecs.erase( newEnd, trimmedColorVecs.end() );
		cubes.emplace_back( RgbCube{ trimmedColorVecs } );
	} else {
		cubes.emplace_back( RgbCube{ mColorsVecs } );
	}

	// split the cubes until we get required amount of colors
	while( cubes.size() < num ) {
		auto& parent = cubes.front();
		const auto& pair = parent.splitAtMedian();
		
		// Randomize order non-power-of-two number of colors
		if( randomize && Rand::randBool() ) {
			cubes.emplace_back( pair.second );
			cubes.emplace_back( pair.first );
		} else {
			cubes.emplace_back( pair.first );
			cubes.emplace_back( pair.second );
		}
		cubes.pop_front();
	}
	
	// get the final palette
	std::vector<Color8u> palette;
	for( auto& cube : cubes ) {
		palette.emplace_back( cube.calcMeanColor() );
	}
	return palette;
}

std::vector<ci::Color8u> PaletteGenerator::kmeansPalette( size_t num ) const
{
	
	RgbCube cube( mColorsVecs );
	auto redBounds = cube.getBounds( RED );
	auto greenBounds = cube.getBounds( GREEN);
	auto blueBounds = cube.getBounds( BLUE );
	
	std::vector<ivec3> centroids;
	
	for( size_t i=0; i<num; ++i ) {
		int r = Rand::randInt( redBounds.first, redBounds.second + 1 );
		int g = Rand::randInt( greenBounds.first, greenBounds.second + 1 );
		int b = Rand::randInt( blueBounds.first, blueBounds.second + 1 );
		centroids.emplace_back( r, g, b );
	}

	CI_ASSERT_MSG( false, "Not fully implemented yet..." );

	return {};
}

std::vector<ci::Color8u> randomPalette( ci::Surface8u surface, size_t num )
{
	PaletteGenerator generator( surface );
	return generator.randomPalette( num );
}

ColorPalette.h

#pragma once

#include "cinder/Color.h"
#include "cinder/ImageIo.h"
#include "cinder/Surface.h"

#include <vector>
#include <array>
#include <future>

namespace col {

	enum ColorChannel {
		RED = 0,
		GREEN = 1,
		BLUE = 2
	};
	
	// Testing out for performance!
	class RgbCube {
	public:
		RgbCube( const std::vector<glm::ivec3>& colors );
		
		//! Get the longest cube channel/axis
		ColorChannel getLongestAxis() const;
		
		//! Get the channel cube dimension
		int getSize( ColorChannel channel ) const;
		
		//! Get the channel cube bounds
		std::pair<uint8_t, uint8_t> getBounds( ColorChannel channel ) const;
		
		//! Calculate the mean color (centroid) of the cube
		ci::Color8u calcMeanColor() const;
		
		//! WARNING! This method is non-const: it sorts the color std::vector
		std::pair<RgbCube, RgbCube> splitAtMedian();
	private:
		//! pair of min-max for each color channel (R-G-B in order)
		std::array< std::pair<uint8_t, uint8_t>, 3 > mBounds;
		
		//! Collection of all colors referenced by cube
		std::vector<glm::ivec3> mColorVecs;
	};

	class PaletteGenerator  {
	public:
		PaletteGenerator( ci::Surface8u surface );

		ci::Color8u					randomSample() const;
		std::vector<ci::Color8u>	randomPalette( size_t num, float luminanceThreshold = 0.0f ) const;
		std::vector<ci::Color8u>	medianCutPalette( size_t num, bool randomize = false, float luminanceThreshold = -1 ) const;
		std::vector<ci::Color8u>	kmeansPalette( size_t num ) const;
	private:
		std::vector<glm::ivec3> mColorsVecs;
	};
	
	typedef std::future<std::vector<ci::Color8u>> AsyncPalette;
}

ColorQuantizationApp.cpp

#include "cinder/app/App.h"
#include "cinder/app/RendererGl.h"
#include "cinder/gl/gl.h"

#include "ColorPalette.h"

template<typename R>
bool is_ready(std::future<R> const& f)
{ return f.valid() && f.wait_for(std::chrono::seconds(0)) == std::future_status::ready; }

using namespace ci;
using namespace ci::app;
using namespace std;

class ColorQuantizationApp : public App {
  public:
	void setup() override;
	void update() override;
	void draw() override;
	void fileDrop( FileDropEvent event ) override;
	
	std::vector<Color8u> mRandomSampleColors;
	std::vector<Color8u> mMedianCutColors;
	
	col::AsyncPalette mRandomAsyncPalette, mMedianAsyncPalette;
};

void ColorQuantizationApp::setup()
{
	gl::enableAlphaBlending();
}

void ColorQuantizationApp::update()
{
	if( is_ready( mRandomAsyncPalette ) ) {
		mRandomSampleColors = mRandomAsyncPalette.get();
	}
	
	if( is_ready( mMedianAsyncPalette ) ) {
		mMedianCutColors = mMedianAsyncPalette.get();
	}
}

void drawColorCircle( std::vector<Color8u> colors ) {
	if( colors.empty() )
		return;
	
	float radius = 100.0f;
	int idx = 0;
	for( auto& color : colors ) {
		gl::color( color );
		float angle = - idx / float( colors.size() ) * 2.0f * M_PI;
		vec2 pos( radius * cos( angle ), radius * sin( angle ) );
		gl::drawSolidCircle( pos, 60.0f );
		++idx;
	}
}

void ColorQuantizationApp::draw()
{
	gl::clear( Color::gray( 0.5f * ( sin(app::getElapsedSeconds()) + 1.0f ) ) );
	
	Font font("Arial", 16 );
	ColorA col( ColorA::white() );
	
	gl::ScopedMatrices push;
	gl::translate( getWindowWidth() / 4, getWindowHeight()/2 );
	drawColorCircle( mRandomSampleColors );
	gl::drawStringCentered( "Random", vec2( 0, - getWindowHeight()/2.15f ), col, font );
	
	gl::translate( getWindowWidth() / 2, 0 );
	drawColorCircle( mMedianCutColors );
	gl::drawStringCentered( "Median cut", vec2( 0, - getWindowHeight()/2.15f ), col, font );
}

std::vector<Color8u> getPalette( const fs::path& imageFile, size_t nb, bool random )
{
	try {
		col::PaletteGenerator generator( Surface8u( loadImage( loadFile( imageFile ) ) ) );
		return ( random ) ? generator.randomPalette( nb, 0.35f ) : generator.medianCutPalette( nb );
	}
	catch( ... ) {
		app::console() << "Palette generation failed." << std::endl;
	}
	return {};
}

void ColorQuantizationApp::fileDrop( FileDropEvent event )
{
	auto file = event.getFile(0);
	size_t nb = 64;
	
	mMedianAsyncPalette = std::async(std::launch::async, getPalette, file, 64, false );
	mRandomAsyncPalette = std::async(std::launch::async, getPalette	, file, 64, true );
}

CINDER_APP( ColorQuantizationApp, RendererGl, []( App::Settings * settings )
{
	int height = 450;
	settings->setWindowSize( 2 * height, height );
	settings->setHighDensityDisplayEnabled();
} )