点集合から四角形の頂点を見つける

Question

四角形の頂点を点集合から取得しようとしています。

• 点のセットは、時々、アウトラインが検索コーナーポイントは、所定のセットのポイントであることを、いくつかのノイズ（第2図を参照）
• ありませんしている発注し、アウトライン
• を記述しています点（左画像3枚目の底を参照）
• ザコーナー点が必ずしも矩形

凸四角形を記述する検索しました

2番目の画像は少し極端ですが、ポイントのセットの「品質」は第1画像と第2画像の間にあります。

最初に私はヒストグラムを1~360度以上の長さから作成することを考えました。 4つの最も高いピークは、各ラインの長さを表す。しかし、私が注文ポイントを失っているだけで、程度と長さまたは行について知っていて、行がどの位置に属しているのか分かりません。

次に、同じ程度のものがあれば、次の2行をマージすることを考えましたが、ここでノイズを処理したり、コーナーを予測する方法がわかりません。

誰かがこの問題やそれに類するものを扱うアルゴリズムを知っていますか？

Answer 1

これをクラスタリングの問題として扱うことができます。クラスタの "センター"は実際には直線です。クラスタリングを計算するには、k-meansアルゴリズムを使用することができます。

1. ポイントをランダムに4つ選びます。それぞれに線を合わせると、点線を通る4本の線があります。
2. 解決策が収束したと思われるまで繰り返す：
   1. それぞれの点について、4本の線それぞれまでの距離を計算する。
   2. ポイントは、最も近くにある行に対応するバケットに割り当てます。 4つのバケットのそれぞれの点に
   3. フィット4つの新しい行は、あなたが上ヒストグラムを取るあなたのアイデアを取ることができる最初のステップを向上させるために

（あなたは、線形回帰やSVDを使用することができます）最も近いピークに対応するバケットに最初に各ポイントを割り当てます。次に、4つのバケットにラインを合わせ、繰り返しを開始します。

これを最適化の問題として扱うこともできます。差の領域（四角形の内側の白い領域と四角形の外側の黒い領域）が最小になるように4点を選択します。一般的な最適化アルゴリズムはおそらく動作しますが、高速化するためには、領域を計算するための合理的なアルゴリズムが必要です。