图像处理之基于图的广度优先搜索组件标记算法-CDA数据分析师官网

热线电话：13121318867

首页精彩阅读图像处理之基于图的广度优先搜索组件标记算法

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

2014-12-07

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

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

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

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

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

20140329134814359

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

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

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

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

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

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

20140329134906984

1. 遍历每个节点- BFS

2. 输出结果与显示

三：运行效果

20140329135014578

四：关键程序实现代码

图的搜索算法，节点状态有三种，未访问(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++;
								
									                }
								
									            }
								
									        }
								
									    }
								
									}