Circle Detection - Reliability Assessment

Question

I'm writing a OpenCV-powered C++ application. The application basically analyzed handwritten images and recognizes symbols (do not expect alphanumerical symbols, it is a deaf-specific writing system).

My input images contain symbols with very different shapes, but I'd like to focus on circles. The following picture illustrates a selection of circle-shaped symbols that I'm currently dealing with (after noise reduction and binarization).

To recognize circle-shaped symbols, I use the Hough Circle Transform, which does its job pretty well. The transform is applied after the application of a median filter to reduce noise, and of a threshold to binarize the image.

My problem is that sometimes, the Hough Circle Transform detects circles where there is no circle (see the following picture).

Now, I've been looking for some "reliability assessment" for the detected circles. But I had little luck. Is there any way to see if the detected circle is related to a real circle?

I am beginning to think about some solutions on my own, but maybe someone figured out something smarter, i could:

• Evaluate the Husdorff distance of each point of the detected circle with the actual symbol, and use it as a measurement of some kind
• Using the coordinates of the detected center, i could split the image in 4 sectors (see image below) and see if the Hough Circle Transform detects something in each (or most) sector.

Remember: I am dealing with handwritten (i.e. very roughly drawn) symbols.

Answer 1

I solved the problem designing a function which is based on the idea of @Abhishek.

Here is the pseudocode, and its C++ implementation.

checkCircleSectors(imagePoints, circle, circleExpansionFactor, theta, acceptThreshold)

  Divide the circle in n sectors, using angle theta (so n = 2*PI /theta)

  (Optional) Slightly expand or reduce the radius of the circle by circleExpansionFactor, if needed.

  for each point "curPoint" within the image (imagePoints){

    if the distance between curPoint and center.circle is lesser/equal to circle.radius{

      let "curAngle" be the angle between circle.center and curPoint, calculated using curPoint as origin.
      let "curSector" be the sector of circle which contains curAngle
          upgrade the ranking of curSector by one.
    }
  }

  if there are more than acceptThreshold sectors whose rank is zero
    the circle is not acceptable
  else
    the circle is acceptable

Notes:

I found it very useful to slightly expand the radius of the circle (I use a 1.25 expand factor) beacause sometimes (expecially in the case of handwritten circles) the detection could be inaccurate.

Here is my C++ implementation of the concept:

boolean ImgCheck::checkCircleSectors(vector<Point> tgtPoints, Point tgtCenter, int tgtRadius, float tgtRadiusExp, int tgtStep, int tgtThreshold){

  vector<int> circleData( 360 / tgtStep, 0);
  int detectionReliability = 0;

  tgtRadius = tgtRadius * tgtRadiusExp;

  /* Analyze the sectors.                               */
  for(size_t i=0; i<tgtPoints.size(); i++){

    Point curCartesianPoint = getCartesianCoordinates(tgtCenter, tgtPoints[i]);

    float angleRad = arctangent2(curCartesianPoint);
    int   angleDeg = angleRad * (180/M_PI);

    if(distance(tgtPoints[i],tgtCenter) <= tgtRadius){
      circleData.at(angleDeg / tgtStep) += 1;
    }

  }

  /* Count the postive-ranked sectors.                 */
  for(size_t i = 0; i< circleData.size(); i++){
    if(circleData[i] > 0)
      detectionReliability += 100.0/(360/tgtStep);
  }

  if(detectionReliability >= tgtThreshold)
    return true;
  }
  return false;
}

Notes:

My preference for the last three parameters is the following:

• tgtRadiusExp = 1.25 (radius expanded by a quarter of its length)
• tgtStep = 5 (theta = 5 degrees -> circle divided in 72 sectors)
• tgtTreshold = 75 (at least 75 non-zero sectors required to pass the test)

The function getCartesianCoordinates (source code below) converts OpenCV coordinates in cartesian coordinates. It takes two arguments:

• Point tgtOrigin are the openCV coordinates of the point which must be used as origin.
• Point tgtPoint are the openCV coordinates of another point.

The function returns the coordinates of tgtPoint, converted using tgtOrigin as origin.

Point getCartesianCoordinates(Point tgtOrigin, Point tgtPoint){

  Point resPoint = tgtPoint - tgtOrigin;

  return Point(resPoint.x, -resPoint.y);
}

Answer 2

I think some form of evaluating the distance of your circle points to the symbol is the way to go - I doubt that there are more sophisticated alternatives that are also practical.

There are, however, more and less sophisticated and efficient ways to do the distance evaluation.

As your symbol images are already binarized, I would recommend the following: Compute the Distance Transform on the binary image; there are efficient algorithms for doing this. Then you only need to sample the distance image at the circle points and sum up the distances (probably normalized with respect to the circle circumference, to get some scale invariance) to get an error score.

This fails if you happen to have a lot of small clutter in your images, but those you posted look pretty clean.

Answer 3

Having spent some time hand-coding ellipse detectors, I have followed a similar path with regard to detecting "ellipse-ness" (goodness of fit is a guide). Ultimately, though, hand-coding such detectors is a brittle business, because your input is really not so well defined; you will probably find that human readers will successfully recognise many "circles" that will fail any reasonable mathematical definition of "circularity". Accept therefore that the actual operating definition of your character is not the equation of a circle.

I suggest that you consider a completely different approach; instead of hand-coding detectors, train them. This is the state-of-the-art approach to hand-writing recognition, and you can take your pick of popular well-proven algorithms (the MNIST dataset of hand-written arabic numerals is a popular bench-mark). Instead of coding detectors, build yourself a really decent training set; you won't have to hand-code detectors for each character, and you'll build something really robust and well-tested that can cope with very sloppy handwriting, smudges, scribbles, etc. (such as you can find in the MNIST dataset).