title: Detect Lines, circles and arcs in simple black and white drawing image
body: <p>I am trying to detect lines, circles and arcs in a simple black and white drawing image file (jpg or bmp format)</p>
  
  <p>I posted a <a href="https://stackoverflow.com/questions/19765074/searching-jpeg-bmp-pdf-image-for-straight-lines-circles-and-text">similar question</a> before, in which OpenCV library was suggested. It is a good library, however, it is not accurate enough for my purpose. More specifically, the Canny detection algorithm somehow does not work perfectly for my images.</p>
  
  <p>Hence I am trying to implement the algorithm myself using QImage. I have managed to successfully implement it for straight lines. The code in Qt C++ is as follows. It is a very cluttered code, but I am just giving it for reference.</p>
  
  <p>The algorithm is very simple:<br>
  1. I scan the image from top left, row-wise.<br>
  2. Whenever I encounter a black pixel, I scan towards its right, left bottom to check whether it is a corner of a line segment.</p>
  
  <pre><code>for ( int i = 0; i &lt; myImage.height(); i++ ) {
  
          for ( int j = 0; j &lt; myImage.width(); j++ ) {
              if ( qGray( myImage.pixel( j, i ) ) == 0 ) {
  
                  myImage.setPixel( j, i, value );
                  bool horiLineDrawn = false;
                  int xRight = j+1, xLeft = j-1;
                  int y = i+1;
                  while ( xRight &lt; myImage.width() &amp;&amp; qGray( myImage.pixel( xRight, i ) ) == 0 ) {
                      myImage.setPixel( xRight, i, value );
                      xRight++;
                  }
                  while ( y &lt; myImage.height() &amp;&amp; xLeft &gt;= 0 &amp;&amp;
                          qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                      if ( xLeft - 1 &gt;= 0 &amp;&amp;
                           qGray( myImage.pixel( xLeft - 1, y ) ) == 0 ) {
                          while ( xLeft &gt;= 0 &amp;&amp;
                                  qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                              myImage.setPixel( xLeft, y, value );
                              xLeft--;
                          }
                          y++;
                      } else if ( y+1 &lt; myImage.height() &amp;&amp;
                                  qGray( myImage.pixel( xLeft, y + 1 ) ) == 0 ) {
                          while ( y &lt; myImage.height() &amp;&amp;
                                  qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                              myImage.setPixel( xLeft, y, value );
                              y++;
                          }
                          xLeft--;
                      } else {
                          xLeft--;
                          y++;
                      }
                  }
                  y--;
                  xLeft++;
                  if ( y &gt; i &amp;&amp; ( y - i &gt; MIN_PIXELS_LINE ||
                                  xRight-1 - xLeft &gt; MIN_PIXELS_LINE )
                       ) {
                      drawFile.Line( fileName2, xRight-1, myImage.height() - i, xLeft,
                                     myImage.height() - y, 0 );
                      horiLineDrawn = true;
                  }
  
                  y = i + 1;
                  while ( y &lt; myImage.height() &amp;&amp; xRight &lt; myImage.width() &amp;&amp;
                          qGray( myImage.pixel( xRight, y ) ) == 0 ) {
  
  
                      if ( xRight + 1 &lt; myImage.width() &amp;&amp;
                           qGray( myImage.pixel( xRight + 1, y ) ) == 0 ) {
                          while ( xRight &lt; myImage.width() &amp;&amp;
                                  qGray( myImage.pixel( xRight, y ) ) == 0 ) {
                              myImage.setPixel( xRight, y, value );
                              xRight++;
                          }
                          y++;
                      } else if ( y+1 &lt; myImage.height() &amp;&amp;
                                  qGray( myImage.pixel( xRight, y + 1 ) ) == 0 ) {
                          while ( y &lt; myImage.height() &amp;&amp;
                                  qGray( myImage.pixel( xRight, y ) ) == 0 ) {
                              myImage.setPixel( xRight, y, value );
                              y++;
                          }
                          xRight++;
                      } else {
                          xRight++;
                          y++;
                      }
                  }
                  y--;
                  xRight--;
                  if ( y - i &gt; MIN_PIXELS_LINE || xRight - j &gt; MIN_PIXELS_LINE
                       &amp;&amp; !horiLineDrawn) {
                      drawFile.Line( fileName2, j, myImage.height() - i, xRight,
                                     myImage.height() - y, 0 );
                      horiLineDrawn = true;
                  }
  
                  y = i + 1;
                  while ( y &lt; myImage.height() &amp;&amp; qGray( myImage.pixel( j, y ) ) == 0 ) {
                      myImage.setPixel( j, y, value );
                      y++;
                  }
                  xLeft = j - 1;
                  xRight = j + 1;
                  if ( xLeft &gt;= 0 &amp;&amp; y &lt; myImage.height() &amp;&amp;
                       qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                      while ( xLeft &gt;= 0 &amp;&amp; y &lt; myImage.height() &amp;&amp;
                              qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                          while ( y &lt; myImage.height() &amp;&amp;
                                  qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                              myImage.setPixel( xLeft, y, value );
                              y++;
                          }
                          xLeft--;
                      }
                      xLeft++;
                      y--;
                      if ( y - i &gt; MIN_PIXELS_LINE || j - xLeft &gt; MIN_PIXELS_LINE )
                          drawFile.Line( fileName2, j, myImage.height() - i, xLeft,
                                         myImage.height() - y, 0 );
                  } else if ( xRight &lt; myImage.width() &amp;&amp; y &lt; myImage.height() &amp;&amp;
                              qGray( myImage.pixel( xRight, y ) ) == 0 ) {
                         while ( xRight &lt; myImage.width() &amp;&amp; y &lt; myImage.height() &amp;&amp;
                                 qGray( myImage.pixel( xRight, y ) ) == 0 ) {
                             while ( y &lt; myImage.height() &amp;&amp;
                                     qGray( myImage.pixel( xRight, y ) ) == 0 ) {
                                 myImage.setPixel( xRight, y, value );
                                 y++;
                             }
                             xRight++;
                         }
                         xRight--;
                         y--;
                         if ( y - i &gt; MIN_PIXELS_LINE || xRight - j &gt; MIN_PIXELS_LINE )
                             drawFile.Line( fileName2, j, myImage.height() - i, xRight,
                                            myImage.height() - y, 0 );
                  } else {
                      y--;
                      if ( y - i &gt; MIN_PIXELS_LINE )
                          drawFile.Line( fileName2, j, myImage.height() - i, j,
                                         myImage.height() - y, 0 );
                  }
  
  
              }
          }
      }
  </code></pre>
  
  <p>This works fine. For example:</p>
  
  <p>Input image:<br>
  <img src="https://i.stack.imgur.com/BnQ1d.png" alt="enter image description here">  </p>
  
  <p>Output image:<br>
  <img src="https://i.stack.imgur.com/qLT7D.png" alt="enter image description here"></p>
  
  <p><strong>Can anyone suggest how I can implement similar or better algorithm for circles and arcs? Efficiency is not a problem since my image size shall be maximum 1000 by 1000 pixels.
  However, accuracy is critical.</strong></p>
  
  <p>EDIT: There may be a lot of bugs in my present implementation of straight lines, like I haven't tested it for intersecting lines etc. But I think I shall be able to manage those complications.</p>