ConnComp.java

import java.util.*;
import java.awt.image.*;
import java.io.*;

public class ConnComp {
    int nobjs;

    public BufferedImage label2rgb(BufferedImage img) {
        int w1 = img.getWidth();
        int h1 = img.getHeight();

	int type = BufferedImage.TYPE_INT_RGB;
        BufferedImage out = new BufferedImage(w1, h1, type);// new image

        int  v, c;
	int value[] = new int[w1];
	int zero = 0xFF000000;
	int [] colormap = {0xFFFF00FF,0xFFFF0000,0xFF00FF00,0xFF0000FF,0xFFFFFF00,0xFF00FFFF};
	int clen = colormap.length;

        for (int j = 0; j < h1; j++) {
           img.getRGB(0, j, w1, 1, value, 0, w1); // read and store pixel value
       	   for (int i = 0; i < w1; i++) {
		v = value[i]&0xFFFFFF;
		if (v>0) value[i] = colormap[v%clen];
	   }
	   out.setRGB(0, j, w1, 1, value, 0, w1);
	}
	return out;
}


    public BufferedImage connect(BufferedImage img) {
        int w1 = img.getWidth();
        int h1 = img.getHeight();

	int type = BufferedImage.TYPE_INT_RGB;
        BufferedImage out = new BufferedImage(w1, h1, type);// new image

        int  v, r, g, b, c;
	int value[] = new int[w1];
	ArrayList<Run> A = new ArrayList<Run>();
	ArrayList<Run> B = new ArrayList<Run>();
	Run rn=null;
	boolean active = false;
	int count = 0;
	ArrayList<Merge> mlist = new ArrayList<Merge>();
        for (int j = 0; j < h1; j++) {
           img.getRGB(0, j, w1, 1, value, 0, w1); // read and store pixel value
       	   for (int i = 0; i <= w1; i++) {
		try {
 			v = value[i];
		}
		catch(ArrayIndexOutOfBoundsException e) {
			v=0;
                }
		v = v & 0xFFFFFF;
		if (active && v==0) {
		        rn.nlast = i-1;
			active = false;
			for (Run ra: A) {
				int n = Run.compare(rn,ra);
				// n==0 means runs overlap
				if (n==0) {
					if (rn.nlabel==0) rn.nlabel = ra.nlabel;
					else if (rn.nlabel != ra.nlabel) {
						Merge m = new Merge(ra,rn);
						boolean isdup = false;
						for (Merge mt: mlist) {
							if (m.equals(mt)) isdup = true;
						}
						if (!isdup) mlist.add(m);
					}
				}
				if (n<0) break;
			}
			if (rn.nlabel==0) rn.nlabel = ++count;
				
		}
		else if (!active && v>0) {
			active = true;
			rn = new Run(i);
			B.add(rn);
		}
            }
	    for (Run rb: B) {
		for (int i=rb.nfirst; i<=rb.nlast; i++) value[i] = rb.nlabel;
	    }
	    out.setRGB(0, j, w1, 1, value, 0, w1);
 
	    // exchange lists
	    ArrayList<Run> swp = A;
	    A = B;
            B = swp;
	    B.clear();

       }
	nobjs = count;
	if (mlist.isEmpty()) return out;
	int [] lookup = new int[count+1];
	for (int i=0; i<=count; i++) lookup[i] = i;
	for (Merge m: mlist) m.doMerge(lookup);
     	renumber(lookup);
	nobjs = 0;
	for (int k: lookup) nobjs = k>nobjs? k: nobjs;
        for (int j = 0; j < h1; j++) {
           out.getRGB(0, j, w1, 1, value, 0, w1);
       	   for (int i = 0; i < w1; i++) {
		v = value[i]&0xFFFFFF;
		try { value[i] = lookup[v]; }
		catch(ArrayIndexOutOfBoundsException e) {
			value[i] = 0;
                }
	   }
	   out.setRGB(0, j, w1, 1, value, 0, w1);
	}

	return out;
    }

   void showtable(int [] table,String title) {
	System.out.println(title);
   	for (int i=1; i<table.length; i++) {
		System.out.format("%3d ",table[i]);
		if ((i%12)==0) System.out.println();
    	}
	System.out.println();
   }

    void renumber(int [] table) {
    	for (int i=1; i<table.length; i++) {
		if (missing(table, i)) {
		int nt = nextfound(table,i);
		for (int k=1; k<table.length; k++) {
			if (table[k]==nt) table[k] = i;
		   }
		}
	 }
    }



   int nextfound(int [] table, int nq) {
	for (int n: table) {
		if (n>nq) return n;
	}
	return -1;
  }

   boolean missing(int [] table, int nq) {
	for (int n: table) 
		if (n==nq) return false;	
	return true;
   }
}

class Run {
   int nfirst, nlast, nlabel;
   Run(int nstart) {
	nfirst = nstart;
    }
    public String toString() {
	return nlabel + "  " + nfirst + " : "+nlast;
    }
    public static int compare(Run A, Run B) {
	if (A.nlast <B.nfirst-1) return -1; // A is left of B
	if (A.nfirst>B.nlast+1) return 1; // A is right of B
	return 0; // overlap
    }
}

class Merge {
    int na, nb;
    Merge(Run A, Run B) {
	na = A.nlabel;
	nb = B.nlabel;
    }
    public String toString() {
	return "merge " + na + " with " + nb;
    }

    public boolean equals(Merge t) {
	if (na==t.na && nb==t.nb) return true;
	if (na==t.nb && nb==t.na) return true;
	return false;
    }

    public void doMerge(int [] lookup) {
	int nt = lookup[na];
	for (int i=0; i<lookup.length; i++) {
		if (lookup[i]==nt) lookup[i]=lookup[nb];
	}
    }
}