如何在OpenCV中计算凸性缺陷？

Question

如何在OpenCV中计算凸性缺陷？

opencvimage-processingconvex-hullconvexity-defects

3

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

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

- Crazy Cat

输入在文档中有描述--两个坐标列表，一个定义轮廓，另一个定义对应于该轮廓的凸包。该库是开源的，因此您可以阅读实现--如果您不理解算法的某个具体部分，请随时提出具体问题。 - Dan Mašek

1

我正在寻找实现的解释，也就是用文字而不是程序来解释。 - Crazy Cat

好的，希望这解释清楚了。不过，阅读代码并尝试理解它也是非常有价值的——这是学习的绝佳方式，对于程序员来说是一项必不可少的技能。 - Dan Mašek

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dan Mašek · Accepted Answer

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

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

算法的工作方式如下:

如果轮廓或凸包只包含3个或更少的点，则轮廓始终是凸的，不需要进行进一步处理。该算法确保访问轮廓和凸包的方向相同。

N.B .:在进一步说明中，我假设它们的方向相同，并忽略有关将浮点深度表示为整数的详细信息。

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

距离的计算方式如下：

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用于从H_rot找到U_rot，但因为除法比乘法计算量大，所以使用倒数进行优化。在循环遍历C[n]之前就预先计算好，以避免每次迭代重新计算。

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

U_rot = H_rot / |H| = H_rot * scale

然后，C和U_rot之间的点积给出了从缺陷点到凸壳边缘的垂直距离，并使用abs()在任何方向上得到正数大小。

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

在上图所示的场景中，在第一次迭代中，边由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]，可以忽略最后一个轮廓点--那里不可能有缺陷。