热线电话：13121318867

登录
首页精彩阅读图像处理之基于图的广度优先搜索组件标记算法
图像处理之基于图的广度优先搜索组件标记算法
2014-12-07
收藏

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


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

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

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

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

20140329134814359


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

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

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

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

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

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

20140329134906984


1.      遍历每个节点- BFS

2.      输出结果与显示

三：运行效果

20140329135014578


四：关键程序实现代码

图的搜索算法，节点状态有三种，未访问(Unvisit)，已经访问(Visited)，已经标记(Marked)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
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++;
                }
            }
        }
    }
        
}

图像组件标记算法代码：



1
2
3
4
5
6


CDA数据分析师考试相关入口一览（建议收藏）：

▷ 想报名CDA认证考试，点击>>>   “CDA报名” 了解CDA考试详情；

▷ 想学习CDA考试教材，点击>>> “CDA教材” 了解CDA考试详情；

▷ 想加入CDA考试题库，点击>>> “CDA题库” 了解CDA考试详情；

▷ 想了解CDA考试含金量，点击>>> “CDA含金量” 了解CDA考试详情；

数据分析咨询请扫描二维码

若不方便扫码，搜微信号：CDAshujufenxi

上一篇随机森林 vs XGBoost vs 决策树：算法选择中的
下一篇图论在大数据分析中的作用！
数据分析师考试动态
CDA报考指南
数据分析学习
数据分析师资讯
更多

CDA教育闭环

常见问题

关于我们

CDA数据分析师公众号

  • CDA数据分析师公众号

CDA考试中心小程序

  • CDA考试中心服务号

CDA数据分析师App下载

  • CDA数据分析师App下载
Copyright © 2015-2021, www.cda.cn All Rights Reserved. CDA数据分析师(北京国富如荷网络科技有限公司) 版权所有 京ICP备11001960号-9 京公网安备 11010802034615号 经营许可证编号：京B2-20210330
联系电话：13321103290 (微信同号)

OK
客服在线
立即咨询
客服在线
立即咨询