An Efficient Sampling Algorithm with a K-NN Expanding Operator for Depth Data Acquisition in a LiDAR System

The spatial resolution of a depth-acquisition device, such as a Light Detection and Ranging (LiDAR) sensor, is limited because of the slow acquisition. To accurately reconstruct a depth image from limited spatial resolution, a two-stage sampling process has been widely used. However, two-stage sampling uses an irregular sampling pattern for the sampling operation, which requires complex computation for reconstruction and additional memory space for storage. A mathematical formulation of a LiDAR system demonstrates that two-stage sampling does not satisfy its timing constraint for practical use. To overcome the drawbacks of two-stage sampling, this paper proposes a new sampling method that reduces the computational complexity and memory requirements by generating the optimal representatives of a sampling pattern in down-sample data. A sampling pattern can be derived from a k -NN expanding operation from the down-sampled representatives. The proposed algorithm is designed to preserve the object boundary by restricting the expansion-operation only to the object boundary or complex texture. In addition, the proposed algorithm runs in linear-time complexity and reduces the memory requirements using a down-sampling ratio. The experimental results demonstrate that the proposed sampling outperforms grid sampling by at most 7.92 dB. Consequently, the proposed sampling achieves reconstructed quality similar to that of optimal sampling, while substantially reducing the computation time and memory requirements.