$\begingroup$

I have a Matrix, M, of dimensions width x height. The problem is to apply the [-1, 0, 1] filter along the x and y axis (i.e. convolve the image with [-1, 0, 1] kernel along horizontal and vertical axis) in order to compute derivates dx and dy of M along the x and y direction respectively.

I am somewhat familliar with convolution, however I have never heard the terminology "convolve with kernel". How is this different than convolving two functions?

The following algorithm represents my understanding of how the operation would occur. Is this correct, or is there an error in my understanding?

M <- generate matrix with dimensions width x height
dx <- zero matrix with dimensions width x height
dy <- zero matrix with dimensions width x height
for row from 0 to height: for col from 0 to width: dx[row][col] = M[row][col+1] - M[row][col-1] dy[row][col] = M[row+1][col] - M[row-1][col]

$\endgroup$ 4

1 Answer

$\begingroup$

In image processing you are taking an input image, $I$, and applying some kernel, $K$, by means of a discrete convolution to produce a new filtered image, $\hat{I}$.

As a result you are calculating $\displaystyle \hat{I}_{x,y} = (I \star K)_{x,y} = \sum_{i = -\infty}^{+\infty} \sum_{i = -\infty}^{+\infty} I_{i,j} * K_{x-i,y-j}$ for each of the channels in the image.

Assuming a single channel, your naive algorithm is going to be quartic in time.

for(int x = 0; x < I_Width; x++) { for(int y = 0; y < I_Height; y++) { for(int i = 0; i < K_Width; i++) { for(int j = 0; j < K_Height; j++) { if(x-i >= 0 && x-i < I_Width && y-j >= 0 && y-j < I_Height) I_Hat[x,y] += I[x-i,y-j] * K[i, j] } } }
}

As your image grows in size you are going to want to use a more efficient algorithm such as the Fast Fourier Transform (FFT) algorithm.

$\endgroup$ 1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy