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);
}