// Laura Matefy, Dan Knights and Victor Dan
// Cx 336 - Final Project


/* ssd.c
 *
 * SSD-based method of matching tiles to model image
 *
 * Input: 16 GrayImage tiles and 16 GrayImage models
 * Output: array of ordered tile image numbers
 *
 * 
 */



#include <stdio.h>
#include <limits.h> /* for INT_MAX */
#include <getopt.h>
#include <math.h>

/* comment out for speed later! */
//#define IMAGE_CHECKALL

#include "mcimg.h"



/* prototypes for functions defined below: */

void computeLocation(GrayImage tiles[], GrayImage model[]);
int getSSD(GrayImage im1, GrayImage im2);


/***************************************************************************/
/* main program */

int main()
{	
// load all images into tile[] and models[]
  GrayImage tile[16];
  GrayImage models[16]; 

  tile[0] = loadGrayImage ("tile1.pgm");
  tile[1] = loadGrayImage ("tile2.pgm");
  tile[2] = loadGrayImage ("tile3.pgm");
  tile[3] = loadGrayImage ("tile4.pgm");
  tile[4] = loadGrayImage ("tile5.pgm");
  tile[5] = loadGrayImage ("tile6.pgm");
  tile[6] = loadGrayImage ("tile7.pgm");
  tile[7] = loadGrayImage ("tile8.pgm");
  tile[8] = loadGrayImage ("tile9.pgm");
  tile[9] = loadGrayImage ("tile10.pgm");
  tile[10] = loadGrayImage ("tile11.pgm");
  tile[11] = loadGrayImage ("tile12.pgm");
  tile[12] = loadGrayImage ("tile13.pgm");
  tile[13] = loadGrayImage ("tile14.pgm");
  tile[14] = loadGrayImage ("tile15.pgm");
  tile[15] = loadGrayImage ("tile16.pgm");
  
  models[0] = loadGrayImage ("model1.pgm");
  models[1] = loadGrayImage ("model2.pgm");
  models[2] = loadGrayImage ("model3.pgm");
  models[3] = loadGrayImage ("model4.pgm");
  models[4] = loadGrayImage ("model5.pgm");
  models[5] = loadGrayImage ("model6.pgm");
  models[6] = loadGrayImage ("model7.pgm");
  models[7] = loadGrayImage ("model8.pgm");
  models[8] = loadGrayImage ("model9.pgm");
  models[9] = loadGrayImage ("model10.pgm");
  models[10] = loadGrayImage ("model11.pgm");
  models[11] = loadGrayImage ("model12.pgm");
  models[12] = loadGrayImage ("model13.pgm");
  models[13] = loadGrayImage ("model14.pgm");
  models[14] = loadGrayImage ("model15.pgm");
  models[15] = loadGrayImage ("model16.pgm");

  computeLocation (tile, models);
  return(0);
}


/***************************************************************************/
/* motion computation */

/* compute location of tile in puzzle by comparing with models
 */
void computeLocation(GrayImage tile[], GrayImage models[])
{
  int i, j, k, besti, bestj, bestssd; 
  int marker[16] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; // to check if model is already matched
  
  int location[16];  // to store location
  int ssd[16][16];  // to store all ssd's

  for(i=0; i<16; i++){
    location[i] = -1;
    for(j=0; j<16; j++)
      ssd[i][j] = 0;
  }

  /* FOR EACH TILE IN ARRAY */
  for (i=0; i<16; i++) {

    /* FOR EACH MODEL */
    for (j=0; j<16; j++) {

      /* check if model has already been matched to tile */
      if (marker[j] == 0 ){

	ssd[i][j] = getSSD(tile[i], models[j]);
	
      }

    } //close model loop

  } // close tile loop
  



  // given ssd's, use greedy matching to find best fit.
  // check all ssd's for the best one
  for(k=0; k<16; k++){
    bestssd = INT_MAX;
    besti = 0;
    bestj = 0;
    for(i=0; i<16; i++)
      for(j=0; j<16; j++)
	if(ssd[i][j] != -1 && ssd[i][j] < bestssd){
	  besti=i;
	  bestj=j;
	  bestssd = ssd[i][j];
	}
    
    location[besti] = bestj+1;
    // mark tile besti and model bestj as found
    for(i=0; i<16; i++){
      ssd[besti][i] = -1;
      ssd[i][bestj] = -1;
    }
  }


  // print location array to screen
  for(i=0; i<16; i++)
    fprintf(stdout, "%d ", location[i]);
  printf("\n");
  
}


int getSSD(GrayImage im1, GrayImage im2)
{
  int x, y;
  int ssd=0;
  int width, height;

  if(imGetWidth(im1)<imGetWidth(im2)) width = imGetWidth(im1);
  else width = imGetWidth(im2);

  if(imGetHeight(im1)<imGetHeight(im2)) height = imGetHeight(im1);
  else height = imGetHeight(im2);

  /* DO SSD */
  for (y=0; y < height; y++)
    for (x=0; x < width; x++) 
      {
	int d = imRef(im1, x, y)
	  - imRef(im2, x, y);
	ssd += d*d;	   
      }	 
  return ssd;
}