Fourier Transforms in JavaScript September 2nd, 2009
Patrick Stein

In preparation for a study group on Numeric Photography, I started toying with what language to use for the coding projects.

Feature shopping

My inclination, of course, was to go with Lisp. Part of the goal of the assignments, however, was to make interactive web applications for each assignment and a gallery at the end of the completed assignments. I experimented a bit with Armed Bear Common Lisp. The hurdles that I would need a user to go through to use my application safely were too great. The user would have to edit their own java.policy file to give my applet permission. If I wanted to let the user do that with a single click or something, I would have to spring for a $200/year code-signing cert.

My next choice then was stand-alone Lisp applications. Rather than online, interactive applications, I would have downloadable ones. Not ideal, but doable. The big hurdle here is crafting a GUI to run the application. The GUI wouldn’t be too terrible thanks to an interesting concept that Dirk Gerrits pointed out: Immediate Mode GUIs. I have already implemented the buttons from this tutorial in OpenGL under SBCL.

Late one night, I remembered Parenscript. It is a Lisp-like language that compiles to Javascript. Parenscript was a little bit more its own thing and a little bit less Lisp than I had wanted. But, it got me thinking. What can you do in Javascript these days?

I searched for image processing javascript. The first hit was Pixastic. It is a library of basic image processing functions that you can run on any image on your page. At its heart, it uses the Canvas element that is available on Safari, Firefox, and Opera. So, I figured, why not? If I can get an FFT working in Javascript, then there is nothing keeping me from implementing all of the assignments in Javascript. Yes, Javascript is awful, but it’s a dream compared to Java. The new Javascript debugging features in Safari are quite useful, too.

Success

Below is a simple example of what I have working. When you first load the page, you see an image of my son and my dad at the Pittsburgh Zoo. This image is actually loaded in a hidden image and copied into a visible canvas. You are seeing the canvas.

If you press the FFT button and wait for it, you will see a representation of the 2-D Discrete Fourier Transform of the image. Really, the DFT output is complex numbers. The representation is just the magnitude of the complex numbers. The actual complex numbers are kept around in a variable so that when you hit the IFFT button, it has enough information to actually reconstruct the image. So, the FFT button works from the pixels in the canvas. The IFFT button works from the data generated with the last FFT. So, unfortunately, you cannot meaningfully FFT-FFT-IFFT-IFFT here. It is interesting, but not meaningful.

Also, I was trying to add a text box here so that you could use your own image, but I am not getting it right. You’re going to have to wait until I finish the whole assignment.




You need a browser that supports the Canvas tag.
Firefox, Safari, and Opera should all work.

A Different Look at the Mandelbrot Set May 14th, 2009
Patrick Stein

When you see pictures of the Mandelbrot set you are seeing the results of iterating a function over and over.

For the Mandelbrot set, you take a complex number c. You square it and add the original number. You take that, square it, and add the original. You do this a number of times. If the value stays relatively close to zero, the number is in the Mandelbrot set. If the value takes off away from zero, the number is not in the Mandelbrot set. Typically, one colors in the parts of the picture that aren’t in the Mandelbrot set with some color that indicates just how fast it hightailed it out of there.

I wanted to try something different. I wanted to see what the iteration process looks like. So, I threw together some code using Lisp with cl-opengl.

fibersThe first visualization that I coded was to start with tiny patches of the complex plane. From each patch, I would extrude it up out of the plane and over to its next iteration. The picture at the right is (IIRC) a patch with side-length one half centered at i with either 25 or 36 patches tiled in that area. As you can see, this isn’t a wholly satisfying picture of what’s going on.

The other idea that I had was to show the progress through iterations as an animation. This is a bit more interesting to look at until some of the patches start overflowing my floating point numbers or get too big for my clipping region. This is an area of side-length one centered at the origin with four-hundred patches. Here is a movie of that flow.

Updates In Email

Email:

RSS Feeds

l