 //============================================================================
 //Name        : segment.h   : The implementation of plate segmentation
 //============================================================================
#include <stdio.h>
#include <highgui.h>

#define MAX_NUM_CLUSTERS	6
#define MAX_VECTOR_SIZE		10
#define AVG_ERROR_THRESHOLD	1
#define MAX_KMEAN_DATA_SIZE 8000
#define MAX_COORDINATE_SIZE 8000
#define SHOWSEGMENT 

typedef struct KMeanTag
{
	int ** kMeanClusterCenters;
	int ** kMeanClusterCentersBuf;
	int *  kMeanClusterRatios;		
	int ** kMeanDataBuf;
	unsigned char * dataLabel;

	int nKMeanClusters;
    //.................
    int **Coordinates;
	//.................

}KMeanType;
void kMeanInit(KMeanType * KM)
{
	int n, nKMeanClusters;

	KM->kMeanDataBuf = (int **)malloc(MAX_KMEAN_DATA_SIZE * sizeof(int *));
	for(n=0;n<MAX_KMEAN_DATA_SIZE; n++)
		KM->kMeanDataBuf[n] = (int *)malloc(MAX_VECTOR_SIZE * sizeof(int));

	KM->kMeanClusterCenters = (int **)malloc(MAX_NUM_CLUSTERS * sizeof(int *));
	for(n=0; n<MAX_NUM_CLUSTERS; n++)
		KM->kMeanClusterCenters[n] = (int *)malloc(MAX_VECTOR_SIZE * sizeof(int));

	KM->kMeanClusterCentersBuf = (int **)malloc(MAX_NUM_CLUSTERS * sizeof(int *));
	for(n=0; n<MAX_NUM_CLUSTERS; n++)
		KM->kMeanClusterCentersBuf[n] = (int *)malloc(MAX_VECTOR_SIZE * sizeof(int));

	KM->kMeanClusterRatios = (int *)malloc(MAX_NUM_CLUSTERS * sizeof(int));

	KM->dataLabel = (unsigned char *)malloc(MAX_KMEAN_DATA_SIZE);

	//.................
    KM->Coordinates = (int **)malloc(MAX_COORDINATE_SIZE * sizeof(int*));
	for(n=0;n<MAX_COORDINATE_SIZE; n++)
		KM->Coordinates[n] = (int *)malloc(MAX_VECTOR_SIZE * sizeof(int));
	//.................

	//KM->nKMeanClusters = 2;
	//if(nKMeanClusters > MAX_NUM_CLUSTERS) nKMeanClusters = MAX_NUM_CLUSTERS;

}



int kMeanClustering(int ** data, int nPoints, int nDim, int nClusters, KMeanType * KM)
{
	int stepLen, threshold;
	int n, N0, N1, k, i, nIterations;
	int avg, tmp, diff, minDist, minPtr, ct, dist, contFlag;
	int ** tmpBuf;
	int flag;
	int ** kMeanClusterCenters;
	int ** kMeanClusterCentersBuf;
	int *  kMeanClusterRatios;	
	unsigned char * dataLabel;

	if (nPoints < (4 * nClusters)) return -1;

	kMeanClusterCenters = KM->kMeanClusterCenters;
	kMeanClusterCentersBuf = KM->kMeanClusterCentersBuf;
	kMeanClusterRatios = KM->kMeanClusterRatios;
	dataLabel = KM->dataLabel;

	//initial clusters;
	stepLen = nPoints / nClusters;

	for(n=0; n<nClusters; n++)
	{
		N0 = n * stepLen;
		N1 = (n+1) * stepLen;

		if(n == (nClusters-1))	N1 = nPoints;

		if((N1 - N0) < 1) N1 = N0 + 1;

		for(i=0; i<nDim; i++)
		{	
			avg = 0;
			for(k=N0; k<N1; k++)
				avg = avg + data[k][i];

			avg = avg / (N1 - N0);
			kMeanClusterCenters[n][i] = avg;
		}
	}

	contFlag = 1;
	nIterations = 0;

	while(contFlag == 1)
	{
		for(k=0;k<nClusters; k++)
		for(i=0; i<nDim; i++)
			kMeanClusterCentersBuf[k][i] = 0;

		for(k=0; k<nClusters; k++)
			kMeanClusterRatios[k] = 0;

		for(n=0; n<nPoints; n++)
		{
			minDist = 1000000000;
			for(k=0; k<nClusters; k++)
			{
				//find the distance to each cluster center
				tmp = 0;
				for(i=0; i<nDim; i++)
				{
					diff = data[n][i] - kMeanClusterCenters[k][i];
					tmp = tmp + diff * diff;
				}

				if(tmp < minDist)
				{
					minDist = tmp;
					minPtr = k;
				}
			}

			//assign the label
			dataLabel[n] = minPtr;

			//assign this point to the minPtr cluster
			for(i=0;i<nDim; i++)
				kMeanClusterCentersBuf[minPtr][i] = kMeanClusterCentersBuf[minPtr][i] + data[n][i];

			kMeanClusterRatios[minPtr] = kMeanClusterRatios[minPtr] + 1;
		}

		//now update the new cluster center
		dist = 0;

		for(k=0; k<nClusters; k++)
		{
			ct = kMeanClusterRatios[k];

			if(ct > 2)
			{
				for(i=0;i<nDim; i++)
					kMeanClusterCentersBuf[k][i] = kMeanClusterCentersBuf[k][i] / ct;
			}
			else
			{
				//use the old one
				for(i=0;i<nDim; i++)
					kMeanClusterCentersBuf[k][i] = kMeanClusterCenters[k][i];
			}

			for(i=0; i<nDim; i++)
			{
				diff = kMeanClusterCenters[k][i] - kMeanClusterCentersBuf[k][i];
				if(diff < 0) diff = -diff;

				dist = dist + diff;
			}

		}

		//decide to loop again or not
		threshold = nClusters * nDim * AVG_ERROR_THRESHOLD;
		if((nIterations > 20) || (dist < threshold)) 
			contFlag = 0;

		//switch the center buffers
		tmpBuf = kMeanClusterCenters;
		kMeanClusterCenters = kMeanClusterCentersBuf;
		kMeanClusterCentersBuf = tmpBuf;

		nIterations++;
	}

	//output the percentage
	for(k=0; k<nClusters; k++)
		kMeanClusterRatios[k] = (100 * kMeanClusterRatios[k])/nPoints;

	return 1;
}
//END: K-Mean Clustering-----------------------------------------------------------------
void segments(unsigned char * frame, int widthStep, int X0, int Y0, int X1, int Y1, KMeanType * KM, int *xx, int *ss)    //Good One 
{
	//Variables for part1
	int r, c, step, ct, n, thr;
	unsigned char * ptrFrame;    
	int ** kMeanClusterCenters;
	int *  kMeanClusterRatios;	
	int ** kMeanDataBuf;
	int ** Coordinates;
	unsigned char * dataLabel;
	int  nPoints;
	int num_zeros;

	//variables for part2
	int x, y, i, j, avg;
	int * histo = (int *)malloc((X1- X0) * sizeof(int));
    int max, final_x, final_s;
	long total;

	double q= 2.5;  //a character is q times the length of a "."
	int s;          //the scale of "."  : the number of pixels a "." occupies
	int s0= 0;
    int more= 0;     //more pixels beyond the plate's edge on both sides
    int space= 2;   //length of space
	int w_char;     //width of a chracter: q*s
	int score[7];
    //-------------------------------------------------------------------------
	//PART ONE: Make the plate binary. Foreground 1, background 0
	kMeanClusterCenters = KM->kMeanClusterCenters;
	kMeanClusterRatios = KM->kMeanClusterRatios;
	kMeanDataBuf = KM->kMeanDataBuf;
    Coordinates = KM->Coordinates;
    dataLabel = KM->dataLabel;

    thr = MAX_KMEAN_DATA_SIZE - 2;
	n = 0;
	for(r=Y0; r<Y1; r++)
	for(c=X0; c<X1; c++)
	{
			    //sample the pixel
				ptrFrame = frame + r * widthStep + c * 3;
				for(i= 0; i<3; i++)
				{
				  kMeanDataBuf[n][i] = ptrFrame[i];
				}
				Coordinates[n][0] = c;
                Coordinates[n][1] = r;
				n++;

				if(n > thr) 
				{
					printf("Overflow\n");
					n = thr;			//now overflow
				}
	}
	
   //do k-means to seperate foreground from background
   nPoints= (X1-X0)*(Y1-Y0);
   kMeanClustering(kMeanDataBuf , nPoints , 3, 2, KM);
   
   //Separate the foreground from the background
   num_zeros= 0;
   for (n= 0; n< nPoints; n++)
   {
	   if( dataLabel[n]== 0)  num_zeros++;  //number of foreground pixels
   }
   //if foreground is the plate , background is the plate characters, switch their clusters
   if (num_zeros > nPoints- num_zeros)   //white character pixels should be smaller than blue plate pixels, if not, switch
   {
	   for (n= 0; n< nPoints; n++)
	   {
			dataLabel[n]= 1- dataLabel[n];  //0 becomes 1 and 1 becomes 0.
	   }
   }
   //paint black on foreground and white on background
   for (n= 0; n< nPoints; n++)
   {
	   ptrFrame= frame + Coordinates[n][1] * widthStep + Coordinates[n][0] * 3;
      for( i= 0; i<3; i++)
	  {
		  ptrFrame[i]= ( dataLabel[n]== 0 ? 0 : 255);   //if a pixel belongs to foreground, then it's 0, painted black
	  }
   }

   //Make the edges clear
    for (x= X0, y= Y0; x< X1, y<Y1; x++, y++)
   {
         //UP and bottom
         if (   (y< Y0+2)||(y> Y1-2)  )
       {
          ptrFrame= frame + y * widthStep + x * 3;   //saves computation if put inside "if"
	      ptrFrame[0]= ptrFrame[1]= ptrFrame[2]= 255;
        }
         //left and right
         else if (   (x< X0+2)||(x> X1-2)   ) 
       {
          ptrFrame= frame + y * widthStep + x * 3;
	      ptrFrame[0]= ptrFrame[1]= ptrFrame[2]= 255;
       }
   } 
   //-----------------------------------------------------------------------------------//
   //PART TWO: Segment based on the binaried image
   //histo was all 0s at the beginning
   for( x= 0; x< X1- X0; x++) histo[x]= 0;

   for (n= 0; n< nPoints; n++)
   {
	   ptrFrame= frame + Coordinates[n][1] * widthStep + Coordinates[n][0] * 3;
	   x= Coordinates[n][0]- X0;
	   if (ptrFrame[0]== 0)   histo[x]++;   //accumulate character(black) pixels   
   }  
   //-------------------------------------------------------------
   //Don't do binarization here!!
   //--------------------------------------------------------------
   max= 10;
   final_x= X0;
   final_s= 1;
   for(i=0; i<7; i++) score[i]= 0; 
   total= 0;
   //find optimum x and s
   for ( x= X0- more; x<= X0+ int(q*(X1-X0+ more)/(7*q+1)); x++)  
	   for(s= 1; s<= int((X1- x + more)/(7*q+1)); s++)  
	   {
		    s0= 0;
            for (i= 0; i<7; i++)
			{
			   if(i==2) s0= s;
			   for( n= x+ i*q*s + s0; n< x+ (i+1)*q*s + s0; n++)
			   {
			       if( (n< X1)&&(n>=X0) )   score[i]+= ( n< x+ (i+1)*q*s + s0 - space)? histo[n- X0]:((-1)* histo[n- X0]);  
			   }
			}	
		   total= score[0]+ score[6]+ (score[1]+score[2]+score[3]+score[4]+score[5]);
           if (total > max)
		   {
			   max= total;
			   final_x= x;
			   final_s= s;
		   }
		   total= 0;
		   for(i=0; i< 7; i++)  score[i]= 0; 	   
	   }
	   *xx= final_x;
	   *ss= final_s;
    
     //printf("frame is: (%d)\n", frame);
     //printf("(final_x, final_s) is: (%d, %d)\n", final_x, final_s);
	 //printf("(Y0, Y1) is: (%d, %d)\n", Y0, Y1);
	 //Draw the segmenting lines
#ifdef SHOWSEGMENT
     for (y= Y0; y<Y1; y++)
   {
	   for ( i= 0; i<8; i++)
	   {
	       x= final_x+ (i*q)*final_s;
		   ptrFrame= frame + y * widthStep + x * 3;	
		    //if (i==1) //printf("ptrFrame is: (%d)\n", ptrFrame);
		   if(i> 1)
	      {   
	        ptrFrame+= 3*final_s;    
	      }
		   ptrFrame[0]= 255;  ptrFrame[1]= ptrFrame[2]= 0;   
		   ptrFrame -= 3*space;	 
	       ptrFrame[0]= 255;  ptrFrame[1]= ptrFrame[2]= 0; 
	   }
	    ptrFrame= frame + y * widthStep + int(final_x+ 2*q*final_s- space)* 3;	
	    ptrFrame[0]= 255;  ptrFrame[1]= ptrFrame[2]= 0; 
	 }	
#endif
 
}
void show_segment(unsigned char * frame, int widthStep, int Y0, int Y1, int *xx, int *ss )
{
	int i, x, y, q=2.5, space= 2;
	int final_x= *xx;
	int final_s= *ss;
	printf("frame is: (%d)\n", frame);
	printf("(final_x, final_s) is: (%d, %d)\n", final_x, final_s);
	printf("(Y0, Y1) is: (%d, %d)\n", Y0, Y1);
	unsigned char * ptrFrame;
	 //Draw the segmenting lines
     for (y= Y0; y<Y1; y++)
   {
	   for ( i= 0; i<8; i++)
	   {
	       x= final_x+ (i*q)*final_s;
		   ptrFrame= frame + y * widthStep + x * 3;	
		   if (i==1) printf("ptrFrame is: (%d)\n", ptrFrame);
		   if(i> 1)
	      {   
	        ptrFrame+= 3*final_s;    
	      }
		   ptrFrame[0]= 0;  ptrFrame[1]= ptrFrame[2]= 255;   
		   ptrFrame -= 3*space;	 
	       ptrFrame[0]= 0;  ptrFrame[1]= ptrFrame[2]= 255; 
	   }
	    ptrFrame= frame + y * widthStep + int(final_x+ 2*q*final_s- space)* 3;	
	    ptrFrame[0]= 255;  ptrFrame[1]= ptrFrame[2]= 0; 
	 }	
}
