4

我最近使用了 OpenCV (2.4.2) 的 minEnclosureCircle 函数，因为我需要测量一团点的直径。

过了一会儿，我意识到结果不正确，所以我决定编写一个小程序来计算一组非常小的点的直径。

我针对以下功能测试了该功能：

  • 1个单点
  • 连续 2 - 4 个点
  • 仅由4个角点组成的不同大小的正方形

在下表中，您可以看到我的测试结果：

Note         Diameter           Center                                         Points
1x1             2.000       (1.0, 1.0)                                       [[1, 1]]
2x1             2.000       (1.0, 1.5)                               [[1, 1], [1, 2]]
3x1             2.060       (1.0, 2.0)                       [[1, 1], [1, 2], [1, 3]]
4x1             3.090       (1.0, 2.5)               [[1, 1], [1, 2], [1, 3], [1, 4]]
2x2             2.000       (1.5, 1.5)               [[1, 1], [1, 2], [2, 1], [2, 2]]
3x3             2.913       (2.0, 2.0)               [[1, 1], [1, 3], [3, 1], [3, 3]]
4x4             4.370       (2.5, 2.5)               [[1, 1], [1, 4], [4, 1], [4, 4]]
6x6             7.283       (3.5, 3.5)               [[1, 1], [1, 6], [6, 1], [6, 6]]
8x8            10.196       (4.5, 4.5)               [[1, 1], [1, 8], [8, 1], [8, 8]]
9x9            11.653       (5.0, 5.0)               [[1, 1], [1, 9], [9, 1], [9, 9]]
16x16          21.850       (8.5, 8.5)           [[1, 1], [1, 16], [16, 1], [16, 16]]
10x10          13.110       (5.5, 5.5)           [[1, 1], [1, 10], [10, 1], [10, 10]]
100x100       144.207     (50.5, 50.5)       [[1, 1], [1, 100], [100, 1], [100, 100]]
1000x1000    1455.183   (500.5, 500.5)   [[1, 1], [1, 1000], [1000, 1], [1000, 1000]]

我已经看到该函数不会返回小于 1 的半径，所以我得到的最小直径是 2.0。

除此之外，该函数总是返回比我预期更大的半径。例如，10x10 正方形的半径约为 12.726 而不是 13.110。误差随着正方形的大小而增加：对于 1000x1000 的正方形，我希望是 1412.5 而不是 1455。

实际上，我意识到相对误差始终在 3% 左右。

我该如何解释这种奇怪的行为？

4

3 回答 3

2

我相信，子函数中有一个因子 1.03 是错误的icvFindEnslosingCicle4pts_32f——它乘以半径，但不再除以。我在http://code.opencv.org/issues/3362打开了一个带有简单修复的错误报告

于 2013-11-06T13:36:48.913 回答
1

为了完整起见，有几种算法实现可以解决最小包围球问题。

  • 对于 2D 和 3D，Gärtner 的实现（也在此问题的另一个答案中提到）可能是最快的。

  • 对于更高的维度（比如高达 10,000），请查看https://github.com/hbf/miniball，这是 Gärtner、Kutz 和 Fischer 的算法实现（注意：我是其中的一员） -作者）。

  • 对于非常非常高的维度，核心集（近似）算法会更快。

注意：如果您正在寻找一种算法来计算 spheres 的最小封闭球体，您将在Computational Geometry Algorithms Library (CGAL)中找到 C++ 实现。（您不需要使用所有 CGAL；只需提取所需的头文件和源文件。）

于 2013-02-24T04:37:09.460 回答
1

我尝试使用另一个名为Miniball的库来解决同样的问题。

使用 Miniball 获得的结果是正确的。在这一点上，我猜测中使用的算法 minEnclosingCircle包含一些错误。

于 2013-02-11T15:27:32.260 回答