Efficiently calculating sum of squared differences

Question

This is a loop for extracting the RGB values of two images, and calculating the sum of squared differences across all three channels. Running this code directly in my main.py takes 0.07 sec. The speed gets reduced to 1sec if I run it in this .pyx file instead. I have read about cdef the functions, but I have had no success of passing the arrays then. Any help on converting this function to cdef function would be appreciated. I really need this loop to go as fast as possible.

from cpython cimport array
import array
import numpy as np
cimport numpy as np

def fittnes(Orginal, Mutated):

    Fittnes = 0

    for x in range(0, 299):

        for y in range(0, 299):

            DeltaRed   = (Orginal[x][y][0] - Mutated[x][y][0])
            DeltaGreen = (Orginal[x][y][1] - Mutated[x][y][1])
            DeltaBlue  = (Orginal[x][y][2] - Mutated[x][y][2])

            Fittnes += (DeltaRed * DeltaRed + DeltaGreen * DeltaGreen + DeltaBlue * DeltaBlue)

    return Fittnes

My Main.py function call

 NewScore = cythona.fittnes(numpy.array(Orginal), numpy.array(MutatedImage))

If the input arrays are NumPy arrays, you could just do `((Orginal - Mutated)**2).sum()` for super speed. — Divakar, Nov 14 '15 at 15:24
I don't see anything cython specific in your code but as Divakar recommends you can speed your code up significantly just using numpy alone — Padraic Cunningham, Nov 14 '15 at 15:25
@Funktiona `**2` means [`power of 2 or squared`](http://docs.scipy.org/doc/numpy/reference/generated/numpy.power.html). — Divakar, Nov 14 '15 at 15:26

Divakar · Answer 1 · 2015-11-14T16:12:05.460

1

Got me interested to know about the speedup numbers, so I am posting this as a solution. So, as stated/discussed in the comments, if the inputs are NumPy arrays, you could use native NumPy tools, and in this case ndarray.sum(), like so -

out = ((Orginal - Mutated)**2).sum()

You can also use the very efficient np.einsum for the same task, like so -

sub = Orginal - Mutated
out = np.einsum('ijk,ijk->',sub,sub)

Runtime tests

Define functions -

def org_app(Orginal,Mutated):
    Fittnes = 0
    for x in range(0, Orginal.shape[0]):
        for y in range(0, Orginal.shape[1]):
            DR = (Orginal[x][y][0] - Mutated[x][y][0])
            DG = (Orginal[x][y][1] - Mutated[x][y][1])
            DB  = (Orginal[x][y][2] - Mutated[x][y][2])
            Fittnes += (DR * DR + DG * DG + DB * DB)
    return Fittnes

def einsum_based(Orginal,Mutated):
    sub = Orginal - Mutated
    return np.einsum('ijk,ijk->',sub,sub)

def dot_based(Orginal,Mutated): # @ali_m's suggestion
    sub = Orginal - Mutated
    return np.dot(sub.ravel(), sub.ravel())

def vdot_based(Orginal,Mutated):  # variant of @ali_m's suggestion
    sub = Orginal - Mutated
    return np.vdot(sub, sub)

Timings -

In [14]: M,N = 100,100
    ...: Orginal = np.random.rand(M,N,3)
    ...: Mutated = np.random.rand(M,N,3)
    ...: 

In [15]: %timeit org_app(Orginal,Mutated)
    ...: %timeit ((Orginal - Mutated)**2).sum()
    ...: %timeit einsum_based(Orginal,Mutated)
    ...: %timeit dot_based(Orginal,Mutated)
    ...: %timeit vdot_based(Orginal,Mutated)
    ...: 
10 loops, best of 3: 54.9 ms per loop
10000 loops, best of 3: 112 µs per loop
10000 loops, best of 3: 69.8 µs per loop
10000 loops, best of 3: 86.2 µs per loop
10000 loops, best of 3: 85.3 µs per loop

In [16]: # Inputs
    ...: M,N = 1000,1000
    ...: Orginal = np.random.rand(M,N,3)
    ...: Mutated = np.random.rand(M,N,3)
    ...: 

In [17]: %timeit org_app(Orginal,Mutated)
    ...: %timeit ((Orginal - Mutated)**2).sum()
    ...: %timeit einsum_based(Orginal,Mutated)
    ...: %timeit dot_based(Orginal,Mutated)
    ...: %timeit vdot_based(Orginal,Mutated)
    ...: 
1 loops, best of 3: 5.49 s per loop
10 loops, best of 3: 63 ms per loop
10 loops, best of 3: 23.9 ms per loop
10 loops, best of 3: 24.9 ms per loop
10 loops, best of 3: 24.9 ms per loop

edited Nov 14 '15 at 16:12

answered Nov 14 '15 at 15:41

Divakar

218,885
19
262
358

...or just `np.dot(sub.ravel(), sub.ravel())` – ali_m Nov 14 '15 at 15:50
@ali_m Nice! That works too! Add that as a solution? Would like to add it into the benchmarks either way. – Divakar Nov 14 '15 at 16:00
how fast is np.dot(sub.ravel(), sub.ravel()) compared to einsum_based? – Funktiona Nov 14 '15 at 16:09
@Funktiona Added in that alongwith `np.vdot` based one in the benchmarks, check it out. – Divakar Nov 14 '15 at 16:12
((Orginal - Mutated)**2).sum() and einsum_based(Orginal,Mutated) does not give the same results – Funktiona Nov 14 '15 at 17:09
@Funktiona How different are those? – Divakar Nov 14 '15 at 17:24
sum gives me 1000000000000+ – Funktiona Nov 14 '15 at 17:25
1

@Funktiona Ah yes! I think if you aren't working with `float64`, the values with `np.einsum` would be different. What's your input datatype? – Divakar Nov 14 '15 at 17:31
1

@Funktiona You can read up on value inconsistencies with `np.einsum` [`here`](http://stackoverflow.com/a/18366008/3293881). – Divakar Nov 14 '15 at 17:35
These return the color delta of all 3 combined. I need them to extract rgb and compare them separate. – Funktiona Nov 15 '15 at 00:08
@Funktiona I am not sure what you mean by extracting RGB? Could you clarify further? – Divakar Nov 15 '15 at 08:29

Efficiently calculating sum of squared differences

1 Answers1

Linked