ECC算法
实现图像连通区域标记，其核心思想是识别二值化图像中的所有连通区域，并为每个连通区域分配一个唯一的标签。
完整代码及结果
import numpy as np
import matplotlib.image as mpimg
import time
import seg_tools
# 初始化工具
seg_tools.init()
# 定义根查找函数，用于解析等价关系
def root(t, T):
r = t
while T[r] != r: # 查找根节点
r = T[r]
return r
# 定义连通组件标记函数
def label(I):
dim_y, dim_x = np.shape(I) # 获取图像尺寸
# 创建带边框的扩展矩阵，避免边界问题
Ia = np.zeros((dim_y + 2, dim_x + 2), dtype=int)
Ia[1:1 + dim_y, 1:1 + dim_x] = I # 将输入图像嵌入到扩展矩阵中
T = [0] # 等价关系表，初始包含一个值0
cpt = 1 # 初始化标签计数器
# 第一次扫描：分配临时标签并建立等价关系
for y in range(1, 1 + dim_y):
for x in range(1, 1 + dim_x):
if Ia[y, x]: # 当前像素为前景
t = [Ia[y - 1, x - 1], Ia[y - 1, x], Ia[y - 1, x + 1], Ia[y, x - 1]] # 检查邻域
m = 0
for k in range(0, 4): # 遍历邻域标签
if t[k]:
t[k] = root(t[k], T) # 查找根标签
if m == 0:
m = t[k]
else:
m = min(m, t[k]) # 获取最小的根标签
if m == 0: # 邻域中没有标签
Ia[y, x] = cpt # 分配新标签
T.append(cpt)
cpt += 1
else: # 邻域中有标签
Ia[y, x] = m
for k in range(0, 4): # 更新等价关系
if t[k] and t[k] != m:
T[t[k]] = m
print(cpt)
# 第二次扫描：解析等价关系并更新标签
for i in range(0, len(T)):
if T[i] == i:
T[i] = cpt
cpt = cpt + 1
else:
T[i] = T[T[i]]
print(cpt)
for y in range(1, 1 + dim_y):
for x in range(1, 1 + dim_x):
Ia[y, x] = T[Ia[y, x]]
return Ia[1:1 + dim_y, 1:1 + dim_x]
# 主逻辑
if __name__ == "__main__":
# 读取图像
I = mpimg.imread('alphabet.bmp')
# 确保图像为二值化（转换为0和1）
binary_image = np.where(I > 0.5, 1, 0)
# 测量运行时间
t1 = time.perf_counter()
for n in range(5): # 运行5次以评估性能
labeled_image = label(binary_image)
t2 = time.perf_counter()
# 输出运行时间
print('Temps :', (t2 - t1) / 5)
# 使用 seg_tools 可视化原始图像和标记结果
seg_tools.draw_uint8(binary_image)
seg_tools.draw_labels(labeled_image)
# 保存结果到文件
seg_labels.save_labels(labeled_image, "output_labels_modified.txt")
代码详细分析
import numpy as np # 用于数组和矩阵操作
import matplotlib.image as mpimg # 提供图像读取功能
import time # 测量代码运行的时间
import seg_tools # 自定义模块，在文件目录下，包含与分割相关的工具
import seg_labels # 自定义模块，提供标签保存的功能
seg_tools.init() # 调用自定义模块中的初始化函数，来准备可能需要的环境
I = mpimg.imread('alphabet.bmp') # 读取图像
接下来我们定义一个 root 函数，来查找集合中的根节点，确定一个标签的根在等价关系表 T 中的哪个位置
def root(t, T):
t：当前需要查找根的标签值。T：等价关系表，是一个数组（或列表），用于存储标签的父子关系。- T[i] 表示标签 i 的父标签。
- 如果 T[i] = i ，说明 i 是一个根标签。
r = t
令 r 为当前标签 t ，让从 t 开始向上查找。
while T[r] != r:
r = T[r]
- 检查 T[r] 是否等于 r ：
- 如果 T[r] = r ，说明 r 是根标签，退出循环。
- 如果 T[r] \neq r ，说明 r 还有父标签，继续查找，将 r 更新为它的父标签 T[r] 。
- 逐步向上遍历：重复检查 r 的父标签，直到找到根标签。
最后返回最终根标签
return r
完整代码如下:
def root(t,T):
r =T
while T[r]!=r:
r=T[r]
return r
举例
假设等价关系表 T 为以下数组：
T = [0, 1, 2, 3, 3, 3]
- 标签 0, 1, 2 是各自的根： T[0] = 0, T[1] = 1, T[2] = 2 。
- 标签 3 是标签 4 和 5 的根： T[4] = 3, T[5] = 3 。
下面我们查找标签 5 的根，调用 root(5, T)，具体过程如下：
- 初始： r = 5 。
- 检查： T[r]=T[5] = 3 \neq 5 ，更新 r = T[r]=T[5] = 3 。
- 检查： T[3] = 3 （此时 r = 3 ）。
- 返回： r = 3 。
结果：标签 5 的根是 3 。
接下来我们定义一个 label 函数，接收二值化图像 I 作为输入，返回同样大小的标记结果矩阵。
def label(I):
dim_y, dim_x = np.shape(I) # 获取图像尺寸
使用NumPy的np.shape()函数获取图像 I 的大小，高度存储到 dim_y ，宽度存储到 dim_x 。
Ia = np.zeros((dim_y + 2, dim_x + 2), dtype=int)
创建一个二维数组 Ia ，比原图像在宽和高方向各多扩展2个像素，用于给图像外边包一层“边框”（避免后续访问邻域时越界）。
Ia[1:1 + dim_y, 1:1 + dim_x] = I # 将输入图像嵌入到扩展矩阵中
将原图 I 复制到 Ia 的中间部分，使得 Ia 最外圈（第一行、最后一行、第一列、最后一列）都是0（背景），简化了后面“查看邻域”的逻辑。
T = [0] # 等价关系表，初始包含一个值0
定义等价关系表 T 为一个列表，最初仅有0作为占位；索引代表标签值， T[e] 存储标签 e 的父标签。
cpt = 1 # 初始化标签计数器
给 cpt 赋值为1，用于在发现新连通区域时分配新的标签值。
for y in range(1, 1 + dim_y):
外层循环，从1开始遍历到 dim_y （含），对应扩展图像 Ia 的行坐标。
for x in range(1, 1 + dim_x):
内层循环，从1开始遍历到 dim_x （含），对应扩展图像 Ia 的列坐标。
if Ia[y, x]: # 当前像素为前景
判断当前位置 (y, x) 是否为前景像素（即非0），若是前景才需要进行后续操作。
t = [Ia[y - 1, x - 1], Ia[y - 1, x], Ia[y - 1, x + 1], Ia[y, x - 1]] # 检查邻域
从 Ia 中提取当前像素左上、正上、右上和左侧四个邻域像素的标签，存入列表 t 。
- t[0] = 左上像素的标签
- t[1] = 上方像素的标签
- t[2] = 右上像素的标签
- t[3] = 左侧像素的标签
m = 0
初始化 m 为0（表示目前还未找到任何有效的邻域标签）。
for k in range(0, 4): # 遍历邻域标签
遍历这四个邻域标签。
if t[k]:
若 t[k] 不为0（即该邻域存在某个标签）。
t[k] = root(t[k], T) # 查找根标签
调用前面定义的root函数来获取 t[k] 在 T 中的根标签，将结果再次存入 t[k] 。
if m == 0:
如果 m 依旧是0，说明这是遇到的第一个非空标签。
m = t[k]
则将 m 赋值为当前邻域的根标签 t[k] 。
else:
若 m \neq 0 ，说明之前已经遇到过一个邻域标签。
m = min(m, t[k]) # 获取最小的根标签
取 m 和 t[k] 的较小值覆盖 m ，保证 m 始终是已发现根标签中最小的那个。
if m == 0: # 邻域中没有标签
若 m 还是0，表示四个邻域都没有标签，则说明这是一个新出现的连通区域。
Ia[y, x] = cpt # 分配新标签
把当前像素的标签设置为cpt，这是新的连通区域标签。
T.append(cpt)
同时在等价表T的末尾加入此标签cpt（让索引与标签值对应）。
cpt += 1
标签计数器 cpt 自增，为下一个新区域留下可用标签值。
else: # 邻域中有标签
若 m \neq 0 ，说明邻域里已经有标签存在，那么当前像素和它们是连通的。
Ia[y, x] = m
把当前像素的标签设置为 m （最小的根标签），让它们统一到同一个标签。
for k in range(0, 4): # 更新等价关系
再次遍历四个邻域标签，进行标签的合并更新。
if t[k] and t[k] != m:
如果邻域标签 t[k] 不为0，而且与 m 不同，则说明需要把它并到 m 的名下。
T[t[k]] = m
将 T[t[k]] 更新为 m ，意味着 t[k] 的根标签变为 m 。这样做是为了在等价关系表中记录“这些标签其实属于同一区域”。
print(cpt)
打印cpt的值，方便观察第一次扫描后实际分配了多少个临时标签。
for i in range(0, len(T)):
开始第二次扫描前，先遍历等价表 T 。
if T[i] == i:
如果 T[i] 等于 i ，则说明 i 是自己本身的根。
T[i] = cpt
把 T[i] 赋值为 cpt ，为根标签分配一个新的序号（让最终结果中的根标签也彼此不同）。
cpt = cpt + 1
给 cpt 自增1，为下一个根标签留出新的编号。
else:
如果 T[i] 不等于 i ，说明 i 还不是根，它应该直接指向自己的根标签。
T[i] = T[T[i]]
将 T[i] 替换为 T[T[i]] ，相当于“再次向上查找它的父标签”，保证每个标签都指向其根标签所对应的最终编号。
print(cpt)
再打印一次 cpt 的值，以查看第二次扫描（合并标签后的）结果数量。
for y in range(1, 1 + dim_y):
开始对图像做字典序扫描的第二遍（外层循环）。
for x in range(1, 1 + dim_x):
内层循环遍历列。
Ia[y, x] = T[Ia[y, x]]
把当前像素 (y, x) 的标签更新为它在 T 中最终映射的根标签，完成对图像标签的统一。
return Ia[1:1 + dim_y, 1:1 + dim_x]
截取去掉边框后的尺寸，将其返回作为最终标记结果。
if __name__ == "__main__":
判断当前脚本是否作为主程序运行（而非被其他脚本导入）。
I = mpimg.imread('alphabet.bmp')
使用 mpimg的imread函数读取名为“alphabet.bmp”的图像文件，并存储到 I 中。
binary_image = np.where(I > 0.5, 1, 0)
把 I 里的像素二值化，阈值为0.5，大于0.5的像素置1，反之置0，确保输入给label函数的图像只包含0或1。
t1 = time.perf_counter()
记录当前时间 t1 ，用于后续计算算法的平均执行时间。
for n in range(5): # 运行5次以评估性能
运行5次标记过程，以获得相对稳定的耗时评估。
labeled_image = label(binary_image)
调用前面定义的label函数，对二值化图像进行连通区域标记，并将结果赋给labeled_image。
t2 = time.perf_counter()
记录结束时刻 t2 。
print('Temps :', (t2 - t1) / 5)
输出平均耗时，即 (t2 - t1)/5 ，单位通常为秒，表示单次标记过程的大致用时。
seg_tools.draw_uint8(binary_image)
使用自定义模块seg_tools的draw_uint8函数，可视化显示原始二值图像。
seg_tools.draw_labels(labeled_image)
再次使用seg_tools的draw_labels函数，可视化显示连通区域标记结果，不同区域会用不同颜色或不同标签编号呈现。
seg_labels.save_labels(labeled_image, "output_labels_modified.txt")
调用seg_labels模块的save_labels函数，将标签结果labeled_image保存到文件 “output_labels_modified.txt”