Arnold's cat map is named after the mathematician Vladimir Arnold, who demonstrated the effect of repeatedly applying a linear transformation to an image of a cat like this one:  Click on the image above to see an animation of the Cat Map. Watch as the cat is "scrambled", and then, magically, reappears! Just like the Cheshire cat from Alice in Wonderland. IntroductionLast week we saw how to display images using the We will be using a slight modification of Arnold's original algorithm, that uses the Fibonacci sequence, which we learnt about in Week 1. For this reason, I'm going to call it the Fibonacci Feline map. The Fibonacci FelineBefore we can start writing a code, we need to understand a little more about how Arnold's cat map actually works. In essence, Arnold's map is a rule for moving pixels around in a square, in such a way that we don't lose information. Let's consider a square of side length N, where the position of each pixel is given by an x coordinate and a y coordinate. The x and y coordinates are integers in the range 0, 1, ..., N-1. The map is simply a rule to tell us how to change the coordinates of each point, at each step. We can use any map that it is reversible (i.e. does not attempt to map two pixels to the same position) and periodic. We will use a map based on the Fibonacci sequence. Fibonacci SequenceRemember the Fibonacci sequence, 0, 1, 1, 2, 3, 5, 8, 13, 21, etc? It was generated with a simple recurrence relation, Y(n+1) = Y(n) + Y(n-1), starting from two seed values, Y(0) = 0, Y(1) = 1. To get the next Fibonacci number, we add together the previous two. So to take a step forward, we need to know (at least) the two previous numbers. Let's define a new variable, X(n+1) = Y(n). Then the recurrence relation can be rewritten like this:
What's the point of writing the recurrence relation in this way? Well, now we have two numbers, X and Y, which in a moment we will think of as the x and y coordinates of a pixel. And we have a rule for iterating (i.e. moving them around). But first, we need to talk about: Modular ArithmeticEach Fibonacci number is bigger than the last. The numbers in the sequence just keep on increasing, and there's no upper limit. To use the numbers in the Fibonacci sequence as coordinates for pixels in an image, we need to find a way to restrict them to a fixed range. We have already met such a way: we may take a remainder. In Python, the remainder of k when divided by N is found with In maths, "taking the remainder" is the key operation in modular arithmetic (also called clock arithmetic), which is a system of arithmetic for integers, in which numbers "wrap around" upon reaching a certain value N. Here N is called the modulus, and the remainder of k when divided by N is called "k modulo N" and is written as k (mod N). A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. On a 12-hour clock, 1pm on Tuesday appears exactly the same as 1am on a Friday. Time "wraps around" on the clock, and the hour of day is always in the range 1 to 12.
Pisano PeriodsLet's think about the Fibonacci numbers modulo N (in other words, the remainders of the Fibonacci numbers when divided by N). Here is some Python code for generating a sequence modulo N=8: nmax = 36Fib = [0,1]for k in range(2, nmax): Fib.append(Fib[-1] + Fib[-2])N = 8FibmodN = [F % N for F in Fib]print FibmodNThis code should generate a sequence like this: 0,1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,3,5,0,5,5,2,7,1, ... Look carefully at the sequence. Do you see the pattern? The sequence repeats itself - did you spot this? The sequence above is generated from a repeated block of length 12, i.e. 0,1,1,2,3,5,0,5,5,2,7,1, 0,1,1,2,3,5,0,5,5,2,7,1, 0,1,1,2,3,5,0,5,5,2,7,1, etc. Now try changing N to another number (e.g. N=7). Can you find the new repeating pattern? How long is it? Repeating patterns in the Fibonacci sequence modulo N were first spotted by Lagrange in 1774. The Nth Pisano period, written π(N), is the period with which the sequence of Fibonacci numbers, modulo N repeats. So the 8th Pisano period is 12. Pisano periods of other N are given in this long list. The MapThe Fibonacci sequence modulo N gives us a rule for moving the (x,y) coordinates of single pixel. For example, modulo N=8, the pairs of (x,y) values in the Fibonacci sequence are (0,1) -> (1,1) -> (1,2) -> (2,3) -> (3,5) -> (5,0) -> (0,5) -> (5,5) -> (5,2) -> (2,7) -> (7,1) -> (1,0) -> (0,1) In fact, we can start with any two seed values (X0, Y0) and we will get a sequence whose length is the Pisano period. For example, try changing the initial values using (6,7) -> (7,5) -> (5,4) -> (4,1) -> (1,5) -> (5,6) -> (6,3) -> (3,1) -> (1,4) -> (4,5) -> (5,1) -> (1,6) -> (6,7) There are 5 such sequences for N=8, each of length 12, so this gives us a rule for moving all 64 pixels in the 8 x 8 square. The ProgramThe AlgorithmWe want to write a program which does the following:
Here is the rule: xk+1 = yk % N yk+1 = (xk + yk) % N where % indicates the "remainder" operation. Here (xk, yk) are the coordinates of a pixel at the kth step, and (xk+1, yk+1) are the new coordinates. If you are feeling confident, you may now want to write a Python program yourself, to implement the Fibonacci Feline map. Or you may wish to look at: Example CodeAttached below is a Python program, Much of the code is similar to last week's code for the animated sieve. For example, we load an image, retrieve a ( import copyI also rescaled the displayed image to be twice as big as the original image, using: pygame.transform.scale2x(mysurf, screen)Exercises
|
Tutorials >
