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