基于等效采样的最大内接矩形提取算法

俞新凯

(广州南方学院电气与计算机工程学院，广东 广州 510970)

0 引言

用料裁切是生产实践中经常遇到的问题，例如在皮革产业原材料裁切、建筑用地规划、板材边角料循环利用等领域，都期望实现裁切利用率最大化。

计算机图像处理技术在众多方向上的发展已经比较成熟。目标区域的轮廓线提取、二值化与卷积处理、任意曲线路径拟合等相关技术为本课题研究提供了基础条件。目前在同类问题的研究方向上，谢新华等人提出了基于遍历目标物体的中心扩散法[1]，袁哲等人提出了基于改进遗传算法[2]、邹哲康等人提出基于机器视觉的边界排序生长法[3]等研究成果，在提取不规则图形的最大内接矩形的技术实现上，都已获得不错的效果，而关键差异主要还是在算法处理的时间效率上。

本文提出一种基于等效采样与均匀扩散、旋转变换等方法相结合的平面任意图形最大内接矩形算法，力求压缩检测点位的采样空间，又确保不遗失真实、有效的目标结果。

1 问题定义

1.1 图形定义

本文所述平面内任意不规则图形属于拓扑理论中的多连通区域，定义如下[4]：

平面内，区域D 的边界中是由一条或几条曲线所围成，单条曲线必须为闭环，即边界不能有“缺口”，所围区域内可以存在“空洞”，如图1所示。

附加约束：

⑴边界线条由单像素点组成，边界内外没有多余的附着点（毛刺），相关技术实现可以参考图像边界分析或路径拟合等方面的文献[5]；

⑵若在初始图像输入时，存在两个或以上分离的区域，则按不同的对象分别计算各自最大内接矩形。

1.2 问题求解

在区域D（下简称D）内，找出面积最大的矩形R（以下简称R），R 不能超出D 的边界，两者边界可以重合。如图1所示，阴影部分为R。

图1 不规则区域内找出最大内接矩形

D 的边界信息为已知条件，即边界点的像素位置坐标是已知的，本文称其为边界点组（下称Boundary点组）。本文所述面积以像素点为单位，对象区域所覆盖的像素点个数为其面积大小。

2 采样处理

2.1 等效采样分析

这里提出一种等效采样的思路。由于本算法在处理矩形扩散时，采用的策略是四条边等速增长，因此在最大矩形R 内部，是存在一部分等效样本点能扩散成R 的，本文将这些点归为OS 点组，即最优解（Optimal Solution）点组。

在图2 中，OS 点组分两种情形，一是对于R 的角位接触D 的内凹处，此时OS 点聚集于角平分线上且不能离角位太远；二是对于R的边位接触D的内凸处，此时OS 点聚集于该处附近。因此，只要能确保采样空间能覆盖到OS 点组中的任意一个，即可最终求得R，从而压缩样本空间的大小。

图2 最优解OS点组

2.2 划定图形内部

划定区域D的内部空间，并求出其整体面积，是本算法设计要先行解决的问题。输入图形的边界要求是闭合的，且内部必须存在空隙。本文以此为前提条件，采用“注水”法求得D的面积。

⑴构建一个用于保存平面像素点状态的二维数组Matrix（下称Matrix 状态矩阵），该二维数组平面刚好覆盖D区域。

⑵约定Matrix的元素为像素点的状态，值与状态的对应关系为：0-未检测、1-注水点、2-边界点、3-边界外；状态默认初值为0。

⑶检索一轮Boundary 点组，将其对应到Matrix状态矩阵的元素状态值均设为2。

⑷扫描Matrix矩阵，按“边界→空白→边界”的顺序记录行进路线上的节点，当找到这种关系时（状态值变化为2→0+→2），判定中间一连串空白为D的内部点。

⑸以D 中任意一个内部点作为中心的“九宫格”边界有8个点。令九宫中心为P0，其余8个点从左上角开始，按顺时针方向顺序编号，分别为：P1、P2、P3、P4、P5、P6、P7、P8。用传递关系定义所有九宫格，则D 的全体内部点可以构成连通图。

⑹ 构建一个用于按顺序存储注水点的队列Queue（先进先出，下称Q队列）。

⑺以第一个P0作为根节点，按“广度优先”遍历连通图的所有节点[6]，每轮迭代都以当前节点为“九宫中心”，顺序访问其周围的8 个点（从P1到P8），并记录其状态值到Matrix 矩阵中。边界内的点记为注水点⑴；边界外的点记为边界外⑶。每标记一个注水点都将其加入队列Q中。

⑻当前轮检测完毕后，便消去了九宫内的未检测(0)点。下轮迭代则从Q 中出队一个注水点，将P0的游标（九宫中心）移交给它，重复迭代过程。

⑼直至Q队列为空时，迭代结束。此时遍历一轮Matrix状态矩阵，累计边界点和注水点的合计数，便得到区域D的面积，记为Sd。

2.3 均匀布点

由于R 是待求解，无法事前就得知该从哪儿出发才能找到R。这里采用均匀分布的方法，以避开连续走点遍历，达到压缩样本空间效果[7]。

对于以怎样的稀疏度来采样，遵从以下原则：

⑴面积较大的区域D，布点倾向于稀疏；反之则倾向于稠密；

⑵避免在边界邻近处采样，因为内接矩形对边界邻近点的覆盖率低。

对于⑴，使用布点间隔span 来确定稀疏度，span的计算公式如下：

Sd为图形区域D的面积。

图3是按该方法得到对应图形的采样点及相关数据。

图3 采样点分布

对比边界点数、内部点数和采样点数，可见检测点的样本空间已大为减小。这里将采样点集合称为Sample点组。

3 矩形计算

大体上按照“扩散→旋转→触停检测→计算面积→比较大小”的步骤，若中间检测环节发生了“触停”，则对应边停止扩散，否则继续扩散；如果四条边均发生触停，则计算所得矩形面积。

“触停”的定义：当某条边在扩散过程中一旦发生了该边的点集（包括两端点）与图形边界Boundary 点组有交集的事实，则该边停止扩散。

3.1 四边扩散

遍历Sample 点组中的全部样本点，分别从每个样本点P出发，通过四边逐步扩散的求得对应的矩形Rp，再通过比较得到最大R。算法步骤大致如下（以水平摆置为例，在旋转变换后，矩形内部各点保持位置对应关系）。

⑴在像素网格中，以样本点作为中心的九宫方阵为初始矩形原型，扩散过程中成为动态增长的Rp。

⑵定义四角点位数组Corners，初值为九宫方阵的四个角位。

⑶定义四条边的是否可继续扩散（该边远离中心向外移动）的布尔型数组Extensible，初值为true。

⑷定义扩散速度v，为每次扩散所增加的步长，即像素个数，先约定为1。

⑸迭代过程：

①按扩散速度v，更新四角点位的坐标。水平摆置时可以在更新后直接检测触停事件；旋转方向时需要先实施旋转变换后再检测“触停”。

②Corners 数组里角点前后相连可得到四条边，通过斜率关系依次遍历每条边上的所有点。以某条边例，设端点p1为(x1,y1)，端点p2为(xz,yz)；Δx=xz-x1，Δy=yz-y1；k=Δy/Δx，为斜率（浮点型），当Δx=0，时k=999999.0；设Ux 为递增或递减的单位量，按Δx＜0、=0、＞0 分别取-1、0、1，同理设Uy；点(xi,yi)为边线上从p1到p2遍历过程的点，i 为循环增量，从1 到|Δx|。则(xi,yi)可以通过以下公式获得：

③在上一步遍历每条边上点时，若发生触停事件，则设置Extensible 数组中该边对应的值为false，即停止扩散，Corners 数组中对应角点坐标的x 或y 值不再更新。

④当Extensible 数组中四个方向的值全为false时，迭代结束。

⑹根据此时Corners 数组角点坐标，计算得到基于该样本点扩散得到的最大面积矩形maxSp，对应于第p个样本点。

比较所有maxSp，从中找出最大者，即为区域D 的最大矩形R，目前为水平方向上的，见图4(a)。

图4 水平方向与旋转方向上得到的最大矩形

图4中，矩形内部的小黑点为最优解样本点，从该点出发找到最大矩形。可见实验结果符合2.1 小节中关于“等效采样”OS点组的定义。

3.2 旋转变换

前面只考察了水平摆置方向上的最大R，为了考察任何方向上摆置的矩形，需要实施旋转变换，逐个角度旋转，分别考察不同方向上的最大值。例如在考察逆时针旋转θ 角度方向时，每次基于水平方向上扩散得到的Corners角点数组，都要先经旋转变换后再检测触停事件。对于角点原坐标(x,y)，可以按以下公式进行旋转[8]，变换到像坐标(x’,y’)。

这里角点坐标是相对于样本点的，即以样本点为原点的位移量，在进行触停检测前，需要将(x’,y’)平移回图形平面的实际坐标去，才能与Boundary 点组的坐标统一。

经过旋转变换后，最终得到区域D在任意方向上的最大矩形R，见图4(b)，可见所得结果优于水平方向的矩形面积。

3.3 扩散提速

扩散速度v 可以引入动态设定机制，档位为1-5。例如当设定v=4 时，即每次增长步长为4，则可能会出现某条边跨越或触碰了Boundary，此时需要进行回滚处理。扩散提速在理想的情形下效果比较明显，例如在初始阶段，四周较为空荡时。此外，具体到某条边而言，“提速失败”只会发生一次，而且回滚再计算的代价也很小。

4 结束语

本文通过分析研究一种基于等效采样原理的最大内接矩形提取算法，并实现了算法设计的程序代码全过程，测试了各种形状复杂的平面图形，对于区域大小在600×600像素以内的普通图形，程序运行耗时基本上可以控制在2s 以内。与暴力破解法找到的结果相对比，基本上可以保持在99%以上的准确率。

图5 展示了针对地图形状的图形输入运行效果。对于输入对象为多区域分离的图形，程序还实现了批量计算处理。

图5 批量计算多区域分离的图形

该算法经应用化设计后可以进一步推广到相应的需求场景中。不足之处在于，通过均匀分布的方法来采样，只是在概率上尽可能覆盖最优解，极端差情况下的计算结果可能会出现比较大的误差。此外，在算法改良方面，还可以运用放缩变换加以优化，这还需要在后续的相关课题研究中，做进一步的分析与设计完善。