图像分析------连通组件标记算法-阿里云开发者社区

图像分析------连通组件标记算法

2015-07-24 2097

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： <p style="color: rgb(51, 51, 51); font-family: Arial; font-size: 14px; line-height: 26px;">连接组件标记算法(connected component labeling algorithm)是图像分析中最常用的算法之一，</p><p style="color: rgb(51, 51, 51); font-

连接组件标记算法(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类

算法运行结果：

根据标记的索引将组件着色。

定义数据结构的代码如下：

[java]view plaincopy
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的代码如下：

[java]view plaincopy
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如下：

[java]view plaincopy
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的代码如下：

[java]view plaincopy
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);  
                            }  
                        }  
                    }  
                }  
            }  
        }  
    }  
}  

图像分析------连通组件标记算法

热门文章

最新文章

相关课程

相关电子书

相关实验场景