cat map method

I is an image; size(I)=[N N];

A=[1 a; b a*b+1];

where a and b are positive integers and det(A)=1.

I want to change the position of a pixel according to this equation

[x(n+1) y(n+1)]'= (A* [x(n) y(n)]')mod N;

where x and y are the position of pixels (ie i and j)

We say that the equation has period T if the pixel at location (x, y) returns to its original position after being transformed T times. The period T depends on the parameters a, b and size N of the original image.

how can I determine this period with a quick execution? you can see my test code proposed 4 days ago.

thank you

Answer 1

[Walter Roberson]

This is equivalent to Discrete Logarithm, about which it is said, "No efficient classical algorithm for computing general discrete logarithms logb g is known."

Thus, you should not expect to be able to solve this "with a quick execution".

See the reference for a list of algorithms.

[samia]

but I try to find a solution that is to construct a some functions:

function nv_vect=catmap(N,a,b)

A=[1 a; b a*b+1];

nv_vect=zeros(2,N*N);

c=1;

for i=0:N-1

for j=0:N-1

nv_vect(:,c)=mod(A*[i j]',N);

c=c+1;

end

end

nv_vect=uint8(nv_vect+1);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function J=consruct_imag(I,nv_vect,N)

c=1;

for i=1:N

for j=1:N

J(i,j)=I(nv_vect(1,c),nv_vect(2,c));

c=c+1;

end

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%

function J=cat_k_fois(I,N,a,b,k)

for g=1:k

nv_vect=catmap(N,a,b);

J=consruct_imag(I,nv_vect,N);

I=J;

end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function T=rech_k(I)

N=length(I);

a=1;k=1;k=1;

for(b=1:N-2)

while(k<=3*N)

K=cat_k_fois(I,N,a,b,k);

if(K==I)

T=k;break

else

k=k+1;

end

end

end

T;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

the main program is:

I=imread('image');

%% size(I)=N*N

T= rech_k(I);

%%%%%%%%%%%%%%%%%%%%%%

I hope that the function are clear now.

[Walter Roberson]

That's just the "repeated trial" approach, not the "quick execution" that you asked for.

[samia]

if I choose size(I)>=256 the execution takes a long time.

[Walter Roberson]

Well, Yes, that's the point. There is NO algorithm to do this that executes in polynomial time. No matter what you do, the program will get slower and slower the larger you make your matrix.

Answer 2

[Sean de Wolski]

web('http://2.bp.blogspot.com/_xuKCVllHCh4/RtA9fq_lgAI/AAAAAAAADcg/eXU0YxZ9Pg0/s1600-h/map.jpg')

Answer 3

[Walter Roberson]

Really, you are going about this the wrong way.

Any given pixel will return to its original position if and only if the net transformation matrices applied to it are equivalent to the identity matrix.

First of all, remember the properties of exponentiation and mod: ((x mod P) * (x mod P) * (x mod P) ... * (x mod P)) with a total of N terms, is always equal to (x^N) mod P.

Then, if you examine what you are doing, you will see that net transformation applied to [x,y] after T steps is

(A^T * [x;y]) mod N

and thus the condition that you need to satisfy is that (A^T) mod N is the identity matrix.

You do not need to transform any real matrices and compare them to the original: you just need to keep a running A^T matrix, multiply that by A, take the mod N, and see if you get the identity matrix out.

AI = eye(size(A));
AT = AI;
found = false;
numtries = 3*N;
for T = 1:numtries
  AT = mod(AT * A,N);
  if isequal(AT, AI); found = true; break;
end
if ~found
  disp('did not find period')
else
  fprintf('period was %d\n', T);
end

The periods can be tricky to predict by knowing "a" and "b", but perhaps I just did not look at it closely enough.