algorithm - 一連の点から四角形の頂点を見つける

Question

ポイントのセットから四角形のコーナーポイントを取得しようとしています。

• ポイントのセットは順序付けられ、アウトラインを記述します
• アウトラインにノイズがある場合があります (2 枚目の画像を参照)。
• 検索されたコーナー ポイントは、指定されたポイント セットから外れたポイントである必要はありません (左下の 3 番目の画像を参照)。
• 検索されたコーナー ポイントは凸状の四角形を表しますが、必ずしも四角形である必要はありません

2 番目の写真は少し極端ですが、私の一連のポイントの「品質」は最初の写真と 2 番目の写真の間にありました。

最初に、1 ～ 360° と長さからヒストグラムを作成することを考えました。以下の 2 点について説明します。4 つの最高峰は、各線の長さを表します。しかし、それでは注文ポイントを失います。次数と長さ、または線について知っているだけで、線がどの位置に属しているかはわかりません。

次に、2 つの次の行が多かれ少なかれ同じ次数である場合はマージすることを考えましたが、ここでノイズを処理する方法やコーナーを予測する方法がわかりません。

この問題または同様の問題を処理するアルゴリズムを知っている人はいますか?

Answer 1

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

1. ポイントの 4 つのランダムなペアを選択します。それぞれに線を合わせると、点群を通る線が 4 本になります。
2. 解が収束したように見えるまで繰り返します。
   1. ポイントごとに、4 つの線のそれぞれまでの距離を計算します。
   2. ポイントが最も近いラインに対応するバケットにポイントを割り当てます。
   3. 4 つのバケットのそれぞれの点に 4 つの新しい線を当てはめます (線形回帰または SVD を使用できます)。

最初のステップを改善するには、角度にわたってヒストグラムを取得するというアイデアを採用し、最初に各ポイントを最も近いピークに対応するバケットに割り当てます。次に、4 つのバケットに線を当てはめ、反復を開始します。

これを最適化問題として扱うこともできます。差の領域 (四角形の内側の白い領域と外側の黒い領域) が可能な限り小さくなるように 4 つの点を選びます。一般的な最適化アルゴリズムはおそらく機能しますが、高速化するには、面積を計算するための合理的なアルゴリズムが必要です。