image processing – convolution explained.

Image

(image from songho.ca)

The Python code below demonstrates convolution.  First, using Scipy’s convolve() function, then by two – far from optimal, far from high performance!  – ‘invented-here’ implementations of convolve(), that I hacked in order to understand what Scipy’s convolve() actually does.

The perhaps most interesting function to study is new_convolve(), which demonstrates the convention used by the convolve algorithm for the summation and multiplication of the cells.

convolution-graphical

The image to the left  illustates, using color,  which cells from the matrix are multiplied with which cells from the kernel. In this case, the objective is to calculate the new value for the highlighted cell of the matrix.

 

 

 

 

 

 

import numpy as np
import scipy.ndimage.filters as filter

def neighbors(r,c,supermatrix): 
    m = supermatrix[r:r+3,c:c+3] 
    return m

def convolve(n,k):
    sum = 0
    for (rr,cc),value in np.ndenumerate(n):
        sum += value * k[rr,cc]
    return sum

def new_convolve(n,k):
    sum = n[0,0] * k[2,2] + \
          n[1,0] * k[1,2] + \
          n[2,0] * k[0,2] + \
          n[0,1] * k[2,1] + \
          n[1,1] * k[1,1] + \
          n[2,1] * k[0,1] + \
          n[0,2] * k[2,0] + \
          n[1,2] * k[1,0] + \
          n[2,2] * k[0,0]

    return sum

matrix = np.array([[1,2,3],
                   [4,5,6],
                   [7,8,9]])

kernel = np.array([[0,0,0],
                   [1,0,0],
                   [0,0,0]])

print 'matrix'
print matrix

print 'kernel'
print kernel

print 'result'
print  filter.convolve(matrix,kernel,mode='constant', cval=0)

#####
# poor mans convolve, two versions
#####
shape = matrix.shape

# create a 'supermatrix' sm, surrounding the real matrix
# with the borders set to zeros
# insert the real matrix into the center of supermatrix

newshape =(shape[0] + 2,shape[1] + 2) 
sm = np.zeros(newshape,dtype=np.int)
sm[1:-1,1:-1] = matrix

result_own = np.zeros(shape,dtype=np.int)
result_own_unflipped = np.zeros(shape,dtype=np.int)

flipped_kernel = np.flipud(np.fliplr(kernel))

for (r,c),value in np.ndenumerate(matrix):
    n = neighbors(r,c,sm)
    result_own[r,c] = convolve(n,flipped_kernel)
    result_own_unflipped[r,c] = new_convolve(n,kernel)

print 'poor mans convolve'
print result_own
print

print 'unflipped poor mans convolve'
print result_own_unflipped
print
Advertisements

About swdevperestroika

High tech industry veteran, avid hacker reluctantly transformed to mgmt consultant.
This entry was posted in development, software and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s