Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

FarthestPointDownSample: starting with an index other than 0 #7049

Open
3 tasks done
abhishek47kashyap opened this issue Nov 10, 2024 · 7 comments · May be fixed by #7076
Open
3 tasks done

FarthestPointDownSample: starting with an index other than 0 #7049

abhishek47kashyap opened this issue Nov 10, 2024 · 7 comments · May be fixed by #7076
Assignees
@benjaminum
Labels
question

Comments

@abhishek47kashyap
Copy link

abhishek47kashyap commented Nov 10, 2024 •
edited
Loading

Checklist

My Question

Looking at the implementation of PointCloud::FarthestPointDownSample() (linked down below for convenience), the downsampling always starts from points_[0] because farthest_index is initialized as 0.

Open3D/cpp/open3d/geometry/PointCloud.cpp

Lines 509 to 542 in fcc396e

std::shared_ptr<PointCloud> PointCloud::FarthestPointDownSample(
size_t num_samples) const {
if (num_samples == 0) {
return std::make_shared<PointCloud>();
} else if (num_samples == points_.size()) {
return std::make_shared<PointCloud>(*this);
} else if (num_samples > points_.size()) {
utility::LogError(
"Illegal number of samples: {}, must <= point size: {}",
num_samples, points_.size());
}
// We can also keep track of the non-selected indices with unordered_set,
// but since typically num_samples << num_points, it may not be worth it.
std::vector<size_t> selected_indices;
selected_indices.reserve(num_samples);
const size_t num_points = points_.size();
std::vector<double> distances(num_points,
std::numeric_limits<double>::infinity());
size_t farthest_index = 0;
for (size_t i = 0; i < num_samples; i++) {
selected_indices.push_back(farthest_index);
const Eigen::Vector3d &selected = points_[farthest_index];
double max_dist = 0;
for (size_t j = 0; j < num_points; j++) {
double dist = (points_[j] - selected).squaredNorm();
distances[j] = std::min(distances[j], dist);
if (distances[j] > max_dist) {
max_dist = distances[j];
farthest_index = j;
}
}
}
return SelectByIndex(selected_indices);
}

However, how could I start the downsampling from another index?

I could copy the implementation and modify the initial value of farthest_index to my desired index, but I wanted to ask if something already exists for this.
@benjaminum
Copy link
Contributor

You could swap the point at index 0 with the point of your desired index and then call FarthestPointDownSample. Does this work for you?

@abhishek47kashyap
Copy link
Author

swap the point at index 0 with the point of your desired index

That is indeed how I'm doing it right now

@abhishek47kashyap
Copy link
Author

abhishek47kashyap commented Nov 14, 2024 •
edited
Loading

Would maintainers be in favor of providing the option to start from a specified index other than 0? I can take a shot at this then and open a PR

@benjaminum benjaminum self-assigned this Nov 17, 2024
@benjaminum
Copy link
Contributor

Can you explain how you use the feature? I just want to understand the use case better

@abhishek47kashyap
Copy link
Author

Use case

I've got several camera poses (200+) looking at the same region/scene from different viewpoints. For every camera pose, I want to find n farthest viewpoints so as to get maximum "spread" for the scene. So my idea is that I can use the camera positions from the poses and run farthest point sampling, cycle through every camera position, and find the set of camera poses that are truly as far apart as they can be.

Admittedly, I'm not directly operating on a point cloud for this use case, but since I'm working with point clouds as part of the project anyway and therefore am already using Open3D, I thought I would create a "point cloud" out of the camera positions and use an Open3D functionality if available. I came across tools like fpsample but I'm not keen on bringing in a new dependency just for this one thing.

@benjaminum
Copy link
Contributor

Looks like a really good example where setting the start index is needed. Looking forward to the PR!

@abhishek47kashyap abhishek47kashyap linked a pull request Nov 25, 2024 that will close this issue
Open
9 tasks
@abhishek47kashyap
Copy link
Author

@benjaminum PR's up for you to take a look when you can :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@benjaminum benjaminum

Labels
question
Projects
None yet
Milestone
No milestone
2 participants
@benjaminum @abhishek47kashyap