3
$\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
    $\begingroup$ To convolve [something] with a kernel just means to convolve two functions, one of which is the something and the other is the kernel. In your particular case, the functions are two-dimensional, which may be adding to your confusion. But the principle is exactly the same. $\endgroup$
    – user856
    Nov 20, 2012 at 4:20
  • $\begingroup$ I guess part of my confusion has to do with the wording of the problem. It states to convolve the kernel against the horizontal and vertical axes of the matrix. $\endgroup$
    – martega
    Nov 20, 2012 at 5:47
  • 1
    $\begingroup$ That wording does seem like a mild abuse of terminology. They just want you to interpret the one-dimensional signal $[-1,0,1]$ as a 2D signal by orienting it horizontally or vertically. After that, you convolve two 2D signals as usual. $\endgroup$
    – user856
    Nov 20, 2012 at 6:18
  • $\begingroup$ Thanks, I assumed that what they meant but I wasn't sure if I was just completely missing it. If I interpret [-1,0,1] as a 2D signal is my pseudo-code correct? One aspect that I'm not sure about is that in a normal convolution operation, you reflect one of the the functions about some line (i.e. the y axis in the 1D case, y=x in the 2D case), but this problem wants to find the "derivatives". Intuitively, I would think this would mean that I shouldn't flip [-1,0,1] around, but if I didn't, then I wouldn't be doing the convolution operation. $\endgroup$
    – martega
    Nov 20, 2012 at 6:45

1 Answer 1

Reset to default
2
$\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
  • $\begingroup$ Beware: some authors in the image processing literature use $I_{i,j}K_{x+i,y+j}$ rather than $I_{i,j}K_{x-i,y-j}$ as the integrand. $\endgroup$
    – user1551
    Nov 20, 2012 at 12:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .