Computer vision: A separable Gaussian blur

The Gaussian blur is the standard way to smooth an image before edge detection. Build it from its formula, in two fast passes.

What to build

A program that builds a normalised 1-D Gaussian kernel and applies it horizontally and then vertically.

Requirements

  • The kernel has 2r + 1 weights, exp(−i² / (2σ²)) for i = −r … r, divided by their sum. Print them on the first line with four decimal places.
  • Pass 1: each pixel becomes the sum of weight(i) × pixel(row, column + i). Pass 2 does the same down the columns of the pass-1 result: weight(i) × value(row + i, column).
  • Outside the image, use replicate padding. Print the final image with one decimal place per value.

Input

Line 1: H, W, the radius r and sigma (a decimal number). Then H rows of W values.

Output

The weight line, then H rows.

Constraints

1 ≤ H, W ≤ 30; 1 ≤ r ≤ 5; sigma > 0.

Example

Input:

2 2 1 1
50 50
50 50

Output:

0.2741 0.4519 0.2741
50.0 50.0
50.0 50.0

Why it works

A 2-D Gaussian is the product of two 1-D Gaussians, so two 1-D passes give the same result as one 2-D pass with far fewer multiplications; normalising keeps flat areas unchanged.

Examples

Example 1 · Input
2 2 1 1
50 50
50 50
Expected output
0.2741 0.4519 0.2741
50.0 50.0
50.0 50.0
Example 2 · Input
1 3 1 1
0 100 0
Expected output
0.2741 0.4519 0.2741
27.4 45.2 27.4

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

The weights are `math.exp(-(i * i) / (2 * sigma * sigma))` for i from −r to r; divide each by their sum.

Hint 2

Blur every row first (clamping column indices), then blur every column of that result (clamping row indices). Keep floats until printing.

Solution

Show one correct solution (try it yourself first)
import math

h, w, r, sigma = input().split()
h, w, r, sigma = int(h), int(w), int(r), float(sigma)
img = [list(map(float, input().split())) for _ in range(h)]
weights = [math.exp(-(i * i) / (2 * sigma * sigma)) for i in range(-r, r + 1)]
total = sum(weights)
weights = [x / total for x in weights]
print(" ".join(f"{x:.4f}" for x in weights))


def clamp(i, n):
    return min(max(i, 0), n - 1)


across = [[sum(weights[i + r] * row[clamp(c + i, w)] for i in range(-r, r + 1)) for c in range(w)] for row in img]
down = [[sum(weights[i + r] * across[clamp(y + i, h)][c] for i in range(-r, r + 1)) for c in range(w)] for y in range(h)]
for row in down:
    print(" ".join(f"{v:.1f}" for v in row))

Lesson: Blurring and noise removal →