In this paper, we propose a method, based on graph signal processing, to
optimize the choice of $k$ in $k$-nearest neighbor graphs ($k$NNGs). $k$NN is
one of the most popular approaches and is widely used in machine learning and
signal processing. The parameter $k$ represents the number of neighbors that
are connected to the target node; however, its appropriate selection is still a
challenging problem. Therefore, most $k$NNGs use ad hoc selection methods for
$k$. In the proposed method, we assume that a different $k$ can be chosen for
each node. We formulate a discrete optimization problem to seek the best $k$
with a constraint on the sum of distances of the connected nodes. The optimal
$k$ values are efficiently obtained without solving a complex optimization.
Furthermore, we reveal that the proposed method is closely related to existing
graph learning methods. In experiments on real datasets, we demonstrate that
the $k$NNGs obtained with our method are sparse and can determine an
appropriate variable number of edges per node. We validate the effectiveness of
the proposed method for point cloud denoising, comparing our denoising
performance with achievable graph construction methods that can be scaled to
typical point cloud sizes (e.g., thousands of nodes).

基于图信号处理的方法，优化了 $k$- 最近邻图 ($k$NNGs) 中 $k$ 的选择问题，通过离散优化问题求解最佳 $k$ 值，从而实现了点云去噪。

基于图学习视角优化 $k$NN 图中的 $k$ 值

Optimizing $k$ in $k$NN Graphs with Graph Learning Perspective

The intricacy of 3D surfaces often results cutting-edge point cloud denoising
(PCD) models in surface degradation including remnant noise, wrongly-removed
geometric details. Although using multi-scale patches to encode the geometry of
a point has become the common wisdom in PCD, we find that simple aggregation of
extracted multi-scale features can not adaptively utilize the appropriate scale
information according to the geometric information around noisy points. It
leads to surface degradation, especially for points close to edges and points
on complex curved surfaces. We raise an intriguing question -- if employing
multi-scale geometric perception information to guide the network to utilize
multi-scale information, can eliminate the severe surface degradation problem?
To answer it, we propose a Multi-offset Denoising Network (MODNet) customized
for multi-scale patches. First, we extract the low-level feature of three
scales patches by patch feature encoders. Second, a multi-scale perception
module is designed to embed multi-scale geometric information for each scale
feature and regress multi-scale weights to guide a multi-offset denoising
displacement. Third, a multi-offset decoder regresses three scale offsets,
which are guided by the multi-scale weights to predict the final displacement
by weighting them adaptively. Experiments demonstrate that our method achieves
new state-of-the-art performance on both synthetic and real-scanned datasets.

提出一种基于多尺度几何知识指导多尺度信息利用的点云去噪方法（Multi-offset Denoising Network），其中包括低层次的多尺度特征提取、多尺度感知模块以及多尺度权重回归和多偏移解码器，该方法在合成和实际扫描数据集上均实现了最新的性能表现。

MODNet：定制多尺度补丁的多偏移点云去噪网络

MODNet: Multi-offset Point Cloud Denoising Network Customized for Multi-scale Patches

Identifying an appropriate underlying graph kernel that reflects pairwise
similarities is critical in many recent graph spectral signal restoration
schemes, including image denoising, dequantization, and contrast enhancement.
Existing graph learning algorithms compute the most likely entries of a
properly defined graph Laplacian matrix $\mathbf{L}$, but require a large
number of signal observations $\mathbf{z}$'s for a stable estimate. In this
work, we assume instead the availability of a relevant feature vector
$\mathbf{f}_i$ per node $i$, from which we compute an optimal feature graph via
optimization of a feature metric. Specifically, we alternately optimize the
diagonal and off-diagonal entries of a Mahalanobis distance matrix $\mathbf{M}$
by minimizing the graph Laplacian regularizer (GLR) $\mathbf{z}^{\top}
\mathbf{L} \mathbf{z}$, where edge weight is $w_{i,j} = \exp\{-(\mathbf{f}_i -
\mathbf{f}_j)^{\top} \mathbf{M} (\mathbf{f}_i - \mathbf{f}_j) \}$, given a
single observation $\mathbf{z}$. We optimize diagonal entries via proximal
gradient (PG), where we constrain $\mathbf{M}$ to be positive definite (PD) via
linear inequalities derived from the Gershgorin circle theorem. To optimize
off-diagonal entries, we design a block descent algorithm that iteratively
optimizes one row and column of $\mathbf{M}$. To keep $\mathbf{M}$ PD, we
constrain the Schur complement of sub-matrix $\mathbf{M}_{2,2}$ of $\mathbf{M}$
to be PD when optimizing via PG. Our algorithm mitigates full
eigen-decomposition of $\mathbf{M}$, thus ensuring fast computation speed even
when feature vector $\mathbf{f}_i$ has high dimension. To validate its
usefulness, we apply our feature graph learning algorithm to the problem of 3D
point cloud denoising, resulting in state-of-the-art performance compared to
competing schemes in extensive experiments.

本文提出一种基于特征图的方法来学习图信号的复原，通过最小化图拉普拉斯正则项以优化马氏距离矩阵的带权图，在 3D 点云去噪问题上的实验证明，相较于已有的方案，该算法具有最先进的性能。