SickSad

Approximating Images With Random Lines

I’ve been experimenting with iteratively generating approximations of images using black lines.

The algorithm works by randomly placing 40 black lines on 40 copies of a blank source image, each of those 40 is then compared to the goal image using SSIM to measure similarity. If any of the 40 are more similar than the source image that image is used as the source for the next iteration of the algorithm. If none of the 40 are more similar then the algorithm repeats with the original source image until a closer similarity is found.

SSIM was chosen as the similarity measure over the traditional PSNR or mean squared error measures because it is a better suited (although not perfect) method for measuring the similarity between two image as perceived by the human eye.

Plotting the change in SSIM over 9000 iterations results in the following fairly predictable graph.

From this graph it can be seen that beyond roughly 3500 iterations little extra structural similarity is obtained.

Comparison with PSNR & MSE

The following two image show the same algorithm but run using means squared error and psnr respectively.

As you’d expected the images are very similar as they are essentially the same metric but scaled differently.

Plotting the mean squared error against iterations produces a similar graph to one for SSIM, but note the inversion of the shape due to mean squared error measuring dissimilarity.

Also notable is how the curve of the graph flattens much quicker (at around 1500) when compared to SSIM.

In an application such as this where the end result is inherently subjective it is difficult to make a strong assertation about the best similarity measure for this purpose. Personally I prefer the results created by SSIM as I feel it captures some of the finer facial features which helps to produce a more recognizable end result.

Code

The code for this project was written in python based mainly on the PIL and pyssim libraries. The following is a version of the code used to generate the above images with a few bits of logging code removed.

The number of iterations is hard coded to 9000 and the number of images in a generation is set at 40. These are fairly arbitrary decisions and can be easily altered in the code for experimentation. Also included in the code are two methods for computing psnr and mean squared error.

draw.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#!/usr/bin/env python

from PIL import Image
from PIL import ImageDraw
from random import randint
import ssim
import os
import math
import numpy as np

def generate_line(max_width, max_height, max_length=50):
  start = (randint(0,max_width),randint(0,max_width))
  length = float(randint(0, max_length))
  angle = math.radians(float(randint(0,360)))
  x = length * math.cos(angle) + start[0]
  y = length * math.sin(angle) + start[1]
  line = [start,(x,y)]
  return line


def mean_squared_error(img1, img2):
    total =0
    size = img1.size
    if img1.size != img2.size:
        raise Exception("size of images must be the same")
    if img1.mode != 'L':
        img1 = img1.convert('L')
    if img2.mode != 'L':
        img2 = img2.convert('L')

    img1 = np.array(img1.getdata())
    img2 = np.array(img2.getdata())

    return np.mean(np.absolute(img1 -img2))/255.0

def psnr(img1,img2):
    mse = mean_squared_error(img1,img2)
    return 10.0*math.log10(1.0/mse)

def main():
  img = Image.open("kitten.png")
  result_img = Image.new("RGB",img.size)

  draw = ImageDraw.Draw(result_img)
  draw.rectangle([(0,0),result_img.size],fill=(255,255,255))
  max_width, max_height = result_img.size

  for i in range(9000):
      best_img = result_img.copy()
      best_score = ssim.compute_ssim(img,result_img)

      for l in range(40):
          temp_img = result_img.copy()
          draw = ImageDraw.Draw(temp_img)
          line = generate_line(max_width, max_height)
          draw.line(line,width=1, fill=(0,0,0))
          score = ssim.compute_ssim(img,temp_img)
          print score
          if score > best_score:
              score = best_score
              best_img = temp_img.copy()
      
      result_img = best_img
      output_name = str(i).zfill(6)+'.png'
      result_img.save(output_name)

  result_img.show()
  img.show()


if __name__ == "__main__":
  main()

Installing Dependencies on Ubuntu

Pyssim can be installed through pip (the python package index). To get pip run:

sudo apt-get install python-pip

To speed things along I recommend installing the following packages before installing pyssim:

sudo apt-get install python-matplotlib python-scipy python-numpy

Finally run the following command to install pyssim via pip:

sudo pip install pyssim