Saturday, August 13, 2011

Implementation for Connected Componenet Labeling

the following code is based on the information that i got from this page.
http://en.wikipedia.org/wiki/Connected-component_labeling
import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;


public class ConnectedComponent {

/**
*
@param args
*/
public static void main(String[] args) {
//int [][]data={{1,0,1},{0,0,1},{1,0,1}};
/*00100011010000101011111
10100011110010001110000
10001011000000010011000
*/
int [][]data={{0,0,1,0,0,0,1,1,0,1,0,0,0,0,1,0,1,0,1,1,1,1,1},{1,0,1,0,0,0,1,1,1,1,0,0,1,0,0,0,1,1,1,0,0,0,0},{1,0,0,0,1,0,1,1,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0}};

//get the lable matrix
int [][] result = TwoPassAlgorithm(data);

//find the size of available lands
int rowLength = result.length;
Hashtable
<Integer, Integer> sizeCalculator = new Hashtable<Integer, Integer>();
for(int i=0; i<rowLength; i++){
int []resultRow = result[i];
int columnLength = resultRow.length;
for(int j=0; j<columnLength; j++){
int key = result[i][j];
if(key==0)
continue;
if(sizeCalculator.containsKey(key)){
Integer value
= sizeCalculator.remove(key);
value
= value + 1;
sizeCalculator.put(key, value);
}
else{
sizeCalculator.put(key,
1);
}
}
}

//find the big land
Enumeration<Integer> Lands = sizeCalculator.elements();
int max = 0;
while(Lands.hasMoreElements()){
int landSize = Lands.nextElement();
if(landSize > max)
max
= landSize;
}
System.out.println(max);
}
public static int[][]TwoPassAlgorithm(int[][]data){
int rowLength = data.length;
int columnLength = data[0].length;
int [][]Labels = new int[rowLength][columnLength];
//int result[rowLength][columnLength];//throws token error.

//first pass
int nextLabel = 2;
Hashtable
<Integer, ArrayList<Integer>> Linker = new Hashtable<Integer, ArrayList<Integer>>();
for(int i=0;i<rowLength;i++){
for(int j=0;j<columnLength;j++){
if(data[i][j]!=0){
int []neighbourLabels = getNeighbourLabels(Labels, i, j);
if(neighbourLabels == null){
ArrayList
<Integer> value = new ArrayList<Integer>();
value.add(nextLabel);
Linker.put(nextLabel,value);
Labels[i][j]
=nextLabel;
nextLabel
++;
}
else{
Labels[i][j]
= minimum(neighbourLabels);
for(int k=0; k<neighbourLabels.length; k++){
Linker
= union(Linker,neighbourLabels[k],neighbourLabels);
}
}
}
else{
Labels[i][j]
=0;
}
}
}

//Second pass
for(int i=0;i<rowLength;i++){
for(int j=0;j<columnLength;j++){
if(Labels[i][j]!=0){
Labels[i][j]
= minimum(Linker.get(Labels[i][j]));
}
}
}
return Labels;
}
public static int[] getNeighbourLabels(int[][]Labels, int row,int column){
ArrayList
<Integer> neighbourLabels = new ArrayList<Integer>();
int columnLimit = Labels[0].length;
column
--;
if(column>=0 && Labels[row][column]!=0)
neighbourLabels.add(Labels[row][column]);
row
--;
if(column>=0 && row>=0 && Labels[row][column]!=0)
neighbourLabels.add(Labels[row][column]);
column
++;
if(column>=0 && column<columnLimit && row>=0 && Labels[row][column]!=0)
neighbourLabels.add(Labels[row][column]);
column
++;
if(column>=0 && column<columnLimit && row>=0 && Labels[row][column]!=0)
neighbourLabels.add(Labels[row][column]);

int neighbourLabelsSize = neighbourLabels.size();
if(neighbourLabelsSize != 0){
int [] neighbourLabelsArray = new int[neighbourLabelsSize];
for(int i=0;i<neighbourLabelsSize; i++){
neighbourLabelsArray[i]
= neighbourLabels.get(i);
}
return neighbourLabelsArray;
}
return null;
}
public static int minimum(int[]labels){
int minimumLabel = labels[0];
for(int i=1;i<labels.length;i++){
if(minimumLabel>labels[i])
minimumLabel
= labels[i];
}
return minimumLabel;
}
public static int minimum(ArrayList<Integer>labels){
int minimumLabel = labels.get(0);
for(int i=1;i<labels.size();i++){
if(minimumLabel>labels.get(i))
minimumLabel
= labels.get(i);
}
return minimumLabel;
}
public static Hashtable<Integer, ArrayList<Integer>> union(Hashtable<Integer, ArrayList<Integer>> Linker, int key, int[] unionValues){
for(int i=0;i<unionValues.length;i++){
if(!Linker.get(key).contains(unionValues[i]))
Linker.get(key).add(unionValues[i]);
}
return Linker;
}

}

No comments:

Post a Comment