Accurate Point Cloud Registration with Robust Optimal Transport
Authors: Zhengyang Shen
Jean Feydy
Peirong Liu
Ariel Hernán Curiale
Ruben San Jose Estepar
Raul San Jose Estepar
Marc Niethammer
Venue: NeurIPS 2021 Poster (2021)
Keywords: optimal transport
point cloud registration
feature matching
deep learning

Abstract: This work investigates the use of robust optimal transport (OT) for shape matching. Specifically, we show that recent OT solvers improve both optimization-based and deep learning methods for point cloud registration, boosting accuracy at an affordable computational cost. This manuscript starts with a practical overview of modern OT theory. We then provide solutions to the main difficulties in using this framework for shape matching. Finally, we showcase the performance of transport-enhanced registration models on a wide range of challenging tasks: rigid registration for partial shapes; scene flow estimation on the Kitti dataset; and nonparametric registration of lung vascular trees between inspiration and expiration. Our OT-based methods achieve state-of-the-art results on Kitti and for the challenging lung registration task, both in terms of accuracy and scalability. We also release PVT1010, a new public dataset of 1,010 pairs of lung vascular trees with densely sampled points. This dataset provides a challenging use case for point cloud registration algorithms with highly complex shapes and deformations. Our work demonstrates that robust OT enables fast pre-alignment and fine-tuning for a wide range of registration models, thereby providing a new key method for the computer vision toolbox. Our code and dataset are available online at: https://github.com/uncbiag/robot.

Accurate Point Cloud Registration with Robust Optimal Transport
Zhengyang Shen" UNC Chapel Hill zyshen@es.. enc
Jean Feydy" Imperial College London jfeydy0ic.ac.oo
Peirong Liu
UNC Chapel Hill peirongDcs. unc. edu
Ariel Hernán Curiale
Ruben San José Estépar Harvard Medical School
Raúl San José Estépar
Harvard Medical School acur acuriale waweewwh. harvard. edu
Harvard Medical School
harvard edu
r jjosst@bbh harvard. edu
Mare Niethammer
UNC Chapel Hill mnêcs. unc. edu
Abstract
This work investigates the use of robust optimal transport (OT) for shape matching. Specifically, we show that recent OT solvers improve both optimization-bun based and deep learning methods for point cloud registration. boosting accuracy affordable computational cost. This manuscript starts with a practical overview of modern OT theory. We then provide solutions to the main difficulties in ing this framework for shape matching. Finally, we showcase the performance of transport-enhanced registration models rigid registration for partial shapes; scene flow estimation on the Kitti dataset; and nonparametric registration of lung vaseular trees between inspiration and expira- tion. Our OT-based methods achieve state-of-the-art results on Kitti and for the challenging lung registration task, both in terms of accuracy and scalability.
wide range of challenging tasks:
We also release PVT1010, a new public dataset of 1,010 pairs of lung vascular trees with densely sampled points. This dataset provides a challenging use case for point cloud registration algorithms with highly complex shapes and deformations. Our work demonstrates that robust OT enables fast pre-alignment and fine-tuning for wide range of registration models, thereby providing new key method for the computer vision toolbox. Our code and dataset are available online https:///iithu: httpa///....omuccaa///ooooo
Introduction
Shape registration is a fundamental but difficult problem in computer vision. The task to determine plausible spatial correspondences between pairs of shapes, with cases that range from pose estimation for noisy point clouds 144 to the nonparametric registration of high-resolution medical images [77] As illustrated in Fig. T most existing approaches to this problem consist of combination of three steps, possibly fused together by some deep learning (DL) methods: (1) feature extraction: (2) feature matching; and (3) regularization using class of acceptable transformations that is specified through a parametric or nonparametric model. This work discusses how tools derived from
Equal Contribution.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

optimal transport (OT) theory [87 can improve the second step of this pipeline (feature matching) on challenging problems. To put these results in context. we first present an overview of related methods.
1. Feature extraction. To establish spatial correspondences, one first computes descriptive local features. When dealing with (possibly annotated) point clouds, simple choice is to rely on Cartesian coordinates (z, y, =) [3 26]. Going further, stronger descriptors capture local geometric and topo- logical properties: examples include shape orientation and curvatures [2] 96], shape contexts (6] spectral eigenvalues [84 7 and annotations such as color [76] or chemical fingerprints 43
Recently, expressive feature representations have also been learned using deep neural networks (DNN): see [16] and subsequent works on geometric deep learning. Generally, feature extractors are designed to make shape registration as unambiguous as possible. In order to get closer to the ideal case of landmark matching [IT], we associate discriminative features to the salient points of our shapes: this increases the robustness of the subsequent matching and regularization steps.
2. Feature matching. Once computed on both of the source and target shapes, feature vectors are put in correspondence with each other. This assignment is often encoded as an explicit mapping between the two shapes; alternatively, the vector field relating the shapes can be defined implicitly as the gradient of a geometric loss function that quantifies discrepancies between two distributions of features (35]:
a) A first major approach is to rely on nearest neighbor projections and the related chamfer 12 and Hausdorff distances [13], as in the Iterative Closest Point (ICP) algorithm [7]. This method can be softened through the use of softmax (log-sum-exp operator as in the
many variants of the Coherent Point Drift (CPD) method [81 73 72 44 made robust to
outliers in the specific context of rigid and affine registrations
128 14].
b) Alternatively, a second approach is rely on convolutional kernel norms such as the Energy Distance [94]. which are also known as Maximum Mean Discrepancies (MMD) in statistics 48). These loss functions are common imaging science 88 and computational
anatomy 115 21
but are prone to vanishing gradients 44 39.
c) Finally, a third type of approach is to rely on optimal transport (OT) theory
87 and
solutions of the earth mover's 'ss problem 197]. This method is equivalent a nearest neighbor projection under a global constraint of bijectivity that enforces consistency in the matching. On the one hand, OT has been known provide reliable correspondences in computer vision for more than two decades 226] 47 64). On the other hand, it has often faced major issues of scalability and robustness to outliers on noisy data. As detailed below, the main purpose of this work is to overcome these limitations and enable the widespread use of OT tools for challenging registration problems.
3. Regularization with a deformation model. The output of the two steps above is a non-smooth vector field that may not be suitable for downstream tasks due to e.g. tears and compression artifacts.
As third step, most registration methods thus rely on regularization to obtain plausible deformations.
This process is task-specific, with applications that range from rigid registration [33 46 30 2 121
122] to free-form motion estimation [91]22 69 49 In Sec. 3 we address the interaction of OT matching layers with a varied collection of regularization strategies from optimization-ben based spline and diffeomorphic models to DNNs.
Recent progresses. Research works on shape registration combine ideas from the three paragraphs above to best fit the characteristics of computer vision problems [1 [07]. Over the past few years, significant progress has been made on all fronts. On the one hand, (geometric) deep learning networks have been used to define data-driven feature maps 992 992 124] and multiscale regularization modules
[166] 68 [08], sometimes fused within end-to-end architectures [133 91 132 (3). On the other hand, nearest neighbor projections, kernel convolutions and transport-based matching strategies have all been generalized to take advantage of these modern descriptors: they can now be used in
high-dimensional feature spaces [59 371
Nevertheless, state-of-the-a (SOTA) methods in the field still have important limitations. First, modern deep learning pipelines are often hard to train to "pixel-perfect" accuracy on non- smooth shapes, with diminishing returns terms of model size and training data (2). Second, scaling up point neural networks to finely sampled shapes (N > 10k points) remains challenging research topic [49] 135. 37). Third, the impact of the choice of specific feature matching method on the performance of deep learning models remains only partially understood [58).
Challenges.

---

Fig.
U
(a) Source and target points dimension
(b) Source and target frames, sampled with 30k points each.
(c) Exhale and inhale trees, sampled with 60k points each.
Figure 1: Robust Optimal Transport (RobOT) generalizes sorting spaces of dimension D > 1. (a) RobOT is equivalent to a nearest neighbor projection subject to mass distribution constraints that make it robust translations and small deformation. We demonstrate that RobOT is now ready to be part of the standard toolbox in computer vision with extensive numerical experiments for 3D scene flow estimation (b) and lung registration (c). Rendering done with Paraview [ and Vysis 112
Related works. Following major progress computational OT in the mathematical literature [79 27 [03], improved modules for feature matching have attracted interest as a possible solution to these challenges. Works on sliced partial OT [9] and dustbin-OT (28) have shown that outliers can handled effectively by OT methods for rigid registration, beyond the classic Robust Point Matching method (RPM) [47 [26). Going further, the Sinkhorn algorithm for -eeropy-regularizedd (65) has been studied extensively for shape registration computational anatomy The Chomov-Wassensee
OT 12
64
104
distance has also been used for shape analysis [110 [18], albeit at a higher computational cost. These applications have driven interest in the development of complete theory for Robust Optimal Transport (RobOT),
36
45
and computer graphics [74 33 85).
outlined in Sec. 2 which handles both sampling artifacts and outliers 25, 105 67 24 106, 80). Most recently, this framework has started to be used in shape analysis with applications shape matching [3), the segmentation of brain tractograms architecture [91].
38
and deep deformation estimation with the FLOT
Contributions. We build upon the work above to tackle challenging point cloud registration problems for scene flow estimation and computational anatomy. Our key contributions are:
1. Accurate feature matching with scalable OT solvers. For the first time, scale up RobOT for deep feature matching to high-resolution shapes with more than 10k points. To this end, we leverage the latest generation of OT solvers (39 35 and overcome significant issues of memory usage and numerical stability. This allows us to handle fine mee-grained details effectively, which is key for e.g. most medical applications.
2. Interaction with task-specific regularization strategies. We show how to interface RobOT matchings with advanced deformation models. This is in contrast with e.g. the FLOT architecture, which focuses on the direct prediction of a vector field and cannot be used for applications that require guarantees the smoothness of the registration.
3. Challenging new dataset. We release a large dataset of lung vascular trees that should be registered between inhalation and exhalation. This relevant medical problem involves large and complex deformations of high-resolution 3D point clouds. As a new benchmark for the community, provide two strong baselines that rely respectively global feature matching and on deep deformation estimation.
4. Consistent SOTA performance. Our proposed models achieve SOTA results for scene flow on Kitti 778 77 and for point-cloud based lung registration
-elLab- [19]. Notably, we show that RobOT is highly suited to fine-tuning tasks: it consistently turns "good" matchings into nearly perfect registrations at an affordable numerical cost.
Main experimental observations. Is OT relevant in the deep learning era? To answer this question decisively, we perform extensive numerical experiments and ablation studies. We fully document "underwhelming" results in the Supplementary Material and distill the key lessons that we learned in the Robp-RobOT architecture (Section 3.2). This model relies on fast RobOT layers to cover for main weaknesses of point neural networks for shape registration. It is remarkably easy to deploy and generalizes well from synthetic training data to real test samples. We thus believe that will have stimulating impact on both of the computer vision and medical imaging literature.

---

2 Robust optimal transport
This section introduces the mathematical foundations of our work. After a brief overview of Robust Optimal Transport (RobOT) theory, we discuss the main challenges that one encounters when using this framework for computer vision. To avoid memory overflows and numerical stability issues, we introduce the weighted "RobOT matching": vector field that summarizes the information of full transport plan with a linear memory footprint, As detailed the next sections, this representation lets us scale up to high-resolution shapes without compromising on accuracy.
2.1 Mathematical background
The assignment problem. A = (ZI,..., IN) and = (y1....,,,, (9M) are two point clouds in R² with N M, the assignment problem between A and B reads:
B)
min
a0 lo where is permutation.
s: =:IL -IN 2N
This problem generalizes sorting to R if the points I; and y all belong to a line, the optimal permutation s" corresponds to a non-decreasing re-ordering of the point sets A and B (87).
Robust optimal transport. Further, OT theory allows us to consider problems where N * M. Non-negative weights ai,,...: ON, $1...., PM 2 are attached the points Ty, Yy and account for variations of the sampling densities, while feature vectors P1..... PN and 9i..... 9M in Rp may advantageously replace raw point coordinates I; and yj in R Following (251, the robust OT problem between the shapes A (a,, Pi) and B (3 U3.9. qz) reads:
(A,
min (ER
ΣΣ
HIP:: - 4i l
i=1 i= 5=1
o² OKKL( as 2 B3),
r KL (I, Tty al.))
+ 7" KL E, mc
Entropic blur scale iT.
should match A...
ontoono B.
for any choice of the regularization parameters a and T 0. In the equation above, the Kullback-Lebler divergence KL (a,llb,) = Σ a log (a./b.) - ag + b; is a relative entropy that penalizes deviations of non-negative vector weights (a,) to reference measure (b.).
Parameters. The first regularization term is scaled by the square of a blur radius This charac- teristic length quantifies the fuzziness of the probabilistic assignment (x,,) between points x; and y; [35] The last two regularization terms promote the matching of the full distribution of points A onto the target shape B: they generalize the constraints of injectivity and surjectivity probabilistic setting. They are scaled by the square of maximum reach distance т: this parameter acts as soft upper bound on the distance between feature vectors pt and Oj that should be matched with each other [38 [05).
Eq. ① to the
For shape registration, we use simple heuristics for the values of these two characteristic scales: the blur a should be equal to the average sampling distance in feature space ID while the reach should be equal the largest plausible displacement for any given feature vector Pt. These rules are easy to follow if point features correspond to Cartesian coordinates and yj in R3 but may lead to unexpected behaviors if features are output by a DNN. In the latter case, we thus normalize our feature vectors that ||: I| = [| I = 1 and pick values for and 7 between 0 and 2.
Working with a soft, probabilistic transport plan. As detailed in 35 scalable OT solvers for Eq. (2) return a pair of dual vectors (fi) E R and (g,) RBM that encode implicitly an optimal transport plan (Ii,)) E NxM with coefficients:
mh
343,
exp + [f: + + -lpp 9 [ 0.
In the limit case where tends to 0 and 7 tends to +0x, for generic point clouds (ar;) and (31) with N = M and equal weights a; = B3 1/N, Ti. is a permutation matrix [87]. We retrieve the simple

---

assignment problem of Eq. T Taj = 1/N = (t) and 0 otherwise. However, in general the probabilisticc map between the point distributions and B that
transport plan must be understood assigns weight zij to the coupling "x; <> y/ For shape registration, this implies that the main difficulties for using robust OT are two-fold: first, the coupling x is not one-to-one, but one-to-many; second, the lines and columns of the transport plan do not sum up to one. Notably, this implies that when T < +oo, the gradient of the OT cost with respect to the point positions z; is not homogeneous: we observe vanishing and inflated values across the domain [105.
2.2 RobOT: a convenient representation of the optimal transport plan
The weighted RobOT matching.
To work around these issues, introduce the vector field:
1= Ti.j (Uj
vi)) E
U/-
R
with confidence weights wi
Σ
T
(4)
ΣØ= Tij
This object has the same memory footprint as the input shape A and summarizes the information that is contained in the N-by-M transport plan (ma.g) - matrix that is often too large to be stored and manipulated efficiently. This "weighted RobOT matching" is at the heart of our approach and generalizes the standard Monge map from classical OT theory [87] to the setting of (deep) shape registration. In practice, the weighted vector field (w1,71).-. (WN, UN) is both convenient to use and easy to compute on GPUs. Let us briefly explain why.
Fast implementation. Our differentiable RobOT layer takes as input the two shapes A (os, P:) and B (3,, Vj. Uj.g;), with feature vectors pi and qj in RD that have been computed upstream using e.g. a point neural network. It returns the N vectors U, with weights w, that map the source points z; onto the targets y,, in R Starting from the input point features pt. qj and weights a,, 3r, we first compute the optimal dual vectors ft and g, using the fast solvers of the GeomLoss library [39]. We then combine Eq. (3) with Eq. 4 to compute the RobOT vectors v; and weights w. with
O(N + M) memory footprint using the KeOps library 220 37 for Py PyTorch [86] and NumPy [17].
We use log-sum sum-exp formulation to ensure numerical stability. Remarkably, our implementation scales up to N, M = 100k in fractions of a second. Unlike common strategies that are based on dense or sparse representations of the transport plan म, our approach is perfectly suited to symbolic implementation 337 and streams well on GPUs with optimal, contiguous memory accesses.
Comparison with nearest neighbor projections. We use our RobOT layer as plug-in replace- ment for closest point matching (7]. The blur (a) and reach (r) scales play similar roles to the standard deviation (o)) and weight of the uniform distribution (w) in the Coherent Point Drift (CPD) method [8I]: they allow us to smooth the matching in order to increase robustness to sampling artifacts.
The main difference between projection- matching and RobOT is that the latter enforces a mass distribution constraint between the source and the target. This prevents our matching vectors from accumulating on the boundaries of the distributions of point features (PI,-... PN) and (qi,..., (M) in R.D [40]. This property is most desirable when the shapes to register are fully observed, with dense sampling: as detailed in Suppl. A.5] enforcing the global consistency of a matching is then a worthwhile registration prior.
Partial registration. On the other hand, we must also stress that OT theory has known limitations 35). First of all, the RobOT matching cannot guarantee the preservation of remarkable points or of the shapes' topologies "on its own": it should be combined with relevant feature extractors and regularizers. Going further, partial registration is not natural fit for standard OT formulations which assume that all points from both shapes must be put in correspondence with each other.
To mitigate this issue, RobOT leverages the theory of unbalanced optimal transport 25 [06]: we rely on saft Kullback- Leibber penalties to enforce a matching between the shapes A and B in Eq. (2). In practice, the RobOT confidence weights w; of Eq. (4) act as attention mechanism: they vanish when no target feature vector 1j can be found in a n-neihhborhood of the source vector p; in RD. where 7 the reach scale that is associated to Eq. 2 This lets our registration method focus on reliable matches between similar features, without being fooled by strong constraints of bijectivity. As detailed in Suppl. A.3 combining standard FPFH features (T00 with the rigid projection of Eq. 5 allows us to register partially observed shapes that have little overlap with each other.
105 67
24
5

---

3 Regularization and integration with a deep learning model
3.1 Smooth-RobOT: algebraic and optimization-based regularization
Notations. We now detail how to interface the weighted RobOT matching with regularization models and feature extractors that may be handcrafted [114 101 100] or learnt using a deep neural network [133 46
30 29]. Recall that we intend to register a source point cloud T1...., 2N onto a target ya,..... UM in R Non-negative weights 01;-.-; ON and ...... PM e 0 let us take into account variations in the sampling densities and we assume that point features .I..... ,N. ....... QM in IR have been computed upstream by a relevant feature extractor. For every source point 2;, the RobOT matching layer then provides a desired displacement v; in IR' with influence weight we; > 0.
Smoothing in closed form. Standard computations let us derive closed-form expressions for rigid and affine registration [57] [1. These respectively correspond to transformations:
(Rigid RobOT)
JF E + (x - xx) UVT
+ + Uo E R3
(5)
(Affine RobOT)
x E
(x- xe) (X WX) WY) + U R
where W Diag(w;) E NNN is the diagonal matrix of influence weights, 2e = = E, w,x:// E, Wi I is the barycenter of the source shape, ve Σ, w,ys/ Σ, w. E R3 is the average desired displacement, X = (2; - Iz) E IR is the centered matrix of source positions, 02 H. v.) E RRx3 is the centered matrix of desired targets and USV is the singular value decomposition of XTWY E TR333 This corresponds to a weighted Kabsch algorithm [60] Likewise, implement free-form spline registration using the KeOps library [37 20 A Badaraya-Watsee interpolator with kernel k: (x, E RR
(æ,
x R2 + k(I v) O 82 124 induces a transformation:
(Spline RobOT)
R x Zi=1 (,, / Σ wyk(2;; R
Black-box deformation models. Going further, we interface RobOT matchings with arbitrary deformation modules Morph 24) + Di E RR' parameterized by a vector 0 in R If Reg(O) denotes regularization penalty on the parameter @ (e.g. squared Euclidean norm), we use standard optimizers such as L-BFGS-B [136] and Adam [63] find the optimal deformation parameter:
6 arg min Reg(O)= + Σ 1= wi ||;
+ 8; - Morph(0, (0,x;)) 133
(8)
OER
This optimization- based method is especially relevant in the context of computational anatomy, where smooth and invertible deformations are commonly defined through the Large Deformation Diffeo- morphic Metric Mapping (LDDMM) framework [5] 8 35]. We stress that different transformation models may result in different registration results and refer to Suppl. A.3 for further details.
Optimization-basee approaches provide strong geometric guarantees on the final matching. But unfortunately, these often come high computational price: to register complex shapes, quasi- Newton optimizers require dozens of evaluations of the deformation model Morph ()) and of its gradients. In practice, fitting complex model to pair of high-resolution shapes may thus take several minutes or seconds [1 This precludes real-time processing and hinders research on advanced deformation models.
3.2 Meep-RobO11 registration via deep deformation prediction
Deformation prediction. In this context, there growing interest in fast learning methods that avoid the use of iterative optimizers. The idea is to train deep neural network Pred (Ia, Mj) - 0 that takes as input two point clouds A = (FI...., IN). B = (y1..... .MM) and directly predicts the optimal vector of parameters 0 for transformation model Morph(0, .) that should map A onto B. Assuming that the prediction network Pred has been trained properly, this strategy enables real-time processing while leveraging the task-specific geometric priors that are encoded within the deformation model.
Over the last few years, numerous authors have worked in this direction for rigid registration 133 46
30 2 121 [22 and scene flow estimation [91] 126
69 49 Comparable research on diffeomorphic models has focused on images that are supported on dense grid, with successful applications to e.g. the registration of 3D brain volumes [31 107) As of 2021, prediction- approaches have
thus become standard methods for 3D shape registration.

---

1. Affine-RoOT pre-alignment.
0
2.a. Deep prediction network.
End- to-end training on synthetic pairs.
Local deformation. deformation.
2.b. Smooth deformation model.
3. Spline-RobOT post-processing.
Real souree.
Syuthetic target.
We apply three successive registration modules that bring the moving source shape increasingly close to the fixed target point cloud. On the one hand, the RobOT-basee features and do not require any training. On the other hand, our deep registrationn module (2) relies on a multi-scale point neural network "Pred (x) + 0" (2.a) and a task-specific deformation model "Morph(O, -;)) + Di" (2.b). We train it end-to-end on dataset of synthetic pairs of shapes with known ground truth correspondences. Right: To generate these pairs, we apply random deformations to real source shapes. For lung registration. we apply successively vessel-preserving local perturbation and a smooth global deformation as detailed Suppl. A.2
Figure 2:
The D-RobOT architecture. Left:
pre-alignment (1) and fine-tuning (3) steps take the (a. y, 2) coordinates as input
The D-RobOT model. practice though, prediction methods still face three major challenges:
1. Common architectures may not be equivariant to rigid or affine transformations.
2. Dense 3D annotation is expensive, especially in medical context. As consequence, most predictors are trained on synthetic data and have to overcome a sizeable domain gap.
3. Predicted registrations may be less accurate than optimization-baase solutions. Training registration networks to pixel-perfect accuracy is notoriously hard, with diminishing returns in terms of model size and number of training samples.
We propose to address these issues using RobOT layers for pre-alig alignment and post-processing. Our Deep RobOT (D-RobOT) model is end-to-end deep learning architecture that is made up of three consecutive steps that we illustrate in Figure 2 and detail Suppl. A..4
1. OT-based pre-alignment. We use the rigid or affine S-RobOT models of Eqs. normalize the pose of the source shape. This is a fast and differentiable pre preepesccssnng..
to
2. Deep registration module. We combine a deep predictor with task- deforma- tion model register
pre-aligned source onto the target. For the prediction network Pred (Ii, M + 0, we use multiscale point neural network that is adapted from the PointPWC-Net architecture [126]. We refer to Suppl. for a full description of our architecture and training loss.
3. OT-based propesrocss,ng. In order to reach "pixcl-perfect" accuracy, we use the spline S-RobOT deformation model of Eq. 7 with a task-specific kemnel k(2z, y).
Complementary strengths and weaknesses. We apply these three steps successively, which brings the moving source A = (I1,.... ΣN) increasingly close to the fixed target B = (V1..... DMa) Re- markably, each step of our method covers for the weaknesses of the other modules: the RobOT-based multiscale
pre-alignment makes pipeline robust to changes of the 3D acquisition parameters; neural predictor is able to match corresponding key points quickly, even complex situations; domain-specific deformation model acts regularizer and improves the generalization properties of the deep registration module; the RobOT-based fine-tuning improves accuracy and helps our model overcome the domain gap between synthetic and real shape data.
As detailed below, the D-RobOT model generalizes well outside of its training dataset and outperforms state-of tiite-ofttee of-the-art methods on several challenging problems. We see it as a pragmatic architecture for shape registration, which easy to deploy and tailor to domain- specific requirement requirements. As discussed in Suppl. A.4 we found that introducing sensible geometric priors through our RobOT layers and deformation model Morph (0, xx.) + ÿi results in a "forgiving" pipeline: our model produces accurate results, even when trained on synthetic data that is not very realistic. In a context where generating plausible 3D deformations easier than developing custom registration models for every single task (e.g. in computational anatomy), we believe that this is an important observation.
7

---

4 Scene flow estimation
Benchmark. We now evaluate our method on standard registration task in computer vision: the estimation of scene flow between two successive views of the same 3D scene. We follow the same experimental setting as in 126 49
with full details provided in Suppl. [A.4.3]
1. We train on the synthetic Flying3D dataset [75), which is made up of multiple moving objects that are sampled random from ShapeNet. We take 19,640 pairs of point clouds for training, with dense ground truth correspondences.
2. We evaluate on 142 scene pairs from Kitti, real-world dataset 78
We conduct experiments using 8,192 and 30k points per scan, sampled at random from the original data.
77
Performance metrics. We evaluate all methods in [26]: EPE3D is the average 3D eπror, in centimeters; Acc3DS is the percentage of points with 3D error < <m cm or relative error < 5%;; Acc3DR is the percentage of points with 3D error < 10 cm relative error 10%; Outliers3D is the percentage of points with 3D error > 30 cm or relative error > 10%; EPE2D is the average 2D error obtained by projecting the point clouds onto the image plane, measured in pixels; Acc2D is the percentage of points with 2D error < 3 px or relative error < 5%. As detailed in Suppl. A.6 all run times were measured on single GPU (24GB NVIDIA Quadro RTX 6000).
Methods. We study a wide range of methods and report the relevant metrics in Fig. In the upper third of the table, report results for unsupervised methods that do not require ground truth correspondences for training. This includes the "raw" RobOT matching of Eq. 4 computed
on (zz y, 2) coordinates in E with a blur scale also note that PWC refers to an improved version of PointPWC-Net, released on GitHub (https 7/github. cetthuu..cmm//a www.cccmmllll... Dww.ayyauweeeee PPontt/WoC after the publication of [166] with a self-super loss. In the central third of the table, we benchmark a collection of state-of of-the-art point neural networks. In the lower third of the table, study the influence of our RobOT-based layers. The methods "Pre + FLOT/PWC + Post" correspond to the FL.T and PointPWC-Net architectures, with the additional pre-alignment and post-processing modules of Sec. 3.2 The last lines correspond to the full D-RobOT architecture (with spline deformation model) whose training is detailed in Suppl. A.4.3
cm and reach scale
+30 Please
Results. We make three major observations:
1. Without any regularization or training, simple RobOT matching on high-resolution data outperforms many deep learning methods in terms of speed, memory footprint and accuracy (line of the table). This surprising result is strong evidence that geometric methods and baselines deserve more attention from the computer vision community.
2. the lower third of the table, RobOT-enhanced methods consistently outperform state- of-the-art methods by wide margin.
3. As shown in Fig. these improvements are most significant on high-resolution data.
Overall, as detailed in Suppl. A.4.3 and A.5 we observe that optimal transport theory is especially well suited scene flow estimation. Assuming that ground points have been removed from the 3D frames (as a standard pre-pree pee-rocesssin), most object displacements can be explained as translations and small rotations: this is an ideal setting for our robust geometric method.
Registration of high-resolution lung vessel trees
PVT1010: new dataset for lung registration. Going further, we introduce a new dataset of 1,010 pairs of pulmonary vessel trees that must be registered between expiration (source) and inspiration (target). Due to the intricate geometry of the lung vasculature and the complexity of the breathing motion, the registration of these shapes is a real challenge.
As detailed in Suppl. A.J we encode our 1,010 x 2 vessel trees as high-resolution 3D point clouds (N = M = 60k points per tree). For each point, we also provide a local estimate of the vessel radius that we use as an additional point feature or as a weight a; 33 in Eq. (2). Our first 1,000 pairs of 3D point clouds are provided without ground truth correspondences; for all of our experiments, we randomly sample 600 training and 100 validation cases from this large collection of unannotated patients. The last 10 cases correspond to the 10 DirLab COPDGene pairs [19]: they come with 300 expert-annotated 3D Jandmarks per lung pair, that we use to test our methods.
8

---

points 8k points
210
source (centered)
target
ground truch
RobOT (target)
D-RobOT (truth)
Figure 3: Influence of the sampling density on a detail (top car) of the Kitti frames of Fig. b First row: On sub-sampled 3D scenes, the regularizing priors of the D-RobOT architecture prevent over-fitring to the random sampling patterns of the target point cloud (blue). The D-RobOT output (last column, red) is very close the ground truth scene flow (green). Second row: Increasing the number points per frame reduces the influence of sampling artifacts. The simple RobOT baseline (fourth column, red) still over-fits the target (blue) but becomes remarkably competitive.
Prnnic
Momoey
AccIDS
OulllendD
+ ReePPWCPPel
ICP orgith
254
2
11.51
6.50
16.47
57. 12
27.075
10.56
11.11
77.61
13:264
1,000
PW
(15
35.09
33.39
49.57
68.63
3.9459
13.99
BobOT (ow)
RobOT (mwi
86
120
9.12
4.67
68.45
70.30
33.6
4.9920
56.23
750
PlouNact
RP
17.67
37.36
50.71
7.2141
$0.90
XTL.W Nm 131
19
21.74
53.51
05.25
8.300
41.50
Dingel
origisal
13
17:39
25.16
60.11
7.3476
44.11
Supresiaal
PAC [10
TT [1]
M
1.1
137
10/641
1,115
6.28
5.51
7.83
65.8%
75.79
50.55
$1.06
42:10
20.09
18:35
31976
3.3155
1.512
11.45
70.76
250
Piz IPWCI Post FLOT
D-RentTT
Pre BLOT
467
2,825
5.35
76.84
91.85
23.55
3.218h
75.31
RebOT
The PWC Piad
229
1,134
3.35
90.10
97:32
16.20
1,481
93.85
Pre PMC Post
306
1.307
10
3.40
90.04
56.71
17.28
5117
50.37
(ipline)
D-R:0OT
2.33
95.88
13.89
1.036
96.75
Figure Evaluation on the Kitti dataset for 3D scene flow. Black numbers and crosses (x) correspond to results on scene pairs that are sampled with 8,192 points per frame; red numbers and plus signs (++ correspond to scene pairs that are sampled with 30,000 points per frame.
(a) Source.
(b) Target.
(c) RobOT.
(d) S-RobOT and target.
(e) Deep features (source, target).
(f) After pre-alignment, target.
(g) After deep registration, target.
(h) After fino-tuning, target.
Figure 5: Registration lung vascular trees. First row: S-RobOT registration with the deep features of Suppl. A.3.3 We display: (a) the source and (b) target shapes; (c) the "raw" RobOT registration; (d) a smoother S-RobOT registration with spline regularization, an overlap of this result with the target shape; (e) visualization of the deep features colors that correspond to t-SNE embedding of the point features in color space [166.. Second row: D-RobOT registration. We display the successive steps of model: (f) pre-alignment with affine S- R-RobOT; (g) deep registration with an LDDMM model; (h) fine-tuning with spline S-RobOT.
pair of lung vascular trees, with

---

Table 1: 3D registration errors on the 3,000 expert-annotated DirLab landmarks. The sym- bol denotes methods that are based image keypoints [50|5] [1] and are evaluated on the original DirLab im-
Average
Percentiles
error
25%
50%
75%
Time
Method
No training
Input data
23.30
13.18
22.22
31.65
ICP (afline) ?
15.05
9.60
14.06
20.01
0.52
CPD (non-rigid) rigid)
81
9.30
5.95
8.60
11.83
332.60
RobOT (afline)
10:45
6.01
9.83
13.97
0.18
(ra))
9.41
13.04
age dataset; all other approaches are
DGCNNN-CPD
50
4.30
tested on our point clouds. Due to its large memory requirements, CPD is tested on clouds of 20k points (in- stead of 60k).
Supervised
DispEmml
3,2
S-RobOT (splinc)
5.72
3.19
5.04
7.35
2.77
S S-RabOT (LDDMM)
5.48
2.86
4.44
7.14
42.30
D-RobOT (raw)
3:40
1.40
2.58
3.69
1.26
D-RobOT (spline)
2.95
1.30
D-RobOT (LDDMM)
2,86
1.25
2.23
3.11
1.92
Data augmentation. The imbalance between our large training set and the small collection of 10 test cases reveals fundamental challenge in computational anatomy: annotating pairs of 3D medical shapes with dense correspondences is prohibitively expensive. To work around this problem, we train our networks on synthetic deformations of the 600 x 2 lung shapes that make up our training set. As detailed in Suppl. A.2, we use two-scales random field to generate wide variety of deformations. This allows to create suitable training set with dense "ground truth" correspondences.
Overall, as discussed in Suppl. A.4.22 we found that supervised training on synthetic deformations is both easier and more efficient than unsupervised training on real lung pairs. From the chamfer and Wasserstein distances [35] to local Laplacian penalties [266, none of the unsupervised loss functions that we experimented with was able to deal with the complex geometry of our lung vascular trees.
Methods. We benchmark a wide range of methods in Fig. 5 and Tab. I In the upper half of the table, we evaluate geometric approaches that require no training; in the lower half of the table, we benchmark scalable point neural networks that we trained on our synthetic dataset. We evaluate three types of RobOT-based approaches: a simple RobOT matching computed using (Ir, y. coordinates as point features, that may either be "raw" in Eq. (4) regularized using Eq. (6): an S-RobOT
matching that we compute using the deep features of Suppl. A.3.3 and regularize with the spline smoothing of Eq. (7) or the LDDMM optimization of Eq. (10 D-RobOT architecture that we pair with three deformation models Morph(O, xz) + Di and describe in depth in Suppl. A.4.2
Results. We provide additional experiments in Suppl. A.4.2 and make three major observations:
1. Explicit regularization with a spline or LDDMM deformation model key. Model-free architectures that predict raw 3D correspondences produce non-smooth results that are not anatomically plausible, even when they are trained entirely on smooth deformations.
2. The D-RobOT architecture combines high acccuracy with fast run times.
3. Most remaining errors occur at the boundary of the lungs, where acquisition artifacts prevent the thinnest vessels from being sampled reliably in our point cloud representation.
6 Conclusion, limitations and future work
Our work builds upon a decade of active research in the field of computational optimal transport. We leverage major advances on RobOT solvers to define and-play replacement for nearest neighbor projection. This operation has two major uses in 3D shape registration: first, it provides very strong geometric baseline for e.g. scene flow estimation; second, it increases the accuracy and generalization abilities of point neural networks on finely sampled 3D shapes. We D-RobOT as mature and versatile architecture for shape registration which is easy to train and adapt to task-specific requirements in e.g. medical imaging.
matching layer which is plug-
Going forward, in depth the important problem of occlusions and partial acquisitions. Second, integrating task- specific features beyond the v; 2) point coordinates is often key to perfect results. In the specific setting of lung registration, working with image- based features or focusing on branching points could be way of improving performance at the cost of portability: recent works such [52 53]
three main ways of improving this work. First, still have to investigate
an excellent source of inspiration. Finally, we believe that high-quality software packaging is an important part of research in our field. We intend keep working on the topic and distribute our methods through a user-friendly Python library for widespread use by the scientific community.
10

---

Acknowledgments and Disclosure of Funding
Research reported this publication was supported by the National Heart, Lung, and Blood Institute of the National Institutes of Health under award numbers R01HL149877 and RO1HL1 R01HL116473, The content solely the responsibilityy of the authors and does not necessarily represent the official views of the National Institutes of Health. The authors would also like to thank the anonymous reviewers for their most valuable advice.
References
[1] J. Ahrens, B. Geveci, and C. Law. Paraview: An end-user tool for large data visualization. The visualization handbook, 717(8), 2005.
[2] Y. Aoki, H. Goforth, R. A. Srivatsan, and S. Lucey. PointNetLK: Robust & efficient point cloud registration using PointNet. In Proceedings the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 7163-7177 7172,, 2019.
[3] K.S. Arun, T.S. Huang, and S. D. Blostein. Least-squares fitting of two 3-D point sets. IEEE Transactions on pattern analysis and machine intelligence, 5:698-700, 1987.
[4] Balakrishnan, Zhao, R. Sabuncu, J. Guttag, and A. Dalea. Voxelmorph: a learning framework for deformable medical image registration. IEEE transactions on medical imaging, 38(8): 188-10000,, 2019.
[5] M. Beg, M. I. Miller, A. Trouvé, and Younes. Computing large deformation metric mappings via geodesic flows of diffeomorphisms. International journaa of computer vision, 61(2):139-155 2005.
[6] S. Belongie, J. Malik, and J. Puzicha. Shape context: A new descriptor for shape matching and object recognition. Advances in neural information processing systems, 13:831-837. -37,, 2000.
[7] P.J. J. Besl and N. D. McKay. Method for registration of 3-D shapes. In Sensor fusion IV: control paradigms and data structures, volume 1611, pages 586-606. International Society for Optics and Photonics, 1992.
[8] A. Bône, M. Louis, Martin, and S. Durrleman. Deformetrica 4: open-source software for statistical shape analysis. In International Workshop Shape Medical Imaging, pages 3 13. Springer, 2018.
[9] N. Bonneel and D. Coeurjolly. SPOT: sliced partial optimal transport. ACM Transactions on Graphics (TOG), 18(4):1-13, 2019.
[10] L. Bookstein. Principal warps: Thin-plate splines and decomposition of deformations. IEEE Transactions on pattern analysis and machine intelligence, 1166):677-585, 1989.
[11] F. L. Bookstein. Morphometric tools landmark data: geometry and biology. Cambridge University Press, 1997.
[12] G. Borgefors. processing, 27(3):321-355, 1984.
Distance transformations in arbitrary dimensions. Computer vision, graphics, and image
[13] S. Bouaziz, A. Tagliasacchi. H. Li. and M. Pauly. Modern techniques and applications for real-time non-rigid registration. In SIGGRAPH ASIA 2016 Courses, pages 1-25. ACM Digital Library. 2016.
[14] S. Bouaziz, A. Tagliasacchi. and M. Pauly. Sparse iterative closest point. In Computer graphics forum, volume 32, pages 113-123. Wiley Online Library, 2013.
[15] Y. Brenier. Polar factorization and monotone rearrangement of vector-valued functions. Communications on pure and applied mathematics, 44(4):375-417, 1991.
[16] M. M. Bronstein, J. Bruna, LeCun, A. Szlam, and P. Vandergheynst. Geometric deep leamiigg going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
[17] M. Brunn, N. Himthani, Biros, M. Mchl, and A. Mang. Fast GPU 3D diffcomorphic image registration. Journal of Parallel and Distributed Computing, 149:1494 49:1149-62,, 2021.
[18] E. Castillo, R. Castillo, D. Fuentes, and T. Guerrero. Computing global minimizers to a constrained B-spline image registration problem from optimal LI perturbations to block match data. Medical physics, 41(4):041944, 2014.

---

[19] R. Castillo, E. Castillo, D. Fuentes, M. Ahmad, A. M. Wood. M. S. Ludwig, and T. Guerrero. A reference dataset for deformable image registration spatial accuracy evaluation using the COPDgene study archive. Physics in Medicine Biology, 58(9):2861, 2013.
[20] Charlier, J. Feydy, J. Glaunès, F.D. Collin, and Durif. Kernel operations on the GPU, with autodiff, without memory overflows. Journal of Machine Learning Research, 22(74):1-6, 2021.
[21] N. Charon and A. Trouvé. The varifold representation of nonoriented shapes for diffcomorphic registration. SIAM Journal on Imaging Sciences, 6(4):2547-2580, 2013.
[22] R. T. Q. Chen, B. Amos, and M. Nickel. Learning neural event functions for ordinary differential equations. International Conference on Learning Representations, 2021.
[23] R. T. Q. Chen, Y. Rubanova. J. Bettencourt, and D. Duvenaud. Neural ordinary differential equations. Advances in Neural Information Processing Systems, 2018.
[24] L. Chizat, G. Peyné, B. Schmitzer, and F--X. Vialard. Scaling algorithms for unbalanced optimal transport problems. Mathematics of Computation, 87(314);2563-6666 2018.
[25] L. Chizat, G. Peyré, B. Schmitzer, and F.-X. Vialard. Unbalanced optimal transport: Dynamic and Kantorovich formulations. Journal of Functional Analysis, 274(1 ((4((1))30900) 1):0000-3123 2018
[26] H. Chui and A. Rangarajan. A new point matching algorithm for non-rigid registration. Computer Vision and Image Understanding, 89(2-3):114 141,141, 2003.
[27] M. Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26:2292-2233 23000, 2013.
[28] 7. Dang, F. Wang, and M. Salzmann. Learning 3D-3D correspondences for one-shot partial-to-partal registration. arXiv preprint arXiv:2006.04523 2020.
[29] H. Deng, T. Birdal, and S. Iic.. Ppf-foldnet: Unsupervised learning of rolation invariant 3D local descriptors. In Proceedings of the European Conference on Computer Vision (ECCV), pages 602-618, 2018.
[30] H. Deng, Birdal, and S. Ilce. Ppfnet: Global context aware local features robust point matching. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 195-205, 2018.
[31] N. Donati, A. Sharma, and M. Ovsjanikov. Deep geometric functional maps: Robust feature learning for shape correspondence. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8592-8601, 2020.
[32] J. R. Dormand and P. J. Prince. A family of embedded Runge- Kutta formulae. Journal of computational and applied mathematics, 6(1):19-26, 1980.
[33] M. Eisenberger, A. Toker, L. Taixé, and D. Cremers. Deep shells: Unsupervised shape correspon- dence with optimal transport. arXiv preprint arXiv:2010.15261. 2020.
[34] R. S. Estépar, J. C. Ross, K. Russian, T. Schultz, G. R. Washko, and G. L. Kindlmann. Computational vascular morphometry for the assessment of pulmonary vascular discase based on scale-space particles. In 2012 9th IEEE International Symposium on Biomedical Imaging (ISBI), pages 1479-1482. IEEE, 2012.
[35] J. Feydy. Geometric data analysis, beyond convolutions. PhD thesis, Université Paris-Saclay, 2020.
[36] J. Feydy, B. Charlier, F.X. Vialard, and G. Peyré. Optimal transport for diffeomorphic registration. In International Conference on Medical Image Computing and Computer-Asiiteed Intervention, pages 291-299. Springer, 2017.
[37] J. Feydy, J. Glaunès, B. Charlier, and M. Bronstein. Fast geometric learning with symbolic matrices. Proc. NeurlPS, 2(4):6, 2020.
[38] J. Feydy, P. Roussillon, A. Trouvé, and P. Gori. Fast and scalable optimal transport for brain tractograms. International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 636-644. Springer, 2019.
[39] J. Feydy, T. Séjoumé, F-X. Vialard, S.-i. Amari, A. Trouvé, and G. Peyré. Interpolating between optimal transport and MMD using Sinkhorn divergences. In The 22nd International Conference on Artificial Intelligence and Stotistics, pages 2681-2690 PMLR, 2019.
12

---

[40] J. Feydy and A. Trouvé. Global divergences between measures: from Hausdorff distance to optimal transport. In International Workshop on Shape Medical Imaging, pages 102-115. Springer. 2018.
[41] M. A. Fischler and R. C. Bolles. Random sample consensus: paradigm for model fitting with applications image analysis and automated cartography. Communications of the ACM, 24(6):381-399) 1981.
[42] A. F. Frangi. W. J. Niessen, K. L. Vincken, and M. A. Viergever. Multiscale vessel enhancement filtering. In International conference medical image computing and computer-asiistd intervention, pages 130 137. Springer, 1998.
[43] P. Gainza, F. Sverrisson, F. Monti, E. Rodola, D. Boscaini, M. Bronstein, and B. Correia. Deciphering interaction fingerprints from protein molecular surfaces using geometric deep learning. Nature Methods, 1742)1144-19, 2020.
[44] W. Gao and R. Tedrake. Filterreg: Robust and efficient probabilistic point-set registration using Gaussian filter and twist parameterization. Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages I 1095--11044 2019.
[45] Gerber, M. Niethammer, M. Styner, and S. Aylward. Exploratory population analysis with unbalanced optimal transport. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pages 464-472. Springer, 2018.
[46] Z. Gojeic, C. Zhou, J. D. Wegner, and A. Wieser. The perfect match: 3D point cloud matching with smoothed densities. In Proceedings of the IEEE/CVF Conference Computer Vision and Puttern Recognition, pages 5545-5554, 2019.
[47] S. Goldd A. Rangarajan, C.-P. Lu, S. Pappu, and E. Mjolsness. New algorithms for 2D and 3D point matching: pose estimation and correspondence. Pattern recognition, 1003,,1019-1031, 1998.
[48] A. Gretton, K. M. Borgwardt, M. Rasch, B. Schölkopf. and A. Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723 (111):22337733222 2012.
[49] X. Gu, Y. Wang. C. Wu, Y. J. Lee, and P. Wang. Net: Hierarchical permutohedral lattice FlowNet for scene flow estimation on large-scale point clouds. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3254-3263, 2019.
[50] Hansen, D. Dittmer, and M. P. Heinrich. Learning deformable point set registration with regularized dynamic graph CNNs for large lung motion COPD patients. In International Workshop on Graph Learning in Medical Imaging, pages 53-61. Springer, 2019.
[51] Hansen and M. Heinrich. Tackling the problem large deformations deep learning based medical image registration using displacement embeddings. Medical Imaging in Deep Learning, arXiv preprint arXiv:2005. 13338, 2020.
[52] L. Hansen and M. P. Heinrich. Deep lcarning based geometric registration for medical images: How accurate can we get without visual features? In International Conference on Information Processing in Medical Imaging, pages 18-30. Springer, 2021.
[53] L. Hansen and M. P. Heinrich. GraphRegNet: Deep graph regularisation networks on sparse keypoints for dense registration of 3d lung CTs. IEEE Transactions on Medical Imaging, 40(9):2246-20) 22577 2021.
[54] G. L. Hart, C. Zach, and M. Niethammer. An optimal control approach for deformable registration. In CVPR Workshops, pages 9-16, 2009.
[55] M. P. Heinrich, H. Handels, and I. J. Simpson. Estimating large lung motion in COPD patients by symmetric regularised correspondence fields. In International conference on medicul image computing and computer
intervention, pages 338- 345. Springer, 2015.
[56] S. Hermann. Evaluation of scan-line optimization for 3D medical image registration. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3073-3080. 2014.
[57] B. K. Horn. Closed-form solution of absolute orientation using unit quaternions. Josa 4(4):629-641 1987.
[58] X. Huang, G. Mei, J. Zhang, and R. Abbas. A comprehensive survey on point cloud registration. arXiv preprint arXiv:2103 103.02690, 2021.
[59] J. Johnson, M. Douze, and H. Jégou. Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 2019.
13

---

[60] W. Kabsch. A solution for the best rotation to relate two sets of vectors. Acta Crystallogruphica Section
A: Crystal Physics, Diffraction, Theoretical and General Crystallography, 32(5):922-223, 1976.
[61] G. Kindlmann et al. Teem.
httpee/ewmm.ucucrooeeeeeeeeeeeee ptwpurrceeoogeeeee/uuullal html
[62] G. L. Kindlmann, R. J. Estépar, S. M. Smith, and C.-F. Westin. Sampling and visualizing creases with scale-space particles. IEEE transactions visualization and computer graphics, 15(6):1415-1444 2009.
[63] D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: arXiv: 1412.6980. 2014.
[64] J. Kosowsky and A. L. Yuille. The invisible hand algorithm: Solving the assignment problem with statistical physics. Neural networks, 7(3)477-490, 1994.
[65] C. Léonard. From the Schrödinger problem the Monge Kantorovich problem. Journal of Functional Analysis, 262: 1979-1920, 2012.
[66] B. Lévy. A numerical algorithm for L2 semi-discrete optimal transport in 3D. ESAIM: Mathematical Modelling and Numerical Analysis, 49(6):1693 1715, 2015.
[67] M. Licro, A. Mielke, and G. Savaré. Optimal entropy-transpor problems and new Bellinger-Kantrrovve distance between positive measures. Inventiones mathematicae, 21 211(3):969-11 -1177 2018.
[68] O. Litany, Remez, Rodola, A. Bronstein, and Bronstein. Deep functional maps: Structured prediction for dense shape correspondence. In Proceedings of the IEEE international conference on computer vision, pages 5659-5667, 2017.
[69] X. Liu, C. R. Qi, and L. J. Guibas. FlowNet3D: Learning scene flow in 3D point clouds. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 529-537, 2019.
[70] H. Lombaert, L. Grady, X. Pennec, N. Ayache, and F. Cheriet. Spectral log-demons: diffeomorphic image registration with very large deformations. International journal of computer vision, 107(3):254-271 2014.
[71] M. Lüthi, T. Gerig, C. Jud, and T. Vetter. Gaussian process morphable models. IEEE transactions on pattern analysis and machine intelligence, 8008):18 2017.
[72] J. Ma, J. Zhao, Y. Ma, and J. Tian. Non-rigid visible and infrared face registration via regularized Gaussian fields criterion. Pottern Recognition, 48(3):772-784, 2015.
[73] J. Ma. J. Zhao, and A. L. Yuille. Non-rigid point set registration by preserving global and local structures. IEEE Transactions on image Processing, 25(1):53 64, 2015.
[74] M. Mandad, D. Cohen-Steiner, L. Kobbelt, P. Alliez, and M. Desbrun. Variance-miniiizing transport plans for sureresurface mapping. ACM Transactions on Graphics (TOG), 36(4):1-14, 2017.
[75] Mayer, 1lg. Hausser, Fischer, Cremers, A. Dosovitskiy, and T. Brox. large dataset train convolutional networks for disparity, optical flow, and scene flow estimation, In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4040-4048, 2016.
[76] H. Men, B. Gebre, and K. Pochiraju. Color point cloud registration with 4D ICP algorithm. In 2011 IEEE International Conference on Robotics and Automation, pages 151 1516. IEEE, 2011.
[77] M. Menze and A. Geiger. Object scene flow for autonomous vehicles. In Proceedings of the IEEE conference on computer vision and pultern recognition, pages 3061-3070, 2015.
[78] M. Menze, C. Heipke, and A. Geiger. Joint 3D estimation of vehicles and scene flow. ISPRS annals of the photogrammetrr, remote sensing and spatial information sciences, 2:427, 2015.
[79] Q. Mérigot. A multiscalc approach to optimal transport. In Computer Graphics Forum, volume 30, pages 1593- Wiley Online Library, 1.
[80] D. Mukherjee, A. Guha, J. M. Solomon, Y. Sun, and M. Yurochkin. Outlier-robust optimal transport. In International Conference Machine Learning, pages 7850-7860 PMLR, 2021.
[81] A. Myronenko and X. Song. Point set registration: Coherent point drift. IEEE transactions pattern analysis and machine intelligence, 32(12):222-2275, 2010.
[82] E. A. Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9()::411-44, 1964.
14

---

[83] P. Nardelli, J. C. Ross, and R. S. Estépar: Generative-basee based airway and vessel morphology quantification chest CT images. Medical image analysis, 63:101691, 2020.
[84] M. Ovsjanikov, M. Chen,, J. Solomon, A. Butscher, and L. Guibas. Functional maps: a flexible representation of maps between shapes. ACM Transactions on Graphics (TOG), 31(4): 1111 2012.
[85] G. Pai, J. Ren, S. Mclzi, Wonka, and M. Ovsjanikov. Fast Sinkhorn filters: Using matrix scaling for non-rigid shape correspondence with functional maps. In CVPR, 2021.
[86] A. Paszke, Gross, S. Chintala, G. Chanan, E. Yang. Z. DeVito, Z. Lin, A. Desmaison, L., Antiga, and A. Lerer. Automatic differentiation in Py PyTorch. OpenReview.net, 2017.
[87] G. Peyré, M. Cuturi, et al. Computational optimal transport: With application to data science. Foundations and Trends in Muchine Leurning. 11(566)33556607, 2019.
[88] J. P. Pluim, J. A. Maintz, and M. A. Viergever. Mutual information matching in multiresolution contexts. Image and Vision Computing, 19(1-2):45 52, 2001.
[89] T. Polzin, M. Niethammer, M. P. Heinrich, H. Handels, and J. Modersitzki. Memory efficient LDDMM for lung CT. In International conference on medical image computing and computer-axiisted intervention. pages 28-36. Springer, 2016.
[90] Polzin, J. Rühaak, Werner, Strehlow, S. Heldmann, H. Handels, and Modersitzki. Combining automatic landmark detection and variational methods for lung CT registration. In Fifth international workshop on pulmonary image analysis, pages 85-96, 2013.
[91] G. Puy, A. Boulch, and R. Marlet. FLOT: Scone flow on point clouds guided by optimal transport. arXiv preprint arXiv:2007.1 1142, 2020.
[92] C. R. Qi, H. Su, K. Mo, and L. J. Guibas. PointNet: Deep learning point sets for 3D classification and segmentation. In Proceedings of the IEFE conference on computer vision and pattern recognition, pages 652-660, 2017.
[93] C. R. Qi, Yi, H. Su, and L. Guibas. Pointnet++:: Deep hierarchical feature learning on point sets in a metric space. arXiv preprint arXiv:1706.0243: 2017.
[94] M. I.. Rizzo and G. J. Székely, Energy distance. Wiley interdisciplinary reviews: Computational statistics, 8(1):27-38, 2016.
[95] O. Ronneberger, P. Fischer, and T. Brox. U-Net: Convolutional networks for biomedical image segmen- tation. In International Conference on Medical image computing and computer-asiited intervention, pages 234-241. Springer, 2015.
[96] P. Roussillon and J. A. Glaunès. Kernel metrics on normal cycles and application to curve matching. SIAM Journal on Imaging Sciences, 94):1991-20336 2016.
[97] Rubner, C. Tomasi, and Guibas. The earth mover's distance as a metric for image retrieval. International journal of computer vision, 40(2):99- 2000.
[98] J. Rühaak, S. Heldmann, T. Kipshagen, and B. Fischer. Highly accurate fast lung CT registration. In Medical Imaging 2013: Image Processing, volume 8669, page 86690Y. International Society for Optics and Photonics, 2013.
[99] J. Rilhakk T. Polzin, S. Heldmann, 1. J. Simpson, H. Handels. J. Modersitzki, and M. P. Heinrich. Estimation of large motion in lung CT by integrating regularized keypoint correspondences into dense deformable registration. IEEE transactions on medical imaging, 36(8) 1746 1757, 2017.
[100] R. B. Rusu, N. Blodow, and M. Beetz. Fast point feature histograms (FPFH) for 3D registration. In 2009 IEEE international conference on robotics and automation, pages 3212-3217. IEEE, 2009.
[101] R. B. Rusu, N. Blodow, Z. Marton, and M. Beetz. Aligning point cloud views using persistent feature histograms. In 2008 IEEF/RSJ international conference on intelligent robots and systems, pages 3384-3391. IEEE, 2008
[102] R. San José Estepar et al. Chest imaging platform. httpe://cdeestimgg.npplttoooo org/
[103] B. Schmitzer, Stabilized sparse scaling algorithms for entropy regularized transport problems. SIAM Journal on Scientific Computing, 41(3):A1443 -14414 2019.
15

---

[104] E. Schrödinger. Sur la théorie relativiste de l'électron et l'interprétation de la mécanique quantique. In Annales de l'institut Henri Poincaré, volume 2, pages 269-310, 1932.
[105] T. Séjouméé. J. Feydy, F.-X. Vialard, A. Trouvé, and G. Peyré. Sinkhorn divergences for unbalanced optimal transport. arXiv preprint arx:: 1910. 12958, 2019.
[106] T. Séjourné, F.-X. Vialard, and G. Peyré. The unbalanced Gromov Wasserstein distance: Conic formulation and relaxation. arXiv preprint (oXiv:2009.042666 2020.
[107] Z. Shen, X.
Han, Z. Xu, and M. Niethammer. Networks for joint affine and non- cet--arrmetri image registration. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
pages
[108] 7. Shen, F-X. Vialard, and M. Niethammer, Region-specific diffcomorphic metric mapping. Advances in Neural Information Processing Systems, 32: 22:1098-1108 1108, 2019.
[109] D. Shepard. A two-dimensional interpolation function for irregularly spaced data. In Proceedings of the 1968 23rd ACM national conference, pages 117-524, 1968.
[110] J. Solomon, G. Peyré, V. G. Kim, and S. Sra. Entropic metric alignment for correspondence problems. ACM Transactions on Gruphics (TOG), 35(4) 2016.
[111] H. Su, Jampani, D. Sun, Maji. Kalogerakis, M.-H. Yang, and Kautz. SplatNet: Sparse lattice networks for point cloud processing. In Proceedings of the IEEE conference on computer vision and puttern recognition, pages 2530-2539, 2018.
[112] C. B. Sullivan and A. A. Kaszynski. PyVista: 3D plotting and mesh analysis through a streamlined interface for the Visualization Toolkit (vtk). Journal of Open Source Software, 4(37):1450, 2019.
[113] Sverrisson. J. Feydy, E. Correia, and M. M. Bronstein. Fast end-to-end learning on protein surfaces. In Proceedingy of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15272- 15281, 2021.
[114] Tombari, S. Salti, and L. Stefano. Unique signatures of histograms for local surface description, In European conference on computer vision, pages 356-369. Springer, 2010.
[115] M. Vaillant and Glaunes. Surface matching via currents. Biennial International Conference on Information Processing in Medical Imaging, pages 381-392. Springer, 2005.
[116] Van der Maaten and G. Hinton. Visualizing data using tNE,, Journal of machine learning research, 911)), 2008.
[117] Van Der Walt, C. Colbert, and G. Varoquaux. The NumPy array: structure for efficient numerical computation. Computing in science engineering. 13(2):22-30, 2011.
[118] T. Vayer, R. Flamary, N. Courty, R. Tavenard, and L. Chapel. Sliced Maanoo-Wasseesstein. Advances in Neural Information Processing Systems, 22:14753-14766 2019.
[119] V. Vishnevskiy, T. Gass, G. Szekely, C. Tanner, and O. Goksel. Isotropic total variation regularization of displacements in parametric image registration. IEEE transactions on medical imaging, 36(2):385-395. 2016.
[120] V. Vishnevskiy, T. Gass, G. Szekely, C. Tanner, and O. Goksel. Isotropic total variation regularization of displacements parametric image registration. IEEE transactions on medical imaging, 36(2):385-355 2017.
[121] Wang and M. Solomon. Deep closest point: Learning representations for point cloud registration. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 3523-3532, 2019.
[122] Y. Wang and J. M. Solomon. PRNet: Self Self-supervised learning for partial-to-pane -partial registration. arXiv preprint arXiv:1910.122 12240, 2019.
[123] Y. Wang. Y. Sun, Z. Liu, S. E. Sarma, M. M. Bronstein, and J. M. Solomon. Dynamic graph CNN for learning on point clouds. Acm Transactions Graphics (tog), 38(5):1 12,1111222200 2019.
[124] G. S. Watson. Smooth regression analysis. Sankhya: The Indian Journal of Statistics, Series A, pages 359-372, 1964.
[125] W. Wu, Z. Qi. and Fuxin. PointConv: Deep convolutional networks on 3D point clouds. In Proceedings the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 2019.
16

---

[126] W. Wu, Z. Wang. Z. Li. W. Liu, and L. Fuxin. PoinPWW--Net: A coarse-to-fiee fine network for supervised and self-supervised
flow estimation 3D point clouds. arXiv preprint
2019.
[127] Z. Wu, S. Song, A. Khosla, F. Yu, I.. Zhang. X. Tang, and J. Xiao. 3d shapenets: A deep representation for volumetric shapes. In Proceedings the IEEE conference computer vision and pattern recognition. pages 1120,, 2015.
[128] H. Yang and L. Carlone. A polynomial-time solution for robust registration with extreme outlier rates. arXiv preprint MXXiv:1903.08500 2019.
[129] H. Yang, J. Shi, and L. Carlone. Teaser: Fast and certifiable point cloud registration. IEEE Transactions on Roboticy, 2020.
[130] J. Yang, H. Li, D. Camphell, and Y. Jia. Go-iep: A globally optimal solution 3d icp point-set registration. IEEE transactions on pattern analysis and machine intelligence, 38(11):224] 222244122254 2015.
[131] X. Yang, R. Kwitt, M. Styner, and M. Niethammer. QuickSilver: Fast predictive image registration-a deep learning approach. Neurolmage, 158:378-396, 2017.
[132] 7. J. Yew and G. Lee. RPM-Net: Robust point matching using learned features. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 11824-18833, 2020.
[133] A. Zeng, S. Song, M. Nießner, M. Fisher, Xiao, and T. Funkhouser. 3DMatch: Learning local geometric descriptors from RGB-d reconstructions. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1802-1811, 2017.
[134] Q.-Y. Zhou, Park, Koltun. global registration. In European Conference on Computer Vision. pages 766-782. Springer, 2016.
[135] Zhou, C. Wu, Li, C. Cao, Y. Ye, J. Saragih, Li, and Y. Sheikh. Fully convolutional mesh autoencoder using efficient spatially varying kemelss. arXiv preprint arXi:20006004325, 2020.
[136] Zhu, R. H. Byrd, P. Lu, J. Nocedal, Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale
bound-constrained optimization. ACM Transactions on mathematical software (TOMS), 23(4):550-560,
1997.
17


Reviews:
[{"review_id": "zk3tBKrpLuD", "reviewer": "Reviewer_Y4k6", "summary": "This paper proposes a transport optimal method to calculate the assignment by adding several regularizers.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper adds several regularizers to the standard optimal transport method.\n\nQuality: Firstly, the contribution is limited. Secondly, I am a bit worried about whether the better performance comes from the regularizers since the proposed method has pre-alignment and post-processing. The key contribution of this paper lies in post-processing. How about the performance by replacing the post-processing with standard transport optimal method. This research work of this submission seems not complete. I recommend the authors conduct these experiments.\n\nClarity: The overall writing is well and very easy to follow.\n\nsignificance: The results are important but not convince to me. More ablation study is still required to demonstrate the value of this work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "HIjSf1gq7Pt", "reviewer": "Reviewer_Yt1x", "summary": "The paper proposes a computationally efficient point cloud registration method based on Optimal Transport. The DRobOT pipeline relies on a deep module that predicts parameters of a registration model, plus pre and post processing steps based on RobOT. The paper shows results for scene flow and point cloud lung registration. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "PROS\n======\nEFFICENCY\\\nThe method shows efficiency in terms of computation without an explosion of memory. This is a relevant aspect that has a high application interest in several fields. The method specifies that code and data will be available, and these are both remarkable contributions.\n\nREAL-WORLD RESULTS\\\nI like that the shown results are on real data, with an extensive comparison with many different methods on two different applicative domains. It is also providing an ablation on different aspects of the method; I think this is a good validation for the method. \n\nDIFFERENT REGISTRATION MODELS\\\nThe method admits different kinds of registration models, which may be properly selected for different applicative purposes. Also, the method can face partiality (as shown in a toy example from supplementary material), which I consider an interesting and challenging setting.\n\nCONS\n======\nPRESENTATION\\\nI think the paper is a bit verbose, and the extensive use of paragraphs make it hard to understand the structure of the underlying story. For example, Section 3 is a bit confused; the first paragraphs are about derivations useful for the method, then some properties are listed (partial registration, black-box deformation models), to move to lung data presentation and then experimental setting. I would suggest rethinking Section 3 and 4 to better group a) elements of the method (and maybe an enumerate workflow of different steps), b) analysis of the method properties, c) involved datasets, d) experiments on the two different scenarios. However, I would suggest revising the text and finding ways to make it more compact and schematic, and also adding some support Figures to improve the narration (e.g., some toy examples of the process, like the sphere to cube from the supplementary). Consequently, I would suggest rethinking page 7, since it breaks the text and the reader has some work to do to go back and forth between the pages. I would suggest highlighting in bold the first and the second best values in Figure 3, 4 and Table 1, to ease the inspection of the values. Understanding the lunge images is a bit complicated for non-expert users (like me) in particular when they are aligned; maybe highlighting errors in visualization (e.g., heat map) would be beneficial. Also, I think that some image examples of KITTI dataset could be moved from supplementary to the main manuscript. I would suggest including losses into the main manuscript and removing Algorithm 1, which seems not significantly informative. Finally, the title is a bit generic; I would suggest adding something that emphasizes the specific contribution of the paper (e.g., the use of a deep network, the mention of the efficiency, the use of the DRobOT, ...).\n\nFORMULATION VS IMPLEMENTATION \\\nIn several parts, the problem formulation is somehow obfuscated by implementation aspects. For example, in the \"The weighted RobOT matching\" paragraph, the formulation is mixed with the use of libraries (GeomLoss, PyTorch, KeOps, NumPy). It is not completely clear to me if the efficiency comes from the smart formulation or from the library implementations. I would like to read a comment on this aspect; in general, I would suggest creating a \"implementation\" subsection where list all the aspects of the coding.\n\nSUPERVISION \\\nWhile the method presents general characteristics in the deformation paradigm, it requires a supervised setting for training. I think this is somehow limiting, considering that Optimal Transport finds application in many fields in which a ground truth correspondence is, in general, an ill-posed problem or hard to obtain.\n\nMINOR COMMENTS AND QUESTIONS\n=======\na) I see from Figure 5 of Supplementary Materials that the method can also solve for partiality. Do you have any insight on the amount of partiality that the method could tackle? I think an evaluation on this aspect would also make the paper significantly stronger. \\ \nb) Do you see any limitations to use more complex deformation paradigms, e.g., the parameters of morphable models (which may also be some hundreds)? \n\nRATING JUSTIFICATION\n=========\nThe idea is not particularly surprising, but the evaluation and efficiency analysis are interesting, and the method seems to be of potential interest for NeurIPS community. I would suggest revising the presentation and work on the clarity of the method presentation.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I do not see any potential negative societal impact in this work.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not see any ethical concern in this work.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "F3dWg7q0rWe", "reviewer": "Reviewer_Cd96", "summary": "This paper proposes to combine optimal control (OT) and a set of deformation models for point cloud registration. They propose two settings to leverage OT: global feature matching and deep feature prediction. Experiments on two datasets verified the effectiveness of the proposed method. The writing is overall clear.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes to combine optimal control and a set of deformation models (e.g., rigid, affine, spline, and LDDMM) for point cloud registration. The bijectivity from the optimal control can provide reliable matchings and gradients. The bijective matching is typically time-consuming, but the proposed method leverages an efficient OP solver and scales to more than 10k points.\n\nThe method proposes two settings to utilize OT for point cloud registration:\nThe first one is global feature matching. The feature may come from heuristic rules of neural networks. They then use the extracted feature to solve a \"weighted robOT matching\". They then project the result with certain deformation models.\nThe second one is registration via deep deformation prediction:\nThey first use a fast OT solver for rigid or affine pre-alignment. They then propose to use a network to predict the parameters of a chosen registration model. The model is trained with supervision. Finally, they RobOT to fine-tune and post-process the result.\n\nThe proposed methods achieve the SOTA results on two datasets: lung registration and the Kitti dataset.\n\nThe overall idea is novel, clear, and effective.\n\n\n---------Weakness:\n\nFor partial registration, there is only one toy example shown in supplementary. It would be helpful to show more results on incomplete and occluded point clouds. For example, we can have large-scale quantitative experiments on the ShapeNet dataset. The task can be registering two random views, which is of great interest to many readers.\n\nDeep-feature learning: Using cross-entropy to force the feature to preserve Euclidean distance may not be the best solution. Another idea would be contrastive learning with matched pairs as positive pairs and others as negative pairs.\n\nFor Kitti experiments, there aren't many qualitative results. It would be better to include more visualization for local matching details, as many readers may be interested in the Kitti experiments.\n\nThe author claims that \"the image-based methods can make use of more information.\" It's interesting to know whether the proposed method will outperform the image-based methods when the color information is taken as input.\n\nSymbols of the deep-feature learning part (starts from line 230) are not very clear. More explanations are encouraged.\n\nIn figure 3, for the optimization-based method, it's not clear whether the runtime includes the deep-feature inference time.\n\nIn Kitti experiments, it's not clear which feature is used for matching. Handcrafted feature of NN feature?\n \nThe black-box optimization is still time-consuming. For example, LDDMM takes 40 seconds.\n\nMSN[1] also provides an EMD implementation that supports more than 10k points without memory issues. Please discuss the work.\n\n[1] Liu, Minghua, et al. \"Morphing and sampling network for dense point cloud completion.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 07. 2020.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "3yLsk9XdGb-", "reviewer": "Reviewer_qUAf", "summary": "This paper discusses the application of optimal transport theory in and contributed several useful practices to shape matching. First, the proposed RobOT method implements the traditional entropy-regularized unbalanced optimal transport using the kernel method and reduces the memory footprint to linear, enabling the processing of over 60k points. Second, the paper introduces several effective strategies to regularize/project the transport vectors given a deformation model (RobOTP). Third, the deep deformation framework (DRobOT) is proposed by sandwiching the parameter prediction module with pre-alignment and post-optimization steps, which lead to SoTA performance on a new lung dataset and scene flow datasets. Apart from the algorithmic side, the authors also give a clear summary which cover most of the vision algorithms using optimal transport. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "PROs\n- The paper provides a good summary of the usage of optimal transport in computer vision pipelines. The analysis is thorough and clear.\n- The experiments on Lung registration and scene flow estimation show promising results compared to the baselines.\n- The proposed method can scale up to 60k points for registration tasks in a deep OT context, which is a non-trivial advancement.\n\nCONs\n- One of the core contributions of the paper, i.e., RobOT, seems to be a programming/engineering trick and a simple stacking of GeomLoss and KeOps library (which is btw already included in GeomLoss several years ago). Please refer to Line155-Line164 for this claim. Although the kernel trick can significantly reduce the memory footprint (i.e. from quadratic to linear), no extra computational effort is saved and we lost the efficiency provided by the cublas libraries by removing matrix multiplication. So I'm curious how and why is the proposed method faster and more robust?\n\n- The size of the test set for lung registration is too small (only 10 compared to the 800-200 train/val split used for training). I would expect the paper to re-split their 1k-sized annotated dataset and used at least 100 samples for testing.\n\n- The following works are certainly relevant and are worth comparing to (given that they share a similar philosophy to this paper):\nGojcic, Zan, et al. \"Weakly Supervised Learning of Rigid 3D Scene Flow.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.\nLi, Ruibo, et al. \"HCRF-Flow: Scene Flow from Point Clouds with Continuous High-order CRFs and Position-aware Flow Embedding.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.\n\nOther Concerns:\n- Please refer to the supplementary material in the main text for the definition of LDDMM and spline deformation model or add a brief introduction to these models in order to be self-contained.\n- How is the pipeline in Sec.4 (deep registration, D/RobOTP) trained? Did you train/pre-train each part individually or the full pipeline end-to-end? If so, how do you differentiate through the argmin in Alg.1? How stable is the training process? Is the blur radius and reach distance trained altogether?\n- Line 98-100: I don't think the proposed projection is in -sharp contrast- with FLOT. FLOT utilizes a refinement module which learns the smoothness prior from the training data and it acts as an implicit regularization module compared to the explicit projection model proposed in this paper.\n- According to Line194-Line203, the confidence weight reflects the occlusion status of the point clouds to be registered. Is this claim justified by the experiments? Please plot the confidence weight, e.g. in a representative sample in Flying3D dataset and verify the claim.\n- The paper should note (and clarify) that the rigid projection in Eq.(5) is also related to a weighted Kabsch algorithm.\n- Line 119: sorting to -> sorting in;  Fig.8 in Supplementary: fow -> flow; ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper misses a broader impact statement and the main paper fails to discuss the limitations - these are rather relegated to the supplementary material. I would recommend that the paper includes a brief discussion in the main paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper was a borderline case, but despite some weaknesses we are recommending acceptance for NeurIPS.  Here, the positive aspects are mostly practical/empirical; the authors show how unbalanced OT can be incorporated into realistic pipelines for rigid/nonrigid registration.  But the work is mostly engineering, and the methodological/algorithmic contribution is smaller.

The AC/SAC also had some concern about precisely what objective function this algorithm is optimizing.  It is not articulated clearly in the paper and appears to be a bilevel problem with optimal transport as the "inner" problem----but then the gradients may not be correct.  Empirically this appears to be OK in the results, but it'd be preferable to give a clearer mathematical story in this work.

Two additional related papers need to be acknowledged/discussed in the final version of this paper:
* Feydy et al.  "Optimal Transport for Diffeomorphic Registration."  MICCAI 2017. ---- This paper contains many related ideas and incorporates optimal transport losses in a similar fashion.
* Mukherjee et al.  "Outlier-Robust Optimal Transport."  ICML 2021. --- This paper proposes a similar unbalanced transport model.  It also uses the same "ROBOT" acronym to refer to their model.
Please make sure the camera-ready acknowledges and discusses these two works, and also take the suggestions in the individual reviews seriously.
Decision: Accept (Poster)