前言

先说说原始需求。事情是这样的，上周末一个项目组突然求援，说是他们打算拿之前手工处理好的一堆图像切片（类似于Jigsaw Puzzle那样的七巧板拼图）来制作小游戏，要求这些七巧板能够完美拼接回原图，同时每一块切片又具有基础的2D物理效果（可以拖动，碰撞，弹飞之类）。我寻思使用Unity自带的Rigid Boly和Polygon2D组件不就解决问题了么？再一细问才发现，他们手头上有大量切割好的“七巧板”png格式文件，但是当年用Photoshop钢笔工具切割时产生的路径点(Path points)早已不知去了哪里=_,= 换言之，他们需要的其实是一套算法，用来对海量的Jigsaw Pieces做边缘检测和轮廓提取。如果结合实际再多做一些要求的话，那么按照原始位置将提取的每一份多边形轮廓拼接起来，必须能够复原回一张严丝合缝的全图（Pieces之间无缝隙）。另一方面，考虑到实时物理效果（如碰撞检测算法）的复杂度，还需要在满足第一项基本需求的前提下，尽可能减少多边形轮廓线段的个数。我问了下期望“交货”的期限，答曰越快越好，2~3天内最佳，于是就答应了下来，心想图像处理领域里边缘检测算法那么多，总有一款现成的可以拿来用。

问题细化

在拿到测试样例后，我确信可以通过对Alpha通道做阈值判断，将彩色图像转化为“二值图”，一张切片的具体模样可参考下图：

图像切片全貌

每张切片都经过了二值化处理，而完整的图像由数十张此类切片拼接而成。综合起来，待处理的问题可以归纳为如下几点：

1. 找到构成边缘轮廓的像素点
2. 按顺时针(CCW)方向串联起所有轮廓像素点，构成"有向像素链"
3. 以某种合适的方式采样"有向像素链"，形成轮廓线段集合
4. 优化线段集合，在不破坏原有形态的前提下，避免过拟合
5. 所有其他后续处理，包括三角形化，Mesh化，添加Unity物理组件等

算法调研

为了不重新造轮子，我大致整理了一下学界常用的“边缘检测”和“轮廓提取”方案，主流的有Canny，Sobel，Laplacian，Roberts等边缘提取算法。它们的共同点是首先基于某型“算子”来提取当前点及其周围一定范围内颜色梯度的变化率，再辅以阈值判断出当前点是否处于轮廓区域。我没法直接使用这些算法，主要问题如下：

1. 检出边缘点的顺序往往和算子游历的顺序一致，很难在检测的同时以顺时针(CCW)方向串联起所有边界点；
2. 视算子不同和大小区别，检出的不一定都是有效边界点，存在“False Positive”这样的过输出问题，需要二次调整；
3. 我这边输入的是纯纯的黑白二值图，用这些高级算法略感杀鸡牛刀了 :)

另一些检索到的备选算法，诸如

1. Douglas-Peucker算法: 主要用于抽象曲线，不适合多边形轮廓提取 (PASS)
2. Zhao-Saalfeld算法：本身是一种简化多边形的算法，虽然对从0到1的构建多边形用处不大，但也许对后续多边形从繁到简有帮助
3. Kanungo算法：是一种基于K-Mean聚类的轮廓提取算法，需要大量迭代，消耗算力太大 (PASS)
4. Zhang-Suen算法：只能提取骨骼 (PASS)

除此之外我还光顾了github上诸多开源插件，只可惜受限于时间和精力，我没有找到特别满意的解决方案。而已有的方案要么效果不尽人意，要么就是内嵌在底层的闭源组件。若想要在短时间（2~3天）内找到资料并读懂和优化出想要的效果，个人感觉还不如自己开发一套算法来得快，至少东西是自己弄的，调优的时候不会磕磕绊绊 ε=(´ο｀*))) 这就是本文的由来。

算法的起点

找到第一个边界点！虽说万事开头难，但这个开头着实简单，具体如下图：

找到第一个点

为了便于理解，以上面图示表述的内容来说，程序可以从图像的最上端开始向下逐行遍历，每一行则自左而右的做检测，目标是找到第一个左右分属外点和内点的组合即可（所谓边界点）。抛开这种近乎Brute-force的遍历不谈，按固定朝向和顺序挨个查找的方式，能带来一些我很喜欢的起始边界点的小特性：既起始边界点必然只会向右或者向下延伸，形成顺时针(CCW)回环的第一个节点（除非图像就这么一个点）。

当然，纯粹暴力查找会带来O(N^2)的开销（其中N为输入图像纹理的像素边长），特别是当输入纹理尺寸达到数千级别时，大量的CPU资源会消耗在遍历海量的像素信息上。如果你不在意这些，可以跳过本段后续内容。要降低暴力遍历的开销其实基本思路不麻烦，我们可以利用Divide && Conque思想做一些优化：为了找到图像上的第一个点，首先我们可以从样本纹理正中间的行(Row)开始确认（对应行标为⌈N/2⌉的行），通过遍历整行判断是否能命中某个边界点，如果不成功，便将样本一分为二，对立对2个子集应用同样的方法进行查找。这个拆分过程将会持续进行，直到产生第一次命中为止。一旦我们定位到了待处理图像的一个行坐标，基于物体必然连续的先验经验，就可以放心得沿着当前命中行号M开始向纹理顶部开始遍历，寻找到目标图像最顶端的第一个交界点为止，算是彻底完成了目标。如果我们的待处理图像所占行数不多（比如不超过Log(N)大小，其中N为纹理高度），那么直接暴力向上逐行查找即可。但如果确信不是这种情况，那就只能再次祭出二分法来定位，这里不再赘述。

按序输出全部边界点

先说一下大体思路，由于我们已经获取到了第一个边界点，并且它就呆在图像的左上角（确信），那么只要一开始向右（如果没有则向下）以某种方式开始检测和输出新发现的边界点，一圈下来回到原点时我们就能获取到按顺时针排序的边界点集合了！

于是问题可以细化为：

找到一种算法，它能够凭借当前的遍历状态，高效得给出下一个边界点位置，并完成迭代和步进。

我最先冒出来的想法大体如下图所示：

抽象出一个九宫格，以最初找到的边界点为中心，将其笼罩的点分为外点和内点两类。通过分析宫格内的状态，找出下一个顺时针边界点，然后步进一次，将九宫格中心对准新找到的边界点，从而开启新一轮迭代。

之所以最终没有按照九宫格的模式将算法设计下去，是因为我感到9个变量的排列组合实在有点多，想要快速的归纳出正确的状态判断逻辑（这是核心）恐怕很难。更重要的是，我发现其实有比九宫格更加简单的方案可循，参考下图：

核心思想仍然是借助局部数据进行状态记录和决策判断，但是放弃了原先基于像素点的规划，改为基于像素边界线的轮廓查找（参考上方左图）！自从意识到这条选项后，我发现原先依赖的九宫格可以被田字格取代，现在需要关注的元素包括田字格内左下（LeftDown），左上（LeftUp），右上（RightUp）和右下（RightDown）共4个像素（Cell）的状态（内点或外点）。田字格中心十字的4个端点，既左侧点（LeftPoint），上方点（UpPoint），右侧点（RightPoint）和下方点（DownPoint）的访问状态。至于田字格的十字的中心，对准的自然是当前正在处理和访问的轮廓点啦！

算法中田字格将如下图一般游走滑动在图像的边缘像素格上，通过检测田字格内像素类型和属性，准确判断下一个迭代时格子移动的朝向。

田字格遍历示意图

废话不多说，我将这套简单的轮廓追踪算法大致可以归纳为以下要点：

• 找第一个点，采取从上向下，自左而右的简单暴力算法寻找
• 找到第一点后，构造一个虚拟的田字格，把田字中心对准点这个起始点的左上角(LeftUp)，做如下观察
  • 田字格内必然形成左下，左上和右上都是外点(图示中黑色方块表示)，右下角为起始点(白色方块表示) 的结构
  • 观察田字区域内物体的轮廓包线，是一条由起始点左侧和上方的边缘线构成的折线
  • 算法的目的是从当前田字格右侧折线的一个端点开始，依序得迭代得探索下一个未知端点，最终回到当前田字格的下放端点，提取完整的轮廓
    • 好比驾驭着贪吃蛇在曼哈顿街区间游历，每一次迭代都会将已知轮廓延伸出去一个街区(像素)边长的单位
• 迭代的大体思路
  1. Step1: 分析当前田字格内像素点分布情况，确定田字格移动方向（上下左右）
  2. Step2: 按目标方向移动田字格，将田字格中心点在移动前后的位置连线，作为轮廓线输出
  3. Step3: 读取当前田字格内像素点状态（内外点），返回Step1
• 分析田字格状态

  • 首先我们需要定义下“轮廓节点”：

    • 轮廓节点指的是在程序运算过程中，任何放置到了田字格十字中心上的点，它就是轮廓节点，其必然同时处于内点与外点的交界处
      • 请区别于前文田字格图示中，处于上下左右共4个方向上的小光黄点，它们不一定是轮廓点！
    • 为便于工程实现，我使用轮廓点A左下方的像素点坐标位置来表示该点A的位置
      • 方便换算位置索引和世界空间坐标

  • 关于轮廓节点的一些循环不变性，它们确保了按照此算法遍历后能获取到完整和正确的轮廓包线

    1. 下一个轮廓节点必然有且只有一个
    2. 下一个轮廓节点与当前轮廓节点必然可直接联通
    3. 下一个轮廓节点一定未被访问过（起始位置的轮廓节点除外）

  • 能够影响下一个轮廓节点方向的因素只有一个：当前田字格中内外像素排列模式

    • 梳理一下田字格中有哪些内外的组合模式（和顺序无关，和组合有关）

      • 按照内点数量划分

      • 同数量下按组合划分

      • 参考示例图

        
        
        1. 只有1个内点（inner cell）时共有4种分布方式
        2. 当有2个内点时，情况有点特殊，共有4+2 = 6种分布方式，其中前4种属于正常情况，后2中可以列为非正常状态，若要处理必须单列逻辑
        3. 3个内点和1内点情况相似，共有4中分布模式
    • 梳理每种组合模式下，如何确认唯一的下一个轮廓点方位
      • 所谓下一个轮廓点方位，就是田字格十字线条4端的小黄点所在位置，是“上下左右”4个方位中的一个
      • 可以通过预制的查询表(LUT)快速定位下一个朝向 -> 本质是穷举法
      • 也可以通过构造内外点和辅助点对象，模拟田字格内部状态来帮助判断
        • 每次遍历十字端点，查找合规的未访问点即可

      • 具体参考图例

        
        

  • 综合上述分析，总结田字格内关键状态信息

    • 轮廓点（已访问，在访问，未访问）
    • 14种不同的田字格内部像素分布状态（略）
    • 额外的，还需要记录轮廓线走向的趋势 （对后续优化有用）
      • 2内点（非对角）-> 连续线段推进
      • 1内点 -> 构成向内转折的趋势(所谓内转是指当前田字格内的3个轮廓点构成凸多边形的一个局部特征)
      • 3内点 -> 构成向外转折的趋势(同理，但是构成的是凹多边形的一个局部特征)

这套算法能够正确且完整的输出图像轮廓包线，如果需求是尽可能精确得保留图像轮廓细节，那么上述算法无疑是最精确的，因为它是逐像素勾勒的，具有像素级别的拟合。但是真实需求往往并不那么极端（要求绝对精确），而是介于精确与高效之间的某个平衡点。说起“高效”，指的自然是算法的运算效率，既我们把图像轮廓数据投入到应用场景中代入运算的效率是否足够高，速度足够快。影响效率的因素很多，一般而言最简单直接且有效的方式是减少总体参与运算的数据量，也就是减少多边形轮廓的边数。减少输出轮廓边数等效于精简输出的轮廓点，是通过在原始输出点集上采样得到的，这就引出了下文的重点，“采样”。

采样方式多种多样，就拿最简单的“均匀采用”举个例子，假设原始图像轮廓点数量为M，我们在空间域中从起始点开始，每隔开数量N个间断点就做一次采样，将采样像素点依序输出，最后形成总数为M/(N+1)的降采样点集。如果需求不讲究的话，均匀采用其实挺好：其一是设计简单，容易实现，其二是可以方便的通过调节数值N的大小，从而在精确与高效之间做切换。当然均匀采样的问题也一堆，最主要在于它无法很好得处理那些兼具了平滑边缘和起伏边缘的图像轮廓，在上述情况下N取小了会降低平滑边本该获得的效率，但N取大了会面临起伏边缘特征消失的尴尬。我们的项目恰巧含有大量兼具平滑和起伏轮廓线的切图，因此不得不另取他法。好在受到图像学中广为人知的“重要性采样”启发，我摸索了一条基于边缘轮廓像素重要特征的采样方案。

对轮廓点集的重要特征采样

• 定义轮廓特征点(点集)的类型

  1. 起始点(Start point)
  • 原始轮廓点集中的第一个点
  • 单独列出来是因为算法需要一个简便的初始状态
  2. 简单连续点(Simple Sequence)
  • 由2个或多个相邻轮廓像素点构成的纯水平或纯垂直排列点集
  • 通俗的说就是十字线上的连续点
  • 描述一组简单连续点等价于描述其首尾点，故而为其重要特征点

  3. 转折点(Turning point)

     
     
  • 不构成简单连续点的相邻3个轮廓点构成转折点
    • 像素宽度只有1的直线或斜线构成的轮廓点除外 -> 需要单独考虑，消耗额外的计算量
  • 内转点
    • 折线朝内的点
    • 对应田字格内只有1个内点的情况，此时田字格十字中心点即为内转点
  • 外转点
    • 折线朝外的点
    • 对应田字格内有3个内点的情况，同样，此时田字格十字中心点即为外转点
  • 通常简单连续点的首尾2点也必然是转折点

  4. 复杂连续点(Complex Sequence)

     
     
  • 复杂连续点是由简单连续点和转折点以一定方式组合成最小重复模式，且相同模式重复1次以上的点的集合
  • 区别于简单连续点只能描述水平和垂直方面的直线，复杂连续点可以描述任何倾角像素点构成的“直线”

• 基于特征轮廓点(点集)的重要性采样

  • 算法简述：在简单轮廓追踪算法的执行过程中建立移动窗口用于存放最近访问的点集，通过分析窗口内像轮廓点分布特性，判断是否构成特征点，最后基于轮廓特征的重要性输出符合要求的采样点
  • 移动窗口
    1. 队列设计，先进先出，固定大小
    2. 每次对靠近队列头部的若干点进行判断，完成判断后Dequeue
    3. 每次访问新点时，将新点推入队尾
  • 符合要求的特征点（重要特征点）
    • 起始点
    • 内转点
    • 简单连续点的2个端点
    • 复杂连续线的2个端点
  • 不符合要求的特征点
    • 外转点
    • 简单/复杂连续点除端点外的点
  • 分步骤判断
    1. 第一步是随边缘识别的过程，完成对起始点+内转点+简单连续点的输出
    2. 第二步在第一步输出基础上，利用变长移动窗口，找出所有复杂连续点集
  • 一些细节
    • 入队列的像素点需要带上其自身属性和类型，这些信息可以从当前田字格区域内读取到
      • 轮廓点类型：起始点，内转，外转
      • 中心点位置
      • 上一个中心点处于什么方向
      • 下一个中心点处于什么方向
    • 合并相同的输出像素点
      • 再内转点和简单连续点，简单连续点和简单连续点相邻的时候，会产生相同点重复输出的情况

举个栗子，上图左侧描绘的是向上简单连续点 + 外转点(略) + 向右简单连续点的组合，只输出2组简单连续点的首尾端点，在红点出会有重复，需提出。而右侧描绘的是向右简单连续点 + 内转点 + 向下简单连续点，此时黄点处有3个重复输出端点，需要做合并处理。

通过上述方法我们可以得到一个精简过的有向轮廓点集合。在一般情况下，它拥有相比原始数据少数倍的数据量，并且能近乎无损的保留原始轮廓的各种细节。美中不足的是我们并没有可以调节精细程度与运行效能(集合内点数)的神奇因子N，这是因为上面的采样算法完全是基于经验和规则的，无法拆分出控制变量。另一方面我们的实际需求可能不需要如此高的精细程度，相反可能更在乎运行效率多一些，具体请参考下图，这是我们项目中若干目标图像切片使用上述采样后重新三角形化的效果图，可以明显感觉到存在大量的过拟合和浪费现象。这是因为很多在微观上确实不连续的点集，在宏观上是连续的。或者换一种方式解释，我们在高分辨率(8K)下进行的边缘提取，remap到低分辨率(2K)的工程场景时，很多细节将被丢失和模糊。因为我们还需要进一步优化输出点集。

我们对采样能做的已经不多了，那么就尝试后处理吧，一个非常直观和简单的想法是：合并相邻且相似的轮廓边，并引入因子N用于控制这种合并的强度以便平衡精度与效率。让我们以这套念头为基础逐渐展开各种细节逻辑。首先是定义评价标准，既什么样的领边进行合并是好的，什么样的领边不能合并。鉴于我们当下的主要任务是拿精度换取效率，那么合并后的精度损失自然是不可避免的，但是基于对宏观表现上的要求，合并后的线条必须满足这些规则：

• 合并后的线段不可将原有的内部像素点切割出去
• 合并后的线段不可破坏图像的宏观轮廓形状

其中第一条并不是必须的，只是因为项目的需要，希望将拆分开的切图重新拼装后不会在接缝处留有间隙，故而我添加了这条要求用来确保图像以膨胀的形态进行合并，不做任何收缩。 至于第二条则是必须的，不然合并后图片走形，将无法满足项目基本需求。

那么我们优先对第二条进行细化，从而得到最为核心的"评价算法"。这里给出2套候选方案供大家参考：

• 评价算法1：基于相邻线段的相交角度

  1. 考量线段AB和BC，设|AB|和|BC|为归一化向量，则可计算它们的点积为 d=Dot(|AB|, |BC|)
  2. 如果AB和BC同向，那么d的数值将趋于1，反之则由趋于0(垂直)过渡到趋于-1(完全反向)
  3. 将调节系数N绑定为阈值，用于评价d的合理范围，当满足范围时执行合并操作

• 评价算法2：基于对外界侵占的面积与轮廓像素点的数量之比

  1. 由于合并必须满足规则1，那么连接相邻的2个合并后的轮廓点A和B，其连续必然完全处于原始切图的外部
  2. 设C点为图像内部且垂直于AB的一点，将计算空间从纹理空间转换到以连线AB为x轴，以AC为y轴的局部坐标系中
  3. 对AB连线所覆盖的轮廓像素点有M个，对它们积分，计算出线段AB与轮廓点合围区域内的面积 S
  4. 将调节系数N绑定为函数入参X，设计函数Func(X, S, M^2)，返回是否可以合并的bool判断值

两套方案殊途同归，第一套使用的是角度作为判断依据，其一维标量的特性会降低其抗干扰的能力，但是贵在实现简单；第二套则使用了面积比例作为判断依据，相比第一套而言具有较强的稳定性，可惜实现起来比较费力，也更费计算资源。我采用了第一套方案，但同时对方案细节做了一定程度修改，内容如下：

如图，左侧是对向量AB和BC做相似性判断，方法就是通过点积求取θ角的度数，然后使用预设阈值判断是否能够通过合并测试。虽然这种方法直观且简单，但是其忽略了判断双方向量的模长，容易在一些长边+短边的组合中合并失败，从而导致效果不佳。我采用了另一种测量角度的方法，如右图所示，对于连续的轮廓点A,B,C来说，我测量AB和AC的夹角，虽然在计算过程中我任然需要将向量AB和AC归一化，但是对于夹角θ而言，其内天生蕴含了对向量AB和BC模长的信息，可以在处理长边+短边时极大的提高正确性。更妙的是，当起始向量AB本身反映了接下来一系列轮廓点所勾勒的宏观走势(朝向)时，我可以通过雪崩式合并，将线段AB,AC,AD,...一些列点在一轮比较中完成合并。综上所述，在采样点的基础上，后处理合并线段的具体算法伪代码如下：

1. 给定起始点A
2. 向正方向（CCW）读取下一个采样点B，形成向量 AB
3. 继续读取下一个采样点C，形成向量 AC
4. 判断点C在AB的左侧还是右侧

• 左侧代表外折（一定范围内可合并）
  • 引用改良版的评价算法(1)对2条线段进行评价，判断是否可以合并
• 右边折代表内折（必然不可合并）
  • 判断为不可合并

5. 若返回“可”合并，则跳转到（3）
6. 若遇到“不可”合并

• 则将最后“可”合并的点作为终点，将起始点和终点合并输出
• 将终点设置为起始点，跳转到(2)

一些效果展示：

1

上图为项目内切图的轮廓采样+三角形化Mesh的结果，可见边缘保存良好，但是存在过拟合问题。

2

在应用了后处理线段合并后，过拟合得到缓解。