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.