A Multiresolution Grid Structure Applied to Seafloor Shape Modeling

Wojciech Maleika, Michal Koziarski, Pawel ForczmanskiIsprs Int. J. geo inf 2018 · DOI

TL;DR

This paper introduces a novel multiresolution depth grid structure for storing bathymetric data, offering significant data reduction while maintaining high reconstruction accuracy. This approach adapts grid resolution to seafloor complexity, enabling efficient storage and processing of large-scale hydrographic surveys.

What Problem Does This Paper Address?

Accurate seafloor mapping is crucial for safe navigation and various marine applications. Traditional methods often rely on regular grids, which can lead to massive data volumes, especially for high-resolution surveys. This poses challenges for data storage, transmission, retrieval, and processing. While existing methods aim to reduce data size, many struggle with maintaining accuracy, especially for complex seafloor features, or are not well-suited for the dense data generated by modern multibeam echosounders (MBESs). The International Hydrographic Organization (IHO) sets stringent accuracy standards for hydrographic surveys, further emphasizing the need for efficient yet accurate data representation.

Methods

The core contribution of this paper is the development of a "multiresolution depth grid" data structure and associated algorithms. This structure represents seafloor depth data using a hierarchical grid where the resolution varies based on local terrain complexity.

The process involves:

  • Encoding (ENCODEGRID): Input data is processed in 32x32 element blocks. For each block, the algorithm calculates the difference between the average value and the maximum/minimum values within the block. If this difference is within a predefined "Parental Error" (PE) threshold, the block is recursively decomposed into four smaller sub-blocks, and the process repeats. If the error exceeds the PE, the current block (or sub-block) is stored as a single value (average depth) with its associated level of decomposition. This adaptive decomposition ensures that areas with high depth variability are represented with smaller blocks (higher resolution), while flatter areas use larger blocks (lower resolution).
  • Decoding (RECONSTRUCTGRID): This is the inverse process. Stored blocks are read, and the data is expanded back into a full 32x32 grid based on the stored average value and level. These expanded blocks are then concatenated to reconstruct the original grid structure.

The key novelty lies in the adaptive resolution based on error tolerance (PE) and the block-based recursive decomposition, which allows for efficient storage and variable density representation.

Datasets

The authors used real-world bathymetric data collected from the Szczecin Lagoon and Pomeranian Bay (Poland). Four benchmark surfaces were selected to represent diverse seafloor characteristics:

  • Gate Area: Features an artificial riffle and significant depth changes.
  • Anchorage Area: Characterized by a flat seabed.
  • Swinging Area: Exhibits rapid and irregular depth changes due to deepening works.
  • Wrecks Area: A relatively flat area with several distinct objects (car wrecks).

These surfaces were initially provided as regular square grids and were used to evaluate the performance of the proposed multiresolution grid structure.

Key Insights and Ideas

  • Adaptive Resolution is Key: The most significant insight is that a variable grid resolution, driven by local depth variations and a defined error tolerance (PE), is highly effective for both data reduction and accurate representation of complex seafloor topography.
  • Balancing Compression and Accuracy: The method successfully balances data compression with the requirement for high reconstruction accuracy, as defined by the PE. This is crucial for hydrographic applications where safety is paramount.
  • Handling Complex Features: The multiresolution grid excels at precisely describing small, irregular objects (like wrecks) and areas of sudden depth changes, which are critical for navigation safety.
  • Efficiency of Block-Based Processing: The recursive, block-based approach is computationally efficient and amenable to parallelization, making it suitable for processing large datasets.
  • IHO Standards Compliance: The method's ability to meet IHO accuracy standards (e.g., PE of 5 cm, which is significantly stricter than the recommended 30 cm for some areas) is a strong validation of its practical utility.

Key Results

The experiments demonstrated significant data reduction capabilities:

  • Gate Area: Compression Ratios (CR) ranged from 5.5% (for PE = 1 cm) to 93.6% (for PE = 25 cm).
  • Anchorage Area: CR was high, from 70.8% (PE = 1 cm) to 96.0% (PE = 25 cm), due to its flat nature.
  • Swinging Area: CR varied from 20.1% (PE = 1 cm) to 96.4% (PE = 25 cm), reflecting its complex topography.
  • Wrecks Area: CR was 49.5% (PE = 1 cm) and reached 98.1% (PE = 25 cm).

For a practical PE of 5 cm, the compression ratio generally reached around 60-75% for flatter surfaces and 90-95% for more varied surfaces. The visual quality of reconstruction for PE ≤ 10 cm was found to be almost perfect.

Limitations and Future Work

  • Comparison with Frequency-Domain Methods: The paper acknowledges that frequency-domain compression methods (like DCT, Wavelets, PCA) can achieve higher compression ratios. However, these methods typically require uniform grid data and may not adapt as well to the variable density needs of seafloor representation.
  • Data Source Dependency: The current method relies on input data being in a regular grid format. The authors suggest that directly processing raw MBES measurement data, which is often more densely distributed, could lead to even better results and more flexible grid creation.
  • Static PE: The Parental Error (PE) is currently set as a static value for the entire surface. Future work could explore making PE dependent on factors like depth, local seafloor form, or the function of a sub-area (e.g., port vs. channel) for more nuanced representation.
  • Combined Approaches: The authors propose exploring combined methods that integrate the multiresolution grid structure with frequency-domain compression techniques to potentially achieve even greater data reduction while maintaining accuracy.

Summary updated

BibTeX
@article{maleika2018multiresolution,
  author = {Wojciech Maleika and Michal Koziarski and Pawel Forczmanski},
  title = {{A Multiresolution Grid Structure Applied to Seafloor Shape Modeling}},
  journal = {Isprs Int. J. geo inf},
  year = {2018},
  doi = {10.3390/ijgi7030119},
}

Loading related content...

Figure