连通组件标记算法–算法修正版

简介: 连通组件标记算法–算法修正版 昨天使用自己修改的连通组件标记算法代码去对一个稍微复杂点的图片做皮肤的最大连通 区域识别,发现Java报了栈溢出错误,自己想了想,感觉是合并标记时其中一段递归的代 码的问题,修改为非递归以后,运行结果吓我一跳,发现更加的不对,最后发现原来我读 取标记时候使用了逻辑操作符&,导致标记超过255时候被低位截取。

连通组件标记算法–算法修正版

昨天使用自己修改的连通组件标记算法代码去对一个稍微复杂点的图片做皮肤的最大连通

区域识别,发现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();
		}
	}

}
目录
相关文章
|
11月前
|
JSON 算法 数据挖掘
基于图论算法有向图PageRank与无向图Louvain算法构建指令的方式方法 用于支撑qwen agent中的统计相关组件
利用图序列进行数据解读,主要包括节点序列分析、边序列分析以及结合节点和边序列的综合分析。节点序列分析涉及节点度分析(如入度、出度、度中心性)、节点属性分析(如品牌、价格等属性的分布与聚类)、节点标签分析(如不同标签的分布及标签间的关联)。边序列分析则关注边的权重分析(如关联强度)、边的类型分析(如管理、协作等关系)及路径分析(如最短路径计算)。结合节点和边序列的分析,如子图挖掘和图的动态分析,可以帮助深入理解图的结构和功能。例如,通过子图挖掘可以发现具有特定结构的子图,而图的动态分析则能揭示图随时间的变化趋势。这些分析方法结合使用,能够从多个角度全面解读图谱数据,为决策提供有力支持。
421 0
|
12月前
|
存储 算法 Java
【JVM】垃圾释放方式:标记-清除、复制算法、标记-整理、分代回收
【JVM】垃圾释放方式:标记-清除、复制算法、标记-整理、分代回收
292 2
|
XML JavaScript 前端开发
学习react基础(1)_虚拟dom、diff算法、函数和class创建组件
本文介绍了React的核心概念,包括虚拟DOM、Diff算法以及如何通过函数和类创建React组件。
155 3
|
算法 Java
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
Java面试题:解释垃圾回收中的标记-清除、复制、标记-压缩算法的工作原理
212 1
|
算法 Java
Java演进问题之标记-复制算法导致更多的内存占用如何解决
Java演进问题之标记-复制算法导致更多的内存占用如何解决
104 0
|
算法 Java 程序员
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
Java面试题:解释Java的垃圾回收机制,包括常见的垃圾回收算法。介绍一下Java的垃圾回收算法中的标记-压缩算法。
123 0
|
存储 算法 安全
JVM-内存划分-垃圾回收器-回收算法-双亲委派-三色标记
JVM-内存划分-垃圾回收器-回收算法-双亲委派-三色标记
|
7天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
8天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
|
10天前
|
负载均衡 算法 调度
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
基于遗传算法的新的异构分布式系统任务调度算法研究(Matlab代码实现)
82 11

热门文章

最新文章