目錄

?

一、相關知識

1、two_pass算法思想

2、并查集算法

二、自定義的two_pass算法

1、將first_pass得到的等價對表轉換成樹狀結構的列表文件，equlist2equTree.py

2、根據equTree來判斷兩個label是否連通的文件union_find.py

3、主函數two_pass.py

4、例子demo.py

四、不足

---

一、相關知識

此部分轉自：https://blog.csdn.net/hemeinvyiqiluoben/article/details/39854315

union find并查集算法：https://www.cnblogs.com/yscl/p/10185293.html

1、two_pass算法思想

在 Two-pass 連通域標記中，第一次標記 (first pass) 時從左向右，從上向下掃描，會將各個有效像素置一個 label 值，判斷規則如下 ( 以 4 鄰域為例 ) ：

1）?????????當該像素的左鄰像素和上鄰像素為無效值時，給該像素置一個新的label值，label ++;

2）?????????當該像素的左鄰像素或者上鄰像素有一個為有效值時，將有效值像素的label賦給該像素的label值；

3）?????????當該像素的左鄰像素和上鄰像素都為有效值時，選取其中較小的label值賦給該像素的label值。

此時，還需維護一個關系表（等價對表），記錄哪些label值屬于同一個連通域。這個關系表通常用union-find數據結構來實現。

在union-find結構中，屬于同一個連通域的label值被存儲到同一個樹形結構中，如圖1所示，{1,2,3,4,8}屬于同一個連通域，{5,6,7}屬于同一個連通域。同時，樹形結構的數據存儲到一個vector或array中，vector的下標為label值，vector的存儲值為該label的父節點label值，當vector的存儲值為0時，說明該label是根節點。這樣，對于任意一個label，我們都可以尋找其根節點，作為所在連通域的label值，即某一連通域所有像素都被置為同一個label值，即根節點label值。對給定的任意一個label，我們可以通過find算法尋找其根節點，如圖2所示。

2、并查集算法

轉自：https://www.cnblogs.com/yscl/p/10185293.html

class UnionFind(object):"""并查集類"""def __init__(self, n):"""長度為n的并查集"""self.uf = [-1 for i in range(n + 1)] # 列表0位置空出self.sets_count = n # 判斷并查集里共有幾個集合, 初始化默認互相獨立# def find(self, p):# """查找p的根結點(祖先)"""# r = p # 初始p# while self.uf[p] > 0:# p = self.uf[p]# while r != p: # 路徑壓縮, 把搜索下來的結點祖先全指向根結點# self.uf[r], r = p, self.uf[r]# return p# def find(self, p):# while self.uf[p] >= 0:# p = self.uf[p]# return pdef find(self, p):"""尾遞歸"""if self.uf[p] < 0:return pself.uf[p] = self.find(self.uf[p])return self.uf[p]def union(self, p, q):"""連通p,q 讓q指向p"""proot = self.find(p)qroot = self.find(q)if proot == qroot:returnelif self.uf[proot] > self.uf[qroot]: # 負數比較, 左邊規模更小self.uf[qroot] += self.uf[proot]self.uf[proot] = qrootelse:self.uf[proot] += self.uf[qroot] # 規模相加self.uf[qroot] = prootself.sets_count -= 1 # 連通后集合總數減一def is_connected(self, p, q):"""判斷pq是否已經連通"""return self.find(p) == self.find(q) # 即判斷兩個結點是否是屬于同一個祖先

二、自定義的two_pass算法

分為三部分

1、將first_pass得到的等價對表轉換成樹狀結構的列表文件，equlist2equTree.py

# 將等價對表轉換成樹狀結構 ''' 例： equList = [(1, 3), (2, 4), (1, 5), (2, 6)][0 1 2 3 4 5 6] equTree = [0 0 0 1 2 1 2] equmergelist = [[1,3,5],[2,4,6]] ''' import numpy as npdef equlist2equtree(equlist):'''等價對列表轉為樹結構，用列表存儲，只是此時列表的下標為label,元素值為父節點索引:param equlist::return:'''# 求label的最大值，決定列表索引的最大值maxlabel = int(np.max(equlist))print('maxlabel:',maxlabel)# 初始化樹maxlabel += 1equTree = np.zeros(maxlabel,dtype=np.int) #print('init equTree:',equTree)# 遍歷等價對表for left,right in equlist:# left就是right的父節點equTree[right] = leftprint('equTree:',equTree)return equTreedef equTree2equmergelist(equtree):'''將樹轉化為合并后的列表:param equtree::return:'''passif __name__ == '__main__':equlist = [(1, 3), (2, 4), (1, 5), (2, 6)]equTree = equlist2equtree(equlist)

2、根據equTree來判斷兩個label是否連通的文件union_find.py

# 并查集 # 說明：列表的形式，其中列表的下標+1是標簽，該位置儲存的值為父節點的位置索引 ''' 例： equList = [(1, 3), (2, 4), (1, 5), (2, 6)][0 1 2 3 4 5 6] equTree = [0 0 0 1 2 1 2] ''' import numpy as npclass unionFind(object):def __init__(self,equTree):# equTree樹狀列表self.equTree = equTreedef findRoot(self,label):# 尋找label的根節點if self.equTree[label] == 0:return labelself.equTree[label] = self.findRoot(self.equTree[label])return self.equTree[label]def is_connect(self,p,q):# 判斷兩個label是否連通return self.findRoot(p) == self.findRoot(q)if __name__ == '__main__':equTree = [0,0,0,1,2,1,2]n = len(equTree) # label的個數unionobj = unionFind(equTree)print(unionobj.findRoot(4))

3、主函數two_pass.py

import numpy as np from equList2equtree import equlist2equtree from union_find import unionFinddef two_pass(img):'''two_pass方法求解連通域:param img: 二值化圖像:return: 返回一個標記好的連通域和連通域的個數'''h,w = img.shapeprint('img:\n',img)print('imgshape:',(h,w))print('------------------------------------------')# first pass'''1）逐行掃描，若該點不是前景點則繼續；2）如果是前景點，觀察左邊和上邊的點是否為前景點，當該像素的左鄰像素和上鄰像素為無效值時，給該像素置一個新的label值，label ++;當該像素的左鄰像素或者上鄰像素有一個為有效值時，將有效值像素的label賦給該像素的label值；當該像素的左鄰像素和上鄰像素都為有效值時，選取其中較小的label值賦給該像素的label值。注意：這里需要將小的label作為大label的父節點，即為（fatherroot，subroot）->(smaller label,big label),稱之為等價對不是則在當前label的基礎上加1作為一個新的連通域；'''equList = [] # 用于存放等價對labelImg = np.zeros(img.shape,dtype=img.dtype) # 存放每個像素點的連通域label，0表示背景label = 0 # 初始label# 第一次遍歷圖像，查找前景點并且得到等價對表for i in range(h):for j in range(w):if i == 0 and j == 0: # 左上角頂點，左邊和上邊均沒有點if img[i,j] == 255: # 若本身為前景則作為連通域的起始點，label+1label += 1labelImg[i,j] = labelelif i == 0 and j != 0: # 第一行，上邊沒有點if img[i,j] == 255 and img[i,j-1] == 255: # 本身為前景點，且左邊鄰點為前景點，將左邊點的label賦值給當前點的labellabelImg[i,j] = labelImg[i,j-1]elif img[i,j] == 255 and img[i,j-1] == 0: # 本身為前景點，但左邊鄰點為背景點，重新賦值一個label，即新的連通域的開始label += 1labelImg[i,j] = labelelse:passelif i != 0 and j == 0:# 第一列，左邊沒有點if img[i, j] == 255 and img[i-1, j] == 255: # 本身為前景點，且上邊鄰點為前景點，將上邊點的label賦值給當前點的labellabelImg[i, j] = labelImg[i-1, j]elif img[i,j] == 255 and img[i-1,j] == 0: # 本身為前景點，但上邊鄰點為背景點，重新賦值一個label，即新的連通域的開始label += 1labelImg[i, j] = labelelse:passelse: # 像素點不在第一行或者第一列# 該像素的左鄰像素和上鄰像素為無效值時，給該像素置一個新的label值if img[i,j] == 255 and img[i,j-1] == 0 and img[i-1,j] == 0:label += 1labelImg[i,j] = label# 該像素的左鄰像素或者上鄰像素有一個為有效值時，將有效值像素的label賦給該像素的label值elif img[i,j] == 255 and img[i,j-1] == 255 and img[i-1,j] == 0:labelImg[i,j] = labelImg[i,j-1]elif img[i,j] == 255 and img[i,j-1] == 0 and img[i-1,j] == 255:labelImg[i,j] = labelImg[i-1,j]# 該像素的左鄰像素和上鄰像素都為有效值時，選取其中較小的label值賦給該像素的label值elif img[i,j] == 255 and img[i,j-1] == 255 and img[i-1,j] == 255:minlabel = int(min(labelImg[i,j-1],labelImg[i-1,j]))labelImg[i,j] = minlabel# 構建等價對，若左邊和上邊的label一樣，則跳過if labelImg[i,j-1] != labelImg[i-1,j]:maxlabel = int(max(labelImg[i,j-1],labelImg[i-1,j]))equTuple = (minlabel,maxlabel) # 將小的label放左邊，作為右邊的父節點equList.append(equTuple)else: # 背景點passprint('equList:\n',equList)print('------------------------------------------')print('labelImg:\n',labelImg)print('------------------------------------------')# second pass'''根據fisrt pass我們得到了等價對表，這里的等價對表還沒有進行合并，因此需要將具有相同連通域的等價對合并在一起'''# 首先將first pass中的等價對表轉換為樹結構equTree = equlist2equtree(equList)# 最大的label值maxlabels = int(np.max(equList))# 開始將圖像上的label值置為其根節點labelfinalLabelImg = labelImg.copy().astype(np.uint8)union = unionFind(equTree)numOfunions = 0 # 用于記錄有多少個連通域,其實就是根節點的最大值for k in range(1,maxlabels+1):rootlabel = union.findRoot(k)if rootlabel > numOfunions:numOfunions = rootlabelprint('%d的根節點是：%d'%(k,rootlabel))print('------------------------------------------')finalLabelImg[np.where(finalLabelImg==k)] = rootlabel # 將圖像上的label值置為其根節點labelprint('finalLabelImg:\n',finalLabelImg)print('------------------------------------------')print('共有%d個連通域'%(numOfunions))return finalLabelImg,numOfunionsif __name__ == '__main__':# 構造一個含有兩個連通域的mini圖像,255前景，0背景img = np.array([[0, 0, 255, 0, 0, 255, 0],[255, 255, 255, 0, 255, 255, 255],[0, 0, 255, 0, 0, 255, 0],[0, 255, 255, 0, 255, 255, 0]], np.uint8)finalLabelImg,numofunions = two_pass(img)print(type(finalLabelImg))

4、例子demo.py

from two_pass import two_pass import cv2img = cv2.imread('two_pass_img.png',0) ret,thre = cv2.threshold(img,100,255,cv2.THRESH_BINARY) cv2.namedWindow('thre',0) cv2.imshow('thre',thre)finalLabelImg = two_pass(thre) cv2.namedWindow('labelImg',0) cv2.imshow('labelImg',finalLabelImg)cv2.waitKey(0)

根據得到的finalLabelImg就可以對不同的連通域進行著色處理，這里沒有寫這部分的代碼

以上例子可參考：https://blog.csdn.net/csuhoward/article/details/78818244

#find father and update def find_fa(x):global count,fa,ccfx = fa[x]if fa[fx] == fx:#if father has no father, no more searchreturn fxelse:#update x's fatherfa[x] = find_fa(fx)return fa[x]def two_pass(img, mask=255, area=100):#init merge and find setglobal count,fa,ccfa = range(img.shape[0]*img.shape[1]) #father nodecc = np.zeros(img.shape[0]*img.shape[1]) #count connected components area of fa[]cc = cc+1dx = [0,0,-1,1,-1,-1,1,1]dy = [-1,1,0,0,-1,1,-1,1]for i in range(img.shape[0]):for j in range(img.shape[1]):if img[i,j] == mask:for dir in range(8):nx = dx[dir] + iny = dy[dir] + jif nx >= 0 and nx < img.shape[0] and ny >= 0 and ny < img.shape[1] and img[nx,ny] == mask:a = i*img.shape[1]+jb = nx*img.shape[1]+nypa = find_fa(a)#shorten chainpb = find_fa(b)##merge fatherif pa<pb:fa[pb]=pacc[pa]+=cc[pb]cc[pb]=0elif pa>pb:fa[pa]=pbcc[pb]+=cc[pa]cc[pa]=0for i in range(img.shape[0]):for j in range(img.shape[1]):if img[i,j] == mask:a = i*img.shape[1]+jfind_fa(a)count = 0colormap = np.zeros((img.shape[0],img.shape[1],3))#color hash tablefor i in range(img.shape[0]):for j in range(img.shape[1]):if img[i,j] == mask:a = i*img.shape[1]+jpa = find_fa(a)if cc[pa] >= 100: # connected components with area >= 100 pixelspa_i = pa / img.shape[1]pa_j = pa % img.shape[1]if np.max(colormap[pa_i,pa_j,:]) == 0:colormap[pa_i,pa_j,:] = np.random.randint(256,size=3)count += 1colormap[i,j,:] = colormap[pa_i,pa_j,:]print countreturn colormap

四、不足

two_pass算法效率不高，是一個傳統的連通域提取算法，后面還出現了基于行程的連通域提取等算法

本人在寫這篇時，對于并查集的原理并不是很理解，望賜教，網上都是寫的代碼，不知道輸入具體是什么

總結

以上是生活随笔為你收集整理的【图像处理】——Python实现two_pass方法来进行连通域的提取的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。