import numpy as np
def out_size(n, k, p=0, s=1):
return (n + 2 * p - k) // s + 1
img = np.arange(1, 65, dtype=float).reshape(8, 8)
k = np.ones((3, 3)) / 9
def convolve(a, kern, stride, pad=0):
if pad:
a = np.pad(a, pad, mode="constant")
kh = kern.shape[0]
oh = (a.shape[0] - kh) // stride + 1
ow = (a.shape[1] - kh) // stride + 1
out = np.zeros((oh, ow))
where = []
for i in range(oh):
for j in range(ow):
r, c = i * stride, j * stride
out[i, j] = (a[r:r + kh, c:c + kh] * kern).sum()
where.append((r, c))
return out, where
print("an 8x8 image, a 3x3 kernel. where does the kernel actually land?")
for s in (1, 2, 3):
out, where = convolve(img, k, s)
print()
print(" stride %d -> output %dx%d, %d positions" % (s, out.shape[0], out.shape[1], len(where)))
grid = [["." for _ in range(8)] for _ in range(8)]
for (r, c) in where:
grid[r + 1][c + 1] = "x" # mark the kernel CENTRE
for row in grid:
print(" " + " ".join(row))
print()
print(" 'x' marks a pixel the kernel was centred on. at stride 2 half the")
print(" positions are skipped; at stride 3, two thirds.")
print()
print("THE ARITHMETIC. output size and cost against stride:")
print("%8s %14s %18s %14s" % ("stride", "output (224 in)", "multiply-adds", "relative"))
base = None
for s in (1, 2, 3, 4):
o = out_size(224, 3, 1, s)
macs = o * o * 3 * 3 * 64 * 64 # a 64->64 channel layer
base = base or macs
print("%8d %14s %18s %13.2fx"
% (s, "%dx%d" % (o, o), "{:,}".format(macs), macs / base))
print(" stride 2 quarters the compute, because it quarters the number of")
print(" output positions. that is the reason it is used.")
print()
print("WHAT IT COSTS. first, the part people get wrong: at stride 2 with a")
print("3x3 kernel, NO pixel is skipped. the windows still overlap, because")
print("the kernel is wider than the step:")
fine = np.zeros((8, 8))
fine[3, 4] = 100.0
for s in (1, 2, 3, 4):
out, _ = convolve(fine, k, s)
seen = "read %d time(s)" % int(round(out.sum() / 11.11)) if out.max() > 0 else "NEVER READ"
print(" stride %d (kernel 3): a single bright pixel is %s" % (s, seen))
print(" a pixel is only missed when the stride EXCEEDS the kernel width.")
print(" at stride 4 with a 3x3 kernel there are gaps the kernel never")
print(" covers, and whatever sits in them is invisible to that layer.")
print()
print(" what a stride costs at 2 and 3 is not coverage but RESOLUTION.")
print(" two nearby details land in the same output cell and can no longer")
print(" be told apart:")
two = np.zeros((8, 8))
two[3, 2] = 100.0
two[3, 3] = 100.0
for s in (1, 2):
out, _ = convolve(two, k, s)
hits = int((out > 1).sum())
print(" stride %d: two adjacent details produce %d distinct non-zero"
% (s, hits))
print(" output cells" if s == 1 else " output cells -- fewer places to distinguish them")
print()
detail = np.zeros((8, 8))
detail[1::2, 1::2] = 100.0 # a fine checkerboard
print(" and a repeating fine pattern can vanish entirely. a checkerboard")
print(" with period 2, sampled at stride 2:")
for s in (1, 2):
out, _ = convolve(detail, np.array([[1.0]]), s)
print(" stride %d: output values %s"
% (s, np.unique(out)[:4]))
print(" at stride 2 every sample lands on the same phase, so a pattern")
print(" that alternates looks constant. that is ALIASING, and it is why")
print(" you blur before downsampling rather than after.")
print()
print("STRIDED CONVOLUTION vs POOLING -- two ways to halve a feature map:")
rows = [("what it is", "a learned kernel, applied every s pixels",
"a fixed rule over each window"),
("parameters", "yes -- the kernel", "none"),
("can it adapt", "yes, it is trained", "no"),
("overlaps", "only if s < k", "usually not (2x2, stride 2)"),
("used in", "modern nets, GANs, autoencoders", "classic CNNs")]
print("%16s %42s %30s" % ("", "strided conv", "max pooling"))
for a, b, c in rows:
print("%16s %42s %30s" % (a, b, c))
print()
print("both discard three quarters of the positions. the difference is")
print("whether the network gets to choose what survives.")
print()
print("AND THE TRANSPOSED DIRECTION. a stride above 1 in a normal")
print("convolution shrinks; a stride above 1 in a TRANSPOSED convolution")
print("grows, which is how decoders and generators upsample:")
print("%22s %14s %14s" % ("operation", "input", "output"))
for s in (1, 2, 3):
print("%22s %14s %14s"
% ("conv, stride %d" % s, "16x16",
"%dx%d" % ((out_size(16, 3, 1, s),) * 2)))
for s in (2, 3):
o = (16 - 1) * s + 3 - 2
print("%22s %14s %14s" % ("transposed, stride %d" % s, "16x16", "%dx%d" % (o, o)))
print(" the transposed version is what produces checkerboard artefacts in")
print(" generated images, when the stride and kernel size do not divide")
print(" evenly and some output pixels receive more contributions than")
print(" their neighbours:")
for k_, s_ in ((3, 2), (4, 2), (2, 2)):
print(" kernel %d, stride %d -> %s"
% (k_, s_, "uneven overlap, artefacts likely" if k_ % s_ else "clean"))