Steve on Image Processing

September 11th, 2008

Today's post is brought to you directly from the software developer half of my brain.

MATLAB 6 was the first version to use the FFTW library for fast Fourier transform computations, and I was one of the developers who worked on that change.

Making changes to fft and related functions made me a bit nervous. What if we made a mistake and broke it somehow? That would be 15 minutes of fame I would definitely not enjoy.

The best way to proceed when changing existing, working code is to make sure first that you have thorough, effective tests. (See, for example, "The First Step in Refactoring" in Martin Fowler's book, Refactoring: Improving the Design of Existing Code.) And for numerical computation, nothing gives you more confidence in your tests than using independent computation methods to validate your code.

Besides using fft, I can think of at least two other reasonably easy ways to compute the discrete Fourier transform in MATLAB. One is to write an M-file that directly implements the discrete Fourier transform equation. Another is to use a matrix-vector multiply with the Fourier matrix (see the doc for the dftmtx function in the Signal Processing Toolbox.) Normally, you would never want to use either of these methods when you can instead use a much faster fast Fourier transform algorithm.

However, pure speed is not so critical for testing purposes. Many of our automated tests for fft and related functions test their output against the result found using the matrix-vector multiplication. That turned out to be very helpful for making sure that our changes to fft did not result in incorrect output. (If you'd like to know more about MATLAB and FFTW, read this Cleve's Corner.)

Here's another testing example illustrating the need for independent computation. The Mapping Toolbox has functions for computing minimum distance curves on an ellipsoid. No closed-form solutions exist, so series or iterative approximations are commonly used. The Mapping Toolbox test suite checks the numerical accuracy of these approximations by comparing them to the results obtained using MATLAB ODE solvers. (This testing technique was published in a paper. See R. Comer and N. Ramarathnam, "Numerical Validation of Curves on the Ellipsoid," Proceedings of the ASPRS 2005 Annual Conference.)

Often you can independently compute small positive test cases by hand. Many image morphology test cases in the Image Processing Toolbox test suite were computed by hand directly from the relevant formulas and definitions.

It's tempting sometimes, especially for operations that are especially tedious to compute by hand or by another method, to construct test case validation data by saving the output data from the code you are trying to test. Such a test is only useful for making the sure that today's output from the code is the same as yesterday's; it doesn't tell you anything about whether the answers are correct. That's better than no test at all, but not nearly as good as independent validation of correctness.

17:00 UTC | Posted in Uncategorized | Permalink |

You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.

2 Responses to “Independent computation in software tests”

1. Chas Kenny replied on September 12th, 2008 at 21:25 UTC :
   

   Hi Steve,
   Does your new fft allow comparison of phase, one image to another, greater than modulo 2 pi?
   Thanks,
   Chas

2. Steve replied on September 12th, 2008 at 21:30 UTC :
   

   Chas—The fft function computes the discrete Fourier transform. No more, and no less.

Leave a Reply

<pre class="code">
a = magic(3);
sum(a)
</pre>

These postings are the author's and don't necessarily represent the opinions of The MathWorks.