凸包算法

一、技术背景

凸包（Convex Hull）是包围点集的最小凸多边形。在SEM图像分析中，凸包用于：

• 计算目标的密实度（Solidity）
• 分析目标的形状复杂度
• 检测目标的凹陷区域

密实度定义为轮廓面积与凸包面积的比值，反映目标填充凸包的程度，是形状分析的重要指标。

二、数学原理

2.1 凸包定义

凸包是包含点集所有点的最小凸多边形。凸多边形定义为：任意两点连线都在多边形内部或边界上。

数学表示：点集SSS的凸包为：

Conv(S)={∑i=1nλipi∣pi∈S,λi≥0,∑λi=1}Conv(S) = \left\{ \sum_{i=1}^{n} \lambda_i p_i \mid p_i \in S, \lambda_i \geq 0, \sum \lambda_i = 1 \right\}Conv(S)={i=1∑n​λi​pi​∣pi​∈S,λi​≥0,∑λi​=1}

2.2 Graham Scan算法

Graham Scan是经典的凸包算法：

1. 找到y坐标最小的点（起点）
2. 按极角排序所有点
3. 依次处理每个点，维护凸包栈
4. 若新点使栈顶形成右转，弹出栈顶
5. 最终栈中点构成凸包

时间复杂度：O(nlog⁡n)O(n \log n)O(nlogn)

2.3 Jarvis March算法

Jarvis March（礼品包装算法）：

1. 从最左点开始
2. 找到使所有点都在同一侧的点
3. 将该点加入凸包
4. 重复直到回到起点

时间复杂度：O(nh)O(nh)O(nh)，其中hhh为凸包顶点数

2.4 OpenCV实现

OpenCV的ConvexHull函数根据输入点数自动选择算法：

• 点数较少：使用Graham Scan
• 点数较多：可能使用优化的变体

2.5 密实度计算

密实度（Solidity）定义为：

Solidity=AcontourAconvexHullSolidity = \frac{A_{contour}}{A_{convexHull}}Solidity=AconvexHull​Acontour​​

其中：

• AcontourA_{contour}Acontour​：轮廓面积
• AconvexHullA_{convexHull}AconvexHull​：凸包面积

密实度范围[0,1][0, 1][0,1]：

• 接近1：形状接近凸形
• 接近0：形状有大量凹陷

三、代码实现

3.1 MainForm中的凸包计算

文件路径:e:\SEM\Forms\MainForm.cs

// 报告导出中的凸包计算和密实度for(inti=0;i<info.contours.Length;i++){varcontour=info.contours[i];// 面积过滤doubleareaThreshold=200*areaPixelToUm2;if(area<areaThreshold)continue;if(contour.Length<5)continue;RotatedRectellipse=Cv2.FitEllipse(contour);doubleferet=Math.Max(ellipse.Size.Width,ellipse.Size.Height)*umPerPixel;doubleminFeret=Math.Min(ellipse.Size.Width,ellipse.Size.Height)*umPerPixel;doubleangle=ellipse.Angle;doubleaspectRatio=feret/minFeret;doubleroundness=4*Math.PI*area/(perimeter*perimeter);// 凸包计算与密实度doublesolidity=area/(Cv2.ContourArea(Cv2.ConvexHull(contour))*areaPixelToUm2);varrow=newList<string>{// ...aspectRatio.ToString("F2"),roundness.ToString("F2"),solidity.ToString("F2")};}

3.2 凸包点获取

// 获取凸包点集Point[]hull=Cv2.ConvexHull(contour);// 绘制凸包Cv2.Polylines(image,new[]{hull},true,newScalar(255,0,0),2);

3.3 形状因子计算

// 完整的形状因子计算doublearea=Cv2.ContourArea(contour);doubleperimeter=Cv2.ArcLength(contour,true);doubleconvexHullArea=Cv2.ContourArea(Cv2.ConvexHull(contour));// 圆度doublecircularity=4*Math.PI*area/(perimeter*perimeter);// 密实度doublesolidity=area/convexHullArea;// 凸性doubleconvexity=Cv2.ArcLength(Cv2.ConvexHull(contour),true)/perimeter;

四、参数调优

4.1 凸包方向

OpenCV的ConvexHull参数：

// clockwise: 凸包点是否按顺时针排列// returnPoints: 返回点还是索引Point[]hull=Cv2.ConvexHull(contour,clockwise:true,returnPoints:true);

4.2 凸缺陷检测

凸缺陷是轮廓与凸包之间的凹陷区域：

// 检测凸缺陷vardefects=newMat();Cv2.ConvexityDefects(contour,Cv2.ConvexHullIndices(contour),defects);// 解析缺陷信息for(inti=0;i<defects.Rows;i++){intstartIdx=(int)defects.At<Vec4i>(i)[0];intendIdx=(int)defects.At<Vec4i>(i)[1];intfarIdx=(int)defects.At<Vec4i>(i)[2];doubledepth=defects.At<Vec4i>(i)[3]/256.0;// 深度// 绘制凹陷最深点Cv2.Circle(image,contour[farIdx],5,newScalar(0,255,0),-1);}

4.3 形状指标阈值

五、常见问题

Q1: 凸包与轮廓的区别？

Q2: 密实度的应用场景？

密实度在SEM分析中的应用：

1. 孔隙形状分类：区分圆形孔隙和不规则孔隙
2. 颗粒形态分析：评估颗粒的圆整度
3. 缺陷检测：识别有凹陷的目标

Q3: 如何解释密实度值？

Q4: 凸包计算的性能？

时间复杂度：O(nlog⁡n)O(n \log n)O(nlogn)

优化建议：

1. 先对轮廓进行降采样
2. 使用轮廓近似减少点数
3. 并行处理多个轮廓

// 轮廓近似减少点数Matapprox=newMat();Cv2.ApproxPolyDP(contour,approx,0.01*Cv2.ArcLength(contour,true),true);Point[]hull=Cv2.ConvexHull(approx.ToArray());

Q5: 如何计算凸包的缺陷深度？

凸缺陷深度表示凹陷的程度：

vardefects=newMat();Cv2.ConvexityDefects(contour,Cv2.ConvexHullIndices(contour),defects);doublemaxDepth=0;for(inti=0;i<defects.Rows;i++){doubledepth=defects.At<Vec4i>(i)[3]/256.0;maxDepth=Math.Max(maxDepth,depth);}// 深度单位转换（像素 → μm）doublemaxDepth_um=maxDepth*umPerPixel;

Q6: 凸包面积与轮廓面积的关系？

AconvexHull≥AcontourA_{convexHull} \geq A_{contour}AconvexHull​≥Acontour​

密实度计算：

Solidity=AcontourAconvexHull≤1Solidity = \frac{A_{contour}}{A_{convexHull}} \leq 1Solidity=AconvexHull​Acontour​​≤1

当轮廓本身为凸形时，密实度等于1。