Detecting billiard balls with OpenCV

Question

I'm making an android app that takes an image of a billiards game in progress and detects the positions of the various balls. The image is taken from someone's phone, so of course I don't have a perfect overhead view of the table. Right now I'm using houghcircles to find the balls, and it's doing an ok job, but it seems to miss a few balls here and there, and then there are the false positives.

My biggest problem right now is, how do I cut down on the false positives found outside the table? I'm using an ROI to cut off the top portion of the image because it's mostly wasted space, but I can't make it any smaller or I risk cutting off portions of the table since it's a trapezoidal shape. My current idea is to overlay the guide that the user sees when taking the picture on top of the image, but the problem with that is that I don't know what the resolution of the their cameras would be, and therefore the overlay might cover up the wrong spots. Ideally I think I would want to use houghlines but when I tried it my app crashed from what I believe was a lack of memory. Any ideas?

Here is a link to the results I'm getting:

http://graphiquest.com/cvhoughcircles.html

Here is my code:

    IplImage img = cvLoadImage("/sdcard/DCIM/test/picture"+i+".jpg",1);
    IplImage gray = opencv_core.cvCreateImage( opencv_core.cvSize( img.width(), img.height() ), opencv_core.IPL_DEPTH_8U, 1);

    cvCvtColor(img, gray, opencv_imgproc.CV_RGB2GRAY );
    cvSetImageROI(gray, cvRect(0, (int)(img.height()*.15), (int)img.width(), (int)(img.height()-(img.height()*.20))));


    cvSmooth(gray,gray,opencv_imgproc.CV_GAUSSIAN,9,9,2,2);

    Pointer circles = CvMemStorage.create();        
    CvSeq seq = cvHoughCircles(gray, circles, CV_HOUGH_GRADIENT, 2.5d, (double)gray.height()/30, 70d, 100d, 0, 80);

    for(int j=0; j<seq.total(); j++){
        CvPoint3D32f point = new CvPoint3D32f(cvGetSeqElem(seq, j));

        float xyr[] = {point.x(),point.y(),point.z()};
        CvPoint center = new CvPoint(Math.round(xyr[0]), Math.round(xyr[1]));

        int radius = Math.round(xyr[2]);
        cvCircle(gray, center, 3, CvScalar.GREEN, -1, 8, 0);
        cvCircle(gray, center, radius, CvScalar.BLUE, 3, 8, 0);
    }
    String path = "/sdcard/DCIM/test/";
    File photo=new File(path, "picture"+i+"_2.jpg");

    if (photo.exists()) 
    {
        photo.delete();
    }
   cvSaveImage("/sdcard/DCIM/test/picture"+i+"_2.jpg", gray);

Answer 1

I've thought about working on this problem, too, since I play pool and snooker.

A few points:

1. Judging from the Hough circle fits, it looks like you're not filtering the edge points, or your threshold for edge strength isn't high enough. Are you simply using a binary indicator for edge points, or are you selecting edge points based on edge strength?
2. Can you work in RGB space? That'd help with detecting the table bed, the rails, and also in identifying the balls. A blue blob on the table bed could be the 2-ball, the 10-ball, or maybe a hunk of chalk.
3. In your parameter space, you should be able to limit the search for circles of a very limited radius. This would be helped in part if...
4. Detect the table surface and the rails. A Stroke Width Transform could help you find the rails, especially if you search in a color plane (green) in which the rails will have high contrast. You can also use the six pockets (or at least three pockets) to help identify the pose (position and orientation) of the table.
5. Once the rails are detected, you can use an affine transform to correct for perspective distortion. You'll need to do this anyway to place the balls with any sort of accuracy, especially if you want the ball placement to satisfy a serious pool player such as someone who plays One Pocket or Straight Pool. Once you have the affine transform, you can set fairly tight tolerances for radius in your Hough parameter space.
6. Once you've detected the table bed, you could perform an initial segmentation (that is, region labeling or blob finding) and search only for blobs of a certain area and roundness.
7. A strong, even, diffuse overhead light could help eliminate shadows.
8. You can help filter edge points by accepting (or at least favoring) edge points that have gradients that are pointed towards other edge points with parallel gradients. If a local collection of edge point pairs "point" at each other via their edge gradients, then they are good candidates for detection.
9. Once you've detected a candidate ball, perform further processing to accept/reject. A ball should be a relatively uniform hue (cue ball, 1 - 8, or a stripe viewed from the proper angle), or it should have a detectable color stripe and white. The ball surface will not be highly textured like the wood grain of the table.
10. Have an option that the user take two pictures from slightly different angles. You then have two chances to find balls, and could conceivably solve the correspondence problem of matching the tables and balls in the two images to help locate the balls in the 2D space of the table bed.
11. Consider having a second algorithm such as normalized cross-correlation (simple template matching) to help identify balls or at least likely ball locations.
12. Insist that the center point of the image be located somewhere within the table bed. This can help you identifying the positions of the rails since you can then search radially outward for the edges of the rails, and once four (or even just three) rails are found you can reject edge points at radial distances beyond them.

Good luck! It's a fun problem.

EDIT: I was reading another StackOverflow post and read about this paper. The paper which will give you a much more thorough introduction to the technique I suggested to filter edge points (item 8).

"Fast Circle Detection Using Gradient Pair Vectors" by Rad, Faez, and Qaragozlou http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.9956

I haven't implemented their algorithm myself yet, but it looks promising. Here's the post where the paper was mentioned:

Three Dimensional Hough Space

Answer 2

There are some very helpful constraints you could apply. In addition to doing a rectangular region of interest, you should mask your results with the actual trapezoidal shape of the pool table. Use the color information of the image to find the pool table region. You know that the pool table is a solid color. It doesn't have to be green - you can use some histogram techniques in HSV color space to find the most prevalent color in the image, perhaps favoring pixels toward the center. It's very likely to detect the color of the pool table. Select pixels matching this color, perform morphological operations to remove noise, and then you can treat the mask as a contour, and find its convexHull. Fill the hull to remove the holes created by the pool balls.

What I've said so far should suggest a different approach than Hough circles. Hough circles is probably not working too well since the billiard balls are not evenly illuminated. So, another way to find billiard balls is to subtract the pool table color mask from its convexHull. You'll be left with the areas of the table that are obscured by balls.