Simple Function Plotting in Javascript September 15th, 2009
Patrick Stein

graphRather than work more on my FFT Paint program yesterday, I took a break to make a simple function plotter. There are lots of useful Java applets out there that do more than what I’ve done here. And, certainly, gnuplot is much more complete and useful.

On the other hand, if you just want to quickly plot something that you can save as an image, you either have to re-learn gnuplot (every time I use it, I have to sift through the help to figure out how to set up my tics and labels and output size and output filename) or you have to do screen grabs from one of the Java applets.

With the plotter that I wrote yesterday, you click on the Snapshot button, then right-click to save the image or copy it to your clipboard.

Enjoy.

Better Examples of Fourier Transform Painting September 10th, 2009
Patrick Stein

I have now added symmetry options to my Fourier Transform painting application. As PC pointed out in a comment to my previous post, examples with higher frequency information are more interesting. Here are some images of the background tile of this website. The magnitude is on the left and the phase is on the right. You can click them for the full-sized images.

This is the original:

squares_m  squares_p

This is the Fourier transform of the original:

squares_mf  squares_pf

This is my edited version of that transform. I wiped out lots of the off-axis frequencies. I tinted the center red. And, I added some green blotches along the diagonals.

squares_mfe  squares_pfe

And, here is the inverse transform of my edited data.

squares_mfei  squares_pfei

Playing with your Fourier Transforms September 9th, 2009
Patrick Stein

Earlier, I posted a small script that lets you do Fast Fourier Transforms in Javascript. I did this in to test the waters to see if I could do the exercises for the Numeric Photography study group in Javascript.

I am well underway, now, with the first exercise/assignment. The goal is to create an image editor that lets you work on either the image or the Fourier transform of the image. I have only tested it under Safari and Firefox so far. I do intend to add excanvas into it later and test it on some other browsers.

If you are interested (and have Safari or Firefox), here is the current state.

Edit (four hours later): I have now debugged it under Firefox 3.5.2.

The original image Fourier transform with some additions The inverse transform of the processed image.

These are the original image, the Fourier transform in which I painted some green dots and phase-rotated the lowest-order frequencies, and the image after the inverse transform.

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.



Trapdoor Puzzles August 28th, 2009
Patrick Stein

With most logic or word puzzles, your goal is to find a solution. To make those puzzles interesting, the puzzle maker has to assure that there is a solution and that the solution is unique. This is true for crossword puzzles, sudoku puzzles, cryptograms, rebuses (rebi?), mazes, Lights Out games, and binary logic puzzles of this form: Alice is wearing red. John is older than Jimmy. The tallest person is not wearing green. Clue. Clue. Clue. Who is standing next to Alice? Rush Hour games and tanagrams are also usually crafted so that there is a unique solution.

Uniqueness

For some of these games, we mean a unique solution amongst all solutions without backtracking. For example, in solving a maze, we would not consider solutions that involve running down a corridor only to come back along the same corridor. For Lights Out games, the concept is simple but describing it takes work. Imagine that every square on the board, in addition to being lit or not, also has a letter ‘A’ on it at the start of the game. Whenever you press a button labelled ‘A’, it gets relabeled ‘B’. Every time you press a button labelled ‘B’, it gets relabeled ‘A’. Two solutions are identical if the board has the same configuration of ‘A’s and ‘B’s after both moves. Thus, hitting any button more than once was just a waste of time. However, the order that you hit the buttons makes no difference at all.

There is a notable crossword puzzle with two solutions. There are some notorious Sudoku puzzles with two solutions. I don’t know of any cryptograms with two solutions, but I am going to go asearchin’ some time.

Technically, a Sudoku puzzle with two solutions cannot be solved. You had to make a guess somewhere and it turned out you had twice the odds of being right that you should have. It is easy to accidentally take too many numbers out of the Sudoku grid and end up with an ambiguous puzzle. For a crossword puzzle, I doubt most people bother to check to see if the solution is unique. It probably is unique by sheer combinatorics. The same may be true cryptograms, as well. You’d have to specifically be trying to make them ambiguous to achieve it.

Trapdoors

Where are the trapdoors? Well, the puzzle creator has a much harder job than the puzzle solver for most games. It is easy to construct mazes and Lights Out games with unique solutions (in fact, it’s easy to show that if a Lights Out game is solvable, the solution is unique). It is not so easy to construct other puzzles that have provably unique solutions.

This brings us to the Discrete Logarithm Problem. Imagine that I told you that 3^x \equiv 16 \pmod{29} and asked you what x is modulo 28. There is no really easy way to solve this problem, yet it is easy to formulate such problems. I checked that 3^{14} \neq 1 \pmod{29}. Then, I picked x = 12 and plugged it in to see that 3^{12} \equiv 16 \pmod{29}. I started from the answer and was quickly able to generate a problem that I can guarantee has a unique solution.

This is called a trapdoor function. It is easy to calculate, but hard to invert the calculation. It’s also not a very fun problem to do. You will never open up the comics page of your newspaper and find five of these problems below the bridge column and above the horoscopes.

I can easily imagine a whole variety of Lights Out type games where lights have more than one state. It would be easy to prove, for a wide class of such games, that when a solution exists, it is unique. These would all be solvable by inverting a matrix whose coefficients come from a finite field.

What other puzzles could take advantage of trapdoor functions to make the game easier on the puzzle maker than on the puzzle solver?

RSS Feeds

l