ラインセグメントパスの違いを定量化するアルゴリズム

Question

以下の例のサブセットなど、2つのラインセグメントパスがあるとします。それらの違いを定量化するにはどうすればよいですか？

1. |__
2. \_
3. __
4. /\
5. \/
6. |
7. _

2つのパスには異なる数のセグメントがあり、各セグメントの長さとそれらの間の角度は可変です。

座標系を確立し、セグメントをノードとエッジとして定義することは良いと思っていました。違いはおそらく、一方を他方に変換するために必要な操作によって定量化される可能性があります。 levenshtein距離 アルゴリズム。残念ながら、操作スペースは巨大です。何か案は？ありがとう！

Answer 1

私は@awoodlandが指摘したものよりも少し先に進みます：あなたがそれを定量化する方法は依存します 全体的に 違いを定量化したい理由。

ラインセグメントパスのハッシュコードのようなユニークな（少なくとも、ユニークな）数字を思い付くことを探していますか？それとも、ラインセグメントパスを定量化して、「このパスはそのパスよりも複雑（またはより長い、またはより鋭い角度がある）と言っていますか？

ハッシュコードを作成する場合は、2つの32ビットCRC（または同様のもの）を作成することをお勧めします。1つはセグメントの長さと角度用です。これらのCRCを計算したら、高32ビットの角度と低32ビットの長さを使用して、64ビット値にそれらをまとめます。セグメントの数に応じて、おそらく単一のCRC値が実行されます。各セグメントに対して、長さを追加してから、それと次のセグメントの間に角度を追加します。

上記は、各パスの一意の数字を提供する可能性が高いが、保証されていないことに注意してください。

ラインセグメントパスの複雑さを定量化したい場合...私には多くのアイデアがありません。

Answer 2

それらを固定サイズの画像に描画し、ユークリッド距離を使用して画像を比較できます。

または、総長さを測定し、角度の絶対値（おそらく署名された角度）を測定として合計することもできます。これに基づいたものは、形状の向きに不変であるという素晴らしい特性を持っているでしょう（あなたがそれを望むなら！）。

それをどのように定量化するかは多少依存します どうして それらの違いを定量化したい。

Answer 3

あなたはこの論文を見ることができます：

http://www.vision.ee.ethz.ch/~calvin/publications/ferrari07pami.pdf

この論文では、オブジェクト検出にKAS（セグメントペアの一般化：相互に接続する複数のセグメントを持つことができます）を使用しています。これらのセグメントセットの記述子を紹介します。これは、ペアを説明するために使用できるものです。

私たちの記述子は回転不変ではないので、あなたに合わないかもしれません。

Answer 4

操作を使用する場合：

• コーナーとセグメントを追加します
• コーナーとセグメントを削除します
• ストレッチセグメント（差の重み付き）
• ベンドコーナー（差の重み付き）

N^2時間でありながら、まだLevenshtein距離を使用することができます。

次の[セグメント、コーナー]*としてセグメントをエンコードします。だからそれは次のとおりです：

[length, rotation] [length, rotation]...

ここで、回転はセグメントの指し方の方向にそれぞれです。

ストレッチと曲げの計算は非常に明白です。 Value[i-1, j-1] + stretch + bend.

追加/削除の計算。追加 Value[i,j-1] + Cost of adding, 、 削除する Value[i-1, j] + cost of removal.