What is the fastest way of edge detection?

Question

I am thinking of implement a image processing based solution for industrial problem.

The image is consists of a Red rectangle. Inside that I will see a matrix of circles. The requirement is to count the number of circles under following constraints. (Real application : Count the number of bottles in a bottle casing. Any missing bottles???)

1. The time taken for the operation should be very low.
2. I need to detect the red rectangle as well. My objective is to count the items in package and there are no mechanism (sensors) to trigger the camera. So camera will need to capture the photos continuously but the program should have a way to discard the unnecessary images.
3. Processing should be realtime.
4. There may be a "noise" in image capturing. You may see ovals instead of circles.

My questions are as follows,

1. What is the best edge detection algorithm that matches with the given scenario?
2. Are there any other mechanisms that I can use other than the edge detection?
3. Is there a big impact between the language I use and the performance of the system?

Answer 1

• For the circles, try the Hough transform.
• other mechanisms: dunno
• Compiled languages will possibly be faster.

Answer 2

1. Sum of colors + convex hull to detect boundary. You need, mostly, 4 corners of a rectangle, and not it's sides?
2. No motion, no second camera, a little choice - lot of math methods against a little input (color histograms, color distribution matrix). Dunno.
3. Java == high memory consumption, Lisp == high brain consumption, C++ == memory/cpu/speed/brain use optimum.

Answer 3

SIFT should have a very good response to circular objects - it is patented, though. GLOHis a similar algorithm, but I do not know if there are any implementations readily available.

Actually, doing some more research, SURF is an improved version of SIFT with quite a few implementations available, check out the links on the wikipedia page.

Answer 4

Surf/Sift = overkill in this case you certainly don't need it.

If you want real time speed (about 20fps+ on a 800x600 image) I recommend using Cuda to implement edge detection using a standard filter scheme like sobel, then implement binarization + image closure to make sure the edges of circles are not segmented apart.

The hardest part will be fitting circles. This is assuming you already got to the step where you have taken edges and made sure they are connected using image closure (morphology.) At this point I would proceed as follows:

1. run blob analysis/connected components to segment out circles that do not touch. If circles can touch the next step will be trickier
2. for each connected componet/blob fit a circle or rectangle using RANSAC which can run in realtime (as opposed to Hough Transform which I believe is very hard to run in real time.)

Step 2 will be much harder if you can not segment the connected components that form circles seperately, so some additional thought should be invested on how to guarantee that condition.

Good luck.

Edit

Having thought about it some more, I feel like RANSAC is ideal for the case where the circle connected components do touch. RANSAC should hypothetically fit the circle to only a part of the connected component (due to its ability to perform well in the case of mostly outlier points.) This means that you could add an extra check to see if the fitted circle encompasses the entire connected component and if it does not then rerun RANSAC on the portion of the connected component that was left out. Rinse and repeat as many times as necessary.

Also I realize that I say circle but you could just as easily fit an ellipse instead of circles using RANSAC.

Also, I'd like to comment that when I say CUDA is a good choice I mean CUDA is a good choice to implement the sobel filter + binirization + image closing on. Connected components and RANSAC are probably best left to the CPU, but you can try pushing them onto CUDA though I don't know how much of an advantage a GPU will give you for those 2 over a CPU.