Memory-Efficient Boundary Map for Large-Scale Occupancy Grid Mapping

Benxu Tang; Yunfan Ren; Yixi Cai; Fanze Kong; Wenyi Liu; Fangcheng Zhu; Longji Yin; Liuyu Shi

Figure 1: MAV performing a long-range autonomous navigation task in an unknown multi-level building, utilizing the proposed mapping framework. (a) Accumulated point cloud and the MAV trajectory at the end of the task, also visualized from multiple viewpoints in (a1), (a2), and (a3). (b) Hardware configuration of the MAV platform used to perform the navigation task. (c) Overview of the resulting global boundary map, which forms a closed structure. As the viewpoint is external, the low-dimensional property of the map is not evident. To better illustrate its internal structure, the map is sliced along the orange plane. (d) Cross-sectional view revealing the hollow interior of the boundary map. Voxels stored in boundary map are classified into three types, visualized in distinct colors. The green voxels lie on the interior layer of the map, having an occupancy state of free. The grey and blue voxels are located on the exterior layer, with occupancy states of occupied and unknown, respectively.

Figure 2: (a) A uniform occupancy grid where each voxel is classified into one of three states: free, unknown, or occupied, represented by green, blue, and grey, respectively. For clarity, only the voxels along the cross-sectional plane are shown, with the remaining voxels represented by a simplified shape. (b) The boundary surface layer of the free space, highlighted in red, which separates the free regions from the adjacent occupied or unknown regions. (c) Our proposed boundary map, which includes the free, unknown and occupied voxels that neighboring the boundary surface layer.

Figure 3: The boundary map is composed by boundary voxels , which include boundary interior voxels (

\displaystyle\mathbf{b}_{\mathrm{int}}

) and boundary exterior voxels (

\displaystyle\mathbf{b}_{\mathrm{ext}}

). Boundary interior voxels are free voxels neighboring unknown or occupied voxel(s), and are visualized in green. Boundary exterior voxels include boundary exterior (unknown) voxels (

\displaystyle\mathbf{b}_{\mathrm{ukn}}

) and boundary exterior (occupied) voxels (

\displaystyle\mathbf{b}_{\mathrm{occ}}

), represented in blue and grey, respectively. Boundary exterior (unknown) voxels have an unknown occupancy state and neighboring free voxel(s). Boundary exterior (occupied) voxels are all voxels whose occupancy state is occupied.

Figure 4: Occupancy state determination based on our boundary map. The diagram shows the determination process for several example query voxels (nos. 1–5). If the query voxel is located exactly on the boundary map, the query voxel state can be determined by type of the boundary voxel directly (query voxel no. 1). Otherwise, we search along the

\displaystyle z^{+}

direction (i.e., a representative direction for illustration propose) to find the nearest boundary voxel on the boundary map, denoted as

\displaystyle\mathbf{b}_{{nn}}

. If

\displaystyle\mathbf{b}_{{nn}}

is a boundary interior voxel

\displaystyle\mathbf{b}_{\mathrm{int}}

, the query voxel is determined as free (query voxels no. 2 and 3). If the

\displaystyle\mathbf{b}_{{nn}}

is a boundary exterior voxel

\displaystyle\mathbf{b}_{\mathrm{ext}}

(i.e., either unknown

\displaystyle\mathbf{b}_{\mathrm{ukn}}

or occupied

\displaystyle\mathbf{b}_{\mathrm{occ}}

), the query voxel is determined as unknown (query voxels no. 4 and 5). If

\displaystyle\mathbf{b}_{{nn}}

does not exist, the query voxel is determined as unknown too (query voxel no. 6).

Figure 5: The boundary map, which consists of boundary voxels in the three-dimension (3D), is maintained in a two-dimensional (2D) data structure. Without loss of generality,

\displaystyle z

-axis is selected as the projection axis for illustration purpose in the manuscript. The boundary map is projected along the

\displaystyle z

-axis onto the

\displaystyle(x,y)

-plane. Then a hash-based 2D grid map is maintained on the

\displaystyle(x,y)

-plane where each grid cell stores boundary voxels projected onto that cell. Each boundary voxel in the grid cell is represented by its

\displaystyle z

-coordinate and a type indicator indicating its type (i.e.,

\displaystyle\mathbf{b}_{\mathrm{int}}

,

\displaystyle\mathbf{b}_{\mathrm{ukn}}

, and

\displaystyle\mathbf{b}_{\mathrm{occ}}

). The numbers in the figure correspond to the

\displaystyle z

-coordinates of the boundary voxels.

Figure 6: Overview of the proposed global-local mapping framework. The system takes odometry and sensor scans as inputs. The pink block illustrates the map structure, consisting of a global map (the low-dimensional boundary map) and a local map (a dense uniform occupancy grid map). The mapping framework is updated once every new odometry and sensor data arrive. For each point in the new scan, the New Scan Ray Casting performs ray casting and probabilistic occupancy update on the local occupancy grid map. The new odometry is used to determine if the local map needs to slide and, if so, compute the slide-in region

\displaystyle\mathcal{S_{I}}

and slide-out region

\displaystyle\mathcal{S_{O}}

of the local map. If a slide occurs, the occupancy state within the slide-out region of the local map is updated to the global map by the Incremental Boundary Map Update (green block), while the occupancy state within the slide-in region of the local map is loaded from the global map via the Local Occupancy Grid Map Update (brown block).

Figure 7: Illustration of the local and global map update if a slide occurs in Figure 6 . (a) The global map (boundary map) and local map (a uniform occupancy grid map) before sliding, and the local map region before and after the sliding. (b) The local map slides to the new position and updates the occupancy state within the map region (including both slide-in region and the overlapped region) by ray casting all points in the new LiDAR scan ( New Scan Ray Casting ). Meanwhile, boundary voxels in the slide-out region are computed and updated to the global boundary map ( Incremental Boundary Map Update ). (c) From the global boundary map, occupancy states within the slide-in region are loaded. (d) The loaded occupancy states within the slide-in region are fused into the local map ( Local Occupancy Grid Map Update ).

Figure 8: Illustration of step (c) in Figure 7 : loading occupancy states within the slide-in region from the global boundary map. (a) Projecting the slide-in region

\displaystyle\mathcal{S_{I}}

to the

\displaystyle(x,y)

-plane, denoted as

\displaystyle\mathcal{S}_{\mathcal{I}}^{2d}

. (b) For each 2D grid cell within

\displaystyle\mathcal{S}_{\mathcal{I}}^{2d}

, retrieve the boundary voxels saved in the global boundary map. (c) Constructing a dense occupancy grid tile consisting of free voxels and occupied voxels above the 2D grid cell but within the slide-in region. Voxels not encoded in the tile are unknown voxels requiring no processing. (d) This procedure is repeated for all 2D grid cells within

\displaystyle\mathcal{S}_{\mathcal{I}}^{2d}

, resulting in a dense occupancy grid map within the slide-in region

\displaystyle\mathcal{S_{I}}

. This map contains only free and occupied voxels and is finally fused to the local map in step (d) in Figure 7 .

Figure 9: Illustration of the search direction selection in occupancy state querying in the proposed global-local mapping framework. The search direction is selected such that it does not intersect with the local map. For query voxels in regions I and II (voxel no. 1 and 3), the search direction can be selected as

\displaystyle z^{+}

or

\displaystyle z^{-}

, as neither direction intersects with the local map. For query voxels in regions III and IV (voxel no. 2 and 5), only one direction can be chosen, which is the one not intersecting with the local map. For query voxels in region V (voxel no. 4), which lie within the local map, the occupancy state is directly retrieved from the local map.

Figure 10: The HKU private dataset hku_campus . (a) The trajectory and accumulated point cloud scans. The mapping results of our method are shown in (b) and (c), focusing on the boundary map (i.e., the global map). The mapped volume is referred to the volume enclosed by the boundary. (b) provides an overview of the boundary map, while (c) presents interior views alongside the corresponding real-world image. For visualization purposes, only boundary exterior voxels are rendered, including boundary exterior (unknown) voxels (colored in blue) and boundary exterior (occupied) voxels (colored in grey). Boundary interior voxels, which are adjacent to the boundary exterior voxels, are omitted to improve visual clarity.

Sequence	Environment Scale	Traveled	Number	Average Points	Mapped	Sensor	Local Map
	(Bounding Box)	Distance	of	Number	Volume	Range	Size
	( $\displaystyle\mathrm{m}^{3}$ )	( $\displaystyle\mathrm{m}$ )	Scans	(per scan)	( $\displaystyle\mathrm{m}^{3}$ )	( $\displaystyle\mathrm{m}$ )	( $\displaystyle\mathrm{m}^{3}$ )
ford_1	$\displaystyle\mathrm{11,416\times 8,060\times 94}$	16,639	7,757	41,108	3,843,031	65	$\displaystyle\mathrm{130\times 130\times 16}$
ford_2	$\displaystyle 11,584\times 8,027\times 102$	24,064	10,713	40,241	4,781,935	65	$\displaystyle\mathrm{130\times 130\times 16}$
ford_3	$\displaystyle 6,659\times 3,860\times 85$	9,558	8,692	42,501	2,905,112	65	$\displaystyle\mathrm{130\times 130\times 16}$
kitti_00	$\displaystyle 653\times 586\times 58$	3,724	4,541	121,495	243,903	45	$\displaystyle\mathrm{90\times 90\times 6}$

Table 1: Details of datasets used in the benchmark experiments.

Figure 11: Memory consumption (in MB) of UG (Uniform Grid), HG (Hash Grid), Octo (Octomap), UFO (UFOMap), D-Map, and our method on the ford_1 , ford_2 , ford_3 , kitti_00 , and kitti_02 sequences. The percentage shown in red indicates the memory reduction of our method relative to the best of the rest methods in comparison. For our method, we also show the memory breakdown of the local and global maps, respectively. N/A indicates that the method failed due to memory consumption exceeding the limit.

Figure 12: Continuation of Figure 11 : results on the remaining sequences, hku_campus and uav_flight .

Resolution (m)	0.8	0.4	0.2	0.1	0.8	0.4	0.2	0.1	0.8	0.4	0.2	0.1
	ford_1				ford_2				ford_3
Uniform Grid	11.56	$\displaystyle\times$	$\displaystyle\times$	$\displaystyle\times$	11.89	$\displaystyle\times$	$\displaystyle\times$	$\displaystyle\times$	9.74	$\displaystyle\times$	$\displaystyle\times$	$\displaystyle\times$
Hash Grid	12.08	33.16	$\displaystyle\times$	$\displaystyle\times$	11.38	30.46	$\displaystyle\times$	$\displaystyle\times$	12.36	36.04	196.23	$\displaystyle\times$
Octomap	80.01	176.94	498.39	$\displaystyle\times$	77.14	163.72	461.71	$\displaystyle\times$	80.80	173.28	466.49	1353.29
UFOMap	61.69	119.20	246.68	511.86	58.39	113.10	278.57	480.39	62.60	122.40	249.38	528.85
D-Map	13.60	53.83	109.16	$\displaystyle\times$	13.38	49.55	92.71	$\displaystyle\times$	14.18	57.60	117.86	493.75

Table 2: Comparison of map update time (ms) at different resolutions. The best and second-best results in each setting are highlighted using distinct tint colors.

Figure 13: Breakdown of map update time of our method in sequence ford_2 , kitti_00 and hku_campus , respectively.

Resolution (m)	0.8	0.4	0.2	0.1	0.8	0.4	0.2	0.1	0.8	0.4	0.2	0.1
	ford_1				ford_2				ford_3
Uniform Grid	10510.9	$\displaystyle\times$	$\displaystyle\times$	$\displaystyle\times$	25133.8	$\displaystyle\times$	$\displaystyle\times$	$\displaystyle\times$	41.18	$\displaystyle\times$	$\displaystyle\times$	$\displaystyle\times$
Hash Grid	86.28	123.12	$\displaystyle\times$	$\displaystyle\times$	84.11	132.83	$\displaystyle\times$	$\displaystyle\times$	101.73	288.19	173169.0	$\displaystyle\times$
Octomap	373.56	512.90	606.18	$\displaystyle\times$	370.64	490.14	634.95	$\displaystyle\times$	425.05	487.36	636.77	137039.0
UFOMap	174.16	227.98	314.85	39516.2	182.43	234.03	313.96	82606.9	155.77	211.11	295.76	567.18
D-Map	654.38	784.49	903.17	$\displaystyle\times$	680.72	820.07	899.19	$\displaystyle\times$	616.85	758.78	859.91	142607.3

Table 3: Comparison of average map query time (ns) at different resolutions.

Resolution (m)	0.8	0.4	0.2	0.1	0.8	0.4	0.2	0.1	0.8	0.4	0.2	0.1
	ford_1				ford_2				ford_3
Ours	99.99	99.99	99.98	99.94	99.98	99.99	99.98	99.94	99.97	99.98	99.98	99.92
D-Map	94.27	95.66	96.06	$\displaystyle\times$	95.10	96.48	96.55	$\displaystyle\times$	93.66	95.42	95.19	94.70

Table 4: Map Accuracy (%) of our method and D-Map with Octomap as the ground truth.

Figure 14: Illustration of a long-range autonomous navigation task conducted in a multi-level building. Starting from an initial position, the MAV sequentially navigated to a series of manually defined goals, each specified after the previous one was reached. All goals were intentionally placed beyond the MAV’s current local map to enforce long-range navigation. In total, eight goals were assigned and visited. After reaching the final goal (Goal No.8), the MAV was instructed to autonomously plan and execute a return trajectory to the starting position. (a) Locations of the eight goals. Goals No.1–5 are located on level 1, while Goals No.6–8 are on level 2. The figure also demonstrates the accumulated point cloud and the MAV trajectory upon reaching Goal No.8, with the trajectory color-coded by altitude. (b) Return trajectory from Goal No.8 to the starting position, highlighted in orange. The MAV followed the shortest path computed using the A* search algorithm based on the proposed global-local mapping framework. The figure also illustrates the local map at a position selected on the return trajectory, highlighting its limited spatial range compared to the global map. (c) Sample images of the MAV captured during the mission, with their corresponding locations on the trajectory marked in (a) and (b). Images (c1)–(c3) were taken during the outbound flight to Goal No.8, with locations annotated in (a). Images (c4) and (c5) were captured during the return flight and correspond to locations indicated in (b).

Figure 15: Complete MAV flight trajectory, including the outbound trajectory to Goal No.8 and the return to the starting position, overlaid on a Google Maps satellite image. The trajectory is color-coded by altitude.

Figure 16: Illustration of how the MAV navigates itself to a long-range goal, using the segment from Goal No.2 to Goal No.3 as an example. (a) The accumulated point cloud and trajectory when reaching Goal No.2. (b) Visualization of the corresponding mapping framework at this moment, including the global map (i.e., boundary map) and the local map. The free, unknown and occupied voxels are colored by green, blue and grey, respectively. (c) Autonomous navigation process toward Goal No.3. The red dot marks the location of Goal No.3. The green dot indicates the selected target on the frontier. The green line shows the computed A* path to the frontier target. For clarity, both the global and local maps are rendered semi-transparent. (d) Accumulated point cloud and trajectory upon reaching Goal No.3.

Figure 17: (a) Illustration of the autonomous navigation process from Goal No.5 toward Goal No.6. (b) Visualization of the accumulated point cloud and the MAV trajectory upon reaching Goal No.6. The trajectory is color-coded by altitude.

Figure 18: Memory consumption (MB) of our method and other baselines during the flight.

Environment Scale (Bounding Box) ( $\displaystyle\mathrm{m}^{3}$ )	$\displaystyle 277\times 123\times 19$
Travel Distance ( $\displaystyle\mathrm{m}$ )	1,247.5
Mapped Volume ( $\displaystyle\mathrm{m}^{3}$ )	29153.4
Number of Scans	8,291
Average Point Number (per scan)	16,252.1

Table 5: Details of the Real-world Flight

Figure 19: Map update time of our method and other baselines during the flight.

Projection Axis	Memory (MB)	Query (ns)	$\displaystyle\bar{N}_{\text{bv/q}}$
$\displaystyle x$	637.48	82.84	33.47
$\displaystyle y$	669.44	73.45	21.82
$\displaystyle z$	1450.18	56.78	3.02

Table 6: Impact of different projection axis choices on memory consumption and query time for the kitti_02 sequence at a map resolution of 0.1m. The benchmark experiments in Section 8 use the

\displaystyle z

-axis as the projection axis.

Figure 20: Illustration of the relationship between occupancy probability and its log-odds value.

Figure 21: (a) Sample images from sequence 2011_09_29_drive_0071 , where dynamic objects (e.g., vehicles, pedestrians and bicycles) are highlighted by boxes. (b) Mapping results of the sequence obtained by Octomap, our method and D-Map, where all occupied voxels are visualized. Since the baseline methods including Uniform Grid, Hash Grid and UFOMap adopt the same update process as Octomap, they are expected to produce identical mapping results with Octomap.

Memory-Efficient Boundary Map for Large-Scale Occupancy Grid Mapping

Abstract

Figures & tables

Appendix

Occupancy Grid Mapping

D-BDM: A Direct and Efficient Boundary-Based Occupancy Grid Mapping Framework for LiDARs

VEOcc: Voxel-Centric Online Semantic Occupancy Prediction For Embodied Scene Understanding

Large-Scale Continuous Occupancy Mapping via Variance-Weighted Submap Joining

Abstract

Occupancy Grid Mapping

Explore similar work

D-BDM: A Direct and Efficient Boundary-Based Occupancy Grid Mapping Framework for LiDARs

VEOcc: Voxel-Centric Online Semantic Occupancy Prediction For Embodied Scene Understanding

Large-Scale Continuous Occupancy Mapping via Variance-Weighted Submap Joining