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

AHH - YOU HAVE NOW TOLD US THE BOTTLES ARE IN FIXED LOCATIONS!

IT IS AN INCREDIBLY EASIER PROBLEM.

All you have to do is look at each of the 12 spots and see if there is a black area there or not. Nothing could be easier.

You do not have to do any edge or shape detection AT ALL.

It's that easy.

You then pointed out that the box might be rotatated, things could be jiggled. That the box might be rotated a little (or even a lot, 0 to 360 each time) is very easily dealt with. The fact that the bottles are in "slots" (even if jiggled) massively changes the nature of the problem. You're main problem (which is easy) is waiting until each new red square (crate) is centered under the camera. I just realised you meant "matrix" literally and specifically in the sentence in your original questions. That changes everything totally, compared to finding a disordered jumble of circles. Finding whether or not a blob is "on" at one of 12 points, is a wildly different problem to "identifying circles in an image". Perhaps you could post an image to wrap up the question.

---

Finally I believe Kenny below has identified the best solution: blob analysis.

---

"Count the number of bottles in a bottle casing"...

Do the individual bottles sit in "slots"? ie, there are 4x3 = 12 holes, one for each bottle.

In other words, you "only" have to determine if there is, or is not, a bottle in each of the 12 holes.

Is that correct?

If so, your problem is incredibly easier than the more general problem of a pile of bottles "anywhere".

Quite simply, where do we see the bottles from? The top, sides, bottom, or? Do we always see the tops/bottoms, or are they mixed (ie, packed top-to-tail). These issues make huge, huge differences.

Answer 2

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.

Answer 3

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

Answer 4

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 5

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 6

If the contrast is good, blob analysis is the algorithm for the job.