How can I match a small part of an image to its whole image?

Let's say I have an image of a flower, I cut out 3 seemingly identical smaller images of petals from that flower. Now without simply looking at the image and putting those petals back in their EXACT locations, how can I know where each petal belongs EXACTLY in that image of the flower? I thought about doing histogram analysis of each individual petal's image then matching it back to original image, but I am not sure if the histogram of an image can show differences between very similar images. Is this a good method? Is there a better method? Thanks Mates!

Answer 1

[Image Analyst]

No, that histogram algorithm won't work at all, as you'll realize if you just give it a little thought. What you want to use is normalized cross correlation, which is done by the function normxcorr2() in the Image Processing Toolbox. I'm attaching my demo of it, below this image that it creates.

[Neo]

I have in fact given it much thought, why wouldn't it work?

[Image Analyst]

Why should it? Let's say you were looking for a small reddish square. Well the histogram of the target you are looking for will match in lots of locations. Just look how many small reddish squares you can fit in the peppers image. Lots of places will have the same histogram. But if you use normxcorr2 not only will they have a similar histogram but the spatial arrangement of the pixels must also be fairly similar. Just checking the histograms alone does not guarantee that. If a region of image was completely upside down or rotated 90 degrees, or sorted into a ramp, they would all have the same histogram despite looking totally different.

[Neo]

What are the set backs of this method?

[Neo]

Because I don't want the spatial arrangement to be fairly similar I want it to be exact.

[Image Analyst]

Using normxcorr2, it can be exact. Just look for where the value of the max is like 0.9999999999999.

[Neo]

Where the pixel value of the max is like .99999999999?

[Image Analyst]

That happens when the template exactly overlaps the bigger search image. I set a breakpoint at that line of code and checked what it said the max was. Theoretically it should be 1 but I guess with truncation/digitization error it's not quite 1.

[Neo]

Okay I am starting to see. When I run the code do i need to save that image that you gave me in order to see the demo? Then afterwards I can change the picture. Also does this algorithm take into account the boundaries of different shapes within the image? Like If the onion needed to fit within a circle region and not overlap with the cylinder shape of an eggplant.

[Image Analyst]

It doesn't care about shape and it cares everything about shape. Basically it will look for patches in the larger image that have the same intensity values. It doesn't care if you have an onioni or eggplant or anything. All it cares about is if the intensities match up pixel for pixel. If they match exactly, it will give a 1 at that location. If there's not an exact match, it will give some value less than 1. The worse a match it is, the closer the value will be to 0.

[Neo]

What do you mean by it will give a 1 at that location? The code doesn't output any numbers, so are you referring to the C (double matrix) itself?

Also in the demo in the line SmallSubImage = imcrop(rgbImage, [192,82, templateWidth, templateHeight]); I believe the numerical values here correspond to xLeft and xTop if I'm not mistaken. How would I determine these values? By looking at the subimages matrix? And to be sure xLeft is the row and xTop is the column correct?

Sorry these should be my last set of questions.

[Image Analyst]

normxcorr2() outputs an image. There is no "C" matrix, the normxcorr2() output is called correlationOutput. The image ranges from 0 to 1. Where the template is perfectly aligned over the larger image, the output image, correlationOutput, will be 1 at that location. If it's not a perfect match, then correlationOutput will be maximum wherever it thinks the "best" match is.

(192,82) corresponds to xLeft and yTop (not xTop). I just chose those because I wanted the onion to be the template and that's where its bounding box is. If you want some other pepper to be the template, then you would crop the image at a different location. You don't have to crop from the original. If you have the template image in a different image file, you could use that instead.

[Image Analyst]

You're welcome. Sounds like we're done here, so could you officially "Accept" this answer? Thanks in advance.

[Neo]

WAIT! Are the max values from the correlation output represented by the intensities? i.e. in your demo was 1 the brightest spot in the black and white image?

[Image Analyst]

If you look at the lower left grayscale image, you'll see a very bright spot at x = 263, y = 131. That bright spot is caused by the white onion overlapping the white onion. Remember, in correlation and convolution, the output image is bigger than the original image by the width of the template. The values in the gray scale correlation image are the correlation values, and of course, not all of them are the max value, only one of them is. The other values range from 0 to 1 depending on how good of a match the white onion is to the other places in the image.

[Neo]

Hey Image Analyst, I am afraid that using this function to correlate a template with an image will highlight where I need to place the template for the template and the image to line up, not highlight where they line up. Or would this not be a problem because the template would be smaller than the image?

[Image Analyst]

I don't understand what you said or asked. Of course it will point out the template should be placed over the other image for the best match. That's it's point. I don't know what you think the difference is between "where I need to place the template" and "where they line up" is. Basically it locates the location of the best match, and my demo outlines that location with a colored box in the overlay. Explain those two concepts you mentioned and why you think they're different. And explain which one is what I do, and which one is different than what I do in my demo.

[Neo]

Hey Image Analyst, sorry I did not get back to you about the previous comment. That dilemma was presented to me by a colleague and I didn't see the difference so I explained the argument to you to see if you would and I couldn't explain it better because I don't quite believe it myself. However, I was wondering if you could point out some literature in dealing with image analysis. I know that if an image has a correlation value of 1 it is the same, 0 no correlation, and -1 opposing correlations. However, I want to determine how far away from 1 before the correlation between the images are not useful. Can you explain this or point me in the right direction? Thanks if able. - Neo

[Image Analyst]

Many people incorrectly think that correlation is the best way for finding where a pattern occurs in a scene. Though it can, it's not robust. Imagine a simple example where you're trying to find a dark tire in a scene. You know correlations is just sliding the template over some part of the image and multiplying the windows and summing the result. Imagine the tire is over some part of the image that look just like it. It would have some correlation value. Now imagine it was over some part of the image where every pixel in it was 255. Now, which position do you think would have the higher sum? Of course the all white portion would. But was that where the tire was? No, even though that location had the highest correlation value.

See if this makes it more understandable: https://en.wikipedia.org/wiki/Cross-correlation#Normalized_cross-correlation

[Neo]

sorry i should have said ssim value -1, 0, or 1 not correlation. I want to determine how far from 1 an images ssim value can be before that image is deemed not useful for comparison.

[Image Analyst]

Wouldn't that be a judgment call? Just figure out what works for you with your particular images.

[Neo]

Ah. I see thanks Analyst.

[sonia khan]

salam can u plz give me the code of this