{'fraction_non_alphanumeric': 0.032301537165719096, 'fraction_numerical': 0.009391450831754054, 'mean_word_length': 4.883548067393459, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Be your own Benchmark: No-Reference Trajectory Metric on Registered Point Clouds

This paper addresses the problem of assessing trajectory quality in conditions when no ground truth poses are available or when their accuracy is not enough for the specific task - for example, small-scale mapping in outdoor scenes. In our work, we propose a no-reference metric, Mutually Orthogonal Metric (MOM), that estimates the quality of the map from registered point clouds via the trajectory poses. MOM strongly correlates with full-reference trajectory metric Relative Pose Error, making it a trajectory benchmarking tool on setups where 3D sensing technologies are employed. We provide a mathematical foundation for such correlation and confirm it statistically in synthetic environments. Furthermore, since our metric uses a subset of points from mutually orthogonal surfaces, we provide an algorithm for the extraction of such subset and evaluate its performance in synthetic CARLA environment and on KITTI dataset. The code of the proposed metric is publicly available as pip-package.


I. INTRODUCTION
In the past years, the explosion of 3D technologies has spanned numerous research works and algorithms on odometry and SLAM, creating a demand for effective and universal ways to assess the quality of the trajectories produced by those algorithms. Unfortunately, the variety of algorithm use-cases and conditions is not always covered by wellknown and standard benchmarks [1]- [3] and requires hyperparameters tuning, evaluation, and comparison of algorithms on the collected target dataset.
High accurate trajectories are also important in the mapping domain -using them, one can aggregate small-scale maps from a set of registered sequential point clouds [4], [5] by using their estimated trajectory. For example, in the case of sparse point clouds from LiDAR, this allows obtaining a denser representation of the environment, increasing the level of scene understanding, such as feature extraction [6], [7], segmentation [8].
The most straightforward approach to estimate quality is to use full-reference metrics that need ground truth (GT) information and additional sensors to collect it: GT trajectory, obtained from GNSS/INS in outdoors [1] or Motion Capture system indoors [2], [3], or GT map obtained from high-resolution static LiDARs [9]. In addition to the high cost, those sensors also have their limitations: GNSS/INS is effective only on large-scale trajectories, either requires differential GPS, in a widespread KITTI odometry benchmark [1] as demonstrated in Fig. 1 -map aggregated from LiDAR point clouds using GT poses much more distorted than one produced by standard point2plane Iterative Closest Point (ICP) algorithm, which means imperfections of GNSS/INS GT in small-scale trajectories for outdoors. An alternative way to overcome these limitations is to apply a no-reference metric where the quality of the registered map and hence trajectory is estimated without GT by measuring the level of map "inconsistency" and "noise".
Existing quantitative metrics for aggregated maps [10]- [12] tackle this problem from a heuristic point of view without demonstrating a strong correlation of map-based metrics with trajectory-based metrics on different scenes and trajectories.
In this paper, we propose a no-reference trajectory metric MOM (Mutually Orthogonal Metric) that evaluates the quality of the trajectory via evaluating the map consistency from registered point clouds. MOM uses plane variance statistics on points from mutually orthogonal surfaces and hence strongly correlates with Relative Pose Error [13] common full-reference trajectory metric to measure local trajectory consistency. Thus, MOM provides an opportunity to benchmark trajectory quality without GT information for any positioning system with 3D sensing technologies available.
We provide a mathematical interpretation to demonstrate the foundation of MOM correlation with full-reference trajectory metric and present statistical experiments with Li-DAR point clouds in the CARLA simulator [14] on various scenes and trajectories. Because our method requires extraction of points from mutually orthogonal surfaces, we also propose an algorithm for such pre-processing and evaluate its effectiveness on real-life data from KITTI dataset scenes [1]. Fig. 1 illustrates that proposed map metric gives more objective values of aggregated map quality on KITTI dataset. The code of metrics, considered in this paper, is publicly available as pip-package 1 .
The contributions of this paper are as follows: • no-reference trajectory metric for registered point clouds that gives strong correlation with Relative Pose Error and requires 40-60 times fewer points of the map in comparison to previous works; • algorithm for extraction of points from mutually orthogonal subsets in point clouds; • pipeline for evaluation different map metrics.

II. RELATED WORK
The robotics, graphics, computer vision, and many other research communities have studied techniques to evaluate the quality of odometry and SLAM algorithms. The most representative ones are: metrics for trajectory quality, metrics for point cloud quality, and no-reference metrics lying at the intersection of the first two.
Trajectory-based metrics are the main tool for evaluating odometry and SLAM algorithms in robotics. This approach requires ground truth trajectories and it can be mainly divided into two concepts: metrics based on Absolute Pose Error (APE) [15], [16] -to evaluate global trajectory consistency, and metrics based on Relative Pose Error [13], [17] to evaluate local trajectory consistency. Among well-known odometry benchmarks the next metrics are used: the TUM dataset [3]  Point cloud-based metrics have been actively developing in the last ten years by the graphics community. The main purpose of such metrics is to evaluate algorithm quality in the tasks of dense point cloud compression (down-sampling) and denoising. To evaluate metric quality, authors use collected benchmarks [19] from the subjective estimation of different point clouds' quality and estimate the correlation of proposed metrics using the Pearson correlation coefficient [20]. Among these approaches, the next metrics could be highlighted: point2point metric, point2plane metric [21], angular similarity [22], projection-based methods [23], [24] or 3D-SSIM variants [25], [26].
Map-based metrics serve as a tool for estimation trajectory by evaluating the quality of the map from registered point clouds by odometry or SLAM algorithm. Because this method does not require a ground truth trajectory or map, it could be called no-reference. Mean Map Entropy (MME) and Mean Plane Variance (MPV) [10], [11] could be included in such class, providing statistics on average entropy and planarity for every point in the map and demonstrating their correlation in indoor with trajectory-based metrics on some examples. Our method belongs to this category.

III. BACKGROUND A. Relative Pose Error
To describe 3D poses of the trajectory, elements of the Special Euclidean group SE(3) are used: where R is a rotation matrix, an element of the group of rotations SO(3) and t = transl(T ) -translation. Let T gt = {T gt 1 , .., T gt N } be the set of ground truth poses and T est = {T est 1 , .., T est N } -poses estimated by some algorithm. Relative pose difference E ij is defined as: Then, different measures of E ij could be considered for relative pose difference -for translation and rotation part. We will refer to the translation part since it presents the most important challenge for odometry and SLAM algorithm.
Translation-based RPE will be considered for both 1D and 3D trajectories and will have the next forms. For 1D: For 3D: Finally, mean squared among all pairs of i and j is calculated:

B. No-reference metrics
This section describes the main no-reference metrics Mean Map Entropy (MME) and Mean Plane Variance (MPV) [10], [11] and provides a discussion of their effectiveness and boundary cases.
Mean Map Entropy H(P ) of aggregated map P = {p 1 , .., p N |p i ∈ R 3 } is based on the entropy h(p k ) of every point p k in some vicinity W (p k ) and is averaged among all points: where Σ(W (p k )) is the sample covariance of map points in a local vicinity W (p k ) of p k . The next expansion of h(p k ) illustrates that MME captures the "spread" of point vicinity from the map along different axis, where λ 1 , λ 2 , λ 3 -eigenvalues of Σ(W (p k )). Assuming a locally flat surface around p k , then the two major eigenvalues are of equal magnitude, proportional to the radius R of the vicinity and hence h(p k ) will depend only on λ min : Mean Plane Variance V (P ) assumes that the majority of points lie on the planar surface, then map distortions could be measured as plane errors. Vicinity W (p k ) of every point p k in the aggregated map P is fitted to a plane and the corresponding plane error v(p k ) is calculated and averaged for all map points. Since plane error is equal to minimum eigenvalue of sample covariance of W (p k ), MPV will also depend only on λ min .
Despite authors of [11] demonstrated correlation of this metric with trajectory errors on indoor scenes with ground truth trajectory captured by Motion Capture system, the scene setup depicted in Fig. 2 demonstrates the disadvantages of MME and MPV metrics in terms of correlation with trajectory error. The magnitude of shifts (red arrow) between a pair of point clouds is the same for top and down images, statistics collected from obtained maps will be differentthe top map will have less map-metric value because of less deviation along the right plane. Furthermore, if points are not balanced among the planes, the impact of the right notorthogonal plane will be even more. Statistically, this could be demonstrated with a synthetic environment in 3D, which contains three planes. For such a setup, we consider 200 perturbed trajectories, whose length is five poses. Then MME and MPV metrics are calculated for maps aggregated from perturbed trajectories as well as trajectory error is calculated between GT and perturbed trajectories. Finally, statistics for the following three configurations are collected: (i) three orthogonal planes with an equal number of points on every plane, (ii) three orthogonal planes with a different number of points on every plane, (iii) three non-orthogonal planes with an equal number of points on every plane. The collected statistics and corresponding correlation coefficients (Pearson [20], Spearman [27], and Kendall [28]) are depicted in Fig. 3 and numerically demonstrates degradation of correlation when points are notbalanced among planes and when planes are non-orthogonal.

IV. MAP-METRIC BASED ON ORTHOGONALITY
From the example depicted in Fig. 2 it could be noticed that considering only the first two mutually orthogonal planes removes such ambiguity in map metric because distortions in one direction don't affect distortion in others. The issue with not-balanced even orthogonal surfaces could be solved by considering every mutually orthogonal direction separately and averaging statistics along every direction. This section demonstrates how this intuition on using map statistics from mutually orthogonal surfaces could be extended to any  number of poses with some assumptions and proposes an algorithm for extracting points from mutually orthogonal surfaces from the point cloud.

A. No-reference metric based on orthogonality for translation shifts
Firstly, let us consider the next lemma which connects map-metric and trajectory metric (RPE).
Proof. Expanding Σ(A): Expanding RPE(A): Finally, the relation between those values does not depend on value of points from the original set A: Let us consider N shifted planes along direction n as depicted in the Fig. 4 with coordinates A = {a 1 , .., a N |a i ∈ R} with respect to n. In case when points are balanced among those planes, plane variance, which is actually λ min of covariance matrix in some vicinity, will be equal to Σ(A), and following lemma -equal to RPE along axis n.
Then, connection between RPE for 1D trajectory to RPE for 3D trajectory could be demonstrated. Proof. The next expansion demonstrates decomposition of RPE for 3D poses to sum of RPE for 1D along coordinate axis.  Fig. 4: Example of N planes shifted along axes n to demonstrate connection between Relative Pose Error for 1D and plane variance for set of points on those shifted planes.
where t 0 i , t 1 i , t 2 i define coordinates of translation vector t i , and t 0 = {t 0 1 , .., t 0 N |t 0 i ∈ R}, t 1 = {t 1 1 , .., t 1 N |t 1 i ∈ R}, t 2 = {t 2 1 , .., t 2 N |t 2 i ∈ R} -set of 1D poses along every coordinate axis. Rotation of coordinate system gives the same decomposition but along new coordinate axis, which means that any orthogonal basis could be chosen to measure RPE in terms of 1D decomposition.
Finally, connecting decomposition of 3D RPE in any orthogonal basis in 1D RPE (Lemma 2) and dependency between 1D RPE and plane variance (Lemma 1), map metric MOM (Mutually Orthogonal Metric) with interpretable correlation with trajectory metric could be defined in the next form.
1) Extract points that lie on mutually orthogonal surfaces, directions of those surfaces will present orthogonal basis for RPE decomposition. 2) Calculate mean plane variance of the map for every subset of points associated with one basis direction. 3) Average mean plane variance along three directions of orthogonal basis. Because any orthogonal basis could be chosen with respect to Lemma 2, it is desirable to choose such basis that will cover as maximum as possible elements of the map to gather more statistics.

B. Orthogonal subset extraction from point clouds
Following the discussion on statistics based on points from orthogonal surfaces, the problem is reduced to finding a maximum subset of points that lie on the orthogonal surfaces. Let N = {n i | n i ∈ R 3 , n i = 1} be a set of point cloud normals. The set we are interested in can be defined as a set where every pair of normals are either co-linear or orthogonal. Because all sensor measurements tend to produce noisy observations and hence noisy normals, we will consider a concept of nearly co-linear and nearly orthogonal vectors in some vicinity defined in the following way.
Definition IV.1 (Nearly co-linear). Let pair of unit vectors n i and n j be nearly co-linear in some vicinity if Definition IV.2 (Nearly orthogonal). Let pair of unit vectors n i and n j be nearly orthogonal in some vicinity if To gather more statistics from orthogonal surfaces, we are interested in the maximum subset of N where every pair of normals follows the property of nearly co-linearity or nearly orthogonality. This task could be formulated as a max clique problem on a graph G(N ) where normals are graph vertices, and every nearly co-linear or nearly orthogonal pair of vertices is connected via edge. Max clique problem is an NP-complete task which means that solving it for standard point cloud (>10k points) is not effective. To provide an effective solution, we do Agglomerative clustering of normals into nearly located normals with complete linkage criteria and then apply max clique search algorithm for the centers of obtained clusters (<100). Because several max cliques of clusters could be obtained, the max clique with the maximum amount of points in clique clusters is chosen to gather more statistics. Example on Fig. 5 demonstrates such orthogonal subset for KITTI point cloud extracted using the described algorithm. Grey-colored points are the whole KITTI point cloud; red, green, and blue depict points related to mutually orthogonal surfaces.

C. MOM on Degenerate cases
For correlation with trajectory error, our metric requires to have at least three mutually orthogonal surfaces on the scene. Usually, this condition is satisfied in many environments: indoors (apartments, offices), outdoors (urban environments). In case when three mutually orthogonal surfaces are not available, statistics on the available amount of directions could be used -it will still give a measure of map inconsistency that could be used to evaluate the algorithm, but without strong correlation with the trajectory error.

V. EXPERIMENTS
The experiments section is divided into two parts: evaluating metrics quality in synthetic environments with ground truth poses available and evaluation algorithm for orthogonal subset extraction on real-life data (KITTI dataset).

A. Synthetic environment
Synthetic environments allow obtaining ground truth information about point cloud poses along the trajectory and hence estimate the quality of correlation with trajectory error. In this part of the work, we consider two types of synthetic environments: (i) environment with randomly generated configurations of synthetic planes, mainly because discussed metrics rely on this property of environment, (ii) outdoor simulator CARLA [14] with generated LiDAR point clouds for different city maps and trajectories.
To evaluate metric quality, the next pipeline is used: 1) a sequence of point clouds and corresponding ground truth poses T gt are generated; 2) ground truth trajectory is perturbed to obtain T est : for plane environment perturbation of only translation part is used to follow lemma conditions, for CARLA scenes both rotation and translation parts are perturbed; 3) the full-reference metric (RPE) is calculated for the pair of trajectories (T gt , T est ); 4) the no-reference metric is calculated for the map aggregated from point clouds with perturbed trajectory; 5) after sampling 200 perturbed trajectories, a linear correlation and monotonic correlation between fullreference and no-reference metric are calculated using Pearson [20], Spearman [27], and Kendall [28] statistics.
The next metrics were considered for evaluation: • MME -original Mean Map Entropy [11]; • MPV -original Mean Plane Variance [11]; • OMME -Mean Map Entropy on subset of mutually orthogonal surfaces (ours), following discussion on it dependency from plane variance in Sec. III-B; • MOM -Mean Plane Variance on subset of mutually orthogonal surfaces (ours). 1) Synthetic planes: Because the main assumption made in the metric proposals is that environments mainly contain planar surfaces, firstly, we consider the synthetic environment that contains only planes. The purpose of this is to evaluate the stability of considered metrics on different sets of planes, taking into account the problem of non-orthogonal cases and unbalanced number of points.
To generate different configurations of such an environment, the next process was proposed. First, we generate normals for planes: they contain three fixed orthogonal normals, count of other planes are sampled uniformly from [0, 7], normals for those additional planes are sampled uniformly by the uniform sampling of θ from [0, 2π) and φ from [0, π) and obtaining normal from the formula: Secondly, displacement from the origin is generated for every plane in the range [−10, 10] for every coordinate axis avoiding cases of plane intersections. Also, the density of every plane is sampled uniformly from the range [30, 100] per 1 m 2 .
This configuration provides orientation and translation of all planes from the origin as well as their density. For every pose, we uniformly sample points on those planes in radius 1 m 2 .
For experiments, 50 environments were generated. For every environment, trajectories of length [5; 15; 30] were evaluated using the described pipeline.
Results of evaluation are presented on Fig. 6 (a). They demonstrate that usage of orthogonal subsets increases the quality of metric for every correlation coefficient, and orthogonal-based metrics achieve maximum value equal to 1 of the correlation coefficient. Also, high Pearson correlation demonstrates that MOM provides linear correlation with Relative Pose Error that gives more preference to its usage as no-reference map metric with strong dependence with trajectory error. This behavior could be explained by linear dependency between covariance along axis (which is actually a plane variance along plane normal) and RPE along this axis, demonstrated in Sec. IV-A. It could also be noticed, that all correlation coefficients grow with respect to number of poses in the trajectory. This behavior could be explained by the fact of obtaining a denser point cloud in the resulting map, that provides more information on point cloud consistency and errors in trajectory.
2) CARLA simulator: The CARLA simulator was used to generate outdoor LiDAR point clouds and corresponding sensor ground truth trajectories to evaluate metrics on environments with a richer structure. Compared to other simulators and datasets that support LiDAR generating (Pre-SIL [29], Mai City Dataset), CARLA satisfies all the next requirements: 360 degrees of rotation, different outdoor environments, configurable types of LiDAR.
Following main sampling pipeline we obtained the next results depicted in Fig. 6. For all trajectories the trend of orthogonal subset affection remains the same as in synthetic planes dataset -OMME and MOM outperform their ancestors, proving reliability of orthogonal-based approach in correlation with trajectory error. Among OMME and MOM, MOM provides better linear correlation, as demonstrated in Pearson statistics.

B. Real environment
To demonstrate that the algorithm for orthogonal subset extraction is suitable in real-life scenarios, especially outdoors, where ground truth poses are usually noisy for smallscale mapping, we evaluate it on urban KITTI maps (00, 05, 06, 07) [1]. Correct orthogonal subset extraction was visually assessed on every 100 point cloud in those sequences. Also, statistics on the amount of extracted points in orthogonal subsets were calculated and is depicted in Fig. 7. Statistics demonstrate that not more than 2k points are extracted from the original KITTI point cloud (>120k points), which means that MOM requires 60 times fewer points in comparison to its ancestors, speeding up metric calculations.

C. Quality of KITTI odometry benchmark
The proposed map metric could be used not only as an independent tool for trajectory and aggregated map quality assessment when GT is not available, but also as a tool for filtering out weak parts of benchmarks that have GT poses. Such an example is demonstrated in Fig. 8, where MOM is calculated for every ten consecutive poses of the KITTI map providing information on how reliable are GT poses for different parts of the trajectory. Some parts of the map have low map consistency that means that GT poses are potentially not so accurate, that could lead to incorrect interpretation of odometry results on those parts of the trajectory.

VI. CONCLUSION
This paper has presented a no-reference metric MOM for evaluating trajectory quality by assessing the map's quality from registered point clouds via trajectory poses. Our metric employs map points from mutually orthogonal surfaces, thereby providing a strong correlation with full-reference trajectory error in comparison to previous works, and requires 40-60 times fewer points of the map for evaluation. In our work, we have proposed a mathematical interpretation of this correlation under some assumptions. Also, we have conducted statistical experiments in two synthetic environments, including the CARLA simulator that offers close to real-life outdoor scenes and LiDAR point clouds collection. Finally, since our metric requires points from mutually orthogonal surfaces, we developed an algorithm for their extraction from point clouds and evaluated its' performance on KITTI urban scenes.