Need to increase speed of image creation

Question

I'm trying to create an image with every possible color. It would start with a seed pixel and then place randomly-generated RGB pixels around it. Future placements would be based on whichever open spot had the average of the pixels surrounding it closest to the new color to be placed.

from PIL import Image
import numpy as np
from random import randint
import sys
import random
import itertools

sys.setcheckinterval(10000)

def moddistance3(x1,y1,z1,x2,y2,z2):  #get relative distance between two 3D points
    x = abs(x1 - x2)
    y = abs(y1 - y2)
    z = abs(z1 - z2)
    return (x + y + z)

def genColor(unused): #generate random color (not used anymore)
    test = 0
    while test == 0:
        red = randint(0,255)
        green = randint(0,255)
        blue = randint(0,255)
        if unused[red,green,blue] == 1:
            test = 1
    return (red,green,blue)

def surroundAvg(points,unfilled):
    surrounding = {}
    count = len(points)
    for inc in xrange(count):
        neighbors = filledNeighbors(points[inc][0],points[inc][1],unfilled)
        nearcount = len(neighbors)
        pixred = 0
        pixgreen = 0
        pixblue = 0
        for num in xrange(nearcount):
            (temp_red,temp_green,temp_blue) = pixels[neighbors[num][0],neighbors[num][1]]
            pixred = pixred + temp_red
            pixgreen = pixgreen + temp_green
            pixblue = pixblue + temp_blue
        pixred = pixred / nearcount
        pixgreen = pixgreen / nearcount
        pixblue = pixblue / nearcount
        surrounding[(points[inc][0],points[inc][1])] = (pixred,pixgreen,pixblue)
    return surrounding

def genPoint(perim,unfilled,averages,red,green,blue):
    num_test = len(perim)
    test = 0
    least_diff = 9999
    nearby = []
    for point in xrange(num_test):
        i = perim[point][0]
        j = perim[point][1]
        pixred = averages[(i,j)][0]
        pixgreen = averages[(i,j)][1]
        pixblue = averages[(i,j)][2]
        diff = abs(red - pixred) + abs(green - pixgreen) + abs(blue - pixblue)
        if diff < least_diff or test == 0:
            least_diff = diff
            newx = i
            newy = j
            test = 1
    return newx,newy

def cubegen():  #create the cube of colors with each color having its own number
    cube = np.zeros(16777216,dtype=np.object)
    num = 0
    for red in xrange(0,256):
        for green in xrange(0,256):
            for blue in xrange(0,256):
                cube[num] = [red,green,blue]
                num += 1
    return cube

def getNeighbors(x,y,unfilled):
    Prod = itertools.product
    toremove = []
    neighbors = list(Prod(range(x-1,x+2),range(y-1,y+2)))
    for num in xrange(len(neighbors)):
        i,j = neighbors[num]
        if j > 4095 or i > 4095 or unfilled[(i,j)] == 0 or j < 0 or i < 0:
            toremove.append((i,j))
    map(neighbors.remove,toremove)
    return neighbors

def filledNeighbors(x,y,unfilled):
    Prod = itertools.product
    toremove = []
    neighbors = list(Prod(range(x-1,x+2),range(y-1,y+2)))
    #neighbors = filter(lambda i,j: j < 4096 and i < 4096 and unfilled[i,j] == 0 and j > -1 and i > -1,allneighbors)
    for num in xrange(len(neighbors)):
        i,j = neighbors[num]
        if j > 4095 or i > 4095 or unfilled[(i,j)] == 1 or j < 0 or i < 0:
            toremove.append((i,j))
    map(neighbors.remove,toremove)
    return neighbors

img = Image.new('RGB', (4096,4096)) # create a new black image
pixels = img.load() # create the pixel map

colorList = range(16777216)
colorCube = cubegen()
print("Color cube created successfully")
unfilled = {}
for x in xrange(4096):
    for y in xrange(4096):
        unfilled[(x,y)] = 1
startx = 2048
starty = 2048
random.shuffle(colorList)
print("Color list shuffled successfully")
color = colorList[0]
(red,green,blue) = colorCube[color]
pixels[startx,starty] = (red,green,blue)
unfilled[(startx,starty)] = 0
perim_empty = getNeighbors(startx,starty,unfilled)
edge = []
#edge.append((startx,starty))
avg = surroundAvg(perim_empty,unfilled)
print("First point placed successfully.")
#appendEdge = edge.append
#removeEdge = edge.remove
appendPerim = perim_empty.append
removePerim = perim_empty.remove
updateAvg = avg.update


for iteration in xrange(1,16777216):
    temp = {}
    color = colorList[iteration]
    (red,green,blue) = colorCube[color]
    (i,j) = genPoint(perim_empty,unfilled,avg,red,green,blue)
    unfilled[(i,j)] = 0
    pixels[i,j] = (red,green,blue)
    new_neighbors = getNeighbors(i,j,unfilled)
    map(appendPerim,new_neighbors)
    temp = surroundAvg(new_neighbors,unfilled)
    updateAvg(temp)
    removePerim((i,j))
    #appendEdge((i,j))

    #if iteration % 20 == 0:
    #   toremove = []
    #   appendToRemove = toremove.append
    #   for num in xrange(len(edge)):
    #       nearby = getNeighbors(edge[num][0],edge[num][1],unfilled)
    #       if len(nearby) == 0:
    #           appendToRemove(edge[num])
        #for num in xrange(len(toremove)):
        #   edge.remove(toremove[num])
    #   map(removeEdge,toremove)

    if iteration % 500 == 0:
        print("Iteration %d complete" %iteration)
    if iteration == 100000 or iteration == 500000 or iteration ==1000000 or iteration == 5000000 or iteration == 10000000 or iteration == 15000000:
        img.save("Perimeter Averaging -- %d iterations.bmp" %iteration)
img.save("Perimeter Averaging Final.bmp")
img.show()

The problem is that when I try to run this, it takes days to even go through 1,000,000 of the colors, and slows down considerably as it goes. I can't figure out how to make it take less time, and I know there must be a way to do this that doesn't take months. I'm new to code and am teaching myself, so please forgive any obvious fixes I've totally overlooked.

without having looked specifically into your code, have you considered `cython`-izing it or using a JIT compiler like `numba`? — salient, Jun 01 '17 at 22:16
You are right, this could run WAY faster. I'd guess that throwing the massive dictionary around from function to function is probably a pretty big bottleneck. This program eats a ton of memory before it ever gets into the iterative section. There are definitely some areas that you could handle more efficiently. I'll have a go at making a list this evening if I have time. — BHawk, Jun 01 '17 at 22:29
Whenever trying to speed up your code, it's a good idea to profile it to determine where it's spending most of its time...so you know here to spend most of yours optimizing it. See [**_How can you profile a python script?_**](https://stackoverflow.com/questions/582336/how-can-you-profile-a-python-script) That said, often the answer is use a different algorithm altogether and avoid the bottleneck, whatever it is. — martineau, Jun 01 '17 at 22:31
You need to learn your data structures... You are using lists, or numpy arrays, in ways that defeat their strenghts. I think this question belongs in [Code Review](https://codereview.stackexchange.com/), not here. And you are more likely to get actionable help there than here. — Jaime, Jun 01 '17 at 23:03
I tried profiling it using cProfile, and the majority of the time seemed to be being consumed by genPoint, especially since it's called so often. The problem is that I couldn't find a way to change it without increasing the amount of time it took. What data structures would you recommend that would take better advantage of their strengths? — wolf53135, Jun 03 '17 at 22:09
@BHawk, I thought of that, but couldn't think of a way to make it not pass around the dictionary that didn't involve just having it check every point every time, which I thought would be even less efficient. What are your recommendations for using lists to increase the efficiency? — wolf53135, Jun 03 '17 at 22:19

BHawk · Answer 1 · 2017-06-06T21:28:39.953

Okay, I've spent some time looking at this and I've made some changes to speed things up. I really like the idea you're implementing in this program, and the outputs are quite lovely. I would probably have done things a little differently from the start but, as it is, I've left it in the structure that you presented it, with a few tweaks. This by no means represents the fastest or most efficient the code could be, but it was enough to satisfy me of the speed up. Note - There may be some errant print statements in there that I was using to understand what was going on in the code. Hope it helps.

I cleaned up the code to remove anything that wasn't used and to change the way you loop through some objects. These were style changes more than anything else.
I changed your color cube from a numpy array to a tuple, because the np array wasn't necessary. I think the cube generates faster now but I haven't done any testing to confirm that.
It is important to understand that given the way you want the colors to be processed, this algorithm will slow down over time as the number of "perimeter" candidates grows. When I first ran the code, I was getting massive growth in the size of the perimeter list due to coordinates not being properly removed. I couldn't track down why it was happening so I added additional checks into the program to avoid overwriting any pixel that was already written. I also added in some redundant point removal if a point is found that shouldn't be a member of the perimeter list. This has sped things up quite a bit on my system, though the source of the bug still eludes me.
To further combat the problem of processing times that grow in proportion to the perimeter size I introduced a threshold value in genPoint. This allows the function to exit when it is "close enough" to a good location. There is a quality hit in doing this, so you can set the value higher if you want speed or lower if you want a higher quality image. It's a devil's bargain, but the alternative is a program that never completes. When I first ran the script it took my computer about 14 seconds to complete iterations 14000-14500. As it is currently running I'm on iteration 2,330,000 and it's taking about 2-3 seconds per 500 iterations.
I got rid of the unfilled dictionary and instead referenced the image directly from the functions. Not how I would have preferred to do it, but it simplified the code and got rid of the big memory block.
Another, more obvious way to speed this up would be to multi-thread the iterations or the genPoint() function, but I'm not willing to put in the time to do that part of it as it would require a substantial reworking of the code. There would be a lot of thread locks that you'd have to implement in order to make it work, but it would make it faster.

--

from PIL import Image
import sys
import random
import itertools
import datetime as dt


#sys.setcheckinterval(10000)

def surroundAvg(points):
    surrounding = {}
    for inc in points:
        neighbors = filledNeighbors(inc[0],inc[1])
        nearcount = len(neighbors)
        pixred = 0
        pixgreen = 0
        pixblue = 0
        for n in neighbors:
            (temp_red,temp_green,temp_blue) = pixels[n[0],n[1]]
            pixred += temp_red
            pixgreen += temp_green
            pixblue += temp_blue
        pixred = pixred / nearcount
        pixgreen = pixgreen / nearcount
        pixblue = pixblue / nearcount
        surrounding[(inc[0],inc[1])] = (pixred,pixgreen,pixblue)
    return surrounding

def genPoint(perim,averages,red,green,blue):
    test = 0
    least_diff = 9999
    threshold = 35
    for point in perim:
        i = point[0]
        j = point[1]
        if pixels[i,j] == (0,0,0):
            pixred = averages[(i,j)][0]
            pixgreen = averages[(i,j)][1]
            pixblue = averages[(i,j)][2]
            diff = abs(red - pixred) + abs(green - pixgreen) + abs(blue - pixblue)
            if diff < least_diff or test == 0:
                least_diff = diff
                newx = i 
                newy = j 
                test = 1
                if least_diff < threshold:
                    return newx,newy,perim
        else:
            perim.pop(perim.index(point))
    return newx,newy,perim

def cubegen():  #create the cube of colors with each color having its own number
    cube = []
    num = 0
    for red in xrange(0,256):
        for green in xrange(0,256):
            for blue in xrange(0,256):
                cube.append((red,green,blue))
                num += 1
    return tuple(cube)

def getNeighbors(x,y):
    Prod = itertools.product
    toremove = []
    neighbors = list(Prod(range(x-1,x+2),range(y-1,y+2)))
    for num in xrange(len(neighbors)):
        i,j = neighbors[num]
        if j > 4095 or i > 4095 or pixels[i,j] != (0,0,0) or j < 0 or i < 0:
            toremove.append((i,j))
    map(neighbors.remove,toremove)
    return neighbors

def filledNeighbors(x,y):
    Prod = itertools.product
    toremove = []
    neighbors = list(Prod(range(x-1,x+2),range(y-1,y+2)))
    for num in xrange(len(neighbors)):
        i,j = neighbors[num]
        if j > 4095 or i > 4095 or pixels[i,j] == (0,0,0) or j < 0 or i < 0:
            toremove.append((i,j))
    map(neighbors.remove,toremove)
    return neighbors

img = Image.new('RGB', (4096,4096)) # create a new black image
pixels = img.load() # create the pixel map

print("Making list")
colorList = range(16777216)
random.shuffle(colorList)
print("Color list shuffled successfully")

print("Making cube")
colorCube = cubegen()
print("Color cube created successfully")

startx = 2048
starty = 2048
color = colorList[0]

(red,green,blue) = colorCube[color]
#start with a random color
pixels[startx,starty] = (red,green,blue)

#get it's neighboring pixels
perim_empty = getNeighbors(startx,starty)

#calc avg values (original pixel)
avg = surroundAvg(perim_empty)
print("First point placed successfully.")
appendPerim = perim_empty.append
removePerim = perim_empty.remove
updateAvg = avg.update

start = dt.datetime.now()
for iteration in xrange(1,16777216):
    temp = {}
    color = colorList[iteration]
    (red,green,blue) = colorCube[color]
    i,j,perim_empty = genPoint(perim_empty,avg,red,green,blue)
    pixels[i,j] = (red,green,blue)
    new_neighbors = getNeighbors(i,j)
    map(appendPerim,new_neighbors)
    temp = surroundAvg(new_neighbors)
    updateAvg(temp)
    removePerim((i,j))
    for p in perim_empty:
        if p[0] == i and p[1] == j:
            perim_empty.remove(p)

    if iteration % 1000 == 0:
        end = dt.datetime.now()
        print("Iteration %d complete: %f" %(iteration,(end-start).total_seconds()))
        print("Perimeter size: %d"%len(perim_empty))
        print("Averages size: %d"%sys.getsizeof(avg))
        start = dt.datetime.now()
        img.save("%06d.png" % (iteration/1000))

img.save("Perimeter Averaging Final.bmp")
img.show()

Edit: forgot to include my current image (still growing):

Need to increase speed of image creation

1 Answers1