Image similarity measure

Question

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

Answer 1

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.

Answer 2

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()