Pages

Friday, May 24, 2019

Do these numbers scare you as well?

The gif in question
Recently while browsing math related Wikipedia pages I came across a very interesting gif. The image was on the Wikipedia page for Pascal's Triangle and at first look it seemed completely out of place. I thought it must have been some sort of last minute edit to sneak in a spooky gif to an otherwise technical Wikipedia page.

My first thought was that the gif is some sort of creepy mutating dome of retro video game sprites. Each frame looks eerily familiar and I felt like I've seen this all before.

Attempting to learn more about the image proved to be an unfruitful endeavor. Reading the rest of the article and scanning the profile of the submitter yielded nothing. The article's edits page contained some discussion from the editors in which they inquired how the gif got there but nothing else.

Not only did the image seem out of place but it came alongside a very technical description that took me a while to wrap my head around. I'll include the description below along with a few images to try and show what it's trying to describe.

Each frame represents a row in Pascal's triangle. Each column of pixels is a number in binary with the least significant bit at the bottom. Light pixels represent ones and the dark pixels are zeroes.

Pascals Triangle

Binary representation of row 5
Frame 5 of the gif

I hope the images above speak to you but if it isn't doing anything for you then the entirety of this article can be simplified to something along the lines of "Math used to make interesting images that look similar to retro video game sprites".

Once I had an idea as to what I was looking at, I set out to recreate the image in Python. I'll go over some of the more important parts of the code here. A link to the complete repo with instructions for getting it running yourself can be found on my Github.

We start by generating Pascal's Triangle. I got a lot of help from stack overflow here to get started but modified the code to produce binary numbers.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def make_triangle(n_rows):
    """Return pascals triangle in binary.

    Keyword arguments:
    n_rows -- the number of rows in the triangle
    """
    # Function to add binary numbers
    def bin_add(*args): return bin(sum(int(x, 2) for x in args))[2:]

    results = []
    for _ in range(n_rows):
        row = [bin(1)]  # Append a binary 1 to the start of a row
        if results:  # If there are existing results (row > 1)
            last_row = results[-1]
            # The following is just a fancy way to say "For each result in the last row add it with its neighbor"
            # Zip functions collects the previous row with itself and a version indexed one element ahead
            # The bin_add(*pair) unpacks the pair and calls the bin_add function with the results
            row.extend([bin_add(*pair) for pair in zip(last_row, last_row[1:])])
            row.append(bin(1))  # Append a binary 1 to the end of a row
        results.append(row)
    return results

Once we have Pascal's triangle generated we can take a row of it and use it to generate a frame. This was one of those problems where retrospectively I could have saved a lot of time if I'd spent more time planning. Instead I just jumped right into it and realistically choose the wrong data types to represent some of the elements.

If I had to redo it all from scratch I'd probably use a NumPy array to represent the screen. I believe some of the functionality in NumPy would have made it easier to deal with the cases where the row of Pascal's triangle was either very short or very long (the "if" statements on rows 12 and 24). Regardless implementing it all with just str and list makes me appreciate SciPy libraries even more.

 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
def gen_frame(row, filename, frame_dim, interpol):
    """Return an image for a given a row of pascal triangle."""
    frame = []

    # For each element in a row (represented as binary_strs) unpack it into a list of single 0's and 1's
    for binary_str in row:
        binary_str = ''.join(str(i) for i in binary_str if i.isdigit())
        binary_list = list(binary_str.zfill(SIZE[0]))
        binary_list = [int(i) for i in binary_list]

        # If the binary_list is longer then the output dimensions, trim off the LSBs
        if len(binary_list) > SIZE[0]:
            binary_list = binary_list[:SIZE[0]]

        # Append the binary_list of to the frame
        frame.extend(binary_list)

    # If the binary_list doesn't fill the frame than fill the blank space with 0's
    l_append = [0]*(floor((SIZE[0] - len(row))/2))*SIZE[1]
    r_append = [0]*(ceil((SIZE[0] - len(row))/2))*SIZE[1]
    canvas = l_append+frame+r_append

    # If the binary_list exceeds the size of the frame than trim off the edges
    if len(canvas) > (SIZE[0]*SIZE[1]):
        offset = (((len(frame))-(SIZE[0])*SIZE[1]))/2

        # Make sure the offset doesn't cause screen tearing
        if offset % SIZE[0] != 0:
            offset += SIZE[0]/2

        canvas = canvas[int(offset):]

    # Set image interpolation behaviour based on user input
    interpol = Image.LANCZOS if interpol else Image.NEAREST

    # Pack the frame into a byte and generate an image with it
    data = pack('B'*len(canvas), *[pixel*255 for pixel in canvas])
    img = Image.frombuffer('L', SIZE, data)
    img = img.rotate(-90)
    img = img.resize(frame_dim, interpol)
    img.save(filename)

Running the code above for x number of rows yields x images in a your working folder. The next function thankfully provides a context manager and makes a temp folder to work in. This makes it easier to keep track of the images we've generated and allows us to stitch them together into a gif easier.

 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
def gen_gif(n_rows, frame_rate, frame_dim, interpol):
    """Generate a gif with n_rows number of frames and with frame timing of f_time.

    Keyword arguments:
    n_rows -- the number of rows in pascals triangle
    frame_rate -- the frame rate to generate the gif with
    frame_dim -- the dimensions to resize the frame to
    interpol -- flag to interpolate the image when upscaleing to frame_dim resolution
    """
    triangle = make_triangle(n_rows)  # Generate pascals triangle of n_rows

    # Make a temp folder and send all outputs to it
    temp_path = os.path.join(os.getcwd(), r'temp')
    if os.path.exists(temp_path):
        shutil.rmtree(temp_path)
        os.makedirs(temp_path)
    else:
        os.makedirs(temp_path)
    os.chdir(temp_path)

    # For each row in pascals triangle generate a frame based off it
    for idx, row in enumerate(triangle):
        gen_frame(row, "frame_{0}.png".format(idx), frame_dim, interpol)

    # Generate output gif given the files generated above
    with get_writer('pascals_triangle_{}.gif'.format(n_rows), mode='I', duration=frame_rate) as writer:
        filenames = [file for file in os.listdir() if file.endswith('.png')]

        # Sort files by numbers found in string containing numbers (ex. frame_6.png)
        def sortby(x):
            return int(search(r'\d+', x).group())

        filenames.sort(key=sortby)
        for filename in filenames:
            image = imread(filename)
            writer.append_data(image)

Another interesting issue I ran into was sorting the images in the temp folder. The images all follow the pattern "frame_x.png", where we want to sort by x but the png extension is required. If we scan the directory and use the sort method on our list with default arguments our elements are sorted as strings. This leaves us with results looking like:

1
['frame_0.png', 'frame_1.png', 'frame_10.png', 'frame_100.png', 'frame_101.png', 'frame_102.png', 'frame_103.png', 'frame_104.png', 'frame_105.png']

The sorting we see above obviously isn't what we want. To sort properly we can pass our own custom sortby function into the lists sort method. You can see our function on line 23 in the snippit above. This function uses regular expressions to scrape all of the ints from the input file title. The ints returned by the function are what is used by the sort method (ex. frame_10.png --> 10).

Everything gets wrapped together by the imageio library. We throw our images and some metadata at its get_writer class and then save it with our filename. Below is my best attempts to recreate the original gifs, aside from the noticeable difference in colour its good enough for me.

My best attempt at recreation
TL:DR - Made gifs using python. Check out full code on the Github repo