原像素矩阵M为：
根据原像素矩阵M大小，初始化标记矩阵labelM：
算法流程
1. 首先要确定是标记8邻域连通还是4邻域连通，如果是8邻域连通，就用模板1，如果是4邻域连通，就用模板2。中间像素记为目标像素，模版其余像素记为包围像素。
(1) (2)
2. 若原像素矩阵M中，包围像素均为0，则labelM中目标像素标记号+1；如果不全为0，则labelM中目标像素标记号取labelM中周围像素标记号的最小值；将labelM中周围像素不同标记号的并集记为等价对。
3. 等价对的处理：
假设有如下等价对：
(1,2),(1,6),(3,7),(9-3),(8,1),(8,10),(11,5),(11,8),(11,12),(11,13),(11,14),(15,11)
我们需要得到最终序列是：
最终1-2-5-6-8-10-11-12-13-14-15均标记为1；3-7-9标记为2；4标记为3。
算法的python实现
LableConnectedRagion4( M, labelM, eqLable )用于4邻域连通，获得等价对 LableConnectedRagion8( M, labelM, eqLable )用于8邻域连通，获得等价对 EquivalentLabelPairs( N, labelM, eqLabel )用于处理等价，并重新编号
1 def EquivalentLabelPairs( N, labelM, eqLable): 2 L={} 3 invalidLabel=[] #the invalid label number in equivalent label pairs 4 for i in range(1, N+1): 5 6 if i in invalidLabel: #if i is an invalid label 7 continue 8 9 L[i]=[] 10 for j in range(0, len(eqLable)): 11 if i in eqLable[j]: 12 invalidLabel.append(max(eqLable[j])) 13 L[i].append(max(eqLable[j])) 14 15 for k in L[i]: #deep search 16 for j in range(0, len(eqLable)): 17 if (k in eqLable[j]) & (max(eqLable[j])!=k): 18 invalidLabel.append(max(eqLable[j])) 19 L[i].append(max(eqLable[j])) 20 21 trueLable = 1 22 for k in L: 23 labelM[labelM==k]=trueLable 24 for labelNo in L[k]: 25 labelM[labelM==labelNo]=trueLable 26 trueLable+=1 27 28 29 def LableConnectedRagion8(M, labelM, eqLabel): 30 row = M.shape[0] 31 col = M.shape[1] 32 33 label = 0 34 R = 0 #the first row 35 for C in range(0, col): 36 if M[R, C]==1: 37 if C==0: 38 label+=1 39 labelM[R, C]=label 40 else: 41 if labelM[R, C-1]!=0: 42 labelM[R, C]=labelM[R, C-1] 43 elif labelM[R, C-1]==0: 44 label+=1 45 labelM[R, C]=label 46 47 for R in range(1, row): #the rest rows 48 for C in range(0, col): 49 if M[R, C]==1: 50 if C==0: #the first column 51 if (M[R-1, C]==0) & (M[R-1, C+1]==0) : 52 label+=1 53 labelM[R, C]=label 54 elif M[R-1, C] + M[R-1, C+1]==1: 55 labelM[R, C]=max(labelM[R-1, C],labelM[R-1, C+1]) 56 else: 57 labelM[R, C]=min(labelM[R-1, C], labelM[R-1, C+1]) 58 if labelM[R-1, C] != labelM[R-1, C+1]: 59 if [labelM[R-1, C], labelM[R-1, C+1]] not in eqLabel: 60 eqLabel.append([labelM[R-1, C], labelM[R-1, C+1]]) 61 62 elif C!=col-1: #columns except the first and the last 63 if M[R-1, C-1]+M[R-1, C]+M[R-1,C+1]+M[R,C-1]==0 : 64 label+=1 65 labelM[R, C]=label 66 elif M[R-1, C-1]+M[R-1, C]+M[R-1,C+1]+M[R,C-1]==1: 67 labelM[R, C]=max(labelM[R-1, C-1], labelM[R-1, C], labelM[R-1,C+1], labelM[R,C-1]) 68 else: 69 listLabelM=[ labelM[R-1, C-1], labelM[R-1, C], labelM[R-1,C+1], labelM[R,C-1] ] 70 listLabelM=list(set(listLabelM)) 71 72 if 0 in listLabelM: 73 listLabelM.remove(0) 74 labelM[R, C]=min(listLabelM) 75 if len(listLabelM)!=1: 76 if listLabelM not in eqLabel: 77 eqLabel.append(listLabelM) 78 79 else: #the last column 80 if M[R-1, C-1]+M[R-1, C]+M[R,C-1]==0 : 81 label+=1 82 labelM[R, C]=label 83 elif M[R-1, C-1]+M[R-1, C]+M[R,C-1]==1: 84 labelM[R, C]=max(labelM[R-1, C-1], labelM[R-1, C], labelM[R,C-1]) 85 else: 86 listLabelM=[ labelM[R-1, C-1], labelM[R-1, C], labelM[R,C-1] ] 87 listLabelM=list(set(listLabelM)) 88 89 if 0 in listLabelM: 90 listLabelM.remove(0) 91 labelM[R, C]=min(listLabelM) 92 if len(listLabelM)!=1: 93 if listLabelM not in eqLabel: 94 eqLabel.append(listLabelM) 95 return label 96 97 98 def LableConnectedRagion4(M, labelM, eqLable): 99 row = M.shape[0]100 col = M.shape[1]101 102 labelNo = 0103 R = 0104 for C in range(0, col):105 if M[R, C]==1:106 if C==0:107 labelNo+=1108 labelM[R, C]=labelNo109 else:110 if labelM[R, C-1]!=0:111 labelM[R, C]=labelM[R, C-1]112 elif labelM[R, C-1]==0:113 labelNo+=1114 labelM[R, C]=labelNo115 116 for R in range(1, row):117 for C in range(0, col):118 if M[R, C]==1:119 if C==0:120 if M[R-1, C]==0 :121 labelNo+=1122 labelM[R, C]=labelNo123 else:124 labelM[R, C]=labelM[R-1, C] 125 else: 126 if M[R-1, C]+M[R, C-1]==0:127 labelNo+=1128 labelM[R, C]=labelNo129 elif M[R-1, C]+M[R, C-1]==1:130 labelM[R, C]=max(labelM[R-1, C], labelM[R, C-1])131 else:132 labelM[R, C]=min(labelM[R-1, C], labelM[R, C-1])133 if labelM[R-1, C] != labelM[R, C-1]:134 if [labelM[R-1, C], labelM[R, C-1]] not in eqLable:135 eqLable.append([labelM[R-1, C], labelM[R, C-1]])136 137 return labelNo138 处理结果 对于8邻域联通，未处理等价对时：
所有的等价对为：
处理等价对并重新编号：
参考地址：
http://blog.sina.com.cn/s/blog_ad81d4310102vmll.html
http://fuda641.blog.163.com/blog/static/2075142162013111655644406/