一种沿顺时针方向提取二值图形轮廓的方法

摘要

本发明公开了一种沿顺时针方向提取二值图形轮廓的方法，它通过对二值图片进行腐蚀和膨胀及细节修补操作；剔除非轮廓部分；对残差图片执行宽度优先搜索程序，获得闭合曲线列表；回溯算法输出一个曲线队列；最后进行曲线队列调整，得到沿顺时针方向提取的二值图形轮廓。本发明通过采用上述方法只要给定任意二值图形图片，沿顺时针方向排列的像素点坐标可以直接输入到计算机辅助设计软件中，软件可以根据坐标重构所设计的零件的轮廓外形，提高了零件设计效率；其算法执行过程中几乎无需人工干预，可以使用其他软件或算法生成的二值图形，使得该本发明可以作为连接不同算法和计算机辅助设计软件的桥梁，有助于实现零件设计的自动化。

说明书

技术领域

本发明属于图片处理技术领域，具体涉及一种沿顺时针方向提取二值图形轮廓的方法，它能够将二值图片中的图形轮廓转换成按照顺时针方向排列的坐标序列，可用于连接图形生成软件和有限元仿真软件。

背景技术

计算机辅助设计或者其他计算机图形图像处理任务中，有时需要获取二值图像中构成轮廓的像素点。特别地，在某些计算机辅助设计软件中，如需要通过输入像素点坐标的方公式绘制图形图像时，则要求按照图形图像轮廓的顺时针或者逆时针方向依次输入坐标。基于这些顺序输入的坐标，计算机辅助设计软件就可以构造对应的零件造型，并继续后续的加工操作，比如划分网格等。

目前来看，并没有软件或者算法可以直接将绘制在图片中的二维零件草图直接导入到计算机辅助设计软件中。

发明内容

针对现有技术中存在的上述问题，本发明的目的在于提供一种沿顺时针方向提取二值图形轮廓的方法，它通过提取草图中的轮廓，并生成顺时针方向排列的像素点坐标，便于计算机辅助设计软件通过输入坐标的方公式导入二维零件草图，提高了零件设计的效率。

所述的一种沿顺时针方向提取二值图形轮廓的方法，其特征在于它通过对二值图片进行腐蚀和膨胀及细节修补操作；剔除非轮廓部分；对残差图片执行宽度优先搜索程序，获得闭合曲线列表；回溯算法输出一个曲线队列；最后进行曲线队列调整，得到沿顺时针方向提取的二值图形轮廓。

所述的一种沿顺时针方向提取二值图形轮廓的方法，其特征在于具体包括以下步骤：

步骤1)对二值图像P进行腐蚀和膨胀操作，操作完成后，使用所有Q_i,_j替换所有对应的像素点P_i,_j，然后执行后续操作，腐蚀和膨胀操作根据公式(1)和公式(2)进行：

其中，P_i,_j为二值图片中第i行第j列的像素点的值，P_i+m,j+n为二值图片中i+m行j+n列处的像素值，Q_i,_j是腐蚀或膨胀处理后的二值图片中的第i行第j列的像素点的值，P_i,_j和Q_i,_j取值为0或1，m和n均为整数，取值均为-1，0，1；

步骤2)对二值图像进行细节修补操作按照公式(3)、公式(4)对二值图片进行特殊结构定位，将特殊结构中值为0的像素点设置为1，即完成修补操作；

存在(x，y)满足

P_x+i，y+j＝1(4)

其中x、y为二值图像中的特殊接结构左上角在二值图像中的行号和列号，i、j为模板中的值的行号和列号，并约定图片及模板的左上角像素点的行号和列号均为0；P_x+i,_y+j为二值图片中x+i行y+j列处的像素值，L_i,_j为模板中i行j列的值，S为模板中1的个数；

步骤3)去除二值图像P中的连通部分，仅保留边缘轮廓，二值图像P由步骤1)经过一次腐蚀操作之后得到二值图像Q，由公式(5)计算得到仅保留边缘轮廓的二值图像A；

A_x，y＝P_x，y-Q_x，y(5)

其中，A_x,y为仅保留边缘轮廓的二值图片A中的第i行第y列的像素点；

步骤4)对步骤3)得到的轮廓图像A执行宽度优先搜索程序，获得闭合曲线列表，曲线列表存储有二值图像中的一条闭合曲线的像素点坐标；

5)采用回溯算法输出一个曲线队列；

6)对曲线队列进行调整，使之以顺时针方向排列，所有曲线列表存在于一个轮廓列表中，该轮廓列表即为本方法输出图形的内外侧轮廓。

所述的一种沿顺时针方向提取二值图形轮廓的方法，其特征在于二值图像由任意彩色图片经处理后得到的或由软件算法自动生成或是服从某种随机分布的像素点的集合。

所述的一种沿顺时针方向提取二值图形轮廓的方法，其特征在于闭合曲线为二值图像与一次腐蚀后的二值图像的差，即原二值图像中连通区域的像素值设置为0，保留边沿区域的像素值为1，使得二值图像中所有像素值为1的像素点构成原二值图片中图形的轮廓边界，其中的闭合曲线之间不存在交叉，但闭合曲线合围的区域内能存在其他完整又不相交的闭合曲线。

所述的一种沿顺时针方向提取二值图形轮廓的方法，其特征在步骤2)中采用3乘3的矩形模版按照公式(3)、公式(4)对二值图片进行特殊结构定位。

所述的一种沿顺时针方向提取二值图形轮廓的方法，其特征在于步骤4)中的宽度优先搜索程序过程如下搜索过程：

1)输入一副二值轮廓图片A，自上而下逐行扫描图A，找到第一个像素值为1的像素点，记为root，并搜索root的四领域，找到四领域中第一个像素值为1的像素点，作为宽度优先搜索算法的起点，并记为start，记录其父像素点为root；

2)添加start到已访问集合和待展开队列尾部，随后进入循环搜索过程。在循环搜索过程中，从待展开队列首部提取一个数据实体，记为temp，取temp的四领域之一，记为child，如果child的像素值为1，且不在已访问集合中，则添加chlid到已访问集合和待展开队列尾部，并记录child的父像素点为temp，temp的孩子数加1；如果发现temp等于root，则说明宽度优先搜索过程结束，已经找到一条闭合曲线，需要使用回溯方法构造曲线队列，并调整曲线队列为顺时针方向排列，最后记录曲线队列并开始下一条闭合曲线的搜索程序。

所述的一种沿顺时针方向提取二值图形轮廓的方法，其特征在于步骤5)中的采用回溯算法输出一个曲线队列的具体过程如下：将当前所使用的temp，root以及二值轮廓图片输入到回溯程序中，以temp为起点，将temp的像素点横纵坐标点添加到曲线队列的尾部，迭代地将temp设置为temp的父像素点所指向的数据实体，重复上述步骤，同时判断temp与root是否相等，如果相等，则回到了root像素点，将temp的像素点横纵坐标点添加到曲线队列的尾部，输出曲线列表；如果某一个像素点所在实体temp拥有2个以上的孩子数，则在二值轮廓图片中设置该像素点的值为1，否则为0，如此在二值图片中删除当前已找到的闭合曲线又不会破坏与该曲线存在交叉点的其他闭合曲线，输出一个曲线队列，构成一条闭合曲线。

所述的一种沿顺时针方向提取二值图形轮廓的方法，其特征在于步骤6)中的对曲线队列进行调整的具体过程如下：

输入曲线队列，并在队列中随机选取一个像素点记为temp1，并记temp1的纵坐标为row，判断row是否等于曲线纵坐标中的最大或最小值，如果不是，则找到曲线列表中纵坐标等于row且横坐标最小的像素点，记为temp2，且闭合曲线在这个像素点上的切线不能平行于横轴，如果沿着曲线队列的顺序，闭合曲线是自下而上穿过该像素点temp2，则说明曲线队列是按照顺时针方向排列的，否则为逆时针排列的，需要对曲线队列进行逆序操作。

所述的一种沿顺时针方向提取二值图形轮廓的方法，其特征在于逆序操作的过程如下：先获取曲线队列的长度，得到最后一个字符的序列号，然后根据序列号从后往前依次输出队列。

通过采用上述技术，与现有技术相比，本发明的有益效果如下：

1)本发明通过采用上述方法只要给定任意二值图形图片，即可沿顺时针方向输出图形的内外侧轮廓，沿顺时针方向排列的像素点坐标可以直接输入到计算机辅助设计软件中，软件可以根据坐标重构所设计的零件的轮廓外形，提高了零件设计效率；

2)本发明的算法执行过程中几乎无需人工干预，可以使用其他软件或算法生成的二值图形，使得该本发明可以作为连接不同算法和计算机辅助设计软件的桥梁，有助于实现零件设计的自动化。

附图说明

图1a是本发明的第一细节修补模板；

图1b是本发明的第一细节修补模板；

图1c是本发明的第一细节修补模板；

图2是本发明的总体流程图；

图3是本发明的宽度优先搜索流程图；

图4是本发明的回溯操作流程图；

图5是本发明所涉及的一种二值图像；

图6是本发明所涉及的一种二值图像的轮廓图像。

具体实施公式

以下结合说明书附图及实施例对本发明作进一步的描述，但本发明的保护范围并不仅限于此：

如图1a-6所示，本发明的一种沿顺时针方向提取二值图形轮廓的方法，它通过依次对二值图片进行腐蚀和膨胀及细节修补操作；剔除非轮廓部分；对残差图片执行宽度优先搜索程序，获得闭合曲线列表；回溯算法输出一个曲线队列；最后进行曲线队列调整，具体步骤如下：

步骤1：对二值图片进行腐蚀和膨胀操作，分别按公式(1)和公式(2)进行

其中P_i,j为二值图片中第i行第j列的像素点的值，Q_i,j是腐蚀或膨胀处理后的二值图片中的第i行第j列的像素点的值。当操作完成后，可使用所有Q_i,j替换所有对应的P_i,j，然后执行后续操作。由于是二值图片，所以P_i,j和Q_i,j取值为0或1，m和n为整数，取值为-1，0，1，为了剔除细小的噪声点，本发明实施例中可先执行两次腐蚀操作，然后再执行两次膨胀操作；

步骤2：对二值图片进行细节修补操作

二值图片中存在一些微小的特殊结构，会对后续的曲线提取算法造成干扰，需要对这些特殊结构进行修补，本发明采用图1a、图1b及图1c所示的3种模板按照公式(3)进行特殊结构定位，将特殊结构中值为0的像素点设置为1，如公式(4)即完成修补操作。图1a、图1b及图1c的3种模板即为3种典型的特殊结构：

存在(x，y)满足

P_x+i，y+j＝1(4)

其中x、y为二值图像中特殊结构左上角在二值图像中的行号和列号，i、j为模板中的值的行号和列号，并约定图片及模板的左上角像素点的行号和列号均为0，P_x+i,y+j为二值图片中x+i行y+j列处的像素值，L_i,j为模板中i行j列的值，S为模板中1的个数，图1中的3种模板通过旋转90度及180度可以衍生出其他6种模板，所以公式(3)共需执行9次，处理结果的一种实例结果如图5所示；

步骤3：去除二值图片中的连通部分，仅保留边缘轮廓

二值图像P先执行两次腐蚀操作，然后再执行两次膨胀操作恢复到了原来的大小，再由公式(1)即经过一次腐蚀操作之后可得到二值图像Q，由公式(5)计算得到仅保留边缘轮廓的二值图像A,经过该处理后的结果图像A如图6所示。

A_x，y＝P_x，y-Q_x，y(5)

步骤4：对轮廓图像A执行宽度优先搜索程序，获得闭合曲线列表。

宽度优先搜索程序的流程图见图2，其中root、start、temp、child都表示一种数据实体，其中包含了所代表的像素点的行号和列号，父像素点和孩子数。其中root为轮廓图像A中扫描找到的第一个像素值为1的像素点，start为宽度优先搜索算法的起点，temp为从待展开队列头部取出的数据实体，待展开队列是一种在尾部放入数据实体，从头部取出的数据结构，child为temp的四领域之一，父像素点是其所属数据实体中的一个指向其他数据实体的指针，孩子数指的是一个像素点四邻域中像素点为1的个数。如果两个数据实体所存储的像素点行列号相等，则认为两个数据实体相等。

如图2所示，宽度优先搜索程序的搜索过程为：输入一副二值轮廓图片A，自上而下逐行扫描图A，找到第一个像素值为1的像素点(即图片上显示白色的点)，记为root。搜索root的四领域(即与root相邻的上下左右四个像素点)，找到四领域中第一个像素值为1的像素点，作为宽度优先搜索算法的起点，并记为start，记录其父像素点为root(父像素点是start中的一个指向root的指针)，添加start到已访问集合和待展开队列尾部(待展开队列是先进先出的，即先放入的数据实体先取出，后放入的数据实体后取出)，随后进入循环搜索过程。在循环搜索过程中，每次都是从待展开队列首部提取一个数据实体，记为temp，取temp的四领域之一，记为child，如果child的像素值为1，且不在已访问集合中，则添加chlid到已访问集合和待展开队列尾部，并记录child的父像素点为temp，temp的孩子数加1；如果发现temp等于root，则说明宽度优先搜索过程结束，已经找到一条闭合曲线，需要使用回溯方法构造曲线队列(见图3)，调整曲线队列为顺时针方向排列(见图4)，最后记录曲线队列并开始下一条闭合曲线的搜索程序。

当宽度优先搜索过程结束后，使用回溯方法构造曲线队列，具体过程如下：将当前所使用的temp，root以及二值轮廓图片输入到图3所示的回溯程序中，回溯程序以temp为起点，将temp的像素点横纵坐标点添加到曲线队列的尾部，迭代地将temp设置为temp的父像素点所指向的数据实体，重复上述步骤，同时判断temp与root是否相等，如果相等，则回到了root像素点，将temp的像素点横纵坐标点添加到曲线队列的尾部，输出曲线列表；在回溯过程中，如果某一个像素点所在实体temp拥有2个(不含)以上的孩子数，则在二值轮廓图片中设置该像素点的值为1，否则为0，如此可以在二值图片中删除当前已找到的闭合曲线又不会破坏与该曲线存在交叉点的其他闭合曲线，最后回溯算法输出一个曲线队列，该队列中的像素点可能以顺时针或者逆时针方向排列，且构成一条闭合曲线。

回溯程序获得的曲线队列中的像素点并不一定是顺时针方向排列的，需要使用图4所示的曲线队列调整程序来判断并调整曲线队列，使之以顺时针方向排列。曲线队列调整程序会随机的找到一条平行于横轴的直线，要求该直线能够贯穿整条闭合曲线，形成多个交点，要求这些交点不包含闭合曲线中纵坐标最大或者最小的像素点，选取这些交点中横坐标最小的像素点，要求闭合曲线在这个像素点上的切线不能平行于横轴(这样排除了极值点)，如果沿着曲线队列的顺序，闭合曲线是自下而上穿过该像素点的，则说明曲线队列是按照顺时针方向排列的，否则则是逆时针排列的，需要对曲线队列进行逆序操作。

所有曲线队列的头指针都保存在轮廓队列中。轮廓队列中保存的是曲线队列的头指针，曲线队列中保存的是按照顺时针方向排列的组成闭合曲线的像素点的行列号。本方法以二值图片为输入，以记录图片中轮廓边沿的轮廓队列为输出，所记录的轮廓边沿的像素点是以顺时针方向排列的。