CODEWITHSUNDEEP
algorithmperformanceimageimage-processingtheory
Karl
Karl

Reputation: 5733

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?

Upvotes: 3

Views: 576

Answers (4)

JP19
JP19

Reputation:

Step 1: Thresholding - reduce the image to 1 bit (black or white) if the general image set permits it. [For the type of example you cite, my guess is thresholding would work nicely - leaving enough details to find objects].

Step 2: Optionally do some smoothing/noise removal.

Step 3: Use some clustering approach to gather the foreground objects.

Step 4: Use an appropriate heuristic to identify the objects.

The parameters in steps 1/2 will depend a lot on the type of images as well as experimentation/observation. 3 is usually straightforward if you have worked out 1/2 correctly. 4 will depend very much on the problem (for example, in your case identifying stars - which would depend on what is the actual shape of the stars expected in the images).

Upvotes: 1

Unreason
Unreason

Reputation: 12704

As you list a property that the shapes are not overlapping then I assume an efficient algorithm would be able to

  • cut out all the shapes by scanning the image in some way (I can imagine relatively efficient and simple algorithm for convex shapes)
  • when you are left with cut out shapes you could use cross relation misha mentioned

You should describe the problem a bit better

  • can the shapes be rotated or scaled (or some other transform?)
  • is the background uniform colour
  • are the shapes uniform colour
  • are the shapes filled

Depending on the answer on the above questions you might have more less or more simple solutions.

Also, maybe this article might be interesting.

If the shapes are very regular maybe turning them into vectors could fit your needs nicely, but it might be an overkill, really depends what you want to do later.

Upvotes: 1

bjoernz
bjoernz

Reputation: 3852

If the shapes are easy to segment from the background, you might be able to compute distinguishing shape/color descriptors. Depending on your problem you could choose descriptors that are invariant to scale, translation or rotation (e.g. compactness, if it is unique to each shape). I do not know if this will be faster, though.

If you already know the exact shape and have an idea about the size, you might want to have a look at the Generalized Hough Transform, which is basically a formalized description of your "brute force algorithm"

Upvotes: 2

mpenkov
mpenkov

Reputation: 21898

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.

Upvotes: 5

Related Questions