Hackszine.com: Math Archives

Archive: Math

April 5, 2008

HOWTO - Encode any string into a trigonometric function

Following Poromenos' nifty "Hello World!" function, Jan Krueger posted a great explanation for why it works along with a general method for producing a trigonometric function for _any_ string you like:

The magic behind Poromenos's function is the Fourier theorem: any "mostly" continuous and periodic function can be expressed as a sum of sines and cosines. I'm not going to bore you with the details; suffice to say that this also works for sampled functions, i.e. discrete series of values.
There's an algorithm called DFT (Discrete Fourier Transform) that takes a series of N complex sample values and generates a corresponding Fourier series which encodes the various sine/cosine coefficients in N complex output values. In the special case of real input values (which is an extremely common case), you can effectively throw away half of these output values and take the remaining N real/imaginary components, do a bit of magic, and end up with coefficients for a function of the form:

f(t) = x0 + x1 cos(t) + x2 sin(t) + x3 cos(2t) + x4 sin(2t) + ...

Now, f(2 pi n/N) returns exactly the (n+1)th character of the original string.

Follow the link and you'll find a nifty C program that will produce a trigonometric function for any string you like.

HOWTO: encode a string into a complicated-looking trigonometric function

April 2, 2008

Poromenos' hello world curve

Take a peek at this curve. If you take the rounded y value for every integer x from 0 through 11, you'll have yourself the ascii values for the string "Hello world!".

Well, I have a computer architecture exam in six hours and can't be bothered, so I figured I would realize a lifelong dream of mine, and make a program that prints "Hello world!" using curve fitting techniques. Enlisting the help of a good friend with numerous mathematical papers under his belt (ostensibly because he could not afford a tighter belt), MATLAB and a longing for procrastination, we embarked on this perilous journey. After many, many hours of fitting and discarding data, I can finally present to you my masterpiece.

It's 12 characters summed from 10 sines and cosines:

96.75 - 21.98*cos(x*1.118) + 13.29*sin(x*1.118) - 8.387*cos(2*x*1.118) + 17.94*sin(2*x*1.118) + 1.265*cos(3*x*1.118) + 16.58*sin(3*x*1.118) + 3.988*cos(4*x*1.118) + 8.463*sin(4*x*1.118) + 0.3583*cos(5*x*1.118) + 5.878*sin(5*x*1.118)

Poromenos' blog has the full Python script which evaluates and renders the famous words. Hands down, this is the best math to happen to me all day.

Printing "Hello world!" using curve fitting techniques

February 28, 2008

Detecting forged photos algorithmically

John Graham-Cumming posted an automated tool for detecting "Clone Tool" Photoshop forgeries. Photojournalism ethics issues (LInk, Link) aside, John had some ulterior motives:

I was motivated to work on this program by greed (or at least my never-ending love of having a little flutter on things). Best of the Best runs spot-the-ball competitions in airports to win very expensive cars. But they also run the same competition online. That meant I could get my hands on the actual image used... could I process it to discover where the ball had been removed? (In reality, this isn't the right way to win because the actual ball position is not governed by where it actually was, but where a judge thinks it was).
Would it be cheating if I could? Apparently not, the competition rules say I should use my skill and judgment in determining the ball position. Surely, skill covers my programming ability.

So, I went looking for tampering algorithms and eventually came across Detection of Copy-Move Forgery in Digital Images written by Jessica Fridrich at SUNY Binghamton. The paper describes an algorithm for detecting just the sort of changes I thought I was looking for.

Essentially the algorithm cuts the image into a bunch of 16x16 chunks and runs each chunk through a discrete cosine transform. The DCTed chunks are compressed and sorted, and the algorithm looks for multiple matching chunks that were shifted the same direction and distance, highlighting the source image if a large number of matches are found.

Another blogger, jjwiseman, released a speed optimization for John's code, which he successfully used on the infamous Adnan Hajj Reuters images. While the algorithm is able to detect this style of manipulation, it's noted that it has a habit of returning false positives in images with a blurry background.

That said, it'd be pretty interesting to run this through a big database of news photos and see what turns up.

Detection of Copy-Move Forgery in Digital Images - Link (PDF)
John Graham-Cumming's Clone Tool Detector - Link
Protecting Journalistic Integrity Algorithmically (jjwiseman's update) - Link

January 31, 2008

R: open source statistical computing

I was digging around for an open source statistics package today and came across R, a GPLed statistics and and data analysis suite. Sweet!

R provides a wide variety of statistical (linear and nonlinear modelling, classical statistical tests, time-series analysis, classification, clustering, ...) and graphical techniques, and is highly extensible. The S language is often the vehicle of choice for research in statistical methodology, and R provides an Open Source route to participation in that activity.
One of R's strengths is the ease with which well-designed publication-quality plots can be produced, including mathematical symbols and formulae where needed. Great care has been taken over the defaults for the minor design choices in graphics, but the user retains full control.

So I've been messing around with this for the last half hour and it's really an exciting package, especially if you're a coder or unix geek. You interface with R through a command line programming interface, executing simple statements, setting variables, and defining functions. It feels similar to issuing commands at a unix prompt, except you're working with data sets instead of file descriptors.

What's cool is the robust capability of the standard function set. Want to read in a data set from a tab delimited table you found on the internet? Check this out:

# Read a table in from a URL (tab delimited table with row headers) Mydata <- read.table(http://someserver.com/table.txt', header=TRUE) # Display summary (mean, median, min, max, etc.) for each column summary(Mydata)
# Get the standard deviation for the values in column "foo" attach(Mydata) sd(foo)

Learning the command set is a little daunting at first, but the console even does tab completion. If you don't know what a function does, just put a question mark before it. For instance, "?sd" will quickly pull up help for the standard deviation function.

I've only scratched the surface, but there are links below to some R beginner guides which should help you get started. Anyone out there more familiar with the package? Please share any useful links and tips in the comments.

The R Project for Statistical Computing - Link
An Introduction to Statistical Computing in R - Link
Producing Simple Graphs with R - Link

January 23, 2008

Accelerometer motion analysis

There's an article over on the WiiLi Wiki that goes into great detail describing how to translate 3D accelerometer measurements into an estimation of the position, rotation, and velocity of a device like the Wiimote. By making a few assumptions—people's arms have a limited range of motion, most Wii play doesn't take place in moving vehicles, etc.—it's quite surprising what you can get away with with just the accelerometer data.

The amusingly named (but rarely used) term for the rate of change of acceleration is jerk. The jerk term for the remote shows up in the time derivative of the force recorded by the sensor, along with the rotation term that contains the angular velocity of the remote. We can extract both rotation and linear acceleration if we assume a few things:
We know the "up" direction before the motion starts.

Throughout the motion, the jerk on the remote perpendicular to the current direction of gravity is small.

Then we can assume the time derivative of the force component which is perpendicular to our current estimate of the up direction is caused by the user rotating the controller only. This allows us to update our estimate of the up direction for the next time step. In each time step, we can also get the linear acceleration of the remote by subtracting our estimate of from the current force sensor report. In effect we are integrating up a coupled set of ordinary differential equations. (Note, need to review the math here. Beware.)

The main problem with this technique is error accumulation in our estimate of "up." Since it is unlikely the user can keep the controller in constant linear motion without injuring themselves, the TV, or their opponent, we can look for times when the total reported force is close to g = 1.0 to recenter . You have to be careful when doing this because it is possible and probably common for the Wiimote to report an acceleration close to g = 1.0 while it is accelerating. When this happens your acceleration vector does not actually point "up" and you will recenter to an incorrect R. This can happen anytime you are accelerating both downward and in the horizontal plane.

I keep thinking that there should be some class of flying vehicle that, when operated under fairly restrained conditions, might be able to get by with just accelerometer measurements to obtain reasonably accurate state information. You could integrate the acceleration data through very limited motions that are within some margin of error, recalibrate, and repeat. This is probably a pipe dream, but I really want a solution for a $50 6DOF IMU. :/

Accelerometer motion analysis - Link

January 25, 2007

Tupper's Self-Referential Formula

Self-Referential Formula.jpeg

Tupper's Self-Referential Formula is an equation that, when graphed, displays the formula itself. Here's the equation (same as the image of the output shown at the beginning of this post):