Steve on Image Processing

April 4th, 2008

Reconsidering the impossible

I grabbed the latest issue of IEEE Signal Processing Magazine out of my mailbox the other day. As I was flipping through the pages I noticed a familiar face: Doug Williams, who is the Special Sections Area Editor for the magazine. (I know Doug because he joined the faculty at Georgia Tech as I was finishing up my Ph.D. there.) He wrote the "From the Editor" column this month, entitled "Periodically Reconsidering the Impossible." His point is that people who recognize outdated assumptions can "sometimes initiate remarkable progress" in a particular field. One example he gives is the fast Fourier transform:

By the late 1990s, very few people were developing new fast Fourier transform (FFT) algorithms, and the field was considered to be very mature. Researchers had long since determined exactly how many arithmetic operations were necessary to perform a discrete Fourier transform (DFT), and optimized FFT software was widely available. However, these algorithms were based on assumptions made in the 1970s that minimizing additions and multiplications would yield the quickest implementations. Computation speed on modern processors is much more dependent on efficient pipelining and memory access. Thus, the field was ripe for a pair of computer scientists to reformulate the problem, and, in 1998, Matteo Frigo and Steven G. Johnson presented "FFTW: An Adaptive Architecture for the FFT" at the 1998 ICASSP. Their software, which can actually be found at http://www.fftw.org, is actually a collection of FFT algorithms that can self-optimize to choose the best combination for a particular computing platform.

—IEEE Signal Processing Magazine, vol. 25, no. 2, March 2008, p. 2

Doug's point about arithmetic operation counting is very true. Today whenever we look at improving performance in MATLAB, memory access patterns and processor utilization tend to dominate the discussion.

It didn't take long for The MathWorks to incorporate FFTW into MATLAB (in version 6). The FFTW code would have horrified DSP researchers from a couple of decades ago. Among other things, it was (GASP!) explicitly recursive, which was a no-no back then.

Doug's column introduces the special issue on compressive sampling, which is a dramatically different look at sampling theory. I'm looking forward to reading through it.

By Steve Eddins

10:56 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.

4 Responses to “Reconsidering the impossible”

  1. Igor Carron replied on April 5th, 2008 at 05:51 UTC :

    Steve,

    As you’ll read the IEEE article, you’ll find that the subject of Compressive Sampling is closely related to Compressed Sensing / Compressive sensing. The main reference library on the subject is at Rice:

    http://www.dsp.ece.rice.edu/cs/

    that is also home of a technology implementing this concept: The single pixel camera.

    Other hardware implementations are listed here:
    http://igorcarron.googlepages.com/cs#hardware

    I also have a blog on the subject if you are interested:
    http://nuit-blanche.blogspot.com/search/label/CS

    and I also try to paint the big picture of this rapidly evolving field here at:

    http://igorcarron.googlepages.com/cs

    You will not be surprised to find out that Matlab is the main language for exploring all the potential avenues of this new field.

    http://www.dsp.ece.rice.edu/cs/#sof

    The rapid prototyping enabled by Matlab is expected to provide a clear way for adoption of this seemingly “impossible” theory (Not unlike what Wavelab did for wavelets some years ago).

    Cheers,

    Igor.

  2. Steve replied on April 5th, 2008 at 07:26 UTC :

    Igor—Thanks for the information and links.

  3. İsmail Arı replied on April 5th, 2008 at 10:51 UTC :

    Hello,
    Thanks for the post. I think there’s “http://” prefix missing in the fftw link :)

    Kind regards,

  4. Steve replied on April 5th, 2008 at 15:17 UTC :

    Ismail—Thanks. I fixed the link.

Leave a Reply

Wrap code fragments inside <pre> tags, like this:

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

If you have a "<" character in your code, either follow it with a space or replace it with "&lt;" (including the semicolon).

About

Steve Eddins manages the Image & Geospatial development team at The MathWorks and coauthored Digital Image Processing Using MATLAB. He writes here about image processing concepts, algorithm implementations, and MATLAB.

Subscribe


Recent Comments

  • Sana: hi steve, could you explain to me how i would be able to use the dir function, to do a loop through a directory...
  • Nishtha: Sir, I have preprocessed the image in following steps: [1] adaptive histogram equalization [2] thresholding...
  • Kristof: I also strongly support the idea. I have just recently bumped into the problem that im2single was not...
  • Steve: David—I’ m glad you found it useful!
  • David Lalejini: I found your example very useful for finding connected nodes in a large set of input pairs. I start...
  • tommy: Dear Steve, I have a question,please if you are kind to help me regarding the accumulator array dimensions of...
  • Steve: Abc—I don’t know how to distinguish the faces. You might try posting your question in the MATLAB...
  • Manju: well if we have a few ovals within each other like in a cell how do we measure the distance from the center...
  • Steve: Manju—What do you mean? How is each region defined?
  • Manju: if we have 2-3 regions within each other how do we measure the regions of each one?

Blog Admin

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