在OpenCV中如何计算凸度缺陷? [英] How Convexity Defect is calculated in OpenCV?

问题描述

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

What is the algorithm used in OpenCV function convexityDefects() to calculate the convexity defects of a contour?

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

Please, describe and illustrate the high-level operation of the algorithm, along with its inputs and outputs.

推荐答案

基于文档，输入的是两个坐标列表:

Based on the documentation, the input are two lists of coordinates:

• contour定义原始轮廓(下图为红色)
• convexhull定义与该轮廓相对应的凸包(下图为蓝色)

• contour defining the original contour (red on the image below)
• convexhull defining the convex hull corresponding to that contour (blue on the image below)

算法有效通过以下方式:

如果轮廓或船体包含3个或更少的点，则轮廓始终为凸形，无需进行更多处理.该算法可确保以相同的方向访问轮廓和船体.

If the contour or the hull contain 3 or less points, then the contour is always convex, and no more processing is needed. The algorithm assures that both the contour and the hull are accessed in the same orientation.

N.B.:在进一步的解释中，我认为它们的方向相同，并且忽略了有关浮点深度表示为整数的详细信息.

N.B.: In further explanation I assume they are in the same orientation, and ignore the details regarding representation of the floating point depth as an integer.

然后对于定义凸包的一个边缘的每对相邻船体点(H[i]，H[i+1])，计算轮廓C[n]之间位于H[i]之间的每个点到该边缘的距离和H[i+1](不包括C[n] == H[i+1]).如果距离大于零，则表示存在缺陷.如果存在缺陷，请记录i，i+1，最大距离以及最大位置所在的轮廓点的索引(n).

Then for each pair of adjacent hull points (H[i], H[i+1]), defining one edge of the convex hull, calculate the distance from the edge for each point on the contour C[n] that lies between H[i] and H[i+1] (excluding C[n] == H[i+1]). If the distance is greater than zero, then a defect is present. When a defect is present, record i, i+1, the maximum distance and the index (n) of the contour point where the maximum located.

距离的计算方法如下:

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

就矢量而言，可视化可能更容易:

It may be easier to visualize in terms of vectors:

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

• C: defect vector from H[i] to C[n]
• H: hull edge vector from H[i] to H[i+1]
• H_rot: hull edge vector H rotated 90 degrees
• U_rot: unit vector in direction of H_rot

H 组件是[dx0, dy0]，因此旋转90度将得到[-dy0, dx0].

H components are [dx0, dy0], so rotating 90 degrees gives [-dy0, dx0].

scale用于从 H_rot 中查找 U_rot ，但是由于除法运算的计算量比乘法大，因此将逆运算用作优化.在循环C[n]之前，它也会预先计算，以避免重新计算每次迭代.

scale is used to find U_rot from H_rot, but because divisions are more computationally expensive than multiplications, the inverse is used as an optimization. It's also pre-calculated before the loop over C[n] to avoid recomputing each iteration.

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

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

U_rot = H_rot /| H | = H_rot * scale

然后，在 C 和 U_rot 之间的点积给出了从缺陷点到船体边缘的垂直距离，并且abs()用于在任何方向上都可以得到正值.

Then, a dot product between C and U_rot gives the perpendicular distance from the defect point to the hull edge, and abs() is used to get a positive magnitude in any orientation.

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

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]开始).

In the scenario depicted on the above image, in first iteration, the edge is defined by H[0] and H[1]. The contour points tho examine for this edge are C[0], C[1], and C[2] (since C[3] == H[1]).

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

There are defects at C[1] and C[2]. The defect at C[1] is the deepest, so the algorithm will record (0, 1, 1, 50).

下一个边由H[1]和H[2]以及相应的轮廓点C[3]定义.没有缺陷，因此没有任何记录.

The next edge is defined by H[1] and H[2], and corresponding contour point C[3]. No defect is present, so nothing is recorded.

下一个边由H[2]和H[3]以及相应的轮廓点C[4]定义.没有缺陷，因此没有任何记录.

The next edge is defined by H[2] and H[3], and corresponding contour point C[4]. No defect is present, so nothing is recorded.

由于C[5] == H[3]，最后一个轮廓点可以忽略-那里没有缺陷.

Since C[5] == H[3], the last contour point can be ignored -- there can't be a defect there.

这篇关于在OpenCV中如何计算凸度缺陷?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！