Borders, Separability & Performance

"Everything was going wonderfully until I reached the edge of the image, at which point I was asked to summarize pixels that do not exist. I have been improvising ever since, and some of my best work is out there."

A Convolution Kernel With Boundary Issues

The previous sections treated filtering mathematically, on images that conveniently extended forever in all directions. Real images stop. And real systems have frame budgets. This closing section pays the chapter's two deferred debts, and in settling them connects hand-designed filtering to how deep learning frameworks implement the very same operation at scale.

1. The Border Problem Beginner

Center a $k \times k$ kernel on a pixel in the top row and $\lfloor k/2 \rfloor$ of its rows dangle above the image, referencing pixels that do not exist. Exactly two honest responses exist. The first: refuse to compute those outputs, producing a result smaller than the input by $k - 1$ in each dimension ("valid" convolution; this is why un-padded CNN feature maps shrink layer by layer). The second: invent the missing pixels by padding, and the inventing policy matters far more than beginners expect. Figure 3.6.1 shows the five standard policies extending the same row.

Each policy fails somewhere specific. Constant (zero) padding surrounds the image with blackness, so any smoothing filter darkens the frame's rim, a vignette artifact visible in careless thumbnail pipelines, and any derivative filter from Section 3.4 hallucinates a strong edge along the entire border. Replicate is safe and bland; it slightly overweights edge pixels. Reflect and reflect_101 continue local statistics most gracefully, which is why reflect_101 is OpenCV's default (cv2.BORDER_REFLECT_101, alias BORDER_DEFAULT); the difference between them, whether the edge pixel itself is duplicated, matters mainly for derivative filters, where the doubled pixel of plain reflect creates a spurious zero-gradient line. Wrap is correct exactly when the data is periodic, which sounds exotic until Chapter 4: FFT-based convolution wraps implicitly, whether you wanted it to or not, and that quietly mandatory wrap is one of that chapter's central gotchas.

The NumPy and OpenCV vocabularies for identical policies differ, and one mismatch is a recurring source of off-by-the-border bugs: NumPy's mode="reflect" equals OpenCV's BORDER_REFLECT_101, while NumPy's mode="symmetric" equals OpenCV's BORDER_REFLECT. The demonstration below makes the policies tangible on a tiny array, and is worth running once just to fix Figure 3.6.1 in memory.

import numpy as np

row = np.array([10, 20, 30, 40, 50, 60])

print(np.pad(row, 3, mode="constant"))   # [ 0  0  0 10 20 30 40 50 60  0  0  0]
print(np.pad(row, 3, mode="edge"))       # [10 10 10 10 20 30 40 50 60 60 60 60]
print(np.pad(row, 3, mode="symmetric"))  # [30 20 10 10 20 30 40 50 60 60 50 40]
print(np.pad(row, 3, mode="reflect"))    # [40 30 20 10 20 30 40 50 60 50 40 30]
print(np.pad(row, 3, mode="wrap"))       # [40 50 60 10 20 30 40 50 60 10 20 30]

# Naming trap: np "reflect" == cv2.BORDER_REFLECT_101 (edge pixel NOT doubled)
#              np "symmetric" == cv2.BORDER_REFLECT  (edge pixel doubled)

2. Separability: The Free Order of Magnitude Intermediate

A 2D kernel $K$ is separable if it factors into an outer product of a column and a row, $K = v\,h^\top$. When it does, the associativity of convolution from Section 3.1 lets the single 2D pass split into two 1D passes (filter rows with $h$, then columns with $v$), and the per-pixel cost falls from $k^2$ multiplications to $2k$:

$$ K * I = (v\,h^\top) * I = v * (h^\top * I) \qquad \Rightarrow \qquad \frac{k^2}{2k} = \frac{k}{2}\times \text{ speedup} $$

For a $15 \times 15$ Gaussian that ratio is 7.5x; for the $31 \times 31$ kernels of the large-kernel renaissance it is 15.5x. The chapter's roster of separable kernels is no accident: the Gaussian of Section 3.2 (the only rotationally symmetric separable filter), the box, and the Sobel of Section 3.4, whose $[1\;2\;1]^\top [-1\;0\;1]$ factorization we met explicitly. The Laplacian and the LoG are not separable, one reason the DoG approximation (a difference of two separable Gaussians) wins in practice.

Linear algebra hands us both a test and a recipe. The outer product $v h^\top$ has rank 1, so a kernel is separable exactly when its matrix rank is 1, and the SVD both checks this and produces the factors:

import numpy as np

def separate_kernel(K, tol=1e-6):
    """If K is rank-1 (separable), return (v, h) with K = outer(v, h)."""
    U, S, Vt = np.linalg.svd(K)
    if S[1] / S[0] > tol:
        return None                      # rank > 1: not separable
    v = U[:, 0] * np.sqrt(S[0])          # column factor
    h = Vt[0, :] * np.sqrt(S[0])         # row factor
    return v, h

sobel_x = np.array([[-1., 0., 1.],
                    [-2., 0., 2.],
                    [-1., 0., 1.]])
v, h = separate_kernel(sobel_x)
print(np.round(v, 3), np.round(h, 3))
# [-0.76  -1.521 -0.76 ] [ 1.316 -0.    -1.316]
# (= [1,2,1] x [-1,0,1] up to sign and scale; only the product is unique)
print(np.allclose(np.outer(v, h), sobel_x))       # True

laplacian = np.array([[0., 1., 0.], [1., -4., 1.], [0., 1., 0.]])
print(separate_kernel(laplacian))                  # None: rank 2, not separable

The payoff is measurable in three lines of timing. OpenCV exposes the two-pass path as cv2.sepFilter2D, and cv2.GaussianBlur uses it internally, which is why the library shortcut in Section 3.2 advertised separability as something you get without asking.

import cv2, numpy as np, time

img = np.random.rand(1080, 1920).astype(np.float32)   # one 1080p frame
g = cv2.getGaussianKernel(31, 5.0)                     # 31-tap 1D Gaussian
G2 = g @ g.T                                           # full 31x31 2D kernel

def clock(fn, reps=20):
    t0 = time.perf_counter()
    for _ in range(reps): fn()
    return (time.perf_counter() - t0) / reps * 1000    # ms per call

t_full = clock(lambda: cv2.filter2D(img, -1, G2))
t_sep  = clock(lambda: cv2.sepFilter2D(img, -1, g, g))
print(f"full 2D: {t_full:.1f} ms   separable: {t_sep:.1f} ms   "
      f"speedup: {t_full / t_sep:.1f}x")
# Representative output (4-core laptop):
# full 2D: 38.4 ms   separable: 4.9 ms   speedup: 7.8x

3. Counting Operations: Direct, Separable, FFT Intermediate

For an $N$-pixel image and a $k \times k$ kernel, the three families of convolution algorithm scale differently, and Table 3.6.1 puts numbers on a 1080p frame ($N \approx 2.07$ million pixels) to make the asymptotics concrete.

Read the last column as a decision procedure. Small kernels: direct convolution, which modern SIMD hardware chews through with excellent cache behavior. Separable kernels of any size: two-pass, almost always optimal. Large inseparable kernels: transform to the frequency domain, multiply, transform back, at a cost that is independent of kernel size. The mathematics licensing that third route is the convolution theorem, the headline result of Chapter 4; OpenCV's filter2D already switches to it silently for kernels above roughly $11 \times 11$, so you have likely used FFT convolution without knowing. (Mind the implicit wrap-around border noted in Figure 3.6.1's discussion.)

4. How Production Systems Actually Do It Advanced

Between the textbook loop and the datasheet speed sits a stack of engineering that is worth knowing even when you never write it, because its vocabulary surfaces in profiler output and framework documentation. Four layers do most of the work.

Vectorization and threading. Libraries process 8 to 32 pixels per CPU instruction (SIMD) and split rows across cores: the baseline 100x over interpreted Python that Chapter 0's vectorization discussion promised. Integral images give the box filter (and through it, the guided filter of Section 3.5) a constant cost per pixel at any radius: precompute running sums once, then any rectangle's sum is four lookups. im2col + GEMM: unroll every kernel-sized window into the row of a giant matrix, so convolution becomes one dense matrix multiply, the single most optimized routine in computing. This memory-hungry but blazingly regular formulation is how cuDNN and PyTorch execute the conv layers of Chapter 19 on GPUs, alongside Winograd variants that trade additions for multiplications on $3 \times 3$ kernels. Downsample-filter-upsample: when a huge blur is the goal (backgrounds, bokeh), blur a quarter-resolution copy with a quarter-sized sigma and upsample; the error is invisible and the saving is 16x before any other trick, which is how phone "portrait mode" affords its giant background blurs.