图像处理之基于图的广度优先搜索组件标记算法
一：图的遍历与广度优先搜索算法
图的遍历算法最常用是广度优先搜索算法(BFS)与深度优先搜索算法(DFS)，从一个的
节点开始，访问相邻的所有子节点，接着从这些子节点出发访问下个相邻子节点，如
此重复直到所有节点都被访问。
二：二值图像组件标记实现流程
如果把图像的每个像素点看成为图的一个节点，则二值图像中的每个连通区域都可以
看成一个无向图，只要遍历图像中的每个像素点就可以找出每个连通区域，实现对二
值图像连通区域组件的标记。大致步骤为：
1. 扫描图像的每个像素点，获得位置信息与图像的灰度值强度(0~255)成为图的节点
2. 对每个节点，初始化状态与获取它的上下左右四个邻域节点
1. 遍历每个节点- BFS
2. 输出结果与显示
三：运行效果
四：关键程序实现代码
图的搜索算法，节点状态有三种，未访问(Unvisit)，已经访问(Visited)，已经标记(Marked)
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; } }
转载请务必注明
