Point Cloud Sampling via Graph Balancing and Gershgorin Disc Alignment.
Where this comes from
- Record sourced from PubMed, PMID 35025739.
- Also identified by DOI 10.1109/TPAMI.2022.3143089.
- No licence information is recorded for this record.
- Because redistribution is not established, this page shows the abstract only. Follow the links below for the full text.
Abstract
Point cloud (PC)-a collection of discrete geometric samples of a 3D object's surface-is typically large, which entails expensive subsequent operations. Thus, PC sub-sampling is of practical importance. Previous model-based sub-sampling schemes are ad-hoc in design and do not preserve the overall shape sufficiently well, while previous data-driven schemes are trained for specific pre-determined input PC sizes and sub-sampling rates and thus do not generalize well. Leveraging advances in graph sampling, we propose a fast PC sub-sampling algorithm of linear time complexity that chooses a 3D point subset while minimizing a global reconstruction error. Specifically, to articulate a sampling objective, we first assume a super-resolution (SR) method based on feature graph Laplacian regularization (FGLR) that reconstructs the original high-res PC, given points chosen by a sampling matrix H. We prove that minimizing a worst-case SR reconstruction error is equivalent to maximizing the smallest eigenvalue λ<sub>min</sub> of matrix H<sup>T</sup> H+ μL, where L is a symmetric, positive semi-definite matrix derived from a neighborhood graph connecting the 3D points. To arrive at a fast algorithm, instead of maximizing λ<sub>min</sub>, we maximize a lower bound λ<sup>-</sup><sub>min</sub>(H<sup>T</sup> H+ μL) via selection of H-this translates to a graph sampling problem for a signed graph G with self-loops specified by graph Laplacian L. We tackle this general graph sampling problem in three steps. First, we approximate G with a balanced graph G<sub>B</sub> specified by Laplacian L<sub>B</sub>. Second, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we perform a similarity transform L<sub>p</sub> = SL<sub>B</sub> S<sup>-1</sup>, so that all Gershgorin disc left-ends of L<sub>p</sub> are aligned exactly at λ<sub>min</sub>(L<sub>B</sub>). Finally, we choose samples on G<sub>B</sub> using a previous graph sampling algorithm to maximize λ<sup>-</sup><sub>min</sub>(H<sup>T</sup> H+ μL<sub>p</sub>) in linear time. Experimental results show that 3D points chosen by our algorithm outperformed competing schemes both numerically and visually in reconstruction quality.