Using linear interpolation instead of binning

The linear-interpolation operator carries us from a uniform mesh to irregularly distributed data. Fundamentally we seek to solve the inverse problem to go the other direction. A nonlinear approach to filling in the missing data is suggested by the one-dimensional examples in Figures 14-15, where the PEF and the missing data are estimated simultaneously. The nonlinear approach has the advantage that it allows for completely arbitrary data positioning, whereas the two-stage linear approach forces the data to be on a uniform mesh and requires there not be too many empty mesh locations.

For addressing the nonlinear problem, we follow the approach we used in one dimension. The idea is to fit the data with linear interpolation $\bold 0\approx \bold L\bold h-\bold d$as well as smooth the map by minimizing the energy output of its own PEF, $\bold 0\approx \bold H\bold u = \bold U\bold h$.(Details of the mathematics, fitting problem, and method of solution led to the one-dimensional equations (42) and (43).) As in 1-D, linearizing and introducing constraints brings us to  

$$\begin{array} {lll} \bold 0 &\approx& \bold r_d \eq \bold L... ...old u + (\bold U\bold h \ {\rm or}\ \bold H\bold u)\end{array}$$ (30)

where $\bold d$ is the data d(x,y), $\bold L$ is linear interpolation, $\bold h$ is the modeled altitude h(x,y), $\bold H$ is convolution with altitude, $\bold u$ is a PEF, $\bold U$ is the operator of convolution with a PEF, and $\bold K$ is an identity matrix but with a zero at the PEF's ``1''.

I have had considerable experience solving (30) and can report that bin filling is easier and works much more quickly and reliably. Eventually I realized that the best way to start the nonlinear iteration (30) is with the final result of bin filling. Then I learned that the extra complexity of the nonlinear iteration (30) offers little apparent improvement to the quality of the SeaBeam result. (This is not to say that we should not try more variations on the idea).

Not only did I find the binning method faster, but I found it to be much faster (compare a minute to an hour). The reasons for being faster (most important first) are,

1.

Binning reduces the amount of data handled in each iteration by a factor of the average number of points per bin.

2.

The 2-D linear interpolation operator adds many operations per data point.

3.

The formulation (30) seems to require more iterations.

Additionally, I found that the iteration (30), like most nonlinear sequences, behaves unexpectedly and badly when you start too far from the desired solution. For example, I often began from the assumed PEF being a Laplacian and the original map being fit from that. Oddly, from this starting location I sometimes found myself stuck. The iteration (30) would not move towards the map we humans consider a better one.

Having said all those bad things about iteration (30), I must hasten to add that with a different type of data set, you might find the results of (30) to be significantly better.