凸包算法应用

凸包算法

一、技术背景

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

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

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

二、数学原理

2.1 凸包定义

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

数学表示：点集 $S$ 的凸包为：

$$Conv(S)=\left\{\sum _{i=1}^n{\lambda }_i{p}_i\mid p_i\in S,{\lambda }_i\ge 0,\sum {\lambda }_i=1\right\}$$

2.2 Graham Scan算法

Graham Scan是经典的凸包算法：

时间复杂度：$O(n\log n)$

2.3 Jarvis March算法

Jarvis March（礼品包装算法）：

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

2.4 OpenCV实现

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

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

2.5 密实度计算

密实度（Solidity）定义为：

$$Solidity=\frac{A_{contour}}{A_{convexHull}}$$

其中：

• $A_{contour}$：轮廓面积
• $A_{convexHull}$：凸包面积

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

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

三、代码实现

3.1 MainForm中的凸包计算

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

// 报告导出中的凸包计算和密实度
for (int i = 0; i < info.contours.Length; i++)
{
var contour = info.contours[i];

// 面积过滤
double areaThreshold = 200 * areaPixelToUm2;
if (area < areaThreshold) continue;

if (contour.Length < 5) continue;

RotatedRect ellipse = Cv2.FitEllipse(contour);

double feret = Math.Max(ellipse.Size.Width, ellipse.Size.Height) * umPerPixel;
double minFeret = Math.Min(ellipse.Size.Width, ellipse.Size.Height) * umPerPixel;
double angle = ellipse.Angle;
double aspectRatio = feret / minFeret;
double roundness = 4 * Math.PI * area / (perimeter * perimeter);

// 凸包计算与密实度
double solidity = area / (Cv2.ContourArea(Cv2.ConvexHull(contour)) * areaPixelToUm2);

var row = new List<string>
{
// …
aspectRatio.ToString("F2"),
roundness.ToString("F2"),
solidity.ToString("F2")
};
}

3.2 凸包点获取

// 获取凸包点集
Point[] hull = Cv2.ConvexHull(contour);

// 绘制凸包
Cv2.Polylines(image, new[] { hull }, true, new Scalar(255, 0, 0), 2);

3.3 形状因子计算

// 完整的形状因子计算
double area = Cv2.ContourArea(contour);
double perimeter = Cv2.ArcLength(contour, true);
double convexHullArea = Cv2.ContourArea(Cv2.ConvexHull(contour));

// 圆度
double circularity = 4 * Math.PI * area / (perimeter * perimeter);

// 密实度
double solidity = area / convexHullArea;

// 凸性
double convexity = Cv2.ArcLength(Cv2.ConvexHull(contour), true) / perimeter;

四、参数调优

4.1 凸包方向

OpenCV的ConvexHull参数：

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

4.2 凸缺陷检测

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

// 检测凸缺陷
var defects = new Mat();
Cv2.ConvexityDefects(contour, Cv2.ConvexHullIndices(contour), defects);

// 解析缺陷信息
for (int i = 0; i < defects.Rows; i++)
{
int startIdx = (int)defects.At<Vec4i>(i)[0];
int endIdx = (int)defects.At<Vec4i>(i)[1];
int farIdx = (int)defects.At<Vec4i>(i)[2];
double depth = defects.At<Vec4i>(i)[3] / 256.0; // 深度

// 绘制凹陷最深点
Cv2.Circle(image, contour[farIdx], 5, new Scalar(0, 255, 0), –1);
}

4.3 形状指标阈值

五、常见问题

Q1: 凸包与轮廓的区别？

Q2: 密实度的应用场景？

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

Q3: 如何解释密实度值？

Q4: 凸包计算的性能？

时间复杂度：$O(n\log n)$

优化建议：

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

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

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

var defects = new Mat();
Cv2.ConvexityDefects(contour, Cv2.ConvexHullIndices(contour), defects);

double maxDepth = 0;
for (int i = 0; i < defects.Rows; i++)
{
double depth = defects.At<Vec4i>(i)[3] / 256.0;
maxDepth = Math.Max(maxDepth, depth);
}

// 深度单位转换（像素 → μm）
double maxDepth_um = maxDepth * umPerPixel;

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

$$A_{convexHull}\ge A_{contour}$$

密实度计算：

$$Solidity=\frac{A_{contour}}{A_{convexHull}}\le 1$$

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