Fun with Filters and Frequencies · CS 180 Project 2

Convolution from scratch

Convolution with just numpy, compared to scipy.

Both functions flip the kernel, pad with zeros and return an image the same size as the input. conv4 uses four loops. conv2 loops over pixels and multiplies the whole window at once.

For even kernels like [1, −1] the extra padding goes on the left (or top). That matches scipy's “same” mode.

def pad_zeros(im, top, bottom, left, right): r, c = im.shape nr = r + top + bottom nc = c + left + right zero_pad = np.zeros((nr, nc)) zero_pad[top:top + r, left:left + c] = im return zero_pad def conv4(im, k): # flip k, zero pad so the output is the same size as im k = k[::-1, ::-1] kh, kw = k.shape pt, pl = kh // 2, kw // 2 p = pad_zeros(im, pt, kh - 1 - pt, pl, kw - 1 - pl) r, c = im.shape out = np.zeros((r, c)) for i in range(r): for j in range(c): total = 0.0 for u in range(kh): for v in range(kw): total += p[i + u, j + v] * k[u, v] out[i, j] = total return out def conv2(im, k): k = k[::-1, ::-1] kh, kw = k.shape pt, pl = kh // 2, kw // 2 p = pad_zeros(im, pt, kh - 1 - pt, pl, kw - 1 - pl) r, c = im.shape out = np.zeros((r, c)) for i in range(r): for j in range(c): out[i, j] = np.sum(p[i:i + kh, j:j + kw] * k) return out

Both match convolve2d(mode="same") to within 2e-15.

Filter	conv4	conv2	scipy
9 × 9 box	1.22 s	0.144 s	0.008 s
D_x = [1, −1]	0.045 s	0.143 s	0.0007 s
D_y = [1, −1]^T	0.047 s	0.143 s	0.0008 s

scipy is much faster since it's compiled. conv4 is slowest on the 9 × 9 box (81 multiplies per pixel), but on the 2-tap filters it beats conv2, because conv2 makes a numpy call at every pixel.

Zero padding makes the border of the blurred image dark. scipy does the same thing by default. With boundary="symm" it mirrors the edge instead and the dark border goes away. I use mirroring after this part.

Grayscale picture of me — Me, grayscale.

Me blurred with a 9 by 9 box filter, dark border from zero padding — 9 × 9 box, zero padding

Me blurred with a 9 by 9 box filter with mirrored edges — 9 × 9 box, mirrored edges

Me convolved with Dx, vertical edges — D_x

Me convolved with Dy, horizontal edges — D_y

Finite difference operator

Derivatives, gradient magnitude and edges on the cameraman.

Cameraman convolved with Dx — ∂/∂x (D_x)

Cameraman convolved with Dy — ∂/∂y (D_y)

Gradient magnitude of the cameraman — Gradient magnitude

Edges: gradient magnitude above 0.2 — Edges, threshold 0.2

D_x = [1, −1] and D_y is its transpose. The gradient magnitude is sqrt(g_x² + g_y²) at each pixel.

I tried a few thresholds. 0.1 picks up the grass and 0.3 loses parts of the tripod and buildings. I went with 0.2, which leaves a little noise in the grass but keeps the real edges.

The cameraman png has a white border that shows up as an edge, so I crop it first.

Edges at threshold 0.1, noisy grass — 0.1

Edges at threshold 0.3, broken tripod legs — 0.3

Derivative of Gaussian

Blur first, then take derivatives.

G is 13 × 13 with σ = 2, made from cv2.getGaussianKernel(13, 2) times its transpose.

Cameraman blurred with the Gaussian — Blurred with G

Blurred cameraman convolved with Dx — Blurred, then D_x

Blurred cameraman convolved with Dy — Blurred, then D_y

Gradient magnitude of the blurred cameraman — Gradient magnitude

Derivative of Gaussian filter in x — G * D_x (13 × 14)

Derivative of Gaussian filter in y — G * D_y (14 × 13)

Edges from the DoG magnitude at threshold 0.05 — DoG edges, threshold 0.05

Cameraman convolved with the DoG x filter — One convolution with G * D_x

Cameraman convolved with the DoG y filter — One convolution with G * D_y

Gradient magnitude from the DoG filters — Gradient magnitude, same as above

Compared to 1.2 there's a lot less noise and the edges are thicker. The magnitudes are smaller too, so I lowered the threshold to 0.05.

The DoG filters are G convolved with D_x and D_y. Using them gives the same result as blurring and then differencing (max difference 1e-15 away from the border).

Bells and whistles

Gradient orientation of the cameraman shown as hue, brightness is edge strength — Hue is the gradient direction, brightness is the magnitude.

Color wheel key: hue for each gradient direction — Color key (y points down).

g_x/|g| and g_y/|g| are already cos θ and sin θ, so I didn't need an angle function. I made r, g and b from cos(θ), cos(θ − 120°) and cos(θ − 240°) using the angle addition formula, then converted to HSV and set saturation to 1 and value to the magnitude.

The two sides of each tripod leg get opposite colors since the gradient flips direction.

Sharpening

Unsharp masking.

im − blur is the high frequencies. Adding α times that back sharpens the image. It works as one filter:

im + α(im − im * G) = im * ((1 + α) e − α G)

where e is the unit impulse. I used σ = 2.

Taj Mahal high frequencies — High frequencies

Taj Mahal sharpened with alpha 1 — Sharpened, α = 1

Taj Mahal sharpened with alpha 0.5 — α = 0.5

Taj Mahal sharpened with alpha 2 — α = 2

Taj Mahal sharpened with alpha 4, halos — α = 4

Higher α looks sharper, but at α = 4 there are halos and the sky gets noisy.

For my own image I used an old scan of a portrait of Hong Liangji. Sharpening brings out the lines but also the paper grain.

Soft scan of a portrait of Hong Liangji — Original scan

High frequencies of the portrait scan — High frequencies

Blur, then sharpen

I blurred a sharp photo and then sharpened it again.

Sharp original photo of a building — Original

Blurred photo sharpened with alpha 2 — Sharpened, α = 2

Blurred photo sharpened with alpha 4 — Sharpened, α = 4

Image	Mean \|difference\| from the original
Blurred	0.066
Sharpened, α = 0.5	0.062
Sharpened, α = 1	0.059
Sharpened, α = 2	0.056
Sharpened, α = 4	0.060

The edges come back (roof, windows) but the texture in the trees doesn't, since the blur removed it. α = 2 had the lowest error and α = 4 overshoots.

Hybrid images

High frequencies of one image plus low frequencies of another.

The low pass is a Gaussian blur and the high pass is the image minus the blur.

Derek and Nutmeg

Nutmeg is the high frequency image and Derek is the low. The other way around didn't work, since the cat is mostly fur and whiskers.

Nutmeg the cat, original — Nutmeg (original)

I aligned on the eyes with the starter code. Rotating Nutmeg leaves black corners that show up in the high pass, so I crop both images to where they overlap.

High frequencies of Nutmeg — high_pass(Nutmeg, σ = 4)

Low frequencies of Derek — low_pass(Derek, σ = 10)

Log magnitude FFT of Nutmeg — FFT, Nutmeg

Log magnitude FFT of high-passed Nutmeg — FFT, high-passed Nutmeg

Log magnitude FFT of low-passed Derek — FFT, low-passed Derek

Log magnitude FFT of the hybrid — FFT, hybrid

Low-passed Derek only has energy near the center, and high-passed Nutmeg has the center removed. The cross in each plot comes from the image borders.

A Gaussian's frequency response is exp(−2π²σ²f²), which drops to 1/2 at about f = 0.19/σ. So Derek (σ = 10) keeps below about 0.019 cycles/pixel and Nutmeg (σ = 4) keeps above about 0.047.

The hybrid at full, half, quarter and eighth size — At 1, 1/2, 1/4 and 1/8 size. The cat goes away as it gets smaller.

Mine

Hybrid of me now and me in 2019 — Then and now

Then and now hybrid at shrinking sizes — Close up it's me now, far away it's me in 2019.

The Earth from Apollo 17 — Earth (low, σ = 8)

Hybrid of the Moon and the Earth — Hybrid

The Moon and Earth hybrid in gray — Same hybrid in gray

This one doesn't work as well. You can see the Earth's color up close too. It's better in gray.

Bells and whistles: color

Hybrid with both images in gray — Both gray

Hybrid with color only in the high frequencies — Color in the high frequencies only

Hybrid with color only in the low frequencies — Color in the low frequencies only

Hybrid with color in both — Color in both

Color in the high frequencies barely changes anything. Color in the low frequencies helps the most, especially from far away. I used color for both.

Gaussian and Laplacian stacks

Like pyramids but without downsampling.

Each Gaussian level blurs the one before it, and σ doubles each level (2, 4, 8, 16). With the same σ every level, the levels looked almost the same.

Each Laplacian level is the difference of two Gaussian levels, and the last one is the last Gaussian level, so they add back up to the original (error 1e-16). I stretched the contrast to show them.

Gaussian stack (top) and Laplacian stack (bottom) of the apple, 5 levels — Apple. Top: Gaussian stack. Bottom: Laplacian stack.

Gaussian stack (top) and Laplacian stack (bottom) of the orange, 5 levels — Orange.

Multiresolution blending

Blending each frequency band separately.

I make a Gaussian stack of the mask too. At each level the output is gm·la + (1 − gm)·lb, and then I add up the levels. The fine levels get a sharp seam and the coarse levels get a wide one. 5 levels, σ = 2.

The oraple: apple and orange blended with a vertical seam — The oraple

Recreation of Szeliski figure 3.42: masked Laplacian levels 0, 2 and 4 of the apple, the orange and the blend, and the reconstructions — Szeliski Fig. 3.42 (a) to (l). Rows: levels 0, 2, 4 and the sum. Columns: apple, orange, both.

At level 0 the seam is basically a hard line. At level 4 it's very wide, so the colors fade smoothly.

Earth and Moon

Same seam. I cropped both so the discs line up.

Earth and Moon blended with a vertical seam — Blended

Me on the Moon

Irregular mask around my face. This is my favorite, so here are all the levels (like Figure 10 in the paper).

The irregular mask around my face — Mask

All five masked Laplacian levels for the face and Moon blend, plus the sums — Levels 0 to 4 and the sum. Columns: my face, the Moon, both.

The fine levels only have my features and the mask edge. The coarse levels are blurry enough that the face and the Moon meet without a line.

Bells and whistles: color

For Earth and Moon, color makes it more interesting. For my face, gray looks better because my skin color stands out against the Moon.

What I learned

The biggest thing I learned is that almost everything in this project is just blurring and subtracting. Sharpening adds back what the blur removed. Hybrids take what the blur removed from one image and what it kept from another. A Laplacian stack is blur and subtract over and over. Once I saw it that way, the four parts felt like one idea instead of four.

It also changed how I pick parameters. At first I was guessing σ values. After working out that a Gaussian cuts off around 0.19/σ cycles per pixel, I could think about which frequencies each image keeps. That's why the cat has to be the high frequency image. Almost all of it is fur and whiskers, so there's nothing left of it after a low pass.

A few smaller things surprised me. Convolution is associative, so blurring and then taking a derivative is the same as one convolution with a DoG filter, and I got the same answer to 1e-15. The edges of the image matter more than I expected: zero padding darkens the border, the cameraman's white frame showed up as an edge, and the black corners from rotating Nutmeg showed up in the high pass. And for blending, the mask needs its own stack. With a hard mask at every level you just get a visible line.

Last, color mostly matters in the low frequencies. In the hybrids, color in the high frequencies barely changed anything. In the blends, color could help (Earth and Moon) or hurt (my face on the Moon) depending on whether the two images have similar colors.