OpenCV Findcontours( ) 函數原理出自于該論文的算法：Topological Structural Analysis of Digitized Binary Images by Border Following
文章傳送門：http://pdf-s3.xuebalib.com:1262/1ftg5E69C3uX.pdf
最近讀了這篇論文并嘗試複現，并填了論文裡面沒提到的一個小坑，整理了一下算法論文和思路，并附上python代碼，如果有錯誤希望各位大佬批評指正(目前隻做了Algorithm1，Algorithm2尋找最外圍輪廓沒寫)
一些重要定義
圖一 邊界關系示例
1，輪廓點(border point)：如果一個像素1在4-或者8-鄰域找到一個像素為0的點，為一個輪廓點，如上圖的B1，B2，B3，B4，其中陰影部分為1，白色部分為0
2，連通區域的環繞(surroundness among connected components)，對于兩個相鄰的連通區域S1和S2，如果對于S1上任意一個點的4個方向，都能達到S2，那麼S2b環繞S1
3，關于外輪廓(outer border)和孔輪廓(hole border)，外輪廓是像素為1連通域内像素為0連通域環繞的輪廓點(如圖一B4)，孔輪廓是像素為0的連通區域被像素為1的連通區域環繞的輪廓點(如圖一 B2)。
4，父輪廓(parent border)，定義了層級關系，假設有像素為1的連通區域S1和像素為0的連通區域S2，并且S2環繞S1
(1)外輪廓S1的父輪廓為環繞S2的值為1的像素，如B3的父輪廓為B2
(2)如果S2是背景，父輪廓為frame 如B4父輪廓為frame
輪廓掃描
開始點(starting point)：文章中掃描的方式為從左到右，從上到下的順序，當找到是邊界起始點的時候，根據下圖判斷輪廓類型。如圖二，滿足(a)，(b)兩種條件的分别為外輪廓和孔輪廓起始點
圖二 開始點
找到起始點後,根據上一個輪廓的編号(LNBD)判斷父輪廓。看table1，如果目前的輪廓與LNBD代表的輪廓是同一個類型的輪廓，則目前輪廓的父輪廓是LNBD代表的輪廓的父輪廓。
最後進行border following找到該輪廓的所有點，參考APPENDIX1：
定義輸入圖檔
，初始化NBD為1，LNBD為1.并且每一行掃描開始，LNBD重設為1
(1)情況一：如果
并且
,則(i，j)是外輪廓的起始點，NBD+1，
.
情況二：如果
并且
, 則(i，j)是孔輪廓的起始點，NBD+1，
.
其他情況跳到(4)
(2)基于輪廓種類決定父輪廓
(3.1)從
開始，以
為中心順時針找到一個非零點為
，如果沒有吧-NBD指派給
，跳到步驟(4)
(3.2)
，
.
(3.3)從
開始，以
為中心逆時針找到一個非零點為
(3.4)根據
，即目前掃描到的pixel，改變
的值，如果
，則
, 如果
(可能為正或者負數)并且
，則
, 其他情況不改變值
(3.5)如果
代表回到了原點，跳到(4)。否則，
，
.
(4)如果
那麼
, 從(i，j+1)開始繼續掃描直到最右下角的像素
整個算法通俗來說就是不斷更新目前點(i3，j3)，然後繞着該點逆時針旋轉找下一點并且不斷更新像素值的過程，下面以文章中給的例子講解
從圖三看，第一次掃描到(a)中的打圈的1，根據(3.4)，改變像素為2，然後逆時針尋找，發現到了左邊邊緣的2根據(3.4)應該是-2。這樣下去結果不對啊!
後來想了一段時間，這裡對像素左邊和右邊同時為0的情況，應該做特殊處理。因為輪廓是逆時針尋找，那麼可以通過尋找的方位判斷該指派NBD還是-NBD，如果是從上往下掃的，則為NBD，如果是從下往上掃描的，則指派-NBD。(具體實作可以參考代碼)
修正後最後結果和文章一緻了！有興趣的朋友可以看下代碼~
結果圖，第一個index為輪廓編号，1為frame邊緣，接着是son子輪廓，parent父輪廓，start_point輪廓開始的index，contour_type輪廓類型是否為孔
結果圖
# -*- coding: utf-8 -*-
"""Created on Wed May 27 15:01:45 [email protected]: 73766"""
import matplotlib.pyplot as plt
import numpy as np
#import cv2
#class Contour:
# def __init__(self,parent,cur_num,contour_type):
# self.parent = parent
# self.contour_num = cur_num
# self.contour_type = contour_type #Hole/Outer
class FindContours:
def __init__(self):
self.grid = np.array([[1,1,1,1,1,1,1,0,0],
[1,0,0,1,0,0,1,0,1],
[1,0,0,1,0,0,1,0,0],
[1,1,1,1,1,1,1,0,0]])
self.reset()
def reset(self):
self.grid = np.pad(self.grid, ((1, 1), (1, 1)), 'constant', constant_values=0)
self.LNBD = 1
self.NBD = 1
self.Disp_with_number = True
self.MAX_BODER_NUMBER = self.grid.shape[0]*self.grid.shape[1]
self.contours_dict = {}
self.contours_dict[1] = self.Contour(-1,"Hole")
def Contour(self,parent,contour_type,start_point = [-1,-1]):
contour = {"parent":parent,
"contour_type":contour_type,
"son":[],
"start_point":start_point}#Hole/Outer
return contour
def load_map_from_array(self,grid):
self.grid = grid.copy().astype("int32")
self.reset()
def trans_number_to_char(self,num):
if self.Disp_with_number:
return str(num)
if num >1:
return chr(63 + num)
if num <0:
return chr(95 - num)
else:
return str(num)
'''display gridd '''
def disp_grid(self):
for i in range(self.grid.shape[0]):
num = '\033[0;37m' + '['
print(num,end = ' ')
for j in range(self.grid.shape[1]):
if self.grid[i][j] == 0:
num = '\033[0;37m' + self.trans_number_to_char(self.grid[i][j])
print(num,end = ' ')
else:
num = '\033[1;31m' + self.trans_number_to_char(self.grid[i][j])
print(num,end = ' ')
num = '\033[0;37m' + ']'
print(num)
print("\033[0;37m")
def find_neighbor(self,center,start,clock_wise = 1):
weight = -1
if clock_wise == 1:
weight = 1
#direction = np.array([[1,0],[0,-1],[0,-1],[-1,0],[-1,0],[0,1],[0,1]])
neighbors = np.array([[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[2,0],[1,0]])
indexs = np.array([[0,1,2],
[7,9,3],
[6,5,4]])
#print(center,start)
start_ind = indexs[start[0] - center[0]+1][start[1] - center[1]+1]
# print(start_ind)
for i in range(1,len(neighbors)+1):
cur_ind = (start_ind + i*weight+8)%8
#print(cur_ind)
x = neighbors[cur_ind][0] + center[0] - 1
y = neighbors[cur_ind][1] + center[1] - 1
# grid[x][y] = a
# a+=1
if self.grid[x][y] != 0:
return [x,y]
return [-1,-1]
def board_follow(self,center_p,start_p,mode):
ij = center_p
ij2 = start_p
ij1 = self.find_neighbor(ij,ij2,1)
x = ij1[0]
y = ij1[1]
if ij1 == [-1,-1]:
self.grid[ij[0]][ij[1]] = -self.NBD
return
ij2 = ij1
ij3 = ij
for k in range(self.MAX_BODER_NUMBER):
#step 3.3
ij4 = self.find_neighbor(ij3,ij2,0)
x = ij3[0]
y = ij3[1]
if ij4[0] - ij2[0] <=0:
weight = -1
else:
weight = 1
if self.grid[x][y] < 0:
self.grid[x][y] = self.grid[x][y]
elif self.grid[x][y-1] == 0 and self.grid[x][y+1] ==0:
self.grid[x][y] = self.NBD*weight
elif self.grid[x][y+1]== 0:
self.grid[x][y] = -self.NBD
elif self.grid[x][y]== 1 and self.grid[x][y+1] != 0:
self.grid[x][y] = self.NBD
else:
self.grid[x][y] = self.grid[x][y]
if ij4 == ij and ij3 ==ij1:
return
ij2 = ij3
ij3 = ij4
def raster_scan(self):
#self.disp_grid()
for i in range(self.grid.shape[0]):
self.LNBD = 1
for j in range(self.grid.shape[1]):
if abs(self.grid[i][j]) > 1:
self.LNBD = abs(self.grid[i][j])
if self.grid[i][j] >= 1:
if self.grid[i][j] == 1 and self.grid[i][j-1] == 0:
self.NBD += 1
self.board_follow([i,j],[i,j-1],1)
border_type = "Outer"
elif self.grid[i][j] > 1 and self.grid[i][j+1] == 0:
border_type = "Hole"
#print(i,j)
self.NBD += 1
self.board_follow([i,j],[i,j+1],1)
#self.contours_dict[self.NBD] = self.Contour(self.LNBD,border_type)
#self.disp_grid()
else:
continue
parent = self.LNBD
if self.contours_dict[self.LNBD]["contour_type"] == border_type:
parent = self.contours_dict[self.LNBD]["parent"]
self.contours_dict[self.NBD] = self.Contour(parent,border_type,[i-1,j-1])
self.contours_dict[parent]["son"].append(self.NBD)
#print("NBD",self.NBD,"LNBD",self.LNBD)
self.grid = self.grid[1:-1,1:-1]
def main():
fc = FindContours()
fc.raster_scan()
fc.disp_grid()
print(fc.contours_dict)
grid1 = np.array([[0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0,0,0,0],
[0,0,1,1,1,1,1,1,1,0,0,0,0],
[0,0,1,0,0,1,0,0,0,1,1,0,0],
[0,0,1,0,0,1,0,0,1,0,0,0,0],
[0,0,1,0,0,1,0,0,1,0,0,0,0],
[0,0,1,1,1,1,1,1,1,0,0,0,0],
[0,0,0,1,0,0,1,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0],])
fc.load_map_from_array(grid1)
fc.raster_scan()
fc.disp_grid()
print(fc.contours_dict)
#
# img1 = cv2.imread("D:\\datas\\luoxuan1.png")
# img = np.mean(np.float32(img1), axis=2)
# img[img<130] = 0
# img[img>0] = 1
# img = 1-img
#
# fc.load_map_from_array(img)
# fc.raster_scan()
# ret =abs(fc.grid)
# ret[ret<2] = 0
# ret[ret>0] = 1
# plt.figure()
# plt.imshow(img,"gray") # 顯示圖檔
# plt.axis('off') # 不顯示坐标軸
# plt.show()
# plt.figure()
# plt.imshow(ret,"gray") # 顯示圖檔
# plt.axis('off') # 不顯示坐标軸
# plt.show()
if __name__ == "__main__":
main()
歡迎大家關注我的專欄，也歡迎大家投稿，我們可以一起研究openCV的原理，分享知識共同進步！OpenCV算法原理了解和numpy實作zhuanlan.zhihu.com