连通组件标记算法–算法修正版
昨天使用自己修改的连通组件标记算法代码去对一个稍微复杂点的图片做皮肤的最大连通
区域识别，发现Java报了栈溢出错误，自己想了想，感觉是合并标记时其中一段递归的代
码的问题，修改为非递归以后，运行结果吓我一跳，发现更加的不对，最后发现原来我读
取标记时候使用了逻辑操作符&，导致标记超过255时候被低位截取。为了找到这个错误，
花了一个下午的时间重新完成了代码与测试。
一：基本原理如下
以前的有问题的算法版本连接，看这里：
http://blog.csdn.net/jia20003/article/details/7596443
二：完整的算法代码如下：
package com.gloomyfish.face.detection;
import java.util.Arrays;
import java.util.HashMap;
/**
* fast connected component label algorithm
*
* @date 2012-05-23
* @author zhigang
*
*/
public class AdjustableConnectedComponentLabelAlg {
private int bgColor;
public int getBgColor() {
return bgColor;
}
public void setBgColor(int bgColor) {
this.bgColor = bgColor;
}
private int[] outData;
private int dw;
private int dh;
public AdjustableConnectedComponentLabelAlg() {
bgColor = 255; // black color
}
public int[] doLabel(int[] inPixels, int width, int height) {
dw = width;
dh = height;
int nextlabel = 1;
int result = 0;
outData = new int[dw * dh];
for(int i=0; i<outData.length; i++) {
outData[i] = 0;
}
// we need to define these two variable arrays.
int[] eightNeighborhoodPixels = new int[8];
int[] eightNeighborhoodLabels = new int[8];
int[] knownLabels = new int[8];
int srcrgb = 0, index = 0;
boolean existedLabel = false;
for(int row = 0; row < height; row ++) {
for(int col = 0; col < width; col++) {
index = row * width + col;
srcrgb = inPixels[index] & 0x000000ff;
if(srcrgb == bgColor) {
result = 0; // which means no labeled for this pixel.
} else {
// we just find the eight neighborhood pixels.
eightNeighborhoodPixels[0] = getPixel(inPixels, row-1, col); // upper cell
eightNeighborhoodPixels[1] = getPixel(inPixels, row, col-1); // left cell
eightNeighborhoodPixels[2] = getPixel(inPixels, row+1, col); // bottom cell
eightNeighborhoodPixels[3] = getPixel(inPixels, row, col+1); // right cell
// four corners pixels
eightNeighborhoodPixels[4] = getPixel(inPixels, row-1, col-1); // upper left corner
eightNeighborhoodPixels[5] = getPixel(inPixels, row-1, col+1); // upper right corner
eightNeighborhoodPixels[6] = getPixel(inPixels, row+1, col-1); // left bottom corner
eightNeighborhoodPixels[7] = getPixel(inPixels, row+1, col+1); // right bottom corner
// get current possible existed labels
eightNeighborhoodLabels[0] = getLabel(outData, row-1, col); // upper cell
eightNeighborhoodLabels[1] = getLabel(outData, row, col-1); // left cell
eightNeighborhoodLabels[2] = getLabel(outData, row+1, col); // bottom cell
eightNeighborhoodLabels[3] = getLabel(outData, row, col+1); // right cell
// four corners labels value
eightNeighborhoodLabels[4] = getLabel(outData, row-1, col-1); // upper left corner
eightNeighborhoodLabels[5] = getLabel(outData, row-1, col+1); // upper right corner
eightNeighborhoodLabels[6] = getLabel(outData, row+1, col-1); // left bottom corner
eightNeighborhoodLabels[7] = getLabel(outData, row+1, col+1); // right bottom corner
int minLabel = 0;
int count = 0;
for(int i=0; i<knownLabels.length; i++) {
if(eightNeighborhoodLabels[i] > 0) {
existedLabel = true;
knownLabels[i] = eightNeighborhoodLabels[i];
minLabel = eightNeighborhoodLabels[i];
count++;
}
}
if(existedLabel) {
if(count == 1) {
result = minLabel;
} else {
int[] tempLabels = new int[count];
int idx = 0;
for(int i=0; i<knownLabels.length; i++) {
if(knownLabels[i] > 0){
tempLabels[idx++] = knownLabels[i];
}
if(minLabel > knownLabels[i] && knownLabels[i] > 0) {
minLabel = knownLabels[i];
}
}
result = minLabel;
mergeLabels(index, result, tempLabels);
}
} else {
result = nextlabel;
nextlabel++;
}
outData[index] = result;
// reset and cleanup the known labels now...
existedLabel = false;
for(int kl = 0; kl < knownLabels.length; kl++) {
knownLabels[kl] = 0;
}
}
}
}
// labels statistic
HashMap<Integer, Integer> labelMap = new HashMap<Integer, Integer>();
for(int d=0; d<outData.length; d++) {
if(outData[d] != 0) {
if(labelMap.containsKey(outData[d])) {
Integer count = labelMap.get(outData[d]);
count+=1;
labelMap.put(outData[d], count);
} else {
labelMap.put(outData[d], 1);
}
}
}
// try to find the max connected component
Integer[] keys = labelMap.keySet().toArray(new Integer[0]);
Arrays.sort(keys);
int maxKey = 1;
int max = 0;
for(Integer key : keys) {
if(max < labelMap.get(key)){
max = labelMap.get(key);
maxKey = key;
}
System.out.println( "Number of " + key + " = " + labelMap.get(key));
}
System.out.println("maxkey = " + maxKey);
System.out.println("max connected component number = " + max);
return outData;
}
private void mergeLabels (int index, int result, int[] labels) {
for(int i=0; i<labels.length; i++) {
if(labels[i] == result) continue;
mergeLabel(index, result, labels[i]);
}
}
private void mergeLabel(int index, int result, int i) {
int row = index / dw;
int idx = 0;
for(int k = 0; k <= row; k++) {
for(int col = 0; col < dw; col++) {
idx = k * dw + col;
if(outData[idx] == i) {
outData[idx] = result;
}
}
}
}
private int getLabel(int[] data, int row, int col) {
// handle the edge pixels
if(row < 0 || row >= dh) {
return 0;
}
if(col < 0 || col >= dw) {
return 0;
}
int index = row * dw + col;
return (data[index] & 0xffffffff);
// it's difficulty for me to find the data overflow issue......
// return (data[index] & 0x000000ff); defect, @_@
}
private int getPixel(int[] data, int row, int col) {
// handle the edge pixels
if(row < 0 || row >= dh) {
return bgColor;
}
if(col < 0 || col >= dw) {
return bgColor;
}
int index = row * dw + col;
return (data[index] & 0x000000ff);
}
/**
* binary image data:
*
* 255, 0, 0, 255, 0, 255, 255, 0, 255, 255, 255,
* 255, 0, 0, 255, 0, 255, 255, 0, 0, 255, 0,
* 255, 0, 0, 0, 255, 255, 255, 255, 255, 0, 0,
* 255, 255, 0, 255, 255, 255, 0, 255, 0, 0, 255
* 255, 255, 0, 0, 0, 0, 255, 0, 0, 0, 0
*
* height = 5, width = 11
* @param args
*/
public static int[] imageData = new int[]{
255, 0, 0, 255, 0, 255, 255, 0, 255, 255, 255,
255, 0, 0, 255, 0, 255, 255, 0, 0, 255, 0,
255, 0, 0, 255, 255, 255, 255, 255, 255, 0, 0,
255, 255, 0, 255, 255, 255, 0, 255, 0, 0, 255,
255, 255, 0, 0, 0, 0, 255, 255, 0, 0, 0,
255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 0, 255, 0, 255, 0, 0, 255, 255, 255, 255,
255, 255, 0, 0, 255, 255, 255, 0, 0, 255, 255
};
public static void main(String[] args) {
AdjustableConnectedComponentLabelAlg ccl = new AdjustableConnectedComponentLabelAlg();
int[] outData = ccl.doLabel(imageData, 11, 8);
for(int i=0; i<8; i++) {
System.out.println("--------------------");
for(int j = 0; j<11; j++) {
int index = i * 11 + j;
if(j != 0) {
System.out.print(",");
}
System.out.print(outData[index]);
}
System.out.println();
}
}
}