Connected Components

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

public class Connect1  {

	static int passes;

   public static void main(String [] args) {
         // load the image
	String filename = args.length>0? args[0]: "uvwb.png";
	int mag = args.length>1? Integer.parseInt(args[1]): 1;
	passes  = args.length>2? Integer.parseInt(args[2]): 2;

	if (passes!=1) passes=2;
	String[] tokens = filename.split("[.]");
	String outfile = tokens[0]+"_pass"+passes;

	 ImageFrame f1 = new ImageFrame(filename);
	 f1.setLocation(100,100);
	 f1.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

	BufferedImage out1 = convert1(f1.img);
        ImageFrame.writeImage(out1,"raw","png");

	BufferedImage out2 = label2rgb(out1);

	 ImageFrame f2 = new ImageFrame(out2,"labeled");
	 f2.setLocation(140+f1.getWidth(),100);
	 f2.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
 	 f2.writeImage(out2,"labeled","png");
		
    }

    public static BufferedImage convert1(BufferedImage img) {

        int w1 = img.getWidth();
        int h1 = img.getHeight();
	System.out.println("image size: " + w1 + " x " + h1);

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

        int  v, r, g, b, c, n;
	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 values
       	   for (int i = 0; i <= w1; i++) {
		try { v = value[i] & 0xFFFFFF; }
		catch(ArrayIndexOutOfBoundsException e) {v=0;}

		if (!active && v>0) {
			active = true;
			rn = new Run(i);
			B.add(rn);
		}		
		else if (active && v==0) {
		        rn.nlast = i-1;
			active = false;
			check_overlap(rn,A,mlist);
			if (rn.nlabel==0) rn.nlabel = ++count;
		}
            }
	    for (Run rb: B) {
		c = rb.nlabel;
		for (int i=rb.nfirst; i<=rb.nlast; i++) value[i] = c;
	    }
	    out.setRGB(0, j, w1, 1, value, 0, w1);
 
	    // exchange lists
	    ArrayList<Run> swp = A;
	    A = B;
            B = swp;
	    B.clear();
       }
	int nobjs = count;
	if (mlist.isEmpty()) {
	    System.out.println(nobjs + " Objects found (no merges)");
	    return out;
	}
	// show results of pass 1 if requested
	if (passes==1) return out;


	boolean seelookup = false;
	
	if (seelookup) System.out.println(mlist.size()+" merges found");
	
	int [] lookup = new int[count+1];
	for (int i=0; i<=count; i++) lookup[i] = i;
	if (seelookup) showtable(lookup,"start");
	for (Merge m: mlist) {
		m.doMerge(lookup);
		if (seelookup) showtable(lookup,""+m);
	}
     	renumber(lookup);
	if (seelookup) showtable(lookup,"renumber");
	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);
	}

	System.out.println(nobjs + " Objects found");
	return out;
    }


   static 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%16)==0) System.out.println();
    	}
	System.out.println();
   }

    static 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;
		   }
		}
	 }
    }



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

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


    static void check_overlap(Run rn, ArrayList<Run> A, ArrayList<Merge> mlist) {
	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; break; }
		}
		if (!isdup) mlist.add(m);
	     }
	  }
	  // n<0 means remaining runs are to right
	  else if (n<0) break;
	}
    }

    public static 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 [] colormap = {0xFFFF0000,0xFF00FF00,0xFF0000FF,0xFFFFFF00,0xFF00FFFF,0xFFFF00FF};
	int clen = colormap.length;
	int value[] = new int[w1];
	int v;
	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] & 0xFFFFFF; }
		catch(ArrayIndexOutOfBoundsException e) {v=0;}
 		if (v>0) value[i] = colormap[(v-1)%clen];
	   }
	   out.setRGB(0, j, w1, 1, value, 0, w1);
	}
	return out;
   }
}

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

class Merge {
    int na, nb;
    Merge(Run ra, Run rb) {
	na = ra.nlabel;
	nb = rb.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 ma = lookup[na];
	int mb = lookup[nb];
	for (int i=0; i<lookup.length; i++) {
		if (lookup[i]==ma) lookup[i]=mb;
	}
    }
}