3D маркировка соединенных точек на основе евклидовых расстояний - PullRequest
Новая
       25

3D маркировка соединенных точек на основе евклидовых расстояний

3 голосов
/ 10 сентября 2010

В настоящее время я работаю над проектом, который пытается сгруппировать трехмерные точки из набора данных, определяя связность как минимальное евклидово расстояние. Мой алгоритм прямо сейчас - это просто 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-деревьев, обходится довольно дорого, но также не удаление точек создает проблемы в том, что каждую точку можно искать сотни раз, каждый соседний с ней рядом.

Итак, мой вопрос: есть ли лучший способ сделать это? Особенно таким образом, что будет расти линейно с набором данных?

Спасибо за любую помощь, которую вы можете оказать

EDIT Я попытался использовать простой отсортированный список, как сказал dash-tom-bang, но результат оказался даже медленнее, чем то, что я использовал раньше. Я не уверен, что это была реализация, или просто слишком медленно повторять каждую точку и проверять евклидово расстояние (даже при использовании квадратного расстояния.

Есть ли у людей другие идеи? Я честно сейчас в замешательстве.

Ответы [ 3 ]

3 голосов
/ 27 сентября 2010

Я предлагаю следующий алгоритм:

  1. Вычислить 3D триангуляцию Делоне для ваших точек данных.

  2. Удалите все ребра, которые длиннее, чемваше пороговое расстояние, O (N), в сочетании с шагом 3.

  3. Найдите связанные компоненты в результирующем графике, размер которого O (N), это делается в O (N α(N)).

Узким местом является этап 1, который может быть выполнен в O (N 2 ) или даже в O (N log N) в соответствии с этой страницейhttp://www.ncgia.ucsb.edu/conf/SANTA_FE_CD-ROM/sf_papers/lattuada_roberto/paper.html. Однако это определенно не алгоритм из 100 строк.

2 голосов
/ 27 сентября 2010

Очки должны быть лучше организованы. Для более эффективного поиска вместо vector<Point3d> вам нужна какая-то хэш-карта, где коллизия хешей подразумевает, что две точки расположены близко друг к другу (поэтому вы используете коллизии хешей в своих интересах). Например, вы можете разделить пространство на кубы размером, равным SEGMENT_MAX_DISTANCE, и использовать хеш-функцию, которая возвращает триплет целых чисел вместо просто целого числа, где каждая часть триплета вычисляется как point.<corresponding_dimension> / SEGMENT_MAX_DISTANCE.

Теперь для каждой точки в этом новом наборе вы ищете только точки в том же кубе и в соседних кубах пространства. Это значительно уменьшает пространство поиска.

2 голосов
/ 10 сентября 2010

Когда я делал что-то в этом духе, я выбирал «начало координат» вне набора данных и сортировал все точки по их расстоянию до этого источника. Тогда у меня был гораздо меньший набор точек для выбора на каждом шаге, и мне нужно было только пройти через область «луковой шкуры» вокруг рассматриваемой точки. Вы будете проверять соседние точки, пока расстояние до ближайшей точки не станет меньше ширины проверяемого диапазона.

Хотя это хорошо сработало для меня, аналогичная версия этого может быть достигнута, отсортировав все ваши точки вдоль одной оси (что представляло бы «начало координат», находящееся бесконечно далеко), а затем просто проверив точки снова, пока ваш «поиск» ширина "превышает расстояние до ближайшей найденной точки.

...