Suzuki-Abe轮廓查找算法边界追踪卡顿问题咨询

问题背景 #

给定初始网格：

0 0 0 0 0 0 
0 1 1 0 0 0
0 1 1 1 0 0
0 1 1 0 1 0
0 0 0 0 0 0

顺时针追踪边界（将边界像素标记为2）后，出现卡顿状态：

0 0 0 0 0 0 
0 2 2 0 0 0
0 1 1 2 0 0
0 1 1 0 2 0
0 0 0 0 0 0

此时最后标记为2的像素邻域无未访问的1像素，但边界未回到起始点，未完成追踪。

解答 #

Suzuki-Abe算法的原生机制 #

Suzuki-Abe算法本身不包含直接应对此类分支边界回溯的机制。该算法核心是基于「当前点-前一个点」的方向约束，按固定顺序（如顺时针）搜索邻域像素追踪边界，默认处理单连通的外边界或内边界。当遇到示例中这种孤立内边界分支时，算法会在分支末端停住，无法自动回溯到主边界继续完成追踪。

基于栈的回溯方案可行性 #

通过保存已访问边界像素的栈来回溯至存在有效1像素的点是可行的，具体实现思路：

• 每次标记边界像素（2）时，将其坐标压入栈中；
• 当遇到邻域无有效1像素的卡顿情况时，从栈中弹出最近的边界点，检查该点邻域是否存在未被标记的1像素；
• 若找到有效像素，则以该点为新的当前点，继续按顺时针规则追踪；若弹出后栈为空，则说明所有边界分支已处理完毕。

这种方法是对Suzuki-Abe算法的扩展，通过栈记录路径来处理多分支边界结构，确保所有连通的边界分支都能被完整追踪。

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