5

この機能に固有の X & Y 座標 (機能ごとに 5 ～ 10 ポイント) のセットとして記述された画像に機能があるプロジェクトに取り組んでいます。また、それぞれが同じタイプの記述子を持つ何千もの機能を持つデータベースもあります。結果は次のようになります。

myFeature: (x1,y1), (x2,y2), (x3,y3)...

myDatabase: Feature1: (x1,y1), (x2,y2), (x3,y3)...
            Feature2: (x1,y1), (x2,y2), (x3,y3)...
            Feature3: (x1,y1), (x2,y2), (x3,y3)...
            ...

myDatabase の機能で myFeature の最適な一致を見つけたいと考えています。

これらの機能を一致させる最速の方法は何ですか? 現在、データベース内の各機能をステップ実行し、個々のポイントを比較しています。

bestScore = 0
for each feature in myDatabase:
    score = 0
    for each point descriptor in MyFeature:
        find minimum distance from the current point to the...
          points describing the current feature in the database
        if the distance < threshold:
            there is a match to the current point in the target feature
            score += 1

    if score > bestScore:
        save feature as new best match

この検索は機能しますが、大規模なデータベースでは明らかに遅くなります。このタイプの検索を行うためのより高速な方法を知っている人はいますか、または少なくとも記述子に明らかに一致しない機能をすばやく除外する方法がある場合は?

4

2 に答える 2

2

各機能からビットセット (1 と 0 の配列) を作成します。

検索条件にこのようなビットマスクを作成し、ビットごとに使用して、検索マスクを機能と比較します。

このアプローチにより、ほとんどの作業をデータの保存を担当するルーチンに移すことができます。また、ビットマスクの作成はそれほど計算集約的であってはなりません。

絶対に一致できない機能を除外したいだけの場合は、マスク作成アルゴリズムがそれを処理し、少しあいまいなビットマスクを作成する必要があります。

このようなマスクを作成する最も簡単な方法は、おそらく、フィーチャのマトリックスと同じ大きさのマトリックスを作成し、フィーチャに設定されているすべての座標に 1 を配置し、そうでないすべての座標に 0 を配置することです。次に、その行列を 1 次元の行に変換します。特徴行を検索マスクとビットごとに比較します。

これは、ビットマップ インデックスが大規模なデータベース (Oracle など) で機能する方法と似ていますが、意図が異なり、メモリ内のすべてのデータベース行の完全なビットマップ イメージがありません。

この力は、ビットごとの比較にあります。

32 ビット マシンでは、1 つの命令で 32 回の比較を実行できますが、ポイント比較では整数で 1 回しか実行できません。アーキテクチャによっては、浮動小数点演算でさらに高いボニーが得られます。

于 2010-11-05T12:55:44.257 に答える
1

これは一般に、空間インデックスの問題のように見えます。私の分野ではありませんが、機能を簡単に検索するために使用できる、クアッドツリーなどの一種のツリーインデックスを作成する必要があります。このウィキペディアの記事からいくつかのリンクを見つけることができます：http：//en.wikipedia.org/wiki/Spatial_index

既存の空間データベースに簡単に実装できるのは問題かもしれません。説明はGISに非常に似ています。

実行できることの1つは、すべてのフィーチャの重心を計算し、それを使用して検索スペースを少し縮小することです（1次元検索は、インデックスを作成するのがはるかに簡単です）が、これには欠点があります。ヒューリスティック（フィーチャの形状によっては、重心が奇妙な場所に配置される場合があります）。

于 2010-11-05T14:00:04.230 に答える