Convolution

Matrix computation
Dr. Thanh-Sach LE
LTSACH@hcmut.edu.vn

GVLab: Faculty of Computer Science and Engineering,

Graphics and Vision Laboratory HCMUT
2 Contents
❖ im2col
❖ kernel2row
❖ Notation
❖ Convolution as matrix multiplication
 Convolution
im2col
Dr. Thanh-Sach LE
LTSACH@hcmut.edu.vn

GVLab: Faculty of Computer Science and Engineering,

Graphics and Vision Laboratory HCMUT
4 im2col

• Notation:

X : input image or feature map

𝕏conv : Matrix created by collecting all the values of X corresponding to the

kernel W into columns of 𝕏conv (illustrated in next slide)
∂b

W : Filter’s kernel
5 im2col

x11 x12 x13

w11 w12 w22 w21
x21 x22 x23

x31 x32 x33 w21 w22 w12 w11

0
∂b
X W Rot180 (W)
Input image Filter’s kernel Rotated kernel
 6 im2col
How to create matrix 𝕏conv
w22x11 w21x12 x13

w22 w21
w12x21 w11x22 x23

w12 w11
x31 x32 x33
flattening

0
∂b

Rotate180 (W)
X

x22

x21

x12

x11

𝕏conv
Flattened in the order corresponding to w11, w12, w21, w22
 7 im2col
How to create matrix 𝕏conv
w22x11 w21x12 x13

x11 x12 x13

w12x21 w11x22 x23
x21 x22 x23
x31 x32 x33
flattening

x31 x32 x33

∂b

x22 x22 x23

x21 x21 x22

x12 x12 x13

x11 x11 x12

𝕏conv
Flattened in the order corresponding to w11, w12, w21, w22
 8 im2col
How to create matrix 𝕏conv
w22x11 w21x12 x13

x11 x12 x13 x11 x12 x13

w12x21 w11x22 x23
x21 x22 x23 x21 x22 x23
x31 x32 x33
flattening

x31 x32 x33 x31 x32 x33

∂b

x22 x22 x23 x22 x23 x32

x21 x21 x22 x21 x22 x31

x12 x12 x13 x12 x13 x22

x11 x11 x12 x11 x12 x21

𝕏conv
Flattened in the order corresponding to w11, w12, w21, w22
 9 im2col
How to create matrix 𝕏conv
w22x11 w21x12 x13

x11 x12 x13 x11 x12 x13 x11 x12 x13

w12x21 w11x22 x23
x21 x22 x23 x21 x22 x23 x21 x22 x23
x31 x32 x33
flattening

x31 x32 x33 x31 x32 x33 x31 x32 x33

∂b

x22 x22 x23 x22 x23 x32 x22 x23 x32 x33

x21 x21 x22 x21 x22 x31 x21 x22 x31 x32

x12 x12 x13 x12 x13 x22 x12 x13 x22 x23

x11 x11 x12 x11 x12 x21 x11 x12 x21 x22

𝕏conv
Flattened in the order corresponding to w11, w12, w21, w22
 Convolution
kernel2row
Dr. Thanh-Sach LE
LTSACH@hcmut.edu.vn

GVLab: Faculty of Computer Science and Engineering,

Graphics and Vision Laboratory HCMUT
11 kernel2row

• Notation:

X : input image or feature map

𝕏conv : Matrix created by collecting all the values of X corresponding to the

kernel W into columns of 𝕏conv (illustrated in next slide)
∂b

W : Filter’s kernel

𝕎conv : Matrix created by rearranging values in the kernel into row of a matrix
(illustrated in next slide)
12 kernel2row

x11 x12 x13

w11 w12 w22 w21
x21 x22 x23

x31 x32 x33 w21 w22 w12 w11

0
∂b
X W Rot180 (W)
Input image Filter’s kernel Rotated kernel
13 kernel2row

How to create matrix 𝕎conv

w22x11 w21x12 0*x13
w22 w21

w12x21 w11x22 0*x23

w12 w11

0*x31 0*x32 0*x33 0

Rotate180 (W)
∂b

X
w22 w21 0 w12 w11 0 0 0 0
flattening

𝕎conv
14 kernel2row

How to create matrix 𝕎conv

0*x11 w22x12 w21x13
w22 w21

0*x21 w12x22 w11x23

w12 w11

0*x31 0*x32 0*x33 0

Rotate180 (W)
∂b

X
w22 w21 0 w12 w11 0 0 0 0

0 w22 w21 0 w12 w11 0 0 0

𝕎conv
15 kernel2row

How to create matrix 𝕎conv

0*x11 0*x12 0*x13
w22 w21

w22x21 w21x22 0*x23

w12 w11

w12x31 w11x32 0*x33 0

Rotate180 (W)
∂b

X
w22 w21 0 w12 w11 0 0 0 0

0 w22 w21 0 w12 w11 0 0 0

0 0 0 w22 w21 0 w12 w11 0

𝕎conv
16 kernel2row

How to create matrix 𝕎conv

0*x11 0*x12 0*x13
w22 w21

0*x21 w22x22 w21x23

w12 w11

0*x31 w12x32 w11x33 0

Rotate180 (W)
∂b

X
w22 w21 0 w12 w11 0 0 0 0

0 w22 w21 0 w12 w11 0 0 0

0 0 0 w22 w21 0 w12 w11 0

0 0 0 0 w22 w21 0 w12 w11

𝕎conv
17 Notation
𝕏flat x11 x12 x13 x21 x22 x23 x31 x32 x33
x11 x12 x13
x22 x23 x32 x33
x21 x22 x23
x21 x22 x31 x32
x31 x32 x33 𝕏conv
x12 x13 x22 x23

∂b
X x11 x12 x21 x22

𝕎flat w11 w12 w21 w22

w11 w12
w22 w21 0 w12 w11 0 0 0 0

w21 w22 0 w22 w21 0 w12 w11 0 0 0

𝕎conv
W 0 0 0 w22 w21 0 w12 w11 0

0 0 0 0 w22 w21 0 w12 w11

18 Convolution as matrix multiplication

X * W = Reshapeo1×o2(𝕎flat × 𝕏conv)
= Reshapeo1×o2(𝕎conv × 𝕏flat)

T
∂b ΔW = Reshapek1×k2(Δ𝕐flat × 𝕏conv)

ΔX = Reshapei1×i2(𝕎Tconv × Δ𝕐flat)

* : Convolution, NOT matrix multiplication

× : Matrix multiplication
o1 x o2: size of Y = X*W
k2 x k2: size of W
i1 x i2: size of X
19 Convolution as matrix multiplication

x22 x23 x32 x33

𝕏conv =
x21 x22 x31 x32
𝕎flat = w11 w12 w21 w22
x12 x13 x22 x23

x11 x12 x21 x22

𝕐flat = 𝕎flat * 𝕏conv =

∂b y11 y12 y21 y22

y11 = w22 x11 + w21x12+ y12 = w22 x12 + w21x13+

w12 x21 + w11x22 w12 x22 + w11x23

y21 = w22 x21 + w21x22+ y22 = w22 x22 + w21x23+

w12 x31 + w11x32 w12 x32 + w11x33

y11 y12
Reshape to 2x2: Y=
y21 y22
20 Convolution as matrix multiplication

x22 x21 x12 x11

𝕏 = T x23 x22 x13 x12

Δ𝕐flat = δy11 δy12 δy21 δy22
x32 x31 x22 x21

x33 x32 x23 x22

∂b

δw11 = δy11x22 + δy12 x23 + δy21x32 + δy22 x33

δw12 = δy11x21 + δy12 x22 + δy21x31 + δy22 x32

T
Δ𝕎flat = Δ𝕐flat × 𝕏 : δw21 = δy11x12 + δy12 x13 + δy21x22 + δy22 x23

δw22 = δy11x11 + δy12 x12 + δy21x21 + δy22 x22

δy11 δy12
Reshape to 2x2: ΔW =
δy21 δy22
21 Convolution as matrix multiplication

w22 w21 0 w12 w11 0 0 0 0 w22 0 0 0

w22 w21 w12 w11 w21 w22 0 0

𝕎conv =
0 0 0 0 0

0 0 0 w22 w21 0 w12 w11 0 0 w21 0 0

0 0 0 0 w22 w21 0 w12 w11 w12 0 w22 0

T
∂b 𝕎conv = w11 w12 w21 w22

0 w11 0 w21

0 0 w12 0

0 0 w11 w12

0 0 0 w11
 22 Convolution as matrix multiplication
w22 0 0 0

w21 w22 0 0

0 w21 0 0

w12 0 w22 0

T
𝕎conv ∂b = w11 w12 w21 w22

0 w11 0 w21

0 0 w12 0

0 0 w11 w12

0 0 0 w11

Δ𝕐flat = δy11 δy12 δy21 δy22

 23 Convolution as matrix multiplication
w22 0 0 0 T
Δ𝕏flat = 𝕎conv × Δ𝕐flat :
w21 w22 0 0
δx11 = δy11w22
0 w21 0 0
δx12 = δy11w21 + δy12w22
w12 0 w22 0
δx13 = δy12w21
T
𝕎conv ∂b = w11 w12 w21 w22

0 w11 0 w21 δx21 = δy11w12 + δy21w22

0 0 w12 0 δx22 = δy11w11 + δy12w12 + δy21w21 + δy11w22

0 0 w11 w12 δx23 = δy12w11 + δy22w21

0 0 0 w11
δx31 = δy21w12

δx32 = δy21w11 + δy22w12

Δ𝕐flat = δy11 δy12 δy21 δy22
δx33 = δy22w11
24 Convolution as matrix multiplication
T
Δ𝕏flat = 𝕎conv × Δ𝕐flat :
δx11 = δy11w22

δx12 = δy11w21 + δy12w22

δx13 = δy12w21
δx11 δx12 δx13
δx21 = δy11w12 + δy21w22
∂b

δx22 = δy11w11 + δy12w12 + δy21w21 + δy11w22 Reshape: 4x4 δx21 δx22 δx23

δx23 = δy12w11 + δy22w21 δx31 δx31 δx33

δx31 = δy21w12 ∆X
δx32 = δy21w11 + δy22w12

δx33 = δy22w11