图像处理之连接组件标记算法
连接组件标记算法(connected component labeling algorithm)是图像分析中最常用的算法之一，
算法的实质是扫描一幅图像的每个像素，对于像素值相同的分为相同的组(group),最终得到
图像中所有的像素连通组件。扫描的方式可以是从上到下，从左到右，对于一幅有N个像
素的图像来说，最大连通组件个数为N/2。扫描是基于每个像素单位，对于二值图像而言，
连通组件集合可以是V={1}或者V={0}, 取决于前景色与背景色的不同。对于灰度图像来说，
连图组件像素集合可能是一系列在0 ～ 255之间的灰度值。
算法流程如下：
1. 首先扫描当前像素相邻的八邻域像素值，发现连通像素加以标记。
2. 完全扫描所有像素点之后，根据标记将所有连通组件合并。
算法实现Class文件解释：
AbstractConnectedComponentLabel：一个抽象的Class定义了抽象方法doConntectedLabel()
同时完成了一些公共方法
ConnectedComponentLabelAlgOne：一个容易读懂的连接组件算法完成，没有任何优化，
继承上面的自抽象类
ConnectedComponentLabelAlgTwo：一个快速的连接组件算法，基于算法优化，取当前像素
的四邻域完成扫描与标记合并。
Label与PixelInfo是两个数据结构，用来存储算法计算过程中的中间变量。
ImageLabelFilter用来测试算法的驱动类，ImageAnalysisUI是现实测试结果的UI类
算法运行结果：
根据标记的索引将组件着色。
定义数据结构的代码如下：
public class Label { private int index; private Label root; public Label(int index) { this.index = index; this.root = this; } public Label getRoot() { if(this.root != this) { this.root = this.root.getRoot(); } return root; } public int getIndex() { return index; } public void setIndex(int index) { this.index = index; } public void setRoot(Label root) { this.root = root; } }
Pixelnfo的代码如下：
package com.gloomyfish.image.analysis; public class PixelInfo { private int value; // pixel value private int xp; private int yp; public PixelInfo(int pixelValue, int yp, int xp) { this.value = pixelValue; this.yp = yp; this.xp = xp; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public int getXp() { return xp; } public void setXp(int xp) { this.xp = xp; } public int getYp() { return yp; } public void setYp(int yp) { this.yp = yp; } }
抽象的组件连通标记算法Class如下：
public abstract class AbstractConnectedComponentLabel { protected int width; protected int height; protected Color fgColor; protected int[] inPixels; protected int[][] chessborad; protected Map<Integer, Integer> neighbourMap; public int getWidth() { return width; } public void setWidth(int width) { this.width = width; } public int getHeight() { return height; } public void setHeight(int height) { this.height = height; } public abstract Map<Integer, List<PixelInfo>> doConntectedLabel(); public boolean isForeGround(int tr, int tg, int tb) { if(tr == fgColor.getRed() && tg == fgColor.getGreen() && tb == fgColor.getBlue()) { return true; } else { return false; } } }
实现抽象类的算法one的代码如下：
import java.awt.Color; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class ConnectedComponentLabelAlgOne extends AbstractConnectedComponentLabel { public ConnectedComponentLabelAlgOne(Color fgColor, int[] srcPixel, int width, int height) { this.fgColor = fgColor; this.width = width; this.height = height; this.inPixels = srcPixel; this.chessborad = new int[height][width]; for(int i=0; i<height; i++) { for(int j=0; j<width; j++) { chessborad[i][j] = 0; } } this.neighbourMap = new HashMap<Integer, Integer>(); } // assume the input image data is binary image. public Map<Integer, List<PixelInfo>> doConntectedLabel() { System.out.println("start to do connected component labeling algorithm"); int index = 0; int labelCount = 0; Label currentLabel = new Label(0); HashMap<Integer, Label> allLabels = new HashMap<Integer, Label>(); for(int row=0; row<height; row++) { int ta = 0, tr = 0, tg = 0, tb = 0; for(int col=0; col<width; col++) { index = row * width + col; ta = (inPixels[index] >> 24) & 0xff; tr = (inPixels[index] >> 16) & 0xff; tg = (inPixels[index] >> 8) & 0xff; tb = inPixels[index] & 0xff; if(isForeGround(tr, tg, tb)) { getNeighboringLabels(row, col); if(neighbourMap.size() == 0) { currentLabel.setIndex(++labelCount); allLabels.put(labelCount,new Label(labelCount)); } else { for(Integer pixelLabel : neighbourMap.keySet().toArray(new Integer[0])) { currentLabel.setIndex(pixelLabel); break; } mergeLabels(currentLabel.getIndex(), neighbourMap, allLabels); } chessborad[row][col] = currentLabel.getIndex(); } } } Map<Integer, List<PixelInfo>> connectedLabels = consolidateAllLabels(allLabels); return connectedLabels; } private Map<Integer, List<PixelInfo>> consolidateAllLabels(HashMap<Integer, Label> allLabels) { Map<Integer, List<PixelInfo>> patterns = new HashMap<Integer, List<PixelInfo>>(); int patternNumber; List<PixelInfo> shape; for (int i = 0; i < this.height; i++) { for (int j = 0; j < this.width; j++) { patternNumber = chessborad[i][j]; if (patternNumber != 0) { patternNumber = allLabels.get(patternNumber).getRoot().getIndex(); if (!patterns.containsKey(patternNumber)) { shape = new ArrayList<PixelInfo>(); shape.add(new PixelInfo(Color.BLUE.getRGB(), i, j)); } else { shape = patterns.get(patternNumber); shape.add(new PixelInfo(Color.BLUE.getRGB(), i, j)); } patterns.put(patternNumber, shape); } } } return patterns; } private void mergeLabels(int index, Map<Integer, Integer> neighbourMap, HashMap<Integer, Label> allLabels) { Label root = allLabels.get(index).getRoot(); Label neighbour; for(Integer key : neighbourMap.keySet().toArray(new Integer[0])) { if (key != index) { neighbour = allLabels.get(key); if(neighbour.getRoot() != root) { neighbour.setRoot(neighbour.getRoot());// thanks zhen712, } } } } /** * get eight neighborhood pixels * * @param row * @param col * @return */ public void getNeighboringLabels(int row, int col) { neighbourMap.clear(); for(int i=-1; i<=1; i++) { int yp = row + i; if(yp >=0 && yp < this.height) { for(int j=-1; j<=1; j++) { if(i == 0 && j==0) continue; // ignore/skip center pixel/itself int xp = col + j; if(xp >=0 && xp < this.width) { if(chessborad[yp][xp] != 0) { if(!neighbourMap.containsKey(chessborad[yp][xp])) { neighbourMap.put(chessborad[yp][xp],0); } } } } } } } }
测试代码可以参考以前的文章 -
