24 #include "Eigen/Geometry" 28 #include "cartographer/mapping/proto/scan_matching//fast_correlative_scan_matcher_options_3d.pb.h" 30 #include "glog/logging.h" 34 namespace scan_matching {
36 proto::FastCorrelativeScanMatcherOptions3D
39 proto::FastCorrelativeScanMatcherOptions3D options;
40 options.set_branch_and_bound_depth(
41 parameter_dictionary->
GetInt(
"branch_and_bound_depth"));
42 options.set_full_resolution_depth(
43 parameter_dictionary->
GetInt(
"full_resolution_depth"));
44 options.set_min_rotational_score(
45 parameter_dictionary->
GetDouble(
"min_rotational_score"));
46 options.set_min_low_resolution_score(
47 parameter_dictionary->
GetDouble(
"min_low_resolution_score"));
48 options.set_linear_xy_search_window(
49 parameter_dictionary->
GetDouble(
"linear_xy_search_window"));
50 options.set_linear_z_search_window(
51 parameter_dictionary->
GetDouble(
"linear_z_search_window"));
52 options.set_angular_search_window(
53 parameter_dictionary->
GetDouble(
"angular_search_window"));
59 const proto::FastCorrelativeScanMatcherOptions3D& options) {
60 CHECK_GE(options.branch_and_bound_depth(), 1);
61 CHECK_GE(options.full_resolution_depth(), 1);
64 Eigen::Array3i last_width = Eigen::Array3i::Ones();
65 for (
int depth = 1; depth != options.branch_and_bound_depth(); ++depth) {
66 const bool half_resolution = depth >= options.full_resolution_depth();
67 const Eigen::Array3i next_width = ((1 << depth) * Eigen::Array3i::Ones());
68 const int full_voxels_per_high_resolution_voxel =
69 1 << std::max(0, depth - options.full_resolution_depth());
70 const Eigen::Array3i shift = (next_width - last_width +
71 (full_voxels_per_high_resolution_voxel - 1)) /
72 full_voxels_per_high_resolution_voxel;
75 last_width = next_width;
87 Candidate3D(
const int scan_index,
const Eigen::Array3i& offset)
88 : scan_index(scan_index), offset(offset) {}
103 float score = -std::numeric_limits<float>::infinity();
106 float low_resolution_score = 0.f;
114 std::vector<std::pair<Eigen::VectorXf, float>> HistogramsAtAnglesFromNodes(
115 const std::vector<TrajectoryNode>& nodes) {
116 std::vector<std::pair<Eigen::VectorXf, float>> histograms_at_angles;
117 for (
const auto& node : nodes) {
118 histograms_at_angles.emplace_back(
119 node.constant_data->rotational_scan_matcher_histogram,
123 node.constant_data->gravity_alignment.inverse())));
125 return histograms_at_angles;
132 const HybridGrid*
const low_resolution_hybrid_grid,
133 const std::vector<TrajectoryNode>& nodes,
134 const proto::FastCorrelativeScanMatcherOptions3D& options)
137 width_in_voxels_(hybrid_grid.grid_size()),
138 precomputation_grid_stack_(
140 low_resolution_hybrid_grid_(low_resolution_hybrid_grid),
141 rotational_scan_matcher_(HistogramsAtAnglesFromNodes(nodes)) {}
145 std::unique_ptr<FastCorrelativeScanMatcher3D::Result>
155 options_.angular_search_window(), &low_resolution_matcher};
157 search_parameters, global_node_pose.
cast<
float>(),
158 global_submap_pose.
cast<
float>(),
164 std::unique_ptr<FastCorrelativeScanMatcher3D::Result>
166 const Eigen::Quaterniond& global_node_rotation,
167 const Eigen::Quaterniond& global_submap_rotation,
169 float max_point_distance = 0.f;
170 for (
const Eigen::Vector3f& point :
172 max_point_distance = std::max(max_point_distance, point.norm());
174 const int linear_window_size =
180 linear_window_size, linear_window_size, M_PI, &low_resolution_matcher};
190 std::unique_ptr<FastCorrelativeScanMatcher3D::Result>
196 const Eigen::VectorXf& rotational_scan_matcher_histogram,
197 const Eigen::Quaterniond& gravity_alignment,
const float min_score)
const {
199 search_parameters, point_cloud, rotational_scan_matcher_histogram,
200 gravity_alignment, global_node_pose, global_submap_pose);
202 const std::vector<Candidate3D> lowest_resolution_candidates =
206 search_parameters, discrete_scans, lowest_resolution_candidates,
208 if (best_candidate.
score > min_score) {
209 return common::make_unique<Result>(
Result{
210 best_candidate.
score,
212 discrete_scans[best_candidate.
scan_index].rotational_score,
221 const float rotational_score)
const {
222 std::vector<std::vector<Eigen::Array3i>> cell_indices_per_depth;
225 std::vector<Eigen::Array3i> full_resolution_cell_indices;
226 for (
const Eigen::Vector3f& point :
228 full_resolution_cell_indices.push_back(original_grid.
GetCellIndex(point));
230 const int full_resolution_depth = std::min(
options_.full_resolution_depth(),
232 CHECK_GE(full_resolution_depth, 1);
233 for (
int i = 0; i != full_resolution_depth; ++i) {
234 cell_indices_per_depth.push_back(full_resolution_cell_indices);
236 const int low_resolution_depth =
237 options_.branch_and_bound_depth() - full_resolution_depth;
238 CHECK_GE(low_resolution_depth, 0);
239 const Eigen::Array3i search_window_start(
243 for (
int i = 0; i != low_resolution_depth; ++i) {
244 const int reduction_exponent = i + 1;
245 const Eigen::Array3i low_resolution_search_window_start(
246 search_window_start[0] >> reduction_exponent,
247 search_window_start[1] >> reduction_exponent,
248 search_window_start[2] >> reduction_exponent);
249 cell_indices_per_depth.emplace_back();
250 for (
const Eigen::Array3i& cell_index : full_resolution_cell_indices) {
251 const Eigen::Array3i cell_at_start = cell_index + search_window_start;
252 const Eigen::Array3i low_resolution_cell_at_start(
253 cell_at_start[0] >> reduction_exponent,
254 cell_at_start[1] >> reduction_exponent,
255 cell_at_start[2] >> reduction_exponent);
256 cell_indices_per_depth.back().push_back(
257 low_resolution_cell_at_start - low_resolution_search_window_start);
266 const Eigen::VectorXf& rotational_scan_matcher_histogram,
267 const Eigen::Quaterniond& gravity_alignment,
270 std::vector<DiscreteScan3D> result;
274 for (
const Eigen::Vector3f& point : point_cloud) {
275 const float range = point.norm();
276 max_scan_range = std::max(range, max_scan_range);
278 const float kSafetyMargin = 1.f - 1e-2f;
279 const float angular_step_size =
284 std::vector<float> angles;
285 for (
int rz = -angular_window_size; rz <= angular_window_size; ++rz) {
286 angles.push_back(rz * angular_step_size);
289 global_submap_pose.
inverse() * global_node_pose;
291 rotational_scan_matcher_histogram,
293 gravity_alignment.inverse().cast<
float>()),
295 for (
size_t i = 0; i != angles.size(); ++i) {
296 if (scores[i] <
options_.min_rotational_score()) {
299 const Eigen::Vector3f angle_axis(0.f, 0.f, angles[i]);
305 global_submap_pose.
rotation().inverse() *
314 std::vector<Candidate3D>
317 const int num_discrete_scans)
const {
319 const int num_lowest_resolution_linear_xy_candidates =
322 const int num_lowest_resolution_linear_z_candidates =
325 const int num_candidates =
327 common::Power(num_lowest_resolution_linear_xy_candidates, 2) *
328 num_lowest_resolution_linear_z_candidates;
329 std::vector<Candidate3D> candidates;
330 candidates.reserve(num_candidates);
331 for (
int scan_index = 0; scan_index != num_discrete_scans; ++scan_index) {
336 y += linear_step_size) {
339 x += linear_step_size) {
340 candidates.emplace_back(scan_index, Eigen::Array3i(x, y, z));
345 CHECK_EQ(candidates.size(), num_candidates);
350 const int depth,
const std::vector<DiscreteScan3D>& discrete_scans,
351 std::vector<Candidate3D>*
const candidates)
const {
352 const int reduction_exponent =
353 std::max(0, depth -
options_.full_resolution_depth() + 1);
356 const DiscreteScan3D& discrete_scan = discrete_scans[candidate.scan_index];
357 const Eigen::Array3i offset(candidate.offset[0] >> reduction_exponent,
358 candidate.offset[1] >> reduction_exponent,
359 candidate.offset[2] >> reduction_exponent);
361 for (
const Eigen::Array3i& cell_index :
363 const Eigen::Array3i proposed_cell_index = cell_index + offset;
370 std::sort(candidates->begin(), candidates->end(),
371 std::greater<Candidate3D>());
374 std::vector<Candidate3D>
377 const std::vector<DiscreteScan3D>& discrete_scans)
const {
378 std::vector<Candidate3D> lowest_resolution_candidates =
380 discrete_scans.size());
382 &lowest_resolution_candidates);
383 return lowest_resolution_candidates;
387 const std::vector<DiscreteScan3D>& discrete_scans,
396 const std::vector<DiscreteScan3D>& discrete_scans,
397 const std::vector<Candidate3D>& candidates,
const int candidate_depth,
398 float min_score)
const {
399 if (candidate_depth == 0) {
401 if (candidate.score <= min_score) {
406 const float low_resolution_score =
409 if (low_resolution_score >=
options_.min_low_resolution_score()) {
413 return best_candidate;
422 best_high_resolution_candidate.
score = min_score;
424 if (candidate.score <= min_score) {
427 std::vector<Candidate3D> higher_resolution_candidates;
428 const int half_width = 1 << (candidate_depth - 1);
429 for (
int z : {0, half_width}) {
433 for (
int y : {0, half_width}) {
434 if (candidate.offset.y() + y >
438 for (
int x : {0, half_width}) {
439 if (candidate.offset.x() + x >
443 higher_resolution_candidates.emplace_back(
444 candidate.scan_index, candidate.offset + Eigen::Array3i(x, y, z));
449 &higher_resolution_candidates);
450 best_high_resolution_candidate = std::max(
451 best_high_resolution_candidate,
453 higher_resolution_candidates, candidate_depth - 1,
454 best_high_resolution_candidate.
score));
456 return best_high_resolution_candidate;
sensor::PointCloud high_resolution_point_cloud
PointCloud TransformPointCloud(const PointCloud &point_cloud, const transform::Rigid3f &transform)
const proto::FastCorrelativeScanMatcherOptions3D options_
PrecomputationGrid3D ConvertToPrecomputationGrid(const HybridGrid &hybrid_grid)
const HybridGrid *const low_resolution_hybrid_grid_
const int linear_z_window_size
_Unique_if< T >::_Single_object make_unique(Args &&... args)
std::function< float(const transform::Rigid3f &)> CreateLowResolutionMatcher(const HybridGrid *low_resolution_grid, const sensor::PointCloud *points)
std::vector< PrecomputationGrid3D > precomputation_grids_
int RoundToInt(const float x)
transform::Rigid3f GetPoseFromCandidate(const std::vector< DiscreteScan3D > &discrete_scans, const Candidate3D &candidate) const
const double angular_search_window
std::unique_ptr< PrecomputationGridStack3D > precomputation_grid_stack_
const int width_in_voxels_
std::unique_ptr< Result > MatchWithSearchParameters(const SearchParameters &search_parameters, const transform::Rigid3f &global_node_pose, const transform::Rigid3f &global_submap_pose, const sensor::PointCloud &point_cloud, const Eigen::VectorXf &rotational_scan_matcher_histogram, const Eigen::Quaterniond &gravity_alignment, float min_score) const
float low_resolution_score
constexpr T Power(T base, int exponent)
FastCorrelativeScanMatcher3D(const HybridGrid &hybrid_grid, const HybridGrid *low_resolution_hybrid_grid, const std::vector< TrajectoryNode > &nodes, const proto::FastCorrelativeScanMatcherOptions3D &options)
const MatchingFunction *const low_resolution_matcher
static Candidate3D Unsuccessful()
double GetDouble(const std::string &key)
Eigen::Quaterniond gravity_alignment
std::unique_ptr< Result > Match(const transform::Rigid3d &global_node_pose, const transform::Rigid3d &global_submap_pose, const TrajectoryNode::Data &constant_data, float min_score) const
std::unique_ptr< Result > MatchFullSubmap(const Eigen::Quaterniond &global_node_rotation, const Eigen::Quaterniond &global_submap_rotation, const TrajectoryNode::Data &constant_data, float min_score) const
Candidate3D BranchAndBound(const SearchParameters &search_parameters, const std::vector< DiscreteScan3D > &discrete_scans, const std::vector< Candidate3D > &candidates, int candidate_depth, float min_score) const
static float ToProbability(float value)
proto::ProbabilityGridRangeDataInserterOptions2D options_
std::vector< float > Match(const Eigen::VectorXf &histogram, float initial_angle, const std::vector< float > &angles) const
const int linear_xy_window_size
Eigen::VectorXf rotational_scan_matcher_histogram
void ScoreCandidates(int depth, const std::vector< DiscreteScan3D > &discrete_scans, std::vector< Candidate3D > *const candidates) const
bool operator>(const Candidate3D &other) const
std::vector< Candidate3D > ComputeLowestResolutionCandidates(const SearchParameters &search_parameters, const std::vector< DiscreteScan3D > &discrete_scans) const
std::vector< Eigen::Vector3f > PointCloud
std::vector< Candidate3D > GenerateLowestResolutionCandidates(const SearchParameters &search_parameters, int num_discrete_scans) const
Eigen::Array3i GetCellIndex(const Eigen::Vector3f &point) const
std::vector< DiscreteScan3D > GenerateDiscreteScans(const SearchParameters &search_parameters, const sensor::PointCloud &point_cloud, const Eigen::VectorXf &rotational_scan_matcher_histogram, const Eigen::Quaterniond &gravity_alignment, const transform::Rigid3f &global_node_pose, const transform::Rigid3f &global_submap_pose) const
PrecomputationGrid3D PrecomputeGrid(const PrecomputationGrid3D &grid, const bool half_resolution, const Eigen::Array3i &shift)
RotationalScanMatcher rotational_scan_matcher_
proto::FastCorrelativeScanMatcherOptions3D CreateFastCorrelativeScanMatcherOptions3D(common::LuaParameterDictionary *const parameter_dictionary)
Candidate3D(const int scan_index, const Eigen::Array3i &offset)
bool operator<(const Candidate3D &other) const
~FastCorrelativeScanMatcher3D()
sensor::PointCloud low_resolution_point_cloud
std::vector< std::vector< Eigen::Array3i > > cell_indices_per_depth
DiscreteScan3D DiscretizeScan(const SearchParameters &search_parameters, const sensor::PointCloud &point_cloud, const transform::Rigid3f &pose, float rotational_score) const
int GetInt(const std::string &key)
PrecomputationGridStack3D(const HybridGrid &hybrid_grid, const proto::FastCorrelativeScanMatcherOptions3D &options)