3

OpenCV函数convexityDefects()中用于计算轮廓凸度缺陷的算法是什么？

请描述和说明算法的高级操作及其输入和输出。

4

1 回答 1

9

根据文档，输入是两个坐标列表：

  • contour定义原始轮廓（下图中的红色）
  • convexhull定义对应于该轮廓的凸包（下图中的蓝色）

示例轮廓和凸包

该算法以下列方式工作：

如果轮廓或外壳包含 3 个或更少的点，则轮廓始终是凸的，不需要更多处理。该算法确保轮廓和船体都以相同的方向访问。

注意：在进一步的解释中，我假设它们处于相同的方向，并忽略有关将浮点深度表示为整数的细节。

然后对于每一对相邻的包点 ( H[i], )，定义凸包的一个边缘，计算轮廓上位于和(不包括)之间H[i+1]的每个点到边缘的距离。如果距离大于零，则存在缺陷。当存在缺陷时，记录、、最大距离和最大值所在轮廓点的索引 ( )。C[n]H[i]H[i+1]C[n] == H[i+1]ii+1n

距离按以下方式计算：

dx0 = H[i+1].x - H[i].x
dy0 = H[i+1].y - H[i].y

if (dx0 is 0) and (dy0 is 0) then
    scale = 0
else
    scale = 1 / sqrt(dx0 * dx0 + dy0 * dy0)

dx = C[n].x - H[i].x
dy = C[n].y - H[i].y

distance = abs(-dy0 * dx + dx0 * dy) * scale

用向量来可视化可能更容易：

  • C: 缺陷向量从H[i]到C[n]
  • H: 船体边缘向量从H[i]到H[i+1]
  • H_rot: 船体边缘矢量H旋转 90 度
  • U_rot: 方向的单位向量H_rot

H组件是[dx0, dy0]，所以旋转 90 度给出[-dy0, dx0]。

scale用于U_rot从中查找H_rot，但由于除法比乘法计算成本更高，因此将逆用作优化。它还在循环结束之前预先计算，C[n]以避免重新计算每次迭代。

| H| = sqrt(dx0 * dx0 + dy0 * dy0)

U_rot = H_rot/ | H| = H_rot*scale

然后，点积和之间的点积C给出U_rot从缺陷点到船体边缘的垂直距离，并abs()用于在任何方向上获得正幅度。

距离 = abs( U_rot. C) = abs(-dy0 * dx + dx0 * dy) * 比例

在上图描绘的场景中，在第一次迭代中，边缘由H[0]和定义H[1]。检查此边缘的轮廓点是C[0]、C[1]和C[2]（因为C[3] == H[1]）。

第一条边

C[1]和处有缺陷C[2]。处的缺陷C[1]最深，因此算法将记录(0, 1, 1, 50)。

下一条边由H[1]和定义H[2]，以及对应的轮廓点C[3]。不存在缺陷，因此没有记录任何内容。

下一条边由H[2]和定义H[3]，以及对应的轮廓点C[4]。不存在缺陷，因此没有记录任何内容。

由于C[5] == H[3]，最后一个轮廓点可以忽略——那里不可能有缺陷。

于 2018-09-24T17:25:29.487 回答