One thing you will quickly come to terms with in Python is that if you code things the wrong way – they will run slowly. To illustrate this, let’s consider a simple box filter – it basically assigned each pixel the average of all the pixels in a neighbouring region. For example, a 5 x 5 box filter centred on pixel I[i,j] will assign to pixel [i,j] in the processed image, the average of the region I[i-2:i+2, j-2:j+2]. It has the effect of smoothing the image and suppressing noise artifacts – the larger the neighbourhood, the more profound the smoothing effect. We’ll test four ways of applying the box filter in Python. For the experiment, the following image (415 × 751) is processed.
The result is a smoothed image.
Here’s a close-up of before (left) and after (right) applying the box filter.
Method 1
This is the most naive approach to coding the solution in Python, yet in languages like C, this is usually the only approach due to the lack of ability to use sub-arrays. It does work, but is extremely slow – it takes 78 seconds to process this relatively small image.
def BoxFilter1(im, r=2):
imS = numpy.zeros(im.shape,dtype=numpy.float)
rN = (r*2+1)**2.0
nr, nc = im.shape
for i in xrange(r, nr-r):
for j in xrange(r, nc-r):
for k in xrange(-r, r+1):
for l in xrange(-r, r+1):
imS[i, j] += im[i-k, j-l] / rN
return imS
Method 2
In the second approach, the code processes the 5×5 neighbourhood without explicitly looping over each pixel in the image. This is achieved by means of vectorization. It relies on the use of numpy – the normalization and addition of the elements of the image are vectorized, releasing the outer two loops from the Method 1 which cycled through each element in the array. This leaves only two small loops: e.g., in the first cycle through the loops, the “neighbourhood” element at position [-2,-2] associated with each pixel in the image is normalized (divided by 25) and added to the pixel in the output image. Next cycle around the loop, neighbourhood element [-2,-1] is processed, etc. until all 25 elements have been processed. The algorithms speed? – 0.132 seconds – 590 times more efficient.
def BoxFilter2(im, r=2):
rN = (r*2+1)**2.0
nr, nc = im.shape
imS = numpy.zeros((nr-2*r,nc-2*r),dtype=numpy.float)
for k in xrange(-r, r+1):
for l in xrange(-r, r+1):
imS += im[r+k:nr-r+k, r+l:nc-r+l] / rN
return imS
Method 3
In the third approach rather than vectorize the image, the numpy function sum is used to sum the pixel values in the neighbourhood for each pixel in the image. The algorithms speed? – 7.31 seconds – only 10 times more efficient.
def BoxFilter3(im, r=2):
rN = (r*2+1)**2.0
nr, nc = im.shape
imS = numpy.zeros(im.shape,dtype=numpy.float)
for i in xrange(r, nr-r):
for j in xrange(r, nc-r):
imS[i, j] = numpy.sum(im[i-r:i+r+1, j-r:j+r+1]) / rN
return imS
Method 4
In the final approach the convolve function is used from the scipy.ndimage package (with a 5 x 5 box filter). The algorithms speed? – 0.11 seconds – slightly more efficient than Method 2.
def BoxFilter4(im):
k1 = numpy.array([[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]])/25.
imS = nd.convolve(im, k1, mode='constant', cval=0.0)
return imS
Every different coding approach (and there are probably more) has a different outcome – yet they all prescribe to the same algorithm. How fast your algorithm runs will be largely dependent on the coding methodology best suited to the language you are using.
The Craft of Coding 