De Rerum Natura

In a previous post I mentioned a way of Fourier analyzing the geometric precision error of DEMs. Today I realized that the scheme I proposed can only account for part of the error signal. The approach I proposed is correct but it can only capture one particular aspect of the total error. The simplest way of seeing this is to consider the $S_2$ symmetry group. This would be the one to use for $p=2$ photographs. From two photographs I can produce two DEMs: $A\to B$ and $B\to A$. The covariance matrix for these two DEMS would be a 2×2 covariance matrix of the form:
$$\left(\begin{array}{c}ab\\ bc\end{array}\right).$$
But the representation induced by $S_2$ on these two DEMs generates the matrices:
$$\left(\begin{array}{c}10\\ 01\end{array}\right)\text{and}\left(\begin{array}{c}01\\ 10\end{array}\right)$$
These two matrices cannot capture the three independent degrees of freedom in the 2×2 covariance matrix. Therefore, the induced representation cannot capture all of the possible errors that are observed when two photograps are used to produce two maps. But the representation would allow you to project out that component of the error that is explained by permutations of the images.

You would need at least $p=7$ photograps to have enough members in $S_p$ to completely model the variation in the DEMs observed when you use two photographs to produce a map. To understand the error that cannot be explained by the permutation group you would need to use three photographs to create a DEM. For $p$ photographs this would create $p*(p-1)*(p-2)$ DEMs. Since we can produce as much or even more than $p!$ DEMs from $p$ photographs, at some point we will always overwhelm the representational power of the symmetry group of $p$ objects (in this case, $p$ photographs). What error remains after we project out the component that can be modelled by $S_n$? I hypothesize that it would be error that can be further Fourier analyzed by using the symmetry group associated with the orientation and positions of the cameras. These parameters are themselves error prone and would, by virtue of their geometry, only induce certain error patterns.

This viewpoint of the errors would therefore view the observed error as one that can be captured by a succesive series of symmetry groups. One component would be that related to the finite group of $S_p$. Another component would be that one induced by translations and rotations of the camera positions and orientations. Like any real theory of errors, this approach would only peel away layers of error — always remaining would be a nugget of error that would require more and more complex models to decompose. The second law of thermodynamics is not violated!

The metaphor to x-raying in the title of this post comes from using Fourier analysis to study X-ray diffraction photographs by crystals. Crystals induce a certain periodicity on the scattered X-rays even when the sample is crushed into a powder. In other words, the randomly scattered blocks of crystal in the powder individually send a perfect difraction pattern. But the X-ray photograph records the mismash of the signals — the picture is blurry. Nonetheless, the bluriness has a symmetry component that comes from the periodic structure of the crystals and therefore Fourier analysis is able to pick the symmetry in the x-ray caused by the crystal periodicity. The Fourier decompositions for geometric errors are doing the same thing. There are many sources of errors in DEMs from aerial photographs. Some come from the fact that you used individual photographs to create the maps. This component of the error can therefore be accounted by studying representations of the symmetry group of p objects. Others come from uncertainty in the position or orientation of the camera when it took the photograph. These are explained by induced representations of non-abelian Lie groups like 3-D rotations in the space of covariance matrices.

I submitted my paper on autonomous precision error estimation in 3-D models to the 2008 International Conference on Machine Learning yesterday. One week early, too, a first for me! The format for the paper is the standard double column format and this makes it very hard to have complex equations in the paper. One mathematical object that is hard to display are the covariance matrices for the DEM errors that I keep talking about in these posts. These are nxn matrices of real numbers. One particular example I use comes from images of a desert terrain in the Twenty-Nine Palms area in California. We have four photographs and can therefore produce $12=4*3$ DEMs. Because of mistakes, two of the DEMs have to be dropped so I end up with 10 DEMs. The resulting covariance matrices are then 10×10 matrices — a hard thing to display in the double-column format since now you have to present 10 numbers in row. So I have hit upon a simple graphical way to present them that saves space but also ends up being more informative to the reader (or me) about the structure of the matrix.

The idea is to turn the 10×10 matrix into a 10×10 pixel image. Each pixel is now a shade of gray. The highest value in the matrix gets the darkest shade, the lowest gets the lighest. Here is an example that illustrates our correlated-pair error model The only terms that are “turned on” are those along the diagonal. In contrast, here is the covariance matrix when you do ${\ell }_1$-minimization and do not assume beforehand that certain DEMs are uncorrelated with each other. So the correlated-pair error model is close to the actual covariances but we see that there are some cross-correlations off the diagonal that are on, albeit weaker than those on the block-diagonal defined by the asymmetric DEM pairs.

I apologize for the strange layout of the mages relative to the text of this post but my WordPress instalation does not save changes that I make to the img tag to identify it as requiring it to have text flow around it.
In any case, I hope this illustration makes clear some of the more abstract ideas I have been discussing about errors in DEMs.

I’ve finished the experiments with different reconstruction matrices for the DEM precision error and I get a rock solid result independent of which reconstruction matrix I use. So my hypothesis that randomness may be used to increase the precision error was wrong. In the process, however, I have finally understood how to use the symmetry group $S_n$ to Fourier analyze the covariance matrix. This has lead me to consider generalizations of our current approach that rely on the asymmetry of stereo matching algorithms.

The covariance matrix for our current procedure for creating maps is made up of photographic pairs. From two images, A and B, we create DEMs $A\to B$ and $B\to A$. So $n$ photographs lead to $n*(n-1)$ DEMs. The resulting covariance matrix can be Fourier analyzed by considering the representation induced by the symmetry group for $n$ objects (in our case the photographs) on the $n*(n-1)$ space. That is, for each element of the group, call it $\pi$, we define $M_{A\to B,C\to D}=1$ if $\pi (A)\to \pi (B)=C\to D$. This matrix representation can then be decomposed into its irreducible components to carry out the Fourier transform.

The above construction can then, in turn, be generalized by using the asymmetry of stereo matching algorithms. One constructs DEMs of the form $A\to B\to C$. This will not, in general, produce the same DEM as $A\to C\to B$ and so on. There will be $n*(n-1)*(n-2)$ ways of constructing these DEMs. A representation of the group can then be induced by generalizing the rule in the previous paragraph. Bringing in more photographs into the chain will induce higher and higher dimensional representations of the symmetry group. But note that all these representations are, by construction, smaller or equal to the $n!$ dimensionality of the symmetry group itself. Higher dimensional representations could be constructed because an arbitrary DEM like $A\to B\to A\to C$ will not be equivalent to the $A\to C$ DEM, for example. The matching process being imperfect will not return to the same pixel when the matching chain is of the form $A\to B\to A$.

None of these more complicated DEM production processes will lead to anything interesting if there were no errors in the matching process. If creating a 3-D model from photographs was perfect, all the DEMs would be error free and the covariance matrix would be proportional to the identity matrix. In other words, the Fourier decomposition of the covariance matrix is interesting because there is a symmetry to the errors. I’ll keep readers updated on the results of this line of inquiry as I obtain concrete results.

If I was to rate the things I have learned from computer science, I would place the algorithmic use of randomness right at the top. The uses of randomness in computations is too vast to start a list here. Check out Probability and Computing: Randomized Algorithms and Probabilistic Analysis for many examples. I want to discuss another way of using randomness in computation by discussing the estimation of precision errors in Digital Elevation Models.

I’ll use some simple linear algebra to explain how precision error can be discussed in the language of compressed sensing. The Swiss paper describes how to turn the estimation of the precision error covariance matrix into a linear algebra problem of the
form
$$S=\Phi \alpha .$$
“S” is the signal. In this case, the autonomous difference terms one can calculate from the DEM elevation estimates. This makes “S” the signal because it can be calculated from what we observe — the DEM elevations. The vector $\alpha$ are the precision error covariance terms the robot is trying to estimate without knowing any ground truth. The “reconstruction” matrix $\Phi (n)$ tells you how to go between these two quantities. $\Phi$is can be calculated exactly and is only a function of the number $n$ of DEMs.

Randomness comes into the error estimation process because there exist many different ways to specify the reconstruction matrix. Take the example of 10 DEMs I have used before since it corresponds to the case I have studied most in my work with Howard Schultz. The autonomous difference equations give us about 5,000 different ways of calculing quantities that do not depend on ground truth. Out of all those many equations, only 45 are linearly independent. Which 45? Any 45. That means that there are many ways of constructing $\Phi$. So many that I can randomly do it by picking equations from the set of 5,000 equations until I get a set of 45 linearly independent ones.

So it becomes possible to check the precision error estimate many different ways. Could one then use this to improve the error estimation process itself? I do not know but I’m investigating that issue today by running experiments with randomly picked independent sets and plotting how the values vary for the same DEMs used as input.

Compressed sensing caught my attention last year. I was doing a literature search on the Internet to see if anyone else had discussed the autonomous difference equations that Howard Schultz and I had devised to measure the precision errors in Digital Elevation Models (DEMs). One of the basic tenets of compressed sensing is that since many natural signals are sparse, why waste your resources taking many measurements when you can just take fewer to get the same reconstructed signal? For example, our high mega-pixel cameras capture images that we end up compressing anyhow to much smaller files. So why have CCDs with so many pixels?

I have a new hypothesis that would justify all these redundant measurements. Scientists view measurements as two numbers. The guess for the measured quantity, say the temperature of a glass of water, is the one that gets quoted first. But equally important is the error on that temperature guess. So the temperature of the glass should be properly be quoted as $10.0\pm 0.2$ Celsius degrees, for example. So repeated measurements may not improve the color and intensity estimate for a pixel in a photograph but it dramatically improves our error on that measurement. Measurements should never be wasted! In the case of maps, it means that repeated images of a terrain would not necessarily improve the resolution of the map, but they would have a dramatic effect on the resolution of the error map for our elevation estimates.

I am currently writing a paper for the International Conference on Machine Learning that is studying this hypothesis in the context of DEMs. I’ll post some of the results in a later post if the hypothesis turns out to be correct. I mentioned this hypothesis for my pre-proposal submission to the National Science Foundation’s new Cyber-Enabled Discovery program but I don’t think it will get much traction just yet.