C++: convolution with zero padding

Apply a Laplacian kernel so the output has the same size as the input and responds to a single bright pixel.

C++

#include <iomanip>
#include <iostream>
#include <vector>

int main() {
  const int n = 5;
  std::vector<std::vector<int>> image(n, std::vector<int>(n, 0));
  image[2][2] = 10;
  int kernel[3][3] = {{0, 1, 0}, {1, -4, 1}, {0, 1, 0}};

  std::vector<std::vector<int>> out(n, std::vector<int>(n, 0));
  for (int r = 0; r < n; ++r) {
    for (int c = 0; c < n; ++c) {
      int sum = 0;
      for (int kr = -1; kr <= 1; ++kr) {
        for (int kc = -1; kc <= 1; ++kc) {
          int rr = r + kr, cc = c + kc;
          if (rr >= 0 && rr < n && cc >= 0 && cc < n) {
            sum += image[rr][cc] * kernel[kr + 1][kc + 1];
          }
        }
      }
      out[r][c] = sum;
    }
  }
  for (const auto& row : out) {
    for (int v : row) {
      std::cout << std::setw(4) << v;
    }
    std::cout << "\n";
  }
}

Output

   0   0   0   0   0
   0   0  10   0   0
   0  10 -40  10   0
   0   0  10   0   0
   0   0   0   0   0

Explanation

A convolution output is smaller than the input if the kernel is only applied where it fits entirely inside the image. To keep the output the same size, the image is padded: pixels outside the border are treated as zero. Each output pixel is the sum of the neighbourhood multiplied by the kernel.

The Laplacian kernel has −4 at the centre and 1 at the four neighbours. It measures how different a pixel is from its neighbours, so it responds to isolated points and edges and gives zero on flat regions. A single bright pixel produces −40 at its own position and 10 at each neighbour.

Explore the dry run

Guided walkthroughReady

1#include <iomanip>

2#include <iostream>

3#include <vector>

5int main() {

6 const int n = 5;

7 std::vector<std::vector<int>> image(n, std::vector<int>(n, 0));

8 image[2][2] = 10;

9 int kernel[3][3] = {{0, 1, 0}, {1, -4, 1}, {0, 1, 0}};

11 std::vector<std::vector<int>> out(n, std::vector<int>(n, 0));

12 for (int r = 0; r < n; ++r) {

13 for (int c = 0; c < n; ++c) {

14 int sum = 0;

15 for (int kr = -1; kr <= 1; ++kr) {

16 for (int kc = -1; kc <= 1; ++kc) {

17 int rr = r + kr, cc = c + kc;

18 if (rr >= 0 && rr < n && cc >= 0 && cc < n) {

19 sum += image[rr][cc] * kernel[kr + 1][kc + 1];

20 }

21 }

22 }

23 out[r][c] = sum;

24 }

25 }

26 for (const auto& row : out) {

27 for (int v : row) {

28 std::cout << std::setw(4) << v;

29 }

30 std::cout << "\n";

31 }

32}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A single bright pixel in the middle of a black 5×5 image.	`image has one non-zero pixel`	—
Pixels outside the image count as zero, so skip them.	`image has one non-zero pixel`	—
Multiply each neighbour by its kernel weight and accumulate.	`centre: -4 × 10 = -40`	—
The response is −40 at the pixel and +10 at its four neighbours; flat areas give 0.	`centre: -4 × 10 = -40`	0 0 0 0 0 0 0 10 0 0 0 10 -40 10 0 0 0 10 0 0 0 0 0 0 0

Cost and common mistakes

O(R·C·k²) for an R×C image and k×k kernel.

Real libraries flip the kernel for true convolution, but the Laplacian is symmetric so flipping changes nothing.
Zero padding creates artificial edges at the border. Reflection or replication padding often works better.
Laplacian filters amplify noise, so images are usually smoothed first.

Try it yourself

What would the output be for a uniform image of all 5s?

Reveal answer and reasoning

Interior pixels give 0, because 4·5 − 4·5 = 0. Border pixels are non-zero because the missing neighbours are treated as zeros.

C++: convolution with zero padding

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading