package yi.iu.processor.graphseg;

import yi.iu.processor.*;
import yi.iu.processor.morph.*;
import yi.util.io.OutputResult;
import yi.iu.ui.SegFrame;

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


public class GraphSeg extends yi.iu.processor.ImageProcessor
{
    public DistanceMeasure dm= null;

    boolean VERBOSE=false;

    public int BSCRGNSIZE=16;  //the basic region size, now try to define as 8*8
    public int STOPRGNSIZE=2;  //after the refine, what's size of the basic block
    //int FIRSTGROWTHRSH= 128;   //the max allowed distance for two basic region grow in the first step
    //int LOOSEFIRSTGROWTHRSH= FIRSTGROWTHRSH*2;   //the max allowed distance for two basic region grow in the first step
    public int DISTANCE_THRESHOLD= 128;   //the max allowed distance for two basic region grow in the first step
    int LOOSE_THRESHOLD_RATIO= 2;

    //final static int MINUNIONNUM=6;
    //final static double STOPUNION=1.5;
    //final static int STOPUNION2=10;

    final static int REFINESCALE=2;     //at 1st step, block size=8; at the next step, block size= 8/REFINESCALE

        //for debug, trace a block
        int traceRgn=-1;

        //int[] sourceData=null;//just for demo

    public GraphSeg() {super();}
    public GraphSeg(DistanceMeasure _dm) {this(); dm=_dm;}

    public int[] getProcessed(int source[], Dimension d)
    {
        return segmentation(source, d.width, d.height);
    }

    public int[] getProcessedPseudoColor(int source[], Dimension d)
    {
        int[] seg= getProcessed(source,d);
        int[] rst= get_displayRgns_frame(source, d.width, d.height, seg);
        return rst;
        //return null;
    }

    public int[] segmentation(int[] source, int w, int h, int dist_thrsh, int basic_size, int stop_size)
    {
        DISTANCE_THRESHOLD=dist_thrsh;
        BSCRGNSIZE=basic_size;
        STOPRGNSIZE=stop_size;
        return segmentation(source,w,h);
    }

    public int[] segmentation(int[] source, int w, int h)
    {
        int wr=w/BSCRGNSIZE, hr=h/BSCRGNSIZE;       //width and height in term of basci region

        //get the bare information about the source image
        int[] bareData= dm.getBareData(source,new Dimension(w,h));

        //just for demo, use the bareData to get the image for display
        //sourceData=source;

        if (VERBOSE) {
            System.err.println();
            System.err.println("--- block size = "+BSCRGNSIZE+" ---");
        }

        //get the information about every basic regions
        int rgnInfo[][]= dm.getBscRgnInfo(bareData, w, h, BSCRGNSIZE);
        int[] segs_1= new int[wr*hr];
        for (int i=0;i<segs_1.length;i++) segs_1[i]=i;

        //displayRgns_frame(source, w, h, BSCRGNSIZE, segs_1, "candidate block_size="+BSCRGNSIZE);
        if (rgn1>0) dm.printDiffOfHists(rgnInfo, rgn1, rgn2);
        /*
        if (rgn3>0) {
            //int len= rgnInfo[rgn3].length;
            int len= 26;
            int[][] temp= new int[3][len];
            for (int i=0;i<len-1;i++) {
                temp[0][i]=rgnInfo[rgn3][i]/rgnInfo[rgn3][len-1];
                temp[1][i]=rgnInfo[rgn4][i]/rgnInfo[rgn4][len-1];
                temp[2][i]=Math.abs(temp[0][i]-temp[1][i]);
            }
            temp[0][len-1]=rgnInfo[rgn3][len-1];
            temp[1][len-1]=rgnInfo[rgn4][len-1];
            OutputResult.outputResult("rgn_comp", temp);
            System.err.println(rgn3+ ","+rgn4+": "+dm.distance(rgnInfo[rgn3], rgnInfo[rgn4]));
            return segs_1;
        }
        */
        //if (BSCRGNSIZE==STOPRGNSIZE) { dm.printDiffOfHists(rgnInfo, rgn1, rgn2); traceRgn=rgn1;
        //}
        //else traceRgn=-1;
        if (rgn1>0) traceRgn=rgn1;
        else traceRgn=-1;

        //region grow on the basic regions
        int[] segs= growOnBscRgn(rgnInfo, wr, hr);
        //displayRgns_frame(source, w, h, BSCRGNSIZE, segs, "grow_step_1");
        //displayRgns_color(w, h, BSCRGNSIZE, segs, "grow_step_1 block_size="+BSCRGNSIZE);


        //check whether the calculation of histogram is correct
        //boolean OK=dm.VerifyRgnInfo(bareData, w, h, BSCRGNSIZE, segs, rgnInfo);
        //if (!OK) System.err.println("wrong histogram calculation after merge on basic blocks!");

        //refine the segmentation
        int[] rfnSegs= refineSeg(bareData, w, h, segs, rgnInfo);
//int[] rfnSegs=segs;
        //OutputResult.outputResult("seg", rfnSegs,w,h);
        //dm.printDiffOfHists(rgnInfo, rgn1, rgn2);


        //rfnSegs= removeSmall(rfnSegs,RGNSIZETHRSH);
        //int[] segimg= yi.util.ImageUtil.makeNewImageFromLabel(rfnSegs);
        //(new SegFrame("refined regions", segimg, w, h, rfnSegs)).show();
        //displayRgns_frame(source, w, h, STOPRGNSIZE, rfnSegs, "result");
        if (rgn3>0) dm.printDiffOfHists(rgnInfo, rgn3, rgn4);
        /*
        if (rgn1>0) {
            //int len= rgnInfo[rgn3].length;
            int len= 26;
            int[][] temp= new int[3][len];
            for (int i=0;i<len-1;i++) {
                temp[0][i]=rgnInfo[rgn1][i]/rgnInfo[rgn1][len-1];
                temp[1][i]=rgnInfo[rgn2][i]/rgnInfo[rgn2][len-1];
                temp[2][i]=Math.abs(temp[0][i]-temp[1][i]);
            }
            OutputResult.outputResult("rgn_comp", temp);
            temp[0][len-1]=rgnInfo[rgn1][len-1];
            temp[1][len-1]=rgnInfo[rgn2][len-1];
            OutputResult.outputResult("rgn_comp", temp);
            System.err.println(rgn1+","+rgn2+": "+dm.distance(rgnInfo[rgn1], rgnInfo[rgn2]));

            return segs_1;
        }
        */
        /*
        if (traceRgn>0&&traceStep>0) {
            OutputResult.outputResult("trace", traceRec, traceRec[0].length, traceStep);
            OutputResult.outputResult("grow_stat", growStat,1,growStat.length);
            int statB=((DM_LAWS3)dm).getStatBegin();
            int statL=((DM_LAWS3)dm).getStatLen();
            int[] temp= new int[statL];
            for (int k=0;k<statL;k++)
                temp[k]=rgnInfo[traceRgn][k+statB];
            OutputResult.outputResult("grow_stat", temp);

        }
        */
        /*
        int test_rgn=77;
        int[][] hci_rst= new int[rgnInfo[test_rgn][49]][6];
        int ptr=0;
        int[] hci= new int[3];
        for (int i=0;i<rfnSegs.length;i++) {
            if (rfnSegs[i]==test_rgn) {
                    int red=source[i]>>16&255;
                    int green=source[i]>>8&255;
                    int blue=source[i]&255;
                DM_HCI.rgb2hci(red,green,blue,hci);
                if (hci[1]<35) continue;
                hci_rst[ptr][0]=red;
                hci_rst[ptr][1]=green;
                hci_rst[ptr][2]=blue;

                hci_rst[ptr][3]=hci[0];
                hci_rst[ptr][4]=hci[1];
                hci_rst[ptr++][5]=hci[2];
            }
        }
        OutputResult.outputResult("77_hue", hci_rst);
        */
        if (STOPRGNSIZE>1) rfnSegs= getFineRegionMap(w, h, STOPRGNSIZE, rfnSegs);
        return rfnSegs;

    }

    //given the information of region, grow it. w*h regions
    int[] growOnBscRgn(int rgnInfo[][], int w, int h)
    {

                int looseTh= DISTANCE_THRESHOLD*LOOSE_THRESHOLD_RATIO;
                Vector[] dists= new Vector[looseTh];     //store the distances

        //calculate the distances between any two basic regions
        int d;
        int candidate=0;
        //int ld[][]= new int[h][w],ud[][]= new int[h][w];
        for (int y = 0; y < h; ++y ){
                for (int x = 0; x < w; ++x ){
                    /*
                    if (x==0&&y==13)
                        x=0;
                    */
                    int current=y*w+x;
                    //the distance between the left and current
                    if (x>0)
                        {
                            int left=current-1;
                            d= dm.distance(rgnInfo[left], rgnInfo[current]);
                            //ld[y][x]=d;
                            if (d<looseTh) {
                                if (dists[d]==null) dists[d]=new Vector();
                                dists[d].addElement(new Dimension(left,current));
                                candidate++;
                            }
                        }
                    //the distance between the upper and current
                        if (y>0)
                        {
                            int upper=current-w;
                            d=dm.distance(rgnInfo[upper], rgnInfo[current]);
                            //ud[y][x]=d;
                            if (d<looseTh){
                                if (dists[d]==null) dists[d]=new Vector();
                                dists[d].addElement(new Dimension(upper,current));
                                candidate++;
                            }

                        }
                }
        }
        if (VERBOSE)
            System.err.println("  candidates= "+candidate);
        //display the statistic information about the distances
        int[] ds= new int[looseTh];
        for (int i=0;i<looseTh;i++) if (dists[i]!=null) ds[i]= dists[i].size();
        //OutputResult.outputResult("distance_stat", ds);
        //OutputResult.outputResult("left_dff", ld);
        //OutputResult.outputResult("upper_dff", ud);

        //make the region-map
        int rgnNum= w*h;
        int[] rgnMap= new int[rgnNum];
        for (int i=0;i<rgnNum;i++) rgnMap[i]=i;

        //grow the region with the order of the distance
        int[] rst= growOnGraph( dists, rgnMap, rgnInfo, DISTANCE_THRESHOLD);

                return rst;
    }

    int[] refineSeg(int[] bareData, int w, int h, int[] segs, int[][] rgnInfo)
    {
        int blkSize=STOPRGNSIZE;
        //refine the result by block (size=4,2,1, if basic_region_size=8)
        for (int s=BSCRGNSIZE/REFINESCALE; s>=blkSize; s/=REFINESCALE) {
            if (VERBOSE) {
                System.err.println();
                System.err.println("--- block size = "+s+" ---");
            }
            //if (blkSize==STOPRGNSIZE) traceRgn=rgn1;
            //else traceRgn=-1;
            int threshold= dm.getThreshold(DISTANCE_THRESHOLD,BSCRGNSIZE,s);
            segs=refineSeg(bareData,w,h,segs,rgnInfo,s, threshold);
        }

        int wr=w/blkSize, hr=h/blkSize;

        //OutputResult.outputResult("hists_after_refine1", rgnInfo);
                //OutputResult.outputResult("refine1_rst", segs, wr, hr);

        /*
        //assign every pixel to a region according to the block-based segmentation
        int[] bigSeg= new int[w*h];
        for (int y=0;y<hr;y++) {
            for (int x=0;x<wr;x++) {
                int label= segs[y*wr+x];
                for (int i=0;i<blkSize;i++) {
                    for (int j=0;j<blkSize;j++) {
                        bigSeg[(y*blkSize+i)*w+(x*blkSize+j)]=label;
                    }
                }
            }
        }
        return bigSeg;
        */

        return segs;
    }

    int[] refineSeg(int[] bareData, int w, int h, int[] segs, int[][] rgnInfo, int blkSize, int threshold)
    {

        int wr=w/blkSize, hr=h/blkSize;       //width and height in term of basic region
        int oldwr=wr/REFINESCALE, oldhr=hr/REFINESCALE;

        //assign every pixel to a region according to the block-based segmentation
        int[] rfnSeg= new int[wr*hr];
        for (int y=0;y<oldhr;y++) {
            for (int x=0;x<oldwr;x++) {
                int label= segs[y*oldwr+x];
                for (int i=0;i<REFINESCALE;i++) {
                    for (int j=0;j<REFINESCALE;j++) {
                        rfnSeg[(y*REFINESCALE+i)*wr+(x*REFINESCALE+j)]=label;
                    }
                }
            }
        }


        //find the usable region label
        int[] label_used= new int[rgnInfo.length];
        for (int i=0;i<segs.length;i++) label_used[segs[i]]=1;
        Vector label_stack= new Vector();
        for (int i=0;i<label_used.length;i++) if (label_used[i]==0) label_stack.addElement(new Integer(i));


        //unionThrsh=Thrsh2/scale;
        //if (unionThrsh<1) unionThrsh=1;
        int label_needed=0;       //when label is not enough!
        //refine the regions
                for (int y = 0; y < oldhr; ++y ){
                for (int x = 0; x < oldwr; ++x ){
                    int current=y*oldwr+x;
                    int old_label=segs[current];
                    int[] hist_current= rgnInfo[old_label];

                    //consider the left and current
                    if (x>0)
                        {
                            int left=current-1;
                            int old_label_l= segs[left];
                            //if current is different from the left, add the two colums on the boundaryto the stack
                            if (old_label_l!=old_label) {
                                for (int i=0;i<REFINESCALE;i++) {
                                    //small blocks in the current block
                                    int newc=x*REFINESCALE+(y*REFINESCALE+i)*wr;
                                    //if the current considered subblock belongs to the same region of the big block, then seperate it
                                    if (rfnSeg[newc]==old_label) {
                                        if (label_stack.size()==0)
                                            label_needed++;
                                        else {
                                            //get a new label
                                            int new_label=((Integer)label_stack.elementAt(0)).intValue();
                                            label_stack.removeElementAt(0);
                                            rgnInfo[new_label]=dm.makeRgnInfo(bareData,w,h,blkSize,x*REFINESCALE,y*REFINESCALE+i);
                                            dm.removeRgn(rgnInfo[old_label], rgnInfo[new_label]);
                                            rfnSeg[newc]=new_label;
                                        }
                                    }

                                    //small blocks on the left
                                    newc=x*REFINESCALE-1+(y*REFINESCALE+i)*wr;
                                    if (rfnSeg[newc]==old_label_l) {
                                        if (label_stack.size()==0)
                                            label_needed++;
                                        else {
                                            //get a new label
                                            int new_label=((Integer)label_stack.elementAt(0)).intValue();
                                            label_stack.removeElementAt(0);
                                            rgnInfo[new_label]=dm.makeRgnInfo(bareData,w,h,blkSize,x*REFINESCALE-1,y*REFINESCALE+i);
                                            dm.removeRgn(rgnInfo[old_label_l], rgnInfo[new_label]);
                                            //change the histogram of the big block
                                            rfnSeg[newc]=new_label;
                                        }
                                    }

                                }
                            }
                        }

                    //consider the upper and current
                    //consider the left and current
                    if (y>0)
                        {
                            int upper=current-oldwr;
                            int old_label_u= segs[upper];
                            //if current is different from the left, add the two colums on the boundaryto the stack
                            if (old_label_u!=old_label) {
                                for (int i=0;i<REFINESCALE;i++) {
                                    //small blocks in the current block
                                    int newc=x*REFINESCALE+i+(y*REFINESCALE)*wr;
                                    //decide whether this block has the histogram of hisself
                                    if (rfnSeg[newc]==old_label) {
                                        if (label_stack.size()==0)
                                            label_needed++;
                                        else {
                                            //get a new label
                                            int new_label=((Integer)label_stack.elementAt(0)).intValue();
                                            label_stack.removeElementAt(0);
                                            rgnInfo[new_label]=dm.makeRgnInfo(bareData,w,h,blkSize,x*REFINESCALE+i,y*REFINESCALE);
                                            dm.removeRgn(rgnInfo[old_label], rgnInfo[new_label]);
                                            rfnSeg[newc]=new_label;
                                        }
                                    }
                                    //small blocks on the left
                                    newc=x*REFINESCALE+i+(y*REFINESCALE-1)*wr;
                                    if (rfnSeg[newc]==old_label_u) {
                                        if (label_stack.size()==0)
                                            label_needed++;
                                        else {
                                            //get a new label
                                            int new_label=((Integer)label_stack.elementAt(0)).intValue();
                                            label_stack.removeElementAt(0);
                                            rgnInfo[new_label]=dm.makeRgnInfo(bareData,w,h,blkSize,x*REFINESCALE+i,y*REFINESCALE-1);
                                            dm.removeRgn(rgnInfo[old_label_u], rgnInfo[new_label]);
                                            rfnSeg[newc]=new_label;
                                        }
                                    }

                                }
                            }
                        }

                }
        }

        //after segment the blocks on the boundary, some connected region becomes to un-connected, assgin them to different region!
        //calculate the connected component first
        int[] connected= (new ConnectComponent()).getProcessed(rfnSeg,new Dimension(wr,hr));
        int[] rgn2con= new int[rgnInfo.length];
        int[] con2rgn= new int[rgnInfo.length]; //mapping from connected component to region label
        for (int i=0;i<rgn2con.length;i++) rgn2con[i]=con2rgn[i]=-1;
        for (int i=0;i<rfnSeg.length;i++) {
            int rgn_label=rfnSeg[i];
            int con_label= connected[i];
            //if this is the first time to use this label, setup the mapping from the label to the corresponding connected component label
            if (rgn2con[rgn_label]==-1) {
                rgn2con[rgn_label]=con_label;
                con2rgn[con_label]=rgn_label;
                continue;
            }
            int new_label=con2rgn[con_label];
            //if the region label has been assign to other connected conponent label, assign this connected component to other label
            if (new_label==-1) {
                if (label_stack.size()==0) {
                    label_needed++;
                    break;
                }
                else {
                    //if (VERBOSE)
                        //System.err.println("Got a unconnected region.");
                    //get a new label
                    new_label=((Integer)label_stack.elementAt(0)).intValue();
                    label_stack.removeElementAt(0);
                    rgnInfo[new_label]=dm.makeRgnInfo(bareData,w,h,blkSize,i);
                    dm.removeRgn(rgnInfo[rgn_label], rgnInfo[new_label]);
                    rfnSeg[i]=con2rgn[con_label]=new_label;
                    continue;
                }
            }
            //if the block belong to a new region, recalculate the region information
            if (rgn_label!=new_label) {
                int[] ri=dm.makeRgnInfo(bareData,w,h,blkSize,i);
                dm.moveRgn(rgnInfo[rgn_label],rgnInfo[new_label],ri);
                rfnSeg[i]=new_label;
            }
        }

        if (label_needed!=0)
            System.err.println("!!Not enough label, "+label_needed+" needed!");

        //displayRgns_frame(sourceData, w, h, blkSize, rfnSeg, "candidate block_size="+blkSize);
        //test the considered regions in the refining step
        //if (blkSize==1)
        //    displayRgns_color(w, h, blkSize, rfnSeg, "candidate block_size="+blkSize);


        //check whether the calculation of histogram is correct
        //boolean OK=dm.VerifyRgnInfo(bareData, w, h, blkSize, rfnSeg, rgnInfo);
        //if (!OK) System.err.println("wrong histogram calculation!");

                int loose= DISTANCE_THRESHOLD*LOOSE_THRESHOLD_RATIO;
                Vector[] dists= new Vector[loose];     //store the distances

        //calculate the distances between any two basic regions
        int d;
        int candidate=0;
        //int ld[][]= new int[h][w],ud[][]= new int[h][w];
        for (int y = 0; y < hr; ++y ){
                for (int x = 0; x < wr; ++x ){
                    /*
                    if (x==0&&y==13)
                        x=0;
                    */
                    int current=y*wr+x;
                    //the distance between the left and current
                    if (x>0)
                        {
                            int left=current-1;
                            d= dm.distance(rgnInfo[rfnSeg[left]], rgnInfo[rfnSeg[current]]);
                            //ld[y][x]=d;
                            if (d<loose) {
                                if (dists[d]==null) dists[d]=new Vector();
                                dists[d].addElement(new Dimension(left,current));
                                candidate++;
                            }
                        }
                    //the distance between the upper and current
                        if (y>0)
                        {
                            int upper=current-wr;
                            d=dm.distance(rgnInfo[rfnSeg[upper]], rgnInfo[rfnSeg[current]]);
                            //ud[y][x]=d;
                            if (d<loose){
                                if (dists[d]==null) dists[d]=new Vector();
                                dists[d].addElement(new Dimension(upper,current));
                                candidate++;
                            }

                        }
                }
        }
        if (VERBOSE)
            System.err.println("  candidates= "+candidate);
        //display the statistic information about the distances
        int[] ds= new int[loose];
        for (int i=0;i<loose;i++) if (dists[i]!=null) ds[i]= dists[i].size();

        //grow the region with the order of the distance
        growOnGraph( dists, rfnSeg, rgnInfo, threshold);

        //if (blkSize==2)
        //    displayRgns_color(w, h, blkSize, rfnSeg, "candidate block_size="+blkSize);
        //displayRgns_frame(sourceData, w, h, blkSize, rfnSeg, "candidate block_size="+blkSize);


        return rfnSeg;
    }

    //for trace a region
    int[][] traceRec=null;
    int TRACEMAXSTEP=50;   //trace max step
    int traceStep=0;
    int[] growStat=null;


    //given the information of region, grow it based on graphs
    //distBucket: store the distance by order (the distances is the edges)
    //rgnMap: mapping the index of node to a region
    int[] growOnGraph(Vector[] distBucket, int[] rgnMap, int rgnInfo[][], int threshold)
    {
        int numRgn= rgnInfo.length;
        int numNode= rgnMap.length;
        int unionThrsh= threshold; //the possible distance is between [0,distThrsh-1)

        if (traceRgn>=0&&traceRec==null) {
            traceStep=0;
            traceRec= new int[TRACEMAXSTEP][];
            growStat= new int[unionThrsh];
        }

                //make the data structure for set-union operation
                int[] parent= new int[numRgn];
                for (int i=0;i<numRgn;i++) parent[i]=i;

                int[] diststat= new int[unionThrsh];     //give the statistic information about the distance
                int i;
                double maxChange=1;     //sometime, a bigger distance could change to smaller, so we need to consider
                                        //more distance candidate greater than the real union threshold

                for (i=0;i<distBucket.length;i++) {
                    if (distBucket[i]==null) continue;
            int l=distBucket[i].size();
            //choice 1
            //if (i>(int)(distMax*STOPUNION)) {
            //    if (VERBOSE) System.err.println("union stop at distance "+i);
            //    break;
            //}
            //choice 2
            //if (i>(int)(unionThrsh+STOPUNION2)) {
            //    if (VERBOSE) System.err.println("union stop at distance "+i);
            //    break;
            //}
            //choice 3
            //no automatic threshold
            //if (traceRgn>=0) System.err.println("distance="+i);
            int numUnion=0;
            for (int j=0;j<l;j++) {
                Dimension pair= (Dimension)distBucket[i].elementAt(j);
                int first=pair.width, second=pair.height;

                int label1=rgnMap[first]=findRgnNum(parent,rgnMap[first]);
                int label2=rgnMap[second]=findRgnNum(parent,rgnMap[second]);

                if (label1==label2) continue;

                //else decide whether need combine together
                //now not reorder, but maybe reorder is better?
                //or try reorder this one, if the distance change to bigger, throw it backward of the queue
                //--------------------------
                //choice1 -- no reorder
                //if (distance(rgnInfo[label1], rgnInfo[label2])<FIRSTGROWTHRSH)
                //    rgnUnion(parent,label1, label2, rgnInfo);
                //--------------------------
                //choice2 -- reorder the current one if the distance changes to bigger
                int d=dm.distance(rgnInfo[label1], rgnInfo[label2]);
//    	        int d=i;

                /*
                //test whether two connected region have been put into the candidates
                int t_label1=560, t_label2=583;
                if ((label1==t_label1&&label2==t_label2)||(label2==t_label1&&label1==t_label2))
                    System.err.println("found ("+label1+","+label2+")="+d);
                */
                //if the distance changed to bigger, re-enqueue it
                if (d>i) {
                    if (d<distBucket.length) {
                                if (distBucket[d]==null) distBucket[d]=new Vector();
                                distBucket[d].addElement(new Dimension(first,second));
                            }
                        }
                        else if (d<unionThrsh) {
                            int newRgn=rgnUnion(parent,label1, label2, rgnInfo);
                            //if (dm.getClass().getName(). =="DM_LAWS3") {
/*
                            try {
                                if (dm.getClass().equals(Class.forName("DM_LAWS3")) ) {
                                    int statB=((DM_LAWS3)dm).getStatBegin();
                                    int statL=((DM_LAWS3)dm).getStatLen();
                                    int bin= d*statL/unionThrsh;
                                    rgnInfo[newRgn][statB+bin]++;
                                }
                            }
                            catch (ClassNotFoundException e) {
                                System.err.println("no DM_LAWS: "+e);
                            }
*/

                            if ((traceRgn>=0)&&(label1==traceRgn||label2==traceRgn)) {
                                System.err.print("#"+traceRgn+"-("+label1+","+label2+"):"+d+"->");
                                traceRgn=findRgnNum(parent,traceRgn);
                                System.err.println(traceRgn);
                                if (traceStep<TRACEMAXSTEP)
                                    traceRec[traceStep++]= (int[])rgnInfo[traceRgn].clone();
                                growStat[d]++;
                            }
                            diststat[d]++;
                            numUnion++;
                            if (i>unionThrsh) maxChange=(double)i/unionThrsh;
                        }
            }
            //if (numUnion>MINUNIONNUM&&i>16) unionThrsh=i;
        }

        //if (VERBOSE) System.err.println("union stop at "+(i-1));
        if (VERBOSE) System.err.println("  union_threshold= "+unionThrsh+"*"+maxChange);


                //recalculate the result according the records in parent
                for (i = 0; i < numNode; i++ ) {
                    rgnMap[i]=findRgnNum(parent,rgnMap[i]);
                }
                //OutputResult.outputResult("distance_stat", diststat);

                return rgnMap;
    }

    int findRgnNum(int[] parent,int x)
    {
                while ( x!=parent[x] )
                        x = parent[x];
                return x;
    }

    int rgnUnion(int[] parent,int label1, int label2, int[][] rgnInfo)
    {
                int rst;
                if (label1==label2) {
                    System.err.println("union on the same region!");
                    return label1;
                }

                /*
                if (label1==1949||label2==1949)
                    rst=0;
                */

            //combine the histogram also
                if (label1>label2) {
                    rst= parent[label1] = label2;
                    int[] histx= rgnInfo[label1];
                    int[] histy= rgnInfo[label2];
                    dm.rgnUnion(histy,histx);
                }
                else {
                    rst= parent[label2] = label1;
                    int[] histx= rgnInfo[label1];
                    int[] histy= rgnInfo[label2];
                    dm.rgnUnion(histx,histy);
                }
                return rst;

    }


/*******************************************************************************
 functions to visualize or display the results
*******************************************************************************/
    /*
        //mark a block from (x1,y1)->(x2-1,y2-1)
        void markRect(int[] hdiff,int w,int h,int x1,int y1,int x2,int y2,int c)
        {
            int i;

            //horizontal lines
            for (i=x1; i<x2; i++) {
                hdiff[y1*w+i]=hdiff[(y2-1)*w+i]=c;
            }

            //vertical lines
            for (i=y1; i<y2; i++) {
                hdiff[i*w+x1]=hdiff[i*w+x2-1]=c;
            }
        }
        //mark the blocks [x1,y1] and [x2,y2]; (index of block)
        void mark2blocks(int[] hdiff,int w,int h,int x1,int y1,int x2,int y2)
        {
            //markRect(hdiff,w,h,x1*BSCRGNSIZE,y1*BSCRGNSIZE,(x1+1)*BSCRGNSIZE,(y1+1)*BSCRGNSIZE,0xffff0000);
            //markRect(hdiff,w,h,x2*BSCRGNSIZE,y2*BSCRGNSIZE,(x2+1)*BSCRGNSIZE,(y2+1)*BSCRGNSIZE,0xffff0000);
            if (x1==x2) {
                //markRect(hdiff,w,h,x1*BSCRGNSIZE,y1*BSCRGNSIZE,(x1+1)*BSCRGNSIZE,(y2+1)*BSCRGNSIZE,0xffff0000);
                for (int y=y1*BSCRGNSIZE+BSCRGNSIZE/2;y<y2*BSCRGNSIZE+BSCRGNSIZE/2;y++) {
                    hdiff[y*w+x1*BSCRGNSIZE+BSCRGNSIZE/2]=0xffff0000;
                }
            }
            else {
                //markRect(hdiff,w,h,x1*BSCRGNSIZE,y1*BSCRGNSIZE,(x2+1)*BSCRGNSIZE,(y1+1)*BSCRGNSIZE,0xff0000ff);
                for (int x=x1*BSCRGNSIZE+BSCRGNSIZE/2;x<x2*BSCRGNSIZE+BSCRGNSIZE/2;x++) {
                    hdiff[(y1*BSCRGNSIZE+BSCRGNSIZE/2)*w+x]=0xffff0000;
                }
            }
        }

        void mark2blocksInt(int[] hdiff,int w,int h,int x1,int y1,int x2,int y2)
        {
            //markRect(hdiff,w,h,x1*BSCRGNSIZE,y1*BSCRGNSIZE,(x1+1)*BSCRGNSIZE,(y1+1)*BSCRGNSIZE,0xffff0000);
            //markRect(hdiff,w,h,x2*BSCRGNSIZE,y2*BSCRGNSIZE,(x2+1)*BSCRGNSIZE,(y2+1)*BSCRGNSIZE,0xffff0000);
            if (x1==x2) {
                //horizontal lines
                for (int i=x1; i<(x1+1); i++) {
                    hdiff[(y2-1)*w+i]=hdiff[y2*w+i]=0xff00ff00;
                }
            }
            else {
                //vertical lines
                for (int i=y1; i<(y1+1); i++) {
                    hdiff[i*w+x2-1]=hdiff[i*w+x2]=0xff00ff00;
                }
            }
        }


        //show the regions by frames
        void displayRgns_frame(int[] chn, int w, int h, int[] mrg, int bw, int hr, String title)
        {
            //int[] bimage= yi.util.ImageUtil.makeNewImageFromGray(chn);
            int[] bimage= (int[])chn.clone();

        //horizontal differences
        for (int y=0;y<hr;y++) {
            for (int x=0;x<bw-1;x++) {
                if (mrg[y*bw+x]!=mrg[y*bw+x+1]) mark2blocksInt(bimage,w,h,x,y,x+1,y);
            }
        }

        //vertical differences
        for (int y=0;y<hr-1;y++) {
            for (int x=0;x<bw;x++) {
                if (mrg[y*bw+x]!= mrg[(y+1)*bw+x]) mark2blocksInt(bimage,w,h,x,y,x,y+1);
            }
        }

        (new yi.iu.ui.DisplayFrame(title, bimage, w, h)).show();
    }
    */

    int[] get_displayRgns_frame(int[] source, int w, int h, int[] seg)
    {
            //int[] bimage= yi.util.ImageUtil.makeNewImageFromGray(chn);
            int[] bimage= (int[])source.clone();
            int frame_color=0xff00ff00;
            //int spec_color=0xff00ff00;
            //int spec_reg=409;

        //horizontal differences
        for (int y=0;y<h;y++) {
            for (int x=0;x<w-1;x++) {
                if (seg[y*w+x]!=seg[y*w+x+1])
                {
                    bimage[y*w+x]=bimage[y*w+x+1]=frame_color;
                    //bimage[y*w+x]=(seg[y*w+x]==spec_reg)?spec_color:frame_color;
                    //bimage[y*w+x+1]=(seg[y*w+x+1]==spec_reg)?spec_color:frame_color;
                }
            }
        }

        //vertical differences
        for (int y=0;y<h-1;y++) {
            for (int x=0;x<w;x++) {
                if (seg[y*w+x]!= seg[(y+1)*w+x])
                {
                    bimage[y*w+x]=bimage[(y+1)*w+x]=frame_color;
                    //bimage[y*w+x]=(seg[y*w+x]==spec_reg)?spec_color:frame_color;
                    //bimage[(y+1)*w+x]=(seg[(y+1)*w+x]==spec_reg)?spec_color:frame_color;

                }
            }
        }

        return bimage;
    }

    //show the regions by frames
    void displayRgns_frame(int[] source, int w, int h, int blkSize, int[] seg, String title)
        {
            int[]bigSeg=getFineRegionMap(w,h,blkSize,seg);
            int[] bimage= get_displayRgns_frame(source, w, h, bigSeg);
        //(new yi.iu.ui.DisplayFrame(title, bimage, w, h)).show();
        (new SegFrame(title, bimage, w, h, bigSeg)).show();
    }

    int[] getFineRegionMap(int w, int h, int blkSize, int[] seg) {
        int wr=w/blkSize, hr=h/blkSize;
        int[] bigSeg= new int[w*h];
        for (int y=0;y<hr;y++) {
            for (int x=0;x<wr;x++) {
                int label= seg[y*wr+x];
                for (int i=0;i<blkSize;i++) {
                    for (int j=0;j<blkSize;j++) {
                        bigSeg[(y*blkSize+i)*w+(x*blkSize+j)]=label;
                    }
                }
            }
        }
            return bigSeg;
    }

    //show the regions by pseudocolor
    void displayRgns_color(int w, int h, int blkSize, int[] seg, String title)
    {
        int wr=w/blkSize, hr=h/blkSize;
        int[] bigSeg= new int[w*h];
        for (int y=0;y<hr;y++) {
            for (int x=0;x<wr;x++) {
                int label= seg[y*wr+x];
                for (int i=0;i<blkSize;i++) {
                    for (int j=0;j<blkSize;j++) {
                        bigSeg[(y*blkSize+i)*w+(x*blkSize+j)]=label;
                    }
                }
            }
        }
        int[] segimg= yi.util.ImageUtil.makeNewImageFromLabel(bigSeg);
        (new SegFrame(title, segimg, w, h, bigSeg)).show();
    }

/*******************************************************************************
 functions to set up the arguments
*******************************************************************************/
    int rgn1=0;
    int rgn2=0;
    int rgn3=0;
    int rgn4=0;
    public int getArguNum() { return 5;}

    public void setArgument(int i, String st)
    {
        if (st.length()==0) return;
        if (i==0) {
            DISTANCE_THRESHOLD= Integer.valueOf(st).intValue();
        }
        if (i==1) {
            BSCRGNSIZE= Integer.valueOf(st).intValue();
        }
        if (i==2) {
            STOPRGNSIZE= Integer.valueOf(st).intValue();
        }

        if (i==3) {
            rgn1= Integer.valueOf(st).intValue();
        }
        if (i==4) {
            rgn2= Integer.valueOf(st).intValue();
        }
/*
        if (i==3) {
            rgn3= Integer.valueOf(st).intValue();
        }
        if (i==4) {
            rgn4= Integer.valueOf(st).intValue();
        }
*/
    }


    public String getArgument(int i)
    {
        if (i==0) return (new Integer(DISTANCE_THRESHOLD)).toString();
        if (i==1) return (new Integer(BSCRGNSIZE)).toString();
        if (i==2) return (new Integer(STOPRGNSIZE)).toString();

        if (i==3) return (new Integer(rgn1)).toString();
        if (i==4) return (new Integer(rgn2)).toString();
/*
        if (i==3) return (new Integer(rgn3)).toString();
        if (i==4) return (new Integer(rgn4)).toString();
*/
        return null;
    }

    public String getArguName(int i)
    {
        if (i==0) return "diff_threshold";
        if (i==1) return "basic region size";
        if (i==2) return "stop region size";

        if (i==3) return "rgn #1";
        if (i==4) return "rgn #2";
/*
        if (i==3) return "rgn #3";
        if (i==4) return "rgn #4";
*/
        return null;
    }


/*******************************************************************************
 functions maybe trash
*******************************************************************************/

        /*
        //find the prominent region in the labeled image
        int[] getPromRegion(int[] label, int w, int h, int reg_size_thrsh)
        {
            //next_label is the number of regions
            int[] regC= new int[next_label];
            //count the size of the regions
            for (int i=0;i<label.length;i++) regC[label[i]]++;

            //eliminate the small region
            int regions=1;
            regC[0]=0;
            for (int i=1;i<regC.length;i++) {
                if (regC[i]==0) regions=i+1;
                if (regC[i]<=reg_size_thrsh) regC[i]=0;
                else regC[i]=regions++;
            }
            if (VERBOSE) System.err.println(regions-1+" regions remain");
            for (int i=0;i<label.length;i++) label[i]=regC[label[i]];
            next_label=regions;
            return label;
        }

    int[] removeSmall(int[] segs, int thrsh)
    {
        int max=0;
        for (int i=0;i<segs.length;i++) if (segs[i]>max) max=segs[i];
        int[] labels= new int[max+2];
        for (int i=0;i<segs.length;i++){
            if (segs[i]==0) segs[i]=max+1;
            labels[segs[i]]++;
        }
        for (int i=0;i<segs.length;i++)
            if (labels[segs[i]]<thrsh) segs[i]=0;
        int index=1;
        for (int i=1;i<labels.length;i++) if (labels[i]>=thrsh) labels[i]=index++;
        for (int i=0;i<segs.length;i++)
            segs[i]=labels[segs[i]];
        return segs;

    }
        */
}