Robust statistics and yet more computationally efficient solutions: From `` Lebesgue summation'' to comparagram

Another way to interpret the error presented in (9) is to rewrite the summation as a sum over the range rather than over the domain of the images⁴: = _m=0^N _n=0^N J(m,n) ( F(f_1(x,y)) - F(f_2(x,y)) + K ) ^2 summing over the values of $(x,y)$ for which $F(f_1(x,y))=m$ and $F(f_1(x,y))=n$.

The quantity $J$ provides a weighting for the number of pixels in image $f_1$ that are equal to $m$ and at the same coordinates $(x,y)$ equal to $n$ in image $f_2$.

It will be easier to understand the form of (15) by grouping (counting) all of the pixel values for which $f_1(x,y)=m$ and, in the corresponding location $f_n(x,y)=n$. The result, denoted by the letter $J$, is called the comparagram[7] of the two images, and has dimensions $N$ by $N$. It should be noted that $J$ captures all of the information about the tonal relationship between the two pictures while discarding all of the spatial information in the images. This tonal relationship is all that is needed to solve (9) while discarding a great deal of irrelevant information. To solve (15), the matrix ${\bf A} \in \R^{N^2 \times N}$ and the vector ${\bf K}$ are constructed to have one row for each element of $J$, as follows: A(mN+n,m) &=&J(m,n)
A(mN+n,n) &=&-J(m,n)
K(mN+n) &=&J(m,n) with the additional constraints appended to $A$ as before, resulting in the same method of solution as before (least-squares).

Looking at comparagrams of typical sets of differently exposed images, the comparagrams tend to be very sparse. Thus working with comparagrams provides us with a very tidy way of greatly increasing the computational efficiency, as well as performing robust statistics (pruning low entries).

Thus the computation can be made still more efficient by removing rows of $A$ and $K$ that are zero, which is done by only including nonempty bins of $J$ that are off the main diagonal (zero entries result from either empty bins of $J$ or from diagonal entries of $J$). Jointly, the comparagram across two images seldom contains more than ten percent nonzero entries, so the resulting computational savings is very significant.

Robust statistics provide improved immunity to noise but this immunity is usually obtained at some computational expense. However, the formulation of (15) with solution (17) may be made both computationally more efficient as well as more robust by thresholding $J$. This is done by setting any entries in $J$ that are less than a certain number equal to zero. A threshold of 10, for example, means that any bins containing less than 10 counts are set to zero prior to solving (17). Interestingly enough, this method of throwing away outliers results in further increases in computational efficiency.