For our final weird Markov Chain experiment we will be working with images. This is the definitely least likely project to result in something interesting. After all, Markove Chains are designed to model and simulate sets of linear data where the next item in the chain is heavily dependent on the items that came before. How are we even going to apply that idea to a 2D image?

I suppose there are a lot of ways you could handle this but what I settled on revolves around the question “What pixels tend to group together?” or more specifically “If I have a 2 x 2 square of pixels and I know what the top left, top right, and lower left pixels are, can I predict what the lower right pixel should be?”

That’s enough to turn an image into a Markov Model. We just loop through every 2 x 2 square in the entire image, use the first three pixels as a key and then keep a count of how often different colors show up for the fourth and final pixel.

We can then use this model to create new images by starting with some randomized corner pixels and then filling in the gap by randomly choosing a pixel based on our model. Adding that one extra pixel creates a new corner with a new gap that we can once again probabilistically paint until we have an entire image that hopefully somewhat reflects the original we based our model on.

What should that model be though? Obviously it needs to be something old enough to be public domain. So how about… this?

The low resolution might catch you by surprise, but it’s an important pre-processing step. There are so many different colors of pixels that trying to build a Markov Model of a full color picture would probably just produce hundreds of thousands of unique keys each with one unique next pixel. For a more meaningful model we need something a little more generic, something that captures general patterns instead of hyper specific patterns. We achieve this by flattening the colors of the original to a limited number of shades of grey.

We can then turn this into a model and use that model to generate new images with some fairly simple code:

from PIL import Image
from random import randint

def getRandomFromProbabilityList(probabilityList):
    total = 0
    for shade, count in probabilityList.items():
        total = total + count
    chosenProbability = randint(0, total -1)
    for shade, count in probabilityList.items():
        if(chosenProbability < count):
            return shade
        chosenProbability = chosenProbability - count

shadeMarkovChain = {}
        
filename = "images\mona_lisa.jpg"
with Image.open(filename) as image: 
    width, height = image.size
    resizeRatio = 64/width
    newWidth = ((int)(width * resizeRatio))
    newHeight = ((int)(height*resizeRatio))
    image = image.resize((newWidth, newHeight))
    image = image.convert('LA')
    image.save("images\output.png")
    
    for x in range(0,newWidth):
        for y in range(0, newHeight):
            oldPixel = image.getpixel((x, y))[0]
            newPixel = oldPixel - oldPixel % 128
            topLeft = -1
            top = -1
            left = -1
            if(x > 0):
                tempPixel = image.getpixel((x-1, y))[0]
                left = tempPixel - tempPixel %128
            if(y > 0):
                tempPixel = image.getpixel((x, y-1))[0]
                top = tempPixel - tempPixel %128
              
            if(x > 0 and y > 0):
                tempPixel = image.getpixel((x-1, y-1))[0]
                topLeft = tempPixel - tempPixel %128
                
            if (topLeft, top, left) not in shadeMarkovChain:
                shadeMarkovChain[(topLeft, top, left)] = {}
            if newPixel not in shadeMarkovChain[(topLeft, top, left)]:
                shadeMarkovChain[(topLeft, top, left)][newPixel] = 1
            else:
                shadeMarkovChain[(topLeft, top, left)][newPixel] += 1
            
            
print(shadeMarkovChain)

print(getRandomFromProbabilityList(shadeMarkovChain[(-1,-1,-1)]))


img = Image.new('LA', (newWidth, newHeight))
for x in range(0,newWidth):
    for y in range(0, newHeight):
        topLeft = -1
        top = -1
        left = -1
        if(x > 0):
            left = img.getpixel((x-1, y))[0]

        if(y > 0):
            top = img.getpixel((x, y-1))[0]
          
        if(x > 0 and y > 0):
            topLeft = img.getpixel((x-1, y-1))[0]

        if(topLeft, top, left) in shadeMarkovChain:
            img.putpixel((x,y),(getRandomFromProbabilityList(shadeMarkovChain[(topLeft, top, left)]), 255))
        else:
            img.putpixel((x,y),(getRandomFromProbabilityList(shadeMarkovChain[(-1, -1, -1)]),255))
img.save("images\markov.png")

The results aren’t exactly that impressive though.

I played around with the program a bit to try and get different results. I pre processed the image less, I pre processed it more, I generated smaller images, I generated larger images, i looked at more neighboring pixels.

Nothing really helped. We wind up with this sort of diagonal storm cloud pattern every time.

Which honestly makes sense. As we mentioned earlier images aren’t really linear. You can’t draw a person just by looking at a few dozen pixels at a time. You need context; you need to know where the entire face is to draw the eyes. You need posture to put the hands in the right place. And while there are certainly generative models that can track this sort of data they are much more complex than the little bit of toy code we have built here.

But I promised you a weird Markov chain and I believe I have delivered.

Last time we learned how to represent musical chords with a Markov Chain as well as how to use them to programmatically write music. Unfortunately the music sounds really really bad because I have no idea what chords are supposed to sound like or what chords are supposed to follow each other.

That’s why this time we’re going to focus on reading files instead of writing them. That way our program can learn from actual musicians what notes and chords should follow each other. Because I’m certainly never going to figure that stuff out.

Of course, my lack of musical knowledge also limits my ability to write code that analyzes existing music but if I can get even close we should see some interesting results. And then all you out in the audience can do me one better by learning enough about real music and mp3 to write something better than the upcoming prototype.

Let’s start by importing some libraries, writing a couple helper functions and setting up a variable to hold our musical markov chain data.

from mido import Message, MidiFile, MidiTrack
from random import randint
       
def getRandomFromProbabilityList(probabilityList):
    total = 0
    for word, count in probabilityList.items():
        total = total + count
    chosenProbability = randint(0, total -1)
    for word, count in probabilityList.items():
        if(chosenProbability < count):
            return word
        chosenProbability = chosenProbability - count
        
def addChordToTrack(track, musicalTuple):
    track.append(Message('note_on', note=musicalTuple[0], velocity=64, time=500))
    for subNote in musicalTuple[1:]:
        track.append(Message('note_on', note=subNote, velocity=64, time=0))
 
markovChain = {}

As you can see we’ve got our classic function for pulling an option out of a list of weighted options as well as a simple function for taking a set of musical notes and adding them to a midi track as a half second long chord.

Next we need a lot of raw music. I found a nice collection of publicly available midis of public domain classical music. I downloaded several from the piano section, put them in a folder named “piano” and then threw their file names into a big list in the code.

inputFiles = ['piano/alice.mid',
                'piano/alkan-op31-1.mid',
                'piano/andre-sonatine.mid',
                'piano/anna-magdalena-20a.mid',
                'piano/bach-invention-01.mid',
                'piano/bach-invention-07.mid',
                'piano/bach-invention-13.mid',
                'piano/bach-invention-14.mid',
                'piano/bluemtns.mid',
                'piano/bwv_462.mid',
                'piano/BWV-117a.mid',
                'piano/bwv-259.mid',
                'piano/bwv347.mid',
                'piano/BWV-511.mid',
                'piano/cpe-bach-rondo.mid',
                'piano/giselle.mid',
                'piano/lanative.mid',
                'piano/lesgraces.mid',
                'piano/Rumores_de_la-caleta.mid',
                'piano/swallows.mid',]

And then we can loop through all the files, use our midi library to loop through all the chords in the piece and build up a one deep markov chain from them.

Getting the chords from a midi file is a little bit more difficult than getting the words from a book. As we saw last time a midi chord is created by using “time = 0” to make several notes play at the same time as the note before them. So to build a cord we loop through “note_on” type events. If the time is 0 we add it to the current chordTemp item. If the time isn’t 0 it must be the start of a new chord so we push the current chord onto our main list of chords, clear it out, add the new note and then start looping again.

And of course, once we have our big list of every chord and the order it happened in we can build a one deep markov chain just the same we did for words.

for inputFile in inputFiles:
 
    mid = MidiFile(inputFile)

    chordList = []
    chordTemp = []

    for msg in mid:
        info = msg.dict()
        if(info['type'] == 'note_on'):
            if(msg.time != 0):
                chordList.append(tuple(sorted(set(chordTemp))))
                chordTemp=[]
            chordTemp.append(msg.note)
                


    for i in range(len(chordList) - 1):
        if chordList[i] not in markovChain:
            markovChain[chordList[i]] = {}
        if chordList[i+1] not in markovChain[chordList[i]]:
            markovChain[chordList[i]][chordList[i+1]] = 1
        else:
            markovChain[chordList[i]][chordList[i+1]] += 1

The last thing we need is a list of starting points for generating new songs. Once again this is a little tricky. A book has thousands upon thousands of senteces each with an easy to find first word. But music? Much harder to pick out the start of a musical phrase within a midi.

So we’ll just take a shortcut and make a list of every chord in our markov chain that links to at least one other chord. And then we’ll grab one at random to be the start of our song.

possibleStartingChords = list(markovChain.keys())
startingChord = possibleStartingChords[randint(0,len(possibleStartingChords)-1)]       

And from there building a new song is easy peasy. Only difference from working with sentences is that our goal here is to produce a song of a certain length instead of just running until we reach a data point with no next possible value. So we loop through 480 chords, using the markov chain whenever we can and choosing a new random note to continue with everytime we hit a dead end.

newMid = MidiFile()
track = MidiTrack()
newMid.tracks.append(track)

track.append(Message('program_change', program=0, time=0))
            
currentChord = startingChord

for x in range(480):
    if(currentChord in markovChain):
        currentChord = getRandomFromProbabilityList(markovChain[currentChord])
    else:
       currentChord = possibleStartingChords[randint(0,len(possibleStartingChords)-1)] 
    addChordToTrack(track, currentChord)

newMid.save('markov_song.mid')

Run it a few times and give the results a listen. What do you think?

Awful isn’t it?

But awful in a way that at times sounds almost like music.

I think the main problem is that several of the chords don’t sound very good. This is probably because our naïve chord collector doesn’t distinguish between different instruments. Nor does it have any way to distinguish between treble and bass cleft chords that happen to be being played at the same time.

This is going to make me sound pretty lazy, but I’m happy leaving this experiment where it is. It’s not a great program for generating music… but as a proof of concept program written by someone who barely understands music it’s pretty good. Or at least, it’s good enough that another programmer who actually understands music could probably take it, improve and make something cool.

So we’ll call this a sort-of success and next time we’ll move on to our final and least likely to succeed experiment: Writing a Markov chain system for painting pictures..