3

現在、接続性を最小ユークリッド距離として指定することにより、データセットから3Dポイントをグループ化しようとしているプロジェクトに取り組んでいます。現在の私のアルゴリズムは、単純なフラッドフィルの3D適応です。

size_t PointSegmenter::growRegion(size_t & seed, size_t segNumber) {
    size_t numPointsLabeled = 0;

    //alias for points to avoid retyping
    vector<Point3d> & points = _img.points;
    deque<size_t> ptQueue;
    ptQueue.push_back(seed);
    points[seed].setLabel(segNumber);
    while (!ptQueue.empty()) {
        size_t currentIdx = ptQueue.front();
        ptQueue.pop_front();
        points[currentIdx].setLabel(segNumber);
        numPointsLabeled++;
        vector<int> newPoints = _img.queryRadius(currentIdx, SEGMENT_MAX_DISTANCE, MATCH_ACCURACY);
        for (int i = 0; i < (int)newPoints.size(); i++) {
            int newIdx = newPoints[i];
            Point3d &newPoint = points[newIdx];
            if(!newPoint.labeled()) {
                newPoint.setLabel(segNumber);
                ptQueue.push_back(newIdx);
            }
        }
    }

    //NOTE to whoever wrote the other code, the compiler optimizes i++ 
    //to ++i in cases like these, so please don't change them just for speed :)
    for (size_t i = seed; i < points.size(); i++) {
        if(!points[i].labeled()) {
            //search for an unlabeled point to serve as the next seed.
            seed = i;
            return numPointsLabeled;
        }
    }
    return numPointsLabeled;
}

このコードスニペットが新しいシードに対して再度実行され、_img.queryRadius（）がANNライブラリを使用した固定半径検索である場合：

vector<int> Image::queryRadius(size_t index, double range, double epsilon) {
    int k = kdTree->annkFRSearch(dataPts[index], range*range, 0);
    ANNidxArray nnIdx = new ANNidx[k];
    kdTree->annkFRSearch(dataPts[index], range*range, k, nnIdx);
    vector<int> outPoints;
    outPoints.reserve(k);
    for(int i = 0; i < k; i++) {
        outPoints.push_back(nnIdx[i]);
    }
    delete[] nnIdx;
    return outPoints;
}

このコードに関する私の問題は、大きなデータセットに対して実行が遅すぎることです。私が間違っていなければ、このコードはすべてのポイントを検索し、検索はO（NlogN）であるため、時間計算量は（N ^ 2 * log（N））になります。

それに加えて、KDツリーから直接覚えている場合、削除には比較的コストがかかりますが、ポイントを削除しないと、各ポイントが近くにあるすべてのポイントで何百回も検索される可能性があるという問題が発生します。

だから私の質問は、これを行うためのより良い方法はありますか？特に、データセットとともに直線的に成長する方法で？

あなたが提供できるかもしれないどんな助けにも感謝します

編集 dash-tom-bangが言ったような単純なソート済みリストを使用してみましたが、結果は以前使用していたものよりもさらに遅くなりました。それが実装だったのか、それとも単に遅すぎてすべてのポイントを反復処理してユークリッド距離をチェックできなかったのかはわかりません（2乗距離を使用した場合でも）。

人々が持っているかもしれない他のアイデアはありますか？私は今正直に困惑しています。

4

3 に答える 3

3

次のアルゴリズムを提案します。

  1. データ ポイントの 3D Delaunay 三角形分割を計算します。

  2. ステップ 3 と組み合わせると、しきい値距離 O(N) よりも長いすべてのエッジを削除します。

  3. サイズが O(N) の結果のグラフで連結要素を見つけます。これは O(N α(N)) で行われます。

ボトルネックは、このページhttp://www.ncgia.ucsb.edu/conf/SANTA_FE_CD-ROM/sf_papers/lattuada_roberto/paperによると、O(N 2 ) または O(N log N)で実行できるステップ 1です。 .html . ただし、100 行のアルゴリズムではないことは間違いありません。

于 2010-09-27T10:41:07.853 に答える
2

ポイントはよりよく整理されている必要があります。より効率的に検索するには、vector<Point3d>ハッシュ衝突が 2 つのポイントが互いに近いことを意味する、ある種のハッシュ マップが必要です (したがって、ハッシュ衝突を有利に使用します)。たとえば、空間を SEGMENT_MAX_DISTANCE に等しいサイズの立方体に分割し、int だけでなく、int のトリプレットを返すハッシュ関数を使用できます。トリプレットの各部分は として計算されpoint.<corresponding_dimension> / SEGMENT_MAX_DISTANCEます。

この新しいセットの各点について、同じ立方体と隣接する空間立方体の点のみを検索します。これにより、検索スペースが大幅に削減されます。

于 2010-09-26T22:31:24.067 に答える
2

これらの線に沿って何かをしたとき、どこかのデータセットの外側の「原点」を選択し、その原点までの距離ですべてのポイントを並べ替えました。次に、各ステップで選択するポイントのセットがはるかに少なくなり、考慮しているポイントの周りの「オニオン スキン」領域を通過するだけで済みました。最も近いポイントまでの距離がチェックしている範囲の幅よりも小さくなるまで、隣接するポイントをチェックします。

それは私にとってはうまくいきましたが、すべてのポイントを1つの軸（「原点」が無限に離れていることを表す）に沿ってソートし、「検索幅」が超えるまでポイントを再度チェックすることで、同様のバージョンを実現できますこれまでに見つかった最も近いポイントまでの距離。

于 2010-09-10T18:37:30.213 に答える