Image Convolution

1-D Convolution

The convolution operation in 1-D can be denoted as:

$$g(x)=f(x)\ast h(x)={\int }_{-\infty }^{\infty }f(\alpha )h(x-\alpha )d\alpha$$

2-D Convolution

• For an LSI 2-D system, the output is a weighted sum of shifted impulse responses
• The 2-D Convolution can be denoted as:

$$g(x,y)=f(x,y)\ast h(x)={\int }_{-\infty }^{\infty }{\int }_{-\infty }^{\infty }f(\alpha ,\beta )h(x-\alpha ,y-\beta )d\alpha d\beta$$

Flip, Slide, Multiply, Sum

There are 4 steps mechanical process for computing 2D image convolution:

1. Flipping: Rotate the filter/kernel matrix by 180 degrees (horizontally and vertically)
2. Sliding: Slide the kernel window over the input image and align its center at $(x,y)$
3. Multiply: Perform element-wise multiplication
4. Sum: Sum them up together

Correlation vs Convolution

Spatial Correlation is when we slide the filter matrix over an image to calculate the sum of element-wise products without flipping the kernel 180 degrees first.

$$h[x-m,y-n]=h[-(m-x),-(n-y)]$$

• the '$-$' sign shows us the flipping process
• For Symmetric Kernels (Gaussian, box average), flipping doesn't change the kernel
• For Derivative Kernals, flipping changes the sign/orientation
• Convolution: $g(x,y)={\sum }_j{\sum }_{i}h(i,j)f(x-i,y-j)$
• Correlation: $g(x,y)={\sum }_j{\sum }_{i}h(i,j)f(x+i,y+j)$

Convolution models Linear and Shift-Invariant (LSI) system responses and spatial filtering, whereas correlation is primarily used for template matching to detect where a specific sub-image pattern matches within a larger image.

Common Kernels

Kernel Name	Matrix Representation h(i,j)	Primary Function / Visual Effect	Sum of Weights
Identity	$\left[\begin{array}{ccc}0& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}\right]$	Leaves the input image unchanged.	$1$
Sharpen	$\left[\begin{array}{ccc}0& -1& 0\\ -1& 5& -1\\ 0& -1& 0\end{array}\right]$	Enhances edges and high-frequency spatial details.	$1$
Laplacian	$\left[\begin{array}{ccc}0& 1& 0\\ 1& -4& 1\\ 0& 1& 0\end{array}\right]$	Computes second-order spatial derivatives to detect edges.	$0$
Gaussian Blur	$\left[\begin{array}{ccc}1/16& 2/16& 1/16\\ 2/16& 4/16& 2/16\\ 1/16& 2/16& 1/16\end{array}\right]$	Applies a weighted bell-curve smoothing to reduce noise softly.	$1$
Mean Blur	$\left[\begin{array}{ccc}1/9& 1/9& 1/9\\ 1/9& 1/9& 1/9\\ 1/9& 1/9& 1/9\end{array}\right]$	Computes a uniform box average across all $9$ neighborhood pixels.	$1$

• Commutativity: The order of convolution does not affect the output.

$$f(x,y)\ast g(x,y)=g(x,y)\ast f(x,y)$$

• Associativity: Cascaded operations can be grouped in any order, allowing complex filters to be combined into a single pre-calculated kernel.

$$f(x,y)\ast (g(x,y)\ast h(x,y))=(f(x,y)\ast g(x,y))\ast h(x,y)$$

• Distributivity: Convolution distributes directly over addition.

$$f(x,y)\ast (g(x,y)+h(x,y))=f(x,y)\ast g(x,y)+f(x,y)\ast h(x,y)$$

• Shifted Impulse: Convolving an image with a shifted unit impulse $\delta (x-m,y-n)$ shifts the entire input image by offset $(m,n)$.

$$f(x,y)\ast \delta (x-m,y-n)=f(x-m,y-n)$$

• Separability: A 2D filter $h(x,y)$ that can be factored into two 1D filters ($h_x\cdot h_y$) reduces computational complexity from $O(k^2)$ to $O(2k)$ per pixel.

Padding

Zero Padding means that if the filter/sliding window/kernel is at the edge where there are no other pixels, we treat it as 0. In otherwords, every neighbour that falls outside the image counts as 0, and you still divide by the given amount. The divisor never changes.

Example of Image Convolution

The boxed up element in the array represents the origin.

We are given an input image of a $2\times 3$ matrix, $x(m,n)$ and a $2\times 2$ filter, $h(m,n)$.

$$x(m,n)=\left[\begin{array}{ccc}1& 4& 1\\ \boxed{2}& 5& 3\end{array}\right]$$ $$h(m,n)=\left[\begin{array}{cc}1& 1\\ \boxed{1}& -1\end{array}\right]$$

1. We first flip kernel $h(m,n)$ to $h(-m,-n)$

$$h(-m,-n)=\left[\begin{array}{cc}-1& \boxed{1}\\ 1& 1\end{array}\right]$$

2. Now we shift the Kernel from $h(-m,-n)$ to $h(1-m,-n)$

$$h(1-m,-n)=\left[\begin{array}{cc}\boxed{-1}& 1\\ 1& 1\end{array}\right]$$

3. We overlap matrix for $y(1,0)$

$$\text{Overlap for }y(1,0)=\left[\begin{array}{cc}\boxed{-2}& 5\\ 0& 0\end{array}\right]⟹y(1,0)=-2+5=3$$

4. Output Convolution Array $y(m,n)$

$$y(m,n)=\left[\begin{array}{cccc}1& 5& 5& 1\\ 3& 10& 5& 2\\ \boxed{2}& 3& -2& -3\end{array}\right]$$