// ========================================================================================
// Quick implementation of the paper
// "Seam Carving for Content-Aware Image Resizing"
// by Shai Avidan and Ariel Shamir (http://www.faculty.idc.ac.il/arik/)
//
// Implementation:
// Cuneyt Ozdas (http://www.cuneytozdas.com)
// 2007.10.23
// ========================================================================================

// ========================================================================================
// Globals (ouch!)
// ========================================================================================
PImage src_im;
PImage eng_im;
boolean show_cut = false;
int    disp_mode = 0;
int[] best_path;
boolean inserted = false;

// ========================================================================================
// Implementation functions
// ========================================================================================
void ComputeEnergy(PImage src, PImage dst)
{
  int w = src.width;
  int h = src.height;

  for(int y=01;y<h;++y)
  {
    int ym = y>0   ? -w : 0;
    int yp = y<h-1 ? w : 0;
    for(int x=0;x<w;++x)
    {
      int xm = x>0   ? -1 : 0;
      int xp = x<w-1 ? 1 : 0;
      int idx = y*w+x;

      float dx = abs(brightness(src.pixels[idx+xm])-brightness(src.pixels[idx+xp]));
      float dy = abs(brightness(src.pixels[idx+ym])-brightness(src.pixels[idx+yp]));
      int e = int(abs(dx)+abs(dy));

      dst.pixels[idx] = color(0,0,e,128);
    }
  }
}

//________________________________________________________________________________________
boolean FindBestPath(PImage e_img, int[] best_path)
{
  int w = e_img.width;
  int h = e_img.height;

  PImage cum_img = createImage(w, h, RGB );
  //copy first row
  for(int x=0;x<w;++x)
  {
    color c = e_img.pixels[x];
    cum_img.pixels[x] =int( blue(c)+red(c)-green(c));
    //print(cum_img.pixels[x]);
  }

  //build cumulative energy array
  for(int y=1;y<h;++y)
  {
    for(int x=0;x<w;++x)
    {
      int didx = y*w+x;
      int sidx = didx-w;

      color c = e_img.pixels[didx];
      int ce = int(blue(c)+red(c)-green(c));
      int me = cum_img.pixels[sidx];
      if(x>0)
        me = min(me, cum_img.pixels[sidx-1]);
      if(x<w-1)
        me = min(me, cum_img.pixels[sidx+1]);

      cum_img.pixels[didx] = ce + me;
    }
  }

  //last row has the end of the best route. find it
  int min_e = 1<<30;
  int min_x = -1;
  int idx = (h-1)*w;
  for(int x=0;x<w;++x)
  {
    int ce = cum_img.pixels[idx+x];
    if(ce<min_e)
    {
      min_e = ce;
      min_x = x;
    }
  }
  if(min_x==-1)
    return false;

  //starting from there, find the best path
  int x=min_x;
  for(int y=h-1;y>0;--y)
  {
    idx = y*w+x;
    //e_img.pixels[idx] = color(255,255,0);
    best_path[y] = x;

    int me = cum_img.pixels[idx-w];
    int mx = x;

    if(x>0 && cum_img.pixels[idx-w-1]<me)
    {
      me=cum_img.pixels[idx-w-1];
      mx=x-1;
    }

    if(x<w-1 && cum_img.pixels[idx-w+1]<me)
    {
      me=cum_img.pixels[idx-w+1];
      mx=x+1;
    }
    x=mx;
  }

  return true;
}

//________________________________________________________________________________________
void DeleteColumn(PImage old_im, PImage new_im, PImage old_en, PImage new_en, int[] path)
{
  int sw = old_im.width;
  int dw = sw-1;
  int h = old_im.height;

  //delete the path pixels
  for(int y=0;y<h;++y)
  {
    int rx = path[y];
    for(int x=0;x<rx;++x)
    {
      new_im.pixels[y*dw+x] = old_im.pixels[y*sw+x];
      new_en.pixels[y*dw+x] = old_en.pixels[y*sw+x];
    }

    for(int x=rx;x<dw;++x)
    {
      new_im.pixels[y*dw+x] = old_im.pixels[y*sw+x+1];
      new_en.pixels[y*dw+x] = old_en.pixels[y*sw+x+1];
    }
  }  

  //re-compute the Energy along the path
  for(int y=0;y<h;++y)
  {
    int rx = path[y];
    int minx = max(0,rx-1);
    int maxx = min(dw-1,rx+1);

    int ym = y>0   ? -dw : 0;
    int yp = y<h-1 ? dw : 0;

    for(int x=minx;x<maxx;++x)
    {
      int xm = x>0   ? -1 : 0;
      int xp = x<dw-1 ? 1 : 0;
      int idx = y*dw+x;

      float dx = abs(brightness(new_im.pixels[idx+xm])-brightness(new_im.pixels[idx+xp]));
      float dy = abs(brightness(new_im.pixels[idx+ym])-brightness(new_im.pixels[idx+yp]));
      int e = int(abs(dx)+abs(dy));
      
      color c=  new_en.pixels[idx];
      new_en.pixels[idx] = color(red(c),green(c),e,128);
    }
  }

}

//________________________________________________________________________________________
void InsertColumn(PImage old_im, PImage new_im, PImage old_en, PImage new_en, int[] path)
{
  int sw = old_im.width;
  int dw = sw+1;
  int h = old_im.height;

  color high_energy = color(0,0,128);

  for(int y=0;y<h;++y)
  {
    //left
    int rx = path[y];
    for(int x=0;x<rx;++x)
    {
      new_im.pixels[y*dw+x] = old_im.pixels[y*sw+x];
      new_en.pixels[y*dw+x] = old_en.pixels[y*sw+x];
    }

    //right
    for(int x=rx;x<sw;++x)
    {
      new_im.pixels[y*dw+x+1] = old_im.pixels[y*sw+x];
      new_en.pixels[y*dw+x+1] = old_en.pixels[y*sw+x];
    }

    //cut line for image
    if(rx==0)
      new_im.pixels[y*dw+rx] = old_im.pixels[y*sw+rx];
    else
    { 
      color ca = old_im.pixels[y*sw+rx-1];
      color cb = old_im.pixels[y*sw+rx];
      color c = color(int(red(ca)+red(cb))>>1, int(green(ca)+green(cb))>>1, int(blue(ca)+blue(cb))>>1);
      new_im.pixels[y*dw+rx] = c;
    }

    //cutline for energy
    new_en.pixels[y*dw+rx] = high_energy;
    if(rx>0)
      new_en.pixels[y*dw+rx-1] = high_energy;
    if(rx<dw-1)
      new_en.pixels[y*dw+rx+1] = high_energy;
  }  

}

//________________________________________________________________________________________
void DrawPath(int x_off, int y_off, int h, int[] path)
{
  for(int y=0;y<h;y++)
  {
    set(x_off+path[y], y_off+y, color(255,0,0));
  }
}

//________________________________________________________________________________________
void DrawImage(PImage im)
{
  image(im, (width-im.width)>>1, (height-im.height)>>1); 
}

//________________________________________________________________________________________
void LoadImage(String num)
{
  src_im = loadImage(num+".jpg");

  int w = src_im.width;
  int h = src_im.height;

  eng_im = createImage(w, h, RGB );
  ComputeEnergy(src_im, eng_im);
}

//________________________________________________________________________________________
void PaintEnergy(PImage im, int x, int y, boolean pos)
{
  
  int w = im.width;
  int h = im.height;

  if(x<0 || y<0 || x>=w || y>=h)
    return;

  int brsize = 4;
  int xn = max(0, x-brsize);
  int xp = min(w-1, x+brsize);
  int yn = max(0, y-brsize);
  int yp = min(h-1, y+brsize);
  
  im.loadPixels();

  for(int i=xn;i<xp;i++)
  {
    for(int j=yn;j<yp;j++)
    {
      color oe = im.pixels[j*w+i];

      if(pos)
        im.pixels[j*w+i] = color(255, green(oe), blue(oe), 128);
      else
        im.pixels[j*w+i] = color(red(oe), 255, blue(oe), 128);
    }
  }
  
  im.updatePixels();
}

// ========================================================================================
// Processing Core Functions
//========================================================================================
void setup() 
{
  size(600, 300);

  LoadImage("1");
  //noLoop();
  redraw();

}

//________________________________________________________________________________________
void draw()
{
  background(255);

  //println("frame rate: " + str(frameRate));
  int w = src_im.width;
  int h = src_im.height;

  best_path = new int[h];
  FindBestPath(eng_im, best_path);

  //show the image
  switch(disp_mode)
  {
  case 0:
    DrawImage(src_im);
    break;

  case 1:
    DrawImage(eng_im);
    break;

  case 2:
  case 3:
    {
      DrawImage(src_im);
      DrawImage(eng_im);
    }
    break;
  }

  //show the cut
  if(show_cut)
    DrawPath((width-w)>>1,  (height-h)>>1, h, best_path);

}

//________________________________________________________________________________________
void keyPressed()
{
  switch(key)
  {
  case '1':
  case '2':
  case '3':
  case '4':
  case '5':
  case '6':
  case '7':
  case '8':
  case '9':
    LoadImage(str(key));
    break;

  case 'c': 
    show_cut = !show_cut; 
    break;

  case 'i': 
    disp_mode=0; 
    break;

  case 'e': 
    disp_mode=1; 
    break;

  case 'p':
    disp_mode = 2;
    break;

  case 'n':
    disp_mode = 3;
    break;

  case CODED:
    switch(keyCode)
    {
    case LEFT:    
      {
        //re compute the energies if there were inserts (causes inserted lines to be removed first)
        if(inserted)
          ComputeEnergy(src_im, eng_im);

        PImage new_im = createImage(src_im.width-1, src_im.height, RGB );
        PImage new_en = createImage(eng_im.width-1, eng_im.height, RGB );
        DeleteColumn(src_im, new_im, eng_im, new_en, best_path);
        src_im = new_im;
        eng_im = new_en;
        inserted=false;
      }
      break;

    case RIGHT:  
      {  
        PImage new_im = createImage(src_im.width+1, src_im.height, RGB );
        PImage new_en = createImage(eng_im.width+1, eng_im.height, RGB );   
        InsertColumn(src_im, new_im, eng_im, new_en, best_path);
        src_im = new_im;
        eng_im = new_en;
        inserted=true;
      }
      break;
    }
    break;
  }

  redraw();
}


//________________________________________________________________________________________
void mouseDragged()
{
  if(disp_mode!=2 && disp_mode!=3)
    return;

  int w = eng_im.width;
  int h = eng_im.height;

  int x = mouseX-((width-w)>>1);
  int y = mouseY-((height-h)>>1);
  
  PaintEnergy(eng_im, x,y, disp_mode==2);

  
  redraw();

  //println(str(x)+","+str(y));
}