Arnolds kat

In de wiskunde is Arnolds kat een dynamisch systeem uit de chaostheorie met een bijhorende transformatie Γ, die een tweedimensionale torus transformeert naar zichzelf. De naam is afkomstig van de Russische wiskundige Vladimir Arnold, die in de jaren zestig de effecten van deze transformatie demonstreerde met behulp van de afbeelding van een kat.

Beschouw de torus ${\displaystyle \mathbb {T} }$, die ontstaat als algebraïsch quotiënt ${\displaystyle \mathbb {R} ^{2}/\mathbb {Z} ^{2}}$. De transformatie die centraal staat in het systeem Arnolds kat is de transformatie ${\displaystyle \Gamma :\mathbb {T} \to \mathbb {T} }$ gedefinieerd via de volgende formule:

${\displaystyle \Gamma (x,y)=(2x+y,x+y){\bmod {1}}.}$

De transformatie ${\displaystyle \Gamma }$ kan ook beschouwd worden als een transformatie van het eenheidsvierkant naar zichzelf in een vlak assenstelsel. De volgende afbeelding laat zien hoe de transformatie Γ het eenheidsvierkant uitrekt tot een parallellogram. Daarna worden de vier driehoekige onderdelen van het parallellogram herschikt in datzelfde eenheidsvierkant via modulair rekenen (modulo 1).

De transformatie ${\displaystyle \Gamma :\mathbb {T} \to \mathbb {T} }$ kan ook als volgt in matrixnotatie gedefinieerd worden:

${\displaystyle \Gamma \left({\begin{bmatrix}x\\y\end{bmatrix}}\right)={\begin{bmatrix}2&1\\1&1\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}{\bmod {1}}={\begin{bmatrix}1&1\\0&1\end{bmatrix}}{\begin{bmatrix}1&0\\1&1\end{bmatrix}}{\begin{bmatrix}x\\y\end{bmatrix}}{\bmod {1}}.}$

De naam Arnolds kat wordt ook gebruikt om de bijhorende transformatie ${\displaystyle \Gamma }$ aan te duiden, zoals verder in dit artikel.

Eigenschappen

• De transformatie ${\displaystyle \Gamma }$ is omkeerbaar, omdat de determinant van de transformatiematrix gelijk is aan 1 zodat de matrix van de inverse transformatie enkel gehele getallen bevat.
• De transformatie ${\displaystyle \Gamma }$ behoudt de oppervlakte.
• De transformatie ${\displaystyle \Gamma }$ is een voorbeeld van een anosovdiffeomorfisme, zie "Anosov diffeomorphism" op de Engelstalige Wikipedia.

Toepassing op de discrete wiskunde

In de discrete wiskunde kan de transformatie Arnolds kat gebruikt worden om discrete elementen, zoals de pixels van een afbeelding, te verwisselen van plaats. Bij toepassing van de transformatie op een afbeelding zal er altijd een cyclus ontstaan, waarbij de originele afbeelding terugkeert na een eindig aantal iteraties, omdat de afbeelding opgebouwd is met een eindig aantal pixels.

Voorbeeld met een afbeelding van negen pixels

In de afbeelding wordt getoond hoe de transformatie Arnolds kat de negen pixels (genummerd van 1 tot 9) van een afbeelding van plaats wisselt. Na vier iteraties komt de originele afbeelding terug tevoorschijn.

De x- en y-waarden van elke pixel staan respectievelijk boven de afbeelding en links van de afbeelding. In dit voorbeeld wordt gerekend 'modulo 3' omdat de afbeelding drie kolommen en drie rijen heeft. De volgende transformatie is hier van toepassing:

${\displaystyle \Gamma (x,y)=(2x+y,x+y){\bmod {3}}.}$

Voorbeeld met een kat

De transformatie Arnolds kat wordt toegepast op een afbeelding van 150×150 pixels met een kat. Deze transformatie is een mooie en eenvoudige toepassing binnen de chaostheorie: na een paar iteraties is de kat helemaal onherkenbaar en de afbeelding ziet er totaal willekeurig uit. Hieronder zie je de originele afbeelding en het resultaat na 1, 2 en 10 iteraties van de transformatie Arnolds kat:

Voorbeeld met een kat, eerste deel.

Maar het is eigen aan een transformatie in de chaostheorie dat er een strenge orde aanwezig is. Inderdaad, bekijk maar het resultaat na de 100e en 200e iteratie hieronder, en merk op dat na 300 iteraties de originele kat terugkomt.

Voorbeeld met een kat, tweede deel.

Voorbeeld met twee kersen

De transformatie Arnolds kat wordt toegepast op een afbeelding van 74×74 pixels met twee kersen. Na 114 iteraties krijgen we de originele afbeelding met de kersen terug. Let op het resultaat na 57 iteraties (halfweg): je ziet de twee kersen ondersteboven.

Voorbeeld met twee kersen.

Python-code voor Arnolds kat

De volgende code is overgenomen van het artikel Arnold's cat op de Engelse Wikipedia.

import os

from PIL.Image import open as load_pic, new as new_pic


def main(path, iterations, keep_all=False, name="arnold_cat-{name}-{index}.png"):
  """
  Params
    path:str
      path to photograph
    iterations:int
      number of iterations to compute
    name:str
      formattable string to use as template for file names
  """
  title = os.path.splitext(os.path.split(path)[1])[0]
  counter = 0
  while counter < iterations:
    with load_pic(path) as image:
      dim = width, height = image.size
      with new_pic(image.mode, dim) as canvas:
        for x in range(width):
          for y in range(height):
            nx = (2 * x + y) % width
            ny = (x + y) % height

            canvas.putpixel((nx, height-ny-1), image.getpixel((x, height-y-1)))

    if counter > 0 and not keep_all:
      os.remove(path)
    counter += 1
    print(counter, end="\r")
    path = name.format(name=title, index=counter)
    canvas.save(path)

  return canvas


if __name__ == "__main__":
  path = input("Enter the path to an image:\n\t")
  while not os.path.exists(path):
    path = input("Couldn't find your chosen image, please try again:\n\t")
  result = main(path, 3)
  result.show()