基于局部区域搜索的颗粒最小外接圆与最大内切圆优化算法  

Optimized Algorithms for Minimum Circumscribing Circle and Maximum Inscribed Circle Based on Partial Area Search

作　　者：綦华宇 刘伟[1] 尹秀文 石君志 王雅静[1] 秦福元 QI Hua-yu;LIU Wei;YIN Xiu-wen;SHI Jun-zhi;WANG Ya-jing;QIN Fu-yuan(School of Electrical and Electronic Engineering,Shandong University of Technology,Zibo 255049,China;Opptronix Technology Shanghai Ltd.,Shanghai 201109,China)

机构地区：[1]山东理工大学电气与电子工程学院,淄博255049 [2]澳谱特科技(上海)有限公司,上海201109

出　　处：《科学技术与工程》2024年第17期7185-7195,共11页Science Technology and Engineering

基　　金：山东省自然科学基金(ZR2020MF124)。

摘　　要：颗粒轮廓通常像素点数多、形状复杂,使得现有最小外接圆(minimum circumscribing circle,MCC)和最大内切圆(maximum inscribed circle,MIC)算法常因搜索点选择不当而导致算法无法收敛或者陷入局部最优。针对此问题提出了基于局部区域搜索(partial area search,PAS)的MCC与MIC优化算法。算法采用欧几里得距离变换(Euclidean distance transformation,EDT)获得中心点,根据此中心点划分不同的局部搜索区域,然后在局部区域中分别搜索MCC和MIC所需的候选点,最后通过计算分别得到需要的圆。在MCC计算中详细说明了通过两点直接确定MCC的方式,并在局部区域中优先选择最外围的点作为构建初始圆的依据。通过这种方式,部分颗粒无需迭代即可获得MCC,消除了由于搜索点选择不合适而导致的出错问题,同时减少了后续的迭代计算需求。MIC计算首先在局部区域中搜索候选点,然后利用Voronoi图计算MIC,免去了迭代步骤,提高了计算精度和效率。计算出MCC与MIC后,即可计算出颗粒的不规则度。通过对已有数据集的对比分析和实际颗粒的实验数据,证明了优化算法的稳定性和精确性,并具有较高的计算效率,同时适用于低分辨率的颗粒图像。研究结果为颗粒形态的分析提供了一种有效的优化算法。The complexity and high pixel count of particle contours often lead to issues with current minimum circumscribing circle(MCC) and maximum inscribed circle(MIC) algorithms,such as non-convergence or local optima,due to improper selection of search points.A partial area search(PAS)-based optimization algorithm for MCC and MIC was proposed to address these issues.Euclidean distance transformation(EDT) was employed by the algorithm to ascertain a center point,around which distinct local search areas were delineated.Then the candidate points required for MCC and MIC were searched in the local region respectively.Finally,the required circles were obtained by calculation.For MCC calculation,a detailed method of direct determination via two points was presented,prioritizing points on the outermost periphery of the local area for initial circle calculation.This approach allowed for certain particles to achieve MCC without iteration,mitigating errors due to improper search point selection and reducing the need for subsequent iterative computations.MIC calculation was commenced by searching for candidate points within the local area,followed by the computation of MIC using a Voronoi diagram,thereby avoiding iterative steps and enhancing calculation precision and efficiency.After MCC and MIC determination,particle irregularity could be computed.Through comparative analysis of existing datasets and experimental data of actual particles,the stability and accuracy of the optimization algorithm have been proven,and it has high computational efficiency,while being suitable for low resolution particle images.The research results provide an effective optimization algorithm for the analysis of particle morphology.

关 键 词：图像分析 计算几何模型 颗粒不规则度 最小外接圆 最大内切圆 

分 类 号：TP301[自动化与计算机技术—计算机系统结构] TP391[自动化与计算机技术—计算机科学与技术] TN911[电子电信—通信与信息系统]