   Does anyone know how to detect image offset?
  Hi,I have two images:http://mercurius.f-snet.com/offset1.pnghttp://mercurius.f-snet.com/offset2.pngThey 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.   
  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 32typedef 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 = 0;   h1.g = 0;   h1.b = 0;   h2.r = 0;   h2.g = 0;   h2.b = 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+=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+=1;   }    }    SDL_UnlockSurface(img1);    SDL_UnlockSurface(img2);    SDL_FreeSurface(img1);    SDL_FreeSurface(img2);  for(int i = 0; i < 256; i++)    {   if((h1.r == h2.r) && (h1.g == h2.g) && (h1.b == h2.b)) {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];  Hi,You could use Fourier Transform and compare only real parts (discarding phase). So It will cancel any rotations or translations.   ;Quote:Original post by krisiunHi,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.   ;  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.   ;  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.   ;  Here is a more complicated case.http://mercurius.f-snet.com/offset3.pnghttp://mercurius.f-snet.com/offset4.pngThese 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.   ;  @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 bear330These 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.   ;  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.   ;  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...   