Question About Linear and Circular Convolution - 1D and 2D

Question

We know that applying a filter on an image is called correlation or convolution depending on the filter angle. In Gonzalez I have read that we can apply linear convolution on an image. Here I have a doubt.

1. Suppose we have a vector image of 4 elements and a filter/kernel also of 4 elements then we get the output of linear convolution which contains 7 elements (4+4-1). Does that mean now the image is represented by 7 elements? If not then what does these 7 elements represent?

2. Also I want to know where do we use Circular Convolution. I have read many posts but not able to get it fully.

3. Last question is from filtering in frequency domain. We know that convolution of f(x,y)* h(x,y) in the spatial domain is equal to the product of DFT's of the image and the kernel i.e F(u,v).H(u,v) in the frequency domain. Then if we have a 64 *64 image and 3*3 filter, please tell me what will be the size of the sequence obtained by applying Linear Convolution in the spatial domain. Also Do we take the DFT of the image f(x,y) as it is or do we need to pad the image first before taking its DFT and if padding is needed how much? I know filter size should also be 64 * 64, so we need to change filter size from 3 * 3 to 64 * 64. It means padding of 61 rows and 61 columns of 0's but where should we pad these 0's. These 0's cannot be equally divided top,bottom,left , right as 61 * 61 is an odd number. Please explain.

Answer 1

Let me answer you:

1. For a signal of size $ m $ and a filter of size $ n $ the output of Linear Convolution is $ n + m - 1 $. In case of 2D signal of size $ \left( m, n \right) $ and filter of size $ \left( p, q \right) $ the output size is $ \left( m + p - 1, n + q - 1 \right) $.

2. You can read about Circular Convolution in Wikipedia. Basically when a convolution is applied on finite discrete signals one should take care of the boundaries. In most cases the default is assuming the signal i padded with zeros which results in Linear Convolution. If you use padding which build a periodic / circular signal and then apply convolution you will get Circular Convolution. It turns out that frequency domain multiplication of discrete signals is equivelnt of Circular Convolution in spatial domain.

3. You need to pad it with zeros and line the axis origin to match the image.
   Have a look at my answer for Kernel Convolution in Frequency Domain - Cyclic Padding. I also shared a MALAB code which shows how to build the kernel correctly.