title: Image Matching on Android Game's Board
body: <p>The question comes 1st: I am looking for <strong>FAST</strong> approach to match images.</p>
  
  <p>Now, the use case: I am developing a detector to detect orb on a 6x5 Match-3 game board for android platform. I have an array of the orb icon with <strong>transparent</strong> background, but the orb on the screen (screenshot) has different background color, probably different size too. I have to compare each orb on the screen with my array of icons (69 icons specifically) so it's a 69x30=2070 steps. I tried lazy implementation and group almost similar icon together to reduce the steps but still take a long time (10s at most) for computation. I also tried checking the channel and depth of image, resizing the images to have same size and tweaking the threshold value but still no luck.</p>
  
  <p>I have tried <code>Histogram Matching (seperate channel, grayscale)</code>, <code>Template Matching (CCOEFF, SQDIFF, CCORR)</code>, <code>AKAZE</code>, <code>ORB(unbounded, bounded)</code>, <code>PHash</code> all using OpenCV but histogram matching and PHash give me erroneous result (too much false positive), Template Matching consume 10s+ (considered too slow for user to wait) while AKAZE and ORB give better result than all other methods but still needs 6s+ per try. Is there any other method that can helps me cut down the computation time down to somewhere near 1s and can give better result considering the worst case scenario is 2070 steps?</p>
  
  <p>Referrences that I have read that compares the performances of different feature matching algorithms:
  <a href="https://www.researchgate.net/publication/323561586_A_comparative_analysis_of_SIFT_SURF_KAZE_AKAZE_ORB_and_BRISK" rel="nofollow noreferrer">A comparative analysis of SIFT, SURF, KAZE, AKAZE, ORB, and BRISK</a>. It shows that ORB and BRISK should be averagely better than the other approach compared while AKAZE is moderately good for most cases. I deleted my Histogram comparison code as it is not really helpful but you may find the rest of it below.</p>
  
  <pre><code>Mat source = Utils.loadResource(this, R.drawable.orb_icon, Imgcodecs.CV_LOAD_IMAGE_UNCHANGED);
  Mat tmp = new Mat();
  Bitmap cropped_img = Bitmap.createBitmap(screenshot, x, y, width, height);
  Utils.bitmapToMat(cropped_img, tmp);
  
  //template matching code
  int r_rows = source.rows() - tmp.rows() + 1;
  int r_cols = source.cols() - tmp.cols() + 1;
  Mat result = new Mat();
  
  result.create(r_rows, r_cols, CvType.CV_32F);
  
  Imgproc.matchTemplate(source, tmp, result, Imgproc.TM_CCOEFF_NORMED);
  Core.MinMaxLocResult mmr = Core.minMaxLoc(result);
  double maxVal = mmr.maxVal;
  return maxVal;
  
  //AKAZE
  MatOfKeyPoint kp1 = new MatOfKeyPoint();
  MatOfKeyPoint kp2 = new MatOfKeyPoint();
  Mat desc1 = new Mat();
  Mat desc2 = new Mat();
  AKAZE akaze = AKAZE.create();
  DescriptorMatcher matcher = DescriptorMatcher.create(DescriptorMatcher.BRUTEFORCE_HAMMING);
  akaze.detectAndCompute(source, new Mat(), kp1, desc1);
  akaze.detectAndCompute(tmp, new Mat(), kp2, desc2);
  List&lt;MatOfDMatch&gt; knnMatches = new ArrayList&lt;&gt;();
  matcher.knnMatch(desc1, desc2, knnMatches, 2);
  
  float threshold = 0.7f;
  int count = 0;
  for(int i=0; i&lt;knnMatches.size(); i++) {
      if(knnMatches.get(i).rows() &gt; 1) {
          DMatch[] matches = knnMatches.get(i).toArray();
          if(matches[0].distance &lt; threshold * matches[1].distance) {
              count++;
          }
      }
  }
  
  //ORB    
  ORB orb = ORB.create();
  DescriptorMatcher matcher = DescriptorMatcher.create(DescriptorMatcher.BRUTEFORCE_HAMMING);
  MatOfKeyPoint kp1 = new MatOfKeyPoint();
  MatOfKeyPoint kp2 = new MatOfKeyPoint();
  Mat desc1 = new Mat();
  Mat desc2 = new Mat();
  orb.detectAndCompute(source, new Mat(), kp1, desc1);
  orb.detectAndCompute(tmp, new Mat(), kp2, desc2);
  List&lt;MatOfDMatch&gt; knnMatches = new ArrayList&lt;&gt;();
  matcher.knnMatch(desc1, desc2, knnMatches, 2);
  
  float threshold = 0.8f;
  int count = 0;
  for(int i=0; i&lt;knnMatches.size(); i++) {
      if(knnMatches.get(i).rows() &gt; 1) {
          DMatch[] matches = knnMatches.get(i).toArray();
          if(matches[0].distance &lt; threshold * matches[1].distance) {
              count++;
          }
      }
  }
  
  //PHash
  Mat hash_source = new Mat();
  Mat hash_tmp = new Mat();
  Img_hash.pHash(tmp, hash_tmp);
  Img_hash.pHash(source, hash_source);
  Core.norm(source, tmp, Core.NORM_HAMMING);
  </code></pre>
  
  <p>Edit: As suggested, below is the game board, icon image, and orb screenshot sample.
  <a href="https://i.stack.imgur.com/Cl11G.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Cl11G.png" alt="Game board"></a> </p>
  
  <p>ICON<a href="https://i.stack.imgur.com/RJH79.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/RJH79.png" alt="orb icon"></a> vs orb screenshot <a href="https://i.stack.imgur.com/0KCYE.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/0KCYE.jpg" alt="orb screenshot"></a></p>
  
  <p>Also, you may observe the simulation result of each approach by comparing the result(overlay smaller icon) on top of the orb on board:</p>
  
  <p>Histogram Matching</p>
  
  <p><a href="https://i.stack.imgur.com/rjuq6.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/rjuq6.png" alt="Histogram"></a>,</p>
  
  <p>Template Matching </p>
  
  <p><a href="https://i.stack.imgur.com/KpUOK.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/KpUOK.png" alt="Template Matching"></a> and</p>
  
  <p>AKAZE (similar to ORB) </p>
  
  <p><a href="https://i.stack.imgur.com/1qODX.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/1qODX.png" alt="AKAZE and ORB"></a></p>
  
  <p>After moving the variable initialization out of my comparison function to base class, detect keypoint and PHash of source icon images on class initialization, run detect and compute function in batch using List to reduce individual function call. It still takes up 4s+ for the image matching process. Time consumption is reduced but accuracy is still a major problem. You may observe my heap stack on below.</p>
  
  <p><a href="https://i.stack.imgur.com/qTCf4.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/qTCf4.png" alt="Profiling output"></a></p>