title: Way to find an image inside another image in PHP/GD?
body: <p>I need a way to find the location of an image inside another image in PHP/gd. 
  For example, locate this image:</p>
  
  <p><a href="https://i.stack.imgur.com/BaQ5k.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/BaQ5k.png" alt="enter image description here"></a> </p>
  
  <p>inside this image:</p>
  
  <p><a href="https://i.stack.imgur.com/fzl4G.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/fzl4G.png" alt="so_big.png"></a></p>
  
  <p>I tried to make a function myself to do this, and I WAS successful, but it's very slow, it takes over 50 seconds at 100% CPU for me with the example pictures above, and I'm not sure how to optimize it (if possible) further. So is there some way to do this faster? Preferably, much faster? (For instance Auto Hotkey can do the same operation in &lt;2 seconds on the same computer with this function <a href="https://autohotkey.com/docs/commands/ImageSearch.htm" rel="nofollow noreferrer">https://autohotkey.com/docs/commands/ImageSearch.htm</a> ) </p>
  
  <p><strong>Edit:</strong> I figured I could simply create a copy of the small image by the big image's color indexes with imagecolorexact, this allows 2 things, detect when the small image has a pixel which doesn't exist in the big image, making a match impossible, AND comparing an <code>int(x)===int(x)</code> is much faster than comparing <code>array("red"=&gt;x,"green"=&gt;x,"blue"=&gt;x)==array("red"=&gt;x,"green"=&gt;x,"blue"=&gt;x)</code> - it looks like the speed nearly tripled this way, using 30 seconds before, using 9 seconds now. Still <em>nowhere near the speed</em> of AutoHotKey's though :/</p>
  
  <pre><code>$big = imagecreatefrompng ( 'so_big.png' );
  $small = imagecreatefrompng ( 'so_small.png' );
  bench ( __LINE__ );
  var_dump ( FindImageInImageV2 ( $big, $small) );
  bench ( __LINE__ );
  die ( "DONED" );
  function FindImageInImageV2($big, $small, int $max = PHP_INT_MAX,bool $center=true): array {
      assert ( is_resource ( $small ) );
      assert ( is_resource ( $big ) );
      $ret = array ();
      //think2 ( $big, 'FindImageInImage/big' );
      //think2 ( $small, 'FindImageInImage/small' );
      $smallx = imagesx ( $small );
      $smally = imagesy ( $small );
      $bigx = imagesx ( $big );
      $bigy = imagesy ( $big );
      assert ( $bigx &gt;= $smallx );
      if ($bigx &lt; $smallx) {
          return $ret; // match is impossible
      }
      assert ( $bigy &gt;= $smally );
      if ($bigy &lt; $smally) {
          return $ret; // match is impossible
      }
      $smallcolors = imagecolorstotal ( $small );
      $bigcolors = imagecolorstotal ( $big );
      // assert($smallcolors&lt;$bigcolors);
      if ($smallcolors &gt; $bigcolors) {
          return $ret; // too many colors, match is impossible.
      }
      $smallImageAsColors = array ();
      for($x = 0; $x &lt; $smallx; ++ $x) {
          $smallImageAsColors [$x] = array ();
          for($y = 0; $y &lt; $smally; ++ $y) {
              $tmp = imagecolorsforindex ( $small, imagecolorat ( $small, $x, $y ) );
              //unset ( $tmp ['alpha'] );
              $tmp=imagecolorexact ( $big, $tmp['red'], $tmp['green'],$tmp['blue']);
              if($tmp===-1){
                  //small has a color that does not exist in big, match is impossible
                  return $ret;
              }
              $smallImageAsColors [$x] [/*$y*/] = $tmp;
          }
      }
      unset ( $x, $y, $tmp );
      for($x = 0; $x &lt; $bigx; ++ $x) {
          if ($bigx &lt; ($x + $smallx)) {//&lt;&lt; todo: can be optimized away.
              break; // too close to the end, no result possible..
          }
          for($y = 0; $y &lt; $bigy; ++ $y) {
              if ($bigy &lt; ($y + $smally)) {//&lt;&lt; todo: can be optimized away.
                  continue; // too close to the bottom, no result possible for this $y..
              }
              //$matchFound = true;
              for($i = 0; $i &lt; $smallx; ++ $i) {
                  for($ii = 0; $ii &lt; $smally; ++ $ii) {
                      // yelp
                      if($smallImageAsColors [$i][$ii]!==imagecolorat($big,$x+$i,$y+$ii))
                      {
                          //$matchFound=false;
                          //goto outofmatching;//i can micro optimize the jumps more actually... but should i?
                          //goto uglyoptimize;
                          continue 3;
                      }
                  }
              }
              //outofmatching:
              //if ($matchFound) {
                  $ret [] = array (
                          'x' =&gt; ($center?$x+((int)floor($smallx/2)):$x),
                          'y' =&gt; ($center?$y+((int)floor($smally/2)):$y)
                  );
                  if (count ( $ret ) &gt;= $max) {
                      //goto done;
                      return $ret;
                  }
              //}
              //uglyoptimize:
          }
      }
      //done:
      return $ret;
  }
  </code></pre>