使用PHP确定一个图像在另一个图像中的位置 [英] Determine position of one image in another with PHP
问题描述
我有两张图片（小图和大图）。其中一个包含另一个。像一张图片的东西是一张照片，另一张图片是这张照片所在的photoalbum页面的图片。我希望你理解我说的话。
I have two images(small and big). One of them contains another one. Something like one image is a photo and another one is a picture of the page of the photoalbum where this photo is situated. I hope you understood what I said.
那么如何使用PHP获取大图像上的小图像的坐标（x，y）？
So how do I get coordinates (x,y) of a small image on the big one using PHP?
推荐答案
除了 gd 以外，依靠外部库，很容易自己做。
It is quite easy to do on your own, without relying on external libs other than gd.
您需要注意的是，您很可能无法对每个像素进行简单的像素检查，因为过滤和压缩可能会略微修改每个像素的值。
What you need to be aware of, is that you most likely cannot do a simple pixel per pixel check, as filtering and compression might slightly modify the value of each pixel.
我在这里提出的代码很可能很慢，如果考虑性能，你可以优化它或采取捷径。希望代码能让您走上正轨！
The code I am proposing here will most likely be slow, if performance is a concern, you could optimize it or take shortcuts. Hopefully, the code puts you on the right track!
首先，让我们迭代我们的照片
$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";
这里的目标是找出像素的相似程度，如果它们有些相似，请保持潜在的位置。在这里，我迭代大图片的每个像素，这可能是一个优化点。
The goal here is to find how similar the pixels are, and if they are somewhat similar, keep the potential position. Here, I iterate each and every pixel of the large picture, this could be a point of optimization.
现在，这个错误来自哪里？
Now, where does this error come from?
获得可能性
我在这里做的是迭代小图片和窗口在大图片中检查红色，绿色和蓝色频道：
What I did here is iterate over the small picture and a "window" in the large picture checking how much difference there was on the red, green and blue channel:
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;
}
到目前为止，我们为每个窗口建立了一个潜在的错误值在可以包含小图片的大图片中，如果它们看起来足够好，则将它们存储在一个数组中。
So far, we've established a potential error value for every "window" in the large picture that could contain the small picture, and store them in an array if they seem "good enough".
排序
现在，我们只需要对最佳匹配进行排序并保持最佳匹配，这很可能是我们的小图片所在：
Now, we simply need to sort our best matches and keep the best one, it is most likely where our small picture is located:
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个像素。
Which corresponds exactly with the position of our duck. The 4 other positions are 1 pixel up, down, left and right.
在我完成一些优化后，我将编辑此条目，如这段代码对于大图片来说太慢了（PHP的表现比我预期的还差）。
I am going to edit this entry after I'm done working on some optimizations for you, as this code is way too slow for big images (PHP performed even worse than I expected).
编辑
首先，在做任何优化代码之前，我们需要数字，所以我添加了
First, before doing anything to "optimize" the code, we need numbers, so I added
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分钟才能执行，我们应该能够相当多地改善这段时间。
at the end to have a specific idea of how much time is taken during the algorithm. This way, I can know if my changes improve or make the code worse. Given that the current code with these pictures takes ~45 minutes to execute, we should be able to improve this time quite a lot.
暂时不成功，是从 $ needle 缓存 RGB 以尝试加速 GetImageErrorAt 函数，但它会缩短时间。
A tentative that was not succesful, was to cache the RGB from the $needle to try to accelerate the GetImageErrorAt function, but it worsened the time.
鉴于我们的计算是在几何尺度上，我们探索的像素越多，所需的时间就越长......因此，解决方案是跳过许多像素以尽可能快地找到我们的图片，然后更准确地将我们的位置区域化。
Given that our computation is on a geometric scale, the more pixels we explore, the longer it will take... so a solution is to skip many pixels to try to locate as fast as possible our picture, and then more accurately zone in on our position.
我将错误函数修改为作为参数如何增加 x 和 y
I modified the error function to take as a parameter how to increment the x and 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 值。
For example, passing 2 will make the function return 4 times faster, as we skip both x and y values.
我还为主循环添加了 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 以获得更多潜在结果。
Doing this, I was able to reduce the execution time from 2657 seconds to 7 seconds at a price of precision. I increased the keepThreshold to have more "potential results".
现在我没有检查每个像素，我的最佳答案是：
Now that I wasn't checking each pixels, my best answer is:
Found 8 potential positions
Most likely at 290,240
正如你所看到的，我们已接近我们想要的位置，但这不太正确。
As you can see, we're near our desired position, but it's not quite right.
接下来我要做的是在这个非常接近的位置定义一个矩形，以探索我们添加的 stepSize 中的每个像素。
What I'm going to do next is define a rectangle around this "pretty close" position to explore every pixel inside the stepSize we added.
我现在正在更改脚本的下半部分：
I'm now changing the lower part of the script for:
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倍。
Which is indeed the right answer, roughly 200 times faster than the initial script.
编辑2
现在，我的测试用例有点过于简单......我将其更改为谷歌图片搜索：
Now, my test case was a bit too simple... I changed it to a google image search:
正在寻找这张图片（它位于 718,432 ）
Looking for this picture (it's located at 718,432)
考虑到更大的图片尺寸，我们可以期待更长的处理时间，但算法确实找到了ri的图片位置：
Considering the bigger picture sizes, we can expect a longer processing time, but the algorithm did find the picture at the right position:
Found 123 potential positions
Most probably around 720,430
Found 17 refined positions
Most likely at 718,432
in 43.224536895752 seconds
编辑3
我决定尝试在评论中告诉你的选项，在执行查找之前缩小图片，我用它做了很好的结果。
I decided to try the option I told you in the comment, to scale down the pictures before executing the find, and I had great results with it.
我在第一个循环之前添加了这段代码：
I added this code before the first loop:
$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 ，给出以下内容：
And for them main loop I iterated on the resized assets with the resized width and height. Then, when adding to the array, I double the x and y, giving the following:
array_push($potentialPositions, array("x" => $x * 2, "y" => $y * 2, "error" => $error));
其余代码保持不变，因为我们想要在实际尺寸上做精确定位图片。你所要做的就是在最后添加：
The rest of the code remains the same, as we want to do the precise location on the real size pictures. All you have to do is add at the end:
imagedestroy($smallresized);
imagedestroy($largeresized);
使用此版本的代码，使用google图片结果，我有：
Using this version of the code, with the google image result, I had:
Found 18 potential positions
Most around 720,440
Found 17 refined positions
Most likely at 718,432
in 11.499078989029 seconds
性能提升4倍！
希望这有助于
这篇关于使用PHP确定一个图像在另一个图像中的位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
