Recently, in the pythonvision mailing list, Alex Liberzon asked how to perform normalised cross-correlation in Python.

His data looks like the following:


and the problem is to detect the beads that are visible. The proposed solution is to use normalised cross-correlation.

Here is the code to implement it. We start with a few imports:

import numpy as np
import mahotas
from scipy import ndimage

Now, we load the image and take out a bead by hard-coding its coordinates:

img = mahotas.imread('copy_cam1.jpg')
img = img.mean(2)
img = img.astype(float)
bead = img[433:443,495:512]
sy,sx = bead.shape

Here is now the code for NCC:

def ncc(x,y):
    x = x.ravel()
    x_ = x.mean()
    sx = x.std()
    y = y.ravel()
    y_ = y.mean()
    sy = y.std()
    return, y-y_)/sx/sy

We now only need to apply it to the whole image with bead as the second argument. However, it is clear that it will be inefficient if y is always the same argument to permanently compute its mean and standard deviation. So, we normalise bead first:

bead = bead.astype(float)
bead = bead.ravel()
bead -= bead.mean()
bead /= bead.std()

def ncc(x,y):
    x = x.ravel()
    x_ = x.mean()
    sx = x.std()
    return, y)/sx

Finally, we apply it to the whole image:

nc = np.zeros(img.shape, float)
for y in xrange(img.shape[0]-sy):
    for x in xrange(img.shape[1]-sx):
        nc[y+sy//2,x+sx//2] = ncc(img[y:y+sy,x:x+sx],bead)
nc /= sx*sy

This is a pretty bad algorithm, but it takes less than 30s on a laptop.

Here is how we display the result:

import matplotlib.pyplot as plt
import pymorph
    pymorph.dilate(pymorph.dilate(nc > .7))))

By trial and error, we set a threshold at 0.7 and call pymorph.dilate twice to make the dots bigger.

The result looks like:


Not great, but we got most of the beads with very little effort.

The full code is available as a gist.