7  Convolution, Filtering, and Local Operators

Convolution is one of the central mathematical operations in computer vision. It is the bridge between classical image processing and convolutional neural networks. In classical vision, convolution is used for smoothing, sharpening, denoising, derivative estimation, edge detection, texture analysis, and scale-space construction. In deep learning, convolution becomes a learnable local linear map applied repeatedly across an image. This chapter develops the mathematical structure of convolution, filtering, and local operators for MA Applied Mathematics and MS Statistics students.

7.1 Learning Goals

After reading this chapter, students should be able to:

1. define discrete convolution and distinguish it from cross-correlation;
2. describe convolution as a linear local operator and as a matrix multiplication;
3. explain translation equivariance and why it matters in vision;
4. handle boundary conditions such as zero, periodic, reflection, and replicate padding;
5. derive common filters, including averaging, Gaussian smoothing, sharpening, derivative, Sobel, and Laplacian filters;
6. explain separable filters and their computational advantages;
7. connect Gaussian smoothing with scale space and the heat equation;
8. interpret filtering as a statistical estimator under noise;
9. explain how CNN convolution generalizes classical convolution using learned multi-channel kernels;
10. design small Python experiments to visualize the behavior of filters.

7.2 6.1 Why Local Operators Matter

An image is large, but many visual structures are local. Edges, corners, texture primitives, small object parts, and local brightness changes can often be detected from a neighborhood around a pixel. A local operator transforms each pixel using only nearby pixels.

For a grayscale image \(I\) indexed by \((i,j)\), a local operator with neighborhood radius \(r\) has the schematic form

\[ (TI)[i,j] = \Phi\bigl( I[i+a,j+b] : -r\le a,b\le r \bigr), \]

where \(\Phi\) is a function of a local patch. If \(\Phi\) is linear, the operator has the form

\[ (TI)[i,j] = \sum_{a=-r}^{r}\sum_{b=-r}^{r} h[a,b] I[i+a,j+b]. \]

This is a local linear filter. Depending on the indexing convention, it is called either convolution or cross-correlation.

A local linear image operator is built from three ingredients:

\[ \text{patch extraction} \quad + \quad \text{linear weights} \quad + \quad \text{shared application over all pixels}. \]

This is exactly the mathematical skeleton of a convolutional layer.

Locality matters because nearby pixels are strongly dependent. Natural images usually have strong spatial correlation: if two pixels are close, their intensities are more likely to be similar than if they are far apart. Filtering uses this dependence to reduce noise, detect changes, or compute local summaries.

7.3 6.2 Discrete Images and Neighborhoods

Let a grayscale image be an array

\[ I \in \mathbb{R}^{H\times W}. \]

The value at row \(i\) and column \(j\) is \(I[i,j]\). A square neighborhood of radius \(r\) around \((i,j)\) is

\[ \mathcal{N}_r(i,j) = \{(i+a,j+b): -r\le a,b\le r\}. \]

The corresponding patch is a vector in \(\mathbb{R}^{(2r+1)^2}\):

\[ P_{i,j}(I) = \bigl(I[i+a,j+b]\bigr)_{-r\le a,b\le r}. \]

A filter kernel is an array

\[ K\in \mathbb{R}^{(2r+1)\times (2r+1)}. \]

The local weighted average at \((i,j)\) is the inner product

\[ \langle K,P_{i,j}(I)\rangle = \sum_{a=-r}^{r}\sum_{b=-r}^{r}K[a,b]I[i+a,j+b]. \]

This expression is the basic local linear measurement. Most classical filters and CNN filters are variations of this formula.

7.3.1 Interactive: a local kernel acting on a patch

The output at a single pixel is an inner product between a small patch and a kernel. This demo shows the patch, the kernel, and the elementwise product whose sum becomes one filtered pixel.

7.4 6.3 Convolution and Cross-Correlation

There are two closely related operations.

7.4.1 Cross-correlation

The discrete cross-correlation of image \(I\) with kernel \(K\) is

\[ (K \star I)[i,j] = \sum_{a=-r}^{r}\sum_{b=-r}^{r}K[a,b]I[i+a,j+b]. \]

This is the operation used by most deep-learning libraries when they say ``convolution.’’ It does not flip the kernel.

7.4.2 Convolution

The discrete convolution of \(I\) with \(K\) is

\[ (K * I)[i,j] = \sum_{a=-r}^{r}\sum_{b=-r}^{r}K[a,b]I[i-a,j-b]. \]

Equivalently,

\[ (K * I)[i,j] = \sum_{a=-r}^{r}\sum_{b=-r}^{r}K[-a,-b]I[i+a,j+b]. \]

So convolution is cross-correlation with the kernel reflected across its center.

7.4.3 When does the distinction matter?

If the kernel is symmetric, meaning

\[ K[a,b]=K[-a,-b], \]

then convolution and cross-correlation agree. Gaussian smoothing kernels and many averaging kernels are symmetric. Derivative filters, however, are usually not symmetric. For example, the one-dimensional forward difference kernel \([-1,1]\) changes sign when flipped.

For this reason, the mathematical literature is careful about the distinction. Deep learning often uses the cross-correlation convention because the weights are learned, so flipping can be absorbed into the learned parameters.

7.5 6.4 Linearity

Let \(T_K\) denote filtering by kernel \(K\):

\[ T_K(I)=K*I. \]

This map is linear. For images \(I,J\) and scalars \(\alpha,\beta\),

\[ T_K(\alpha I+\beta J) =K*(\alpha I+\beta J) =\alpha(K*I)+\beta(K*J). \]

Linearity has several consequences:

• the response to a sum is the sum of responses;
• filtering can be represented by a matrix multiplication after vectorization;
• eigenvectors and frequency modes become important;
• noise propagation can be analyzed using variance formulas;
• stacked linear filters without nonlinearities collapse into one linear filter.

Linearity is also a limitation. Edges, corners, object parts, and semantic classes are not fully captured by one linear filter. This is why modern vision systems alternate linear local maps with nonlinearities, pooling, normalization, and attention.

7.6 6.5 Translation Equivariance

Let \(\tau_{(u,v)}\) be the translation operator

\[ (\tau_{(u,v)}I)[i,j]=I[i-u,j-v]. \]

A map \(T\) is translation equivariant if

\[ T(\tau_{(u,v)}I)=\tau_{(u,v)}T(I). \]

This means: if the input image shifts, the output shifts by the same amount.

For convolution, assuming a boundary convention compatible with translation, we have

\[ K*(\tau_{(u,v)}I)=\tau_{(u,v)}(K*I). \]

This property is fundamental for vision. An edge detector should detect the same edge whether it appears near the left side, the center, or the right side of an image. A CNN feature detector should also respond to the same local pattern wherever it occurs.

NoteEquivariance is not invariance

Translation equivariance means the output shifts when the input shifts. Translation invariance means the output does not change when the input shifts:

\[ T(\tau I)=T(I). \]

Convolution is equivariant. Classification networks often try to become approximately invariant after convolution, nonlinearities, pooling, and global averaging.

7.7 6.6 Convolution as a Matrix

Because convolution is linear, it can be written as matrix multiplication. Let \(x=\operatorname{vec}(I)\in\mathbb{R}^{HW}\). Then there exists a matrix \(A_K\) such that

\[ \operatorname{vec}(K*I)=A_Kx. \]

The matrix \(A_K\) is sparse because each output pixel depends only on a small neighborhood. In one dimension, convolution matrices are Toeplitz matrices. For a signal \(x=(x_1,\ldots,x_n)\) and a three-point kernel \((k_{-1},k_0,k_1)\), ignoring boundary details,

\[ A_K = \begin{bmatrix} k_0 & k_1 & 0 & \cdots & 0\\ k_{-1} & k_0 & k_1 & \ddots & \vdots\\ 0 & k_{-1} & k_0 & \ddots & 0\\ \vdots & \ddots & \ddots & \ddots & k_1\\ 0 & \cdots & 0 & k_{-1} & k_0 \end{bmatrix}. \]

In two dimensions, convolution matrices are block Toeplitz with Toeplitz blocks, under suitable boundary conventions. With periodic boundary conditions, the matrices become block circulant and are diagonalized by the two-dimensional discrete Fourier transform.

This matrix viewpoint is useful for proving facts about filtering:

• smoothing reduces high-frequency components;
• derivative filters amplify high-frequency components;
• repeated convolution corresponds to powers of a matrix;
• deblurring is an inverse problem;
• conditioning depends on the spectrum of \(A_K\).

7.8 6.7 Boundary Conditions

Filtering requires image values outside the original domain. For example, if \((i,j)\) is near the top-left corner, the neighborhood includes invalid indices such as \((-1,j)\) or \((i,-1)\). A boundary convention extends \(I\) beyond its domain.

Common choices include:

Boundary condition	Rule	Typical effect
zero padding	outside pixels equal \(0\)	dark border artifacts
replicate padding	use nearest valid pixel	stable edge behavior
reflection padding	mirror the image at boundary	reduces artificial jumps
periodic padding	wrap around	mathematically convenient for Fourier analysis
valid convolution	compute only where kernel fits	shrinks image

Boundary conditions are not just software details. They change the operator. For small images or large kernels, they can substantially affect the result.

Mathematically, boundary handling is an extension operator

\[ E:\mathbb{R}^{H\times W}\to \mathbb{R}^{\mathbb{Z}\times \mathbb{Z}}. \]

Filtering is then

\[ (T_KI)[i,j] = \sum_{a,b}K[a,b](EI)[i-a,j-b]. \]

7.9 6.8 Averaging Filters

The simplest smoothing filter is the box average. For a \((2r+1)\times(2r+1)\) neighborhood,

\[ K[a,b] =\frac{1}{(2r+1)^2}, \qquad -r\le a,b\le r. \]

Then

\[ (K*I)[i,j] =\frac{1}{(2r+1)^2}\sum_{a=-r}^{r}\sum_{b=-r}^{r}I[i-a,j-b]. \]

This reduces independent noise. Suppose

\[ Y[i,j]=I[i,j]+\varepsilon[i,j], \qquad \varepsilon[i,j]\overset{\text{i.i.d.}}{\sim}(0,\sigma^2). \]

If \(K\) has weights summing to \(1\), then the filtered noise has variance

\[ \operatorname{Var}\left(\sum_{a,b}K[a,b]\varepsilon[i-a,j-b]\right) = \sigma^2\sum_{a,b}K[a,b]^2. \]

For the box filter with \(m=(2r+1)^2\) equal weights, this becomes

\[ \sigma^2\sum_{a,b}\frac{1}{m^2}=\frac{\sigma^2}{m}. \]

So averaging reduces variance. However, it introduces bias near edges because it mixes pixels from different regions. This is the basic smoothing tradeoff:

\[ \text{less noise} \quad \text{but} \quad \text{blurrier edges}. \]

7.10 6.9 Gaussian Filtering

The continuous two-dimensional Gaussian with scale \(\sigma>0\) is

\[ G_\sigma(x,y) =\frac{1}{2\pi\sigma^2}\exp\left(-\frac{x^2+y^2}{2\sigma^2}\right). \]

A discrete Gaussian kernel is obtained by sampling and normalizing:

\[ K_\sigma[a,b] =\frac{\exp\left(-(a^2+b^2)/(2\sigma^2)\right)} {\sum_{u=-r}^{r}\sum_{v=-r}^{r}\exp\left(-(u^2+v^2)/(2\sigma^2)\right)}. \]

Gaussian filters are preferred over box filters because they are smooth, rotationally symmetric in the continuous limit, separable, and connected to the heat equation.

7.10.1 Semigroup property

Continuous Gaussians satisfy

\[ G_{\sigma_1}*G_{\sigma_2}=G_{\sqrt{\sigma_1^2+\sigma_2^2}}. \]

Thus repeated Gaussian smoothing is equivalent to one Gaussian smoothing with a larger variance. In terms of scale parameter \(t=\sigma^2\), this becomes

\[ G_{t_1}*G_{t_2}=G_{t_1+t_2}. \]

7.10.2 Heat equation connection

Let

\[ L(x,y,t)=G_{\sqrt{2t}}*I(x,y). \]

Then \(L\) solves the heat equation

\[ \frac{\partial L}{\partial t}=\Delta L, \qquad L(x,y,0)=I(x,y), \]

where

\[ \Delta L=\frac{\partial^2 L}{\partial x^2}+\frac{\partial^2 L}{\partial y^2}. \]

This gives a deep interpretation of Gaussian smoothing: smoothing is diffusion of image intensity over the spatial domain.

7.10.3 Interactive: Gaussian smoothing across scale

Larger Gaussian scale suppresses fine texture and noise but also blurs edges. The scale parameter controls the tradeoff between detail and stability.

7.11 6.10 Separable Filters

A two-dimensional kernel \(K\) is separable if there exist one-dimensional kernels \(u\) and \(v\) such that

\[ K[a,b]=u[a]v[b]. \]

Then

\[ K*I = u*(v*I), \]

where one convolution is applied along rows and the other along columns.

The Gaussian is separable:

\[ G_\sigma(x,y) =\left(\frac{1}{\sqrt{2\pi}\sigma}e^{-x^2/(2\sigma^2)}\right) \left(\frac{1}{\sqrt{2\pi}\sigma}e^{-y^2/(2\sigma^2)}\right). \]

This reduces cost. A direct \(m\times m\) convolution costs approximately \(m^2\) multiplications per pixel. A separable convolution costs approximately \(2m\) multiplications per pixel.

For large kernels, the difference is substantial:

\[ \frac{m^2}{2m}=\frac{m}{2}. \]

A \(31\times 31\) separable Gaussian can be about \(15.5\) times cheaper than direct convolution.

7.12 6.11 Derivative Filters

Edges are associated with rapid changes in intensity. In continuous variables, the gradient of a grayscale image \(I(x,y)\) is

\[ \nabla I(x,y) = \begin{bmatrix} I_x(x,y)\\ I_y(x,y) \end{bmatrix}. \]

The gradient magnitude and orientation are

\[ \|\nabla I\| =\sqrt{I_x^2+I_y^2}, \qquad \theta=\operatorname{atan2}(I_y,I_x). \]

In discrete images, derivatives are approximated by finite differences. A central difference approximation for \(I_x\) is

\[ I_x[i,j]\approx \frac{I[i,j+1]-I[i,j-1]}{2}. \]

This corresponds to the kernel

\[ K_x =\frac{1}{2} \begin{bmatrix} -1 & 0 & 1 \end{bmatrix}. \]

Similarly,

\[ K_y =\frac{1}{2} \begin{bmatrix} -1\\ 0\\ 1 \end{bmatrix}. \]

Derivative filters amplify high-frequency noise, so in practice derivatives are often computed after smoothing.

7.13 6.12 Sobel and Prewitt Filters

The Sobel filter combines smoothing in one direction with differentiation in the other. The horizontal derivative Sobel kernel is

\[ S_x =\begin{bmatrix} -1 & 0 & 1\\ -2 & 0 & 2\\ -1 & 0 & 1 \end{bmatrix}. \]

The vertical derivative Sobel kernel is

\[ S_y =\begin{bmatrix} -1 & -2 & -1\\ 0 & 0 & 0\\ 1 & 2 & 1 \end{bmatrix}. \]

The Sobel operator estimates derivatives while also smoothing perpendicular to the derivative direction. It is separable:

\[ S_x = \begin{bmatrix}1\\2\\1\end{bmatrix} \begin{bmatrix}-1 & 0 & 1\end{bmatrix}. \]

Thus Sobel is a simple example of combining a smoothing filter and a derivative filter.

7.13.1 Interactive: common filter responses

The same image is passed through several kernels. Compare smoothing, sharpening, and derivative responses.

7.14 6.13 Laplacian and Second Derivatives

The Laplacian of a smooth image is

\[ \Delta I =I_{xx}+I_{yy}. \]

A common discrete approximation is

\[ \Delta I[i,j] \approx I[i+1,j]+I[i-1,j]+I[i,j+1]+I[i,j-1]-4I[i,j]. \]

This corresponds to the kernel

\[ L =\begin{bmatrix} 0 & 1 & 0\\ 1 & -4 & 1\\ 0 & 1 & 0 \end{bmatrix}. \]

Another version includes diagonal neighbors:

\[ L_8 =\begin{bmatrix} 1 & 1 & 1\\ 1 & -8 & 1\\ 1 & 1 & 1 \end{bmatrix}. \]

The Laplacian is sensitive to noise because it uses second differences. A standard solution is to smooth first and then apply the Laplacian:

\[ \Delta(G_\sigma*I). \]

By commutativity of convolution and differentiation in the continuous setting,

\[ \Delta(G_\sigma*I)=(\Delta G_\sigma)*I. \]

The filter \(\Delta G_\sigma\) is called the Laplacian of Gaussian. It detects blob-like structures and zero-crossings associated with edges.

7.15 6.14 Difference of Gaussians

The Difference of Gaussians filter is

\[ \operatorname{DoG}_{\sigma,k\sigma} =G_{k\sigma}-G_\sigma, \qquad k>1. \]

Applied to an image,

\[ \operatorname{DoG}_{\sigma,k\sigma}*I =(G_{k\sigma}*I)-(G_\sigma*I). \]

The DoG filter approximates a scale-normalized Laplacian of Gaussian. It is important in scale-space feature detection because it highlights structures that appear at a particular scale.

Intuitively:

• \(G_\sigma*I\) removes very fine variation;
• \(G_{k\sigma}*I\) removes somewhat coarser variation;
• their difference isolates information between these scales.

This idea will reappear in local feature detection and SIFT-style methods.

7.16 6.15 Sharpening Filters

Smoothing removes high frequencies. Sharpening amplifies high-frequency components. A common sharpening construction is

\[ I_{\text{sharp}} =I+\alpha(I-G_\sigma*I), \qquad \alpha>0. \]

The term

\[ I-G_\sigma*I \]

is a high-pass component. Adding it back increases edge contrast. This method is called unsharp masking.

A simple discrete sharpening kernel is

\[ K_{\text{sharp}} =\begin{bmatrix} 0 & -1 & 0\\ -1 & 5 & -1\\ 0 & -1 & 0 \end{bmatrix}. \]

The weights sum to one, so constant regions are preserved. Negative weights subtract neighboring values, increasing local contrast.

Sharpening can make images visually clearer, but it can also amplify noise and produce ringing artifacts.

7.17 6.16 Filtering as Statistical Estimation

Suppose the observed image is

\[ Y[i,j]=I[i,j]+\varepsilon[i,j], \qquad \varepsilon[i,j]\sim (0,\sigma^2). \]

A filtered estimate is

\[ \widehat I[i,j] =\sum_{a,b}K[a,b]Y[i-a,j-b]. \]

Assume the weights sum to one:

\[ \sum_{a,b}K[a,b]=1. \]

Then

\[ \mathbb{E}[\widehat I[i,j]] =\sum_{a,b}K[a,b]I[i-a,j-b]. \]

The bias is

\[ \operatorname{Bias}(\widehat I[i,j]) =\sum_{a,b}K[a,b]I[i-a,j-b]-I[i,j]. \]

The variance is

\[ \operatorname{Var}(\widehat I[i,j]) =\sigma^2\sum_{a,b}K[a,b]^2. \]

Thus the mean squared error decomposes as

\[ \operatorname{MSE}(\widehat I[i,j]) =\operatorname{Bias}(\widehat I[i,j])^2 +\operatorname{Var}(\widehat I[i,j]). \]

This is the classical bias-variance tradeoff. A larger smoother usually has lower variance but higher bias near edges and texture boundaries.

Filtering is not only an image-processing operation. It is a statistical estimator whose behavior can be analyzed by bias, variance, smoothness, and assumptions about local structure.

7.18 6.17 Local Polynomial Viewpoint

Filtering can also be understood as local regression. Around a point \((i,j)\), suppose the image is approximately constant:

\[ I[i+a,j+b]\approx c. \]

The local least-squares estimate of \(c\) from noisy observations is the local average. If we instead assume the image is approximately linear,

\[ I[i+a,j+b]\approx c_0+c_1a+c_2b, \]

then local least squares estimates both intensity and gradient. This viewpoint connects finite-difference filters with statistical smoothing.

More generally, local polynomial regression solves

\[ \min_\beta \sum_{a,b}w[a,b] \left( Y[i+a,j+b] - \sum_{p+q\le d}\beta_{pq}a^pb^q \right)^2. \]

The estimated coefficients provide smoothed derivatives. This formulation is especially useful for applied mathematics and statistics students because it shows that filters can be derived from approximation assumptions rather than memorized as fixed templates.

7.19 6.18 Nonlinear Local Filters

Not all useful local operators are linear. The median filter is

\[ (TI)[i,j] =\operatorname{median}\{I[i+a,j+b]:(a,b)\in\mathcal{N}_r\}. \]

The median filter is effective for impulsive salt-and-pepper noise because it rejects extreme outliers. However, it is nonlinear:

\[ T(I+J)\ne T(I)+T(J) \]

in general.

Another important nonlinear filter is the bilateral filter:

\[ \widehat I[i,j] = \frac{1}{Z[i,j]} \sum_{a,b} \exp\left(-\frac{a^2+b^2}{2\sigma_s^2}\right) \exp\left(-\frac{(I[i+a,j+b]-I[i,j])^2}{2\sigma_r^2}\right) I[i+a,j+b]. \]

Here \(\sigma_s\) controls spatial distance and \(\sigma_r\) controls intensity similarity. The bilateral filter smooths within regions while reducing smoothing across edges. It is nonlinear because the weights depend on the image itself.

This idea foreshadows attention mechanisms: weights are not fixed only by location; they depend on similarity of content.

7.20 6.19 Multi-Channel Images

For a color image

\[ I\in \mathbb{R}^{H\times W\times C}, \]

where \(C=3\) for RGB, a channelwise filter may apply the same spatial kernel to each channel:

\[ (K*I)[i,j,c] =\sum_{a,b}K[a,b]I[i-a,j-b,c]. \]

A more general linear local filter can mix channels:

\[ Y[i,j,d] =\sum_{c=1}^{C}\sum_{a,b}K[a,b,c,d]I[i-a,j-b,c]. \]

Here \(d\) indexes output channels. This formula is exactly the multi-channel convolution used in CNNs.

The kernel tensor has shape

\[ (\text{kernel height})\times(\text{kernel width})\times (\text{input channels})\times(\text{output channels}). \]

Each output channel is a learned local linear combination of all input channels.

7.21 6.20 Computational Complexity

For an image of size \(H\times W\) and an \(m\times m\) kernel, direct convolution costs

\[ O(HWm^2). \]

If the kernel is separable, the cost becomes

\[ O(HWm). \]

If the kernel is large, convolution can also be performed using the Fourier transform. By the convolution theorem,

\[ K*I=\mathcal{F}^{-1}(\mathcal{F}(K)\cdot\mathcal{F}(I)). \]

The FFT-based cost is approximately

\[ O(HW\log(HW)), \]

after padding and handling boundary effects. For small kernels, direct spatial convolution is usually faster. For large kernels, FFT convolution may be advantageous.

In deep learning, most convolution kernels are small, such as \(3\times3\), \(5\times5\), or \(7\times7\). Small kernels are efficient and can be stacked to build larger effective receptive fields.

7.22 6.21 Receptive Fields

The receptive field of an output unit is the set of input pixels that can influence it. For a single \(3\times3\) convolution, the receptive field is \(3\times3\). For two stacked \(3\times3\) convolutions with stride \(1\), the receptive field becomes \(5\times5\). For \(L\) stacked \(3\times3\) convolutions, the receptive field size is

\[ (2L+1)\times(2L+1). \]

Stacking small filters has two advantages:

1. fewer parameters than one large filter;
2. nonlinearities between layers create a more expressive map.

For example, one \(7\times7\) single-channel filter has \(49\) weights. Three \(3\times3\) filters have \(27\) spatial weights per channel path, and if nonlinearities are inserted between them, the model can represent nonlinear local features.

7.23 6.22 Stride, Padding, and Dilation

A convolutional layer often uses stride, padding, and dilation.

7.23.1 Stride

Stride \(s\) means that output locations are sampled every \(s\) pixels:

\[ Y[p,q] =\sum_{a,b}K[a,b]I[sp-a,sq-b]. \]

Stride reduces spatial resolution. It is a form of learned or fixed downsampling.

7.23.2 Padding

Padding controls output size. For a one-dimensional signal of length \(n\), kernel size \(m\), padding \(p\), and stride \(s\), the output length is

\[ \left\lfloor \frac{n+2p-m}{s}\right\rfloor+1. \]

The same formula applies separately to height and width in two dimensions.

7.23.3 Dilation

Dilation inserts gaps between kernel samples:

\[ Y[i,j] =\sum_{a,b}K[a,b]I[i-da,j-db], \]

where \(d\) is the dilation rate. Dilation increases receptive field without increasing the number of parameters.

7.24 6.23 Classical Filters and CNN Filters

A classical filter is fixed by mathematical design. A CNN filter is learned from data. But the local computation is similar.

Classical filter:

\[ Y[i,j]=\sum_{a,b}K[a,b]I[i-a,j-b]. \]

CNN filter:

\[ Y[i,j,d] =\sigma\left( \beta_d+ \sum_{c=1}^{C}\sum_{a,b}K[a,b,c,d]I[i-a,j-b,c] \right), \]

where \(\sigma\) is a nonlinear activation function.

The key differences are:

Classical filtering	CNN filtering
kernel chosen manually	kernel learned from data
usually few filters	many filters per layer
often linear	followed by nonlinear activation
interpretable by design	sometimes interpretable by visualization
used for specific low-level task	trained for end-to-end objective

Despite these differences, CNNs inherit the same mathematical principles: locality, shared weights, equivariance, and composition.

7.24.1 Interactive: local features from learned-style filters

This demo compares responses from several small filters that resemble early CNN features: smoothing, horizontal edges, vertical edges, and diagonal patterns.

7.25 6.24 Equivariance, Pooling, and Invariance

Convolution is translation equivariant. Pooling and global averaging help convert equivariant feature maps into more invariant representations.

For a feature map \(F\), max pooling over a window \(\mathcal{W}\) is

\[ (PF)[i,j] =\max_{(a,b)\in\mathcal{W}}F[si+a,sj+b]. \]

Average pooling is

\[ (PF)[i,j] =\frac{1}{|\mathcal{W}|} \sum_{(a,b)\in\mathcal{W}}F[si+a,sj+b]. \]

Pooling reduces resolution and creates local robustness to small shifts. However, it also discards spatial information. Segmentation networks must preserve or recover spatial detail, while classification networks can often discard more spatial information.

7.26 6.25 Frequency Interpretation of Filters

By the convolution theorem, a filter modifies frequencies by multiplication:

\[ \widehat{K*I}(\omega_x,\omega_y) =\widehat K(\omega_x,\omega_y)\widehat I(\omega_x,\omega_y). \]

Thus \(\widehat K\) is the frequency response of the filter.

Examples:

• box average: low-pass but with oscillatory side lobes;
• Gaussian: smooth low-pass response;
• derivative: high-pass behavior in the derivative direction;
• Laplacian: amplifies high frequencies isotropically;
• sharpening: boosts high-frequency components while preserving low frequencies.

This interpretation explains why smoothing removes noise and why derivative filters are noise-sensitive.

7.27 6.26 Stability and Operator Norms

Since convolution is linear, its stability can be measured by an operator norm. For vectorized images,

\[ \|A_Kx\|_2\le \|A_K\|_2\|x\|_2. \]

For periodic convolution, Fourier modes diagonalize the operator, and the spectral norm is

\[ \|A_K\|_2 =\max_\omega |\widehat K(\omega)|. \]

A smoothing filter usually has frequency response bounded by \(1\), so it does not amplify energy. A derivative or sharpening filter may have larger high-frequency gain, so it can amplify noise.

Another useful bound follows from Young’s inequality for discrete convolution:

\[ \|K*I\|_2\le \|K\|_1\|I\|_2, \]

where

\[ \|K\|_1=\sum_{a,b}|K[a,b]|. \]

This helps explain why kernel normalization affects numerical stability.

7.28 6.27 Implementation Details That Matter

In practical computer vision, small implementation choices can change results.

Important choices include:

1. whether the operation is convolution or cross-correlation;
2. whether the kernel is normalized;
3. whether the image is stored as integer or floating-point values;
4. how boundaries are handled;
5. whether color channels are filtered independently or jointly;
6. whether the image is gamma-compressed or linearized;
7. whether filtering happens before or after resizing;
8. whether downsampling is preceded by antialiasing;
9. whether output values are clipped.

For mathematical reasoning, always specify the domain, codomain, kernel, boundary convention, and normalization.

7.29 6.28 Python Example: Basic Filtering

The following Python code creates a synthetic image, adds noise, and applies several filters.

import numpy as np
import matplotlib.pyplot as plt
from scipy.ndimage import convolve, gaussian_filter, sobel, laplace

rng = np.random.default_rng(7243)

H, W = 128, 128
y, x = np.mgrid[0:H, 0:W]
image = np.zeros((H, W), dtype=float)
image += 0.7 * ((x - 64)**2 + (y - 64)**2 < 28**2)
image += 0.3 * (x / W)
image += 0.2 * np.sin(2 * np.pi * x / 16)

noisy = image + 0.25 * rng.normal(size=(H, W))

box = np.ones((5, 5)) / 25
box_smooth = convolve(noisy, box, mode="reflect")
gauss_smooth = gaussian_filter(noisy, sigma=2.0, mode="reflect")
sobel_mag = np.hypot(sobel(gauss_smooth, axis=1), sobel(gauss_smooth, axis=0))
laplacian = laplace(gauss_smooth, mode="reflect")

fig, axes = plt.subplots(1, 5, figsize=(14, 3))
for ax, arr, title in zip(
    axes,
    [image, noisy, box_smooth, gauss_smooth, sobel_mag],
    ["clean", "noisy", "box smooth", "Gaussian smooth", "Sobel magnitude"]
):
    ax.imshow(arr, cmap="gray")
    ax.set_title(title)
    ax.axis("off")
plt.tight_layout()
plt.show()

7.29.1 What to observe

• The noisy image has high-frequency variation.
• Box smoothing removes noise but may create block-like blur.
• Gaussian smoothing produces smoother behavior.
• Sobel magnitude highlights boundaries but also responds to texture and noise.

7.30 6.29 Python Example: Convolution as Matrix Multiplication

This example constructs a one-dimensional convolution matrix.

import numpy as np

n = 8
kernel = np.array([1, 2, 1], dtype=float) / 4

A = np.zeros((n, n))
for i in range(n):
    for offset, weight in zip([-1, 0, 1], kernel):
        j = i + offset
        if 0 <= j < n:
            A[i, j] += weight

x = np.arange(n, dtype=float)
y_matrix = A @ x

print("Convolution matrix:")
print(np.round(A, 2))
print("Input:", x)
print("Output:", np.round(y_matrix, 2))

This matrix view is useful for connecting convolution with linear algebra, spectral theory, inverse problems, and numerical stability.

7.31 6.30 Python Example: Bias-Variance Tradeoff in Smoothing

import numpy as np
from scipy.ndimage import gaussian_filter

rng = np.random.default_rng(7243)
H, W = 128, 128
y, x = np.mgrid[0:H, 0:W]
truth = ((x - 64)**2 + (y - 64)**2 < 28**2).astype(float)

sigma_noise = 0.4
scales = [0.5, 1.0, 2.0, 4.0]
trials = 200

for scale in scales:
    estimates = []
    for _ in range(trials):
        noisy = truth + sigma_noise * rng.normal(size=truth.shape)
        estimates.append(gaussian_filter(noisy, sigma=scale, mode="reflect"))
    estimates = np.stack(estimates)
    mean_est = estimates.mean(axis=0)
    variance = estimates.var(axis=0).mean()
    bias2 = ((mean_est - truth)**2).mean()
    mse = ((estimates - truth)**2).mean()
    print(f"scale={scale:3.1f}: bias^2={bias2:.4f}, variance={variance:.4f}, mse={mse:.4f}")

A larger scale should usually reduce variance but increase squared bias near edges.

7.32 6.31 Python Example: CNN Convolution Layer

The following TensorFlow example creates a small convolutional layer. The layer learns multiple local filters from data.

import tensorflow as tf

# A batch of 8 RGB images of size 64 x 64.
x = tf.random.normal((8, 64, 64, 3))

conv = tf.keras.layers.Conv2D(
    filters=16,
    kernel_size=3,
    strides=1,
    padding="same",
    activation="relu"
)

y = conv(x)

print("input shape:", x.shape)
print("output shape:", y.shape)
print("kernel shape:", conv.kernel.shape)
print("bias shape:", conv.bias.shape)

The kernel shape is

\[ 3\times3\times3\times16. \]

This means each of the \(16\) output channels has a \(3\times3\) spatial kernel for each of the \(3\) input color channels.

7.33 6.32 AI Component: Using AI to Study Filters Carefully

Large language models and multimodal AI systems can help students explore filters, but the mathematical definitions must remain explicit. Useful prompts include:

TipAI-assisted study prompts

1. Explain why convolution is linear and translation equivariant. Give a proof using summation notation.
2. Compare convolution and cross-correlation. Construct a nonsymmetric kernel where they produce different signs.
3. Derive the variance reduction formula for a normalized averaging filter under independent Gaussian noise.
4. Explain why Gaussian filtering is connected to the heat equation.
5. Write Python code to compare box smoothing, Gaussian smoothing, median filtering, and bilateral filtering on the same noisy image.
6. Given a kernel, decide whether it is smoothing, sharpening, derivative-like, or edge-detecting. Justify using the sum of weights and sign pattern.
7. Explain how a CNN convolution layer generalizes classical convolution to multi-channel learned filters.

Students should ask AI tools to show assumptions. For example, variance calculations require assumptions about independence and equal variance. Translation equivariance may fail near boundaries depending on padding.

7.34 6.33 Common Mistakes

1. Confusing convolution and cross-correlation. Many libraries implement cross-correlation but call it convolution.
2. Ignoring boundary conditions. Padding changes the operator.
3. Filtering integer images without conversion. Integer clipping can distort results.
4. Using derivative filters without smoothing. Derivatives amplify noise.
5. Assuming smoothing always improves an image. Smoothing reduces variance but increases bias.
6. Interpreting edge maps as object boundaries. Edges are local intensity changes, not necessarily semantic boundaries.
7. Forgetting channel mixing. CNN kernels combine spatial and channel dimensions.
8. Downsampling without antialiasing. High frequencies can fold into low frequencies.

7.35 6.34 Mini-Project: Filter Design for a Noisy Image

Design a complete small experiment.

1. Generate a synthetic image with smooth regions, edges, and texture.
2. Add Gaussian noise and salt-and-pepper noise.
3. Compare box, Gaussian, median, Sobel, Laplacian, and unsharp masking filters.
4. Compute quantitative metrics such as MSE and PSNR when the ground truth is known.
5. Visualize the filters and outputs.
6. Explain each result using bias, variance, frequency response, and edge behavior.
7. Write a short paragraph comparing classical filters with a learned CNN first layer.

7.36 6.35 Exercises

7.36.1 Conceptual Exercises

1. Explain why local operators are useful for images.
2. Give an example of a local nonlinear operator.
3. Explain the difference between equivariance and invariance.
4. Why are Gaussian filters usually preferred over box filters?
5. Why do derivative filters amplify noise?
6. Why is boundary handling mathematically part of the definition of a filter?

7.36.2 Mathematical Exercises

1. Prove that convolution is linear.
2. Prove that convolution is translation equivariant under periodic boundary conditions.
3. Let \(K\) be a normalized filter with independent noise variance \(\sigma^2\). Derive the output noise variance.
4. Show that the Sobel filter \(S_x\) is separable.
5. Compute the response of the Laplacian kernel to a constant image.
6. For a one-dimensional three-point averaging filter, construct the corresponding matrix for \(n=5\) with zero boundary conditions.
7. Derive the output size formula for one-dimensional convolution with padding, stride, and kernel size.
8. For stacked \(L\) layers of \(3\times3\) stride-one convolution, prove that the receptive field size is \((2L+1)\times(2L+1)\).

7.36.3 Python Exercises

1. Implement two-dimensional convolution from scratch using nested loops.
2. Compare zero, reflection, replicate, and periodic boundary conditions on the same image.
3. Apply Gaussian filters with several scales and plot MSE against scale.
4. Implement Sobel edge detection and compare it with finite-difference gradients.
5. Implement unsharp masking and study the effect of the sharpening parameter \(\alpha\).
6. Visualize the Fourier magnitude of smoothing, derivative, and sharpening kernels.
7. Build a simple TensorFlow model with one convolutional layer and inspect the learned kernels after training on a small dataset.

7.36.4 AI-Assisted Exercises

1. Ask an AI tool to explain convolution and cross-correlation. Then identify any missing assumptions or convention choices.
2. Ask an AI tool to generate a filtering experiment. Check whether the code specifies boundary conditions.
3. Ask an AI tool to derive the bias-variance formula for smoothing. Verify each step.
4. Ask an AI tool to compare classical Sobel filters with learned CNN filters. Rewrite the answer using precise mathematical notation.

7.37 6.36 Summary

This chapter developed convolution, filtering, and local operators as mathematical tools for computer vision. The main ideas are:

• local operators use neighborhoods around each pixel;
• linear local operators are weighted sums over patches;
• convolution is linear and translation equivariant;
• boundary conditions define the operator near image borders;
• averaging and Gaussian filters reduce noise but blur edges;
• derivative filters detect change but amplify noise;
• the Laplacian and Difference of Gaussians detect second-order structure and scale-dependent patterns;
• filtering can be analyzed statistically through bias and variance;
• separability reduces computational cost;
• CNN convolution layers are learned multi-channel local filters.

The next chapter uses these tools to study edges, corners, and local features. In that setting, convolution filters become building blocks for detecting stable geometric structures in images.

7.38 Notes and References

Classical filtering, scale space, edges, and image operators are standard topics in computer vision and digital image processing; see Szeliski (2022) and Gonzalez and Woods (2018). The convolutional neural network viewpoint connects this chapter with early deep vision systems such as LeCun et al. (1998) and later large-scale CNN systems such as Krizhevsky et al. (2012).

Gonzalez, Rafael C., and Richard E. Woods. 2018. Digital Image Processing. 4th ed. Pearson.

Krizhevsky, Alex, Ilya Sutskever, and Geoffrey E. Hinton. 2012. “ImageNet Classification with Deep Convolutional Neural Networks.” Advances in Neural Information Processing Systems.

LeCun, Yann, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998. “Gradient-Based Learning Applied to Document Recognition.” Proceedings of the IEEE 86: 2278–324.

Szeliski, Richard. 2022. Computer Vision: Algorithms and Applications. 2nd ed. Springer. https://szeliski.org/Book/.