leonidn
asked on
Matlab - how can I check the level of similarity between two images?
Hi all,
How can I check the level of similarity between two images?
(Basically they are nearly the same size).
Thanks!!
How can I check the level of similarity between two images?
(Basically they are nearly the same size).
Thanks!!
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Both of these techniques will work better if you can make the file the same size before processing.
Either stretch the smaller one or shrink the larger.
You could also normalize the FFT after processing.
What are your images? Faces or maps or fingerprints? What kind of differences are you looing for?
There are particular techniques for some types of images?
Either stretch the smaller one or shrink the larger.
You could also normalize the FFT after processing.
What are your images? Faces or maps or fingerprints? What kind of differences are you looing for?
There are particular techniques for some types of images?
ASKER
Here is some information that is (hopefully) useful.
1) Average size of an image is 24x24, but it can be 23x26, etc...
2) The images are binary (that is, a pixel is either white or black).
3) Possible images: square, triangle, cross (maybe a couple of others, but very different from each other).
Even if both images are squares, that ARE different (because the images are a result of an edge-detection algorithm.
1) Average size of an image is 24x24, but it can be 23x26, etc...
2) The images are binary (that is, a pixel is either white or black).
3) Possible images: square, triangle, cross (maybe a couple of others, but very different from each other).
Even if both images are squares, that ARE different (because the images are a result of an edge-detection algorithm.
Put your little images in the center of a 32x32 square to normalize them.
(You have to pad to 2^n anyway for FFT's.)
The FFT should be able to pick out the various features pretty easily.
You might also want to look at eigenvalue decomposition.
This is one of the techniques they use for comparing faces.
Matlab certainly has the tools for this. Check the SVD function.
(You have to pad to 2^n anyway for FFT's.)
The FFT should be able to pick out the various features pretty easily.
You might also want to look at eigenvalue decomposition.
This is one of the techniques they use for comparing faces.
Matlab certainly has the tools for this. Check the SVD function.
ASKER
Example images (3 sqares and a triangle):
http://www.organizermp3.com/matlab.mat
http://www.organizermp3.com/matlab.mat
ASKER
I've just tried FFT2 on the padded 32x32 images (original images in center).
Then I tried:
f1 = real(fft2(im1));
f2 = real(fft2(im2));
sum(sum(abs(f1-f2)))
For square vs. square it returned 1.3695e+006
And for a square vs. triangle it returned 1.7954e+006
Not a difference you oculd trust :'-(
Am I doing something wrong?
Then I tried:
f1 = real(fft2(im1));
f2 = real(fft2(im2));
sum(sum(abs(f1-f2)))
For square vs. square it returned 1.3695e+006
And for a square vs. triangle it returned 1.7954e+006
Not a difference you oculd trust :'-(
Am I doing something wrong?
Sorry I can not read that file.
Are your images lines or blobs? Are they aligned with the x or y axes?
If they are aligned line drawings, maybe all you have to do is look at the sums of each horizontal and vertical row.
A square would have two peaks in each of the sum vectors.
A triangle woud have one peak in one of the sum vectors.
A cross would have one peak in each of the sum vectors.
And so on...
Are your images lines or blobs? Are they aligned with the x or y axes?
If they are aligned line drawings, maybe all you have to do is look at the sums of each horizontal and vertical row.
A square would have two peaks in each of the sum vectors.
A triangle woud have one peak in one of the sum vectors.
A cross would have one peak in each of the sum vectors.
And so on...
You still have to normalize.
sum(sum(abs(f1-f2)))
K = --------------------------
sum(sum(abs(f1+f2)))
Your K values should be near 1 for matches and near 0 for mismatches.
sum(sum(abs(f1-f2)))
K = --------------------------
sum(sum(abs(f1+f2)))
Your K values should be near 1 for matches and near 0 for mismatches.
Sorry, that is backwards...
Your K values should be near 0 for matches and near 1 for mismatches.
Your K values should be near 0 for matches and near 1 for mismatches.
ASKER
Another test:
I took 3 squares (a, b, c), and compared to each other, and then same with two triangles (d and e):
1.3695e+006 <-- a vs. b
7.1811e+005 <-- a vs. c
1.3644e+006 <-- b vs. c
6.3247e+005 <-- d vs. e
Then I took each of the 3 squared, and compared to a triangle d:
1.7983e+006 <-- a vs. d
1.7392e+006 <-- b vs. d
1.7954e+006 <-- c vs. d
Then I took each of the 3 squared, and compared to another triangle e:
1.7663e+006 <-- a vs. e
1.7510e+006 <-- b vs. e
1.7852e+006 <-- c vs. e
########################## #########
The results are always correct (I can match between the two objects), but I do not think the difference is very reliable.
What do you think?
I took 3 squares (a, b, c), and compared to each other, and then same with two triangles (d and e):
1.3695e+006 <-- a vs. b
7.1811e+005 <-- a vs. c
1.3644e+006 <-- b vs. c
6.3247e+005 <-- d vs. e
Then I took each of the 3 squared, and compared to a triangle d:
1.7983e+006 <-- a vs. d
1.7392e+006 <-- b vs. d
1.7954e+006 <-- c vs. d
Then I took each of the 3 squared, and compared to another triangle e:
1.7663e+006 <-- a vs. e
1.7510e+006 <-- b vs. e
1.7852e+006 <-- c vs. e
##########################
The results are always correct (I can match between the two objects), but I do not think the difference is very reliable.
What do you think?
ASKER
Here are the images: a, b, c, d and e (left to right):
http://www.organizermp3.com/matlab.jpg
http://www.organizermp3.com/matlab.jpg
ASKER
> If they are aligned line drawings, maybe all you have to do is look at the sums of each horizontal and vertical row.
>
> A square would have two peaks in each of the sum vectors.
> A triangle woud have one peak in one of the sum vectors.
> A cross would have one peak in each of the sum vectors.
> And so on...
Yes, they are aligned, but I can't assume these are all the shapes I can get. The algorithm has to be more generic than just squares and triangles...
By the way, the shapes do not rotate, so this makes the task a little easier.
>
> A square would have two peaks in each of the sum vectors.
> A triangle woud have one peak in one of the sum vectors.
> A cross would have one peak in each of the sum vectors.
> And so on...
Yes, they are aligned, but I can't assume these are all the shapes I can get. The algorithm has to be more generic than just squares and triangles...
By the way, the shapes do not rotate, so this makes the task a little easier.
ASKER
Just to clarify the task:
I get some objects in pairs (for example, 2 squares, and two triangles).
The images can be passed to the function in any order,
I need to match between every pair.
I get some objects in pairs (for example, 2 squares, and two triangles).
The images can be passed to the function in any order,
I need to match between every pair.
ASKER
After normalizing your way:
sum(sum(abs(f1-f2)))
K = --------------------------
sum(sum(abs(f1+f2)))
I get:
########################## ########## ########## ########## ########
Comparing two similar shapes:
>> k_ab = sum(sum(abs(aa-bb))) / sum(sum(abs(aa+bb)))
0.6372
>> k_ac = sum(sum(abs(aa-cc))) / sum(sum(abs(aa+cc)))
0.2880
>> k_bc = sum(sum(abs(bb-cc))) / sum(sum(abs(bb+cc)))
0.6240
>> k_de = sum(sum(abs(dd-ee))) / sum(sum(abs(dd+ee)))
0.2531
########################## ########## ########## ########## ########
Comparing two different shapes:
>> k_ad = sum(sum(abs(aa-dd))) / sum(sum(abs(aa+dd)))
0.9060
>> k_ae = sum(sum(abs(aa-ee))) / sum(sum(abs(aa+ee)))
0.8928
>> k_bd = sum(sum(abs(bb-dd))) / sum(sum(abs(bb+dd)))
0.8821
>> k_ce = sum(sum(abs(cc-ee))) / sum(sum(abs(cc+ee)))
0.8987
########################## ########## ########## ########## ########
So it too gives correct reults (I can match pairs), but the results are still quite close to each, I think).
sum(sum(abs(f1-f2)))
K = --------------------------
sum(sum(abs(f1+f2)))
I get:
##########################
Comparing two similar shapes:
>> k_ab = sum(sum(abs(aa-bb))) / sum(sum(abs(aa+bb)))
0.6372
>> k_ac = sum(sum(abs(aa-cc))) / sum(sum(abs(aa+cc)))
0.2880
>> k_bc = sum(sum(abs(bb-cc))) / sum(sum(abs(bb+cc)))
0.6240
>> k_de = sum(sum(abs(dd-ee))) / sum(sum(abs(dd+ee)))
0.2531
##########################
Comparing two different shapes:
>> k_ad = sum(sum(abs(aa-dd))) / sum(sum(abs(aa+dd)))
0.9060
>> k_ae = sum(sum(abs(aa-ee))) / sum(sum(abs(aa+ee)))
0.8928
>> k_bd = sum(sum(abs(bb-dd))) / sum(sum(abs(bb+dd)))
0.8821
>> k_ce = sum(sum(abs(cc-ee))) / sum(sum(abs(cc+ee)))
0.8987
##########################
So it too gives correct reults (I can match pairs), but the results are still quite close to each, I think).
ASKER
P.S. I also tried to use fftshift before applying your forumla:
sum(sum(abs(f1-f2)))
K = --------------------------
sum(sum(abs(f1+f2)))
but got really similar results as without fftshift.
sum(sum(abs(f1-f2)))
K = --------------------------
sum(sum(abs(f1+f2)))
but got really similar results as without fftshift.
Those results look pretty good to me.
You could set your threshold at 0.7 and call it a day.
What is the penalty for making an error.
The only thing that keeps the results from looking very good is that k_ab and k_bc ~ 0.6
I would have hoped for something less than 0.5
Is there something odd about image b??
You could set your threshold at 0.7 and call it a day.
What is the penalty for making an error.
The only thing that keeps the results from looking very good is that k_ab and k_bc ~ 0.6
I would have hoped for something less than 0.5
Is there something odd about image b??
ASKER
> The only thing that keeps the results from looking very good is that k_ab and k_bc ~ 0.6
> I would have hoped for something less than 0.5
That's exactly my point...
Is there something odd about image b??
I don't think so... have a look at the middle square in the image I uploaded:
http://www.organizermp3.com/matlab.jpg
> I would have hoped for something less than 0.5
That's exactly my point...
Is there something odd about image b??
I don't think so... have a look at the middle square in the image I uploaded:
http://www.organizermp3.com/matlab.jpg
ASKER
> What is the penalty for making an error?
Pretty bad because it may probably cause cascading errors...
I will try to allow a fault surrounded by several successes, but I prefer to avoid the situation...
The direct effect of an error in the algorithm may cause the robot not recognize an object that gets nearer and nearer to it. As a result, the robot won't bend, and the ball will hit it just in the "face" :-)
Pretty bad because it may probably cause cascading errors...
I will try to allow a fault surrounded by several successes, but I prefer to avoid the situation...
The direct effect of an error in the algorithm may cause the robot not recognize an object that gets nearer and nearer to it. As a result, the robot won't bend, and the ball will hit it just in the "face" :-)
ASKER
d-glitch,
Increased by 100 points, and accepted your answer as 'excellent'.
Thank you very much for your quick and good answer.
Your help is very much appreciated!
Increased by 100 points, and accepted your answer as 'excellent'.
Thank you very much for your quick and good answer.
Your help is very much appreciated!
I think the problem might be with the ragged corners on the squares.
You might be able to improve things by some simple filtering.
Vertical lines have high frequency X components and low frequency Y components.
Horizontal lines have high frequency Y components and low frequency X components.
Slanted lines will have intermediate X and Y components.
But the jagged corners will have HF X and Y components. This is essentially noise.
You may be able to eliminate it before you do the comparisons.
Look at what parts of the FFT are contributing the most to k_ab and k_bc ==> 0.6
and set those elements to zero. It should be appox 1/4 or less of the array.
You might be able to improve things by some simple filtering.
Vertical lines have high frequency X components and low frequency Y components.
Horizontal lines have high frequency Y components and low frequency X components.
Slanted lines will have intermediate X and Y components.
But the jagged corners will have HF X and Y components. This is essentially noise.
You may be able to eliminate it before you do the comparisons.
Look at what parts of the FFT are contributing the most to k_ab and k_bc ==> 0.6
and set those elements to zero. It should be appox 1/4 or less of the array.
ASKER
I do like the FFT2 idea, but it the result matrixes are of (slightly) different sizes. How can I compare these ones?