Detect Lines, circles and arcs in simple black and white drawing image

Question

I am trying to detect lines, circles and arcs in a simple black and white drawing image file (jpg or bmp format)

I posted a similar question 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.

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.

The algorithm is very simple:
1. I scan the image from top left, row-wise.
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.

for ( int i = 0; i < myImage.height(); i++ ) {

        for ( int j = 0; j < 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 < myImage.width() && qGray( myImage.pixel( xRight, i ) ) == 0 ) {
                    myImage.setPixel( xRight, i, value );
                    xRight++;
                }
                while ( y < myImage.height() && xLeft >= 0 &&
                        qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                    if ( xLeft - 1 >= 0 &&
                         qGray( myImage.pixel( xLeft - 1, y ) ) == 0 ) {
                        while ( xLeft >= 0 &&
                                qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                            myImage.setPixel( xLeft, y, value );
                            xLeft--;
                        }
                        y++;
                    } else if ( y+1 < myImage.height() &&
                                qGray( myImage.pixel( xLeft, y + 1 ) ) == 0 ) {
                        while ( y < myImage.height() &&
                                qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                            myImage.setPixel( xLeft, y, value );
                            y++;
                        }
                        xLeft--;
                    } else {
                        xLeft--;
                        y++;
                    }
                }
                y--;
                xLeft++;
                if ( y > i && ( y - i > MIN_PIXELS_LINE ||
                                xRight-1 - xLeft > MIN_PIXELS_LINE )
                     ) {
                    drawFile.Line( fileName2, xRight-1, myImage.height() - i, xLeft,
                                   myImage.height() - y, 0 );
                    horiLineDrawn = true;
                }

                y = i + 1;
                while ( y < myImage.height() && xRight < myImage.width() &&
                        qGray( myImage.pixel( xRight, y ) ) == 0 ) {


                    if ( xRight + 1 < myImage.width() &&
                         qGray( myImage.pixel( xRight + 1, y ) ) == 0 ) {
                        while ( xRight < myImage.width() &&
                                qGray( myImage.pixel( xRight, y ) ) == 0 ) {
                            myImage.setPixel( xRight, y, value );
                            xRight++;
                        }
                        y++;
                    } else if ( y+1 < myImage.height() &&
                                qGray( myImage.pixel( xRight, y + 1 ) ) == 0 ) {
                        while ( y < myImage.height() &&
                                qGray( myImage.pixel( xRight, y ) ) == 0 ) {
                            myImage.setPixel( xRight, y, value );
                            y++;
                        }
                        xRight++;
                    } else {
                        xRight++;
                        y++;
                    }
                }
                y--;
                xRight--;
                if ( y - i > MIN_PIXELS_LINE || xRight - j > MIN_PIXELS_LINE
                     && !horiLineDrawn) {
                    drawFile.Line( fileName2, j, myImage.height() - i, xRight,
                                   myImage.height() - y, 0 );
                    horiLineDrawn = true;
                }

                y = i + 1;
                while ( y < myImage.height() && qGray( myImage.pixel( j, y ) ) == 0 ) {
                    myImage.setPixel( j, y, value );
                    y++;
                }
                xLeft = j - 1;
                xRight = j + 1;
                if ( xLeft >= 0 && y < myImage.height() &&
                     qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                    while ( xLeft >= 0 && y < myImage.height() &&
                            qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                        while ( y < myImage.height() &&
                                qGray( myImage.pixel( xLeft, y ) ) == 0 ) {
                            myImage.setPixel( xLeft, y, value );
                            y++;
                        }
                        xLeft--;
                    }
                    xLeft++;
                    y--;
                    if ( y - i > MIN_PIXELS_LINE || j - xLeft > MIN_PIXELS_LINE )
                        drawFile.Line( fileName2, j, myImage.height() - i, xLeft,
                                       myImage.height() - y, 0 );
                } else if ( xRight < myImage.width() && y < myImage.height() &&
                            qGray( myImage.pixel( xRight, y ) ) == 0 ) {
                       while ( xRight < myImage.width() && y < myImage.height() &&
                               qGray( myImage.pixel( xRight, y ) ) == 0 ) {
                           while ( y < myImage.height() &&
                                   qGray( myImage.pixel( xRight, y ) ) == 0 ) {
                               myImage.setPixel( xRight, y, value );
                               y++;
                           }
                           xRight++;
                       }
                       xRight--;
                       y--;
                       if ( y - i > MIN_PIXELS_LINE || xRight - j > MIN_PIXELS_LINE )
                           drawFile.Line( fileName2, j, myImage.height() - i, xRight,
                                          myImage.height() - y, 0 );
                } else {
                    y--;
                    if ( y - i > MIN_PIXELS_LINE )
                        drawFile.Line( fileName2, j, myImage.height() - i, j,
                                       myImage.height() - y, 0 );
                }


            }
        }
    }

This works fine. For example:

Input image:

Output image:

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.

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.

Answer 1

Out of curiosity, are all of your images binary with thin lines? Are these scanned hand drawings or pixel art? I ask because you will run into trouble using JPEG compression, it is notoriously bad on line art. You should make sure you are always using a lossless compression with line drawings.

If there is noise and other artifacts in the image, it is highly unlikely that any edge detector is going to be perfect. If I was attacking this problem I would focus on pre-processing the data to make it have stronger lines so that the line detection process is easier. This could be done by pre-thresholding the image, possibly doing some morphological clean-up, or even sharpening the image.

Also, if your images are already binary (or could be made binary with a simple threshold), the Canny edge detection (or really any grayscale edge detector) might not be the best tool to use. You would be better off making your imagery binary and using something like findContours to identify the edges.

If you are looking for something slightly different than the Hough transform for identifying shapes, you could try using a model fitting algorithm such as RANSAC.