Search code examples
algorithmperformanceimageimage-processingtheory

Fastest method to search for a specified item on an image?

Imagine we have a simple 2D drawing, filled it with lots of non-overlapping circles and only a few stars.

If we are to find all the stars among all these circles, I can think of very few methods. Brute force is one of them. Another one is possibly reduce the image size (to the optimal point where you can still distinguish the objects apart) and then apply brute force and map to the original image. The drawback of brute force is of course, it is very time consuming. I am looking for faster methods, possibly the fastest one.

What is the fastest image processing method to search for the specified item on a simple 2D image?

Solution

  • One typical way of looking for an object in an image is through cross correlation. Basically, you look for the position where the cross-correlation between a mask (the object you're attempting to find) and the image is the highest. That position is the likely location of the object you're trying to find.

    For the sake of simplicity, I will refer to the object you're attempting to find as a star, but in general it can be any shape.

    Some problems with the above approach:

    • The size of the mask has to match the size of the star. If you don't know the size of the star, then you will have to try different size masks. Image pyramids are more effective than just iteratively trying different size masks, but still require extra effort.
    • Similarly, the orientations of the mask and the star have to match. If they don't, the cross-correlation won't work.

    For these reasons, the more you know about your problem, the simpler it becomes. This is the reason why people have asked you for more information in the comments. A general purpose solution doesn't really exist, to the best of my knowledge. Maybe someone more knowledgeable can correct me on this.

    As you've mentioned, reducing the size of the image will help you reduce the computational time of your approach. In my opinion, it's hardly the core element of a solution -- it's just an optional optimization step.