4

最近、OpenCV（2.4.2）の関数minEnclosingCircleを使用しました。これは、ポイントのブロブの直径を測定する必要があるためです。

しばらくして、結果が正しくないことに気づいたので、非常に小さな点のセットの直径を計算する小さなルーチンを作成することにしました。

私は以下に対して機能をテストしました：

  • 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の正方形の半径は、13.110ではなく約12.726になります。エラーは正方形のサイズとともに増加します。1000x1000の正方形の場合、1455ではなく1412.5と予想されます。

実際、相対誤差は常に約3％であることに気づきました。

この奇妙な振る舞いをどのように説明できますか？

4

3 に答える 3

2

サブ関数には係数1.03が間違っていると思いますicvFindEnslosingCicle4pts_32f。半径に乗算されますが、二度と除算されることはありません。http://code.opencv.org/issues/3362で簡単な修正を加えたバグレポートを開きました

于 2013-11-06T13:36:48.913 に答える
1

Miniballという別のライブラリを使用して同じ問題を解決しようとしました。

Miniballで得られた結果は正しいです。この時点で、で使用されているアルゴリズムにエラーが含まれていると思い minEnclosingCircleます。

于 2013-02-11T15:27:32.260 に答える
1

完全を期すために、最小の囲みボールの問題を解決するためのアルゴリズムの実装がいくつかあります。

  • 2Dおよび3Dの場合、この質問に対する別の回答でも言及されているGärtnerの実装がおそらく最速です。

  • より高い次元（たとえば、最大10,000）については、 https：//github.com/hbf/miniballを参照してください。これは、Gärtner、Kutz、およびFischerによるアルゴリズムの実装です（注：私は共同の1人です-作成者）。

  • 非常に高次元の場合、コアセット（近似）アルゴリズムが高速になります。

注：球の最小の囲み球を計算するアルゴリズムを探している場合は、計算幾何学アルゴリズムライブラリ（CGAL）にC++の実装があります。（すべてのCGALを使用する必要はありません。必要なヘッダーとソースファイルを抽出するだけです。）

于 2013-02-24T04:37:09.460 に答える