Prologue

conv layer에서 지적했듯이 기존 방법으로 CNN을 연산하면 속도가 $O(n^4)$로 느리다. 그래서 머리 좋은 사람들이 컴퓨팅 자원을 효율적으로 쓰려고 만든 방법이 im2col이다.

im2col

두 matrix를 strides 1, padding 0으로 convolve하면 3x3 matrix가 나온다. 이렇게 하면 직관적이지만 위에서 언급했듯이 느리다는 단점이 있다. im2col은 메소드 이름처럼 연산에 들어가는 모든 matrix를 vector로 만든다. 이미지 한 장은 그냥 vector로 만들면 되지만 kerel matrix는 좀 복잡하다. 5x5 이미지의 시작점에 kernel이 올라가 있는 경우를 생각해볼 건데 kernel 밖에서 연산하는 것을 원하지 않으므로 0으로 한다.

이 matrix를 이미지 vector와 계산할 거라서 row vector로 주욱 펼쳐준다.

이걸 이미지 vector와 계산하면 scalar하나가 나올건데 이게 3x3 feature map의 (0, 0)에 위치하게 될 거다. 이 과정을 염두하고 남은 과정을 반복해서 row 방향으로 붙이면 kernel은 sparse matrix로 만들 수 있다.

Implementation

kernel을 하나만 쓰는 경우는 거의 없으므로 다수의 커널을 쓰는 경우를 구현할거다.

def im2col(img_shape, kernel_shape, strides):
    _, ih, iw, ic = img_shape
    kf, kh, kw, kc = kernel_shape
    sh, sw = strides
    out_h = ih - kh + 1
    out_w = iw - kw + 1
    out = np.zeros((kf, out_h * out_w, ic, ih, iw))
    for i in range(kf):
        for h in range(out_h):
            for w in range(out_w):
                n = h * out_w + w
                out[i][n][:, h*sh:h*sh+kh, w*sw:w*sw+kw] = kernel[i]
    out.reshape(kf, out_h*out_w, -1)
    return out

Epilogue

• 그냥 두 matrix를 여러번 계산하지말고 matrix들의 모양을 새로 만들어서 한 방에 계산하고 싶다는 의도가 깔려있다. 좀더 나아가서 이렇게 하면 backward pass도 효율적으로 처리할 수 있을 것 같다.
• 이 글에서 알아본 im2col이 나중에 transpose convolution까지 이어진다.