• View
• History
• Print

Old 2008 Course Web: Main / ConvoleEndpoints

What to do about the edges of a convolution?

We discussed this in class, and it was pointed out to me that the topic isn't discussed in the book, and I'm not always consistent in my terminology. So here it is written down.

When you perform a convolution (I'll discuss this for the discrete 1D case, but it applies in other cases as well), there is an issue when the signals have finite length (since the convolution summations/integrals are infinite).

For example if I have the (discrete) signal:

    f(t) = [ 1 2 3 4 5 6 7 8 ]

It is clear that this signal has values for t = 0-7. But what about outside that range?

This comes up, because when we do a convolution between two signals, there will be times when the signals don't overlap. For example, if I define another signal

    g(t) = [ 1 1 1 ]

and compute

    h(t) = f(t) * g(t)

The first step (for t = 0) will have the signals overlap like:

        1 2 3 4 5 6 7 8
    1 1 1

Generally, we interpret those "blank" spaces as zeros. And for filter kernels, that's almost always the right thing to do.

So what we're trying to decide are the values of A B C for cases like

    A B 1 2 3 4 5 6 7 8
    1 1 1

or

    1 2 3 4 5 6 7 8 A B
                  1 1 1

Here are a few different choices

• make them be zero - this is the typical definition, but it has the downside that it can make black rings around the outside of your images when you blur
• make them have the last value (at the edge), so A and B have value 1 in the upper example and 8 in the lower example. This is sometimes referred to as clamping.
• you can reflect (A.K.A. mirroring) the last values of signal before the edge. So in the upper case, B would be 1, and A would be 2 (or, if you didn't include the edge in the reflection, you'd get B=2,A=3). For the lower case, it would be A=8, B=7 (or A=7, B=6). Reflection is nice because the "made up" signal has the similar frequency content to the original image.
• you can just forget about the overhanging parts. So the convolution sums in these examples just have 1 element. The catch here, is that since we're throwing away part of the kernel (it has a sum of 3 not of 1), we need to re-scale the kernel (which would have a single element) to have the same magnitude/sum as the original one did. I call this kernel renormalization because it involves re-normalizing the kernel to have the right magnitude.