image pattern matching, MAD

image-pattern-matching.php

<?php
class ImgCompare
{
    /** @var string $bigSrc */
    protected $bigSrc;

    /** @var array $haystack */
    protected $haystack = [];

    /** @var array $needle */
    protected $needle = [];

    public function __construct(string $bigSrc)
    {
        $this->bigSrc = $bigSrc;
    }

    public function find(string $smallSrc): array
    {
        $big = $this->loadImage($this->bigSrc);
        $small = $this->loadImage($smallSrc);

        $scales = $this->calcScales($big, $small);
        $suitable = [];
        $prevScale = null;
        foreach ($scales as $scale) {
            $haystack = $this->resize($big, $scale);
            $this->loadCache($haystack, $this->haystack);
            imagedestroy($haystack);

            $needle = $this->resize($small, $scale);
            $this->loadCache($needle, $this->needle);
            imagedestroy($needle);

            if ($prevScale !== null) {
                $suitable = $this->expand($suitable, $prevScale / $scale);
            }
            $prevScale = $scale;

            $suitable = $this->compare($suitable);
            $suitable = $this->crop($suitable);
        }
        return $suitable;
    }

    protected function calcScales($big, $small): array
    {
        return [4, 2, 1];
    }

    protected function loadImage($src)
    {
        $img = imagecreatefrompng($src);
        return $img;
    }

    protected function resize($src, int $scale)
    {
        $width = imagesx($src);
        $height = imagesy($src);
        $w = (int) round($width / $scale);
        $h = (int) round($height / $scale);
        $dest = imagecreatetruecolor($w, $h);
        imagecopyresampled($dest, $src, 0, 0, 0, 0, $w, $h, $width, $height);
        return $dest;
    }

    protected function loadCache($img, &$arr)
    {
        $arr = [];
        $w = imagesx($img);
        $h = imagesy($img);
        for ($row = 0; $row < $h; $row++) {
            $arr[$row] = [];
            for ($col = 0; $col < $w; $col++) {
                $arr[$row][$col] = imagecolorat($img, $col, $row);
            }
        }
    }

    protected function compare(array $suitable): array
    {
        $width = count($this->haystack[0]);
        $height = count($this->haystack);

        $w = count($this->needle[0]);
        $h = count($this->needle);

        $arr = [];
        for ($row = 0; $row <= $height - $h; $row++) {
            if (empty($suitable) || isset($suitable[$row])) {
                for ($col = 0; $col <= $width - $w; $col++) {
                    if (empty($suitable) || isset($suitable[$row][$col])) {
                        $arr[$row][$col] = $this->weight($row, $col);
                    }
                }
            }
        }
        return $arr;
    }

    protected function weight(int $row, int $col): int
    {
        $w = count($this->needle[0]);
        $h = count($this->needle);

        $result = 0;
        for ($r = 0; $r < $h; $r++) {
            for ($c = 0; $c < $w; $c++) {
                $result += abs($this->needle[$r][$c] - $this->haystack[$row + $r][$col + $c]);
            }
        }
        return $result;
    }

    protected function crop(array $suitable): array
    {
        $arr = [];
        foreach ($suitable as $row => $cols) {
            foreach ($cols as $col => $weight) {
                $arr["{$row},{$col}"] = $weight;
            }
        }
        asort($arr);
        $arr = array_slice($arr, 0, 25, true);

        $suitable = [];
        foreach ($arr as $entry => $weight) {
            list($row, $col) = explode(",", $entry);
            if (!isset($suitable[$row])) {
                $suitable[$row] = [];
            }
            $suitable[$row][$col] = $weight;
        }
        return $suitable;
    }

    protected function expand(array $suitable, float $scale): array
    {
        $arr = [];
        foreach ($suitable as $row => $cols) {
            $arr[$row * $scale] = [];
            foreach ($cols as $col => $weight) {
                $arr[$row * $scale][$col * $scale] = $weight;
                // + 8 around
                // upper
                if ($row > 0) {
                    $arr[$row * $scale - 1][$col * $scale - 1] = $weight;
                    $arr[$row * $scale - 1][$col * $scale] = $weight;
                    $arr[$row * $scale - 1][$col * $scale + 1] = $weight;
                }
                // left, right
                if ($col > 0) {
                    $arr[$row * $scale][$col * $scale - 1] = $weight;
                }
                if ($col < count($cols) - 1) {
                    $arr[$row * $scale][$col * $scale + 1] = $weight;
                }
                // bottom
                if ($row < count($suitable) - 1) {
                    $arr[$row * $scale + 1][$col * $scale - 1] = $weight;
                    $arr[$row * $scale + 1][$col * $scale] = $weight;
                    $arr[$row * $scale + 1][$col * $scale + 1] = $weight;
                }
            }
        }
        return $arr;
    }
}

//$img = imagecreatetruecolor(200, 150);
//$gray = imagecolorallocate($img, 150, 150, 150);
//imagefill($img, 0, 0, $gray);
//$red = imagecolorallocate($img, 255, 100, 100);
//// 1
//imagesetpixel($img, 0, 0, $red);
//imagesetpixel($img, 1, 0, $red);
//imagesetpixel($img, 0, 1, $red);
//imagesetpixel($img, 1, 1, $red);
//// 2
//imagesetpixel($img, 20, 30, $red);
//imagesetpixel($img, 21, 30, $red);
//imagesetpixel($img, 20, 31, $red);
//imagesetpixel($img, 21, 31, $red);
//imagepng($img, __DIR__ . '/big.png');
//imagedestroy($img);
//
//$img = imagecreatetruecolor(8, 11);
//$gray = imagecolorallocate($img, 150, 150, 150);
//imagefill($img, 0, 0, $gray);
//$red = imagecolorallocate($img, 255, 100, 100);
//imagesetpixel($img, 0, 0, $red);
//imagesetpixel($img, 1, 0, $red);
//imagesetpixel($img, 0, 1, $red);
//imagesetpixel($img, 1, 1, $red);
//imagepng($img, __DIR__ . '/small.png');
//imagedestroy($img);

$start = microtime(true);

$c = new ImgCompare(__DIR__ . '/big.png');
$suitable = $c->find(__DIR__ . '/small.png');
foreach ($suitable as $row => $cols) {
    foreach ($cols as $col => $weight) {
        echo "{$row},{$col} = {$weight}\n";
    }
}

$stop = microtime(true);
echo 'time: ' . round($stop - $start, 4) . ' sec.' . PHP_EOL;

class Test extends ImgCompare
{
    public function Test_loadCache()
    {
        $img = imagecreatetruecolor(3, 1);
        $bgColor = imagecolorallocate($img, 255, 255, 255);
        imagefill($img, 0, 0, $bgColor);
        $r = imagecolorallocate($img, 255, 0, 0);
        $g = imagecolorallocate($img, 0, 255, 0);
        $b = imagecolorallocate($img, 0, 0, 255);
        imagesetpixel($img, 0, 0, $r);
        imagesetpixel($img, 1, 0, $g);
        imagesetpixel($img, 2, 0, $b);

        $this->loadCache($img, $this->haystack);
        assert(count($this->haystack) === 1);
        assert(isset($this->haystack[0]));
        assert(count($this->haystack[0]) === 3);
        assert($this->haystack[0][0] === 255 * pow(256, 2) + 0 * pow(256, 1) + 0 * pow(256, 0));
        assert($this->haystack[0][1] === 0 * pow(256, 2) + 255 * pow(256, 1) + 0 * pow(256, 0));
        assert($this->haystack[0][2] === 0 * pow(256, 2) + 0 * pow(256, 1) + 255 * pow(256, 0));
    }

    public function Test_weight()
    {
        $this->haystack = [
            [10, 20, 30],
            [40, 50, 60],
            [70, 80, 90],
        ];
        $this->needle = [
            [100, 20],
            [200, 50],
        ];

        assert($this->weight(0, 0) === abs(100 - 10) + abs(20 - 20) + abs(200 - 40) + abs(50 - 50));
        assert($this->weight(0, 1) === abs(100 - 20) + abs(20 - 30) + abs(200 - 50) + abs(50 - 60));
        assert($this->weight(1, 0) === abs(100 - 40) + abs(20 - 50) + abs(200 - 70) + abs(50 - 80));
        assert($this->weight(1, 1) === abs(100 - 50) + abs(20 - 60) + abs(200 - 80) + abs(50 - 90));
    }

    public function Test_compare()
    {
        $this->haystack = [
            [10, 20, 30],
            [40, 50, 60],
            [70, 80, 90],
        ];
        $this->needle = [
            [100, 20],
            [200, 50],
        ];

        $expected = [
            [$this->weight(0, 0), $this->weight(0, 1)],
            [$this->weight(1, 0), $this->weight(1, 1)],
        ];
        $actual = $this->compare([]);

        assert(
            $expected === $actual,
            'Expected: ' . var_export($expected, true) . '; actual: ' . var_export($actual, true)
        );
    }
}

$test = new Test('');
$test->Test_loadCache();
$test->Test_weight();
$test->Test_compare();