/*Diana Negoescu '09
 * program 'reads' a road sign using shape context
 * execution: java Method2 picture_name.jpg
 */ 

import java.awt.Color;

public class Method2{
  
  //function that computes the luminance of a pixel
  public static double lum(Color color){
    int r=color.getRed();
    int g=color.getGreen();
    int b=color.getBlue();
    return .299*r+.587*g+.114*b;
  }
  
  //function that transforms a picture into a black and white one of same
  //dimension
  public static Picture blackwhite(String filename){
    Picture source=new Picture(filename);
    int w=source.width();
    int h=source.height();
    Picture result=new Picture(w,h);
    Color black=new Color(0,0,0);
    Color white=new Color(255, 255, 255);
    double max=0.0;
    double min=255.0;
    double av=0;
    for (int i=0; i<h; i++){
      for (int j=0; j<w; j++){
        Color color=source.get(j,i);
        av=av+lum(color);
      }
    }
    av=av/(w*h);
    for (int i=0; i<h; i++){
      for (int j=0; j<w; j++){
        Color color=source.get(j,i);
        if (lum(color)>av+50) result.set(j,i,white);
        else result.set(j,i,black);
      }
    }
    result.show();
    return result;
    
  }
  
  //label each pixel according to which object it belongs to
  public static void floodfillstack(Picture pic, int[][] a, Stack s, Color c,
                                    int k){ 
    while (!s.isEmpty()){
      Stack.Node x=s.pop();
      if ((x.i>=pic.height())||(x.j>=pic.width())||(x.i<0)||(x.j<0)){
        continue;
      }
      Color col=pic.get(x.j,x.i);
      if (col.equals(Color.BLACK)) continue;
      if (a[x.i][x.j]!=0) continue;
      s.push(x.i+1,x.j);
      s.push(x.i,x.j-1);
      s.push(x.i-1,x.j);
      s.push(x.i,x.j+1);
      a[x.i][x.j]=k;
    }
  }
  
  
  static boolean less(double x, double y) {
    return (x < y);
  }
  
  static void exch(Letter[] a,int[] mmin, int i, int j) {
    Letter swapl = a[i];
    a[i] = a[j];
    a[j] = swapl;
    int swap=mmin[i];
    mmin[i]=mmin[j];
    mmin[j]=swap;
  } 
  
  static int partition(Letter[] a, int[] mmin, int left, int right) {
    int i = left - 1;
    int j = right;
    
    while(true) { 
      while (less(mmin[++i], mmin[right]))   // left pointer
        if (i == right) break;
      
      while (less(mmin[right], mmin[--j]))   // right pointer
        if (j == left) break;
      
      if (i >= j) break;               // pointers cross?
      
      exch(a, mmin, i, j);                   // swap left and right
    }
    
    exch(a, mmin, i, right);                  // swap pivot
    return i;
  }
  
  public static void quicksortgen(Letter[] a, int b, int i, int[] mmin) {
    quicksort(a, mmin, b, i);
  }
  
  private static void quicksort(Letter[] a,int[] mmin, int left,int right){
    if (right <= left) return;
    int i = partition(a, mmin, left, right);
    quicksort(a, mmin, left, i-1);
    quicksort(a, mmin, i+1, right);
  }
  
  
  //function that extracts the letters from a 'flood' matrix
  public static Letter[] extract(int[][] a, int h, int w, int k){
    
    //create an array of letters
    Letter[] letters=new Letter[k-1];
    int[] mmin=new int[k-1];
    int[] jmin=new int[k-1];
    int[] jmax=new int[k-1];
    for (int i=1; i<k; i++){
      
      //find out the maximum and minimum coordinates of each letter
      jmin[i-1]=h;
      jmax[i-1]=0;
      mmin[i-1]=w;
      int mmax=0;
      for (int j=0; j<h; j++){
        for (int m=0; m<w; m++){
          if ((a[j][m]==i)&&(j<jmin[i-1])) 
            jmin[i-1]=j;
          if ((a[j][m]==i)&&(j>jmax[i-1])) 
            jmax[i-1]=j;
          if ((a[j][m]==i)&&(m<mmin[i-1])) 
            mmin[i-1]=m;
          if ((a[j][m]==i)&&(m>mmax)) mmax=m;
        }
      }
      
      //create a smaller matrix just fitting the letter
      int[][] x=new int[jmax[i-1]-jmin[i-1]+1][mmax-mmin[i-1]+1];
      
      //put 1's where the letter's pixels were
      for (int j=0; j<h; j++){
        for (int m=0; m<w; m++){
          if (a[j][m]==i) {
            x[j-jmin[i-1]][m-mmin[i-1]]=1;
          }
        }
      }
      
      //pad the matrix on the edges because some pixels will be lost in the canny edge detection
      int[][] matbig=new int[x.length+14][x[0].length+14];
      for (int j=0; j<matbig.length; j++){
        for (int m=0; m<matbig[0].length; m++){
          if ((j<7)||(j>=x.length+7)||(m<7)||(m>=x[0].length+7))
            matbig[j][m]=0;
          else matbig[j][m]=x[j-7][m-7];
        }
      }
      
      letters[i-1]=new Letter(matbig);
    }
    
    
    int b=0;
    
    //sort the letters
    for (int i=0; i<k-2; i++){
      if (jmax[i]<jmin[i+1]) {
        //sort the objects on the same line so that they are in the right order
        quicksortgen(letters, b, i, mmin);
        b=i+1;
      }
    }
    quicksortgen(letters, b, k-2, mmin);
    
    
    return letters;
  }
  
  
  public static Letter scale(Letter a,int H, int W){
    int h=a.height();
    int w=a.width();
    int[][] m=new int[H][W];
    for (int i=0; i<H; i++){
      for (int j=0; j<W; j++){
        double x=(h*i)/H;
        double y=(w*j)/W;
        int ii=(int) Math.round(x);
        int jj=(int) Math.round(y);
        if ((ii>=0)&&(ii<h)&&(jj>=0)&&(jj<w))
          m[i][j]=a.get(ii,jj);
      }
    }
    return new Letter(m);
  }
  
  
  public static int compare(Letter a, Letter r){
    int dif=0;
    for (int i=0; i<a.height(); i++){
      for (int j=0; j<a.width(); j++){
        int x=a.get(i,j);
        int y=r.get(i,j);
        if (x!=y) dif++;
      }
    }
    return dif;
  }
  
  public static void correlation(Letter[] reference, Letter[] letters){
    int H=reference[0].height();
    int W=reference[0].width();
    //scale the letters
    for (int i=0; i< letters.length; i++){
      letters[i]=scale(letters[i], H, W);
    }
    
    //compare each letter to the database
    for (int i=0; i<letters.length; i++){
      int min =H*W;
      for (int j=0; j<reference.length; j++){
        int dif=compare(letters[i], reference[j]);
        if (dif<min) min=dif;
      }
      for (int j=0; j<reference.length; j++){
        int dif=compare(letters[i], reference[j]);
        if (dif==min){
          System.out.print(reference[j].character());
        }
      }
    }
  }
  
  //function that performs a rows convolution given the vector and a picture
  public static double[][] convolutionrows(double[] gx, double[][] pic){
    
    //compute the matrix after the convolution
    double[][] x=new double[pic.length][pic[0].length-4];
    for (int i=0; i<pic.length; i++){
      for (int j=2; j<pic[0].length-2; j++){
        for (int k=0; k<gx.length; k++){
          x[i][j-2]+=gx[k]*pic[i][ j-2+k];
        }
      }
    }
    return x;
  }
  
  //function that performs a columns convolution given the vector a picture
  public static double[][] convolutioncolumns(double[] gy, double[][] pic){
    
    //compute the matrix after the convolution
    double[][] x=new double[pic.length-4][pic[0].length];
    for (int i=2; i<pic.length-2; i++){
      for (int j=0; j<pic[0].length; j++){
        for (int k=0; k<gy.length; k++){
          x[i-2][j]+=gy[k]*pic[i-2+k][j];
        }
      }
    }
    return x;
  }
  
  
  //compute the value of the gaussian function at a point x, given sigma
  public static double gauss(double sigma, double x){
    return ((1.0/(sigma*Math.sqrt(2*Math.PI)))*
            Math.exp(-x*x/(2*sigma*sigma)));
  }
  
  //set up a vector that samples the function at -2, -1, 0, 1 and 2
  public static double[] gaussvec(double sigma){
    double[] vec=new double[5];
    double s=0.0;
    for (int i=0; i<5; i++){
      vec[i]=gauss(sigma, (double) i-2);
      s=s+vec[i];
    }
    for (int i=0; i<5; i++){
    }
    
    return vec;
  }
  
  //set up the vector of the derivative of the gaussian at points -2,-1,0,1,2
  public static double[] gaussdervec(double sigma){
    double[] vec= new double[5];
    
    for (int i=0; i<5; i++){
      vec[i]=(-2*(double)(i-2)/(sigma*sigma))*gauss(sigma, (double) (i-2));
    }
    
    
    return vec;
  }
  
  public static Picture canny(Picture pic, double sigma, double tlow, double thigh){
    //compute the luminance matrix
    double[][] lumin=new double[pic.height()][pic.width()];
    for (int i=0; i<pic.height(); i++){
      for (int j=0; j<pic.width(); j++){
        Color c=pic.get(j,i);
        lumin[i][j]=lum(c) / 255;
      }
    }
    
    //turn the picture into grayscale    
    Picture pic2=new Picture(pic.width(), pic.height());
    for (int i=0; i<pic.height(); i++){
      for (int j=0; j<pic.width(); j++){
        int c=(int) lumin[i][j];
        Color color=new Color(c,c,c);
        pic2.set(j,i,color);
        
      }
    }
    double[] g=gaussvec(sigma);
    double[] gder=gaussdervec(sigma);
    double[][] x1=convolutionrows(gder, lumin);
    double[][] x2=convolutioncolumns(g, x1);
    double[][] y1=convolutionrows(g, lumin);
    double[][] y2=convolutioncolumns(gder, y1);
    double[][] gradmagn=new double[lumin.length-4][lumin[0].length-4];
    double[][] graddir=new double[lumin.length-4][lumin[0].length-4];
    double max=0;
    double min=Double.POSITIVE_INFINITY;
    
    //fill the matrices of the gradient magnitude and direction
    for (int i=0; i<gradmagn.length; i++){
      for (int j=0; j<gradmagn[0].length; j++){
        gradmagn[i][j]=Math.sqrt(x2[i][j]*x2[i][j]+y2[i][j]*y2[i][j]);
        if (gradmagn[i][j]>max) max=gradmagn[i][j];
        if (gradmagn[i][j]<min) min=gradmagn[i][j];
        graddir[i][j]=Math.atan2(y2[i][j],x2[i][j]);
      }
    }
    Picture result;
    result=new Picture(pic.width()-4, pic.height()-4);
    
    
    //create a grayscale picture  using the gradient
    double x;
    for (int i=0; i<pic.height()-4; i++){
      for (int j=0; j<pic.width()-4; j++){
        x=255*(gradmagn[i][j]-min)/(max-min);
        int col=(int) Math.round(x);
        Color c=new Color(col,col,col);
        result.set(j,i,c);
      }
    }
    
    double[][] rough_edge=new double[gradmagn.length-2][gradmagn[0].length-2];
    for (int i=1; i<graddir.length-1; i++){
      for (int j=1; j<graddir[0].length-1; j++){
        rough_edge[i-1][j-1]=gradmagn[i][j];
       
        //make sure the direction is in the right quadrant
        if (graddir[i][j]<-Math.PI/2) graddir[i][j]+=Math.PI;
        if (graddir[i][j]>Math.PI/2) graddir[i][j]-=Math.PI; 
        
        //'kill' the pixels that are not edges
        if ((graddir[i][j]<-3*Math.PI/8.0) || (3*Math.PI/8<=graddir[i][j])) {
          if ((gradmagn[i][j]<gradmagn[i-1][j])||(gradmagn[i][j]<gradmagn[i+1][j]))
            rough_edge[i-1][j-1]=0;
        }
        else if ((-3*Math.PI/8<=graddir[i][j])&&(graddir[i][j]<-Math.PI/8.0)){
          if ((gradmagn[i][j]<gradmagn[i-1][j+1])||(gradmagn[i][j]<gradmagn[i+1][j-1]))
            rough_edge[i-1][j-1]=0;
        }
        else if ((-Math.PI/8<=graddir[i][j])&&(graddir[i][j]<Math.PI/8.0)){
          if ((gradmagn[i][j]<gradmagn[i][j+1])||(gradmagn[i][j]<gradmagn[i][j-1]))
            rough_edge[i-1][j-1]=0;
        }
        else {
          if ((gradmagn[i][j]<gradmagn[i+1][j+1])||(gradmagn[i][j]<gradmagn[i-1][j-1]))
            rough_edge[i-1][j-1]=0;
        }
      }
    }
    max=0;
    min=Double.POSITIVE_INFINITY;
    for (int i=0; i<rough_edge.length; i++){
      for (int j=0; j<rough_edge[0].length; j++){
        if (rough_edge[i][j]>max) max=rough_edge[i][j];
        if (rough_edge[i][j]<min) min=rough_edge[i][j];
      }
    }
    //normalize the values
    Picture result2=new Picture(rough_edge[0].length, rough_edge.length); 
    for (int i=0; i<rough_edge.length; i++){
      for (int j=0; j<rough_edge[0].length; j++){
        x=255*(rough_edge[i][j]-min)/(max-min);
        int col=(int) Math.round(x);
        Color c=new Color(col,col,col);
        result2.set(j,i,c);
      }
    }
    
    //do the hysteresis
    
    for (int i=1; i<rough_edge.length-1; i++){
      for (int j=1; j<rough_edge[0].length-1; j++){
        if (rough_edge[i][j]-min<tlow*(max-min)) rough_edge[i][j]=0;
        else if (rough_edge[i][j]-min<thigh*(max-min)) {
          if (!((rough_edge[i][j+1]-min>thigh*(max-min))||
                (rough_edge[i][j-1]-min>thigh*(max-min))||
                (rough_edge[i+1][j]-min>thigh*(max-min))||
                (rough_edge[i-1][j]-min>thigh*(max-min))||
                (rough_edge[i+1][j+1]-min>thigh*(max-min))||
                (rough_edge[i-1][j-1]-min>thigh*(max-min))||
                (rough_edge[i-1][j+1]-min>thigh*(max-min))||
                (rough_edge[i+1][j-1]-min>thigh*(max-min)))){
            rough_edge[i][j]=0;
          }
        }
      }
    }
    
    
    for (int i=0; i<rough_edge.length; i++){
      for (int j=0; j<rough_edge[0].length; j++){
        if (rough_edge[i][j]!=0) rough_edge[i][j]=255;
      }
    }
    Picture result3=new Picture(rough_edge[0].length-2, rough_edge.length-2); 
    for (int i=0; i<rough_edge.length-2; i++){
      for (int j=0; j<rough_edge[0].length-2; j++){
        int col=(int) rough_edge[i+1][j+1];
        Color c=new Color(col,col,col);
        result3.set(j,i,c);
      }
    }
    return result3;
  }
  
  public static double cost(Circle c1, Circle c2){
    double s=0;
    for (int i=0; i<c1.getsectors()*c1.getshells(); i++){
      if (!((c1.distribution()[i]==0)&&(c2.distribution()[i]==0)))
        s+=((c1.distribution()[i]-c2.distribution()[i])*(c1.distribution()[i]-c2.distribution()[i])/
            (c1.distribution()[i]+c2.distribution()[i]));
    }
    return s;
  }
  
  public static double[][] costmat(Nodep[] p1, Nodep[] p2){
    Circle[] circ1=new Circle[100];
    for (int i=0; i<100; i++){
      circ1[i]=new Circle(p1[i], p1, 8, 5, 2);
    }
    Circle[] circ2=new Circle[100];
    for (int i=0; i<100; i++){
      circ2[i]=new Circle(p2[i], p2, 8, 5, 2);
    }
    double[][] costmat=new double[100][100];
    for (int i=0; i<100; i++){
      for (int j=0; j<100; j++){
        costmat[i][j]=cost(circ1[i],circ2[j]);
      }
    }
    
    return costmat;
  }
  
  public static Picture scalepic(Picture a,int H, int W){
    int h=a.height();
    int w=a.width();
    Picture pic=new Picture(W, H);
    for (int i=0; i<W; i++){
      for (int j=0; j<H; j++){
        double x=(w*i)/W;
        double y=(h*j)/H;
        int ii=(int) Math.round(x);
        int jj=(int) Math.round(y);
        if ((ii>=0)&&(ii<w)&&(jj>=0)&&(jj<h)){
          Color c=a.get(ii,jj);
          pic.set(i,j,c);
        }
      }
    }
    return pic;
  }
  
  public static double matsum(double[][] m){
    double s=0;
    for (int i=0; i<m.length; i++){
      for (int j=0; j>m[0].length; j++){
        s=s+m[i][j];
      }
    }
    return s;
  }
  
  public static void main(String[] args){
    String filename="database.txt";
    In in=new In(filename);
    //read the database file
    int N=in.readInt();
    int h=in.readInt();
    int w=in.readInt();
    Letter[] reference=new Letter[N];
    for (int i=0; i<N; i++){
      String c=in.readString();
      int[][] m=new int[h][w];
      for (int j=0; j<h; j++){
        String x=in.readString(); 
        for (int k=0; k<w; k++){
          m[j][k]=Integer.parseInt(x.substring(k, k+1));   
          
        }
      }
      int[][] matbig=new int[m.length+14][m[0].length+14];
      for (int j=0; j<matbig.length; j++){
        for (int k=0; k<matbig[0].length; k++){
          if ((j<7)||(j>=m.length+7)||(k<7)||(k>=m[0].length+7))
            matbig[j][k]=0;
          else matbig[j][k]=m[j-7][k-7];
        }
      }
      reference[i]=new Letter(matbig, c.charAt(0));
    }
    
    
    Letterpic[] referencepic=new Letterpic[N];
    for (int i=0; i<N; i++){
      referencepic[i]=new Letterpic(reference[i].getmat(), reference[i].character());
      referencepic[i]=new Letterpic(canny(referencepic[i].getpic(), 1, 0, 0.2), reference[i].character());
    }
    
    //read the file to be scanned
    String file=args[0];
    Picture pic=new Picture(file);
    pic.show();
    Picture pic2=blackwhite(file);
    //create a matrix of the same dimension as the picture, storing
    //the labels that say to which object each pixel corresponds 
    int[][] a=new int[pic2.height()][pic2.width()];
    int k=1;
    Stack s=new Stack();                  
    
    //floodfill until every pixel has been visited
    for (int i=0; i<pic2.height(); i++){
      for (int j=0; j<pic2.width(); j++){  
        if (a[i][j]==0) {
          Color c=pic2.get(j,i);
          if (c.equals(Color.WHITE)) {
            s.push(i,j);
            floodfillstack(pic2, a, s, c,k);      
            k++;
          }
        }
      }
    }
    
    
    //generate the array of letters
    Letter[] letters=new Letter[k-1];
    letters=extract(a,pic.height(),pic.width(),k);
    Letterpic[] lets=new Letterpic[k-1];
    char c=' ';
    for (int i=0; i<k-1; i++){
      lets[i]=new Letterpic(letters[i].getmat(),c);
      lets[i]=new Letterpic(canny(lets[i].getpic(), 1, 0, 0.2), c);
    }
    
    //create 100 random points on the edge of each reference letter
    Nodep[][] selpoints=new Nodep[referencepic.length][100];
    for (int q=0; q<referencepic.length; q++){
      
      //find out how many white points there are on the edge of the letter
      int count=0;  
      
      for (int i=0; i<referencepic[q].getpic().width(); i++){
        for (int j=0; j<referencepic[q].getpic().height(); j++){
          Color color=referencepic[q].getpic().get(i,j);
          if (color.equals(Color.WHITE)) count++;
        }
      }
      
      //store all the white points in an array
      Nodep[] points=new Nodep[count];
      count=0;
      for (int i=0; i<referencepic[q].getpic().width(); i++){
        for (int j=0; j<referencepic[q].getpic().height(); j++){
          Color color=referencepic[q].getpic().get(i,j);
          if (color.equals(Color.WHITE)){
            points[count++]=new Nodep(j,i);
            
          }
        }
      }
      
      // get 100 random points and put them in the matrix
      for (int i=0; i<100; i++){
        int r1=(int) (count * Math.random());
        selpoints[q][i]=points[r1];
      }
    }
    
    
    for (int q=0; q<k-1; q++){
      int count=0;  
      for (int i=0; i<lets[q].getpic().width(); i++){
        for (int j=0; j<lets[q].getpic().height(); j++){
          Color color=lets[q].getpic().get(i,j);
          if (color.equals(Color.WHITE)) count++;
        }
      }
      
      //create an array with all the points on the edge
      Nodep[] points=new Nodep[count];
      count=0;
      for (int i=0; i<lets[q].getpic().width(); i++){
        for (int j=0; j<lets[q].getpic().height(); j++){
          Color color=lets[q].getpic().get(i,j);
          if (color.equals(Color.WHITE)){
            points[count++]=new Nodep(j,i);
            
          }
        }
      }
      
      Nodep[] selpointlet=new Nodep[100];
      //get 100 random points on the edge
      for (int i=0; i<100; i++){
        int r1=(int) (count * Math.random());
        selpointlet[i]=points[r1];
      }
      double min=Double.POSITIVE_INFINITY;
      double[] costarray=new double[referencepic.length];
      for (int i=0; i< referencepic.length; i++){
        double[][] cost=costmat(selpoints[i], selpointlet);
        String m="min";
        int[][] match=HungarianAlgorithm.hgAlgorithm(cost, m);
        //compute the total cost associated with the matching
        double sum=0;
        for (int j=0; j<100; j++){
          Circle c1=new Circle(selpoints[i][j], selpoints[i], 8,5, 2);
          Circle c2=new Circle(selpointlet[match[j][1]], selpointlet, 8, 5, 2);
          sum=sum+cost(c1, c2);
        }
        costarray[i]=sum;
        if (sum<min) min=sum;
      }
      for (int i=0; i<referencepic.length; i++){
        if (costarray[i]==min) System.out.print(referencepic[i].character());
      }
    } 
  }
}