霍夫圆变换

简介

Hough circle transform 是一种图像变换，允许从图像中提取圆形对象，即使圆形不完整。该变换对于圆形也是有选择性的，并且通常会忽略拉长的椭圆。该变换有效地搜索具有高度径向对称性的对象，每个对称度在搜索空间中接收一个“投票”。通过搜索 3D 霍夫搜索空间，变换可以测量图像中每个圆形物体的质心和半径。

<figcaption><p>Hough circle transform is specific to circular objects. Left Panel: This panel shown the input data for the Hough circle transform. The data includes (clockwise from top left) a circle (radius 37 pixels), a square (length 37 pixels), an ellipse (minor axis 37 pixels), and a sectored circle (radius 37 pixels).</p>

Right Panel: This panel shows the output of a 24 step Hough circle transform. As you can see, the circle and the sectored circle converge to local maxima, while the square and ellipse do not, show the specificity of the transform for circular objects.

</figcaption></figure>该方法的工作原理是将图像围绕一个圆圈进行变换。每次强度大于零的变换像素落在笛卡尔坐标上时，该坐标都会获得一票。随着图像继续在给定半径的圆上变换，如果图像中的圆具有相同的半径，则投票将在该圆的质心处累积。因此，通过找到变换中的最大值（得票数最高的点），您可以找到图像中圆的质心。霍夫圆变换还可用于通过搜索 3D 变换空间来查找未知半径的圆，其中第三维是要测试的半径范围。

图像处理工作流程

霍夫圆变换根据周长的旋转对称性找到圆。因此，需要将数据转换为这种格式才能使转换生效。

步骤 0：将 XYZ(T) 数据转换为 XY(T) 数据

如果数据是 3D 堆栈，则使用最大、总和或平均强度投影将数据折叠到 2D 空间。该插件可以处理堆栈中的多个帧（时间点），但它只能在 2D 空间中搜索。

第 1 步：找到边

如果圆形物体是实心的而不是空心的，则通过运行以下命令求图像的导数：Process › Find Edges。这将仅保留每个对象的周长。

第 2 步：阈值

该算法不会根据像素的强度对变换进行加权，因为这会导致明亮的非圆形对象获得非常高的分数。因此，任何强度 > 0 的像素每次变换都会获得一票。这意味着您不希望成为变换一部分的任何像素都需要设置为零，最好通过对图像进行阈值处理并通过运行：Image › Adjust › Threshold 创建蒙版来完成。为数据选择正确的阈值后，按“应用”创建带有反转 LUT 的蒙版（0 为白色，255 为黑色）。通过转到Image › Lookup Tables › Grays，可以将 LUT 改回正常灰度。

步骤 3：运行霍夫变换

现在您已准备好运行霍夫变换（有关各种选项的详细信息，请参阅下文）。如果圆的数量未知或因帧而异，则最佳选择是将搜索设置为一个圆，并对输出集执行变换以显示结果表，并在原始图像上标记质心。这将为您提供整个图像中最高的霍夫分数，并允许您确认找到的圆是否正确以及其分数是多少。如果圆不正确，请调整搜索参数以缩小霍夫搜索空间。

如果找到的圆是正确的，则逐渐减小阈值，直到找到图像中的所有圆。这将为您提供阈值上限。继续降低阈值，直到检测到错误的圆，这将为您提供阈值下限。设置上限和下限之间的阈值，然后对完整数据集运行转换。

运行霍夫圆变换插件

该插件在当前活动图像上运行，也可以处理堆栈，但无法处理超堆栈。该插件还可以记录宏实现，并通过多线程在 3D 霍夫空间上进行快速搜索。通过按 GUI 中的“取消”按钮或按“Escape”键，可以随时取消该插件。 该插件有两种独立的算法可用：

完整霍夫变换： 该算法对每一帧执行完整霍夫圆变换。然后，算法首先搜索得分最高的圆圈，然后搜索第二高的圆圈，依此类推。当找到圆时，清除找到的圆周围的霍夫变换空间，以防止重复找到相同的圆。可以调整此参数以允许增加相邻圆之间的重叠程度。

局部霍夫变换： 该算法专为延时系列中的圆的高速跟踪而设计。该算法对第一帧执行完整的霍夫圆变换，以找到每个圆的初始半径和位置。在后续帧中，算法仅在后续帧中每个圆的质心附近执行霍夫变换。如果找到的圆的数量低于指定圆的最小数量，则算法对下一帧执行完整的霍夫圆变换，以尝试找到本地搜索中遗漏的任何圆。

图形用户界面模式

GUI 有两种可用模式：“简单”和“高级”。

简单模式

此模式使用运行转换所需的最少用户输入值。其余参数均默认为最保守的值，以便找到所有符合条件的圆。要检索默认值，请在打开记录器的情况下以简单模式运行 GUI： Plugins › Macros › Record… 这将返回搜索中使用的每个参数的值。

高级模式

此模式旨在进行更精细的搜索，例如更好地使搜索空间适应您的数据，和/或提高霍夫变换的速度。在此模式下，所有可用的搜索参数均可用，并且查看原始霍夫变换输出的选项也可用。

---

搜索参数

霍夫圆插件旨在适应各种分割任务，因此，有七个搜索参数可以调整以调整搜索空间。

最小/最大搜索半径

最小和最大搜索半径是您期望在图像中找到的半径的下限和上限。理想情况下，您希望使霍夫搜索空间尽可能具体，因此请务必将这些值设置为您期望在数据中找到的半径范围。

半径搜索增量

这确定了创建从最小半径到最大半径的 3D 霍夫空间时要使用的半径步长大小。这允许在速度和分辨率之间进行权衡，其中较大的步长将带来速度的线性增加，但也会降低测量半径的精度。

注意：此选项仅在高级模式下可用。在简单模式下，该值默认为 1。

要找到的最大圆数

此选项设置搜索中可以找到的圆圈数的上限。如果图像中得分高于阈值（见下文）的圆圈数量少于指定数量，则算法将仅返回高于阈值的圆圈数量。由于霍夫空间搜索是从得分最高的圆开始，然后是第二高的圆，依此类推，如果得分高于阈值的圆的数量多于“要找到的最大圆数”中设置的限制，则只会返回得分最高的圆。该值的上限为 65535，因为这是可以以 16 位分辨率生成的最大数量的圆 ID。

注意：此选项仅在高级模式下可用。在简单模式下，该值默认为 65535。

霍夫分数阈值

此选项设置圆圈可以算作有效对象的霍夫分数（即投票比率）的最小截止值。该值被描述为以下比率：

\[\text{霍夫分数}=\left ( \frac{\text{投票数}}{\text{变换分辨率}} \right )\]

由于一个圆可以收到的最大票数是变换分辨率（即每个变换都会产生一票），因此一个圆可以收到的最高分数是 1.0。因此，分数阈值越低，搜索对不完整和/或不完美圆的容忍度就越高。

霍夫变换分辨率

此选项设置每个圆形变换的步数。为了减少不必要的计算，如果分辨率设置为任意高（例如默认值 1000），算法将自动查找最大半径可能的最接近的唯一变换数量（即唯一整数 x,y 坐标），并使用该值作为变换系列中的实际分辨率（注意：可以在高级模式中关闭此选项：请参阅“降低变换分辨率”）。将分辨率降低到最大值以下可以大大加快算法速度，但也会降低变换的特异性和灵敏度。 注意：此选项仅在高级模式下可用。在简单模式下，该值默认为 1000。

<figcaption><p>Effect of transform resolution on distinguishing various n-gons. Panel 1 shows a circle and three regular polygons: a 4-gon, 8-gon, and 16-gon. Panel 2 shows a Hough circle transform with four steps. Since all the shapes are radially symmetrical with 90° rotations, they all have an equal peak score at their centroids.</p>

Panel 3 shows a Hough circle transform with eight steps. Since the circle, 8-gon, and 16-gon radially symmetrical with 45° rotations, they all have an equal peak score at their centroids. These shapes have a higher score at their centroids than the 4-gon, because it lacks 45° radial symmetry.

Panel 4 shows a Hough circle transform with sixteen steps. Only the circle and 16-gon are radially symmetrical at this resolution, so their centroids have equally high scores, while the 4-gon and 8-gon have significantly lower scores.

Panel 5 shows a Hough circle transform with 400 steps. The centroid of the circle now has a higher score than all of the other shapes, allowing for the circle to be distinguished even from the 16-gon.

</figcaption></figure>#### 清除邻居半径比

3D 霍夫搜索空间接近局部最大值。因此，当找到一个圆时，需要去除局部最大值周围的空间，以防止再次找到该圆。被清除的霍夫搜索空间的半径被定义为找到的圆的半径的比率，这意味着大圆比小圆清除更多的霍夫搜索空间。

默认情况下，该比率设置为 1，这意味着从整个搜索空间中清除与找到的圆大小和位置相同的圆。这具有消除所找到的质心的一个半径内的所有潜在质心的效果。这有效地从搜索中排除了类似半径的重叠圆。为了允许重叠的圆，可以减小该比率。比率为“0”将导致重复找到相同的圆。这意味着在插件的一次运行中无法找到完美的同心圆，而是需要通过从图像中删除找到的圆并重新运行插件来迭代地找到。

注意：此选项仅在高级模式下可用。在简单模式下，该值默认为 1.0。

<figcaption><p>Adjusting the clear radius ratio to find overlapping circles.</p>

The left panel shows the input data with a single circle on top and a pair of overlapping circles below. The next panel shows the resulting Hough circle transform (24 steps).

The top right pair of panels show the effect of a clear ratio of 1.0, where when the first overlapping circle is found, the centroid of the neighboring circle is removed, resulting in only two high scoring circles being found.

The bottom right pair of panels show the effect of a clear ratio of 0.2, where when the first overlapping circle is found, only its centroid is removed and the neighboring centroid is preserved for the neighboring circle to also be found, resulting in all three circles being found.

</figcaption></figure>#### 降低变换分辨率

由于所有图像都是笛卡尔坐标系中的像素，因此变换只能是离散整数坐标（即 x=5，y=10）。因此，在无限精细的分辨率下，当变换的下一步四舍五入到最接近的整数坐标时，这些坐标可能与前一个变换步骤相同。这意味着当执行转换时，它将对这两个步骤执行相同的转换。

为了加速霍夫变换，您可以在执行变换之前找到并删除所有冗余变换步骤，仅保留一组唯一的变换步骤。该插件通过删除最大搜索半径的所有冗余变换步骤来执行此检查，然后将其设置为后续半径的新分辨率。这意味着较小的半径将执行冗余变换，但这对于确保每个半径获得相同数量的投票轮数至关重要（否则大圆圈总是比小圆圈得分更高）。

在加速算法的同时，需要权衡的是变换步骤对于最大半径是各向异性分布的（所有后续半径将是各向同性的）。取消选中此框将导致变换执行所有指定的变换步骤，这对于高分辨率值来说可能需要大量计算。

注意：此选项仅在高级模式下可用。在简单模式下，默认选择此选项。

---

本地搜索参数

当使用霍夫变换随时间跟踪圆形对象时（例如通过瞳孔扩张或眼睛跟踪），计算完整的霍夫空间然后搜索完整的霍夫空间的效率非常低，因为您知道当前帧中的对象将与前一帧中的相应对象大致处于相同的位置并且具有大致相同的半径。 局部搜索算法利用此“先验”信息来大大减少后续帧中的变换和搜索空间的体积，从而使处理速度提高多个数量级。

局部搜索算法由三个子算法组成，具体取决于前一帧的状态：

**完整 - **对于第一帧，执行“完整”霍夫圆变换（标准算法）以查找帧中每个圆形对象的初始半径和位置（最多为设置的最大圆数）。如果给定帧中找到的圆形对象的数量为 0，也将使用完整的霍夫变换。

**局部 - **如果前一帧中圆形物体的数量大于或等于设置的最小物体数量，则算法将使用排他性局部搜索来查找下一帧中相同的圆形物体。局部算法仅对上一帧中找到的对象的附近霍夫空间执行变换，然后仅在该局部空间中搜索当前帧中的相同对象。

**部分局部 - **如果前一帧中圆形物体的数量小于设置的最小物体数量但大于0，则算法将使用混合搜索。将执行完整的霍夫变换，以便现在可以找到任何丢失的圆。然而，为了加快搜索速度，算法将首先在霍夫空间内局部搜索在前一帧中找到的相同圆形物体，然后在整个霍夫空间中搜索任何剩余的圆形物体。

<figcaption><p>Local versus full Hough transform.</p>

The left panel shows the input data with a single circle in the center of the image with a radius of 50 pixels. The center panel shows orthogonal projections of the full 3D Hough space. The radius search range was 10-110 pixels. The left panel shows a local Hough transform of the same circle, with a search area of 20x20 pixels, and a radius search range of +/- 10 pixels of the original circle radius. NOTE: In Hough space, the Z-dimension is the radius of the transform.

</figcaption></figure>#### 要找到的最小圆圈数

该值表示霍夫圆变换在切换到使用部分或完整搜索算法查找丢失的圆之前将搜索的最小圆数。例如，如果变换在第一帧中找到 20 个圆，并且最小值设置为 10，则算法将允许在整个霍夫空间中搜索丢失的圆之前丢失 10 个原始圆的轨迹。

本地半径搜索带宽（+/- 先前半径）

该值允许您设置局部霍夫搜索空间的 Z 轴。例如，如果在您的数据中，您不希望任何圆形对象的半径在单个帧中变化超过 10 个像素，那么您可以通过输入 10 来缩小本地搜索范围。然后，本地搜索将搜索与上一帧中半径相同 +/- 10 像素的圆形对象。

注意：此选项仅在高级模式下可用。在简易模式下，该值默认为总半径搜索范围（最大搜索半径 - 最小搜索半径）。

下一个质心位置的局部搜索半径

该值允许您设置 x,y 轴搜索半径。例如，如果在您的数据中，您预计单个帧中任何圆形对象的位置变化不会超过 10 个像素，则您可以输入 10 来缩小局部搜索范围。然后，局部搜索将搜索与前一帧中位置相同 +/- 10 个像素的圆形对象。

注意：此选项仅在高级模式下可用。在简单模式下，该值默认为最小搜索半径。

---

输出选项：

该插件包含多个输出选项，用于可视化转换以及导出分析结果。

原始霍夫变换系列

此选项将输出一个堆栈，其中每个切片都是指定半径的变换。每个切片还在标题中标有半径（以像素为单位）和分辨率。如果输入的数据是多帧堆栈，则转换将返回一个超堆栈，其中 Z 维度是测试的每个半径，T 维度是电影中的每个帧。

为了节省内存，霍夫分数设置为 8 位尺度，变换搜索空间中的最高分数值为 255（即无饱和）。如果输入的数据是电影，则每个帧将独立重新缩放。然而，虽然分数被下采样到 8 位尺度，但霍夫变换会为您的数据集添加额外的维度，因此，如果您的电影和搜索空间很大，请确保您有足够的 RAM。

注意：此选项仅在高级模式下可用。该值默认为 1.0。

原始图像上标记的圆质心

此选项将在图像中找到的每个质心上绘制十字线图案，覆盖在原始图像的蒙版上。此输出对于优化霍夫搜索参数特别有用。图像的标题包含在图像中找到的圆圈数。如果输入的数据不是掩码，则会计算阈值为1的掩码。

如果输入的数据是多帧堆栈，则转换将返回一个堆栈，其中 Z 维度是电影中的每个帧，标题将显示每个帧中找到的圆圈数。

质心处的圆半径图（像素强度 = 圆半径）

此选项返回一个图像，其中每个圆的质心由单个像素标记，其强度等于圆的半径，图像的标题显示找到的圆的数量。为了节省内存，图像被格式化为 16 位，这意味着它可以显示的最大半径为 65535 像素。如果您需要导出更大的半径，请将结果导出到结果表（见下文）。

如果输入的数据是多帧堆栈，则转换将返回一个堆栈，其中 Z 维度是电影中的每个帧，标题将显示每个帧中找到的圆圈数。

质心处的圆得分图（像素强度 = 圆得分）

此输出与半径输出相同（见上文），但像素强度是霍夫分数。为了节省内存，图像被格式化为16位，这意味着它可以显示的最高分数是65535。

将测量结果导出到结果表

这会将转换结果输出到结果表中。导出的测量结果为：1) 每个质心的 X 和 Y 坐标，2) 每个圆的半径（以像素为单位），3) 每个圆的霍夫分数，4) 在该帧中找到的圆的数量，5) 变换使用的实际分辨率（这实际上也是可能的最高霍夫分数），以及 6) 找到圆的帧。

如果在帧中没有找到圆圈，则该帧将从结果表中排除。

安装插件

霍夫圆变换插件是 UCB Vision Sciences 库的一部分。要安装它，您只需 add UCB Vision Sciences 更新站点：

1) 从 Fiji 菜单中选择 Help › Update… 以启动更新程序。

2) 单击管理更新站点。这将弹出一个对话框，您可以在其中激活其他更新站点。

3) 激活UCB Vision Sciences更新站点并关闭对话框。现在您应该会看到其他可供下载的 jar 文件。

4) 单击应用更改并重新启动斐济。

您现在应该在子菜单Plugins › UCB Vision Sciences › Hough Circle Transform下找到该插件。

注意：霍夫圆变换只是 UCB Vision Sciences 套件中包含的插件之一。通过遵循这些安装步骤，您将安装套件中的其余插件。

致谢

该插件是由Hemerson Pistori and Eduardo Rocha Costa实现的霍夫圆变换的修改版本。该变换算法基于 Mark Schulze 的原始实现。

该插件是作为加州大学伯克利分校视觉科学核心资助 NIH P30EY003176 的一部分而开发的。

错误报告

2018 年 4 月 5 日 - 修复了忽略净半径比的错误。

2018 年 9 月 21 日 - 修复了重复调用插件会导致内存泄漏的错误。

许可证

该程序是免费软件；您可以根据自由软件基金会 (http://www.gnu.org/licenses/gpl.txt) 发布的 GNU 通用公共许可证 的条款重新分发和/或修改它。

分发此程序的目的是希望它有用，但不提供任何保证；甚至没有适销性或特定用途适用性的默示保证。有关更多详细信息，请参阅 GNU 通用公共许可证。

,