Sign in to follow this  
bear330

Does anyone know how to detect image offset?

Recommended Posts

Hi, I have two images: http://mercurius.f-snet.com/offset1.png http://mercurius.f-snet.com/offset2.png They are the same in visually by eyes, but actually they are different because of margin. Does anyone know any algorithm or way to compare these two images but ignores the offset of images? (I mean, offset2.png can be treated like offset1.png + n pixels offset, it only moved, not changed.) If I do boost::gil::equal_pixels(offset1, offset2), I will get false because they are different. I need a way to compare offset1.png and offset2.png with moving detection. Any suggestion is welcome! Thanks.

Share this post


Link to post
Share on other sites
How accurate do you want to be? If accuracy doesn't need to 100% you could use a heuristic comparison. For example, you could compare them statistically, such as with a color histogram. You'd count how often each shade of each of the three primary colors (RGB) occurred for each image. Finally, compare the histograms.

Here is some crude code I quickly threw together. It changes the window title to indicate the result.


#include <SDL/SDL.h>
#include <SDL/SDL_image.h>

#define SCREEN_W 640
#define SCREEN_H 480
#define SCREEN_BPP 32

typedef struct hist
{
unsigned int r[256];
unsigned int g[256];
unsigned int b[256];
};

SDL_Surface* loadimage(char* file);
int main(int argc, char *argv[])
{
SDL_Surface *screen;
SDL_Surface *img1 = NULL;
SDL_Surface *img2 = NULL;

hist h1, h2;
int r,g,b;

for(int i = 0; i <256 ; i++)
{
h1.r[i] = 0;
h1.g[i] = 0;
h1.b[i] = 0;

h2.r[i] = 0;
h2.g[i] = 0;
h2.b[i] = 0;
}

unsigned int *pixel;
unsigned int tmp = 0;

atexit(SDL_Quit);

if(SDL_Init(SDL_INIT_EVERYTHING) < 0)
{
return EXIT_FAILURE;
}

if((screen = SDL_SetVideoMode(SCREEN_W, SCREEN_H, SCREEN_BPP, SDL_SWSURFACE)) == NULL)
{
return EXIT_FAILURE;
}

img1 = loadimage("offset1.png");
img2 = loadimage("offset2.png");

if(img1 == NULL && img2 == NULL)
{
return EXIT_FAILURE;
}

SDL_LockSurface(img1);
SDL_LockSurface(img2);



pixel = (unsigned int*)img1->pixels;

for(int y = 0; y < img1->h; y++)
{
for(int x = 0; x < img1->w; x++)
{
tmp = pixel[x + (y *img1->w)];

r = tmp & 0xff000000;
g = tmp & 0x00ff0000;
b = tmp & 0x0000ff00;

r = r >> 24;
g = g >> 16;
b = b >> 8;


h1.r[r]+=1;

h1.g[g]+=1;

h1.b[b]+=1;

}
}


pixel = (unsigned int*)img2->pixels;

for(int y = 0; y <img2->h; y++)
{
for(int x = 0; x < img2->w; x++)
{
tmp = pixel[x + (y *img2->w)];
r = tmp & 0xff000000;
g = tmp & 0x00ff0000;
b = tmp & 0x0000ff00;

r = r >> 24;
g = g >> 16;
b = b >> 8;

h2.r[r]+=1;

h2.g[g]+=1;

h2.b[b]+=1;
}
}

SDL_UnlockSurface(img1);
SDL_UnlockSurface(img2);
SDL_FreeSurface(img1);
SDL_FreeSurface(img2);

for(int i = 0; i < 256; i++)
{
if((h1.r[i] == h2.r[i]) &&
(h1.g[i] == h2.g[i]) &&
(h1.b[i] == h2.b[i]))
{
SDL_WM_SetCaption("Match!", 0);
}
else
{
SDL_WM_SetCaption("No Match...", 0);
}

}

SDL_Delay(3000);

return EXIT_SUCCESS;
}




SDL_Surface* loadimage(char* file)
{
SDL_Surface *img;
SDL_Surface *tmp;

tmp = IMG_Load(file);

if(tmp != NULL)
{
img = SDL_DisplayFormat(tmp);
SDL_FreeSurface(tmp);
}
else
{
return NULL;
}

return img;
}









I did a little searching and came across this thread. Some of the suggestion may be of use.

[Edited by - prh99 on June 8, 2009 1:37:05 AM]

Share this post


Link to post
Share on other sites
Hi,

You could use Fourier Transform and compare only real parts (discarding phase). So It will cancel any rotations or translations.

Share this post


Link to post
Share on other sites
Quote:
Original post by krisiun
Hi,

You could use Fourier Transform and compare only real parts (discarding phase). So It will cancel any rotations or translations.


He means compare only the magnitude, which is sqrt((real part)2 + (imaginary part)2). I think this is a good idea. If you need to figure out what the offset is, there are Fourier methods for this too:
1. (Naive method) Ratio of images' FFTs gives phase factor. Inverse transform this to get delta function at location corresponding to offset.
2. (Better method) Find the maximum of the cross-correlation; this can be computed by passing the images with zeros and doing FFTs.

Share this post


Link to post
Share on other sites
To prh99:

Thank you! I will try your method to test it fulfills my requirement or not.

To krisiun:

I am very embarrassing that I don't understand FFT at all. :(
I only know a little about it, how FFT will help me?

Thank you very much.

Share this post


Link to post
Share on other sites
Oh, the performance for my application is critical and the background of image might not white (background might be black, brown...etc and even a other pattern image).

Does there any algorithm or library fit my requirement?
Thanks.

Share this post


Link to post
Share on other sites
Here is a more complicated case.

http://mercurius.f-snet.com/offset3.png
http://mercurius.f-snet.com/offset4.png

These two images are different by image comparison method, but you can't find what different in human eyes. The only different part is background pattern.

I need a way to ignore the background and detect the image moving.

Thanks.

Share this post


Link to post
Share on other sites
@krisiun: Also, the Fourier magnitude image is NOT invariant under rotation of the original image. In fact, it rotates along with it.

@bear330: You can use HTML "img" tags to embed images in your posts.

Quote:
Original post by bear330
These two images are different by image comparison method, but you can't find what different in human eyes. The only different part is background pattern.

I need a way to ignore the background and detect the image moving.


What exactly do you want? If you were to input those two images to a program that did what you wanted, what would it output? A pair of numbers giving the 2d offset of the background? Some kind of TRUE/FALSE output? I'm not clear on what you want here.

Share this post


Link to post
Share on other sites
Oh, I need some thing like this:

fuzzy_compare_image(offset1.png, offset2.png)

it returns TRUE/FALSE.

It can detect image moving (case offset1.png and offset2.png) and ignore the noise background pattern (case offset3.png and offset4.png).

Thank you very much.

Share this post


Link to post
Share on other sites
Ah, I see. One issue is that some parts of the problem are a little bit ill-defined -- like, "what's the 'background?'" In any event, I'm liking krisiun's idea more and more: From each image, generate a fourier magnitude image; then compare these fourier magnitude images with a more 'naive' image comparison algorithm like Euclidean distance; if the distance is less than some threshold return 'TRUE' and otherwise return 'FALSE.'

Another idea would be to look at the scale-invariant feature transform (SIFT)...

You could try looking here for an overview of some relevant algorithms...

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this