图像处理之基于图的广度优先搜索组件标记算法

图像处理之基于图的广度优先搜索组件标记算法

一：图的遍历与广度优先搜索算法

图的遍历算法最常用是广度优先搜索算法(BFS)与深度优先搜索算法(DFS)，从一个的

节点开始，访问相邻的所有子节点，接着从这些子节点出发访问下个相邻子节点，如

此重复直到所有节点都被访问。

二：二值图像组件标记实现流程

如果把图像的每个像素点看成为图的一个节点，则二值图像中的每个连通区域都可以

看成一个无向图，只要遍历图像中的每个像素点就可以找出每个连通区域，实现对二

值图像连通区域组件的标记。大致步骤为：

1.      扫描图像的每个像素点，获得位置信息与图像的灰度值强度(0~255)成为图的节点

2.      对每个节点，初始化状态与获取它的上下左右四个邻域节点

1.      遍历每个节点- BFS

2.      输出结果与显示

三：运行效果

四：关键程序实现代码

package com.gloomyfish.image.watershed;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Breath First Search for graphics
 * @author gloomyfish
 *
 */
public class BFSAlgorithm {
	private List<PixelPoint> pixelList = null;
	private int grayLevel = 1;
	public int getGrayLevel() {
		return grayLevel;
	}
	
	public int getTotalOfLabels()
	{
		Map<Integer, Integer> labelMap = new HashMap<Integer, Integer>();
		for(PixelPoint p : pixelList)
		{
			if(p.getValue() >= grayLevel)
			{
				if(labelMap.containsKey(p.getLabel()))
				{
					Integer count = labelMap.get(p.getLabel());
					count += 1;
					labelMap.put(p.getLabel(), count);
				}
				else
				{
					labelMap.put(p.getLabel(), new Integer(1));
				}
			}
		}
		Integer[] keys = labelMap.keySet().toArray(new Integer[0]);
		for(Integer key : keys)
		{
			System.out.println("Label index : " + key);
		}
		System.out.println("total labels : " + labelMap.size());
		return labelMap.size();
	}

	public void setGrayLevel(int grayLevel) {
		this.grayLevel = grayLevel;
	}

	public BFSAlgorithm(List<PixelPoint> pixelList)
	{
		this.pixelList = pixelList;
		grayLevel = 1; // front color - target pixel
	}
	
	public void process()
	{
		if(this.pixelList == null) return;
		int label = 1;
		for(PixelPoint pp : pixelList)
		{
			if(pp.getValue() >= grayLevel)
			{
				if(pp.getStatus() == PixelPoint.UNMARKED)
				{
					pp.setStatus(PixelPoint.VISITED);
					pp.setLabel(label);
					MyQueue mq = new MyQueue(10000);
					for(PixelPoint npp : pp.getNeighbours())
					{
						if(npp.getStatus() == PixelPoint.UNMARKED && npp.getValue() >= grayLevel)
						{
							npp.setStatus(PixelPoint.MARKED);
							mq.enqueue(npp);
						}
					}
					while(!mq.isEmpty())
					{
						PixelPoint obj = (PixelPoint)mq.dequeue();
						if(obj.getStatus() == PixelPoint.MARKED)
						{
							obj.setLabel(label);
							obj.setStatus(PixelPoint.VISITED);
						}
						for(PixelPoint nnpp : obj.getNeighbours())
						{
							if(nnpp.getStatus() == PixelPoint.UNMARKED && nnpp.getValue() >= grayLevel)
							{
								nnpp.setStatus(PixelPoint.MARKED);
								mq.enqueue(nnpp);
							}
						}
					}
					label++;
				}
			}
		}
	}

}

package com.gloomyfish.image.watershed;

import java.awt.image.BufferedImage;
import java.util.ArrayList;
import java.util.List;

import com.gloomyfish.filter.study.AbstractBufferedImageOp;
/**
 * work for binary image
 * @author fish
 *
 */
public class LabelledConnectedRegionAlg extends AbstractBufferedImageOp {

	@Override
	public BufferedImage filter(BufferedImage src, BufferedImage dest) {
		int width = src.getWidth();
        int height = src.getHeight();

        if ( dest == null )
            dest = createCompatibleDestImage( src, null );
        List<PixelPoint> pixelList = new ArrayList<PixelPoint>();
        int[] inPixels = new int[width*height];
        int[] outPixels = new int[width*height];
        getRGB( src, 0, 0, width, height, inPixels );
        int index = 0;
        for(int row=0; row<height; row++) {
        	for(int col=0; col<width; col++) {
        		index = row * width + col;
        		PixelPoint p = new PixelPoint(row, col, (inPixels[index] >> 16) & 0xff);
        		pixelList.add(p);
        	}
        }
        
        for(int row=0; row<height; row++) {
        	for(int col=0; col<width; col++) {
        		index = row * width + col;
        		PixelPoint p = pixelList.get(index);
        		
        		// add four neighbors for each pixel
        		if((row - 1) >= 0)
        		{
        			index = (row-1) * width + col;
        			p.addNeighour(pixelList.get(index));
        		}
        		if((row + 1) < height)
        		{
        			index = (row+1) * width + col;
        			p.addNeighour(pixelList.get(index));
        		}
        		if((col - 1) >= 0)
        		{
        			index = row * width + col-1;
        			p.addNeighour(pixelList.get(index));
        		}
        		if((col+1) < width)
        		{
        			index = row * width + col+1;
        			p.addNeighour(pixelList.get(index));
        		}
        	}
        }

        BFSAlgorithm bfs = new BFSAlgorithm(pixelList);
        bfs.process();
        int labels = bfs.getTotalOfLabels();
        int unit = 255 / (labels+1);
        
        // post process - color different labels
        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;
        		PixelPoint p = pixelList.get(index);
        		ta = 255;
        		if(p.getLabel() > 0)
        		{
	        		tr = 0; // unit * p.getLabel();
	                tg = unit * p.getLabel();
	                tb = unit * p.getLabel();
        		}
        		else
        		{
            		tr = p.getValue();
                    tg = p.getValue();
                    tb = p.getValue();
        		}
                outPixels[index] = (ta << 24) | (tr << 16) | (tg << 8) | tb;
        	}
        }
        
        setRGB( dest, 0, 0, width, height, outPixels );
        return dest;
	}

}