How to compare image similarity using php regardless of scale, rotation?

Question

I want to compare similarity between below images. Acording to my requirements I want to identify all of these images as similar, since it has use the same color, same clip art. The only difference in these images are rotation ,scale and the placement of the clip art. Since all 3 t-shirts has used the same color and clip art I want to identify all 3 images as similar. I tried out the method described in hackerfactor.com. But it doesn't give me correct result acording to my requirements. How to identify all these images as similar?DO you have any suggestions? Please help me.

The below images should be recognized as different from above images.(Even though the tshirts has the same color, clip arts are different. Last tshirt is different from above, because it has use the same clip art, but twice. )

Answer 1

Moved to GitHub

Because this question is quite interesting, I moved the whole thing to GitHub where you can find the current implementation: ImageCompare

Original answer

I made a very simple approach, using img-resize and comparing the average color of the resized images.

$binEqual = [
    file_get_contents('http://i.stack.imgur.com/D8ct1.png'),
    file_get_contents('http://i.stack.imgur.com/xNZt1.png'),
    file_get_contents('http://i.stack.imgur.com/kjGjm.png')
];

$binDiff = [
    file_get_contents('http://i.stack.imgur.com/WIOHs.png'),
    file_get_contents('http://i.stack.imgur.com/ljoBT.png'),
    file_get_contents('http://i.stack.imgur.com/qEKSK.png')
];


function getAvgColor($bin, $size = 10) {

    $target = imagecreatetruecolor($size, $size);
    $source = imagecreatefromstring($bin);

    imagecopyresized($target, $source, 0, 0, 0, 0, $size, $size, imagesx($source), imagesy($source));

    $r = $g = $b = 0;

    foreach(range(0, $size - 1) as $x) {
        foreach(range(0, $size - 1) as $y) {
            $rgb = imagecolorat($target, $x, $y);
            $r += $rgb >> 16;
            $g += $rgb >> 8 & 255;
            $b += $rgb & 255;
        }
    }   

    unset($source, $target);

    return (floor($r / $size ** 2) << 16) +  (floor($g / $size ** 2) << 8)  + floor($b / $size ** 2);
}

function compAvgColor($c1, $c2, $tolerance = 4) {

    return abs(($c1 >> 16) - ($c2 >> 16)) <= $tolerance && 
           abs(($c1 >> 8 & 255) - ($c2 >> 8 & 255)) <= $tolerance &&
           abs(($c1 & 255) - ($c2 & 255)) <= $tolerance;
}

$perms = [[0,1],[0,2],[1,2]];

foreach($perms as $perm) {
    var_dump(compAvgColor(getAvgColor($binEqual[$perm[0]]), getAvgColor($binEqual[$perm[1]])));
}

foreach($perms as $perm) {
    var_dump(compAvgColor(getAvgColor($binDiff[$perm[0]]), getAvgColor($binDiff[$perm[1]])));
}

For the used size and color-tolerance I get the expected result:

bool(true)
bool(true)
bool(true)
bool(false)
bool(false)
bool(false)

More advanced implementation

Empty T-Shirt to compare:

$binEqual = [
    file_get_contents('http://i.stack.imgur.com/D8ct1.png'),
    file_get_contents('http://i.stack.imgur.com/xNZt1.png'),
    file_get_contents('http://i.stack.imgur.com/kjGjm.png')
];

$binDiff = [
    file_get_contents('http://i.stack.imgur.com/WIOHs.png'),
    file_get_contents('http://i.stack.imgur.com/ljoBT.png'),
    file_get_contents('http://i.stack.imgur.com/qEKSK.png')
];

class Color {
    private $r = 0;
    private $g = 0;
    private $b = 0;

    public function __construct($r = 0, $g = 0, $b = 0)
    {
        $this->r = $r;
        $this->g = $g;
        $this->b = $b;
    }

    public function r()
    {
        return $this->r;
    }

    public function g()
    {
        return $this->g;
    }

    public function b()
    {
        return $this->b;
    }

    public function toInt()
    {
        return $this->r << 16 + $this->g << 8 + $this->b;
    }

    public function toRgb()
    {
        return [$this->r, $this->g, $this->b];  
    }

    public function mix(Color $color)
    {
        $this->r = round($this->r + $color->r() / 2);
        $this->g = round($this->g + $color->g() / 2);
        $this->b = round($this->b + $color->b() / 2);
    }

    public function compare(Color $color, $tolerance = 500)
    {
        list($r1, $g1, $b1) = $this->toRgb();
        list($r2, $g2, $b2) = $color->toRgb();

        $diff = round(sqrt(pow($r1 - $r2, 2) + pow($g1 - $g2, 2) + pow($b1 - $b2, 2)));

        printf("Comp r(%s : %s), g(%s : %s), b(%s : %s) Diff %s \n", $r1, $r2, $g1, $g2, $b1, $b2, $diff);

        return  $diff <= $tolerance;
    }

    public static function fromInt($int) {
        return new self($int >> 16, $int >> 8 & 255, $int & 255);
    }
}


function getAvgColor($bin, $size = 5) {

    $target    = imagecreatetruecolor($size, $size);
    $targetTmp = imagecreatetruecolor($size, $size);

    $sourceTmp = imagecreatefrompng('http://i.stack.imgur.com/gfn5A.png');
    $source    = imagecreatefromstring($bin);

    imagecopyresized($target, $source, 0, 0, 0, 0, $size, $size, imagesx($source), imagesy($source));
    imagecopyresized($targetTmp, $sourceTmp, 0, 0, 0, 0, $size, $size, imagesx($source), imagesy($source));

    $r = $g = $b = $relPx = 0;

    $baseColor = new Color();

    foreach(range(0, $size - 1) as $x) {
        foreach(range(0, $size - 1) as $y) {
            if (imagecolorat($target, $x, $y) != imagecolorat($targetTmp, $x, $y))
                $baseColor->mix(Color::fromInt(imagecolorat($target, $x, $y)));
        }
    }

    unset($source, $target, $sourceTmp, $targetTmp);

    return $baseColor;

}

$perms = [[0,0], [1,0], [2,0], [1,0], [1,1], [1,2], [2,0], [2,1], [2,2]];

echo "Equal\n";
foreach($perms as $perm) {
    var_dump(getAvgColor($binEqual[$perm[0]])->compare(getAvgColor($binEqual[$perm[1]])));
}

echo "Different\n";
foreach($perms as $perm) {
    var_dump(getAvgColor($binEqual[$perm[0]])->compare(getAvgColor($binDiff[$perm[1]])));
}

Result:

Equal
Comp r(101 : 101), g(46 : 46), b(106 : 106) Diff 0 
bool(true)
Comp r(121 : 101), g(173 : 46), b(249 : 106) Diff 192 
bool(true)
Comp r(219 : 101), g(179 : 46), b(268 : 106) Diff 241 
bool(true)
Comp r(121 : 101), g(173 : 46), b(249 : 106) Diff 192 
bool(true)
Comp r(121 : 121), g(173 : 173), b(249 : 249) Diff 0 
bool(true)
Comp r(121 : 219), g(173 : 179), b(249 : 268) Diff 100 
bool(true)
Comp r(219 : 101), g(179 : 46), b(268 : 106) Diff 241 
bool(true)
Comp r(219 : 121), g(179 : 173), b(268 : 249) Diff 100 
bool(true)
Comp r(219 : 219), g(179 : 179), b(268 : 268) Diff 0 
bool(true)
Different
Comp r(101 : 446), g(46 : 865), b(106 : 1242) Diff 1442 
bool(false)
Comp r(121 : 446), g(173 : 865), b(249 : 1242) Diff 1253 
bool(false)
Comp r(219 : 446), g(179 : 865), b(268 : 1242) Diff 1213 
bool(false)
Comp r(121 : 446), g(173 : 865), b(249 : 1242) Diff 1253 
bool(false)
Comp r(121 : 654), g(173 : 768), b(249 : 1180) Diff 1227 
bool(false)
Comp r(121 : 708), g(173 : 748), b(249 : 1059) Diff 1154 
bool(false)
Comp r(219 : 446), g(179 : 865), b(268 : 1242) Diff 1213 
bool(false)
Comp r(219 : 654), g(179 : 768), b(268 : 1180) Diff 1170 
bool(false)
Comp r(219 : 708), g(179 : 748), b(268 : 1059) Diff 1090 
bool(false)

In this calculation the background is ignored what leads to bigger difference in the avg color.

Final implementation (OOP)

Quite interessting topic. So i tryed to tune it up a liddle bit. This is now a complete OOP implementation. You can now create a new image and subtract some mask of it in order to eliminate a background. Then you can compare one image to another using the compare method. To keep the calculation limited it's better to resize your image first (masks are allways fittet to the current image)

The compare algorythme it self chunks the two images into serveral tiles, then eliminates tiles, that are almost equal to white average color and then compares the average color of all remaining tile-permutations.

Class Image {

    const HASH_SIZE = 8;
    const AVG_SIZE = 10;

    private $img = null;

    public function __construct($resource)
    {
        $this->img = $resource;;
    }

    private function permute(array $a1, array $a2) {
        $perms = array();
        for($i = 0; $i < sizeof($a1); $i++) {
            for($j = $i; $j < sizeof($a2); $j++) {
                if ($i != $j) {
                    $perms[] = [$a1[$i], 
                    $a2[$j]];
                }
            }
        }

        return $perms;
    }

    public function compare(Image $comp) {
        $avgComp = array();

        foreach($comp->chunk(25) as $chunk) {
            $avgComp[] = $chunk->avg();
        }

        $avgOrg = array();

        foreach($this->chunk(25) as $chunk) {
            $avgOrg[] = $chunk->avg();
        }

        $white = Color::fromInt(0xFFFFFF);

        $avgComp = array_values(array_filter($avgComp, function(Color $color) use ($white){
            return $white->compare($color, 1000);
        }));

        $avgOrg = array_values(array_filter($avgOrg, function(Color $color) use ($white){
            return $white->compare($color, 1000);
        }));

        $equal = 0;
        $pairs = $this->permute($avgOrg, $avgComp);

        foreach($pairs as $pair) {
            $equal += $pair[0]->compare($pair[1], 100) ? 1 : 0;
        }

        return ($equal / sizeof($pairs));
    }

    public function substract(Image $mask, $tolerance = 50)
    {
        $size = $this->size();

        if ($mask->size() != $size) {
            $mask = $mask->resize($size);
        }

        for ($x = 0; $x < $size[0]; $x++) {
            for ($y = 0; $y < $size[1]; $y++) {
                if ($this->colorat($x, $y)->compare($mask->colorat($x, $y), $tolerance))
                    imagesetpixel($this->img, $x, $y, 0xFFFFFF);
            }
        }

        return $this;
    }

    public function avg($size = 10)
    {
        $target = $this->resize([self::AVG_SIZE, self::AVG_SIZE]);

        $avg   = Color::fromInt(0x000000);
        $white = Color::fromInt(0xFFFFFF);  

        for ($x = 0; $x < self::AVG_SIZE; $x++) {
            for ($y = 0; $y < self::AVG_SIZE; $y++) {
                $color = $target->colorat($x, $y);
                if (!$color->compare($white, 10))
                    $avg->mix($color);
            }
        }

        return $avg;
    }

    public function colorat($x, $y)
    {
        return Color::fromInt(imagecolorat($this->img, $x, $y));
    }

    public function chunk($chunkSize = 10)
    {
        $collection = new ImageCollection();
        $size = $this->size();

        for($x = 0; $x < $size[0]; $x += $chunkSize) {
            for($y = 0; $y < $size[1]; $y += $chunkSize) {
                switch (true) {
                    case ($x + $chunkSize > $size[0] && $y + $chunkSize > $size[1]):
                        $collection->push($this->slice(['x' => $x, 'y' => $y, 'height' => $size[0] - $x, 'width' => $size[1] - $y]));
                        break;
                    case ($x + $chunkSize > $size[0]):
                        $collection->push($this->slice(['x' => $x, 'y' => $y, 'height' => $size[0] - $x, 'width' => $chunkSize]));
                        break;
                    case ($y + $chunkSize > $size[1]):
                        $collection->push($this->slice(['x' => $x, 'y' => $y, 'height' => $chunkSize, 'width' => $size[1] - $y]));
                        break;
                    default:
                        $collection->push($this->slice(['x' => $x, 'y' => $y, 'height' => $chunkSize, 'width' => $chunkSize]));
                        break;
                }
            }
        }

        return $collection;
    }

    public function slice(array $rect)
    {
        return Image::fromResource(imagecrop($this->img, $rect));
    }

    public function size()
    {
        return [imagesx($this->img), imagesy($this->img)];
    }

    public function resize(array $size = array(100, 100))
    {
        $target = imagecreatetruecolor($size[0], $size[1]);
        imagecopyresized($target, $this->img, 0, 0, 0, 0, $size[0], $size[1], imagesx($this->img), imagesy($this->img));

        return Image::fromResource($target);
    }

    public function show()
    {
        header("Content-type: image/png");
        imagepng($this->img);
        die();
    }

    public function save($name = null, $path = '') {
        if ($name === null) {
            $name = $this->hash();
        }

        imagepng($this->img, $path . $name . '.png');

        return $this;
    }

    public function hash()
    {
                // Resize the image.
        $resized = imagecreatetruecolor(self::HASH_SIZE, self::HASH_SIZE);
        imagecopyresampled($resized, $this->img, 0, 0, 0, 0, self::HASH_SIZE, self::HASH_SIZE, imagesx($this->img), imagesy($this->img));
        // Create an array of greyscale pixel values.
        $pixels = [];
        for ($y = 0; $y < self::HASH_SIZE; $y++)
        {
            for ($x = 0; $x < self::HASH_SIZE; $x++)
            {
                $rgb = imagecolorsforindex($resized, imagecolorat($resized, $x, $y));
                $pixels[] = floor(($rgb['red'] + $rgb['green'] + $rgb['blue']) / 3);
            }
        }
        // Free up memory.
        imagedestroy($resized);
        // Get the average pixel value.
        $average = floor(array_sum($pixels) / count($pixels));
        // Each hash bit is set based on whether the current pixels value is above or below the average.
        $hash = 0; $one = 1;
        foreach ($pixels as $pixel)
        {
            if ($pixel > $average) $hash |= $one;
            $one = $one << 1;
        }
        return $hash;
    }

    public static function fromResource($resource)
    {
        return new self($resource);
    }

    public static function fromBin($binf)
    {
        return new self(imagecreatefromstring($bin));
    }

    public static function fromFile($path)
    {
        return new self(imagecreatefromstring(file_get_contents($path)));
    }
}

class ImageCollection implements IteratorAggregate
{
    private $images = array();

    public function __construct(array $images = array())
    {
        $this->images = $images;
    }

    public function push(Image $image) {
        $this->images[] = $image;
        return $this;
    }

    public function pop()
    {
        return array_pop($this->images);
    }

    public function save()
    {
        foreach($this->images as $image)
        {
            $image->save();
        }

        return $this;
    }

    public function getIterator() {
        return new ArrayIterator($this->images);
    }
}

class Color {
    private $r = 0;
    private $g = 0;
    private $b = 0;

    public function __construct($r = 0, $g = 0, $b = 0)
    {
        $this->r = $r;
        $this->g = $g;
        $this->b = $b;
    }

    public function r()
    {
        return $this->r;
    }

    public function g()
    {
        return $this->g;
    }

    public function b()
    {
        return $this->b;
    }

    public function toInt()
    {
        return $this->r << 16 + $this->g << 8 + $this->b;
    }

    public function toRgb()
    {
        return [$this->r, $this->g, $this->b];  
    }

    public function mix(Color $color)
    {
        $this->r = round($this->r + $color->r() / 2);
        $this->g = round($this->g + $color->g() / 2);
        $this->b = round($this->b + $color->b() / 2);
    }

    public function compare(Color $color, $tolerance = 500)
    {
        list($r1, $g1, $b1) = $this->toRgb();
        list($r2, $g2, $b2) = $color->toRgb();

        $diff = round(sqrt(pow($r1 - $r2, 2) + pow($g1 - $g2, 2) + pow($b1 - $b2, 2)));

        //printf("Comp r(%s : %s), g(%s : %s), b(%s : %s) Diff %s \n", $r1, $r2, $g1, $g2, $b1, $b2, $diff);

        return  $diff <= $tolerance;
    }

    public static function fromInt($int) {
        return new self($int >> 16, $int >> 8 & 255, $int & 255);
    }
}

$mask = Image::fromFile('http://i.stack.imgur.com/gfn5A.png');

$image1 = Image::fromFile('http://i.stack.imgur.com/D8ct1.png')->resize([50, 100])->substract($mask, 100);
$image2 = Image::fromFile('http://i.stack.imgur.com/xNZt1.png')->resize([50, 100])->substract($mask, 100);
$image3 = Image::fromFile('http://i.stack.imgur.com/kjGjm.png')->resize([50, 100])->substract($mask, 100);

$other1 = Image::fromFile('http://i.stack.imgur.com/WIOHs.png')->resize([50, 100])->substract($mask, 100);
$other2 = Image::fromFile('http://i.stack.imgur.com/ljoBT.png')->resize([50, 100])->substract($mask, 100);
$other3 = Image::fromFile('http://i.stack.imgur.com/qEKSK.png')->resize([50, 100])->substract($mask, 100);


echo "Equal\n";
var_dump(
    $image1->compare($image2),
    $image1->compare($image3),
    $image2->compare($image3)
);

echo "Image 1 to Other\n";
var_dump(
    $image1->compare($other1),
    $image1->compare($other2),
    $image1->compare($other3)
);

echo "Image 2 to Other\n";
var_dump(
    $image2->compare($other1),
    $image2->compare($other2),
    $image2->compare($other3)
);

echo "Image 3 to Other\n";
var_dump(
    $image3->compare($other1),
    $image3->compare($other2),
    $image3->compare($other3)
);

Result:

Equal
float(0.47619047619048)
float(0.53333333333333)
float(0.4)
Image 1 to Other
int(0)
int(0)
int(0)
Image 2 to Other
int(0)
int(0)
int(0)
Image 3 to Other
int(0)
int(0)
int(0)

Answer 2

I'm not claiming to really know anything about this topic, which I think generally is termed 'vision'.

What I would do however, is something along these lines:

Flow:

• Posterise, to minimal number of colors/shades (guess).
• Remove two largest colors (white + shirt).
• Compare remaining color-palette, and fail if schemes differ too much.
• Calculate a coarse polygon around any remaining 'color-blobs' (see https://en.wikipedia.org/wiki/Convex_hull )
• Compare number of polygons and largest polygon’s number of angles and angle-values (not size), from each image, and fail or pass.

Main problem in such a setup, will be rounding ... as in posterising a color, that is precisely at middelpoint between two colors ... sometimes it gets colorA, sometimes it gets colorB. Same with the polygons, I guess.