Quadtree-guided 3-D interpolation of irregular sonar data sets

Bottom-penetrating sonar can be used to visualize large areas, for example by normal logging and printing of collected pings. In many applications, it is necessary to obtain an impression of three-dimensional (3-D) structures, but this is not easy because of the irregular spatial sampling due to coarse ship trajectories. Normally, the ping map and the ping data, cover only a very small part of a region of interest. In this paper, we describe a new method for interpolating irregularly spaced sonar data. The basic idea is to use a two-dimensional quadtree of the ping map in order to guide the 3-D interpolation process: since gaps between pings become smaller at higher tree levels, the volume can be filled by marking neighborhood relations in the quadtree and interpolating available pings when they become neighbors. Different marking schemes and their central processing unit times are compared. In the interpolation process, we apply cross correlations of ping data in order to construct continuity of sloping reflections. Our results show that excellent results can be obtained on real sonar data sets, even for volumes filled for less than 7%, for which processing times are reasonable even for large areas, and that the interpolated data can be used for volumetric interactive visualization.