Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
image pattern matching, MAD
<?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();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.