Need help and suggestions for image comparison method

[Maxwell777]

Things to note:
I am using C++, Qt, and OpenCV.

Background info:
I am trying to create a program (actually a method) in C++ that takes two (filtered to two color black & white) images from a moving robot, one within X amount of time of the other, then trys to find the amount of shift between each frame. It does this by overlaying the second picture ontop of the first, in every possible placement, and comparing the overlapping area, pixel per pixel.

I've gotten all of the bugs out (to the extent of my knowledge), with the exception of one. There is a method that takes two images, one from the overlapping area of each frame, counts each matching pixel, and returns a "score" of how similar the two images that were passed in. My issue with this is the "score" returned. This score only returns the number of matching pixels. If I were to give it larger images, it would return a larger score than if I gave it smaller ones, even if the smaller ones were more similar. I've already tried dividing the score by the area of the images.

The program does that for many different images to figure out which is the best match, which is dictated by the "score".

I was wondering what the best way to calculate the "score" is, that would always give the pair of images with the most in common the best score, regardless of size or shape.

Here is the troublesome code:

double ImgCompare (Mat Img1, Mat Img2, int ImgWidth, int ImgHeight) { //both images are the same diamentions

double Score = 0;

double ImgArea = ImgWidth * ImgHeight;

for (int Y = -1; Y < abs(ImgHeight-2); Y=Y) {

for (int X = -1; X < abs(ImgWidth-2); X=X) {

if (Img1.at<double>(X,Y) == Img2.at<double>(X,Y) ) {

Score++;

}

X++;

}

Y++;

}

//printf("Score = %f\n", Score);
return(Score);

}

Sorry for the lack of indents

Would anyone like the code for the rest?

[SoftwareBug2.0]

Are you using black and white or "color" (greyscale) or full color?

Your can do something like the average absolute value of the difference between the pixels. If you're using b&w or "color" that should be easy to calculate. If you're doing actual full color, then the computation will be a little more complex since there's a few different options.

Incedentily, the increments of your for loops bother me: "X=X" really shouldn't do anything.

[Greg McKaskle]

And what was the problem with dividing by the area? That will give score a range from 0 -- when no pixels match, to 1.0 when all pixels match. That normalizes the score.

I think the bigger problem is that your goal is to determine the shift, and counting matching pixels doesn't always act as a good predictor of shifted distance.

Lets look at two examples.
If the image is simple ... a black background and a smaller white square within it. If I shift the square one pixel to the right, two rows of pixels will contain errors. If I shift it two pixels four rows have errors. It seems to work well. Once the shift amount is greater than the edge size of the square, the score plateaus -- not that helpful in determining shift amount.

In the second image, lets have stripes, like a picket fence. The stripes are two pixels wide with two pixels of black in between. Shift one pixel and half of the rows have errors. Shift two and all rows have errors. Shift three and half have errors again, four and no errors (depends on what enters the frame).

Anyway this difficult problem, and a simple score like you are computing works well in some cases, but less well in others.

After you've completed this approach, perhaps you want to try another based on feature extraction. It could find the largest particle, or the ten largest and compare positions of those. It could identify corners within the image and track those. You may also find it useful to read about Optical Flow algorithms. They are pretty sophisticated to implement, but they are pretty robust.

Greg McKaskle

[Maxwell777]

Originally Posted by SoftwareBug2.0

Are you using black and white or "color" (greyscale) or full color?

Your can do something like the average absolute value of the difference between the pixels. If you're using b&w or "color" that should be easy to calculate. If you're doing actual full color, then the computation will be a little more complex since there's a few different options.

Incedentily, the increments of your for loops bother me: "X=X" really shouldn't do anything.

Sorry about those incrementations. I did it to keep the loop indexed at 0, instead of the loop starting with an x value of 1.

The images are in literal black & white, as in the pixles are either black, or they are white.

[Maxwell777]

Originally Posted by Greg McKaskle

And what was the problem with dividing by the area? That will give score a range from 0 -- when no pixels match, to 1.0 when all pixels match. That normalizes the score.

I think the bigger problem is that your goal is to determine the shift, and counting matching pixels doesn't always act as a good predictor of shifted distance.

Lets look at two examples.
If the image is simple ... a black background and a smaller white square within it. If I shift the square one pixel to the right, two rows of pixels will contain errors. If I shift it two pixels four rows have errors. It seems to work well. Once the shift amount is greater than the edge size of the square, the score plateaus -- not that helpful in determining shift amount.

In the second image, lets have stripes, like a picket fence. The stripes are two pixels wide with two pixels of black in between. Shift one pixel and half of the rows have errors. Shift two and all rows have errors. Shift three and half have errors again, four and no errors (depends on what enters the frame).

Anyway this difficult problem, and a simple score like you are computing works well in some cases, but less well in others.

After you've completed this approach, perhaps you want to try another based on feature extraction. It could find the largest particle, or the ten largest and compare positions of those. It could identify corners within the image and track those. You may also find it useful to read about Optical Flow algorithms. They are pretty sophisticated to implement, but they are pretty robust.

Greg McKaskle

When you divide the score by the area, I think (as in it's possible there's a bug elsewhere and I lied to you) the program then becomes focused on reducing the area to achieve a better score. I also tried reducing the area's influence (Score = matches / Area/2 ) of the total score, which didn't help.

This program is actually a dumb program, in that it takes every possible shift, and gives it a score, and whichever shift(shiftX, shiftY) has the best score is the shift that it considers to be right. It disregards all scores other than the best one, so it doesn't matter if the score plateaus.

Images the program are working with have almost no pattern whatsoever (it's looking at patches of moss on the bottom of a pool), so I'm not worried about things like you're fence example.

This program is actually an optical flow program, and this was the simplest system I could think of.

[Greg McKaskle]

I didn't tie this to the post from Freddi. While this is good for learning the effectiveness of various algorithms, but this brute force approach will be thousands of times slower than more modern approaches. If you can provide some video sequences of the pool bottom, it would allow for different approaches to be compared in order to identify the performance and robustness tradeoffs.

Greg McKaskle

[Maxwell777]

I was looking at other methods of achieving this, but I would still like to get this one working. As for performance, I found this system works just fine, only at a lower resolution, say 64px by 64px. I could also improve performance later on by looking at every Nth frame, and only checking the match hotspots.

I think I'll try other, already done, forms of optical flow for now however.

[SoftwareBug2.0]

Something you can try is to multiply the score of each match by an estimate of how likely that result should be. For example, if you think the robot should be moving slowly, then results that would imply large motions should be penalized.

One way to do this is to use normal distributions. For example, you might estimate that you should have moved 10 px forward since the last frame with a standard deviation of 3. From That, you can give an initial estimate of how likely having moved 8 px is vs 10 px vs 1 px. So the initial estimate would say 10 px of movement is likely and 8 px is reasonable and 1 px is unlikely because it's 3 standard deviations away from what was expected.

I hope that makes sense.

[Greg McKaskle]

One thing you may want to do is to plot your result as an image. You have image A, and image B, and you are skipping a few steps but are essentially computing image C=B==A and then summing all pixels in C. It may be helpful to visualize C and see if there are issues around the edges, or see if your algorithm does something unexpected. You may also want to compare the current approach to using C= |B-A| or similar functions that aren't just binary.

Greg McKaskle

[Al Skierkiewicz]

A technique we have used for years in broadcast is to invert one of the images and then add. The result is only that which is different. Counting that should be fairly easy. If you are comparing pixel by pixel the overall number shouldn't change with image/zoom should it?

[Joe Ross]

Originally Posted by Maxwell777

When you divide the score by the area, I think (as in it's possible there's a bug elsewhere and I lied to you) the program then becomes focused on reducing the area to achieve a better score. I also tried reducing the area's influence (Score = matches / Area/2 ) of the total score, which didn't help.

I'm confused. Why do you have images of different resolutions being scored and compared to each other?

[SoftwareBug2.0]

Originally Posted by Joe Ross

I'm confused. Why do you have images of different resolutions being scored and compared to each other?

I think what he's saying is that to compare two images that are offset he's just comparing the region of overlap. So if the upper left pixel is black in the first image and the lower right pixel is black in the second image, one of the combinations he would try would consist of only those two pixels. Then, since they're both black there would be a 100% match.

[Pault]

Originally Posted by Joe Ross

I'm confused. Why do you have images of different resolutions being scored and compared to each other?

They aren't different resolutions. This is best explained using visuals.

Here is the first picture:

XXXXX
XXXXX
XXXXX
XXXXX
XXXXX

And the second picture:

YYYYY
YYYYY
YYYYY
YYYYY
YYYYY

Now, he is trying to see how far the robot has moved is a given direction. His unit of measurment is pixels that the camera sees. He makes this measurement by overlapping the 2 pictures in every possible way. Here are 2 examples:

(Z is the overlap between the pictures)

XXXXX
XXXXX
XXXXX
XXXXX
ZZZZZ
YYYYY
YYYYY
YYYYY
YYYYY

XXXXX
ZZZZZ
ZZZZZ
ZZZZZ
ZZZZZ
YYYYY

In the case that example 1 is the right match, the robot has moved backwards 4 pixels. If example 2 is the right match, the robot has moved backwards 1 pixel. To figure out which overlap is the right match, he scores the overlap based on how many pixels in the overlapping areas match color. So lets look at the overlap from the 2 examples:

ZZZZZ

ZZZZZ
ZZZZZ
ZZZZZ
ZZZZZ

Now, lets say just that all of the pixels in example 1 match up, but only half of the pixels in example 2 match. You would probably think "example 1 is the right match", but it only has a score of 5, where as the second picture has a score of 10. That is where the different areas come in.

I may have went a little overboard with this explanation .

[Maxwell777]

Good Example. I shoulda put that up originally.

[Maxwell777]

Originally Posted by SoftwareBug2.0

Something you can try is to multiply the score of each match by an estimate of how likely that result should be. For example, if you think the robot should be moving slowly, then results that would imply large motions should be penalized.

One way to do this is to use normal distributions. For example, you might estimate that you should have moved 10 px forward since the last frame with a standard deviation of 3. From That, you can give an initial estimate of how likely having moved 8 px is vs 10 px vs 1 px. So the initial estimate would say 10 px of movement is likely and 8 px is reasonable and 1 px is unlikely because it's 3 standard deviations away from what was expected.

I hope that makes sense.

I hadn't tried that yet. Maybe instead of using a solid estimate, I could use the current speed as a base point, and from there it would reduce the score for shifts as they get father away from the avg shift. Actually wait no. That would probably screw up the accuracy. I'll just go with yours