package yi.iu.processor.clc;

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

import yi.iu.processor.line.*;
import yi.iu.processor.ort.*;
import yi.ai.cluster.KMCluster;
import yi.util.config.*;
import yi.util.io.*;
import yi.iu.processor.color.*;
import yi.stat.em.*;
import yi.math.*;
import yi.stat.hist.*;
import yi.stat.em.GaussianComponent;



/**
 * CLC_KMeansColorPair clusters lines by their color pair using K-Means
 */

public class CLC_KMeansColorPair extends KMCluster implements Configurable{

  public boolean DEMO_COLOR_CLC = true;
  public boolean DEMO_COLOR_CLC_REGION = false;

  public double MIN_COLOR_VARIANCE = 5 * 5;

  public final static int POST_NONE = 0;
  public final static int POST_DISTANCE_CLASSIFY = 1;
  public final static int POST_GAUSSIAN_CLASSIFY = 2;
  public int POST_CLASSIFY = POST_GAUSSIAN_CLASSIFY;

  public String[] getParameterNames() {
    return new String[] {
        "POST_CLASSIFY",
    };
  }

  public CLC_KMeansColorPair(){
    Configuration.configParameters(this);
  }


  /**
   * A mean is 6-vector, the first 3 element represent RGB color on one side,
   * and the second 3 elements represent another.  A vector is 9-vector, the
   * first 3 element represent RGB color on one side, the second 3 elements
   * represent RGB color on the line, and the third 3 elements represent RGB
   * color on the right.
   * @param info
   * @param means
   * @param best_cp
   * @param no_empty
   * @return
   */
  public int[] clusteringByColorPair(int[][] info, int[][] means,  int[][] best_cp, boolean no_empty)
  {

    this.K = means.length;
    this.initMethod = PREDEFINED;
    this.data = info;
    this.info_len = means[0].length;
    this.init_means = yi.util.data.CloneUtil.clone(means);

    int size=info.length;       // number of data to be classified

    label= new int[info.length];      //store the result of labeling
    int i,j,m,n,temp;
    int ic=1;
    boolean changed=true;

    //used when re-calculate the means before the iteration step
    long[][] sum= new long[K][info_len];
    int[] num= new int[K];


    while (changed) {
        //find the minimum distance for each vector
        for (i=0;i<size;i++) {
            double min_dist = lineColorPairDistance(info[i], means[0], best_cp[i], info_len);
            int min_dist_index = 0; //remember the index of the mean with the minimum distance
            int[] cp = new int[6];
            for (m=1; m<K; m++) {
                double d = lineColorPairDistance(info[i], means[m], cp, info_len);
                if (min_dist > d) {
                  min_dist = d;
                  min_dist_index = m;
                  for (j=0; j<cp.length; j++) best_cp[i][j] = cp[j];
                }
            }
            // assign the data to the closest cluster
            label[i]= min_dist_index;
        }
        //recalculate the means
        for (m=0;m<K;m++) java.util.Arrays.fill(sum[m], 0);
        java.util.Arrays.fill(num, 0);
        for (i=0;i<size;i++) {
          temp=label[i];
          for (n=0;n<info_len;n++) sum[temp][n]+=best_cp[i][n];
          num[temp]++;
        }

        changed=false;
        long change_sum = 0;
        for (m=0;m<K;m++) {
            for (n=0;n<info_len;n++) {
                int new_mean = (num[m]==0)? means[m][n]: (int)Math.round((double)sum[m][n]/num[m]);
                if (means[m][n]==new_mean) continue;
                changed=true;
                change_sum += Math.abs(means[m][n] - new_mean);
                means[m][n] = new_mean;

            }
        }
        System.out.println("changes = " + change_sum);
    }

    // eliminate empty cluster
//        System.out.println("cluster_number before eliminate empty cluster = " + m_clusterNumber);
    if (no_empty) m_clusterNumber = eliminateEmptyCluster(label, means);
    this.means = new int[m_clusterNumber][info_len];
    for (i=0; i<m_clusterNumber; i++) {
      for (j=0; j<info_len; j++) this.means[i][j] = means[i][j];
    }

//        System.out.println("cluster_number after = " + m_clusterNumber);
    return label;
  }

  /**
   * Color Pairs of a line contain 3 rgb colors (left, mid, right).  A color
   * pair contains 2 colors.  Compare (left, mid), (mid, left), (mid, right),
   * (right, mid) to to_compare, and fill the best one to best_cp and return
   * the shortest distance.
   * @param colors
   * @param to_compare
   * @param best_cp
   * @param info_len
   * @return
   */
  public double lineColorPairDistance(int[] line_cps, int[] cp, int[] best_cp, int info_len) {
    int[][] colors = new int[][] {
        new int[] {line_cps[0], line_cps[1], line_cps[2]},
        new int[] {line_cps[3], line_cps[4], line_cps[5]},
        new int[] {line_cps[6], line_cps[7], line_cps[8]},
    };

    ColorPair best_match = new ColorPair();
    ColorPair color_pair = new ColorPair(
        ColorUtil.packRGB(cp[0], cp[1], cp[2]),
        ColorUtil.packRGB(cp[3], cp[4], cp[5])
        );

    double d = color_pair.bestMatch(colors, best_match);
    int[] best_x = ColorUtil.RGB2IntArray(best_match.x);
    int[] best_y = ColorUtil.RGB2IntArray(best_match.y);
    if (best_cp != null) combineColorPair(best_cp, best_x, best_y);
    return d;
/*
    int[] left = new int[] {line_cps[0], line_cps[1], line_cps[2]};
    int[] mid  = new int[] {line_cps[3], line_cps[4], line_cps[5]};
    int[] right= new int[] {line_cps[6], line_cps[7], line_cps[8]};

    int[] c1 = new int[] {cp[0], cp[1], cp[2]};
    int[] c2 = new int[] {cp[3], cp[4], cp[5]};

    // left, mid
    double min_distance = distance(left, mid, c1, c2);
    combineColorPair(best_cp, left, mid);

    // mid, left
    double distance = distance(mid, left, c1, c2);
    if (distance < min_distance) {
      min_distance = distance;
      combineColorPair(best_cp, mid, left);
    }

    // mid, right
    distance = distance(mid, right, c1, c2);
    if (distance < min_distance) {
      min_distance = distance;
      combineColorPair(best_cp, mid, right);
    }

    // right, mid
    distance = distance(right, mid, c1, c2);
    if (distance < min_distance) {
      min_distance = distance;
      combineColorPair(best_cp, right, mid);
    }

    // left, right
    distance = distance(left, right, c1, c2);
    if (distance < min_distance) {
      min_distance = distance;
      combineColorPair(best_cp, left, right);
    }

    // right, left
    distance = distance(right, left, c1, c2);
    if (distance < min_distance) {
      min_distance = distance;
      combineColorPair(best_cp, right, left);
    }

    for (int i=0; i<best_cp.length; i++) {
      if (best_cp[i] != best_cp2[i]) {
        if (VectorUtil.EuclideanDistance(best_cp, cp) != VectorUtil.EuclideanDistance(best_cp2, cp)) {
          OutputResult.print(System.err, best_cp);
          OutputResult.print(System.err, best_cp2);
          OutputResult.print(System.err, cp);
          System.err.println(VectorUtil.EuclideanDistance(best_cp, cp));
          System.err.println(VectorUtil.EuclideanDistance(best_cp2, cp));
          break;
        }
      }
    }
    return min_distance;
 */
  }

  double emModelProbability(GaussianComponent em_model, int[] data) {
    double prob = 0;
    double[] double_data = yi.util.data.Conversion.toDouble(data);
    try {
      prob = em_model.getDensity(double_data);
    } catch (GaussianModelSingularException e) {
      prob = 0;
    }
    return prob;
  }

  boolean gaussianModelFallsIn(SimplifiedEMCumulator em_model, int[] data, double threshold) {
    double[] double_data = yi.util.data.Conversion.toDouble(data);
    try {
      return em_model.fallenIn(double_data, threshold);
    } catch (GaussianModelSingularException e) {
    }
    return false;
  }

  public boolean lineColorPairBelongsTo(int[] line_cps, SimplifiedEMCumulator em_model,
                                       int[] best_cp, int info_len) {
    int[] left = new int[] {
        line_cps[0], line_cps[1], line_cps[2]};
    int[] mid = new int[] {
        line_cps[3], line_cps[4], line_cps[5]};
    int[] right = new int[] {
        line_cps[6], line_cps[7], line_cps[8]};

    int[] data = new int[6];
    boolean prob = false;
    double threshold = 2.63;
    double[] double_data = null;

    // left, mid
    combineColorPair(data, left, mid);
    prob = gaussianModelFallsIn(em_model, data, threshold);
    if (prob) {
      System.arraycopy(data, 0, best_cp, 0, 6);
      return true;
    }

    // mid, left
    combineColorPair(data, mid, left);
    prob = gaussianModelFallsIn(em_model, data, threshold);
    if (prob) {
      System.arraycopy(data, 0, best_cp, 0, 6);
      return true;
    }

    // mid, right
    combineColorPair(data, mid, right);
    prob = gaussianModelFallsIn(em_model, data, threshold);
    if (prob) {
      System.arraycopy(data, 0, best_cp, 0, 6);
      return true;
    }

    // right, mid
    combineColorPair(data, right, mid);
    prob = gaussianModelFallsIn(em_model, data, threshold);
    if (prob) {
      System.arraycopy(data, 0, best_cp, 0, 6);
      return true;
    }

    // left, right
    combineColorPair(data, left, right);
    prob = gaussianModelFallsIn(em_model, data, threshold);
    if (prob) {
      System.arraycopy(data, 0, best_cp, 0, 6);
      return true;
    }

    // right, left
    combineColorPair(data, right, left);
    prob = gaussianModelFallsIn(em_model, data, threshold);
    if (prob) {
      System.arraycopy(data, 0, best_cp, 0, 6);
      return true;
    }

    return false;
  }

  public double lineColorPairDistance(int[] line_cps, GaussianComponent em_model, int[] best_cp, int info_len) {
    int[] left = new int[] {line_cps[0], line_cps[1], line_cps[2]};
    int[] mid  = new int[] {line_cps[3], line_cps[4], line_cps[5]};
    int[] right= new int[] {line_cps[6], line_cps[7], line_cps[8]};

    int[] data = new int[6];
    double prob = 0;

    // left, mid
    combineColorPair(data, left, mid);
    prob = emModelProbability(em_model, data);
    double max_prob = prob;
    System.arraycopy(data, 0, best_cp, 0, 6);

    // mid, left
    combineColorPair(data, mid, left);
    prob = emModelProbability(em_model, data);
    if (prob > max_prob) {
      max_prob = prob;
      System.arraycopy(data, 0, best_cp, 0, 6);
    }

    // mid, right
    combineColorPair(data, mid, right);
    prob = emModelProbability(em_model, data);
    if (prob > max_prob) {
      max_prob = prob;
      System.arraycopy(data, 0, best_cp, 0, 6);
    }

    // right, mid
    combineColorPair(data, right, mid);
    prob = emModelProbability(em_model, data);
    if (prob > max_prob) {
      max_prob = prob;
      System.arraycopy(data, 0, best_cp, 0, 6);
    }

    // left, mid
    combineColorPair(data, left, mid);
    prob = emModelProbability(em_model, data);
    if (prob > max_prob) {
      max_prob = prob;
      System.arraycopy(data, 0, best_cp, 0, 6);
    }

    // mid, left
    combineColorPair(data, mid, left);
    prob = emModelProbability(em_model, data);
    if (prob > max_prob) {
      max_prob = prob;
      System.arraycopy(data, 0, best_cp, 0, 6);
    }

    // mid, right
    combineColorPair(data, mid, right);
    prob = emModelProbability(em_model, data);
    if (prob > max_prob) {
      max_prob = prob;
      System.arraycopy(data, 0, best_cp, 0, 6);
    }

    // right, mid
    combineColorPair(data, right, mid);
    prob = emModelProbability(em_model, data);
    if (prob > max_prob) {
      max_prob = prob;
      System.arraycopy(data, 0, best_cp, 0, 6);
    }

    // left, right
    combineColorPair(data, left, right);
    prob = emModelProbability(em_model, data);
    if (prob > max_prob) {
      max_prob = prob;
      System.arraycopy(data, 0, best_cp, 0, 6);
    }

    // right, left
    combineColorPair(data, right, left);
    prob = emModelProbability(em_model, data);
    if (prob > max_prob) {
      max_prob = prob;
      System.arraycopy(data, 0, best_cp, 0, 6);
    }
    return max_prob;
  };


  /**
   * Color Pairs (cp) contain 2 rgb colors (cc1, cc2).  The color pair to be
   * compared contains 2 colors (c1, c2).  Compare (cc1, cc2) and (cc2, cc1) to
   * to_compare (c1, c2), and fill the best one to best_cp and return
   * the shortest distance.
   * @param cp
   * @param to_compare
   * @param best_cp
   * @return
   */
  public double colorPairDistance(int[] cp, int[] to_compare, int[] best_cp) {
    int[] cc1 = new int[] {cp[0], cp[1], cp[2]};
    int[] cc2  = new int[] {cp[3], cp[4], cp[5]};

    int[] c1 = new int[] {to_compare[0], to_compare[1], to_compare[2]};
    int[] c2 = new int[] {to_compare[3], to_compare[4], to_compare[5]};

    // left, mid
    double min_distance = distance(cc1, cc2, c1, c2);
    combineColorPair(best_cp, cc1, cc2);

    // mid, left
    double distance = distance(cc2, cc1, c1, c2);
    if (distance < min_distance) {
      min_distance = distance;
      combineColorPair(best_cp, cc2, cc1);
    }

    // mid, right
    return min_distance;
  }

  /**
   * Calcuate the distance from rgb color pair (c1, c2) to rgb color pair
   * (cc1, cc2)
   * @param c1
   * @param c2
   * @param cc1
   * @param cc2
   * @return
   */
  double distance(int[] c1, int[] c2, int[] cc1, int[] cc2) {
    int[] v1 = new int[6];
    int[] v2 = new int[6];
    combineColorPair(v1, c1, c2);
    combineColorPair(v2, cc1, cc2);

    return yi.math.VectorUtil.EuclideanDistance(v1, v2);
  }

  /**
   * Copy rgb color c1 and rgb color c2 to 6-element vector cp
   * (r1,g1,b1,r2,g2,b2)
   * @param cp
   * @param c1
   * @param c2
   */
  static void combineColorPair(int[] cp, int[] c1, int[] c2) {
    cp[0] = c1[0];
    cp[1] = c1[1];
    cp[2] = c1[2];
    cp[3] = c2[0];
    cp[4] = c2[1];
    cp[5] = c2[2];
  }

  static int[] rgbMeanColorOnALine(ORTLine line, int LineThickness, int[] pixels, int img_width, int img_height)
  {
    int[] rgb_sum2 = line.rgbMeanColor(LineThickness, pixels, img_width, img_height);
    return rgb_sum2;
  }

  static int[] getColorPairs(ORTLine line, int[] pixels, int img_width, int img_height) {
    int[][] color_pairs = line.rgbMeanColors(1, pixels, img_width, img_height);
    int[] cps = new int[] {
        color_pairs[0][0],
        color_pairs[0][1],
        color_pairs[0][2],
        color_pairs[1][0],
        color_pairs[1][1],
        color_pairs[1][2],
        color_pairs[2][0],
        color_pairs[2][1],
        color_pairs[2][2],
    };

    return cps;
  }

  public LineClusterSets getClusters(LineClusterSet lines, int[] rgb, int width, int height) {
    // find the dominant colors
    DPU_DominantColor dpu_dc = new DPU_DominantColor();
    DS_DominantColor ds_dc = dpu_dc.getReusableDominantColors(rgb, width, height);
    // convert dominant colors
    Collection colors = ds_dc.getDominantColors();

    return clustering(new Vector(lines), ds_dc, colors, rgb, width, height);
  }

  public LineClusterSets clustering(Vector lines, DS_DominantColor ds_dc, Collection colors,
                                    int[] pixels, int width, int height) {
    int color_num = colors.size();
    int[][] m_colors = new int[colors.size()][];
    int it_count = 0;
    for (Iterator i = colors.iterator(); i.hasNext(); it_count++) {
      int rgb = CIELab.lab2rgb( (CIELab) i.next());
      m_colors[it_count] = yi.iu.processor.color.ColorUtil.RGB2IntArray(rgb);
    }

    // find the init means
    int[][] init_means = new int[color_num * (color_num - 1) / 2][6];
    for (int i = 0, count = 0; i < color_num - 1; i++) {
      for (int j = i + 1; j < color_num; j++, count++) {
        CLC_KMeansColorPair.combineColorPair(init_means[count], m_colors[i],
                                             m_colors[j]);
      }
    }

    // find the color pairs of each line
    int[][] data = new int[lines.size()][];
    it_count = 0;
    for (Iterator i = lines.iterator(); i.hasNext(); it_count++) {
      ORTLine l = (ORTLine) i.next();
      data[it_count] = CLC_KMeansColorPair.getColorPairs(l, pixels, width, height);
    }

    // cluster
    int[][] best_cp = new int[data.length][6]; // return the best color pair of left, right, and itself
    clusteringByColorPair(data, init_means, best_cp, true);

//    postMerge();
    LineClusterSets lcss = null;
    switch (POST_CLASSIFY) {
      case POST_NONE:
        lcss = postClassify(lines, pixels, width, height);
        break;
      case POST_GAUSSIAN_CLASSIFY:
        lcss = gaussianBasedClassify(lines, best_cp, pixels, width, height);
        break;
      case POST_DISTANCE_CLASSIFY:
        lcss = distanceBasedClassify(lines, pixels, width, height);
        break;
    }

    return lcss;

  }

  LineClusterSets postClassify(Vector lines, int[] pixels, int width, int height) {
    // the color pair of each cluster mean
    ColorPair[] cp_means = new ColorPair[m_clusterNumber];
    for (int i = 0; i < m_clusterNumber; i++) {
      int c1 = ColorUtil.packRGB(means[i][0], means[i][1], means[i][2]);
      int c2 = ColorUtil.packRGB(means[i][3], means[i][4], means[i][5]);
      cp_means[i] = new ColorPair(c1, c2);
    }

    LineClusterSets lcss = new LineClusterSets(width, height);
    int it_count = 0;
    for (Iterator i = lines.iterator(); i.hasNext(); it_count++) {
      ORTLine l = (ORTLine) i.next();
      lcss.add(cp_means[label[it_count]], l);
    }
    return lcss;
  }

  LineClusterSets distanceBasedClassify(Vector lines, int[] pixels, int width, int height) {
    // the color pair of each cluster mean
    ColorPair[] cp_means = new ColorPair[m_clusterNumber];
    for (int i = 0; i < m_clusterNumber; i++) {
      int c1 = ColorUtil.packRGB(means[i][0], means[i][1], means[i][2]);
      int c2 = ColorUtil.packRGB(means[i][3], means[i][4], means[i][5]);
      cp_means[i] = new ColorPair(c1, c2);
    }


    LineClusterSets lcss = new LineClusterSets(width, height);

    boolean STATISTICS = false;
    SimpleHistogram assign_hist = new SimpleHistogram(20); // for statistics

    int it_count = 0;
    for (Iterator i = lines.iterator(); i.hasNext(); it_count++) {
      ORTLine line = (ORTLine) i.next();

      int[] cp_mid = rgbMeanColorOnALine(line, 0, pixels, width, height);
      ORTLine shift_left = line.makeNewLineByAngleShift(1, Math.PI / 2);
      int[] cp_left = rgbMeanColorOnALine(shift_left, 0, pixels, width,
                                          height);
      ORTLine shift_right = line.makeNewLineByAngleShift(1, -Math.PI / 2);
      int[] cp_right = rgbMeanColorOnALine(shift_right, 0, pixels, width,
                                           height);

      int[] line_cps = new int[] {
          cp_left[0], cp_left[1], cp_left[2],
          cp_mid[0], cp_mid[1], cp_mid[2],
          cp_right[0], cp_right[1], cp_right[2]
      };

      int[] best_cp = new int[info_len];

      double threshold_d = 20;
      Set assign_to = new HashSet(); // store the close clusters
      double min_distance = 50000; // impossible big number
      int min_cluster = -1;

      for (int j = 0; j < m_clusterNumber; j++) {
        double d = lineColorPairDistance(line_cps, means[j], best_cp, info_len);
        // get the closest cluster
        if (d < min_distance) {
          min_distance = d;
          min_cluster = j;
        }
        // remember all the cluster closer than threshold
        if (d < threshold_d) assign_to.add(new Integer(j));
      }

      if (STATISTICS)  assign_hist.putToBin(assign_to.size());

      if (assign_to.size() == 0) { // classify it to the closest one
        lcss.add(cp_means[min_cluster], line);
      } else { // assign it to each close cluster
        for (Iterator it=assign_to.iterator(); it.hasNext();) {
          int to = ((Integer)it.next()).intValue();
          lcss.add(cp_means[to], line);
        }
      }

    }
    int[] assign_hist_bins = assign_hist.getHistogram();
    if (STATISTICS) OutputResult.print("assign_hist", assign_hist_bins);
    return lcss;

  }

  LineClusterSets gaussianBasedClassify(Vector lines, int[][] best_cps, int[] pixels, int width, int height) {

    // the color pair of each cluster mean
    ColorPair[] cp_means = new ColorPair[m_clusterNumber];
    for (int i = 0; i < m_clusterNumber; i++) {
      int c1 = ColorUtil.packRGB(means[i][0], means[i][1], means[i][2]);
      int c2 = ColorUtil.packRGB(means[i][3], means[i][4], means[i][5]);
      cp_means[i] = new ColorPair(c1, c2);
    }

    // the em model for each cluster
    SimplifiedEMCumulator[] em_models = new SimplifiedEMCumulator[m_clusterNumber];
    for (int i=0; i<m_clusterNumber; i++) em_models[i] = new SimplifiedEMCumulator(MIN_COLOR_VARIANCE);
    for (int i=0; i<best_cps.length; i++) {
      double[] best_data = yi.util.data.Conversion.toDouble(best_cps[i]);
      em_models[label[i]].add(best_data, 1); // prob = 1
    }

    LineClusterSets lcss = new LineClusterSets(width, height);

    boolean STATISTICS = false;
    SimpleHistogram assign_hist = new SimpleHistogram(20); // for statistics

    int it_count = 0;
    for (Iterator i = lines.iterator(); i.hasNext(); it_count++) {
      ORTLine line = (ORTLine) i.next();

      int[] cp_mid = rgbMeanColorOnALine(line, 0, pixels, width, height);
      ORTLine shift_left = line.makeNewLineByAngleShift(1, Math.PI / 2);
      int[] cp_left = rgbMeanColorOnALine(shift_left, 0, pixels, width,
                                          height);
      ORTLine shift_right = line.makeNewLineByAngleShift(1, -Math.PI / 2);
      int[] cp_right = rgbMeanColorOnALine(shift_right, 0, pixels, width,
                                           height);

      int[] line_cps = new int[] {
          cp_left[0], cp_left[1], cp_left[2],
          cp_mid[0], cp_mid[1], cp_mid[2],
          cp_right[0], cp_right[1], cp_right[2]
      };

      int[] best_cp = new int[info_len];

      Set assign_to = new HashSet(); // store the close clusters
/*
      for (int j = 0; j < m_clusterNumber; j++) {
        boolean b = lineColorPairBelongsTo(line_cps, em_models[j], best_cp, info_len);
        // remember all the cluster closer than threshold
        if (b) assign_to.add(new Integer(j));
      }
*/
int[][] colors = line.rgbMeanColors(1, pixels, width, height);
for (int j = 0; j < m_clusterNumber; j++) {
  boolean b = ColorPair.belongsTo(colors, em_models[j], null, 2.63);
  // remember all the cluster closer than threshold
  if (b) assign_to.add(new Integer(j));
}


      if (STATISTICS)  assign_hist.putToBin(assign_to.size());

      if (assign_to.size() == 0) { // classify it to the closest one
        double min_distance = 50000; // impossible big number
        int min_cluster = -1;

        for (int j = 0; j < m_clusterNumber; j++) {
//          double d = lineColorPairDistance(line_cps, means[j], best_cp, info_len);
          double d = cp_means[j].bestMatch(colors, null);
          // get the closest cluster
          if (d < min_distance) {
            min_distance = d;
            min_cluster = j;
          }
        }
        lcss.add(cp_means[min_cluster], line);

      } else { // assign it to each close cluster
        for (Iterator it=assign_to.iterator(); it.hasNext();) {
          int to = ((Integer)it.next()).intValue();
          lcss.add(cp_means[to], line);
        }
      }

    }
    int[] assign_hist_bins = assign_hist.getHistogram();
    if (STATISTICS) OutputResult.print("assign_hist", assign_hist_bins);
    return lcss;

  }


  /**
   * post merge the similar cluster
   */
  void postMerge() {
    double[][] dist_matrix = new double[m_clusterNumber][m_clusterNumber];
    SimpleHistogram hist = new SimpleHistogram(400);
    for (int i=0; i<m_clusterNumber-1; i++) {
      for (int j=i+1; j<m_clusterNumber; j++) {

        int[] mean_j_alternative = new int[] {
            means[j][3], means[j][4], means[j][5],
            means[j][0], means[j][1], means[j][2]
        };

        double min_dist = VectorUtil.EuclideanDistance(means[i], means[j]);
        double dist2 = VectorUtil.EuclideanDistance(means[i], mean_j_alternative);
        if (dist2 < min_dist) min_dist = dist2;
        dist_matrix[i][j] = min_dist;
        hist.putToBin((int)min_dist);
        if (min_dist < 30) {
          int[] colors = new int[] {
              yi.iu.processor.color.ColorUtil.packRGB(means[i][0], means[i][1], means[i][2]),
              yi.iu.processor.color.ColorUtil.packRGB(means[i][3], means[i][4], means[i][5]),
              yi.iu.processor.color.ColorUtil.packRGB(means[j][0], means[j][1], means[j][2]),
              yi.iu.processor.color.ColorUtil.packRGB(means[j][3], means[j][4], means[j][5]),
          };
          int[] cp_demo = yi.iu.processor.color.ColorUtil.createSpectrum(colors, 40, 40);
          OutputResult.outputGIFImage("cp_dist." + i + "." + j + "." + (int)min_dist + ".gif", cp_demo, 40*4, 40);
          System.out.println("color#" + i);
          System.out.println(" " + means[i][0] + "," + means[i][1] + "," + means[i][2]);
          System.out.println(" " + means[i][3] + "," + means[i][4] + "," + means[i][5]);
          System.out.println("color#" + j);
          System.out.println(" " + means[j][0] + "," + means[j][1] + "," + means[j][2]);
          System.out.println(" " + means[j][3] + "," + means[j][4] + "," + means[j][5]);
          System.out.println("dist=" + min_dist);
        }
      }
    }
    yi.util.io.OutputResult.print("dist_matrix", dist_matrix, m_clusterNumber, m_clusterNumber);
    int[] dist_hist = hist.getHistogram();
    yi.util.io.OutputResult.print("dist_hist", dist_hist, true);


//    // post merge the similar cluster
//    Merge merge = new Merge(cluster_num);
//    for (int i=0; i<cluster_num-1; i++) {
//      for (int j=i+1; j<cluster_num; j++) {
//        int[] best = new int[6];
//        int[] cc1 = new int[] {
//            means[i][0], means[i][1], means[i][2]};
//        int[] cc2 = new int[] {
//            means[i][3], means[i][4], means[i][5]};
//        int[] c1 = new int[] {
//            means[j][0], means[j][1], means[j][2]};
//        int[] c2 = new int[] {
//            means[j][3], means[j][4], means[j][5]};
//
//        if (VectorUtil.EuclideanDistance(cc1,c1) < 20 && VectorUtil.EuclideanDistance(cc2,c2) < 20 ||
//            VectorUtil.EuclideanDistance(cc2,c1) < 20 && VectorUtil.EuclideanDistance(cc1,c2) < 20) {
//          merge.merge(j, i);
//        }
//      }
//    }
//
//    int[] merge_rst = merge.result();
//    for (int i=0; i<cluster_num; i++) {
//      if (merge_rst[i] == i) continue;
//      merge(labels, means, i, merge_rst[i]);
//    }
//    int old_cluster_num = m_clusterNumber;
//    eliminateEmptyCluster(label, means);
//    int new_cluster_num = m_clusterNumber;
//    System.out.println("merge : " + old_cluster_num + " -> " + new_cluster_num);
//
//    cluster_num = m_clusterNumber;

  }

  /**
   * Merge from "from" cluster to "to" cluster
   * @param labels
   * @param means
   * @param from
   * @param to
   */
  void merge(int[] labels, int[][] means, int from, int to) {
    int from_num = 0, to_num = 0;
    // change the label
    for (int i=0; i<labels.length; i++) {
      if (labels[i] == from) {
        from_num ++;
        labels[i] = to;
      }
      else if (labels[i] == to) {
        to_num ++;
      }
    }
    // change the mean
    int[] best = new int[6];
    // find the best order (c1, c2) or (c2, c1)
    colorPairDistance(means[from], means[to], best);
    for (int i=0; i<means[to].length; i++) {
      means[to][i] = (means[to][i] * to_num + best[i] * from_num) / (to_num + from_num);
    }
  }


  public static void main(String[] args) {
    // init configuration
    Configuration.init(args);

    // get the image name
    String img_name = ReadArgu.getOption('i', args);
    if (img_name == null) {
      System.err.println("Usage: -i image_name");
      System.exit(1);
    }

    // read in image
    Image image = null;
    Dimension d = new Dimension();
    int[] pixels = null;
    try {
      image = yi.util.io.ImageReader.readImageFile(img_name);
      pixels = yi.util.io.ImageReader.getPixels(image, d);
    }
    catch (java.io.IOException e) {
      System.err.println("Can't read image " + img_name);
      e.printStackTrace();
      System.exit(2);
    }

    // process
    Configuration.setParameter("SOURCE_NAME", img_name);
    long startTime = System.currentTimeMillis();

    //find all the lines in an image
    yi.iu.processor.ort.DPU_Fex dp = new DPU_Fex();
    Vector[] segs= dp.getLinesAndArcs(pixels, d.width, d.height);
    Vector lines= segs[0];
    LineClusterSet lcs = new LineClusterSet(lines, d.width, d.height);

//    int[] lcs_demo = lcs.demo(pixels, d, true, false, false, true);
//    OutputResult.outputColorImage(img_name + ".line.ppm", lcs_demo, d.width, d.height);

    // find the dominant colors
    DPU_DominantColor dpu_dc = new DPU_DominantColor();
    DS_DominantColor ds_dc = dpu_dc.getReusableDominantColors(pixels, d.width, d.height);
    {
      int[] dc_img = dpu_dc.getDemo(pixels, d.width, d.height);
      OutputResult.outputGIFImage(img_name + ".dc.gif", dc_img, d.width, d.height);
      int[] dc_lilne_demo = lcs.demo(dc_img, d, true, false, false, true);
      OutputResult.outputGIFImage(img_name + ".line.gif", dc_lilne_demo, d.width, d.height);
    }

    // convert dominant colors
    Collection colors = ds_dc.getDominantColors();

    CLC_KMeansColorPair k_means = new CLC_KMeansColorPair();
    LineClusterSets lcss = k_means.clustering(lines, ds_dc, colors,
                                    pixels, d.width, d.height);

    long endTime = System.currentTimeMillis();
    System.out.println("running time: " + (endTime-startTime));

    // illustration each line cluster
    {
      Iterator i= lcss.keySet().iterator();
      int label = 1;
      while (i.hasNext()) {
        ColorPair cp = (ColorPair)i.next();
        LineClusterSet line_cluster = (LineClusterSet)lcss.get(cp);
        // draw
        int[] lineimg= yi.util.ImageUtil.makeBackground(pixels);
        line_cluster.draw(lineimg, d.width, d.height, 0xffffffff);
        // color spectrum
        int[] color_pair = new int[] {cp.x, cp.y};
        int color_w = 40, color_h = 50;
        int[] spectrum = yi.iu.processor.color.ColorUtil.createSpectrum(color_pair, color_w, color_h);
        for (int y=0; y<color_h; y++) {
          for (int x=0;x<color_w*color_pair.length; x++) {
            lineimg[y*d.width+x] = spectrum[y*color_w*color_pair.length+x];
          }
        }
        // make a simple color index
//        OutputResult.outputColorImage(img_name + ".cclc." + cp_index, lineimg, d.width, d.height, true);
        OutputResult.outputColorImage(img_name + ".kmcp",
                                      lineimg, d.width, d.height, true);

//        // output the region
//        lineimg= yi.util.ImageUtil.makeBackground(pixels);
//        Region r = line_cluster.getRegion();
//        Region.drawRegions(lineimg, d, r, colors[0]);
//        OutputResult.outputColorImage(img_name + ".clc_region", lineimg, d.width, d.height, true);
        label ++;
      }
    }


    // demo the line clusters
    if (k_means.DEMO_COLOR_CLC) {
      int[] lineimg = lcss.demo(d.width, d.height);
      OutputResult.outputGIFImage(img_name + ".color_clcs.gif", lineimg, d.width, d.height);
    }

//    // demo the line cluster regions
//    {
//      Iterator i= lcss.values().iterator();
//      int[] lineimg= new int[pixels.length];
//      int label = 1;
//      while (i.hasNext()) {
//        LineClusterSet line_cluster = (LineClusterSet)i.next();
//        // draw region
//        Region r = line_cluster.getRegion();
//        Region.drawRegions(lineimg, d, r, label++);
//      }
//      lineimg = yi.util.ImageUtil.makeNewImageFromLabel(lineimg);
//      OutputResult.outputColorImage(img_name + ".clc_regions.", lineimg, d.width, d.height, true);
//    }

    // demo the line cluster regions (only the biggest)
    if (k_means.DEMO_COLOR_CLC_REGION) {
      int[] lineimg = lcss.demoRegions(d.width, d.height);
      OutputResult.outputGIFImage(img_name + ".clc_regions.gif", lineimg, d.width, d.height);
    }

    System.exit(0);
  }


}