Python实现黑白位图精确方形像素矢量追踪的优化需求

针对你需要的轴对齐矩形边界追踪需求，Moore邻域边界追踪算法是最适配的标准方案，调整后可完美满足要求：仅生成水平/垂直线段、内角90度、外层顺时针/孔洞逆时针排列、起点为左下角、无直线冗余顶点。

核心算法思路 #

1. 坐标系与像素映射 #

先明确坐标规则：

• 输入NumPy数组binary_img中，binary_img[i][j]对应第i行、第j列的像素（行从上到下为y增大方向，列从左到右为x增大方向）
• 每个像素是边长为1的正方形，左下角坐标为(j, i)，右下角(j+1, i)，左上角(j, i+1)，右上角(j+1, i+1)

2. 初始点定位 #

遍历数组找到最左下角的黑像素（优先找x最小的列，同列找y最小的行），该像素的左下角(j, i)即为外层轮廓的起始顶点。

3. 顺时针外层轮廓追踪 #

• 初始方向设为向右（x正方向），按顺时针优先级（右→上→左→下）检查邻域像素：
  1. 若当前方向的下一个像素是未访问的黑像素，沿该方向继续
  2. 否则顺时针转90度，重复检查直到找到可行方向
• 追踪过程中仅保留方向变化的顶点：连续同方向移动时，只记录线段的起点和终点，自动删除直线上的多余点
• 直到回到起始点，完成闭合轮廓

4. 逆时针孔洞轮廓追踪 #

外层轮廓追踪完成后，查找被黑像素包围的白像素区域：

• 找到孔洞区域最左下角的边界点（白像素的相邻黑像素边界）
• 初始方向设为向右，按逆时针优先级（右→下→左→上）进行追踪，同样只保留方向变化的顶点
• 生成的轮廓自动按逆时针排列

简化实现代码 #

import numpy as np

def trace_aligned_contours(binary_img):
    rows, cols = binary_img.shape
    # 标记已访问的黑像素，避免重复追踪
    visited = np.zeros_like(binary_img, dtype=bool)
    contours = []

    # 方向定义：(dx, dy)，对应x/y轴变化
    # 顺时针方向优先级：右、上、左、下
    clockwise_dirs = [(1, 0), (0, -1), (-1, 0), (0, 1)]
    # 逆时针方向优先级：右、下、左、上
    counter_clockwise_dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]

    # 寻找外层轮廓：从最左下角的黑像素开始
    for i in reversed(range(rows)):  # 从下往上遍历（y从小到大）
        for j in range(cols):  # 从左到右遍历（x从小到大）
            if binary_img[i][j] == 1 and not visited[i][j]:
                start = (j, i)
                current_x, current_y = start
                current_dir_idx = 0  # 初始方向向右
                contour = [start]
                # 标记当前像素为已访问
                visited[i][j] = True

                while True:
                    found = False
                    # 按顺时针优先级尝试转向
                    for k in range(4):
                        dir_idx = (current_dir_idx + k) % 4
                        dx, dy = clockwise_dirs[dir_idx]
                        # 计算下一个像素的数组索引
                        next_i = current_y + dy
                        next_j = current_x + dx
                        # 检查是否在数组范围内且是未访问的黑像素
                        if 0 <= next_i < rows and 0 <= next_j < cols:
                            if binary_img[next_i][next_j] == 1 and not visited[next_i][next_j]:
                                current_dir_idx = dir_idx
                                current_x += dx
                                current_y += dy
                                visited[next_i][next_j] = True
                                found = True
                                break
                        # 超出数组范围视为白像素，继续尝试转向
                    if not found:
                        break

                    # 仅在方向变化时添加顶点，删除直线多余点
                    last_point = contour[-1]
                    # 检查当前线段方向是否和上一段一致
                    if len(contour) >= 2:
                        prev_dx = last_point[0] - contour[-2][0]
                        prev_dy = last_point[1] - contour[-2][1]
                        if prev_dx == dx and prev_dy == dy:
                            # 方向相同，更新最后一个顶点为当前点
                            contour[-1] = (current_x, current_y)
                            continue
                    contour.append((current_x, current_y))

                    # 回到起点则闭合轮廓
                    if (current_x, current_y) == start and len(contour) > 1:
                        break

                # 确保轮廓闭合
                if contour[-1] != start:
                    contour.append(start)
                contours.append(contour)

    # 处理孔洞：核心逻辑为查找内部白像素边界，用逆时针方向优先级追踪
    # 可复用上述追踪框架，仅替换方向数组为counter_clockwise_dirs，初始点改为孔洞的左下角边界点

    return contours

关键优化点 #

• 去除直线多余点：通过对比当前方向与上一段方向，仅在转向时保留顶点，避免直线上的冗余坐标
• 起点合规：从最左下角的黑像素开始，确保轮廓起点符合要求
• 方向控制：通过顺时针/逆时针方向优先级，自动生成符合要求的轮廓排列顺序

内容的提问来源于stack exchange，提问作者user695931