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;
}

我对这段代码的问题是它运行 waaaaaaaaaaaaaaaay 对于大型数据集来说太慢了。如果我没记错的话，这段代码将对每一个点进行搜索，搜索时间为 O(NlogN)，时间复杂度为 (N^2*log(N))。

除此之外，如果我从 KD 树中记得，删除相对昂贵，而且不删除点也会产生问题，因为每个点都可以被靠近它的每个邻居搜索数百次。

所以我的问题是，有没有更好的方法来做到这一点？特别是随着数据集线性增长的方式？

感谢您提供的任何帮助

编辑 我曾尝试使用像 dash-tom-bang 所说的简单排序列表，但结果甚至比我以前使用的要慢。我不确定它是否是实现，或者它只是太慢了，无法遍历每个点并检查欧几里得距离（即使只使用平方距离。

人们可能还有其他想法吗？我现在真的很难过。

4

3 回答 3

3

我提出以下算法：

  1. 计算数据点的 3D Delaunay 三角剖分。

  2. 与步骤 3 结合使用时，删除所有长于阈值距离 O(N) 的边。

  3. 在结果图中找到大小为 O(N) 的连通分量，这是在 O(N α(N)) 中完成的。

瓶颈是步骤 1，根据此页面http://www.ncgia.ucsb.edu/conf/SANTA_FE_CD-ROM/sf_papers/lattuada_roberto/paper可以在 O(N 2 ) 甚至 O(N log N) 中完成.html。但是，它绝对不是 100 行算法。

于 2010-09-27T10:41:07.853 回答
2

当我按照这些思路做某事时，我在数据集之外的某个地方选择了一个“原点”，并根据它们到该原点的距离对所有点进行排序。然后，我在每一步都有一组小得多的点可供选择，我只需要通过正在考虑的点周围的“洋葱皮”区域。您将检查相邻点，直到到最近点的距离小于您正在检查的范围的宽度。

虽然这对我来说效果很好，但可以通过沿一个轴对所有点进行排序（这表示“原点”无限远）然后再次检查点直到您的“搜索宽度”超过到目前为止找到的最近点的距离。

于 2010-09-10T18:37:30.213 回答
2

应该更好地组织点。为了更有效地搜索而不是 avector<Point3d>您需要某种哈希映射，其中哈希冲突意味着两个点彼此靠近（因此您可以使用哈希冲突来获得优势）。例如，您可以将空间划分为大小等于 SEGMENT_MAX_DISTANCE 的立方体，并使用一个哈希函数返回一个整数的三元组而不是一个整数，其中三元组的每个部分计算为point.<corresponding_dimension> / SEGMENT_MAX_DISTANCE.

现在对于这个新集合中的每个点，您只搜索同一个立方体中的点，以及相邻的空间立方体中的点。这大大减少了搜索空间。

于 2010-09-26T22:31:24.067 回答