Establishing reliable correspondences is essential for registration tasks
such as 3D and 2D3D registration. Existing methods commonly leverage geometric
or semantic point features to generate potential correspondences. However,
these features may face challenges such as large deformation, scale
inconsistency, and ambiguous matching problems (e.g., symmetry). Additionally,
many previous methods, which rely on single-pass prediction, may struggle with
local minima in complex scenarios. To mitigate these challenges, we introduce a
diffusion matching model for robust correspondence construction. Our approach
treats correspondence estimation as a denoising diffusion process within the
doubly stochastic matrix space, which gradually denoises (refines) a doubly
stochastic matching matrix to the ground-truth one for high-quality
correspondence estimation. It involves a forward diffusion process that
gradually introduces Gaussian noise into the ground truth matching matrix and a
reverse denoising process that iteratively refines the noisy matching matrix.
In particular, the feature extraction from the backbone occurs only once during
the inference phase. Our lightweight denoising module utilizes the same feature
at each reverse sampling step. Evaluation of our method on both 3D and 2D3D
registration tasks confirms its effectiveness.

建立可靠的对应关系对于 3D 和 2D3D 对准等任务至关重要。为了解决大变形、尺度不一致和模糊匹配问题所带来的挑战，本文引入了一种用于建立鲁棒对应关系的扩散匹配模型，在双随机矩阵空间内将对应估计视为去噪扩散过程，逐步去噪（细化）双随机匹配矩阵至准确的匹配矩阵，以进行高质量的对应估计。该方法在 3D 和 2D3D 对准任务上的评估验证了其有效性。

Diff-Reg v1：用于配准问题的扩散匹配模型

Diff-Reg v1: Diffusion Matching Model for Registration Problem

In this paper we consider the well-studied problem of finding a perfect
matching in a d-regular bipartite graph on 2n nodes with m=nd edges. The
best-known algorithm for general bipartite graphs (due to Hopcroft and Karp)
takes time O(m\sqrt{n}). In regular bipartite graphs, however, a matching is
known to be computable in O(m) time (due to Cole, Ost and Schirra). In a recent
line of work by Goel, Kapralov and Khanna the O(m) time algorithm was improved
first to \tilde O(min{m, n^{2.5}/d}) and then to \tilde O(min{m, n^2/d}). It
was also shown that the latter algorithm is optimal up to polylogarithmic
factors among all algorithms that use non-adaptive uniform sampling to reduce
the size of the graph as a first step.
In this paper, we give a randomized algorithm that finds a perfect matching
in a d-regular graph and runs in O(n\log n) time (both in expectation and with
high probability). The algorithm performs an appropriately truncated random
walk on a modified graph to successively find augmenting paths. Our algorithm
may be viewed as using adaptive uniform sampling, and is thus able to bypass
the limitations of (non-adaptive) uniform sampling established in earlier work.
We also show that randomization is crucial for obtaining o(nd) time algorithms
by establishing an \Omega(nd) lower bound for any deterministic algorithm. Our
techniques also give an algorithm that successively finds a matching in the
support of a doubly stochastic matrix in expected time O(n\log^2 n) time, with
O(m) pre-processing time; this gives a simple O(m+mn\log^2 n) time algorithm
for finding the Birkhoff-von Neumann decomposition of a doubly stochastic
matrix.

本文提出了一种基于随机算法和修剪的自适应均匀采样策略，在 O (n log n) 时间内寻找 d - 正则图中完美匹配，并用于求解双随机矩阵的 Birkhoff-von Neumann 分解。