Определить положение одного изображения в другом с помощью PHP

Это довольно легко сделать самостоятельно, не полагаясь на внешние библиотеки, отличные от gd .

Что вам нужно знать, так это то, что вы, скорее всего, не сможете выполнить простую проверку пикселя на пиксель, поскольку фильтрация и сжатие могут немного изменить значение каждого пикселя.

Код, который я предлагаю здесь, скорее всего, будет медленным, если производительность вызывает беспокойство, вы можете оптимизировать его или использовать ярлыки. Надеюсь, код поставит вас на правильный путь!

Во-первых, позволяет выполнять итерацию на наших фотографиях

 $small = imagecreatefrompng("small.png"); $large = imagecreatefrompng("large.png"); $smallwidth = imagesx($small); $smallheight = imagesy($small); $largewidth = imagesx($large); $largeheight = imagesy($large); $foundX = -1; $foundY = -1; $keepThreshold = 20; $potentialPositions = array(); for($x = 0; $x <= $largewidth - $smallwidth; ++$x) { for($y = 0; $y <= $largeheight - $smallheight; ++$y) { // Scan the whole picture $error = GetImageErrorAt($large, $small, $x, $y); if($error["avg"] < $keepThreshold) { array_push($potentialPositions, array("x" => $x, "y" => $y, "error" => $error)); } } } imagedestroy($small); imagedestroy($large); echo "Found " . count($potentialPositions) . " potential positions\n"; 

Цель здесь состоит в том, чтобы найти, насколько похожи пиксели, и если они несколько схожи, сохраняйте потенциальную позицию. Здесь я повторяю каждый пиксель большой картинки, это может быть точкой оптимизации.

Теперь, откуда эта ошибка?

Получение вероятности

То, что я здесь сделал, это перебрать маленькую картинку и «окно» на большом снимке, проверяя, какая разница на red , green и blue каналах:

 function GetImageErrorAt($haystack, $needle, $startX, $startY) { $error = array("red" => 0, "green" => 0, "blue" => 0, "avg" => 0); $needleWidth = imagesx($needle); $needleHeight = imagesy($needle); for($x = 0; $x < $needleWidth; ++$x) { for($y = 0; $y < $needleHeight; ++$y) { $nrgb = imagecolorat($needle, $x, $y); $hrgb = imagecolorat($haystack, $x + $startX, $y + $startY); $nr = $nrgb & 0xFF; $hr = $hrgb & 0xFF; $error["red"] += abs($hr - $nr); $ng = ($nrgb >> 8) & 0xFF; $hg = ($hrgb >> 8) & 0xFF; $error["green"] += abs($hg - $ng); $nb = ($nrgb >> 16) & 0xFF; $hb = ($hrgb >> 16) & 0xFF; $error["blue"] += abs($hb - $nb); } } $error["avg"] = ($error["red"] + $error["green"] + $error["blue"]) / ($needleWidth * $needleHeight); return $error; } 

До сих пор мы установили потенциальное значение ошибки для каждого «окна» на большом изображении, которое могло содержать маленькое изображение, и хранить их в массиве, если они кажутся «достаточно хорошими».

Сортировка

Теперь нам просто нужно отсортировать наши лучшие матчи и сохранить лучший, скорее всего, где находится наша маленькая картинка:

 function SortOnAvgError($a, $b) { if($a["error"]["avg"] == $b["error"]["avg"]) { return 0; } return ($a["error"]["avg"] < $b["error"]["avg"]) ? -1 : 1; } if(count($potentialPositions) > 0) { usort($potentialPositions, "SortOnAvgError"); $mostLikely = $potentialPositions[0]; echo "Most likely at " . $mostLikely["x"] . "," . $mostLikely["y"]; } 

пример

Учитывая две следующие фотографии:

а также

Вы должны иметь следующий результат:

 Found 5 potential positions Most likely at 288,235 

Что точно соответствует положению нашей утки. 4 других положения – 1 пиксель вверх, вниз, влево и вправо.

Я собираюсь отредактировать эту запись после того, как я закончил работу над некоторыми оптимизациями для вас, поскольку этот код слишком медленный для больших изображений (PHP выполнялся даже хуже, чем я ожидал).

редактировать

Во-первых, прежде чем делать что-либо, чтобы «оптимизировать» код, нам нужны числа, поэтому я добавил

 function microtime_float() { list($usec, $sec) = explode(" ", microtime()); return ((float)$usec + (float)$sec); } $time_start = microtime_float(); 

а также

 $time_end = microtime_float(); echo "in " . ($time_end - $time_start) . " seconds\n"; 

в конце концов, чтобы иметь конкретное представление о том, сколько времени занимает алгоритм. Таким образом, я могу знать, улучшатся ли мои изменения или ухудшится код. Учитывая, что текущий код с этими фотографиями занимает ~ 45 минут, чтобы выполнить, мы должны быть в состоянии улучшить это время довольно много.

Предварительным, что не было успешным, было кэширование RGB из $needle чтобы ускорить функцию GetImageErrorAt , но это ухудшило время.

Учитывая, что наши вычисления находятся в геометрическом масштабе, чем больше пикселей мы исследуем, тем дольше это займет … поэтому решение состоит в том, чтобы пропустить много пикселей, чтобы попытаться найти как можно быстрее нашу картину, а затем более точно включить зону наша позиция.

Я изменил функцию ошибки, чтобы взять в качестве параметра, как увеличивать x и y

 function GetImageErrorAt($haystack, $needle, $startX, $startY, $increment) { $needleWidth = imagesx($needle); $needleHeight = imagesy($needle); $error = array("red" => 0, "green" => 0, "blue" => 0, "avg" => 0, "complete" => true); for($x = 0; $x < $needleWidth; $x = $x + $increment) { for($y = 0; $y < $needleHeight; $y = $y + $increment) { $hrgb = imagecolorat($haystack, $x + $startX, $y + $startY); $nrgb = imagecolorat($needle, $x, $y); $nr = $nrgb & 0xFF; $hr = $hrgb & 0xFF; $ng = ($nrgb >> 8) & 0xFF; $hg = ($hrgb >> 8) & 0xFF; $nb = ($nrgb >> 16) & 0xFF; $hb = ($hrgb >> 16) & 0xFF; $error["red"] += abs($hr - $nr); $error["green"] += abs($hg - $ng); $error["blue"] += abs($hb - $nb); } } $error["avg"] = ($error["red"] + $error["green"] + $error["blue"]) / ($needleWidth * $needleHeight); return $error; } 

Например, передача 2 приведет к возврату функции в 4 раза быстрее, поскольку мы пропускаем значения x и y .

Я также добавил stepSize для основного цикла:

 $stepSize = 10; for($x = 0; $x <= $largewidth - $smallwidth; $x = $x + $stepSize) { for($y = 0; $y <= $largeheight - $smallheight; $y = $y + $stepSize) { // Scan the whole picture $error = GetImageErrorAt($large, $small, $x, $y, 2); if($error["complete"] == true && $error["avg"] < $keepThreshold) { array_push($potentialPositions, array("x" => $x, "y" => $y, "error" => $error)); } } } 

Сделав это, я смог сократить время выполнения с 2657 секунд до 7 секунд с ценой точности. Я увеличил keepThreshold чтобы получить больше «потенциальных результатов».

Теперь, когда я не проверял каждый пиксель, мой лучший ответ:

 Found 8 potential positions Most likely at 290,240 

Как вы можете видеть, мы находимся рядом с нашей желаемой позицией, но это не совсем правильно.

Далее я буду определять прямоугольник вокруг этой «довольно близкой» позиции, чтобы исследовать каждый пиксель внутри stepSize .

Теперь я меняю нижнюю часть скрипта на:

 if(count($potentialPositions) > 0) { usort($potentialPositions, "SortOnAvgError"); $mostLikely = $potentialPositions[0]; echo "Most probably around " . $mostLikely["x"] . "," . $mostLikely["y"] . "\n"; $startX = $mostLikely["x"] - $stepSize + 1; // - $stepSize was already explored $startY = $mostLikely["y"] - $stepSize + 1; // - $stepSize was already explored $endX = $mostLikely["x"] + $stepSize - 1; $endY = $mostLikely["y"] + $stepSize - 1; $refinedPositions = array(); for($x = $startX; $x <= $endX; ++$x) { for($y = $startY; $y <= $endY; ++$y) { // Scan the whole picture $error = GetImageErrorAt($large, $small, $x, $y, 1); // now check every pixel! if($error["avg"] < $keepThreshold) // make the threshold smaller { array_push($refinedPositions, array("x" => $x, "y" => $y, "error" => $error)); } } } echo "Found " . count($refinedPositions) . " refined positions\n"; if(count($refinedPositions)) { usort($refinedPositions, "SortOnAvgError"); $mostLikely = $refinedPositions[0]; echo "Most likely at " . $mostLikely["x"] . "," . $mostLikely["y"] . "\n"; } } 

Что теперь дает мне выход вроде:

 Found 8 potential positions Most probably around 290,240 Checking between X 281 and 299 Checking between Y 231 and 249 Found 23 refined positions Most likely at 288,235 in 13.960182189941 seconds 

Это действительно правильный ответ, примерно в 200 раз быстрее, чем исходный сценарий.

Изменить 2

Теперь мой тестовый пример был слишком простым … Я изменил его на поиск изображений в Google:

Ищет это изображение (он находится по адресу 718,432 )

Учитывая большие размеры изображений, мы можем ожидать более длительное время обработки, но алгоритм нашел изображение в правильном положении:

 Found 123 potential positions Most probably around 720,430 Found 17 refined positions Most likely at 718,432 in 43.224536895752 seconds 

Редактировать 3

Я решил попробовать вариант, который я сказал вам в комментарии, чтобы уменьшить изображение перед выполнением поиска, и у меня были отличные результаты.

Я добавил этот код до первого цикла:

 $smallresizedwidth = $smallwidth / 2; $smallresizedheight = $smallheight / 2; $largeresizedwidth = $largewidth / 2; $largeresizedheight = $largeheight / 2; $smallresized = imagecreatetruecolor($smallresizedwidth, $smallresizedheight); $largeresized = imagecreatetruecolor($largeresizedwidth, $largeresizedheight); imagecopyresized($smallresized, $small, 0, 0, 0, 0, $smallresizedwidth, $smallresizedheight, $smallwidth, $smallheight); imagecopyresized($largeresized, $large, 0, 0, 0, 0, $largeresizedwidth, $largeresizedheight, $largewidth, $largeheight); 

И для них основной цикл я повторил на измененных размерах с измененной шириной и высотой. Затем, добавляя к массиву, я удваиваю x и y , давая следующее:

 array_push($potentialPositions, array("x" => $x * 2, "y" => $y * 2, "error" => $error)); 

Остальная часть кода остается прежней, так как мы хотим сделать точное местоположение на изображениях реального размера. Все, что вам нужно сделать, это добавить в конце:

 imagedestroy($smallresized); imagedestroy($largeresized); 

Используя эту версию кода, с результатом изображения Google, у меня было:

 Found 18 potential positions Most around 720,440 Found 17 refined positions Most likely at 718,432 in 11.499078989029 seconds 

Увеличение производительности в 4 раза!

Надеюсь это поможет

Используйте ImageMagick .

Эта страница даст вам ответ: как я могу определить / рассчитать, есть ли маленькие снимки внутри большего изображения?