最小外接矩阵在植物叶片分割中算法比较研究

最小外接矩阵在植物叶片分割中算法比较研究

罗文军1, 周凌宁2

机电工程学院 成都理工大学 

摘要：在图像分析中，经常会对图像中的几何参数进行比较分析，其中涉及长宽,面积等，通常采用最小外接矩阵的方法进行分割测量，测量的时候一般先提取叶片的最小矩形，由于植物叶片表面粗糙并且不规整，边缘的棱角也呈现的极不规律，这就要求我们在处理的过程中，针对最小外接矩阵的各项参数以及所采用的算法都具有一定的特性，。如今，通常采用目标旋转法，顶点链码法两种。但是之前的算法要求高速的计算机运算。在原有的基础上，提出一种优化算法进行分析在植物叶片上。

关键字：外接矩阵 分割

1. 常用的提取最小矩阵算法

（1）目标旋转算法

本方法主要是通过对目标进行一定方向的旋转，可以进行的是顺时针或者逆时针的操作，每次进行一次旋转，将得到的外接矩阵进行记录然后进行统计对比，同时把取到的的最小面积部分作为最终的测试结果，但是这种操作进行的缺点是进行的次数相对来说操作次数较多，对于计算机的运算要求较高，随着计算的次数增加，容错率相对也会增加不少。

（2）顶点链码法

此方法操作的基础是采用的二值图像，找到图像的中最小矩阵的几个近邻点，进行一定的编码分析处理，根据近邻点边界的得到顶点链码表，然后进行解码处理，得到横纵坐标的最大和最小值进行连接处理，连接的线就是最小外接矩阵的的对角线，同时可以得到最小外接矩阵，这种方法具有一定的优点，但是其分析的过程相对计算机的操作仍然比较困难。

2. 提出对最小外接矩阵进行优化的算法

2.1获取外接轮廓

首先采用Canny边缘检测植物叶片的外接轮廓，其次对外接轮廓进行平面扫描，然后采用Graham算法得到边缘的凸包链，最后通过凸包链得到该植物叶片的最小外接矩形。

凸包链可简单理解为目标图像的外接轮廓，R(可以指图片上某一个点的坐标集，若描述的某一个集合N的外形轮廓，可以称为该N集合的凸包链，凸链可大致的描述目标的轮廓，经常和深度学习进行结合分类处理或者一般外形轮廓计算。凸链来源于Graham算法的平面扫描，过程如下：

2.1.1 排序：把N点的x，y坐标进行从小到大的排列N（。和必然是链上的点，因此可以进行往下操作。

2.1.2   把依次进入一个栈中，然后进行排序，构造下链，刚进栈的,若不能与前面的点形成向左的回路，则对栈顶进行分析处理，重复该过程，直到没有出栈的点，则进栈，对N内所有都进行处理分析，最后得到的点形成凸包链下链，

2.1.3  构造凸上链。类似凸下链，不同点是方向相反。为了减少计算量，采用取余函数进行计算。

完成包链构造以后，找最小外接矩阵。具体算法如下：

（a）在植物叶片的包链中随意截取一条边，视为初始边，同时以为任意多边形一个边的两个端点。同时以为轴中心进行旋转度，作为包链的边对应的夹角（表示凸包链上两条链的交点顺序数，表示交点总个数，根据一定的角度进行旋转，最后得到与轴平行的边状态，旋转角公式如下：

                  第一个公式相当把角在范围内进行旋转，表示取x除以y余数，将和固定阈值比较，若该角小于该阈值，则删除对应点。此目的是为了提高计算效率。

（b）把包链上的点围绕点旋转度。也为链上一点，在绕点旋转后的新的坐标位置点由如下公式确定：

（c）以边作为上下边界，同时找出y所对应的极值点（极大值或极小值），通过该点找到平行于x轴的直线，通过这种方式确定上下边界。同理可找出x左右边界，那么得到的四条直线就可以作为一个矩形，计算矩形面积，然后再依次进行旋转角度。

（d）根据坐标顺序大小，把边作为定位边，若已经被计算，则跳转到下一步，否则，需要再次计算。

（e）当检测出所有外接矩阵之后，找到最小外接矩阵，根据c步骤的计算，倒置植物叶片然后恢复出检测叶片，最小外接矩阵对应长宽就是目标叶片的长和宽。采用旋转法、顶点链码法、优化后的算法叶片最小外接矩形图像的提取，如下所示：

2.2分析对比

为检测优化后的算法对外接矩阵上有何不同在运算时间以及冗余度有何区别，需要进行实验验证，选择茎叶轮廓明显植物叶片数据集进行试验，本叶片数据集中包含200多类的植物叶片茎叶样本，每类叶片包含80张不同叶片茎叶样本，随机选取20种进行试验，分别使用前面所讲的旋转法算法、顶点链玛法算法以及本文优化后的算法进行试验，下图表示几种算法的时间运算。

图4运行时间                    图5面积差

根据上图可以知道，对于最小外接矩阵的算法中，三种算法具有明显的不同在运算时间上，旋转法算法所花费的时间最多，顶点链码法所用时间相对来说较短，同时所花费时间最短的应该是本文采用的优化后的算法。该方法极大的缩短了运算的时间，提升了效率。同时对于所选的十五种不同类型的叶片茎叶的数据集，有良好的稳定性。

由图可得，在提取最小外接矩形算法中，本文优化算法与顶点链码法计算的图形结果很接近，与旋转法面积差较大，优化取余函数的算法既保证精度，还极提高算法运算速度。

结论

通过对比，提取外接矩阵的算法得到了优化在原有基础上，同时提取的时间也得到了进一步的缩短，同时提取的准确度也大幅增加和传统方法对比，优化了植物叶片表面粗糙并且不规整，边缘的棱角不规律所引起的误差问题，深度学习中不同算法的应用对外形轮廓的处理上也截然不同，通过取余的算法也得到了很好的效果，但是对于更加复杂的事物，比如不规整的果实，外表凹凸不平的时候是否能用该算法合理应用还有待考量。后期的工作也将以此展开来分析。

参考文献

[1]. Toth P Nanostructure quantification of turbostratic carbon by HRTEM image analysis: state of the art, biases, sensitivity and best practices - ScienceDirect[J]. Carbon, 2021.

[2]. Matsui T, Nishiyama S , Goto S , et al. Analysis of electric-field domain formations and carrier transport phenomena in GaAs/AlAs asymmetric double-quantum-well superlattices.  2021.

[3].王焕鹏. 基于图像的植物叶片老化过程可视化技术研究[D]. 沈阳农业大学. 2016

[4].王艺蒙. 人脸检测与匹配识别算法研究[D]. 哈尔滨工业大学. 2018

[5].崔志锴. 崔志锴. 基于深度学习和标记相关性的特征优化方法[D]. 南京邮电大学. 2019