Quadtree Pyramid Interpolation

The quadtree decomposition is an adaptive sampling scheme which seeks to divide a digital image into regions of nearly homogeneous pixel value. Intuitively, the block size is smallest where the image changes most rapidly, and largest where the pixel values are constant over large areas.

A similar intuition applies to the interpolation of sparse data. Given point data collected on the Earth's surface, equation (1) relates how the data is placed into the discrete computational grid. If data is collected at perfectly regular intervals on the Earth's surface, it is possible to choose a bin size such that one and only one measurement falls in each bin. On the other hand, if the data sampling is irregular, two problems may arise: 1) more than one datum may fall into a given bin, and the values averaged, implying information loss, and 2) no data may fall into a given bin, leaving a ``hole'' in the model.

Applied to interpolation, the quadtree methodology seeks to adaptively sample the model such that 1) where data are closely spaced, the bin size is small, to minimize averaging of adjacent data and 2) where data are sparsely distributed, the bin size is large, to avoid introducing holes in the model.

First assume that there exists a regular bin size such that binning the data produces a model with no holes. From here, we regard ``bin size'' as equivalent to ``scale'' - where scale goes from coarsest (largest bins) to finest (smallest bins). Also assume that at each scale, the bins which contain one or more data values are known.

• $\bold m_i$ - Model at scale i; i=0 is coarsest scale, i=n is finest scale.
• $\bold B_i$ - Bin data onto grid of scale i; i=0 is coarsest scale, i=n is finest scale.
• $\bold K_i$ - Known data mask at scale i - 1 for bins which contain data, 0 otherwise; i=0 is coarsest scale, i=n is finest scale.
• $\bold U_i$ - Upsampling operator. Upsample from scale i-1 to scale i. i=0 is coarsest scale, i=n is finest scale. Adjoint to the downsampling operator in the multiscale regularization discussion. For instance, if the downsampling operator sums four input bin locations into an output location and averages, the upsampling operator takes the averaged value and places it back into the four bins.
• $\bold d$ - data.

The algorithm proceeds as follows.

1.

Compute $\bold m_0 = \bold B_0^T \bf d$.

2.

Loop over scale: $i = 1 \rightarrow n$.

3.

Upsample $\bold m_i^u = \bold U_i \bold m_{i-1}$.

4.

Compute $\bold m_i^b = \bold B_i^T \bf d$.

5.

Where $\bold K_i = 1, \bold m_i = \bold m_i^b$. Otherwise, $\bold m_i = \bold m_i^u$.

6.

End Loop.

This approach is quite similar to the Multigrid-style method employed by Crawley (1995), but there is no inversion involved - my method is totally explicit. Interestingly, Luettgen et al. (1994) show that for the underdetermined optical flow determination problem of image processing, use of an explicit quadtree scheme gives results identical by some measures to the result obtained by solving a regularized inverse problem.