Edge detection: The Convolution Approach

Today I would like to show a very basic technique of detection based on simple convolution of an image with small kernels (masks). The purpose of these kernels is to enhance certain properties of the image at each pixel. What properties? Those that define what means to be an edge, in a differential calculus way—exactly as it was defined in the description of the Canny edge detector. The big idea is to assign to each pixel a numerical value that expresses its strength as an edge: positive if we suspect that such structure is present at that location, negative if not, and zero if the image is locally flat around that point. Masks can be designed so that they mimic the effect of differential operators, but these can be terribly complicated and give rise to large matrices. The first approaches were performed with simple 3 \times 3 kernels. For example, Faler came up with the following four simple masks that emulate differentiation:

\begin{pmatrix} -1 & 0 & 1\\ -1 & 0 & 1\\ -1 & 0 & 1 \end{pmatrix}\quad \begin{pmatrix} 1 & 1 & 1\\ 0 & 0 & 0 \\ -1 & -1 & -1 \end{pmatrix}\quad \begin{pmatrix} -1 & -1 & -1 \\ -1 & 8 & -1 \\ -1 & -1 & -1 \end{pmatrix}\quad \begin{pmatrix} 0 & 1 & 0 \\ -1 & 0 & 1 \\ 0 & -1 & 0 \end{pmatrix}

Note that, adding all the values of each matrix, one obtains zero. This is consistent with the third property required for our kernels: in the event of a locally flat area around a given pixel, convolution with any of these will offer a value of zero.

from numpy import *
from scipy import misc, ndimage

def detect_edges(image,masks):
    edges=zeros(image.shape)
    for mask in masks:
        edges=maximum(scipy.ndimage.convolve(image,mask), edges)
    return edges

image=scipy.misc.lena()
Faler=[ [[-1,0,1],[-1,0,1],[-1,0,1]], 
        [[1,1,1],[0,0,0],[-1,-1,-1]],
   	[[-1,-1,-1],[-1,8,-1],[-1,-1,-1]],
	[[0,1,0],[-1,0,1],[0,-1,0]] ]

edges=detect_edges(image, Faler)

Note that the computed edges show different intensities; the brighter, the more likely to be a genuine edge—as found by this technique. With a simple thresholding we should be able to create a True-False image with the required edge map. How would the reader proceed to find a reliable threshold for this task?

Sobel pushed the technique a little bit further by creating compass gradients. In a nutshell: at any given pixel, an edge could spread in eight different directions; therefore, we could create for each possibility a different kernel capturing such event. These are the masks proposed by Sobel, following that philosophy:

\begin{array}{cccc}  \begin{pmatrix} 1&2&1\\ 0&0&0\\ -1&-2&-1 \end{pmatrix} &  \begin{pmatrix} 2&1&0\\ 1&0&-1\\ 0&-2&-1 \end{pmatrix} &  \begin{pmatrix} 1&0&-1\\ 2&0&-2\\ 1&0&-1 \end{pmatrix} &  \begin{pmatrix} 0&-1&-2\\ 1&0&-1\\ 2&1&0 \end{pmatrix} \\ \\  \begin{pmatrix} -1&-2&-1\\ 0&0&0\\ 1&2&1 \end{pmatrix} &  \begin{pmatrix} -2&-1&0\\ -1&0&1\\ 0&1&2 \end{pmatrix} &  \begin{pmatrix} -1&0&1\\ -2&0&2\\ -1&0&1 \end{pmatrix} &  \begin{pmatrix} 0&1&2\\ -1&0&1\\ -2&-1&0 \end{pmatrix}   \end{array}

You have surely heard also of Kirsch and Prewitt’s edge detectors. They can also be realized as convolutions with the proper sets of kernels in the same way. I collected below their corresponding masks for reference. I leave to the reader the task to run a few experiments, compare the different outputs for the same image, and find good choices of thresholds for each case. I also encourage you to create your own set of masks: do not restrict yourself to 3 \times 3 matrices, or only to eight possibilities. Do you see any connection with wavelets? If so, how would you combine these two a-priori disconnected ideas to identify edges?

Kirsch = [ [[5,5,5],[-3,0,-3],[-3,-3,-3]],
[[-3,5,5],[-3,0,5],[-3,-3,-3]],
[[-3,-3,5],[-3,0,5],[-3,-3,5]],
[[-3,-3,-3],[-3,0,5],[-3,5,5]],
[[-3,-3,-3],[-3,0,-3],[5,5,5]],
[[-3,-3,-3],[5,0,-3],[5,5,-3]],
[[5,-3,-3],[5,0,-3],[5,-3,-3]],
[[5,5,-3],[5,0,-3],[-3,-3,-3]] ]
Prewitt = [ [[1,1,1],[1,-2,1],[-1,-1,-1]],
[[1,1,1],[1,-2,-1],[1,-1,-1]],
[[1,1,-1],[1,-2,-1],[1,1,-1]],
[[1,-1,-1],[1,-2,-1],[1,1,1]],
[[-1,-1,-1],[1,-2,1],[1,1,1]],
[[-1,-1,1],[1,-2,1],[1,1,1]],
[[-1,1,1],[-1,-2,1],[-1,1,1]],
[[1,1,1],[-1,-2,1],[-1,-1,1]] ]

References


The Image Processing Handbook, Sixth Edition

Advertisements
  1. Ksiv
    November 9, 2014 at 7:17 pm

    Good, thnx you for sharing your knowledges.
    Maybe mistake in second Sobel mask? (-2 should be -1)

    • November 9, 2014 at 9:13 pm

      You are correct! The entries must add up to zero. Thanks!—I have just taken care of it.

  1. November 20, 2011 at 12:28 am

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

%d bloggers like this: