Structured Skip List: A Compact Data Structure for 3D Reconstruction

The model produced by 3D reconstruction algorithm is usually represented by voxels. The management of these voxels is usually divided into two categories: ordered and unordered methods. The ordered method holds too many empty voxels to maintain data order which leads to a low storage efficiency. On the contrary, the unordered method keeps massive index data to only store nonempty voxels. In this paper, we design a new data management method for real-time indoor 3D reconstruction, called Structured Skip List (SSL). The SSL can be treated as a semi-ordered method, because the advantages of both the ordered and unordered methods are taken into account: 1) it only holds nonempty voxels similar to the unordered method; 2) the structured information is introduced to reduce the storage space of index data. By these designs, the SSL has a better performance on storage efficiency. To handle the data collision in voxel allocation, a hash allocation list (HAL) is proposed. The length of each Skip List is kept balanced by fusing the IMU (Inertial Measurement Unit) information for a high operation efficiency. The storage efficiency analysis of different data management methods is shown in this paper. What's more, exhaustive investigation is carried out on several datasets with these methods. The experimental result demonstrates that our design can achieve a high storage efficiency with little time loss compared to the state-of-the-art methods.

Authors

• Shijie Li 0006
• Ming-Ming Cheng
• Yun Liu 0011
• Shao-Ping Lu
• Yahui Wang
• Victor Adrian Prisacariu

Keywords

• Three-dimensional displays
• Indexes
• Data structures
• Image reconstruction
• Resource management
• Solid modeling
• Pipelines
• Data Structure
• 3D Reconstruction
• Skip List
• Reconstruction Algorithm
• Index Data
• Inertial Measurement Unit
• Efficient Storage
• List Length
• Real-time Reconstruction
• Data Distribution
• Subject Headings
• Color Images
• 3D Space
• Sparse Matrix
• Depth Images
• Hash Function
• 3D Point
• Average Running Time
• Principal Directions
• Simultaneous Localization And Mapping
• Voxel Data
• Iterative Closest Point
• Allocation Procedure
• 3D Model Reconstruction
• World Coordinate System