Naive (Direct) Image Convolution: Definition, Algorithm, and Cost

This page is a reference explanation of naive (direct) image convolution.
It explains what convolution means, how the naive algorithm implements it, and why its computational cost grows quickly.

Every faster convolution technique makes sense only in comparison to this baseline, so understanding naive convolution is essential.

1. Images as Data, Not Pictures

When we work with images in a program, we are not working with photographs or visuals.
We are working with data.

An image can be modeled as a two-dimensional grid of numbers:

• each position corresponds to a pixel location,
• each value represents the brightness (intensity) at that location.

Mathematically, we can think of an image as a discrete function:

I(x, y)

In a program, this function is stored as a rectangular array of values.
All image processing algorithms operate on this grid.

2. What a Convolution Kernel Represents

A convolution kernel is a small matrix of numbers, typically much smaller than the image itself (for example, 3×3 or 5×5).

Each number in the kernel describes how much influence a nearby pixel should have on the output pixel.

Different kernels encode different local rules:

• blur: nearby pixels should be averaged,
• sharpen: the center pixel should be emphasized,
• edge detection: differences between neighbors should be amplified.

The important idea is this:

The algorithm does not change.
Only the numbers in the kernel change.

3. The Definition of Discrete Convolution

Discrete convolution is defined as a sum of products:

(I * K)(x, y) = Σ Σ I(x + i, y + j) · K(i, j)

This formula says:

• take the kernel,
• align it with the image at position (x, y),
• multiply corresponding entries,
• add the results.

This definition is independent of implementation.
Any correct convolution algorithm must compute values consistent with this definition (up to numerical error).

4. The Naive Algorithm

The naive algorithm implements the definition directly.

For each output pixel:

1. Place the center of the kernel over that pixel.
2. Look at the surrounding pixels covered by the kernel.
3. Multiply each pixel by the corresponding kernel weight.
4. Add all of the products together.
5. Store the result.

This computation is done independently for every pixel in the image.

There is no reuse of work.
There is no memory of previous results.

In pseudocode:

for each pixel (x, y):
    sum = 0
    for each kernel offset (i, j):
        sum += image[x+i][y+j] * kernel[i][j]
    output[x][y] = sum

5. Computational Cost

Let:

• W = image width
• H = image height
• k = kernel width (assume square kernel)

The total number of multiplications is:

W · H · k²

This quadratic dependence on kernel size is the core limitation.

• A 3×3 kernel requires 9 multiplications per pixel.
• A 31×31 kernel requires 961 multiplications per pixel.
• Doubling the kernel size quadruples the work.

For large kernels, naive convolution becomes impractically slow.

6. Why the Naive Algorithm Still Matters

Despite its cost, naive convolution is critically important:

• it exactly matches the mathematical definition,
• it is easy to implement correctly,
• its performance behavior is predictable,
• it provides a trusted reference result.

In performance engineering, you always want a:

simple, obviously correct baseline

Naive convolution is that baseline.

7. What Profiling Reveals

When you profile naive convolution, you should expect to see:

• nearly all runtime spent in tight nested loops,
• very little overhead elsewhere,
• runtime scaling directly with kernel size.

This clarity makes naive convolution the perfect contrast case for FFT-based convolution, which changes the structure of the computation entirely.