4

私は2つの画像（小と大）を持っています。そのうちの 1 つに別の 1 つが含まれています。ある画像は写真であり、別の画像はこの写真が掲載されているフォトアルバムのページの写真です。私が言ったことを理解していただければ幸いです。

では、PHP を使用して大きな画像上の小さな画像の座標 (x,y) を取得するにはどうすればよいでしょうか?

4

2 に答える 2

11

以外の外部ライブラリに依存せずに、自分で行うのは非常に簡単です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"];
}

例

次の2つの写真を考えると：

大きい

と

小さな

次の結果が得られるはずです。

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からをキャッシュすることでしたが、時間が悪化しました。$needleGetImageErrorAt

計算が幾何学的なスケールで行われることを考えると、調査するピクセルが多いほど、時間がかかります...したがって、解決策は、多くのピクセルをスキップして、できるだけ早く画像を見つけようとし、より正確にゾーンインすることです私たちの立場。

エラー関数を変更して、パラメーターとしてどのようにインクリメントするかを受け取り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 倍速く戻ります。xy

stepSizeまた、メイン ループに for を追加しました。

$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 画像検索に変更しました。

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);

そして、それらのメインループのために、サイズ変更された幅と高さでサイズ変更されたアセットを繰り返しました。次に、配列に追加するときに、 and を 2 倍にし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倍のパフォーマンスアップ！

お役に立てれば

于 2013-01-17T15:46:04.343 に答える
2

ImageMagickを使用します。

このページで答えが得られます:大きな画像の中に小さな画像が存在するかどうかを検出/計算するにはどうすればよいですか?

于 2013-01-15T20:08:59.660 に答える