// Finds position of a small image in a larger image
// Compile: gcc imgfind.c -o imgfind -lgd

#include <stdio.h> 
#include <gd.h> 
#include <stdlib.h>  
#define QUANT 10 

int avgcol(gdImagePtr image, int x, int y) {
 int color;
 color=gdImageGetPixel(image,x,y);
 return (gdTrueColorGetRed(color)+gdTrueColorGetGreen(color)+gdTrueColorGetBlue(color))/(3*QUANT);
}

int main(int argc, char *argv[]) {
 gdImagePtr image_small,image_large;
 int i,x,y,avg,query_size,sumdiff,lastavg,px,py;
 int mindiff=999,maxdiff=0,minx=0,miny=0,maxy=0;
 int *query;
 FILE *infile1, *infile2;
 if (argc<3) {
  printf("Syntax: imgfind <small.jpg> <large.jpg>\n");
  exit(1);
 }
 infile1 = fopen(argv[1], "rb");
 if(infile1==NULL) {
  printf("Unable to open %s\n",argv[1]);
  exit(1);
 }
 image_small = gdImageCreateFromJpeg(infile1);
 fclose(infile1);
 infile2 = fopen(argv[2], "rb");
 if(infile2==NULL) {
  printf("Unable to open %s\n",argv[2]);
  exit(1);
 }
 image_large = gdImageCreateFromJpeg(infile2);
 fclose(infile2);
 query_size=image_small->sx;
 query=malloc(sizeof(int)*query_size);
 for (y=0;y<image_small->sy;y++) {
  sumdiff=0;
  lastavg=-1;
  for (x=0;x<image_small->sx;x++) {
   avg=avgcol(image_small,x,y);
   if (lastavg>-1) {sumdiff+=abs(avg-lastavg);}
   lastavg=avg;
  }
  if (sumdiff>maxdiff) {
   maxdiff=sumdiff;
   maxy=y;
  }
 }
 for (x=0;x<query_size;x++) {query[x]=avgcol(image_small,x,maxy);}
 for (x=0;x<image_large->sx;x++) {
  for (y=0;y<image_large->sy;y++) {
   sumdiff=0;
   for (i=0;i<query_size;i++) {
    if (x+i>=image_large->sx) {
     sumdiff+=100/QUANT;
     continue;
    }
    sumdiff+=abs(query[i]-avgcol(image_large,x+i,y));
   }
   if (sumdiff<mindiff) {
    mindiff=sumdiff;
    minx=x;
    miny=y;
   }
  } 
 }
 px=minx+image_small->sx/2;
 py=miny-maxy+image_small->sy/2;
// printf("%s: maxy = %d, mindiff = %d, minpos = %d/%d\n",argv[2],maxy,mindiff,px,py);
 printf("%d\t%d\t%d\n",mindiff,px,py);
 free(query);
 gdImageDestroy(image_large);
 gdImageDestroy(image_small);
 return 0;
}