如果一个值为1的点的邻域里有一个点的值也为1,则这两个点属于同一个连通域。
如上图,在四连通意义上,值为1的点可分为2个连通域,在八连通域的意义上,只有1个连通域。
下面分享一个我今天刚琢磨出来的四连通域算法(八连通域算法只要在判断条件上稍作修改即可):
首先在第一行按列扫描,新遇到1则标记为一个新的连通域,连通域的label从0开始计数,后续紧邻的1显然都计入该连通域。
然后对之后的每一行:
按列扫描,新遇到1则查询它上一行的对应点是否属于某个连通域X,是则添加进连通域X,不是则创建新的新的连通域Y并加入Y。
如果发现某个值为1的点,其上一行的对应点属连通域X,而它左边有紧邻的1属于连通域Y(Y 不等于X), 则将Y合并到X中,再删除Y。
# -*- 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()中:
def connectedDomain(img):
h,w = img.shape
# 4-connected domain
domain =dict()
label = -1 # 用于标记连通域ID
#i==0 # 第一行
flag = True #上一个像素是否为0?
for 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()
至此求解出了上图中所有的四连通域,下面仅给出最大的三块:
利用此算法,我们可以自动图像分割。下图中的两片树叶,可以分割为左右两片(代码不再赘述):
本文分享自 Python可视化编程机器学习OpenCV 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!