/******************************************************************************
This class find the dominant colors of an image:
1. RGB->CIEL*a*b*
2. calculate the number of pixels in any colors
   (using hash-table to save memory, not good when lots of colors in the image)
3. find the dominant colors

Options:
1. Use class QuanLab to get the index of a CIELab color, and the QuanLab use
   3 quantilization arguments, m_lShrinkFactor, m_aShrinkFactor, and m_bShrinkFactor
2. TCD, MAX_CLUSTER_NUM, MAX_CLUSTERED_PXL (see the comments)
@deprecated replaced by DPU_DominantColor
******************************************************************************/

package yi.iu.processor.color;

import yi.iu.processor.*;

import yi.iu.ui.*;
import yi.util.io.*;

import java.awt.*;
import java.util.*;

public class DominantColor extends yi.iu.processor.ImageProcessor
{
    /**
     * Minmum distance of two color clusters.  If the distance of two
     * clusters is less than this number, they will be merged.
     */
    double MIN_CLUSTER_DIST = 9;

    /**
     * Maximum number of color cluster.
     */
    int MAX_CLUSTER_NUM=20;

    /**
     * Maximum number of clustered pixels.  If the number of clustered pixels
     * are higher than this number, the clustering algorithm will stop.  This
     * value is represented in percentage.
     */
    double MAX_CLUSTERED_PXL=0.75;

    /**
     * It is currently not used.  This can be used to stop the clustering
     * algorithm.  It is the minimum size of the color bin qualified to consider.
     * If no color bin can satify this rule, then stop.
     */
    double MIN_CLR_BIN_SIZE=0.18;

    /**
     * At the final step, every pixel will be assigned to a closest dominant color.
     * This is only true when their distance is not greater than this maximum
     * assignable distance.
     */
    double MAX_ASSGN_DIST=100;

    /**
     * A CIEL*a*b* color will be first indexed and put into a hashtable (as
     * histogram).  This is the length of a bin for component L
     */
    int L_SHRINK_FACTOR = 3;

    /**
     * A CIEL*a*b* color will be first indexed and put into a hashtable (as
     * histogram).  This is the length of a bin for component a*
     */
    int A_SHRINK_FACTOR = 3;

    /**
     * A CIEL*a*b* color will be first indexed and put into a hashtable (as
     * histogram).  This is the length of a bin for component b*
     */
    int B_SHRINK_FACTOR = 3;

    int COLOR_HASHTABLE_INIT_SIZE = 1000;

    boolean VERBOSE = false;

    public DominantColor() {super();}

    public DominantColor(double mincd, int maxcn, double maxcp, double maxad,
      int lsf, int asf, int bsf) {
        super();
        MIN_CLUSTER_DIST =mincd;
        MAX_CLUSTER_NUM  =maxcn;
        MAX_CLUSTERED_PXL=maxcp;
        MAX_ASSGN_DIST   =maxad;
        L_SHRINK_FACTOR  = lsf;
        A_SHRINK_FACTOR  = asf;
        B_SHRINK_FACTOR  = bsf;
    }

    public int getArguNum() { return 4;}

    public void setArgument(int i, String st)
    {
        if (st.length()==0) return;
        if (i==0) MIN_CLUSTER_DIST= Integer.valueOf(st).intValue();
        else if (i==1) MAX_CLUSTER_NUM= Integer.valueOf(st).intValue();
        else if (i==2) MAX_CLUSTERED_PXL= Double.valueOf(st).doubleValue();
        else if (i==3) MAX_ASSGN_DIST= Double.valueOf(st).doubleValue();
    }

    public String getArgument(int i)
    {
        if (i==0) return (String.valueOf(MIN_CLUSTER_DIST));
        else if (i==1) return (new Integer(MAX_CLUSTER_NUM)).toString();
        else if (i==2) return (new Double(MAX_CLUSTERED_PXL)).toString();
        else if (i==3) return (new Double(MAX_ASSGN_DIST)).toString();
        return null;
    }

    public String getArguName(int i)
    {
        if (i==0) return "MIN_CLUSTER_DIST";
        else if (i==1) return "Tnc";
        else if (i==2) return "Tnp";
        else if (i==3) return "Tassign";
        return null;
    }

    public int[] getProcessed(int source[], Dimension d)
    {
        // This method is derived from class yi.iu.processor.ImageProcessor
        // to do: code goes here
        return null;
    }

    /**
     * The main process of DominantColor.  Given an image in integer (0xffrrggbb)
     * array, it return the dominant colors.
     *
     * @param source Source image stored in integer array.  (0xffrrggbb format).
     * @param d Dimension of the image.
     * @param label Output the image in terms of the label of dominant colors.
     *              The dominant colors are returned as an array.  The array
     *              index is used to represent to which dominant color a pixel
     *              is clustered.  If there are N dominant colors, then the
     *              valid values of this label array are 0,..,N.  If a pixel is
     *              assigned to no dominant color, a N is assigned to it.
     * @return An array storing the dominant colors.  Each dominant color is
     *         a 3-length double array having the values of L, a, b.
     */
    public double[][] getProcessed_ex(int source[], Dimension d, int[] label)
    {
        // get the CIE L*a*b* color space
        if (VERBOSE) System.err.println("Get the dominant colors");

        int[] lab= CIELab.rgb2lab(source);  // adjusted labs

        // index the color values
        // and make a histogram with respect to those index
        // in a bin, a integer array used to store:
        // 0: the total number of color index falling into this bin
        // 1: the summary of value of l component of those lab colors
        // 2: the summary of value of a component of those lab colors
        // 3: the summary of value of b component of those lab colors
        if (VERBOSE) System.err.println("  Quantilization");

        LabIndexMaker lab_index =
          new LabIndexMaker(L_SHRINK_FACTOR, A_SHRINK_FACTOR, B_SHRINK_FACTOR);
        int indexSize= lab_index.size();

        Hashtable hist= new Hashtable(COLOR_HASHTABLE_INIT_SIZE);
        int i, index;
        for (i=0;i<lab.length;i++) {
            index= lab_index.getIndex(lab[i]);
            if (index>=indexSize) {
                System.err.println("  index:"+index+" >="+indexSize);
                continue;
            }
            Object key= new Integer(index);
            if (hist.containsKey(key)) {
                int[] info= (int[])hist.get(key);
                info[0]++;
                info[1]+=CIELab.getL(lab[i]);
                info[2]+=CIELab.getA(lab[i]);
                info[3]+=CIELab.getB(lab[i]);
            }
            else {
                int[] info={1,
                  CIELab.getL(lab[i]),CIELab.getA(lab[i]),CIELab.getB(lab[i])};
                hist.put(key,info);
            }
        }

        if (VERBOSE) System.err.println("  non-empty="+hist.size()+" %="+hist.size()/(double)indexSize);

        //clustering
        if (VERBOSE) System.err.println("  Clustering");
        int[][] cluster= new int[MAX_CLUSTER_NUM][4];   //store the info of cluster
                                            //[0]-size [1]-sum of L [2]-sum of a
                                            //[3]-sum of b
        int cNum=0;                         //number of cluster
        int consideredNum=0;                //number of considered pixel

        int j=0;
        int loopC=0;    // total loop number of the clustering
        int Tcs= (int)(Math.min(100, Math.sqrt(lab.length)*MIN_CLR_BIN_SIZE));
                // threshold for the num of color bin considered
        double Td= MIN_CLUSTER_DIST;
                // minmum distance between two cluster to not be merged
        while (true){
            //System.err.println("Considered .. "+consideredNum);

            // find the color with the most pixels
            int max=0;
            int[] max_info=null;
            for (Enumeration e = hist.elements() ; e.hasMoreElements() ;) {
                int[] info=(int[])e.nextElement();
                if (info[0]>max) {
                    max=info[0];max_info=info;
                }
            }
            if (max ==0) break;

            // find the distance of that color to all the existing clusters
            double close_d = Td;    //the smallest distance
            int    close_i=-1;      //the cluster with smallest distance
            for (j=0;j<cNum;j++) {
                double dist=CIELab.edistance(
                    cluster[j][1]/(double)cluster[j][0],
                    cluster[j][2]/(double)cluster[j][0],
                    cluster[j][3]/(double)cluster[j][0],
                      max_info[1]/(double)max_info[0],
                      max_info[2]/(double)max_info[0],
                      max_info[3]/(double)max_info[0]
                    );
                if (dist < close_d) {
                    close_d = dist; close_i = j;
                }
            }

            //if no cluster close to this color, new a cluster
            if (close_i<0) {
                cluster[cNum]=(int[])(max_info.clone());
                cNum++;
                max_info[0]=0; //mark the color to considered
            }
            //combine with the closest cluseer
            else {
                cluster[close_i][0]+=max_info[0];
                cluster[close_i][1]+=max_info[1];
                cluster[close_i][2]+=max_info[2];
                cluster[close_i][3]+=max_info[3];
                max_info[0]=0; //mark the color to considered
            }
            consideredNum+= max;
            loopC++;

            /*
            if (consideredNum>(int)(lab.length*MAX_CLUSTERED_PXL)
                ||cNum>=MAX_CLUSTER_NUM
                ||max<Tcs)
                    break;
            */
            // new break condition:
            // Number of clusters got >= MAX_CLUSTER_NUM
            // Considered pixel number >= MAX_CLUSTERED_PXL
            if (consideredNum>(int)(lab.length*MAX_CLUSTERED_PXL)) break;
            if (cNum>=MAX_CLUSTER_NUM) {
                // if after merge, number of clusters got get smaller, continue
                cNum= merge(cluster, cNum, Td);
                if (cNum < MAX_CLUSTER_NUM) break;
                // loose the merge threshold, and try again
                Td ++;
                cNum= merge(cluster, cNum, Td);
                // after merge, the number of cluster may remain the same.
                // However, in the next step of clustering, after a new color
                // is considered and merged into a existing cluster, the
                // distances may change and new merge may happen
                if (VERBOSE) System.out.println("  considered pixels = "+consideredNum/(double)lab.length);
                if (VERBOSE) System.out.println("  use new Threshold for distance = "+Td);
            }
        }
        if (VERBOSE) System.err.println("  Done");
        if (VERBOSE) System.err.println("  total clusters = "+cNum);
        if (VERBOSE) System.err.println("  considered pixels = "+consideredNum/(double)lab.length);
        if (VERBOSE) System.err.println("  loop counter = "+loopC);

        //combine the close clusters
        cNum= merge(cluster, cNum, Td);
        if (VERBOSE) System.err.println("  after post-combine, cluster number is "+cNum);

        //calculate the mean color of the clusters
        double[][] cluster_color= new double[cNum][3];
        for (i=0;i<cNum;i++) {
            cluster_color[i][0]= cluster[i][1]/(double)cluster[i][0];
            cluster_color[i][1]= cluster[i][2]/(double)cluster[i][0];
            cluster_color[i][2]= cluster[i][3]/(double)cluster[i][0];
        }

        //assign the pixel to dominant colors
        for (i=0;i<source.length;i++) {
            //find the distance of that color to all the existing clusters
            double close_d=MAX_ASSGN_DIST;    //the smallest distance
            int close_i=-1;     //the cluster with smallest distance
            for (j=0;j<cNum;j++) {
                double dist=CIELab.edistance(cluster[j][1]/(double)cluster[j][0],
                    cluster[j][2]/(double)cluster[j][0],
                    cluster[j][3]/(double)cluster[j][0],
                    lab[i]>>24,
                    (lab[i]>>12)&0xfff,
                    lab[i]&0xfff
                    );
                if (dist<=close_d) {
                    close_d=dist; close_i=j;
                }
            }
            //if no cluster close to this color, new a cluster
            if (close_i<0) {
                label[i]=cNum;
            }
            else {
                label[i]=close_i;
            }
        }

        lab=null;hist=null;cluster=null;System.gc();
        return cluster_color;
    }


    //draw the un-decided as red
    public int[] getProcessedPseudoColor(int source[], Dimension d)
    {
        int[] label= new int[source.length];
        double[][] cluster_color= getProcessed_ex(source,d,label);
        int cNum=cluster_color.length;
        int i;

        //transfer the color space
        int[] clusterColor = new int[cluster_color.length];
        for (i=0; i<cluster_color.length; i++)
          clusterColor[i] = CIELab.lab2rgb(cluster_color[i]);

        ///* make the spectrum of the clustered colors
        makeSpectrum(clusterColor, 30, 60);
        int[][] rgb= new int[cNum][3];
        for (i=0;i<cNum;i++) {
            rgb[i][0]=(clusterColor[i]>>16)&0xff;
            rgb[i][1]=(clusterColor[i]>>8)&0xff;
            rgb[i][2]=(clusterColor[i])&0xff;
        }
        OutputResult.outputResult("clusted_color", rgb);
        //*/

        int[] demo= new int[source.length];
        for (i=0;i<source.length;i++) {
            if (label[i]==cNum) demo[i]=0xffff0000;
            else demo[i]=clusterColor[label[i]];
        }
        (new SegFrame("cluster", demo, d.width, d.height , label)).show();
        int[] cluster_img= yi.util.ImageUtil.makeNewImageFromLabel(label);
        (new SegFrame("colored-line", cluster_img, d.width, d.height, label)).show();
        //(new DisplayFrame("cluster", demo, d)).show();

        return demo;
    }


    /**
     * <p>
     * The class is to index a color instance in CIE L*a*b* space.  It will
     * return an integer as the index.
     * </p>
     *
     * <p>
     * A lab value is in format of 0xllaaabbb, where
     * </p>
     *
     * <pre>
     * l:[0..100], a:[0..1000], b:[0..400]
     * </pre>
     *
     * <p>
     * An index will be very big if we let lab as it is.  So first the values on
     * l, a, and b will be shrinked by a shrink factor, say 3, then the biggest
     * index will be only 1/9 of the one before
     * </p>
     *
     * <p>
     * Example: Suppose the shrink factors are 3 for every component of a Lab
     * color.  The ranges of Lab will be [0,33], [0,333], [0,133].  A color
     * (50, 200, 300) will be shrinked to (16, 66, 100), and the index
     * is 16*333*133+66*133+100
     * </p>
     */
    class LabIndexMaker {

        int m_lShrinkFactor = 3;
        int m_aShrinkFactor = 3;
        int m_bShrinkFactor = 3;

        int m_sizeL =  100/m_lShrinkFactor+1;
        int m_sizeA = 1000/m_aShrinkFactor+1;
        int m_sizeB =  400/m_bShrinkFactor+1;

        int m_sizeAB = m_sizeA * m_sizeB;

        public LabIndexMaker(int lShrinkFactor, int aShrinkFactor, int bShrinkFactor) {
          m_lShrinkFactor = lShrinkFactor;
          m_aShrinkFactor = aShrinkFactor;
          m_bShrinkFactor = bShrinkFactor;
        }

        /**
         * Given a lab color in format of 0xllaabb, return its index.
         * @param lab a lab color.
         * @return the index.
         */
        int getIndex(int lab) {
            int l=(lab>>24)&0xff;
            int a=(lab>>12)&0xfff;
            int b=(lab)&0xfff;
            l/=m_lShrinkFactor;a/=m_aShrinkFactor;b/=m_bShrinkFactor;

            return (l* m_sizeAB + a * m_sizeB + b);
        }

        /**
         * @return the shrinked size of lab space
         */
        int size() {
            return m_sizeL * m_sizeA * m_sizeB;
        }
    }

    //make a spectrum to represent all the colors int the c array
    void makeSpectrum(int[] c, int w, int h){
        int numC= c.length;
        System.err.println(numC);
        int w0= w*numC;
        int[] img= new int[w0*h];
        for (int i=0;i<numC;i++) {
            for (int j=0;j<w;j++) {
                for (int y=0;y<h;y++) {
                    img[y*w0+i*w+j]=c[i];
                }
            }
        }
        (new PPMSaver()).getProcessed(img, new Dimension(w0,h));
    }

    int merge(int[][] cluster, int cNum, double Td)
    {
        int i,j;
        int old_cNum;
        do {
          old_cNum = cNum;
          for (i=0;i<cNum-1;i++) {
              for (j=i+1;j<cNum;j++) {
                  double dist=CIELab.edistance(
                      cluster[j][1]/(double)cluster[j][0],
                      cluster[j][2]/(double)cluster[j][0],
                      cluster[j][3]/(double)cluster[j][0],
                      cluster[i][1]/(double)cluster[i][0],
                      cluster[i][2]/(double)cluster[i][0],
                      cluster[i][3]/(double)cluster[i][0]
                      );
                  if (dist<MIN_CLUSTER_DIST) {
                      //combine
                      cluster[i][0]+=cluster[j][0];
                      cluster[i][1]+=cluster[j][1];
                      cluster[i][2]+=cluster[j][2];
                      cluster[i][3]+=cluster[j][3];
                      //shift the clusters to eliminate the combined
                      for (int k=j;k<cNum-1;k++)
                          cluster[k]=cluster[k+1];
                      cNum--;
                  }
              }
          }
        } while (cNum != old_cNum);
        return cNum;
    }

}