Zoom on a Random Walk

After reading Darren's post about the Mandelbrot set I was browsing through the Wikipedia entry on the Mandelbrot set which has a few amazing animations of really deep zooms on the fractal bounded by the set.

The good/bad thing about fractals is that as you magnify them, the pattern and resulting image that you see is in some way similar to patterns you saw at lower magnifications. So the zooms are in some sense self-similar.

It occurred to me that viewing random walks at different magnifications should have a similar property. You should not be able to tell what magnification you are looking at, since the average trajectory should be random, regardless of the scale of the trajectory. As long as you are away from the scale at which you can observe any discrete steps making up the walk, that is.

So, we should be able to make semi-infinite zooms of random walks, in which all magnifications look believably random and as if they were generated from the same process but without any repeating or recurring patterns. I think the random walks are quite pleasing to look at. It is a bit tricky to create this zoom though, since I can't think of any cunning way to step from one magnification to another by "filling in" the gaps in the walk that have just come into view. So I have to create a massive random walk image, and progressively resize and crop it to achieve the zoom. Also, the PyGame code I posted a while ago is too slow for generating a massive random walk. However, there's no need to see the walk being generated in this case, so we can just colour pixels black and anti-alias during image resize (using the Python Imaging Library) instead of doing it in real-time.

Deep zooming is cool anyway as you can see in the amazing Powers of Ten video by Charles and Ray Eames.

So, here's a zoom on a random walk that I made (approximately 100 times zoom, made on a 32-bit machine with 3.5Gb RAM):

Zoom on a Random Walk


The frames were generated with the Python code below. If you have a more powerful computer than me to hand, you can generate a deeper zoom! Just increase the width and height parameters until you run out of memory or patience. I patched the output images together and created a .gif animation using the amazing VirtualDub. 

import PIL,random,math,os

from PIL import Image,ImageDraw

 

# Define screen size and initialize

size=width,height=3500,3500

plot=Image.new("L",(width,height),'white')

pix=plot.load()

 

# Output Frame size

wf,hf=250,250

# Zoom parameters

zmax,zno=1.0,700

 

# Start at centre of image

x,y=width/2,height/2

pix[x,y]=0

 

# Prepare to find the bounding box for the walk

xmin,ymin,xmax,ymax=x,y,x,y

pcount=0

 

# Start walking until we hit the edge

while 1<=x<width-1 and 1<=y<height-1:

        # Generate new steps

        xnew=x+random.randint(-1,1)

        ynew=y+random.randint(-1,1)

        x,y=xnew,ynew

        pix[x,y]=0

        pcount+=1

        if x<xmin:xmin=x

        if x>xmax:xmax=x

        if y<ymin:ymin=y

        if y>ymax:ymax=y

 

# Crop to the walk      

plot=plot.crop((xmin,ymin,xmax,ymax))

 

# Rotate if necessary to make image wider than tall

if xmax-xmin<ymax-ymin:

        plot=plot.rotate(90)

(w,h)=plot.size

 

# Set minium zoom to just capture entire walk

zmin=float(wf)/float(w)

 

# For geometric zooming:

# zoom(z) = a*pow(phi,b*z)

# insist that zoom(0)=zmin, zoom(zno)=zmax

phi=10.0

a=zmin

b=math.log(zmax/zmin,phi)/zno

 

for z in xrange(0,zno+1):

        zoom=a*pow(phi,b*z)

        print "FRAME: ",z, zoom

        blank=Image.new("L",(wf,hf),'white')

        if z>0 and z%50==0:

                # Throw away pixels to achieve deeper zoom with set memory

                cz=float(hf)/float(hnew)

                xa=max(0,int(round(float(w)/2.0-cz*float(w)/2.0)))

                ya=max(0,int(round(float(h)/2.0-cz*float(h)/2.0)))

                xb=min(w,int(round(float(w)/2.0+cz*float(w)/2.0)))

                yb=min(h,int(round(float(h)/2.0+cz*float(h)/2.0)))

                plot=plot.crop((xa,ya,xb,yb))

                (w,h)=plot.size

        wnew=int(round(zoom*float(w)))

        hnew=int(round(zoom*float(h)))

        # Resize the frame

        small=plot.resize((wnew+1,hnew+1),Image.ANTIALIAS)

        # This crop is to trim grey lines which appear

        small=small.crop((1,1,wnew+1,hnew+1))

        xmin=int(round(float(wnew)/2.0-float(wf)/2.0))

        ymin=int(round(float(hnew)/2.0-float(hf)/2.0))

        xmax=int(round(float(wnew)/2.0+float(wf)/2.0))

        ymax=int(round(float(hnew)/2.0+float(hf)/2.0))

        if wnew<wf or hnew<hf:

                frame=Image.new("L",(wf,hf),'white')

                px=int(round(float(wf-wnew)/2.0))

                py=int(round(float(hf-hnew)/2.0))

                frame.paste(small,(px,py))

        else:

                frame=small.crop((xmin,ymin,xmax,ymax))

        fname="FrameL%05d.png"%z

        frame.save(fname)

 

print "Zoom: ",1.0/zmin

print "Steps: ",pcount