I have spoken in previous blogs of how the Terrest system developed by Howard Schultz exploits the asymmetry of computer stereo matching algorithms to produce two Digital Elevation Models (DEMs) from a pair of aerial photographs. This seems like a kind of trickery to many who are exposed to this feature of Terrest since the common practice in map-making from photographs is to produce only one DEM from a photographic pair.

Last Spring we started to develop a theory that explains why this DEM doubling is completely justified. Our approach was to use other photographic pairs to study the correlations between the two DEMs of a photographic pair. We called this model “the correlated-pair error model”. It rests on the assumption that DEMs from different photographic pairs are completely uncorrelated. Mathematically this is expressed by saying that the cross correlation between the errors of two DEMs from unrelated pairs is zero:
$$\left[ \delta_{AB} \delta_{CD} \right] = 0,$$
where the square brackets denote averaging of the elevation error of each DEM, $\delta$, over the whole area of the map.

This cross-correlation is not zero when considering the two DEMs from a photographic pair. For example, with two photographs A and B we can produce two DEMs AB and BA. This non-zero value means that on average the error of one DEM at a particular location is likely to be similar in the other DEM at the same location. The existence of this correlation is what has repelled others from producing two DEMs from a photographic pair.

I recently finished a manuscript for the IEEE Computer Vision and Pattern Recognition 2008 conference that was discussed in an earlier post. A misunderstanding on my part lead me to suspect a result I was obtaining with a calculation so I decided to finally do the compressed sensing calculation I had been speculating would be useful in these situations. What do I mean by that? Let me explain it by considering the particular calculation I did.

I had 10 DEMs that came from five photographic pairs. The covariance matrix of the average error of these DEMs is of dimension 10×10. Because it is a symmetric matrix, it only has 55 independent components. The linear equations in our theory only give us 45 independent equations: too many unknowns, too few equations. This is strictly speaking an unsolvable linear equation system. But if most components in the covariance matrix are zero (the assumption of the correlated pair error model), the system is solvable by something called the prime-dual interior point method. As luck would have it, the scientific software system Mathematica has a function call to solve these kind of problems! It is appropriately called “LinearProgramming”.

So I put in all the data from my 10 DEMs into the function using the 45 equations I had to try to figure out the 55 components of the covariance matrix. Imagine the pleasant surprise I felt when out came the very correlated-pair error model I have been assuming all along as correct. That is, without any assumptions, it turns out that the best way to explain the error in the 10 DEMs is precisely the one where only DEMs from the same photographic pair are correlated but DEMs from different pairs are not. How good is this result? DEMs from the same photographic have a typical cross-correlation of $0.08 m^2$. Across photographic pairs that cross-correlation is of order $10^{-12} m^2.$ I call that as close to zero as one can hope with real data!

This is proof that error is itself a sparse signal, so all the theory of compressed sensing also applies to it.