# FOG-Zip: Bitstream Compression for Octree-Encoded LiDAR Data

## Abstract

Light detection and ranging (LiDAR) sensors play a critical role in enabling precise and reliable environmental perception for autonomous vehicles. However, handling the large amounts of data they generate presents a significant challenge. With the emergence of standards, such as the geometry based point cloud compression (G-PCC) standard, octrees have been used as a key data structure for compressing 3-D light detection and ranging (LiDAR) data. Despite their advantages, octrees often lead to high memory utilization and computational overhead, particularly when dealing with high-resolution datasets, limiting their utilization in systems with real-time requirements. This letter presents FOG-zip: a hardware-accelerated octree compression approach designed for embedded systems with limited resources. Experimental results demonstrate that FOG-zip achieves up to a 27.8% reduction in data size compared to the same uncompressed octree bitstream, while processing each frame within the frame rate limits of the sensor used.

## Authors

Ricardo Roriz *ALGORITMI Research Center/LASI, University of Minho, Guimarães, Portugal* [ORCID: 0000-0002-8543-550X](https://orcid.org/0000-0002-8543-550X)

Jorge Cabral *ALGORITMI Research Center/LASI, University of Minho, Guimarães, Portugal* [ORCID: 0000-0001-9954-9746](https://orcid.org/0000-0001-9954-9746)

Sandro Pinto *ALGORITMI Research Center/LASI, University of Minho, Guimarães, Portugal* [ORCID: 0000-0003-4580-7484](https://orcid.org/0000-0003-4580-7484)

Tiago Gomes *ALGORITMI Research Center/LASI, University of Minho, Guimarães, Portugal* [ORCID: 0000-0002-4071-9015](https://orcid.org/0000-0002-4071-9015)

## Publication Information

**Journal:** IEEE Sensors Letters **Year:** 2025 **Volume:** 9 **Issue:** 8 **Pages:** 1-4 **DOI:** [10.1109/LSENS.2025.3588338](https://doi.org/10.1109/LSENS.2025.3588338) **Article Number:** 11078905 **ISSN:** Electronic ISSN: 2475-1472

## Metrics

**Total Downloads:** 41

---

## Keywords

**IEEE Keywords:** Octrees, Codes, Binary sequences, Symbols, Encoding, Three-dimensional displays, Laser radar, Point cloud compression, Field programmable gate arrays, Frequency conversion

**Index Terms:** Light Detection And Ranging, Point Cloud, Light Detection, Computational Overhead, High Computational Overhead, 3D Space, Peak Signal-to-noise Ratio, Frequency Tables, Codeword, Binary Tree, Point Cloud Data, Hardware Resources, Compression Method, Peak Signal-to-noise Ratio Values, Compression Algorithm, Time Compression, Dynamic Tree, Coding Tree, Lossless Compression, Compressed Layer, Original Point Cloud, Entropy Coding, Code Assignment, Point Cloud Reconstruction, Frequency Analysis, Lookup Table, Data Transmission

**Author Keywords:** Sensor applications, 3-D light detection and ranging (LiDAR), compression, field-programmable gate array (FPGA), octree

undefined
## SECTION I. Introduction

Autonomous driving is reshaping the automotive industry, driving the demand for advanced technologies capable of providing accurate and efficient environmental perception. With light detection and ranging (LiDAR) sensors becoming a cornerstone for generating high-resolution 3-D maps of the surroundings [^1], which are essential for tasks, such as obstacle detection and path planning, the challenge of efficiently managing these data has become increasingly important.

One promising approach is the use of octrees [^2], a tree data structure that partitions 3-D space into smaller cubes or regions. This structure simplifies the storage, access, and processing of large datasets, while also enabling effective downsampling of point clouds. For applications requiring data storage or data transmission, octrees offer good compression ratios (CRs) compared to the original point cloud. This reduction can be further enhanced by applying compression techniques to the bitstream generated by the octree.

The geometry based point cloud compression (G-PCC) [^3] standard uses octrees as the core data structure for efficiently encoding spatial information, applying arithmetic coding to the output bitstream to achieve higher CRs. Similarly, the point cloud library (PCL) [^4], a widely used library for point cloud processing, provides compression methods that leverage octree implementations to eliminate spatial and temporal redundancies in the 3-D data. However, despite their efficiency in achieving high CRs with minimal or no data loss, generating octrees from LiDAR sensors can still result in high memory utilization and computational overhead when handling large datasets.

Since most sensors operate at a frequency of at least 10 Hz, it is crucial to ensure that point cloud collection, octree generation, compression, and data transmission are completed within 100 ms to match the frame generation rate and avoid frame drops. This letter presents FOG-zip, a lossless bitstream compression method tailored for octree-encoded LiDAR data generated by the fast octree generator (FOG) [^5] octree implementation. FOG-zip employs a Huffman coding algorithm that has been specifically adapted and fully optimized for efficient deployment on field-programmable gate array (FPGA). Experimental results demonstrate that FOG-zip can achieve a CR of 55.8 for the Velodyne HDL-64, while maintaining the frame compression time as low as 38.3 ms, which is 2.6 times below the frame rate of the sensor.

## SECTION II. Octree Representation and Bitstream Compression

### A. Octree Representation

The generation of an octree [^6], as illustrated Fig. 1, consists in creating a hierarchical data structure that recursively divides 3-D space into eight smaller cubic regions, called octants. This process continues until a predefined condition, such as a maximum depth or minimum size (resolution) is reached. The resulting octants, or voxels (volumetric pixels), represent the smallest regions within the octree. Octrees are particularly efficient for representing sparse 3-D data, as they allocate nodes only for occupied or relevant regions, reducing the memory required to store the final output bitstream. The bitstream is typically created by traversing the tree in a specific order by using algorithms, such as the depth first search, and recording the occupation codes of each node. This traversal results in a serialized output that encodes the spatial distribution of all points.

![Figure 1](https://ieeexplore.ieee.org/mediastore/IEEE/content/media/7782634/11075636/11078905/roriz1-3588338-large.gif)

*Fig. 1. Data structure of an octree.*

### B. Bitstream Compression

Although the bitstream already provides a compact representation of the original 3-D space, additional techniques can further reduce its size. For instance, Kammerl et al. [^7] proposed a compression method that computes differences between consecutive octree frames using an exclusively-OR (XOR) operation, followed by integer arithmetic range encoding. Similarly, G-PCC [^3] uses a context-based entropy coding technique that adapts its predictions based on the current context of the data. Schnabel et al. [^8] introduced prediction techniques specifically designed for point-sampled geometry, utilizing local surface approximations to achieve high compression rates. Most recently, learning-based techniques have emerged to enhance compression efficiency [^9], [^10], [^11]. For instance, Huang et al. [^12] developed a conditional entropy model that learns the octree structure and predicts node occupancies, creating an optimized bitstream. While reducing octree's redundancy can increase CRs, their computational complexity often limits their use in real-time applications or on resource-constrained platforms.

Given the complexity of current state-of-the-art solutions, traditional compression techniques can be explored to compress octree bitstreams. Run-length encoding (RLE) compresses sequences of identical elements by replacing them with a single value and its count, making it effective for datasets with long runs of repeating values. Algorithms, such as LZ77 and LZ4, replace repeated patterns with references to earlier occurrences. While LZ77 is designed to maximize CRs, LZ4 prioritizes speed, making it ideal for real-time applications. Huffman encoding [^13] assigns variable-length codes to symbols based on their frequencies. By giving shorter codes to frequent symbols and longer codes to low-probability ones, Huffman encoding generates a lossless but highly compact bitstream optimized for the characteristics of the data.

## SECTION III. FOG-Zip Algorithm

FOG-zip is a compression algorithm designed to efficiently compress the bitstreams generated by FOG [^5], a solution that optimizes the creation of LiDAR octree structures and their corresponding bitstreams. FOG employs a multitree architecture to process multiple regions of 3-D space in parallel, leveraging FPGA technology to achieve low-latency performance. FOG-zip adds a lightweight compression layer to the FOG algorithm that aims to further reduce the size of the binary bitstream, while preserving the original efficiency of the algorithm.

### A. Software-Based Bitstream Compression

To identify the compression algorithm that delivers the best performance on octree-generated data, RLE, LZ4, LZ77, and Huffman encoding were evaluated using octree bitstreams generated by FOG. These algorithms were chosen for their widespread use in bitstream compression and their simplicity, making them suitable candidates for FPGA implementation alongside the FOG algorithm. The evaluation was performed using LiDAR datasets from different Velodyne sensors collected in distinct environments: the VLP-32 dataset corresponds to a sparse, off-road scenario, while the VLP-16 and HDL-64 datasets represent complex urban scenes with high spatial variability. Given the lossy nature of octree encoding, the spatial homogeneity of the environment significantly influences octree complexity and, consequently, the CR. More homogeneous scenes, such as the VLP-32 dataset, result in simpler octree structures with higher occupancy redundancy, reducing entropy and increasing the CR. In addition, octree parameters, such as maximum depth, affect CR by controlling the level of detail retained in the point cloud representation. The VLP-32 dataset was collected off-road. The compressed size (in KB) and CR were measured and compared to the original point cloud data size. As shown in Table 1, Huffman encoding consistently achieved the smallest compressed size and significantly outperformed LZ4, LZ77, and RLE, establishing it as the preferred method for FOG-zip.

![Figure 2](https://ieeexplore.ieee.org/mediastore/IEEE/content/media/7782634/11075636/11078905/roriz.t1-3588338-large.gif)

*Table 1*

### B. Hardware-Based Compression

The compression layer uses a scheme based on the Huffman coding algorithm. As shown in Fig. 2, this process is divided into three steps: (1) frequency analysis, (2) codebook creation and code assignment, and (3) encoding.

![Figure 3](https://ieeexplore.ieee.org/mediastore/IEEE/content/media/7782634/11075636/11078905/roriz2-3588338-large.gif)

*Fig. 2. Processing flow of FOG-zip compression algorithm.*

*1) Frequency Analysis:* In this step, the frequency of each unique symbol in the bitstream is tracked in a frequency table. Traditional Huffman-based methods calculate these frequencies by reading the entire bitstream, which can be computationally intensive, or by using predetermined tables based on prior data analysis. In FOG-zip, the frequency analysis of the octree bitstream and the creation of the 8-bit symbol frequency table are carried out in parallel with the octree generation process.

*2) Codebook Creation and Code Assignment:* In Huffman coding, prefix-free codes are generated to ensure that no code is a prefix of another. Typically, these codes are created dynamically by constructing a binary tree based on symbol frequencies. Symbols with higher frequencies are positioned closer to the root, resulting in shorter codes, while less frequent symbols are placed deeper in the tree, leading to longer codes. However, deploying dynamic binary trees in hardware can be complex and resource-intensive. To simplify this process and enhance execution performance, FOG-zip replaces the dynamic Huffman binary tree with a *Code Mapping Table* containing predetermined prefix-free codes that are assigned to each symbol based on their frequency. This approach eliminates the need for dynamic tree construction, resulting in a static structure that efficiently encodes all symbols in the octree bitstream.

The *Code Mapping Table* is organized into Tiers, each identified by a unique Tier ID. Within each Tier, FOG-zip assigns a fixed number of bits to represent the corresponding symbols. For example, in Tier 0, which handles the first four symbols, the resulting code consists of the Tier ID (0) plus two additional bits to represent the four most frequent symbols. Once the *Frequency Table* and *Code Mapping Table* are established, the *Codebook* is created, where each eight-bit symbol is assigned a unique codeword. Fig. 2 illustrates the processing flow of the FOG-zip algorithm. In the example, the symbol “00000100” appears 1643 times in the bitstream, while the symbol “11010110” appears only 50 times. Using the *Code Mapping Table*, the symbol “00000100” is mapped to the codeword “000,” while the symbol “11010110” is mapped to the codeword “10 000”.

*3) Encoding:* Since the *Code Mapping Table* is static and holds a fixed number of symbols (up to 256), the header of the encoded bitstream only contains the original symbols ordered by their frequency. With this, the original bitstream can be restored by replacing each codeword in the encoded data with its corresponding symbol from the *Code Mapping Table* present in the decoder, ensuring the symbol-to-code mapping is accurately reversed.

## SECTION IV. Evaluation

FOG-zip was implemented and evaluated on the ZCU104 Evaluation Kit from Xilinx, which features the Zynq UltraScale+ MPSoC. This MPSoC includes a quad-core Arm Cortex-A53 processor, an FPGA with 504 K logic cells, 1728 DSP slices, and 2 GB of DDR4 memory. The same datasets used in the preliminary results presented in Table 1 were employed for the evaluation, including execution performance, CR, peak signal-to-noise ratio (PSNR), and FPGA resource usage. FOG-zip was compared against the uncompressed octree generated by FOG, as well as the compressed octree created by the *OctreePointCloudCompression* library from the PCL, which provides structural and functional features aligned with this work. To ensure consistency, all methods were evaluated on the same platform. The configuration used in the PCL is summarized in Table 2, while for the FOG octree the *numberOfNodes* was set to 250 000, the *BBCoordinates* were defined as a cube-shaped bounding box with a 200 m edge centered on the sensor to include all points, and a *maxDepth* of 12, corresponding to a resolution of 5 cm. These parameters were chosen to produce similar results in terms of octree creation and original point cloud reconstruction, as discussed in [^5].

![Figure 4](https://ieeexplore.ieee.org/mediastore/IEEE/content/media/7782634/11075636/11078905/roriz.t2-3588338-large.gif)

*Table 2*

![Figure 5](https://ieeexplore.ieee.org/mediastore/IEEE/content/media/7782634/11075636/11078905/roriz.t3-3588338-large.gif)

*Table 3*

![Figure 6](https://ieeexplore.ieee.org/mediastore/IEEE/content/media/7782634/11075636/11078905/roriz.t4-3588338-large.gif)

*Table 4*

### A. Performance Evaluation and Hardware Resources

*Compression Time:* FOG-zip demonstrates significant improvements in compression time across all evaluated datasets compared to both PCL and FOG. For the VLP-16 dataset, FOG-zip processes a frame in 12.6 ms, achieving a reduction of 88.7% compared to PCL and 7.9% compared to FOG. For the VLP-32 dataset, it achieves a compression time of 16.1 ms, representing an improvement of 85.7% over PCL and 5.3% over FOG. Similarly, for the HDL-64 dataset, FOG-zip processes a frame in 38.3 ms, marking an 89.1% improvement over PCL and 3.0% over FOG.

*CR and PSNR:* FOG-zip achieves a CR of 31.5, 64.3, and 55.8 for the VLP-16, VLP-32, and HDL-64 datasets, respectively, representing reductions of 15.8%, 9.2%, and 7.6% compared to PCL. Regarding the PSNR, which quantifies the similarity between the original and reconstructed point clouds, both FOG and FOG-zip share the same value, as the distortion is introduced in the octree generation step. On the VLP-16 dataset, it achieves a PSNR of 57.7 dB, representing an 18.6% reduction compared to PCL. For the VLP-32 and HDL-64 datasets, the PSNR values are 56.9 and 60.0 dB, corresponding to reductions of 21.3% and 14.7%, respectively, with HDL-64 showing the smallest quality loss.

*Hardware Resources:* The compression layer of FOG-zip adds a small increase in hardware resource utilization, particularly in terms of lookup tables (LUTs), flip-flops (FFs), and multiplexers (MUXes). FOG-zip requires 114029 LUTs, utilizing 49.49% of the total available resources, which represents an increase of 7.06% compared to FOG. Similarly, the utilization of FFs rises from 33 926 (7.36% of the available resources) with FOG to 10.89% with FOG-zip, an increase of 3.53%. The MUX utilization exhibits a similar pattern, with FOG-zip requiring 36.03% of the available resources, representing an 8.06% increase compared to the 27.97% used by FOG.

### B. Discussion

The evaluation of FOG-zip highlights its advantages and tradeoffs compared to PCL and FOG. Regarding compression time, FOG-zip significantly outperforms both across all datasets. This improvement comes primarily from FOG-zip's parallel execution with FOG, which avoids adding extra processing overhead. In addition, the encoded bitstream generated by FOG-zip is smaller, reducing time required for processing and transmission. In terms of PSNR, as discussed in [^5], the octree generated by PCL retains more detailed information about the original point cloud. However, FOG-zip achieves PSNR values exceeding 55 dB, indicating high-quality lossy compression, as shown in Fig. 3. While lossless methods typically exceed 70 dB, FOG-zip is classified as lossy, not due to its inherently lossless compression layer but because of the lossy octree generation process in FOG. Similarly, regarding CR, FOG-zip achieves values significantly higher than FOG but slightly lower than PCL (when compression is applied). This is because FOG's output is not a compressed bitstream, and PCL uses more complex entropy coding, reducing the overall encoded size. FOG-zip follows the principles of the Huffman coding, however;* it removes the need to construct a temporary Huffman tree by using a deterministic prefix-free *Code Mapping Table*. This allows for faster code assignment and ensures a consistent encoding and decoding process. However, this method may lead to suboptimal compression, as it may add more bits to the encoded bitstream than necessary. Compared to the original Huffman code symbols, FOG symbol codes can also grow rapidly in datasets with numerous unique or low-frequency symbols. Despite this, FOG-zip can be used in applications where fast encoding and decoding is a requirement, and it can fit in embedded platforms since it is simpler to deploy.

![Figure 7](https://ieeexplore.ieee.org/mediastore/IEEE/content/media/7782634/11075636/11078905/roriz3-3588338-large.gif)

*Fig. 3. Comparison of original and decompressed point clouds using FOG-zip with a 12-depth octree. (a) Original point cloud. (b) Reconstructed point cloud.*

## SECTION V. Conclusion

This letter introduced FOG-zip, an algorithm designed to integrate lossless compression into octree-generated bitstreams for LiDAR data, tested within the FOG framework. The algorithm uses a simplified Huffman coding-based approach that relies on a static prefix-free *Code Mapping Table* instead of creating a dynamic Huffman tree. This simpler approach is optimized for FPGA implementation, achieving reduced compression time and acceptable encoded bitstream sizes. The evaluation results highlight the tradeoffs and benefits of FOG-Zip, demonstrating its suitability for real-time applications. Future work will focus on enhancing the compression layer, including exploring additional layers to improve the overall CR. Moreover, FOG-zip's performance could be evaluated in autonomous driving applications, such as object detection, to determine whether its slightly lower PSNR impacts performance in real-world scenarios.

## References

[^1]: Y. Li and J. Ibanez-Guzman, “LiDAR for autonomous driving: The principles, challenges, and trends for automotive LiDAR and perception systems,” IEEE Signal Process. Mag., vol. 37, no. 4, pp. 50–61, Jul. 2020. [IEEE](https://ieeexplore.ieee.org/document/9127855) [Google Scholar](https://scholar.google.com/scholar?as_q=LiDAR+for+autonomous+driving%3A+The+principles%2C+challenges%2C+and+trends+for+automotive+LiDAR+and+perception+systems&as_occt=title&hl=en&as_sdt=0%2C31)

[^2]: R. Roriz, H. Silva, F. Dias, and T. Gomes, “A survey on data compression techniques for automotive LiDAR point clouds,” Sensors, vol. 24, no. 10, pp. 16–20, 2024. [DOI](https://doi.org/10.3390/s24103185) [Google Scholar](https://scholar.google.com/scholar?as_q=A+survey+on+data+compression+techniques+for+automotive+LiDAR+point+clouds&as_occt=title&hl=en&as_sdt=0%2C31)

[^3]: D. Graziosi, O. Nakagami, S. Kuma, A. Zaghetto, T. Suzuki, and A. Tabatabai, “An overview of ongoing point cloud compression standardization activities: Video-based (V-PCC) and geometry-based (G-PCC),” APSIPA Trans. Signal Inf. Process., vol. 9, no. 1, pp. 9–13, 2020. [DOI](https://doi.org/10.1017/ATSIP.2020.12) [Google Scholar](https://scholar.google.com/scholar?as_q=An+overview+of+ongoing+point+cloud+compression+standardization+activities%3A+Video-based+%28V-PCC%29+and+geometry-based+%28G-PCC%29&as_occt=title&hl=en&as_sdt=0%2C31)

[^4]: R. B. Rusu and S. Cousins, “3D is here: Point cloud library (PCL),” in Proc. IEEE Int. Conf. Robot. Automat., 2011, pp. 1–4. [IEEE](https://ieeexplore.ieee.org/document/5980567) [Google Scholar](https://scholar.google.com/scholar?as_q=3D+is+here%3A+Point+cloud+library+%28PCL%29&as_occt=title&hl=en&as_sdt=0%2C31)

[^5]: R. Roriz, D. Costa, M. Ekpanyapong, and T. Gomes, “FOG: Fast octree generator for LiDAR point clouds,” IEEE Sens. Lett., vol. 9, no. 1, Jan. 2025, Art. no. 6001304. [IEEE](https://ieeexplore.ieee.org/document/10816469) [Google Scholar](https://scholar.google.com/scholar?as_q=FOG%3A+Fast+octree+generator+for+LiDAR+point+clouds&as_occt=title&hl=en&as_sdt=0%2C31)

[^6]: D. Meagher, “Geometric modeling using octree encoding,” Comput. Graph. Image Process., vol. 19, no. 2, pp. 129–147, 1982. [DOI](https://doi.org/10.1016/0146-664X(82)90104-6) [Google Scholar](https://scholar.google.com/scholar?as_q=Geometric+modeling+using+octree+encoding&as_occt=title&hl=en&as_sdt=0%2C31)

[^7]: J. Kammerl, N. Blodow, R. B. Rusu, S. Gedikli, M. Beetz, and E. Steinbach, “Real-time compression of point cloud streams,” in Proc. IEEE Int. Conf. Robot. Automat., 2012, pp. 778–785. [IEEE](https://ieeexplore.ieee.org/document/6224647) [Google Scholar](https://scholar.google.com/scholar?as_q=Real-time+compression+of+point+cloud+streams&as_occt=title&hl=en&as_sdt=0%2C31)

[^8]: R. Schnabel and R. Klein, “Octree-based point-cloud compression,” in Proc. 3rd Eurographics/IEEE VGTC Conf. Point-Based Graph., 2006, p. 111–121. [Google Scholar](https://scholar.google.com/scholar?as_q=Octree-based+point-cloud+compression&as_occt=title&hl=en&as_sdt=0%2C31)

[^9]: C. Fu, G. Li, R. Song, W. Gao, and S. Liu, “OctAttention: Octree-based large-scale contexts model for point cloud compression,” in Proc. AAAI Conf. Artif. Intell., 2022, pp. 625–633. [DOI](https://doi.org/10.1609/aaai.v36i1.19942) [Google Scholar](https://scholar.google.com/scholar?as_q=OctAttention%3A+Octree-based+large-scale+contexts+model+for+point+cloud+compression&as_occt=title&hl=en&as_sdt=0%2C31)

[^10]: S. Biswas, J. Liu, K. Wong, S. Wang, and R. Urtasun, “MuSCLE: Multi sweep compression of LiDAR using deep entropy models,” in Adv. Neural Inf. Process. Syst., 2020, pp. 15335–15346. [Google Scholar](https://scholar.google.com/scholar?as_q=MuSCLE%3A+Multi+sweep+compression+of+LiDAR+using+deep+entropy+models&as_occt=title&hl=en&as_sdt=0%2C31)

[^11]: Z. Que, G. Lu, and D. Xu, “VoxelContext-Net: An octree based framework for point cloud compression,” in Proc. IEEE/CVF Conf. Comput. Vis. Pattern Recognit., 2021, pp. 6038–6047. [IEEE](https://ieeexplore.ieee.org/document/9578231) [Google Scholar](https://scholar.google.com/scholar?as_q=VoxelContext-Net%3A+An+octree+based+framework+for+point+cloud+compression&as_occt=title&hl=en&as_sdt=0%2C31)

[^12]: L. Huang, S. Wang, K. Wong, J. Liu, and R. Urtasun, “OctSqueeze: Octree-structured entropy model for LiDAR compression,” in Proc. IEEE/CVF Conf. Comput. Vis. Pattern Recognit., Jun. 2020, pp. 1310–1320. [IEEE](https://ieeexplore.ieee.org/document/9157381) [Google Scholar](https://scholar.google.com/scholar?as_q=OctSqueeze%3A+Octree-structured+entropy+model+for+LiDAR+compression&as_occt=title&hl=en&as_sdt=0%2C31)

[^13]: D. A. Huffman, “A method for the construction of minimum-redundancy codes,” Proc. IRE, vol. 40, no. 9, pp. 1098–1101, 1952. [IEEE](https://ieeexplore.ieee.org/document/4051119) [Google Scholar](https://scholar.google.com/scholar?as_q=A+method+for+the+construction+of+minimum-redundancy+codes&as_occt=title&hl=en&as_sdt=0%2C31)

### Additional References