2
\$\begingroup\$

I'm attempting to speed up my genetic algorithm that modifies images. After searching, I've found that my fitness function is the bottleneck, taking sometimes up to 11 seconds to complete.

The fitness function accepts two images and returns a float representing the total difference between the images' corresponding pixels, measured as distance in Cartesian RGB space.

To test, I used some large images of the same size (1254 x 834). What can I do to speed this process up?

def fitness(original, new):
    fitness = 0

    for x in range(0, width):
        for y in range(0, height):
            r1, g1, b1 = original.getpixel((x, y))
            r2, g2, b2 = new.getpixel((x, y))

            deltaRed = abs(r1 - r2)
            deltaGreen = abs(g1 - g2)
            deltaBlue = abs(b1 - b2)

            pixelFitness = pixelFitness = math.sqrt(deltaRed ** 2 + deltaGreen ** 2 + deltaBlue ** 2)

            fitness += pixelFitness

    return fitness
\$\endgroup\$
  • 1
    \$\begingroup\$ getpixel((x, y)) is very likely to be the trouble, as it is very slow operation for every language(and API) I know. I dont know much of python but finding alternative should be easy task for you. \$\endgroup\$ – wondra Jan 29 '15 at 22:12
  • \$\begingroup\$ The three calls to abs() are pretty pointless, given that the only thing we do with the results is to square them. \$\endgroup\$ – Toby Speight Dec 5 '18 at 16:18
  • \$\begingroup\$ I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Please check that I haven't misrepresented your code, and correct it if I have. \$\endgroup\$ – Toby Speight Dec 5 '18 at 17:03
2
\$\begingroup\$

Thanks to @wondra for the help. I rewrote the function without the getpixel and just loaded the pixels using the image.load() method. This caused the execution time to reduce down to 3.09 seconds.

Rewritten function:

def fitness_new(new):
    fitness = 0

    new_data = new.load()

    for x in range(0, width):
        for y in range(0, height):
            r1, g1, b1 = optimal_data[x, y]
            r2, g2, b2 = new_data[x, y]

            deltaRed = abs(r1 - r2)
            deltaGreen = abs(g1 - g2)
            deltaBlue = abs(b1 - b2)

            pixelFitness = pixelFitness = math.sqrt(deltaRed ** 2 + deltaGreen ** 2 + deltaBlue ** 2)

            fitness += pixelFitness

    return fitness

optimal_data is preloaded as a global variable instead of being passed as an argument, because it is accessed elsewhere. I know this is probably not the most ideal method.

\$\endgroup\$
1
\$\begingroup\$

To speed this up further, you should use the numpy interface of PIL (if you are not yet using PIL, you should, for this reason):

from PIL import Image
import numpy as np

# `int` important because otherwise it might wrap around when subtracting
optimal_data = np.asarray(Image.open("optimal.png"), dtype=int) 
new = np.random.randint(0, 256, optimal_data.shape)

def fitness(optimal_data, new):
    return np.sqrt(((optimal_data - new)**2).sum(axis=-1)).sum()

This takes only 258 ms ± 2.21 ms for a 2424 x 2424 pixel image on my machine, while the function by @TimCPogue takes 9.93 s ± 465 ms with the same images.

Note that the array has the shape (width, height, channels), where channels is usually 4 (red, green, blue, alpha), not 3 like your code assumes. If you want to disregard differences in alpha, either set the alpha channel of the new image to the one of the optimal data (new[:,:,-1] = optimal_data[:,:,-1]), or slice in the fitness (optimal_data[...,:-1] - new[...,:-1]).

For some more readability and the possibility to use a different norm in the future (albeit at the cost of about 30% speed), you could make the norm to use a parameter and use np.linalg.norm, as suggested in the comments by @GarethReese:

def fitness(optimal_data, new, norm=np.linalg.norm):
    return norm(optimal_data - new, axis=-1).sum()
\$\endgroup\$
  • \$\begingroup\$ Consider using numpy.linalg.norm instead of writing your own 2-norm. \$\endgroup\$ – Gareth Rees Dec 5 '18 at 14:41
  • \$\begingroup\$ @GarethRees: While it does make it more readable, it is about 30% slower. Even after making norm = np.linalg.norm a local variable. \$\endgroup\$ – Graipher Dec 5 '18 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.