首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >连通域算法

连通域算法

作者头像
用户6021899
发布于 2019-12-25 06:42:36
发布于 2019-12-25 06:42:36
5K00
代码可运行
举报
运行总次数:0
代码可运行
  • 四连通域与八连通域 1.四连通区域或四邻域,是指对应像素位置的上、下、左、右 共4个紧邻的位置。 2.八连通区域或八邻域,是指对应像素位置的上、下、左、右,左上、右上、左下、右下 共8个紧邻的位置

如果一个值为1的点的邻域里有一个点的值也为1,则这两个点属于同一个连通域。

如上图,在四连通意义上,值为1的点可分为2个连通域,在八连通域的意义上,只有1个连通域。

下面分享一个我今天刚琢磨出来的四连通域算法(八连通域算法只要在判断条件上稍作修改即可):

首先在第一行按列扫描,新遇到1则标记为一个新的连通域,连通域的label从0开始计数,后续紧邻的1显然都计入该连通域。

然后对之后的每一行:

按列扫描,新遇到1则查询它上一行的对应点是否属于某个连通域X,是则添加进连通域X,不是则创建新的新的连通域Y并加入Y。

如果发现某个值为1的点,其上一行的对应点属连通域X,而它左边有紧邻的1属于连通域Y(Y 不等于X), 则将Y合并到X中,再删除Y。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
# -*- coding: utf-8 -*-
"""
Created on Sat Dec 15 10:15:18 2019
@author: wangsp
"""
import numpy as np
from matplotlib import pyplot as plt

img = np.random.randint(0,2,size=(10,10))
plt.imshow(img)
plt.show()

上图黄色方块的四连通域有哪些呢?

求解思路都体现在函数connectedDomain()中:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
def connectedDomain(img):
    h,w = img.shape
    # 4-connected domain
    domain =dict()
    label = -1 # 用于标记连通域ID
    #i==0 # 第一行
    flag = True #上一个像素是否为0for j in range(w):
        if img[0,j]==1:
            if flag: #上一个元素是0则新建连通域
                label += 1
                domain[label] = set()
            domain[label].add((0,j))
            flag = False
        else:
            flag = True
    for i in range(1,h):#第1行外的其它行
        flag = True
        for j in range(w):
            if img[i,j] == 1:
                for key in domain:
                    if (i-1,j) in domain[key]:#上一行对应元素是否属于某个连通域?
                        domain[key].add((i,j))
                        
                        if not flag:#左边的元素为1
                            if last_label != key:
                                domain[key]=domain[key].union(domain[last_label]) #合并
                                del domain[last_label]
                                
                        last_label = key    
                        break
                else:#不属于上行已有的连通域
                    if flag:
                        label += 1
                        domain[label] = set()
                        domain[label].add((i,j))
                        last_label = label
                    else:
                        domain[last_label].add((i,j))
                
                flag = False
            else:
                flag = True
    return domain
    
domain = connectedDomain(img)
print()
print(sum(img))
print(sum([ len(value) for key, value in domain.items()]))# 元素1的个数
print()
#按面积排序
descended = sorted(domain.items(),key = lambda x: len(x[1]),reverse=True)
for item in descended[:3]: #最大的3块
    z = np.zeros((img.shape))
    for x,y in item[1]:
        z[x,y] =1
    plt.imshow(z)
    #raw2 = raw.copy()
    #aw2[np.where(z!=1)] =[0,0,0]
    #plt.imshow(raw2)
    plt.show()

至此求解出了上图中所有的四连通域,下面仅给出最大的三块:

利用此算法,我们可以自动图像分割。下图中的两片树叶,可以分割为左右两片(代码不再赘述):

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-12-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Python可视化编程机器学习OpenCV 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档