Convolution: Learning Local Patterns

Imaging your grandpa is reading a newspaper by using a magnifier. Every time he could only read parts of the newspaper and the size of the magnifier decides how many he could read at a time. Convolution is similar to that.

Convolution is one of the foundational operations in computer vision. It allows a neural network to examine small local regions of an input, detect useful patterns, and reuse the same detector at different positions.

Before studying convolution on images, it helps to begin with the simpler one-dimensional case.

1-D Convolution

For a one-dimensional input (x) and a kernel or filter (w) of length (K), the output at position (i) is commonly computed in deep-learning libraries as:

Technically, this operation is cross-correlation, because the kernel is used in its original order.

In strict mathematical convolution, the kernel is reversed. However, in computer vision and deep learning, cross-correlation is commonly called convolution.

The practical distinction rarely causes a problem because the kernel values are learned during training. If reversing the kernel would be useful, the network can learn the corresponding reversed values.

Key idea: In deep-learning convolution, the kernel slides across the input without being reversed.

A Simple 1-D Example

Consider the input:

and the kernel:

The kernel has length three, so it examines three neighboring input values at a time.

At the first position:

At the second position:

At the third position:

At the last position:

Therefore:

The same three kernel weights are reused at every valid position.

The Kernel Slides Across the Input

At each step, the kernel:

1. selects a small local region,
2. multiplies each selected value by the corresponding kernel weight,
3. adds the products, and
4. writes the result into the output.

For a length-three kernel:

Notice that adjacent outputs examine overlapping input regions.

Convolution as Sparse Connectivity

A fully connected layer connects every output neuron to every input value. Convolution uses only local connections.

The previous operation can be written as a matrix multiplication:

Each output connects to only three nearby input values, shown by the nonzero entries in its row. The zeros represent missing connections.

This is called sparse connectivity.

The matrix also reveals another important property: the same values (w[0]), (w[1]), and (w[2]) are repeated in every row.

This is called weight sharing.

Together, sparse connectivity and weight sharing allow convolution to use far fewer parameters than a fully connected layer.

Receptive Field

The portion of the input used to calculate one output value is called its receptive field.

With a kernel of length three, every output value has a local receptive field containing three input values.

For example:

An individual output cannot directly see the entire input. It sees only the region covered by the kernel at that position.

When multiple convolutional layers are stacked, deeper outputs indirectly receive information from progressively larger regions.

Number of outputs

If input size is $N$ and filter size is $K$:

where:

$N$ is the input size.

$K$ is the filter size.

2-D Convolution

Images are arranged in two spatial dimensions: height and width. Therefore, computer vision commonly uses two-dimensional kernels.

Consider a grayscale image represented by an input matrix (X) and a two-dimensional kernel (W) with height (K_h) and width (K_w).

The output at location ((i,j)) is:

The kernel slides both horizontally and vertically across the image.

At each location, the model:

1. places the kernel over a local image patch,
2. performs element-wise multiplication,
3. adds all the products, and
4. stores the result in the output feature map.

A Simple 2-D Example

Consider this $4 \times 4$ input:

and this $2 \times 2$ kernel:

At the top-left position, the kernel covers:

The corresponding output value is:

The kernel then moves to the next position and repeats the same calculation using the same four weights.

What Does a Kernel Detect?

A kernel responds strongly when the local input patch matches the pattern represented by its weights.

Different kernels can respond to different visual features, such as:

• vertical edges,
• horizontal edges,
• diagonal edges,
• corners,
• color transitions, and
• textures.

During training, a CNN usually learns useful kernel values automatically through backpropagation. We do not normally specify the final filters by hand.

A kernel is a small, reusable pattern detector.

The Feature Map

The matrix produced by sliding one kernel across an image is called a feature map or activation map.

Each value in the feature map indicates how strongly the kernel responded at a particular spatial location.

If a kernel detects vertical edges, then regions containing strong vertical transitions may produce large activations.

Because the same kernel is applied throughout the image, the same feature can be detected at different positions.

Convolution on an RGB Image

A grayscale image has one channel, while an RGB image has three:

Therefore, an RGB image has the shape:

A convolutional filter must cover all the input channels. For example, if the filter has a spatial size of (3 \times 3), its complete shape is:

The filter contains one $3 \times 3$ set of weights for each RGB channel.

At a particular image location:

1. The filter examines a $3 \times 3$ region from the red channel.
2. It examines the corresponding region from the green channel.
3. It examines the corresponding region from the blue channel.
4. The results from all three channels are added together.
5. A bias is added to produce one output value.

The operation can be written as:

As the filter moves across the image, it produces a two-dimensional matrix of values called a feature map.

One filter covering all input channels produces one feature map.