9

長さnとmの2つのシーケンスがあります。それぞれが（x、y）の形式の点のシーケンスであり、画像内の曲線を表します。これらのシーケンスがどのように異なる（または類似している）かを見つける必要があります

  1. 一方のシーケンスはもう一方のシーケンスよりも長い可能性があります（つまり、一方のシーケンスの長さはもう一方のシーケンスの半分または4分の1になりますが、ほぼ同じ曲線をトレースする場合は同じです）

  2. これらのシーケンスは反対方向である可能性があります（つまり、シーケンス1は左から右に進み、シーケンス2は右から左に進みます）

    レーベンシュタインのようないくつかの違いの推定値や、タンパク質フォールディングの構造的類似性マッチングの編集距離を調べましたが、どれもうまくいかないようです。独自のブルートフォースメソッドを作成することもできますが、もっと良い方法があるかどうか知りたいです。

ありがとう。

4

5 に答える 5

3

x、y座標に変換された曲線を一致させようとしているということですか？画像処理のテクニックの1つは、チェーンコードを使用することです[まともなリファレンスを探していますが、今見つけられるのはこれだけです]各シーケンスをエンコードしてから、それらのチェーンコードを比較します。差の合計（モジュロ8）をとることができ、結果が0の場合、曲線は同一です。シーケンスは長さが異なり、必ずしも同じ相対位置で開始する必要はないため、1つのシーケンスをシフトしてこれを何度も繰り返す必要がありますが、チェーンコードを作成する必要があるのは1回だけです。シーケンスの1つが逆になっているかどうかを検出する唯一の方法は、シーケンスの1つの順方向と逆方向の両方を試すことです。曲線が完全に類似していない場合、合計はゼロより大きくなりますが、曲線が単純に合計とどのように異なるかを判断するのは簡単ではありません。

この方法は回転不変ではありません。回転不変の方法が必要な場合は、境界中心の極座標エンコーディングを確認する必要があります。そのための無料のリファレンスは見つかりませんが、説明が必要な場合はお知らせください。

于 2011-06-21T04:12:34.450 に答える
2

これらの行に沿った方法が機能する可能性があります。

両方のシーケンスについて:

シーケンスを通して曲線を当てはめます。[0,1] からこの曲線上の点まで、1 対 1 の関数が連続していることを確認してください。つまり、0 と 1 の間の各 (実数) 数値に対して、この関数はそれに属する曲線上の点を返します。0 から 1 までのすべての数値について関数をトレースすると、曲線全体が得られます。

曲線を当てはめる 1 つの方法は、連続する点の各ペア間に直線を引くことです (これは鋭い曲がりがあるため、適切な曲線ではありませんが、目的には適している可能性があります)。その場合、関数はすべての線分 (ピタゴラス) の合計の長さを計算することによって取得できます。数値 Y (0 から 1 の間) に対応する曲線上の点は、シーケンスの最初の点からの距離 Y * (すべての線分の合計の長さ) を持つ曲線上の点に対応します。線分 (!!)。

ここで、最初のシーケンスの関数 F(double) と 2 番目のシーケンスの G(double) を取得した後、次のように類似度を計算できます。

double epsilon = 0.01;
double curveDistanceSquared = 0.0;
for(double d=0.0;d<1.0;d=d+epsilon)
{
   Point pointOnCurve1 = F(d);    
   Point pointOnCurve2 = G(d); 
   //alternatively, use G(1.0-d) to check whether the second sequence is reversed       
   double distanceOfPoints = pointOnCurve1.EuclideanDistance(pointOnCurve2);
   curveDistanceSquared = curveDistanceSquared + distanceOfPoints * distanceOfPoints;
}
similarity = 1.0/ curveDistanceSquared;

考えられる改善:

- カーブに合わせるための改善された方法を見つけます。上記の方法が機能するには、曲線をトレースする関数がまだ必要であることに注意してください。

-距離を計算するときは、距離が最小になるように関数 G を再パラメータ化することを検討してください。（これは、R（0）= 0およびR（1）= 1のような増加関数Rがあることを意味しますが、それ以外は一般的です。使用する距離を計算するとき

   Point pointOnCurve1 = F(d);    
   Point pointOnCurve2 = G(R(d));

次に、距離が最小になるように R を選択しようとします。(何が起こるかを確認するには、G(R(d)) も曲線をトレースすることに注意してください))。

于 2011-06-21T13:11:54.617 に答える
1

なんらかの曲線フィッティング手順 (通常または非線形の最小二乗法) を実行して、形状パラメーターの係数が同じかどうかを確認してみませんか。パネル データのようなモデルとして実行すると、パラメーターのセットが互いに有意に異なるかどうかの明示的な統計テストが行​​われます。これにより、同じ曲線でも異なる解像度でサンプリングされるという問題が解決されます。

于 2011-06-21T03:35:49.987 に答える
1

ステップ 1: 方向を正規化します。たとえば、すべての曲線が辞書式順序が最も低い端点から始まるとします。

def inCanonicalOrientation(path):
    return path if path[0]<path[-1] else reversed(path)

ステップ 2: おおよそ正確にすることも、非常に正確にすることもできます。非常に正確にしたい場合は、スプラインを計算するか、両方の曲線を適切な次数の多項式に当てはめ、係数を比較します。大まかな見積もりが必要な場合は、次のようにします。

def resample(path, numPoints)
    pathLength = pathLength(path)  #write this function

    segments = generateSegments(path)
    currentSegment = next(segments)
    segmentsSoFar = [currentSegment]

    for i in range(numPoints):
        samplePosition = i/(numPoints-1)*pathLength
        while samplePosition > pathLength(segmentsSoFar)+currentSegment.length:
            currentSegment = next(segments)
            segmentsSoFar.insert(currentSegment)
        difference = samplePosition - pathLength(segmentsSoFar)
        howFar = difference/currentSegment.length
        yield Point((1-howFar)*currentSegment.start + (howFar)*currentSegment.end)

これは、線形リサンプリングからより良いものに変更できます。

def error(pathA, pathB):
    pathA = inCanonicalOrientation(pathA)
    pathB = inCanonicalOrientation(pathB)

    higherResolution = max([len(pathA), len(pathB)])
    resampledA = resample(pathA, higherResolution)
    resampledB = resample(pathA, higherResolution)

    error = sum(
        abs(pointInA-pointInB)
        for pointInA,pointInB in zip(pathA,pathB)
    )
    averageError = error / len(pathAorB)
    normalizedError = error / Z(AorB)
    return normalizedError

Z はパスの「直径」のようなもので、おそらくパス内の任意の 2 点間の最大ユークリッド距離です。

于 2011-06-22T01:03:02.697 に答える
0

曲線フィッティング手順を使用しますが、定数項、つまり 0 = B0 + B1*X + B2*Y + B3*X*Y + B4*X^2 なども使用します。これにより並進分散が捕捉され、次に、それらを分類する方法として、2 つの点のセットによって形成される曲線の推定係数の統計的比較を行うことができます。データがxy平面で任意の曲線を形成する場合、二変量補間を行う必要があると思います。

于 2011-06-21T21:26:33.387 に答える