Consider taking a square image, consisting of N-by-N pixels, where the coordinate of each pixel is represented by the ordered pair (X, Y).
Arnoldβs cat map induces a discrete-time dynamical system in which the evolution is given by iterations of the mapping Ξπππ‘ βΆ π2 β π2 given the formula
Let the nth number of the Fibonacci sequence be defined by the recurrence relation πΉπ = πΉπβ1 + πΉπβ2 with πΉ0 =0, πΉ1 =1. We can get the f irst Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Hence, the matrix representation of πΉ=[0 1 1 1]=[πΉ0 πΉ1 πΉ1 πΉ2] will generate the sequence πΉπ =[πΉπβ1 πΉπ πΉπ πΉπ+1 ]
Letβs say we iterate twice πΉ2, then πΉ =[0 1 1 1][0 1 1 1]=[1 1 1 2] which is also equal to the largest eigenvalue of πΉ.
Back in 1774, Lagrange discovered repeating patterns in the Fibonacci sequence πππ π. The ππ‘β Pisano period, written π(π), is the number of times the Fibonacci sequence, modulo π, repeats.
For example, if we take the first 15 Fibonacci numbers πΉ15 with πΉ0 =0, πΉ1 =1, we will get 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377 Then we take the remainder using the modular arithmetic of each number π in the sequence by dividing it to the π.
If π =3, we will get 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2
with a pattern of:
0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2
As a result, we can see the 3rd Pisano period is 8.
At first, we want to load the image and get its width and height
img = Image.open(input_img)
width, height = img.width, img.height
In this program, user may only take a square size of the image. If the condition does not meet this requirement, we can create a function that resizes it to square.
def resize_img(self, img) -> Image:
min_size = min(img.size)
imageBoxSize = 200 # maximum width of image placeholder
# arnold's cat map must be square
if min_size >= imageBoxSize:
resized_im = img.resize((imageBoxSize,imageBoxSize))
else:
resized_im = img.resize((min_size,min_size))
return resized_im
This simply explains to resize the image to the desired size if the image exceeds the value of the image placeholderβs otherwise, resize the image to its minimum size of (width, height) to make a square image.
Now to make the chaotic map, we can create a new canvas and take the image we have as reference.
canvas = Image.new(img.mode, (img.width, img.height))
Given by the formula for Arnoldβs Cat Map, we can draw and apply the rule on each pixel of the image in the π₯ and π¦ coordinates of the canvas and setting the π equal to the width or height of the image. Thus,
done = False
while not done:
for x in range(canvas.width):
for y in range(canvas.height):
nx = (2 * x + y) % canvas.width
ny = (x + y) % canvas.height
canvas.putpixel((nx,canvas.height-ny-1),img.getpixel((x, canvas.height-y-1)))
self.iteration += 1
new_image = self.images_path + f'ACM-{namex}-{self.iteration}.png'
canvas.save(new_image)
img = Image.open(new_image)
if images_the_same(self.images_path + f'ACM-{namex}-0.png', new_image):
done = True
This is done by iterating infinitely until we get the same image with the help of OpenCV module in python.
import cv2
def images_the_same(image1, image2):
"""
:param image1: path of image1
:param image2: path of image2
:return: True if images are the same, False if images are not the same
"""
im1 = cv2.imread(image1)
im2 = cv2.imread(image2)
if im1.shape != im2.shape:
return False
difference = cv2.subtract(im1, im2)
b, g, r = cv2.split(difference)
if (cv2.countNonZero(b) == 0 and cv2.countNonZero(g) == 0 and cv2.countNonZero(r) == 0):
return True
return False
As we recall the imageBoxSize is sets to 200 because the higher size of the image will result in longer process of doing the map. Overall, the time complexity represented in Big O notation of this program is π(π2)+π where π represents the width and height of the image and π is the iteration until the original image reappears.