title: FAST Algorithm : No Corner Detection in Rectangular shapes
body: <p>I am trying to implement my own FAST algorithm in c++ following the OpenCV tutorial. As the algorithm <a href="https://docs.opencv.org/3.0-beta/doc/py_tutorials/py_feature2d/py_fast/py_fast.html" rel="nofollow noreferrer">says</a> : </p>
  
  <blockquote>
    <p>The pixel p is a corner if there exists a set of n contiguous
    pixels in the circle (of 16 pixels) which are all brighter than I_p +
    t, or all darker than I_p − t. (Shown as white dash lines in the above
    image). <strong>n</strong> was chosen to be 12.</p>
    
    <p>A high-speed test was proposed to exclude a large number of
    non-corners. This test examines only the four pixels at 1, 9, 5 and 13
    (First 1 and 9 are tested if they are too brighter or darker. If so,
    then checks 5 and 13). If p is a corner, then at least three of these
    must all be brighter than I_p + t or darker than I_p − t. If neither
    of these is the case, then p cannot be a corner. The full segment test
    criterion can then be applied to the passed candidates by examining
    all pixels in the circle. This detector in itself exhibits high
    performance</p>
  </blockquote>
  
  <p>I compared my FAST output to OpenCV's FAST output with a threshold=100. I realized mine fails to detect all corners :
  <a href="https://i.stack.imgur.com/6Sokv.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/6Sokv.png" alt="enter image description here"></a></p>
  
  <p>When I decrease n to 0 (altough n should be >12 for optimum results), I kind of get the same result (only) with this type of image test but still it doesn't detect corners of rectangular shapes in general: </p>
  
  <p><a href="https://i.stack.imgur.com/xb2mu.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/xb2mu.png" alt="enter image description here"></a></p>
  
  <p>Here is my full code :</p>
  
  <pre><code>#include &lt;opencv2/opencv.hpp&gt;
  #include &lt;stdio.h&gt;
  #include &lt;iostream&gt;
  #include &lt;opencv2/features2d/features2d.hpp&gt;
  
  using namespace std;
  using namespace cv;
  
  #define THRESHOLD 100
  
  
  /*
  ** Compares intensity of pixels 1,5,9,13 of the circle surrounding a pixel at (i,j) of an image with its intensity ip.
  ** If 3 out of 4 satisfy the threshold FAST constraints : bright (i&gt;ip+t) &amp; dark (i&lt;ip-t),
  ** the pixel at (i,j) is considered a possible key point
  */
  bool couldBeKeyPoint(Mat imageIn, int i, int j, int threshold) { 
      uchar ip   = imageIn.at&lt;unsigned char&gt;(i, j); //intensity of the potential key point
      uchar ip9  = imageIn.at&lt;unsigned char&gt;(i, j - 3); //intensity of pixel 1 of the surrounding circle
      uchar ip1  = imageIn.at&lt;unsigned char&gt;(i, j + 3); //intensity of pixel 9 of the surrounding circle 
      uchar ip5  = imageIn.at&lt;unsigned char&gt;(i + 3, j); //intensity of pixel 5 of the surrounding circle
      uchar ip13 = imageIn.at&lt;unsigned char&gt;(i - 3, j); //intensity of pixel 13 of the surrounding circle
  
      //checking FAST bright constraints on these 4 surrounding pixels
      bool b1 = (ip1 &gt;= ip +  threshold);
      bool b9 = (ip9 &gt;= ip +  threshold);
      bool b5 = (ip5 &gt;= ip +  threshold);
      bool b13 = (ip13 &gt;= ip +  threshold);
  
          //cout &lt;&lt; b1+b9+b5+b13 ;
      //at least three of these must all be brighter than I_p + t.
      if (b1+b9+b5+b13 &gt;=3) 
          return true;
  
      bool d1 = (ip1 &lt;= ip - threshold);
      bool d9 = (ip9 &lt;= ip -  threshold);
      bool d5 = (ip5 &lt;= ip - threshold);
      bool d13 = (ip13 &lt;= ip -  threshold);
      //cout &lt;&lt; d1+d9+d5+d13 &lt;&lt; "\n" ;
      //at least three of these must all be darker than I_p − t.
      if (d1+d9+d5+d13 &gt;=3) 
          return true;
  
      return false;
  }
  
  bool isKeyPoint(Mat imageIn, int i, int j, int threshold, int numberPixelsToCheck){
      cout &lt;&lt; "iskeypoint";
      vector&lt;unsigned char&gt; pixelSurroundings;
  
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i, j));//the potential key point
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i, j + 3));//pixel 1
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i + 1, j + 3 3));//pixel 2
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i + 2, j + 2));//pixel 3
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i + 3, j + 1));//pixel 4
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i + 3, j));//pixel 5
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i + 3, j - 1));//pixel 6
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i + 2, j - 2));//pixel 7
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i + 1, j - 3));//pixel 8
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i, j - 3));//pixel 9
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i - 1, j - 3));//pixel 10
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i - 2, j - 2));//pixel 11
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i - 3, j - 1));//pixel 12
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i - 3, j));//pixel 13
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i - 3, j + 1));//pixel 14
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i - 2, j + 2));//pixel 15
      pixelSurroundings.push_back(imageIn.at&lt;unsigned char&gt;(i - 1, j + 3));//pixel 16
  
      if (numberPixelsToCheck &gt; 16){
          numberPixelsToCheck = 12; //The author have used N=12 in the first version of the algorithm
          cout &lt;&lt;  "Error number of surrounding pixels to check should not exceed 16! Value 12 was used instead. " &lt;&lt; std::endl ;
      }
  
      unsigned char ip = pixelSurroundings[0];
      int  brightScore = 0;
      int  darkScore = 0;
      bool d = false,e=false;
      for(int j=1;j&lt;pixelSurroundings.size();j++){
          unsigned char i = pixelSurroundings[j];
          d = (i &gt;= ip + (unsigned char ) threshold);
          e = (i &lt;= ip - (unsigned char ) threshold);
  
          brightScore += d;
          darkScore +=  e;
      }
          cout &lt;&lt; darkScore &lt;&lt; " DARKSCORE \n";
          cout &lt;&lt; brightScore &lt;&lt; " BRIGHTSCORE \n";
      if (darkScore &gt;= numberPixelsToCheck || brightScore &gt;= numberPixelsToCheck){
          //cout &lt;&lt; darkScore &lt;&lt; " DARKSCORE \n";
          //cout &lt;&lt; brightScore &lt;&lt; " BRIGHTSCORE \n";
          return true; //the pixel is a key point
      }
  
      return false;
  }
  
  //renvoit un ensemble de détections
  //inputarray image
  vector&lt;KeyPoint&gt; FAST(Mat imageIn, vector&lt;KeyPoint&gt; keypoints, int threshold){
      if(!imageIn.data )                              // Check for invalid input
      {
          cout &lt;&lt;  "Could not open or find the image" &lt;&lt; std::endl ;
          //return {};
      }
      keypoints.clear();
      int i, j, count =0;
      for (i = 3; i &lt; imageIn.rows - 3; i++)
      {
          for (j = 3; j &lt; imageIn.cols - 3; j++)
          {
              if (couldBeKeyPoint(imageIn, i, j, threshold)){
                  if (isKeyPoint(imageIn, i, j, threshold, 0)){
                          keypoints.push_back(KeyPoint(j, i ,1));
                          count++;
                          cout &lt;&lt; "keypoint found at " &lt;&lt; i &lt;&lt; " " &lt;&lt; j &lt;&lt; "\n";
                      }
              }
          }
      }
      cout &lt;&lt; "NUMBER OF KEYPOINTS :" &lt;&lt; keypoints.size() &lt;&lt; "\n";
      return keypoints;
  }
  
  
  int main(int argc, char** argv){
      vector&lt;KeyPoint&gt; keypointsMyFast;
      vector&lt;KeyPoint&gt; keypointsOpenCvFast;
      Mat src, destMyFast, destOpenCvFast;
      //src= imread(argv[1], CV_LOAD_IMAGE_GRAYSCALE);
      //src= imread(argv[1], CV_8UC3);
      src= imread(argv[1], CV_LOAD_IMAGE_GRAYSCALE);
      imshow( "ORGINAL",src); 
      waitKey(1);
  
      keypointsMyFast = FAST(src, keypointsMyFast,THRESHOLD);
      drawKeypoints(src, keypointsMyFast, destMyFast, Scalar(255,0,0));
      imshow( "MYFAST",destMyFast); 
      waitKey(1);
      FAST(src,keypointsOpenCvFast,THRESHOLD,false);
      cout &lt;&lt; "NUMBER OF open cv KEYPOINTS :" &lt;&lt; keypointsOpenCvFast.size() &lt;&lt; "\n";
      drawKeypoints(src, keypointsOpenCvFast, destOpenCvFast, Scalar(255,0,0));
      imshow( "Display window",destOpenCvFast); 
      waitKey(0);
  
  
  }
  </code></pre>
  
  <p>Any idea on what could cause the algorithm not to detect corners in rectangles?
  Espicially : how to load the image properly using <code>imread</code>? (Changing the second argument gives different results)</p>
  
  <p>Thank you so much</p>