A gif prepared on the image below by performing Arnold's cat map transform

Author: thethreesisters, Source: Flickr, License: CC by 2.0

Today let us discuss Arnold's cat map tranform. I would like to keep this article less technical so that anyone can understand it. Let us start by seeing what Wikipedia says about this cat map transform:

In mathematics, Arnold's cat map is a chaotic map from the torus into itself, named after Vladimir Arnold, who demonstrated its effects in the 1960s using an image of a cat, hence the name.

So Arnold's map is a chaotic map. Don't panic by hearing chaotic maps. Chaotic maps are those functions which iteratively maps an input space(a set of numbers) to output space(another set of numbers). (The terms input space and output space may not be very technical. It is just for explaining purposes in this article.) It keeps on repeating that process and exhibits chaos. What does chaos means exactly? It simply means that a small change in the input creates an output which is entirely different than that of the original output.

One popular analogy which I can think of is this: Imagine a chef preparing dough for making pizza/chapati. So the chef is presented with a input space, which is the dough. Now the chef is going to apply a chaotic map onto this input space(dough). The function/map here are the operations which the chef repeatedly doing to the dough. Let us imagine that the chef performs these operations repeatedly onto the dough:

beat the dough
stretch the dough
fold it back
roll it to a sphere
repeat the processes 1. to 4.

Let the chef repeats this for N steps. Where is the chaos here? To understand chaos, let us assume there are 2 imaginary points in the dough ball initially. And let us track the shortest distance between those 2 points as the chef performs his algorithm on the dough. We can draw trajectories for this scenario. As an example see the plot below:

The initial points are 0 and 0.1 here for the blue and red curves here. Naively I would have imagined both red and blue curves moving on top of the other. But, see the divergence of both of these curves. Both of them emerge from the same Algorithm. But a slight change in the initial condition makes the curves to diverge in behavior. You can imagine the same happening to the shortest distance between 2 points on the dough. Even a small change in the positioning of the second point would have diverged the behavior of their distance trajectories.(Also I would like to emphasize that these curves have nothing to do with randomness. Chaos is purely deterministic.)

Let us see the rules of Arnold's cat map transform algorithm which the chef has to perform on images.(See the reference [1] for those who need a mathematical treatment of the subject. This paper calculates some bounds for the number of iterations(period) necessary to see the original image again.)

Arnold's cat map is a chaotic map applied on images. As you can see there are two operations. First one is shearing image( For those who want to understand what a linear transform is please see one of my early articles.) and the second one is slicing and putting it back to square via modulo operation. For certain kind of transformations, repeating this process multiple times ends up in the original picture as we started. But it is not easy to predict the number of steps(period) when we see the original image again! This period is dependent on the dimension of the image(in a complicated way). There are certain bounds etc for this. See ref [1] for the details.(The original image is from Paul Downey, Source: Flickr, License: CC by 2.0)

Mathematically:
(x_n+1, y_n+1) = (x_n + y_n, x_n + 2y_n) mod N

(Shearing operation + modulo operation)

n+1 subscript stands for the step corresponding to the transformed output from n^th step. x and y represents the spatial pixel dimensions of the images.

As you can see it takes 48 iterations for a 576x576 image to repeat itself in Arnold's tranform algorithm.(See the gif below)

Matlab Code


clear
A=imread('Cheshire_cat.jpg');

s=size(A);
s=min(s(1),s(2));
A = imresize(A,[s s]);

iter=96;
N=s;
Aold=A;
Anew=A;
h=figure
for i=1:iter
    for x = 1 : s
        for y = 1 : s
            xmap = mod(x+y, N) + 1;
            ymap = mod(x+2*y, N) + 1;
            Anew(x, y, :) = Aold(xmap, ymap, :);
        end
    end
imshow(Anew)
title(sprintf('Iteration %d', i))
pause(0.1)

    drawnow 
      % Capturing image
      frame = getframe(h); 
      im = frame2im(frame); 
      [imind,cm] = rgb2ind(im,256); 
      % Writing to GIF File 
      if i == 1 
          imwrite(imind,cm,'cat.gif','gif', 'Loopcount',inf); 
      else 
          imwrite(imind,cm,'cat.gif','gif','WriteMode','append'); 
      end 


Aold=Anew;
end

See the Github Repository.

Some Arnold transform trivia

One important point to note that all the Arnold transform matrices will have a determinant 1. So play around with the code which I have uploaded.
The recurrences of the patterns are called Poincare's Recurrannce. This indirectly says that order emerges out of chaos if we wait for enough(that can be the age of the universe too! :P). This has deep implications in statistical mechanics etc. We know that entropy in the universe on average increases and as an example physicists say that it is very very improbable to see that a broken glass coming back to a proper one. But this nonlinear dynamics system(Arnold transform) shows that even after scrambling images a lot of time, sometimes the original one re-emerges whereby there is a dip in entropy. (I am open to discussion regarding these points. So don't forget to comment below!)

Reference

#steemSTEM

#steemSTEM is a very vibrant community on top of STEEM blockchain for Science, Technology, Engineering and Mathematics (STEM). If you wish to support steemstem visit the links below:

Have you voted for steemSTEM Witness?

Quick link for voting for the SteemSTEM Witness(@stem.witness)

Delegation links for @steemstem give ROI of 65% of curation rewards

(quick delegation links: 50SP | 100SP | 500SP | 1000SP | 5000SP | 10000SP).

Also visit the steemstem app here: https://www.steemstem.io

All images without image sources are my creations :)

Follow me @dexterdev

 ____ _______  ______ _________ ____ ______    
/  _ /  __\  \//__ __/  __/  __/  _ /  __/ \ |\
| | \|  \  \  /  / \ |  \ |  \/| | \|  \ | | //
| |_/|  /_ /  \  | | |  /_|    | |_/|  /_| \// 
\____\____/__/\\ \_/ \____\_/\_\____\____\__/

credit: @mathowl

Bye! STEEM ON!

Sort:

Trending

[-]

steemstem (73) 7 years ago

This post has been voted on by the SteemSTEM curation team and voting trail in collaboration with @utopian-io and @curie.

If you appreciate the work we are doing then consider voting all three projects for witness by selecting stem.witness, utopian-io and curie!

For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!

$0.94

3 votes

lemouth (74) 7 years ago

Do you have by any chance examples of practical applications of this kind of maps? Thanks!

PS: I love the cat output :D

$0.00

1 vote

dexterdev (63) 7 years ago

I just saw that this transform is applied to encrypt images. Attaching the researchgate link to a related publication: https://www.researchgate.net/publication/309463059_Arnold's_Cat_Map_Algorithm_in_Digital_Image_Encryption

I am yet to see other applications in real world.

Thanks! Don't hesitate to share anything you could you hear about future applications of this.

Okay 😃

Thank you😻.

irelandscape (62) 7 years ago

Reminds me of my old TV. ;-)

dexterdev (63) 7 years ago (edited)

We used to call those noise patterns as grains 😂

mathowl (66) 7 years ago (edited)

What is the size of the matrix s for your cat jpg? I am guessing that it has just the right size for periodicity to occur.

Posted using Partiko Android

the original size was 576x640. But for simplicity of coding, I resized it to 576x576.

I am guessing that it has just the right size for periodicity to occur.

that is a right guess. there are some bounds for this periodicity. From https://arxiv.org/pdf/1111.2984.pdf

And some samples:

mathowl (66) 7 years ago

Let B be the matrix associated to the Arnold map, so B =[1 1;1 2] . Then with some effort you can show that B^48 mod 576 is equal to the identity matrix. This explains the result.

$0.03

2 votes

Oh ok. That is a nice find. But is there a general rule to find periodicity of any number sized image?

So you can write B as B=invXDX where X is the eigen matrix with corresponding eigenvalues on the diagonal of the diagonal matrix D. It is then easy compute B^m you then need to find an m such that B^m mod size of your matrix is equal to the identity matrix. So this gives you equations to find the periodicity

$0.04

Again to find m I will have to iterate till I see identity matrix right? So that means it is sometimes computationally intensive right?

When you iterate you only have to compute D^m D is a diagonal matrix so that is pretty easy to compute. X and invX stay the same. More specifically B^m=invX D^m X

$0.05

Ah so I guess it is 576. 576=48x12. Probably there is some kind of reason for this.

utopian-io (71) 7 years ago

Hi @dexterdev!

Your post was upvoted by Utopian.io in cooperation with @steemstem - supporting knowledge, innovation and technological advancement on the Steem Blockchain.

Contribute to Open Source with utopian.io

Learn how to contribute on our website and join the new open source economy.

Want to chat? Join the Utopian Community on Discord https://discord.gg/h52nFrV

Fun with Arnold's cat map transform