Forums

image in image search

Started by Andreas September 3, 2003
Hello!

I am trying to implement an algorithm which is supposed to find the best
match of a given (small) image in a larger image.

I have thought about a few (naive) ways of implementation, and recently have
been pointed at FT and wavelets, which - if applicable - sound rather
interesting for my problem.

So I was wondering whether you can give me any tips on whether using those
transformations makes sense, and also - if you know about these matters as
well - how well such an algorithm can be parallelized (as I am going to
implement the algorithm on a few FPGAs), or if there may be approaches which
are better suited.

Best regards and thx for any answers,

Andreas


Andreas wrote:
> > Hello! > > I am trying to implement an algorithm which is supposed to find the best > match of a given (small) image in a larger image. > > I have thought about a few (naive) ways of implementation, and recently have > been pointed at FT and wavelets, which - if applicable - sound rather > interesting for my problem. > > So I was wondering whether you can give me any tips on whether using those > transformations makes sense, and also - if you know about these matters as > well - how well such an algorithm can be parallelized (as I am going to > implement the algorithm on a few FPGAs), or if there may be approaches which > are better suited. > > Best regards and thx for any answers, > > Andreas
I don't know what you mean by "best match of a given (small) image in a larger image." If that refers to a small image that is part of a larger one, what does it match? If "in" should have been "to" so that the phrase reads "best match of a given (small) image to a larger image", then there is a scaling problem that's not trivial, but depending on the nature of the images, reducing them to the same scale might be simple enough. It it is, you may get further ideas from Chapter 24 of Steven W. Smith's book, "The Scientist and Engineer's Guide to Digital Signal Processing", available on line at http://www.dspguide.com/. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
"Andreas" <reiff(remove_me)@amo.de> wrote in message
news:<bj4poj$rlv$1@nets3.rz.RWTH-Aachen.DE>...
> Hello! > > I am trying to implement an algorithm which is supposed to find the best > match of a given (small) image in a larger image. > > I have thought about a few (naive) ways of implementation, and recently have > been pointed at FT and wavelets, which - if applicable - sound rather > interesting for my problem. > > So I was wondering whether you can give me any tips on whether using those > transformations makes sense, and also - if you know about these matters as > well - how well such an algorithm can be parallelized (as I am going to > implement the algorithm on a few FPGAs), or if there may be approaches which > are better suited. > > Best regards and thx for any answers, > > Andreas
FT and wavelet algorithms can easily be run in parallel on successive lines of a scanned image. Some of the other algorithms used in further compressing the image might be less well adapted to parallel processing but they usually consume a lesser portion of your compute budget. Regards, Ken Asbury
First of all, thanks for the answers!



I am trying to find an image in another one (along the lines of a house in a
map

Photographed from the air). Scaling shouldnt be too big a problem, as both
images

Will be very similar in resolution.

So - I am trying to find a position in the larger image, where the smaller
is with

A high probability.



Still, I thought a transformation would make the search more robust against
scaling

And/or rotation errors, as well as colour shifts (in comparison to a simple
colour

Value comparision). Is that true?



Sorry, I dont really know a lot about wavelets/FT.

Best regards,

Andreas


Andreas wrote:
> I am trying to find an image in another one (along the lines of a house in a > map > > Photographed from the air).
Hi Andreas, long time ago, I programmed a detector for geometric objects in an image. I think the algorithm could be adjusted for your use (sorry, doesn't use FT or Wavlets :). It is very robust against distortion, rotation and partial overlapp. To quote the Beasty Boys: It goes a little something like this: 1. "Learn" the object: Get a picture of the object, and define a point (the "center") by hand on the picture. Apply an edge-detector to the picture to find the edges of the contour of the object, and a another filter (I forgot which one) which assigns the angle of the contour at each point on the contour. Draw some rays (let's say twenty) radially starting from the user-defined "center"-point until they hit the contour (advance the angle of the next ray by 360/number-of-rays so that you get the full circle). Store the angle of the contour at that point. This will give you twenty angles, which already define your object (the distance from the "center" point to the contour doesn't matter). 2. Search: Run an edge detector over the image which you are searching, and afterwords the angle detector (as in step 1). For each point (pixel) in the image, draw twenty radial rays and compare the angles you find when you hit a contour with the ray with the angles you have stored for your object. If you have matched let's say 2/3 of the angles, you have found the object in the picture, and you know where it's contour is and how it is rotated. Parameters for this algorithm are the number of rays used to define an object and the number of matches before you declare the object found (you can also play around with the edge-detect kernel for contour sensitivity). It is easily fine-tuned for different applications. I also experimented with compound objects with more than one contour (for example a ring) which worked as well. This was about ten years ago, most probably more sophisticated algorithms are available (this algorithm completely ignores surface texture). Regards, Andor