俞新凯
(广州南方学院电气与计算机工程学院,广东 广州 510970)
用料裁切是生产实践中经常遇到的问题,例如在皮革产业原材料裁切、建筑用地规划、板材边角料循环利用等领域,都期望实现裁切利用率最大化。
计算机图像处理技术在众多方向上的发展已经比较成熟。目标区域的轮廓线提取、二值化与卷积处理、任意曲线路径拟合等相关技术为本课题研究提供了基础条件。目前在同类问题的研究方向上,谢新华等人提出了基于遍历目标物体的中心扩散法[1],袁哲等人提出了基于改进遗传算法[2]、邹哲康等人提出基于机器视觉的边界排序生长法[3]等研究成果,在提取不规则图形的最大内接矩形的技术实现上,都已获得不错的效果,而关键差异主要还是在算法处理的时间效率上。
本文提出一种基于等效采样与均匀扩散、旋转变换等方法相结合的平面任意图形最大内接矩形算法,力求压缩检测点位的采样空间,又确保不遗失真实、有效的目标结果。
本文所述平面内任意不规则图形属于拓扑理论中的多连通区域,定义如下[4]:
平面内,区域D 的边界中是由一条或几条曲线所围成,单条曲线必须为闭环,即边界不能有“缺口”,所围区域内可以存在“空洞”,如图1所示。
附加约束:
⑴边界线条由单像素点组成,边界内外没有多余的附着点(毛刺),相关技术实现可以参考图像边界分析或路径拟合等方面的文献[5];
⑵若在初始图像输入时,存在两个或以上分离的区域,则按不同的对象分别计算各自最大内接矩形。……