PHP class to extract dominant colours from an image using K-Means clustering. This features an extremely rough-and-ready (read: inefficient) implementation of K-Means which I wrote to run on PHP < 5.3. If you can use an up-to-date build of PHP then you can take advantage of some proper implementations that proper maths-type people have written f…

DominantColours.php

<?php

/**
 * Dominant colours by k means derived from code by Charles Leifer at:
 *   http://charlesleifer.com/blog/using-python-and-k-means-to-find-the-dominant-colors-in-images/
 * 
 * MagickWand docs: http://www.magickwand.org/
 *
 * Color transformation algorithms from EasyRGB: http://easyrgb.com/
 *
 */

class DominantColours
{
    /**
     * Get an array of K dominant colours from an image
     *
     * @param $imagePath - an image stored locally
     * @param $params    - an array of params, like:
     *     array(
     *         'resizeX' => // width to resize image to before processing
     *         'resizeY' => // height to resize image to before processing
     *         'k'       => // number of colours you want to extract
     *         'space'   => // colour space to cluster in: 'rgb'|'yuv'|'hsl'
     *     ); 
     */
    private function getDominantColours($imagePath, $params)
    {
        $dominantColours = null;
        if (file_exists($imagePath)) {
            $dominantColours = $this->processImage($imagePath, $params);
        }

        return $dominantColours;
    }

    private function processImage($imagePath, $params)
    {
        $params = array_merge(array(
            'space'   => 'rgb',
            'resizeX' => 100,
            'resizeY' => 100,
            'k'       => 3,
        ), $params);
        $space   = $params['space'];
        $resizeX = $params['resizeX'];
        $resizeY = $params['resizeY'];
        $k       = $params['k'];

        $dominantColours = array();

        $wand = NewMagickWand();
        MagickReadImage($wand, $imagePath);

        // resize image
        MagickResizeImage($wand, $resizeX, $resizeY, MW_QuadraticFilter, 1.0);

        // initialize an array to hold colour info about our points
        $points = array();

        // iterate over all the pixels in the image
        $pixelIterator = NewPixelIterator($wand);
        if (strtolower($space) == 'yuv') {
            while ($row = PixelGetNextIteratorRow($pixelIterator)) {
                foreach ($row as $pixel) {
                    $points[] = $this->rgbToYuv(PixelGetRed($pixel), PixelGetGreen($pixel), PixelGetBlue($pixel));
                }
            }
        } elseif (strtolower($space) == 'hsl') {
            while ($row = PixelGetNextIteratorRow($pixelIterator)) {
                foreach ($row as $pixel) {
                    $points[] = $this->rgbToHsl(PixelGetRed($pixel), PixelGetGreen($pixel), PixelGetBlue($pixel));
                }
            }
        } else {
            // assume we're just doing straight RGB
            while ($row = PixelGetNextIteratorRow($pixelIterator)) {
                foreach ($row as $pixel) {
                    $points[] = array(
                        PixelGetRed($pixel),
                        PixelGetGreen($pixel),
                        PixelGetBlue($pixel),
                    );
                }
            }
        }
        $results = $this->kMeans($points, $k, 0.005);
        $dominantColours = array();
        for ($i = 0; $i < count($results); $i++) {
            if (strtolower($space) == 'yuv') {
                list($y, $u, $v) = $results[$i][0];
                $rgb = $this->yuvToRgb($y, $u, $v);
            } elseif (strtolower($space) == 'hsl') {
                list($h, $s, $l) = $results[$i][0];
                $rgb = $this->hslToRgb($h, $s, $l);
            } else {
                // assume colour space is already RGB
                $rgb = $results[$i][0];
            }
            foreach ($rgb as $j => $v) {
                $rgb[$j] = floor($v * 256);
            }
            $dominantColours[] = $rgb;
        }
        
        return $dominantColours;
    }

    private function kMeans($points, $k, $min_diff)
    {
        $numPoints = count($points);
        $clusters = array();
        $seen = array();

        while (count($clusters) < $k) {
            $index = floor(rand(0, $numPoints - 1));
            $found = false;
            for ($i=0; $i < $k; $i++) {
                if (isset($seen[$i]) && $index == $seen[$i]) {
                    $found = true;
                    break;
                }
            }
            if (!$found) {
                $seen[] = $index;
                $clusters[] = array(
                    $points[$index],
                    array(
                        $points[$index],
                    ),
                );
            }
        }

        while (true) {
            $plists = array();
            for ($i = 0; $i < $k; $i++) {
                $plists[] = array();
            }

            for ($j = 0; $j < $numPoints; $j++) {
                $p = $points[$j];
                $smallest_distance = 10000000;
                $index = 0;
                for ($i = 0; $i < $k; $i++) {
                    $distance = $this->euclidean($p, $clusters[$i][0]);
                    if ($distance < $smallest_distance) {
                        $smallest_distance = $distance;
                        $index = $i;
                    }
                }
                $plists[$index][] = $p;
            }

            $diff = 0;
            for ($i = 0; $i < $k; $i++) {
                $old = $clusters[$i];
                $list = $plists[$i];
                $center = $this->calculateCenter($plists[$i], 3);
                $new_cluster = array($center, $plists[$i]);
                $dist = $this->euclidean($old[0], $center);
                $clusters[$i] = $new_cluster;
                $diff = $diff > $dist ? $diff : $dist;
            }
            if ($diff < $min_diff) {
                break;
            }
        }

        return $clusters;
    }

    private function calculateCenter($points, $n)
    {
        $vals = array();
        $plen = 0;
        for ($i = 0; $i < $n; $i++) {
            $vals[] = 0;
        }
        $l = count($points);
        for ($i = 0; $i < $l; $i++) {
            $plen++;
            for ($j = 0; $j < $n; $j++) {
                $vals[$j] += $points[$i][$j];
            }
        }
        for ($i = 0; $i < $n; $i++) {
            if ($plen !== 0) {
                $vals[$i] = $vals[$i] / $plen;
            } else {
                $vals[$i] = 0;
            }
        }

        return $vals;
    }

    private function euclidean($p1, $p2)
    {
        $s = 0;
        $l = count($p1);
        for ($i = 0; $i < $l; $i++) {
            $diff = $p1[$i] - $p2[$i]; 
            $s += pow($diff, 2);
        }

        return sqrt($s);
    }

    private function rgbToYuv($r, $g, $b)
    {
        $y = ($r * 0.299) + ($g * 0.114) + ($b * 0.587);
        $u = 0.492 * ($b - $y);
        $v = 0.877 * ($r - $y);

        return array($y, $u, $v);
    }

    private function yuvToRgb($y, $u, $v)
    {
        $r = $y + ($v / 0.877);
        $g = $y - (0.395 * $u) - (0.581 * $v);
        $b = $y + ($u / 0.492);

        return array($r, $g, $b);
    }

    private function getLuminance($r, $g, $b, $method='objective')
    {
        switch (strtolower($method)) {
            case 'perceived_fast':

                return (0.299 * $r) + (0.587 * $g) + (0.114 * $b);
                break;
            case 'perceived_slow':

                return sqrt(pow(0.241 * $r, 2) + pow(0.691 * $g, 2) + pow(0.068 * $b, 2));
                break;
            case 'approximate': // should be the fastest

                return ($r + $r + $g + $g + $g + $b) / 6;
                break;
            case 'objective':
            default:

                return (0.2126 * $r) + (0.7152 * $g) + (0.0722 * $b);
        }
    }

    private function orderByLuminance($colours)
    {
        $luminances = array();
        foreach ($colours as $index => $rgb) {
            $luminances[$index] = $this->getLuminance($rgb[0], $rgb[1], $rgb[2], 'approximate');
        }
        arsort($luminances);
        foreach ($luminances as $index => $value) {
            $sortedColours[] = $colours[$index];
        }

        return $sortedColours;
    }

    private function orderByHue($colours)
    {
        $luminances = array();
        foreach ($colours as $index => $rgb) {
            $luminances[$index] = $this->getHue($rgb[0], $rgb[1], $rgb[2]);
        }
        arsort($luminances);
        foreach ($luminances as $index => $value) {
            $sortedColours[] = $colours[$index];
        }

        return $sortedColours;
    }

    private function rgbToHsl($r, $g, $b)
    {
        $min = min($r, $g, $b);
        $max = max($r, $g, $b);
        $delta = $max - $min;
        $l = ($max + $min) / 2;
        if ($delta == 0) {
            // this is grey (no chroma)
            $h = 0;
            $s = 0;
        } else {
            //Chromatic data...
            if ( $l < 0.5 ) {
                $s = $delta / ( $max + $min );
            } else {
                $s = $delta / ( 2 - $max - $min );
            }
            $rDelta = ((($max - $r) / 6) + ($delta / 2)) / $delta;
            $gDelta = ((($max - $g) / 6) + ($delta / 2)) / $delta;
            $bDelta = ((($max - $b) / 6) + ($delta / 2)) / $delta;
            if ($r == $max) {
                $h = $bDelta - $gDelta;
            } elseif ( $g == $max ) {
                $h = (1 / 3) + $rDelta - $bDelta;
            } elseif ( $b == $max ) {
                $h = (2 / 3) + $gDelta - $rDelta;
            }
            if ( $h < 0 ) {
                $h += 1;
            }
            if ( $h > 1 ) {
                $h -= 1;
            }
        }

        return array($h, $s, $l);
    }

    private function hslToRgb($h, $s, $l)
    {
        if ( $s == 0 ) {
            $r = $l;
            $g = $l;
            $b = $l;
        } else {
            if ( $l < 0.5 ) {
                $v2 = $l * (1 + $s);
            } else {
                $v2 = ($l + $s) - ($s * $l);
            }
            $v1 = 2 * $l - $v2;
            $r = $this->hueToRgb($v1, $v2, $h + (1 / 3));
            $g = $this->hueToRgb($v1, $v2, $h );
            $b = $this->hueToRgb($v1, $v2, $h - (1 / 3));
        }

        return array($r, $g, $b);
    }

    private function rgbToHue($r, $g, $b)
    {
        return atan2(sqrt(3) * ($g - $b), 2 * ($r - $g - $b));
    }

    private function hueToRgb($v1, $v2, $vh)
    {
        if ($vh < 0) {
            $vh += 1;
        }
        if ($vh > 1) {
            $vh -= 1;
        }
        if ((6 * $vh) < 1) {
            return ($v1 + ($v2 - $v1) * 6 * $vh);
        }
        if ((2 * $vh) < 1) {
            return $v2;
        }
        if ((3 * $vh) < 2) {
            return ($v1 + ($v2 - $v1) * ((2 / 3) - $vh) * 6);
        }

        return $v1;
    }
}