Part 3-2

This article is about “A Guide to ‘Fractal-Based’ Image Compression and Function Approximation” found at http://links.uwaterloo.ca/papers/waterloo/vr95.pdf. It is meant as a study aid to be read in parallel with the article. Python stuff is in bold.

I am going to talk about the one different IFSM in each part. The IFSM functions can be found in the library HGF.py which can be found here: http://paste.pocoo.org/show/556565/.

“Over the centuries the difference between representation and symbol tends to fade away. Once a meaning is established, the pictures we draw can become so stretched and distorted that their originators would barely recognize them. What begins as a representation, a crude picture, becomes stylized and abstracted until—as in the elaborate Chinese and Japanese ideographs called kanji—no more than a hint of the original image remains. But as long as we can distinguish one image from another, the meanings can be preserved.” - George Johnson, Fire in the Mind

The first thing that I thought that I would explore was the rotation and reflection functions. Not because the article said as much but because this might be the pathway to the elusive superfractal (that’s right, the mother of all fractals).

Remember the physics demonstration where there was glycerin in a flask and the demonstrator puts colored die in and then winds it up and winds it back (Laminar Flow http://www.youtube.com/watch?v=p08_KlTKP50). I was going to wind this image up into a fractal and just unwind it back into the image. When I looked at my eight tranformation functions it was obvious that there were only two functions rotation and reflection and that all I needed was a IFSM that could pass the angle to the function. The only extra number that I had was the gray value so naturally I wrote an IFSM that passes the gray value with the x and y coordinates. The graymaps made with this new IFSM showed some interesting structures but the hole function that I was using at the time just returned a zero and after repeated iterations zeros overtook the image. I decided that I needed a different hole function. Long story short I tried all kinds of stuff and finally settled on a function that just switches the real and imaginary parts of a complex number. To me it is a type of residual value, an invariant measure.

Lets take a look at the IFSM.

Some imports,

import Image, ImageDraw

import math,random,itertools

from HGF import *

some functions,

def imgtouxm(fname):

    img = Image.open(file(fname,’rb’))

    img  =  img  .resize((512,512))

    img  =  img  .convert(‘L’)

    imgdata =  img.getdata()

    uxm = zip(*[iter( imgdata  )]*img.size[0])

    return uxm

def imggray(gray,fname):

    im = Image.new(‘L’,(len(gray[int(len(gray)/2)]),len(gray)))

    for c,i in enumerate(gray):

        for k,l in enumerate(i):

            if l == None:

                l= 0

            elif l> 255:

                l = 255

            elif l < 0:

                l = 0.

            im.putpixel((k,c),int(l))

    im.save(file(fname,’wb’))

def rotation(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.21 +.5,y_prime*0.21 + .5,z[2])

def reflection(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*.21 + .5, y_prime*.21 +.5, z[2])

thetavalsadd = [0.3 for i in range(8)]

thetavals = [.5 for i in range(8)]

def Idxy1(x):

    return x*thetavals[0] + thetavalsadd[0]

def Idxy2(x):

    return x*thetavals[1]+ thetavalsadd[1]

def Idxy3(x):

    return x*thetavals[2] +thetavalsadd[2]

def Idxy4(x):

    return x*thetavals[3] +thetavalsadd[3]

def Idxy5(x):

    return x*thetavals[4]+ thetavalsadd[4]

def Idxy6(x):

    return x*thetavals[5] +thetavalsadd[5]

def Idxy7(x):

    return x*thetavals[6]+ thetavalsadd[6]

def Idxy8(x):

    return x*thetavals[7]+thetavalsadd[7]

the IFSmapping.

fnlist = [rotation, reflection]

Idxlist = [Idxy1,Idxy2,Idxy3,Idxy4,

            Idxy5,Idxy6,Idxy7,Idxy8]

uxmlena = imgtouxm(‘lena.png’)

uxmlena = [[complex(float(di)/255.,float(di)/255.) for di in j] for j in uxmlena ]

fsm = IFSmapping(fnlist,[(0.,0.,0.),(0.,0.,1.),(0.,1.,1.),

                                  (0.,1.,0.),(1.,0.,0.),(1.,0.,1.),(1.,1.,1.),(1.,1.,0.)])

A look at the graymap.

for i in range(40):    

    func,theta,gray = IFSM3d(uxmlena ,fsm,Idxlist)

    testreal = [[int(float(di.real)*255.) for di in j] for j in  gray ]

    testimag = [[int(float(di.imag)*255.) for di in j] for j in gray ]    

    imggray( testreal  ,’testrotref’ + str(i) +’.png’)

    imggray( testimag  ,’testrotrefI’ + str(i) +’.png’)

    uxmlena = gray

One time.

Real.

Imaginary.

Five times.

Real.

Imaginary.

Twenty times.

Real.

 

Imaginary.

Forty times.

Real.

Imaginary.

I really don’t know what the squares are. I think that they are visual representations of Banach’s Contraction Mapping Theorem of the outer edge of the picture that because of the theta values are Contraction maps.

So now that I have my glycerin flask I’m just going to unwind it.

some translation functions

def unrotation(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.21 +.5,y_prime*0.21 + .5,z[2])

def unreflection(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*.21 + .5, y_prime*.21 +.5, z[2])

A function to look at the fractal.

def fractimg(finalimg,fsm):

    klist = [[j.next() for j in i] for i in fsm.IFSlist]   

    for j in klist:

        for k in j:

            x,y,pt = int(k[0].real*512),int(k[1].real*512),abs(k[2])*255

            if x < 0:

                x = 0

            if y < 0:

                y = 0            

            if x > 511:

                x=511

            if y > 511:

                y=511

            if pt > 255:

                pt = 255

            finalimg[y][x] = (finalimg[y][x] + pt)/2.

    return finalimg

Make a list compatible with the translation functions.

newlist = []

for cy,i in enumerate(uxmlena):

    for cx,j in enumerate(i):

        newlist.append((float(cx)/len(i),float(cy)/len(uxmlena),abs(j)))

Our IFSmapping.

fsm = IFSmapping([unrotation,unreflection],newlist)

An empty uxm.

finalimg = [[0 for i in range(512)] for j in range(512)]  

and fill it up.

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’testfinalimgA.bmp’)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’testfinalimgB.bmp’)

And just for fun here’s Lena.

First pass.

second pass

Neither of these look like Lena.

What if I iterated the image through the process that I outlined in part 3-1. An interesting thing happens during the first pass.

fnlist = [rotation, reflection]

Idxlist = [Idxy1,Idxy2,Idxy3,Idxy4,

            Idxy5,Idxy6,Idxy7,Idxy8]

uxmlena = imgtouxm(‘lena.png’)

uxmlena = [[complex(float(di)/255.,float(di)/255.) for di in j] for j in uxmlena ]

fsm = IFSmapping(fnlist,[(0.,0.,0.),(0.,0.,1.),(0.,1.,1.),

                                  (0.,1.,0.),(1.,0.,0.),(1.,0.,1.),(1.,1.,1.),(1.,1.,0.)])

for i in range(7):

    func,theta,gray = IFSM3d(uxmlena ,fsm,Idxlist)

    testreal = [[int(float(di.real)*255.) for di in j] for j in  gray ]

    testimag = [[int(float(di.imag)*255.) for di in j] for j in gray ]    

    imggray(  testreal  ,’testgray’ + str(i) +’.png’)

    imggray(  testimag  ,’testgrayI’ + str(i) +’.png’)

    newmat = [[sum([Fct(Ui) for Fct in Fi]) + Ui for Ui,Fi in zip(U,F)] for U,F in zip( uxmlena  ,theta)]

    diffmat = [[Ni-Gi for Gi,Ni in zip(G,N)] for G,N in zip(gray,newmat)]

    divmat = [[ Di /len( Fi ) for  Fi , Di in zip(F,D)] for F,D in zip(func, diffmat )]

    testreal = [[int(float(di.real)*255.) for di in j] for j in  divmat ]

    testimag = [[int(float(di.imag)*255.) for di in j] for j in divmat ]    

    imggray(  testreal  ,’testlena’ + str(i) +’.png’)

    imggray(  testimag  ,’testlenaI’ + str(i) +’.png’)

    uxmlena  = divmat 

First gray real.

First gray Imaginary.

First divmat real.

First divmat imaginary.

Last gray real.

last gray Imaginary.

Last divmat real.

Last divmat imaginary.

Those concentric rings reminded me of deplictions of electron clouds. Go back and look at the first IFSM from the article (x*.6 + .4, x* .6) and notice how much it is like the double slit experiment.

I’m going to look at the fractal.

newlist = []

for cy,i in enumerate(uxmlena):

    for cx,j in enumerate(i):

        newlist.append((float(cx)/len(i),float(cy)/len(uxmlena),abs(j)))        

finalimg = [[0 for i in range(512)] for j in range(512)]       

fsm = IFSmapping([unrotation,unreflection],newlist)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’testfinalimgA.bmp’)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’testfinalimgB.bmp’)

How about the last graymap.

newlist = []

for cy,i in enumerate(gray):

    for cx,j in enumerate(i):

        newlist.append((float(cx)/len(i),float(cy)/len(uxmlena),abs(j)))

finalimg = [[0 for i in range(512)] for j in range(512)]       

fsm = IFSmapping([unrotation,unreflection],newlist)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,testfinalimgC.bmp’)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’testfinalimgD.bmp’)

Those don’t look like Lena either.

The Laminar flow theory of derfractalization was turning out to be a bust.

I was going to try one more thing.

def rotation(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.21 +.5,y_prime*0.21 + .5,z[2])

def reflection(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*.21 + .5, y_prime*.21 +.5, z[2])

def rotation2(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.21 + .5,y_prime*0.105 + .25,z[2])

def reflection2(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*.21+.5, y_prime*0.105+ .25, z[2])

def rotation3(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.21+.5,y_prime*0.105 + .75,z[2])

def reflection3(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*0.21+.5,y_prime*0.105 + .75,z[2])

def rotation4(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.105+.25,y_prime*0.21+.5,z[2])

def reflection4(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*0.105+.25,y_prime*0.21+.5,z[2])

def rotation5(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.105 +.75,y_prime*0.21 +.5,z[2])

def reflection5(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*0.105 +.75,y_prime*0.21 +.5,z[2])

fnlist = [rotation,rotation2,rotation3,rotation4

              ,rotation5,reflection,reflection2,reflection3

              ,reflection4,reflection5]

Idxlist = [Idxy1,Idxy2,Idxy3,Idxy4,

                Idxy5,Idxy6,Idxy7,Idxy8,Idxy1,Idxy1]

uxmlena = imgtouxm(‘c:\python27\tom\lena.png’)

uxmlena = [[complex(float(di)/255.,float(di)/255.) for di in j] for j in  uxmlena ]

fsm = IFSmapping(fnlist,[(0.,0.,0.),(0.,0.,1.),(0.,1.,1.), (0.,1.,0.),

                                                (1.,0.,0.),(1.,0.,1.),(1.,1.,1.),(1.,1.,0.)])

for i in range(7):

    func,theta,gray = IFSM3d(uxmlena ,fsm,Idxlist)

    testreal = [[int(float(di.real)*255.) for di in j] for j in  gray ]

    testimag = [[int(float(di.imag)*255.) for di in j] for j in gray ]    

    imggray(  testreal  ,’testgray’ + str(i) +’.png’)

    imggray(  testimag  ,’testgrayI’ + str(i) +’.png’)

    newmat = [[sum([Fct(Ui) for Fct in Fi]) + Ui for Ui,Fi in zip(U,F)] for U,F in zip( uxmlena  ,theta)]

    diffmat = [[Ni-Gi for Gi,Ni in zip(G,N)] for G,N in zip(gray,newmat)]

    divmat = [[ Di /len( Fi ) for  Fi , Di in zip(F,D)] for F,D in zip(func, diffmat )]

    testreal = [[int(float(di.real)*255.) for di in j] for j in  divmat ]

    testimag = [[int(float(di.imag)*255.) for di in j] for j in divmat ]    

    imggray(  testreal  ,’testlena’ + str(i) +’.png’)

    imggray(  testimag  ,’testlenaI’ + str(i) +’.png’)

    uxmlena  = divmat 

First gray real.

First gray Imaginary.

First divmat real.

First divmat imaginary.

Last gray real.

last gray Imaginary.

Last divmat real.

Last divmat imaginary.

I’m going to look at the fractal.

Functions first.

def unrotation(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.21 +.5,y_prime*0.21 + .5,z[2])

def unreflection(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*.21 + .5, y_prime*.21 +.5, z[2])

def unrotation2(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.21 + .5,y_prime*0.105 + .25,z[2])

def unreflection2(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*.21+.5, y_prime*0.105+ .25, z[2])

def unrotation3(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.21+.5,y_prime*0.105 + .75,z[2])

def unreflection3(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*0.21+.5,y_prime*0.105 + .75,z[2])

def unrotation4(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.105+.25,y_prime*0.21+.5,z[2])

def unreflection4(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*0.105+.25,y_prime*0.21+.5,z[2])

def unrotation5(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.105 +.75,y_prime*0.21 +.5,z[2])

def unreflection5(z):

    x,y,Th = z[0],z[1],z[2]

    Th = -Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*0.105 +.75,y_prime*0.21 +.5,z[2])  

newlist = []

for cy,i in enumerate(uxmlena):

    for cx,j in enumerate(i):

        newlist.append((float(cx)/len(i),float(cy)/len(uxmlena),abs(j)))

finalimg = [[0 for i in range(512)] for j in range(512)]       

fsm = IFSmapping([unrotation,unrotation2,unrotation3,unrotation4,

                               unrotation5,unreflection,unreflection2,unreflection3,

                               unreflection4,unreflection5],newlist)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’c:\python27\tom\testfinalimg32A.bmp’)

def scrunch1(z):

    x,y,Th = z[0],z[1],z[2]

    x = x* .5 + .5

    y = y

    return (x,y,z[2])

def scrunch2(z):

    x,y,Th = z[0],z[1],z[2]

    x = x * .5

    y = y

    return (x,y,z[2])

def scrunch3(z):

    x,y,Th = z[0],z[1],z[2]

    x = x

    y = y * .5 + .5

    return (x,y,z[2])

def scrunch4(z):

    x,y,Th = z[0],z[1],z[2]

    x = x

    y = y * .5

    return (x,y,z[2])

def scrunch5(z):

    x,y,Th = z[0],z[1],z[2]

    x = x * .5

    y = y * .5

    return (x,y,z[2])

def scrunch6(z):

    x,y,Th = z[0],z[1],z[2]

    x = x * .5 + .5

    y = y * .5 + .5

    return (x,y,z[2])

def scrunch7(z):

    x,y,Th = z[0],z[1],z[2]

    x = x * .5 + .5

    y = y * .5

    return (x,y,z[2])

def scrunch8(z):

    x,y,Th = z[0],z[1],z[2]

    x = x * .5

    y = y * .5 + .5

    return (x,y,z[2])

thetavalsadd = [0.3 for i in range(8)]

thetavals = [.5 for i in range(8)]

def Idxy1(x):

    return x*thetavals[0] + thetavalsadd[0]

def Idxy2(x):

    return x*thetavals[1]+ thetavalsadd[1]

def Idxy3(x):

    return x*thetavals[2] +thetavalsadd[2]

def Idxy4(x):

    return x*thetavals[3] +thetavalsadd[3]

def Idxy5(x):

    return x*thetavals[4]+ thetavalsadd[4]

def Idxy6(x):

    return x*thetavals[5] +thetavalsadd[5]

def Idxy7(x):

    return x*thetavals[6]+ thetavalsadd[6]

def Idxy8(x):

    return x*thetavals[7]+thetavalsadd[7]

fnlist = [scrunch1,scrunch2,scrunch3,scrunch4,

            scrunch5,scrunch6,scrunch7,scrunch8]

Idxlist = [Idxy1,Idxy2,Idxy3,Idxy4,

            Idxy5,Idxy6,Idxy7,Idxy8]

uxmlena = imgtouxm(‘lena.png’)

uxmlena = [[complex(float(di)/255.,float(di)/255.) for di in j] for j in uxmlena ]

fsm = IFSmapping(fnlist,[(0.,0.,0.),(0.,0.,1.),(0.,1.,1.),

            (0.,1.,0.),(1.,0.,0.),(1.,0.,1.),(1.,1.,1.),(1.,1.,0.)])

for i in range(13):

    func,theta,gray = IFSM3d(uxmlena ,fsm,Idxlist)

    newmat = [[sum([Fct(Ui) for Fct in Fi]) + Ui for Ui,Fi in zip(U,F)] for U,F in zip( uxmlena  ,theta)]

    diffmat = [[Ni-Gi for Gi,Ni in zip(G,N)] for G,N in zip(gray,newmat)]

    divmat = [[ Di /len( Fi ) for  Fi , Di in zip(F,D)] for F,D in zip(func, diffmat )]

    testreal = [[int(float(di.real)*255.) for di in j] for j in  divmat ]

   testimag = [[int(float(di.imag)*255.) for di in j] for j in divmat ]

    imggray(  testreal  ,’testlena’ + str(i) +’.png’)

    imggray(  testimag  ,’testlenaI’ + str(i) +’.png’)

uxmlena  = divmat 

testlena 0

testlena 3

testlena 8

testlena 12

Now that looks more like a fractal.

I’m going to try an unscrunch

def unscrunch1(z):

    x,y,Th = z[0],z[1],z[2]

    x = x/ .5 - .5

    y = y

    return (x,y,z[2])

def unscrunch2(z):

    x,y,Th = z[0],z[1],z[2]

    x = x / .5

    y = y

    return (x,y,z[2])

def unscrunch3(z):

    x,y,Th = z[0],z[1],z[2]

    x = x

    y = y / .5 - .5

    return (x,y,z[2])

def unscrunch4(z):

    x,y,Th = z[0],z[1],z[2]

    x = x

    y = y / .5

    return (x,y,z[2])

def unscrunch5(z):

    x,y,Th = z[0],z[1],z[2]

    x = x / .5

    y = y / .5

    return (x,y,z[2])

def unscrunch6(z):

    x,y,Th = z[0],z[1],z[2]

    x = x/ .5 - .5

    y = y / .5 - .5

    return (x,y,z[2])

def unscrunch7(z):

    x,y,Th = z[0],z[1],z[2]

    x = x / .5 - .5

    y = y / .5

    return (x,y,z[2])

def unscrunch8(z):

    x,y,Th = z[0],z[1],z[2]

    x = x / .5

    y = y / .5 - .5

    return (x,y,z[2])

A new fractal viewer.

def fractimg(finalimg,fsm):

    klist = [[j.next() for j in i] for i in fsm.IFSlist]

    for j in klist:

        for k in j:

            x,y,pt = int(k[0].real*512)+756,int(k[1].real*512)+756,k[2]*355 - 100

            if x < 0:

                x = 0

            if y < 0:

                y = 0

            if x > 2047:

                x=2047

            if y > 2047:

                y=2047

            if pt > 255:

                pt = 255

            finalimg[y][x] =  pt

    return finalimg

newlist = []

for cy,i in enumerate(uxmlena):

    for cx,j in enumerate(i):

        newlist.append((float(cx)/len(i),float(cy)/len(uxmlena),j.real))

finalimg = [[0. for i in range(2056)] for j in range(2056)]

fsm = IFSmapping([unscrunch1,unscrunch2,unscrunch3,unscrunch4,

                                  unscrunch5,unscrunch6,unscrunch7,unscrunch8],newlist)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’c:\python27\tom\testfinalimgscrunchA.bmp’)

 

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’c:\python27\tom\testfinalimgscrunchB.bmp’)

newlist = []

for cy,i in enumerate(uxmlena):

    for cx,j in enumerate(i):

        newlist.append((float(cx)/len(i),float(cy)/len(uxmlena),j.imag))

finalimg = [[255. for i in range(2056)] for j in range(2056)]

fsm = IFSmapping([unscrunch1,unscrunch2,unscrunch3,unscrunch4,

                            unscrunch5,unscrunch6,unscrunch7,unscrunch8],newlist)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,testfinalimgscrunchA.bmp’)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’testfinalimgscrunchB.bmp’)

Hard to see but it is a fractal. Now we’ll do that tiling thing with the new fractal maker.

A new fractaling function for the 16 x 16 tiles

def fractimg(finalimg,fsm):

    klist = [[j.next() for j in i] for i in fsm.IFSlist]

    for j in klist:

        for k in j:

            x,y,pt = int(k[0].real*len(finalimg[0])),int(k[1].real*len(finalimg)),abs(k[2])#+(len(finalimg[0])/2)

            if x < 0:

                x = 0

            if y < 0:

                y = 0

            if x >= len(finalimg[0]):

                x=len(finalimg[0])-1

            if y >= len(finalimg):

                y=len(finalimg)-1

            finalimg[y][x] =  pt

    return finalimg

prepare the blocks.

Idxlist = [Idxy1,Idxy2,Idxy3,Idxy4,

                 Idxy5,Idxy6,Idxy7,Idxy8]

lena = Image.open(file(‘c:\python27\tom\lena.png’,’rb’))

lena =  lena.convert(‘L’)

Parent_block = [[(i+k,j+l) for k,l in itertools.product(range(16),range(16))] for i,j in itertools.product(range(0,lena.size[0],16),range(0,lena.size[1],16))]

child_block = []

for i in Parent_block:

    child_block.append( [i[:int(len(i)/4)],i[int(len(i)/4):int(len(i)/2)],i[int(len(i)/2):int(len(i)/2)+int(len(i)/4)],i[int(len(i)/2)+int(len(i)/4):]])

A function for the process.

def nwefunc(uxm,fsm,Idxlist): 

 func,theta,gray = IFSM3d(uxm ,fsm,Idxlist)

    newmat = [[sum([Fct(Ui) for Fct in Fi]) + Ui for Ui,Fi in zip(U,F)] for U,F in zip( uxmlena  ,theta)]

    diffmat = [[Ni-Gi for Gi,Ni in zip(G,N)] for G,N in zip(gray,newmat)]

    divmat = [[ Di /len( Fi ) for  Fi , Di in zip(F,D)] for F,D in zip(func, diffmat )]

   return divmat 

A list to put the little fractals in.

IDlist = []

Go through the Parent Blocks make a fractal and put it in the list.

for ct in range(len(Parent_block)):

    uxm = map(lena.getpixel,Parent_block[ct])

    uxm = zip(*[iter(uxm)]*16)

    fnlist = [scrunch1,scrunch2,scrunch3,scrunch4,

                   scrunch5,scrunch6,scrunch7,scrunch8]

    fsm = IFSmapping(fnlist,[(0.,0.,0.),(0.,0.,1.),(0.,1.,1.),(0.,1.,0.),(1.,0.,0.),(1.,0.,1.),(1.,1.,1.),(1.,1.,0.)])

    newgray = nwefunc(uxm,fsm,Idxlist)

    for i in range(9):

        newgray = nwefunc(newgray,fsm,Idxlist)  

    IDlist.append(newgray)

A list for each little image that has been unscrunched.

finalimglist = []

finalimglist2 = []

fnlist = [unscrunch1,unscrunch2,unscrunch3,unscrunch4,unscrunch5,unscrunch6,unscrunch7,unscrunch8]

Go through the little fractal list, unscrunch and put the small images into the appropriate list.

for count,hh in enumerate(IDlist):    

    newlist = []

    for cy,i in enumerate(hh):

        for cx,j in enumerate(i):

            newlist.append((float(cx.real)/len(i),float(cy.real)/len(uxm3r),j))

    finalimg = [[0. for i in range(16)] for j in range(16)]    

    fsmu = IFSmapping(fnlist,newlist)

    fsm = IFSmapping([FnCx],newlist)

    finalimg = fractimg(finalimg,fsm)

    finalimglist.append(finalimg)    

    finalimg2 = [[random.uniform(.25,.35) for i in range(32)] for j in range(32)]

    finalimg2 = fractimg(finalimg2,fsmu)

    finalimglist2.append(finalimg2)    

make a new image and paste the tiles into it.

newImage = Image.new(‘L’,(lena.size[0],lena.size[1]),255)

Parent_block = [[(i+k,j+l) for k,l in itertools.product(range(16),range(16))] for i,j in itertools.product(range(0,newImage.size[0],16),range(0,newImage.size[1],16))]

for ii,j in zip(finalimglist,Parent_block):

    im = Image.new(‘L’,(len(ii[int(len(ii)/2)]),len(ii)))

    for c,i in enumerate(ii):

        for k,l in enumerate(i):

            if l == None:

                l= 0

            im.putpixel((c,k),int(l.real*255))    

    newImage.paste(im,j[0])

newImage.save(file(‘lenabigger.bmp’,’wb’))

newImage = Image.new(‘L’,(lena.size[0]*2,lena.size[1]*2),255)

Parent_block = [[(i+k,j+l) for k,l in itertools.product(range(32),range(32))] for i,j in itertools.product(range(0,newImage.size[0],32),range(0,newImage.size[1],32))]

for ii,j in zip(finalimglist2,Parent_block):

    im = Image.new(‘L’,(len(ii[int(len(ii)/2)]),len(ii)))

    draw = ImageDraw.Draw(im)

    for c,i in zip(range(len(ii)),ii):

        for k,l in zip(range(len(i)),i):

            if l == None:

                l= 0

            draw.rectangle((c,k,c+4,k+4),fill = int(l.real*255)+int(l.imag*255))

    newImage.paste(im,j[0])

newImage.save(file(‘c:\python27\tom\lenabigger2.bmp’,’wb’))

Not very visually apealing but I do feel that I have achieved a decent collage. In the next part I am going to try to use that collage to produce a formula for the image.

Comming soon part 3-3

The golden path.

So it has come to this. An ignorant, ill informed giggle wrapped in a chuckle and stuffed with monkey business in an all out battle royal against the greatest intelectual minds of our time, or not.

Consider this mess.

scrunchfactor = .24

scrunchadd = complex(.01,.01)

def scrunchandjulia1(z):

    x,y,j = z[0].real,z[0].imag,z[1]

    x = x* .5 + .5

    y = y

    x_p =  z[0]*scrunchfactor + scrunchadd

    Th = (j+x_p)/2.

    try:

        Th = Th**2 + complex(0,Th.imag)

    except OverflowError:

        Th = 1.

    return (complex(x,y),Th)

def scrunchandjulia2(z):

    x,y,j = z[0].real,z[0].imag,z[1]

    x = x *  .5

    y = y

    x_p =  z[0]*scrunchfactor + scrunchadd

    Th = (j+x_p)/2.

    try:

        Th = Th**2 + complex(0,Th.imag)

    except OverflowError:

        Th = 1.

    return (complex(x,y),Th)

def scrunchandjulia3(z):

    x,y,j = z[0].real,z[0].imag,z[1]

    x = x

    y = y * .5 + .5

    x_p =  z[0]*scrunchfactor + scrunchadd

    Th = (j+x_p)/2.

    try:

        Th = Th**2 + complex(0,Th.imag)

    except OverflowError:

        Th = 1.

    return (complex(x,y),Th)

def scrunchandjulia4(z):

    x,y,j = z[0].real,z[0].imag,z[1]

    x = x

    y = y *  .5

    x_p =  z[0]*scrunchfactor + scrunchadd

    Th = (j+x_p)/2.

    try:

        Th = Th**2 + complex(0,Th.imag)

    except OverflowError:

        Th = 1.

    return (complex(x,y),Th)

def scrunchandjulia5(z):

    x,y,j = z[0].real,z[0].imag,z[1]

    x = x *  .5

    y = y *  .5

    x_p =  z[0]*scrunchfactor + scrunchadd

    Th = (j+x_p)/2.

    try:

        Th = Th**2 + complex(0,Th.imag)

    except OverflowError:

        Th = 1.

    return (complex(x,y),Th)

def scrunchandjulia6(z):

    x,y,j = z[0].real,z[0].imag,z[1]

    x = x * .5 + .5

    y = y * .5 + .5

    x_p =  z[0]*scrunchfactor + scrunchadd

    Th = (j+x_p)/2.

    try:

        Th = Th**2 + complex(0,Th.imag)

    except OverflowError:

        Th = 1.

    return (complex(x,y),Th)

def scrunchandjulia7(z):

    x,y,j = z[0].real,z[0].imag,z[1]

    x = x  * .5 + .5

    y = y *  .5

    x_p =  z[0]*scrunchfactor + scrunchadd

    Th = (j+x_p)/2.

    try:

        Th = Th**2 + complex(0,Th.imag)

    except OverflowError:

        Th = 1.

    return (complex(x,y),Th)

def scrunchandjulia8(z):

    x,y,j = z[0].real,z[0].imag,z[1]

    x = x * .5

    y = y * .5 + .5

    x_p =  z[0]*scrunchfactor + scrunchadd

    Th = (j+x_p)/2.

    try:

        Th = Th**2 + complex(0,Th.imag)

    except OverflowError:

        Th = 1.

    return (complex(x,y),Th)

def fnCX1(j):

    try:

        return j**2 + complex(0,j.imag)

    except OverflowError:

        return 1.

Part 3-1 (of 3).

This article is about “A Guide to ‘Fractal-Based’ Image Compression and Function Approximation” found at http://links.uwaterloo.ca/papers/waterloo/vr95.pdf. It is meant as a study aid to be read in parallel with the article. Python stuff is in bold.

I am going to talk about the one different IFSM in each part. The IFSM functions can be found in the library HGF.py which can be found here: http://paste.pocoo.org/show/556565/.

To those of you out there who are knowledgeable and find yourself confused by my language: Don’t panic. You are not lost. What you are experiencing is a whole new type of mathematics, which itself is simply a revolutionary new way of understanding the behavior of numbers. Just as Albert Einstein’s general relativity theory observed that space was not an absolute but depended on the observer’s movement in time and that time was not an absolute but depended on the observer’s movement in space, so it is now realized that numbers are not absolute, but depend on the observer’s movement in restaurants. Let’s look at the explanation:

“The first nonabsolute number is the number of people for whom the table is reserved. This will vary during the course of the first three telephone calls to the restaurant and then bear no apparent relation to the number of people who actually turn up or the number of people who subsequently join them after the show/match/party/gig or to the number of people who leave when they see who else has shown up.

The second nonabsolute number is the given time of arrival, which is now known to be one of those most bizarre mathematical concepts, a recipriversexcluson, a number whose existence can only be defined as being anything other than itself. In other words, the given time of arrival is the one moment of time at which it is impossible that any member of the party will arrive. Recipriversexclusons now play a vital part in many branches of mathematics, including statistics and accountancy, and also form the basic equations used to engineer the Somebody Else’s Problem field.

The third and most mysterious piece of nonabsoluteness of all lies in the relationship between the number of items on the bill, the cost of each item, the number of people at the table, and what they are each prepared to pay for. (The number of people who have actually brought any money is only a sub-phenomenon in this field.)”

So remember that when you are confronted with questions like, “What is he doing?” and “Why is he doing it?” that it is not you who are confused but that the universe is confusing.

A note as to what has brought me to this article in the first place is in order. As the name implies I am first and foremost here for recreation, and as the name of the article says “The Hitchhiker’s Guide to…” I am drifting through a galaxy on tools made by giants.

When I first read about fractal compression it quickly pummeled my brain. So I decided I could write my own fractal compression (found here: http://paste.pocoo.org/show/557277/ ) using neural nets and the Fibonacci sequence. It goes like this: You take a 3 x 7 pixel, blend certian pixels together,

+++   -+-   -+-   —-   —-

+++   -+-   -+-   -+-   —-

+++   +++   -+-   -+-   -+-

+++   +++   -++   -+-   -+-

+++   +++   -+-   -+-   -+-

+++   -+-   -+-   -+-   —-

+++   -+-   -+-   —-   —-

and train a neural net between the steps. The results applied recursively look like this:

(Try adding a little noise between each recursion.) So when we came to the part about chopping Lena up into 8 x 8 pixels, I felt a little let down. This seems like doing the same thing in a different way, and that smacks of work, not recreation! Although I did really like the sqrt(x) function approximation thing so I thought that should persevere.

    When we last left off the author said, “Now let us return to a ‘real’ two-dimensional image.” I realised that I had only made a one-dimensional IFSM, so in a straightforward way I made an IFSM2d. It works the same way as the one-dimensional IFSM.

some imports

from HGF import *

import Image,itertools

start with a graymap.

uxm =[[255,0 ,0 ,0 ,0 ,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,160 ],

    [255,255,0 ,0 ,0 ,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,160 ],

    [255,0 ,255,0 ,0 ,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,140 ],

    [255,0 ,0 ,255,0 ,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,120 ],

    [255,0 ,0 ,0 ,255,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,100 ],

    [255,0 ,0 ,0 ,0 ,255,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,80 ],

    [255,0 ,0 ,0 ,0 ,0 ,255,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,60 ],

    [255,0 ,0 ,0 ,0 ,255,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,40 ],

    [255,0 ,0 ,0 ,255,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,20 ],

    [255,0 ,0 ,255,0 ,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,19 ],

    [255,0 ,255,0 ,0 ,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,18 ],

    [255,255,0 ,0 ,0 ,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,17 ],

    [255,0 ,255,0 ,0 ,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,16 ],

    [255,0 ,0 ,255,0 ,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,15 ],

    [255,0 ,0 ,0 ,255,0 ,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,5 ],

    [255,0 ,0 ,0 ,0 ,255,0 ,255,20 ,40 ,60 ,80 ,100 ,120 ,140 ,0 ]]

some functions

def scrunch1(z):

    x,y = z[0],z[1]

    x = x* .5 + .5

    y = y

    return (x,y)

def scrunch2(z):

    x,y = z[0],z[1]

    x = x * .5

    y = y

    return (x,y)

def a3(y):

    return y*.5 + .5

Make an IFSmapping.

fsm = IFSmapping([ scrunch1,scrunch2 ],[(0.,1.),(1.,1.),(0.,0.),(1.,0.)])

Run the IFSM2d function.

func,theta,gray = IFSM2d(uxm,fsm,[ a3 , a3 ])

Here’s a function to look at the graymap.

def imggray(gray,fname):

    im = Image.new(‘L’,(len(gray[int(len(gray)/2)]),len(gray)))

    for c,i in enumerate(gray):

        for k,l in enumerate(i):

            if l == None:

                l= 0

            elif l> 255:

                l = 255

            elif l < 0:

                l = 0.

            im.putpixel((k,c),int(l))

    im.save(file(fname,’wb’))

imggray(uxm,’testuxm.png’)

imggray(gray,’testgray.png’)

The Function map.

print func[0]

[[<function scrunch2 at 0x02A2C730>], [<function scrunch2 at 0x02A2C730>], [<function scrunch2 at 0x02A2C730>], [<function scrunch2 at 0x02A2C730>], [<function scrunch2 at 0x02A2C730>], [<function scrunch2 at 0x02A2C730>], [<function scrunch2 at 0x02A2C730>], [<function scrunch2 at 0x02A2C730>], [<function scrunch1 at 0x02A2C6F0>], [<function scrunch1 at 0x02A2C6F0>], [<function scrunch1 at 0x02A2C6F0>], [<function scrunch1 at 0x02A2C6F0>], [<function scrunch1 at 0x02A2C6F0>], [<function scrunch1 at 0x02A2C6F0>], [<function scrunch1 at 0x02A2C6F0>], [<function scrunch1 at 0x02A2C6F0>]]

The Thetamap.

print theta[0]

[[<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>], [<function a3 at 0x02A626B0>]]

On page nine the article has a discussion about what to do when formulas overlap. When I started messing around with 2D IFSM, I had eight formulas stacked on top of one another. The pixel values got out of control when summing the pixel values, especially with more exotic theta functions, so instead of adding the pixel values I’m taking the average. The reader is encouraged to chop, slop, smatter or puree the functions any way they would like. Holes are strictly forbidden, but when you squeeze images in two directions, holes are inevitable. They’re often called allizing errors, but for our purposes we’re going to think of them as Hausdorff dimensional omissions. I’ll explain. Suppose I have two scales of one hundred samples. Each one is a measure of grayscale from 0 to 100, the other is a measure of grayscale from 0 to 20, and you want to add them, so in computer world we would divide element x by the total 100 or 20 and stick it in some sort of list. The result is a stair step with one and a smooth line with the other. In math world the universe is always smooth, so the Hausdorff dimension tells us how to get from smooth to stepladder by describing balls that cover the smoothness of each step. I didn’t program this in, so when a hole occurs there is a hole function in HGF.py that fills it. There is also a hole function for the theta values. In later incarnations (part 2 and 3) I use these hole functions as a sort of invariant measure.

Now consider the image.

lena = Image.open(file(‘lena.png’,’rb’))

Convert to grayscale.

lena = lena.convert(‘L’)

Now I’m going to make a list of pixel coordinates tuples for the Parent block’s and the child_block’s. 

Parent_block = [[(i + k,j + l) for k,l in itertools.product(range(16),range(16) ) ] for i,j in itertools.product(range(0,lena.size[0],16 ), range(0,lena.size[1],16 ) ) ]

print Parent_block[0]

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10), (0, 11), (0, 12), (0, 13), (0, 14), (0, 15), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (1, 12), (1, 13), (1, 14), (1, 15), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10), (2, 11), (2, 12), (2, 13), (2, 14), (2, 15), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (3, 11), (3, 12), (3, 13), (3, 14), (3, 15), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (4, 6), (4, 7), (4, 8), (4, 9), (4, 10), (4, 11), (4, 12), (4, 13), (4, 14), (4, 15), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8), (5, 9), (5, 10), (5, 11), (5, 12), (5, 13), (5, 14), (5, 15), (6, 0), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6), (6, 7), (6, 8), (6, 9), (6, 10), (6, 11), (6, 12), (6, 13), (6, 14), (6, 15), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7), (7, 8), (7, 9), (7, 10), (7, 11), (7, 12), (7, 13), (7, 14), (7, 15), (8, 0), (8, 1), (8, 2), (8, 3), (8, 4), (8, 5), (8, 6), (8, 7), (8, 8), (8, 9), (8, 10), (8, 11), (8, 12), (8, 13), (8, 14), (8, 15), (9, 0), (9, 1), (9, 2), (9, 3), (9, 4), (9, 5), (9, 6), (9, 7), (9, 8), (9, 9), (9, 10), (9, 11), (9, 12), (9, 13), (9, 14), (9, 15), (10, 0), (10, 1), (10, 2), (10, 3), (10, 4), (10, 5), (10, 6), (10, 7), (10, 8), (10, 9), (10, 10), (10, 11), (10, 12), (10, 13), (10, 14), (10, 15), (11, 0), (11, 1), (11, 2), (11, 3), (11, 4), (11, 5), (11, 6), (11, 7), (11, 8), (11, 9), (11, 10), (11, 11), (11, 12), (11, 13), (11, 14), (11, 15), (12, 0), (12, 1), (12, 2), (12, 3), (12, 4), (12, 5), (12, 6), (12, 7), (12, 8), (12, 9), (12, 10), (12, 11), (12, 12), (12, 13), (12, 14), (12, 15), (13, 0), (13, 1), (13, 2), (13, 3), (13, 4), (13, 5), (13, 6), (13, 7), (13, 8), (13, 9), (13, 10), (13, 11), (13, 12), (13, 13), (13, 14), (13, 15), (14, 0), (14, 1), (14, 2), (14, 3), (14, 4), (14, 5), (14, 6), (14, 7), (14, 8), (14, 9), (14, 10), (14, 11), (14, 12), (14, 13), (14, 14), (14, 15), (15, 0), (15, 1), (15, 2), (15, 3), (15, 4), (15, 5), (15, 6), (15, 7), (15, 8), (15, 9), (15, 10), (15, 11), (15, 12), (15, 13), (15, 14), (15, 15)]

child_block = []

for i in Parent_block:

    child_block.append([i[:int(len(i) / 4)],

        i[int(len(i) / 4):int(len(i) / 2)],

        i[int(len(i) / 2):int(len(i) / 2)+int(len(i) / 4)],

        i[int(len(i) / 2)+int(len(i) / 4):]] )

print child_block[0][0]

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10), (0, 11), (0, 12), (0, 13), (0, 14), (0, 15), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10), (1, 11), (1, 12), (1, 13), (1, 14), (1, 15), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (2, 9), (2, 10), (2, 11), (2, 12), (2, 13), (2, 14), (2, 15), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (3, 11), (3, 12), (3, 13), (3, 14), (3, 15)]

So what did he say? 4 rotations, 4 mirror inversions.

So let’s see a rotation

def rotation(z,Th):

    x,y = z[0],z[1]

    x_prime = x * math.cos(Th) - y * math.sin(Th)

    y_prime = x * math.sin(Th) + y * math.cos(Th)

    return (x_prime,y_prime)

and a reflection (mirror)

def reflection(z,Th):

    x,y = z[0],z[1]

    x_prime = x * math.cos(Th) + y * math.sin(Th)

    y_prime = x * math.sin(Th) - y * math.cos(Th)

    return (x_prime,y_prime)

Four rotations.

def rot1(z):

    x,y = z[0],z[1]

    z = rotation((x,y),0)

    return z

def rot2(z):

    x,y = z[0],z[1]

    x = x

    y = y

    z = rotation((x,y),90)

    return z

def rot3(z):

    x,y = z[0],z[1]

    x = x

    y = y

    z = rotation((x,y),180)

    return z

def rot4(z):

    x,y = z[0],z[1]

    x = x

    y = y

    z = rotation((x,y),270)

    return z

Four reflections.

def ref1(z):

    x,y = z[0],z[1]

    x = x

    y = y

    z = reflection((x,y),0)

    return z

def ref2(z):

    x,y = z[0],z[1]

    x = x

    y = y

    z = reflection((x,y),90)

    return z

def ref3(z):

    x,y = z[0],z[1]

    x = x

    y = y

    z = reflection((x,y),180)

    return z

def ref4(z):

    x,y = z[0],z[1]

    z = reflection((x,y),270)

    return z

An IFSmapping.

fsm = IFSmapping([rot1,rot2,rot3,rot4,ref1,ref2,ref3,ref4],[(0.,1.),(1.,1.),(0.,0.),(1.,0.)])

Okay, make an IFSM with our test uxm

func,theta,gray = IFSM2d(uxm,fsm,[ a3 , a3 , a3 , a3  , a3  , a3  , a3  , a3  ])

imggray(gray,’testuxm.png’)

Now with a child block.

uxm = map(lena.getpixel,child_block[1][1])

uxm = zip(*[iter(uxm)]*8)

func,theta,gray = IFSM2d(uxm,fsm,[ a3 , a3 , a3 , a3  , a3  , a3  , a3  , a3  ])

imggray(gray,’testuxm2.png’)

Now a bunch of times.

for i in range(50):

    func,theta,gray = IFSM2d(gray,fsm,[ a3 , a3 , a3 , a3  , a3  , a3  , a3  , a3  ])

imggray(gray,’testuxm3.png’)

What the heck is that? That’s not useful or fun.

Here is what would be fun: to take the entire image and put it through the process.

A function to turn an image to an uxm

def imgtouxm(fname):

    img = Image.open(file(fname,’rb’))

    img  =  img  .resize((512,512))

    img  =  img  .convert(‘L’)

    imgdata =  img.getdata()

    uxm = zip(*[iter( imgdata  )]*img.size[0])    

    return uxm

uxmlena = imgtouxm(‘lena.png’)

A test.

imggray( uxmlena  ,’testlena.png’)

func,theta,gray = IFSM2d( uxmlena  ,fsm,[ a3 , a3 , a3 , a3  , a3  , a3  , a3  , a3  ])

imggray(gray,’testlena2.png’)

Now thats cool!

How about ten times this time?

for i in range(10):

     func,theta,gray = IFSM2d(gray,fsm,[ a3 , a3 , a3 , a3  , a3  , a3  , a3  , a3  ])

imggray(gray,’testlena3.png’)

What the heck is that? 

Let’s try different theta functions.

def a3(y):

    return y*.9 + .9

func,theta,gray = IFSM2d( uxmlena  ,fsm,[ a3 , a3 , a3 , a3  , a3  , a3  , a3  , a3  ])

for i in range(10):

func,theta,gray = IFSM2d(  gray  ,fsm,[ a3 , a3 , a3 , a3  , a3  , a3  , a3  , a3  ])

imggray(gray,’testlena3.png’)

Yea! Wheres my fractal? I don’t think this is what the author meant by four rotations and four inversions.

What I wanted is a fractal of the image that just put into the IFSmapping, and POW! ever increasing Lenas.

So I decided to go back to the test image. I was going to do the impossible. I was going to be clever like Waterloo mathematicians. Clever when I wake in the morning, clever when I drink tea, but most of all clever with fractals.

First run the IFSM function.

func,theta,gray = IFSM2d(uxm ,fsm,[a3,a3, a3,a3,a3,a3,a3 a3]) 

A look at the numbers in the graymap

for i in gray:

    for j in i:

        print round(j,2),

    print

158.38 94.13 33.16 0.89 20.01 58.25 0.87 94.11 70.34 15.5 80.18 144.87 99.31 113.79 74.23 92.56

196.33 36.46 70.82 31.37 4.47 4.47 137.15 49.89 84.07 96.72 48.42 35.75 57.12 112.25 80.75 84.03

137.15 115.65 33.16 30.78 53.19 31.37 119.22 103.11 63.18 63.0 57.28 68.97 93.12 95.67 128.32 105.99

104.88 0.89 115.65 33.16 69.03 0.87 174.81 82.81 28.38 38.78 57.14 71.13 81.82 95.39 100.43 88.4

107.27 29.57 0.9 115.65 16.14 68.13 185.57 39.79 60.34 95.36 56.5 58.25 84.75 108.04 100.59 85.85

43.9 101.29 0.89 0.87 176.61 37.66 120.7 62.05 59.82 88.36 110.4 101.55 113.1 114.51 99.31 81.2

36.73 74.4 61.85 36.75 120.57 1.45 119.57 63.44 90.05 62.76 11.56 65.02 108.01 118.98 104.67 39.18

65.42 104.88 5.37 118.55 61.6 178.1 26.98 52.85 58.27 110.83 94.69 84.7 83.85 82.07 74.56 33.1

73.2 107.41 159.46 5.95 52.05 130.41 28.95 52.7 62.98 44.21 107.91 110.23 106.18 66.14 114.47 34.0

49.01 143.9 15.14 84.63 40.55 117.52 9.89 58.04 64.74 67.69 111.64 84.7 94.69 61.62 100.86 29.03

107.04 84.98 56.43 15.72 40.07 158.39 26.75 62.82 35.56 75.64 83.09 89.2 97.59 52.59 102.04 31.54

109.86 57.26 68.39 21.35 62.18 133.08 70.64 110.5 64.35 82.87 65.29 126.89 98.72 52.14 102.04 30.23

116.98 22.25 126.45 23.2 137.34 49.75 40.83 68.88 92.04 127.67 77.34 81.84 98.72 51.69 102.04 29.29

121.11 32.37 96.98 60.16 138.7 38.57 63.26 87.21 43.92 70.34 73.97 90.84 43.37 81.68 95.18 10.8

68.98 89.75 102.42 8.75 174.07 12.87 32.95 91.58 49.22 61.59 75.04 90.79 41.74 81.68 95.18 4.05

63.05 25.65 141.0 26.7 139.61 69.13 41.48 89.61 57.09 59.29 75.04 90.79 37.54 81.68 95.18 0.68

Not very helpful.

The length of the function map lists per pixel.

for i in func:

    for j in i:

        print len(j),

    print

8 7 6 6 6 5 5 5 5 5 5 5 5 5 5 5

7 8 8 7 6 6 6 6 6 6 6 5 5 5 5 5

6 8 6 8 8 7 6 5 6 6 6 6 5 6 6 5

6 7 8 6 8 5 7 7 6 6 6 6 6 6 5 5

6 6 8 8 8 8 8 7 7 7 6 5 6 6 6 5

5 6 7 5 8 6 6 8 8 7 7 7 6 6 5 5

5 6 6 7 8 6 8 7 8 6 5 7 7 7 6 5

5 6 5 7 7 8 7 6 8 8 8 6 6 6 5 5

5 6 6 6 7 8 8 8 8 7 7 8 8 6 4 4

5 6 6 6 7 7 6 8 7 8 8 6 7 5 4 3

5 6 6 6 6 7 5 8 7 8 8 6 4 4 3 3

5 5 6 6 5 7 7 6 8 6 6 6 4 4 3 3

5 5 5 6 6 6 7 6 8 7 4 4 4 4 3 3

5 5 6 6 6 6 7 6 6 5 4 4 4 2 2 2

5 5 6 5 6 5 6 5 4 4 3 3 3 2 2 2

5 5 5 5 5 5 5 5 4 3 3 3 3 2 2 2

The Thetamap looks the same way.

I thought to myself, what can I do to this thing? The author said to think about the image as a formula. So I have two formula maps and a pixel map. If I could somehow meld the pixel values with the formulas and squish everything into one nice formula…

Let’s look at what the image would look like if it had not gone through the transformation functions but had only gone through the theta functions.

newmat = []

for U,F in zip(uxm,theta):

    nf = []

    for Ui,Fi in zip(U,F):

        nj = Ui

        for Fct in Fi:

            nj = nj +  Fct(Ui)

        nf.append(nj)

    print [round(u,6) for u in nf]

    newmat.append(nf)

or

newmat = [[sum([Fct(Ui) for Fct in Fi]) + Ui for Ui,Fi in zip(U,F)] for U,F in zip(uxm,theta)]

[2098.2, 6.3, 5.4, 5.4, 5.4, 4.5, 4.5, 1407.0, 114.5, 224.5, 334.5, 444.5, 554.5, 664.5, 774.5, 884.5]

[1867.8, 2098.2, 7.2, 6.3, 5.4, 5.4, 5.4, 1637.4, 133.4, 261.4, 389.4, 444.5, 554.5, 664.5, 774.5, 884.5]

[1637.4, 7.2, 1637.4, 7.2, 7.2, 6.3, 5.4, 1407.0, 133.4, 261.4, 389.4, 517.4, 554.5, 773.4, 901.4, 774.5]

[1637.4, 6.3, 7.2, 1637.4, 7.2, 4.5, 6.3, 1867.8, 133.4, 261.4, 389.4, 517.4, 645.4, 773.4, 774.5, 664.5]

[1637.4, 5.4, 7.2, 7.2, 2098.2, 7.2, 7.2, 1867.8, 152.3, 298.3, 389.4, 444.5, 645.4, 773.4, 901.4, 554.5]

[1407.0, 5.4, 6.3, 4.5, 7.2, 1637.4, 5.4, 2098.2, 171.2, 298.3, 444.3, 590.3, 645.4, 773.4, 774.5, 444.5]

[1407.0, 5.4, 5.4, 6.3, 7.2, 5.4, 2098.2, 1867.8, 171.2, 261.4, 334.5, 590.3, 736.3, 882.3, 901.4, 334.5]

[1407.0, 5.4, 4.5, 6.3, 6.3, 2098.2, 6.3, 1637.4, 171.2, 335.2, 499.2, 517.4, 645.4, 773.4, 774.5, 224.5]

[1407.0, 5.4, 5.4, 5.4, 1867.8, 7.2, 7.2, 2098.2, 171.2, 298.3, 444.3, 663.2, 827.2, 773.4, 647.6, 95.6]

[1407.0, 5.4, 5.4, 1637.4, 6.3, 6.3, 5.4, 2098.2, 152.3, 335.2, 499.2, 517.4, 736.3, 664.5, 647.6, 73.0]

[1407.0, 5.4, 1637.4, 5.4, 5.4, 6.3, 4.5, 2098.2, 152.3, 335.2, 499.2, 517.4, 463.6, 555.6, 520.7, 69.3]

[1407.0, 1407.0, 5.4, 5.4, 4.5, 6.3, 6.3, 1637.4, 171.2, 261.4, 389.4, 517.4, 463.6, 555.6, 520.7, 65.6]

[1407.0, 4.5, 1407.0, 5.4, 5.4, 5.4, 6.3, 1637.4, 171.2, 298.3, 279.6, 371.6, 463.6, 555.6, 520.7, 61.9]

[1407.0, 4.5, 5.4, 1637.4, 5.4, 5.4, 6.3, 1637.4, 133.4, 224.5, 279.6, 371.6, 463.6, 337.8, 393.8, 43.8]

[1407.0, 4.5, 5.4, 4.5, 1637.4, 4.5, 5.4, 1407.0, 95.6, 187.6, 224.7, 298.7, 372.7, 337.8, 393.8, 15.8]

[1407.0, 4.5, 4.5, 4.5, 4.5, 1407.0, 4.5, 1407.0, 95.6, 150.7, 224.7, 298.7, 372.7, 337.8, 393.8, 1.8]

Next I’ll subtract the gray map.

diffmat = []

for G,N in zip(gray,newmat):

    nf = []

    for Gi,Ni in zip(G,N):

        nf.append(N-Gi)

    print [round(u,2) for u in nf]

    diffmat.append(nf) 

or

diffmat = [[Ni-Gi for Gi,Ni in zip(G,N)] for G,N in zip(gray,newmat)]

[1939.82, -87.83, -27.76, 4.51, -14.61, -53.75, 3.63, 1312.89, 44.16, 209.0, 254.32, 299.63, 455.19, 550.71, 700.27, 791.94]

[1671.47, 2061.74, -63.62, -25.07, 0.93, 0.93, -131.75, 1587.51, 49.33, 164.68, 340.98, 408.75, 497.38, 552.25, 693.75, 800.47]

[1500.25, -108.45, 1604.24, -23.58, -45.99, -25.07, -113.82, 1303.89, 70.22, 198.4, 332.12, 448.43, 461.38, 677.73, 773.08, 668.51]

[1532.52, 5.41, -108.45, 1604.24, -61.83, 3.63, -168.51, 1784.99, 105.02, 222.62, 332.26, 446.27, 563.58, 678.01, 674.07, 576.1]

[1530.13, -24.17, 6.3, -108.45, 2082.06, -60.93, -178.37, 1828.01, 91.96, 202.94, 332.9, 386.25, 560.65, 665.36, 800.81, 468.65]

[1363.1, -95.89, 5.41, 3.63, -169.41, 1599.74, -115.3, 2036.15, 111.38, 209.94, 333.9, 488.75, 532.3, 658.89, 675.19, 363.3]

[1370.27, -69.0, -56.45, -30.45, -113.37, 3.95, 1978.63, 1804.36, 81.15, 198.64, 322.94, 525.28, 628.29, 763.32, 796.73, 295.32]

[1341.58, -99.48, -0.87, -112.25, -55.3, 1920.1, -20.68, 1584.55, 112.93, 224.37, 404.51, 432.7, 561.55, 691.33, 699.94, 191.4]

[1333.8, -102.01, -154.06, -0.55, 1815.75, -123.21, -21.75, 2045.5, 108.22, 254.09, 336.39, 552.97, 721.02, 707.26, 533.13, 61.6]

[1357.99, -138.5, -9.74, 1552.77, -34.25, -111.22, -4.49, 2040.16, 87.56, 267.51, 387.56, 432.7, 641.61, 602.88, 546.74, 43.97]

[1299.96, -79.58, 1580.97, -10.32, -34.67, -152.09, -22.25, 2035.38, 116.74, 259.56, 416.11, 428.2, 366.01, 503.01, 418.66, 37.76]

[1297.14, 1349.74, -62.99, -15.95, -57.68, -126.78, -64.34, 1526.9, 106.85, 178.53, 324.11, 390.51, 364.88, 503.46, 418.66, 35.38]

[1290.02, -17.75, 1280.55, -17.8, -131.94, -44.35, -34.53, 1568.52, 79.16, 170.63, 202.26, 289.76, 364.88, 503.91, 418.66, 32.61]

[1285.89, -27.87, -91.58, 1577.24, -133.3, -33.17, -56.96, 1550.19, 89.48, 154.16, 205.63, 280.76, 420.23, 256.13, 298.62, 33.0]

[1338.02, -85.25, -97.02, -4.25, 1463.33, -8.37, -27.55, 1315.42, 46.38, 126.01, 149.66, 207.91, 330.96, 256.13, 298.62, 11.75]

[1343.95, -21.15, -136.5, -22.2, -135.11, 1337.87, -36.98, 1317.39, 38.51, 91.41, 149.66, 207.91, 335.16, 256.13, 298.62, 1.13]

So this map is a representation of one function applied some number of times, all I have to do is divide by the number of functions.

divmat = []

for F,D in zip(func,diffmat):

    nf = []

    for Fi,Di in zip(F,D):

        nf.append(Di/len(Fi))

    print [round(u,2) for u in nf]

    divmat .append(nf)

or

divmat = [[ Di /len( Fi ) for  Fi , Di in zip(F,D)] for F,D in zip(func, diffmat )]

[242.48, -12.55, -4.63, 0.75, -2.44, -10.75, 0.73, 262.58, 8.83, 41.8, 50.86, 59.93, 91.04, 110.14, 140.05, 158.39]

[238.78, 257.72, -7.95, -3.58, 0.15, 0.15, -21.96, 264.58, 8.22, 27.45, 56.83, 81.75, 99.48, 110.45, 138.75, 160.09]

[250.04, -13.56, 267.37, -2.95, -5.75, -3.58, -18.97, 260.78, 11.7, 33.07, 55.35, 74.74, 92.28, 112.96, 128.85, 133.7]

[255.42, 0.77, -13.56, 267.37, -7.73, 0.73, -24.07, 255.0, 17.5, 37.1, 55.38, 74.38, 93.93, 113.0, 134.81, 115.22]

[255.02, -4.03, 0.79, -13.56, 260.26, -7.62, -22.3, 261.14, 13.14, 28.99, 55.48, 77.25, 93.44, 110.89, 133.47, 93.73]

[272.62, -15.98, 0.77, 0.73, -21.18, 266.62, -19.22, 254.52, 13.92, 29.99, 47.7, 69.82, 88.72, 109.81, 135.04, 72.66]

[274.05, -11.5, -9.41, -4.35, -14.17, 0.66, 247.33, 257.77, 10.14, 33.11, 64.59, 75.04, 89.76, 109.05, 132.79, 59.06]

[268.32, -16.58, -0.17, -16.04, -7.9, 240.01, -2.95, 264.09, 14.12, 28.05, 50.56, 72.12, 93.59, 115.22, 139.99, 38.28]

[266.76, -17.0, -25.68, -0.09, 259.39, -15.4, -2.72, 255.69, 13.53, 36.3, 48.06, 69.12, 90.13, 117.88, 133.28, 15.4]

[271.6, -23.08, -1.62, 258.8, -4.89, -15.89, -0.75, 255.02, 12.51, 33.44, 48.45, 72.12, 91.66, 120.58, 136.69, 14.66]

[259.99, -13.26, 263.49, -1.72, -5.78, -21.73, -4.45, 254.42, 16.68, 32.45, 52.01, 71.37, 91.5, 125.75, 139.55, 12.59]

[259.43, 269.95, -10.5, -2.66, -11.54, -18.11, -9.19, 254.48, 13.36, 29.75, 54.02, 65.09, 91.22, 125.86, 139.55, 11.79]

[258.0, -3.55, 256.11, -2.97, -21.99, -7.39, -4.93, 261.42, 9.89, 24.38, 50.56, 72.44, 91.22, 125.98, 139.55, 10.87]

[257.18, -5.57, -15.26, 262.87, -22.22, -5.53, -8.14, 258.37, 14.91, 30.83, 51.41, 70.19, 105.06, 128.06, 149.31, 16.5]

[267.6, -17.05, -16.17, -0.85, 243.89, -1.67, -4.59, 263.08, 11.6, 31.5, 49.89, 69.3, 110.32, 128.06, 149.31, 5.88]

[268.79, -4.23, -27.3, -4.44, -27.02, 267.57, -7.4, 263.48, 9.63, 30.47, 49.89, 69.3, 111.72, 128.06, 149.31, 0.56]

There it is: an image really similar to the original that I would have no idea how to turn into a function.

Here is a function to look at this type of IFSmapping.

def fractimg(finalimg,fsm):

    klist = [[j.next() for j in i] for i in fsm.IFSlist]

    for j in klist:

        for k in j:

            x,y = int(k[0] * 120) + 480,int(k[1] * 120) + 480

            if x < 0:

                x = 0

            if y < 0:

                y = 0

            if x > 1439:

                x=1439

            if y > 1439:

                y=1439            

            finalimg[y][x] = 255

    return finalimg

Make a list with input consistent with your functions.

newlist = []

for cy,i in enumerate(uxm):

    for cx,j in enumerate(i):

        newlist.append((float(cx)/len(i),float(cy)/len(uxm)))

An empty uxm.

finalimg = [[0. for i in range(720)] for j in range(720)]

A IFSmapping with the new list.

fsm = IFSmapping([rot1,rot2,rot3,rot4,ref1,ref2,ref3,ref4],newlist)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’testfinalA.png’)

finalimg = fractimg(finalimg,fsm)

imggray(finalimg,’testfinalB.png’)

The author had talked about separating the image into tiles but a fractal isn’t just composed of regular segments. It is the entirety of the image superimposed on parts of itself and not the other way around. To make an image into a single function I’ll have to work with whole images and not tiles.

You know the old saying, “If you can’t do it Waterloo style then do it Santa Fe style.” 

Coming soon Part 3-2.

consider the functions.

def scrunch1(z):

    x,y,Th = z[0],z[1],z[2]

    x = x* .5 + .5

    y = y

    return (x,y,z[2])

def scrunch2(z):

    x,y,Th = z[0],z[1],z[2]

    x = x * .5

    y = y

    return (x,y,z[2])

def scrunch3(z):

    x,y,Th = z[0],z[1],z[2]

    x = x

    y = y * .5 + .5

    return (x,y,z[2])

def scrunch4(z):

    x,y,Th = z[0],z[1],z[2]

    x = x

    y = y * .5

    return (x,y,z[2])

def scrunch5(z):

    x,y,Th = z[0],z[1],z[2]

    x = x * .5

    y = y * .5

    return (x,y,z[2])

def scrunch6(z):

    x,y,Th = z[0],z[1],z[2]

    x = x * .5 + .5

    y = y * .5 + .5

    return (x,y,z[2])

def scrunch7(z):

    x,y,Th = z[0],z[1],z[2]

    x = x * .5 + .5

    y = y * .5

    return (x,y,z[2])

def scrunch8(z):

    x,y,Th = z[0],z[1],z[2]

    x = x * .5

    y = y * .5 + .5

    return (x,y,z[2])

thetavalsadd = [0.3 for i in range(8)]

thetavals = [.5 for i in range(8)]

def Idxy1(x):

    return x*thetavals[0] + thetavalsadd[0]

def Idxy2(x):

    return x*thetavals[1]+ thetavalsadd[1]

def Idxy3(x):

    return x*thetavals[2] +thetavalsadd[2]

def Idxy4(x):

    return x*thetavals[3] +thetavalsadd[3]

def Idxy5(x):

    return x*thetavals[4]+ thetavalsadd[4]

def Idxy6(x):

    return x*thetavals[5] +thetavalsadd[5]

def Idxy7(x):

    return x*thetavals[6]+ thetavalsadd[6]

def Idxy8(x):

    return x*thetavals[7]+thetavalsadd[7]

consider the process. 

fnlist = [scrunch1,scrunch2,scrunch3,scrunch4,

            scrunch5,scrunch6,scrunch7,scrunch8]

Idxlist = [Idxy1,Idxy2,Idxy3,Idxy4,

            Idxy5,Idxy6,Idxy7,Idxy8]

uxmlena = imgtouxm(‘lena.png’)

uxmlena = [[complex(float(di)/255.,float(di)/255.) for di in j] for j in  uxmlena ]

fsm = IFSmapping(fnlist,[(0.,0.,0.),(0.,0.,1.),(0.,1.,1.),

            (0.,1.,0.),(1.,0.,0.),(1.,0.,1.),(1.,1.,1.),(1.,1.,0.)])

for i in range(7):

    func,theta,gray = IFSM3d(uxmlena ,fsm,Idxlist)

    newmat = [[sum([Fct(Ui) for Fct in Fi]) + Ui for Ui,Fi in zip(U,F)] for U,F in zip( uxmlena  ,theta)]

    diffmat = [[Ni-Gi for Gi,Ni in zip(G,N)] for G,N in zip(gray,newmat)]

    divmat = [[ Di /len( Fi ) for  Fi , Di in zip(F,D)] for F,D in zip(func, diffmat )]

    testreal = [[int(float(di.real)*255.) for di in j] for j in  divmat ]

   testimag = [[int(float(di.imag)*255.) for di in j] for j in divmat ]

    imggray(  testreal  ,’testlena’ + str(i) +’.png’)

    imggray(  testimag  ,’testlenaI’ + str(i) +’.png’)

uxmlena  = divmat 

Part 2.

This article is about “A Guide to ‘Fractal-Based’ Image Compression and Function Approximation” found at http://links.uwaterloo.ca/papers/waterloo/vr95.pdf It is meant as a study aid to be read in parallel with the article. Python stuff is in bold.

I am going to talk about the library HGF.py which can be found here http://paste.pocoo.org/show/548119/ 

First import HGF

from HGF import *

In part one we defined the IFS

MyIFS = IFS(Fn,.5)

and the IFSmapping

Mymap = IFSmapping([Fn1,Fn2],[.5])

Part one concluded with the idea that a picture is more than a collection of geometric shapes but also of grayscale.

First I’m going to create a dummy graymap.

dummdata = [2-(math.sin(i/100.)) for i in range(300)]

Here is range(len(dummdata)) Vs. dummdata

Consider the following functions.

def f1(x):

    return .6*x

def f2(x):

    return .6*x+.4

def a1(y):

    return y*.5 + .5

def a2(y):

    return y*.75

Make an IFSmapping

f= IFSmapping([f1,f2],[0.,1.])

It is here at the bottom of page nine that the author introduces us to the Iterated Function System with Gray-Level Maps (ISFM). It is at this time that I would like to pause and make the author a Pan-Galactic Gargle Blaster. I often program my way through articles or book chapters that are math heavy. Very rarely does one class or function just meld into the next. It is a lot like having your brain smashed out by a slice of lemon wrapped round a large gold brick.

The ISFM is a function that takes three lists and returns three lists. Here is how it works: it takes a graymap and an IFSmapping and a list of Theta functions. The list of Theta functions must be as long or longer than the function list. It returns a function list, a theta function list and a new graymap.

The graymap is indexed between zero and one, passed through function one of the IFSmapping then the gray values are passed through theta function one and the results are put in a new list forming a layer. The layers are then compared. If layer one has a number, that number is put in the new graymap. The function from the IFSmapping is put in the function list and the theta function is added to the Theta list. If the second layer has a number in the same spot that number is added to the graymap. A new Lambda function is made combining the function from the function list and function two then a new Lambda function is made for the theta functions as well. The Lambda functions will cause a recursion error if the IFSmapping has more than seven functions. In the two dimensional IFSM’s I don’t use Lambda functions and just stack the functions in the list so you can use as many functions in the IFSmapping as you want.

Lets look at an IFSM

func,theta,gray = IFSM(dummdata,f,[a1,a2])

Here is range(len(gray)) Vs. gray

For a second pass I’ll just put the graymap back through.

func,theta,gray = IFSM(gray,f,[a1,a2])

Here is range(len(gray)) Vs. gray

One hundred times.

for i in range(100):

    func,theta,gray = IFSM(gray,newmap,[a1,a2])

Here is range(len(gray)) Vs. gray

And there you have the attractor of the IFSM above.

Next let’s consider the functions from page eleven.

def f1(x):

    return x/3.

def f2(x):

     return x/3.+1./3.

def f3(x):

     return x/3.+2./3.

def a1(y):

    return y*.5

def a2(y):

    return .5

def a3(y):

    return y*.5 + .5

Make an IFSmapping.

fsm = IFSmapping([f1,f2,f3],[0.,1.])

Run the process.

func,theta,gray = IFSM(dummdata,fsm,[a1,a2,a3])

for i in range(100):

    func,theta,gray = HGF.IFSM(gray,fsm,[a1,a2,a3])

Here is range(len(gray)) Vs. gray (The Devil’s Staircase)

Consider the function.

def F5(x):

    return math.sqrt(x)

IFS map functions.

def F1x(x):

    return x/2.

def F2x(x):

    return x/2.+.5

Dummy theta function.

def Id(x):

    return x

Here’s our graymap

uxm =[F5(float(i)/1000.) for i in range(1000)]

Here is range(len(uxm)) Vs. uxm

Our mapping.

fsm = IFSmapping([F1x,F2x],[0.,1.])

func,theta,gray = IFSM(uxm,fsm,[Id,Id])

Here is range(len(gray)) Vs. gray almost figure 8(a).

 

Here is gray Vs. [func[i](j) for i,j in zip(range(len(gray)),uxm)]) should be figure 8(b)

Now we’ll add the Theta functions that should approximate the sqrt function.

def a1(y):

    return y/math.sqrt(2)

def a2(y):

    return .35216*y + .62717

Many iterations.

for i in range(1000):

    func,theta,gray = HGF.IFSM(gray,fsm,[a1,a2])

Here is range(len(gray)) Vs. gray

Let’s do that interested thing on page 15

def InterestFN(x):

    return math.sin(math.pi*x)

fsm = IFSmapping([F1x,F2x],[0.,1.])

uxm =[InterestFN(float(i)/1000.) for i in range(1000)]

Here is range(len(uxm)) Vs. uxm

func,theta,gray = IFSM(uxm,fsm,[Id,Id])

Here is range(len(gray)) Vs. gray

Finally here is gray Vs. [func[i](j) for i,j in zip(range(len(gray)),uxm)])

It is at this point that I made a horrible detour. The author said that the translation to a two dimensional graymap was straightforward and that there were eight IFS maps so…

Coming Soon:

Part 3 - If expressing an image as a single, self-repeating function is a virtual impossibility, then its collage must be a finite improbability.

Consider the functions.

def rotation(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th) - y * math.sin(Th)

    y_prime = x* math.sin(Th) + y * math.cos(Th)

    return (x_prime*0.23+.5,y_prime*0.23 + .5,z[2])

def reflection(z):

    x,y,Th = z[0],z[1],z[2]

    Th = Th.real*360.

    x_prime = x* math.cos(Th)*2 + y * math.sin(Th)*2

    y_prime = x* math.sin(Th)*2 - y * math.cos(Th)*2

    return (x_prime*.23+.5, y_prime*.23 + .5, z[2])

def Id1(x):

    return x*.3 + .5

def Id2(x):

    return x*.3 + .5

Consider the graymap.

import image

lena= Image.open(file(‘lena.jpg’,’rb’))

lena =  lena .convert(‘L’)

imgdata =  lena.getdata()

uxm = zip(*[iter(imgdata)]* lena .size[0])

uxm =[[complex(float(di)/255.,float(di)/255.) for di in j] for j in uxm]

Consider the IFSM.

fsm = IFSmapping([rotation,reflection],[(0.,0.,0.),(0.,0.,1.)])

func,theta,gray = IFSM3d(uxm,fsm,[Id1,Id2])

Part 1.

This article is about “A Guide to ‘Fractal-Based’ Image Compression and Function Approximation” found at http://links.uwaterloo.ca/papers/waterloo/vr95.pdf It is meant as a study aid to be read in parallel with the article. Python stuff is in bold.

I had always wanted to try my hand at fractal compression. I tried to read a PDF once but got lost, so when I saw this article, I thought I might give it a try again. 

Oh yea! I’m going to read this article and then sit down and fractal compress some images. A little history on the first page…I’m down…some math on the second page…Euclidean, heard that word before…one of the set symbol thingies, about the bottom of page two I’m thinking…wow, math does things to numbers.

Page three, Cantor, you know he’s just this guy…Somewhere on page four when the author started talking about contracting my spleen, I knew that these guys were serious.

I realized that I could not just read about “fractal-based” anything and that I had to encode it to something that I could understand like Python. 

The following sometimes kludge code (sometimes on purpose) is my struggling attempt at understanding what fractal compression is.

First, I need some tools.

import math, itertools

I am going to talk about the library HGF.py which can be found here http://paste.pocoo.org/show/548119/ in the first and second parts and about doing fun things with it in the third. I’ll import it for now.

from HGF import *

The first thing the author does is define an Iterated Function System as some function that starts with an initial value and puts that value back in the function. Python speaks iteration with +, =, etc. It even has a native iter class. I just wrote it as an iterator because it says Iterated Function System. Its main property is the .next() function that gives you the next number. The IFS in HGF.py works like this:

Define a function,

def Fn(x):

    return x**2

Create an IFS with the function and an initial start value,

MyIFS = IFS(Fn,.5)

The function.

print MyIFS.Fn

<function Fn at 0x02850030>

Initial start value.

print MyIFS.Io

0.5

Iterations.

print  MyIFS.next()

0.25

print  MyIFS.next()

0.0625

print  MyIFS.next()

0.00390625

Define a function,

def Fn(pt):

    return (pt[0]**2,pt[1]/2)

Create an IFS with the function and an initial start value,

MyIFS = IFS(Fn,(.5,.5))

print MyIFS.Fn

<function Fn at 0x02850070>

print MyIFS.Io

(0.5, 0.5)

print  MyIFS.next()

(0.25, 0.25)

print  MyIFS.next()

(0.0625, 0.125)

print  MyIFS.next()

(0.00390625, 0.0625)

Now that we have an IFS let’s do the exercise on page two.

def F1pg_2(x):

    return 4*x*(1.-x)

Now I’m going to step through a list from 0 to .9 by .1,

Create an IFS with each step and print out 10 iterations from each IFS,

for i in [j/10. for j in range(10)]:

    a = IFS(F1pg_2,i)

    for i in range(10):

        print a.next(),

    print

To best investigate the behavior of Xn for every Xo, I should probably make list of a thousand elements or so and graph them. 

Next we are asked to consider the two functions.

def F1(x):

    return x/3.

def F2(x):

    return (x/3.) + (2./3.)

Now define the following set valued IFS mapping f.

f = IFSmapping([F1,F2],[0.,1.])

Here are the parts.

The return map of function list over the initial input list.

print f.retmap

[[0.0, 0.3333333333333333], [0.6666666666666666, 1.0]]

The union of the return map.

print f.unionv

[0.0, 1.0, 0.6666666666666666, 0.3333333333333333]

The IFS list is IFS’s for the return map.

print f.IFSlist

[[<HGF.IFS object at 0x0284DE70>, <HGF.IFS object at 0x0284DDB0>], [<HGF.IFS object at 0x0284DDF0>, <HGF.IFS object at 0x0284DE30>]]

A function list and initial input list.

print f.Fnlist

[<function F1 at 0x02850CF0>, <function F2 at 0x02850D30>]

print f.Iolist

[0.0, 1.0]

Next I created an iterator for the map, it just takes unions of the .next() function of each IFS in the IFSlist and the union of the previous results. The problem is unions of long lists take forever.

f_iter= mapIterator(f)

print  f_iter .next()

[0.0, 1.0, 0.7777777777777777, 0.8888888888888888, 0.2222222222222222, 0.3333333333333333, 0.1111111111111111, 0.6666666666666666]

print  f_iter .next()

[0.0, 1.0, 0.7777777777777777, 0.7037037037037037, 0.037037037037037035, 0.2222222222222222, 0.9629629629629629, 0.8888888888888888, 0.3333333333333333, 0.2962962962962963, 0.1111111111111111, 0.6666666666666666]

It is quicker to just ask each IFS in the IFSlist for its .next() function.

print [[j.next() for j in i] for i in f.IFSlist]

[[0.0, 0.037037037037037035], [0.9629629629629629, 1.0]]

Now would be a good time to read up on George Cantor.

We are next asked to place a third function in the IFSmapping.

def F3(x):

    return (x/3.) + (1./3.)

f = IFSmapping([F1,F2,F3],[0.,1.])

fI= mapIterator(f)

print fI.next()

[0.0, 1.0, 0.7777777777777777, 0.1111111111111111, 0.2222222222222222, 0.5555555555555556, 0.8888888888888888, 0.6666666666666666, 0.4444444444444444, 0.3333333333333333]

print fI.next()

[0.0, 1.0, 0.8518518518518519, 0.7037037037037037, 0.037037037037037035, 0.5555555555555556, 0.4444444444444444, 0.2962962962962963, 0.9629629629629629, 0.8148148148148148, 0.6666666666666666, 0.5185185185185185, 0.2222222222222222, 0.48148148148148145, 0.7777777777777777, 0.6296296296296295, 0.1111111111111111, 0.8888888888888888, 0.1851851851851852, 0.14814814814814814, 0.37037037037037035, 0.3333333333333333]

The attractor is a set of three numbers.

Here is Serpinski’s gasket.

def F1xy(pt):

    x,y =  pt [0], pt [1]

    return (x/2.,y/2.)

def F2xy(pt):

    x,y =  pt [0], pt [1]

    return (x/2.+.5,y/2.)

def F3xy(pt):

    x,y =  pt[0], pt[1]

    return (x/2. + .25,y/2. + math.sqrt(3.)/4.)

sg =  IFSmapping([F1xy,F2xy,F3xy],[(.5,.5)])

sgi = mapIterator(sg)

print sgi.next()

[(0.125, 0.125), (0.5, 0.6830127018922193), (0.5, 0.774519052838329), (0.875, 0.125), (0.375, 0.5580127018922193), (0.625, 0.125), (0.625, 0.5580127018922193), (0.75, 0.34150635094610965), (0.25, 0.25), (0.375, 0.125), (0.75, 0.25), (0.25, 0.34150635094610965)]

I fiddled with the fern a little, but I could feel that something crunchy was on the horizon.

And, boy, I was not disappointed. The author gets right to the point. The first time I read the page I kind of glossed over it thinking about those fancy-pants Waterloo math boys and their collage girls. After about the third reading I finally started to get the gist of it.

The author is discussing a corollary of Banach’s Contracting Mapping Theorem called the “Collage Theorem”. Well, I have to say, the third arm suits you, Banach.

There is some set S, presumably numbers, that we want to be expressed as an IFSmapping. If we were to take that IFSmapping and run it through a mapIterator it is the .next() function that returns the “collage”. Then there is this thing called the “collage distance”, if the “collage” is equal to S like above, then the “collage distance” is zero—easy enough. The problem I’m having is that the “collage” is essentially an infinitely long list; where do I stop to calculate the “Collage Distance”? Problem or not, I tried to calculate out the IFSmapping later on, but it became impossibly complex for me.

Right afterward, the author urges us to go back to the Spleenwart. He says something that has kept me plugging away at this thing for weeks. He says it is more natural to think of picture as defining a function, so every time I get distracted and find myself just processing the image, I step back and think about the image as a function.

The last thing in this part is called the “chaos game”. I call it the markov_game. At first I thought, “How goofy,” but now I’m thinking that one reduces the image to a “collage”, and then one scan line is some sort of Invariant measure of the IFSmapping, but I wouldn’t know what to do with that.

Here’s the markov_game.

print markov_game(sg)

[(0.5, 0.6830127018922193), (0.25, 0.34150635094610965), (0.125, 0.17075317547305482), (0.3125, 0.5183892896287468), (0.15625, 0.2591946448143734), (0.328125, 0.562610024299406), (0.1640625, 0.281305012149703), (0.08203125, 0.1406525060748515), (0.041015625, 0.07032625303742575), (0.5205078125, 0.035163126518712874), (0.76025390625, 0.017581563259356437), (0.880126953125, 0.008790781629678219), (0.6900634765625, 0.4374080927070584), (0.84503173828125, 0.2187040463535292), (0.922515869140625, 0.1093520231767646), (0.9612579345703125, 0.0546760115883823), (0.9806289672851562, 0.02733800579419115), (0.7403144836425781, 0.44668170478931485), (0.37015724182128906, 0.22334085239465742), (0.6850786209106445, 0.11167042619732871), (0.5925393104553223, 0.48884791499088365), (0.7962696552276611, 0.24442395749544182), (0.6481348276138306, 0.5552246806399402), (0.3240674138069153, 0.2776123403199701), (0.6620337069034576, 0.13880617015998506), (0.5810168534517288, 0.5024157869722118), (0.2905084267258644, 0.2512078934861059), (0.3952542133629322, 0.5586166486352723), (0.4476271066814661, 0.7123210262098554), (0.47381355334073305, 0.789173214997147), (0.4869067766703665, 0.8275993093907927), (0.7434533883351833, 0.41379965469539637), (0.37172669416759163, 0.20689982734769818), (0.6858633470837958, 0.10344991367384909), (0.8429316735418979, 0.051724956836924546), (0.671465836770949, 0.4588751803106816), (0.5857329183854745, 0.6624502920475601), (0.5428664591927372, 0.7642378479159994), (0.2714332295963686, 0.3821189239579997), (0.1357166147981843, 0.19105946197899984), (0.31785830739909215, 0.5285424328817192), (0.6589291536995461, 0.2642712164408596), (0.579464576849773, 0.5651483101126491), (0.5397322884248865, 0.7155868569485438), (0.5198661442124433, 0.7908061303664913), (0.5099330721062216, 0.8284157670754649), (0.5049665360531108, 0.8472205854299517), (0.2524832680265554, 0.42361029271497586), (0.6262416340132777, 0.21180514635748793), (0.8131208170066389, 0.10590257317874396), (0.4065604085033194, 0.05295128658937198), (0.4532802042516597, 0.4594883451869053), (0.7266401021258299, 0.22974417259345264), (0.6133200510629149, 0.5478847881889456), (0.5566600255314574, 0.7069550959866922), (0.2783300127657287, 0.3534775479933461)]

Coming soon!

Part 2 - Knots in the Devil’s staircase.

Part 3 - If expressing an image as a single, self-repeating function is a virtual impossibility, then its collage must be a finite improbability.