连通组件标记算法–算法修正版
昨天使用自己修改的连通组件标记算法代码去对一个稍微复杂点的图片做皮肤的最大连通
区域识别,发现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();
}
}
}
分享到:
相关推荐
包含该两种连通区域标记算法说明和代码,欢迎使用。
本资源介绍了一种高效的基于二值图像的连通域标记的算法
针对传统Hough变换进行圆检测,计算量过大、检测同心圆精度不高、自动化程度低等缺点,提出一种基于连通区域标记算法的圆检测算法。该算法首先通过连通区域标记算法对图像进行处理得到一个圆,解决了传统Hough变换...
一次扫描连通区域标记算法C++
本代码根据计算机视觉的二值图像分析的逐行标记算法编写,实现连通成分标记功能
c++连通区域标记,c++连通区域标记,功能和matlab 中的 bwlabel相似
基于跑长码的连通区域标记算法,大大提高连通区域的标记速度,比种子增长法快很多。
连通组件标记演算法源碼
基于模糊理论的连通区域标记算法,算法速度很快,C++编写的一个类
这是非常实用的VC代码,用于二值图像连通区域的标记,请大家参考
传统的弱信号恢复方法在强噪声背景下具有较大的局限性,有用的信息往往淹没在强噪声背景下不易被识别。针对这个难点,提出一种基于三维曲波变换的弱信号恢复的方法。该方法将三维曲波变换和自适应滤波器相融合,从而...
采用灰度图像创建Maxtree的基本思想,提出一种新的二值图像连通区域标记算法。该算法主要采用8邻域搜索及排序队列方式实现,通过一次扫描二值图像即可完成连通区域标记。提出一种新的8邻域搜索策略,可以将...
二值图像 连通区域 标记 算法.O(N)
连接组件标记问题:最新算法综述
本文要介绍的是两年前我自己琢磨出来的一种用FPGA实现的二值图像连通域标记算法。这个算法的特点是它是一个基于逐行扫描的流水线算法,也就是说这个算法只需要缓存若干行的图像数据,并在这若干行的固定延时内就给出...
二值图像的连通区域标记,easy to label an binary image
首先,在进行标记算法以前,利用硬件开辟独立的图像标记缓存和连通关系数组,接着在视频流的采集传输过程中,以流水线的方式按照视频传输顺序对图像进行逐行像素扫描,然后对每个像素的邻域分别按照逆时针方向和...
c++连通区域标记算法2,功能和matlab 中的 bwlabel相似,用opencv 编写
基于共同连通域数组的二次扫描算法的matlab实现