Efficient Reversible Data Hiding in Encrypted Point Clouds via KD Tree-Based Path Planning and Dual-Model Design
Yuan‐Yu Tsai, Chang‐Tsun Li, Cheng-Yu Ho, Ching‐Ta Lu · Mathematics · 2025
Reversible data hiding in encrypted point clouds presents unique challenges due to their unstructured geometry, absence of mesh connectivity, and high sensitivity to spatial perturbations. In this paper, we propose an efficient and secure reversible data hiding framework for encrypted point clouds, incorporating KD tree-based path planning, adaptive multi-MSB prediction, and a dual-model design. To establish a consistent spatial traversal order, a Hamiltonian path is constructed using a KD tree-accelerated nearest-neighbor algorithm. Guided by this path, a prediction-driven embedding strategy dynamically adjusts the number of most significant bits (MSBs) embedded per point, balancing capacity and reversibility while generating a label map that reflects local predictability. The label map is then compressed using Huffman coding to reduce the auxiliary overhead. For enhanced security and lossless recovery, the encrypted point cloud is divided into two complementary shares through a lightweight XOR-based (2, 2) secret sharing scheme. The Huffman tree and compressed label map are distributed across both encrypted shares, ensuring that neither share alone can reveal the original point cloud or the embedded message. Experimental evaluations on diverse 3D models demonstrate that the proposed method achieves near-optimal embedding rates, perfect reconstruction of the original model, and significant obfuscation of the geometric structure. These results confirm the practicality and robustness of the proposed framework for scenarios involving secure 3D point cloud transmission, storage, and sharing.