15

任意の長方形を順序付けられていない点のセットに最適に適合させるアルゴリズムを探しています。具体的には、ポイントから長方形のエッジのいずれかまでの距離の合計が最小になる長方形を探しています。最適な線、円、楕円のアルゴリズムをたくさん見つけましたが、四角形にはありません。理想的には、C、C++、または Java で何かを作成したいと考えていますが、言語に関してそれほどうるさくはありません。

入力データは通常、長方形の上または近くにあるほとんどのポイントで構成され、いくつかの外れ値があります。データの分布は不均一で、四隅すべてが含まれる可能性は低いです。

4

4 に答える 4

3

ここにあなたを助けるかもしれないいくつかのアイデアがあります.

ポイントがエッジ上にあるかコーナー上にあるかは、次のように推定できます。

  1. ポイントの n 近傍を収集します
  2. ポイントの重心を計算する
  3. ポイントの共分散行列を次のように計算します。
    1. 皮切りにCovariance = ((0, 0), (0, 0))
    2. ポイントごとに計算するd = point - centroid
    3. Covariance += outer_product(d, d)
  4. 共分散の固有値を計算します。(例: SVD を使用)
  5. 分類ポイント:
    • 一方の固有値が大きく、もう一方の固有値が非常に小さい場合、おそらく限界に達しています
    • そうでなければ、私たちは角にいるはずです

すべてのコーナー ポイントを抽出し、セグメンテーションを実行します。エントリが最も多い 4 つのセグメントを選択します。これらのセグメントの重心は、長方形の角の候補です。

2 つの反対側の正規化された方向ベクトルを計算し、それらの平均を計算します。他の 2 つの反対側の平均を計算します。これらは、平行四辺形の方向ベクトルです。長方形が必要な場合は、それらの方向の 1 つに垂直なベクトルを計算し、他の方向ベクトルで平均を計算します。次に、長方形の方向は平均ベクトルと垂直ベクトルです。

角を計算するために、候補をその方向に投影し、それらが長方形の角を形成するように移動できます。

于 2013-07-03T09:27:19.607 に答える
1

これが一般的な考え方です。小さいセルでグリッドを作成します。空すぎないセルごとに最適な線を計算します (計算はすぐに行われます1、検索は含まれません)。標準偏差が改善している/あまり悪化していないことを確認しながら、隣接するセルを結合します。このようにして、4 つの辺と 4 つの角を検出し、点を 4 つのグループに分け、それぞれが 4 つの辺の 1 つに属します。

次に、角のセルを捨てて、4 本の近似直線の代わりに真の長方形を置き、ちょっとした山登り (または何でも) を行います。この場合、2 本の線が平行であり、点を 4 つのグループに分けているため、最適な線の計算を拡張することができます (特定の長方形の場合、2 つの反対側の間のデルタ y がわかっています (ちょっと水平っぽい辺を取ります) ので、このデルタ y をyポイントの下位グループの s に追加して計算を行います)。

最初の長方形のグリッドは、ストライプ (たとえば、垂直) による作業に置き換えることができます。次に、ストライプの少なくとも半分には、ポイントの2つの顕著なグループがあります（各ストライプを水平方向の分割線でセルに分割することでそれらを見つけます）。

1直線について、その直線に対するデータ点 {x i ,y i }Y = a*X+bの垂直距離の二乗和を最小化します。これはとについて直接解けます。縦線を増やすには、X と Y を反転します。ab

PS私は問題を、長方形のすべての辺ではなく、長方形の最も近い辺までの各点の垂直距離の二乗和を最小化するものとして解釈します。

于 2013-07-03T13:19:55.823 に答える
0

完全にはわかりませんが、ポイントから PCA を介して最初の 2 (3?) 次元で遊ぶ可能性があります。ほとんどの場合、かなり高速に動作します。

于 2016-09-20T19:58:50.977 に答える