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 = img.mean(2)
img = img.astype(float)

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 np.dot(x-x_, 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:

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

Finally, we apply it to the whole image:

nc = np.zeros(img.shape, float)
for y in xrange(img.shape-sy):
for x in xrange(img.shape-sx):
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
plt.imshow(
pymorph.overlay(img.astype(np.uint8),
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.