Im2col

im2col은 'image to column', 즉 '이미지에서 행렬로'라는 의미이다.

Convolution연산을 곧이곧대로 구현하면 for문이 겹겹이 쌓인다. NumPy등의 라이브러리는 for문을 연속으로 사용할 경우 성능이 떨어지는 문제가 있다. 따라서 데이터 가중치 계산이 편한 형태로 변환해야 하는데 이 연산을 im2col이라 한다.

How to work

CNNs in Practice ¹

Im2col_how_to_work.png

위 그림에서 N은 Patch(Kernel/Window)의 개수를 나타내고 D는 필터의 개수를 나타낸다.

Caffe sample

Caffe에서 중요한 내용중 하나는 위의 Feature Map을 C*K*K*N순서로(순서가 중요하다!) 배치하게 된다. 배열의 세로 순서로 삽입된다는 의미이다.

아래와 같은 조건을 전제한다.

int channels   = 1;
int height     = 5;
int width      = 5;
int kernel_h   = 3;
int kernel_w   = 3;
int pad_h      = 0;
int pad_w      = 0;
int stride_h   = 2;
int stride_w   = 2;
int dilation_h = 1;
int dilation_w = 1;

이미지 배열은 아래와 같다고 가정한다.

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

배열로 나타내면 아래와 같다.

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]

im2col을 거치면 아래와 같이 변환된다.

1	3	11	13
2	4	12	14
3	5	13	15
6	8	16	18
7	9	17	19
8	10	18	20
11	13	21	23
12	14	22	24
13	15	23	25

배열로 나타내면 아래와 같다.

[1, 3, 11, 13, 2, 4, 12, 14, 3, 5, 13, 15, 6, 8, 16, 18, 7, 9, 17, 19, 8, 10, 18, 20, 11, 13, 21, 23, 12, 14, 22, 24, 13, 15, 23, 25]

만약 채널이 2개 이상일 경우 im2col을 거치면 아래와 같은 배열 스타일이 출력된다.

[r, r, r, ... r, g, g, g, ... g, b, b, b, ... b]

위와 같이 변환하는 이유는 BLAS호환을 맞추기 위해서 이다.

in Caffe

Convolution in Caffe: a memo

Loosely speaking, assume that we have a WH image with depth D at each input location. For each location, we get a KK patch, which could be considered as a KKD vector, and apply M filters to it. In pseudocode, this is (ignoring boundary conditions):

for w in 1..W
  for h in 1..H
    for x in 1..K
      for y in 1..K
        for m in 1..M
          for d in 1..D
            output(w, h, m) += input(w+x, h+y, d) * filter(m, x, y, d)
          end
        end
      end
    end
  end
end

위 의사코드를 C/C++로 구현한 Caffe 구현체는 아래와 같다. (src/util/im2col.cpp파일을 참조하면 된다)

template <typename Dtype>
void im2col_cpu(const Dtype* data_im, const int channels,
    const int height, const int width, const int kernel_h, const int kernel_w,
    const int pad_h, const int pad_w,
    const int stride_h, const int stride_w,
    const int dilation_h, const int dilation_w,
    Dtype* data_col) {
  const int output_h = (height + 2 * pad_h -
    (dilation_h * (kernel_h - 1) + 1)) / stride_h + 1;
  const int output_w = (width + 2 * pad_w -
    (dilation_w * (kernel_w - 1) + 1)) / stride_w + 1;
  const int channel_size = height * width;
  for (int channel = channels; channel--; data_im += channel_size) {
    for (int kernel_row = 0; kernel_row < kernel_h; kernel_row++) {
      for (int kernel_col = 0; kernel_col < kernel_w; kernel_col++) {
        int input_row = -pad_h + kernel_row * dilation_h;
        for (int output_rows = output_h; output_rows; output_rows--) {
          if (!is_a_ge_zero_and_a_lt_b(input_row, height)) {
            for (int output_cols = output_w; output_cols; output_cols--) {
              *(data_col++) = 0;
            }
          } else {
            int input_col = -pad_w + kernel_col * dilation_w;
            for (int output_col = output_w; output_col; output_col--) {
              if (is_a_ge_zero_and_a_lt_b(input_col, width)) {
                *(data_col++) = data_im[input_row * width + input_col];
              } else {
                *(data_col++) = 0;
              }
              input_col += stride_w;
            }
          }
          input_row += stride_h;
        }
      }
    }
  }
}

Graph

Im2col-example.jpg

Filter to im2col

5×5 데이터 행렬을 3×3에 넣기 위한 im2col의 결과는 아래와 같다.

5x5_to_3x3_im2col_result_example.png

Favorite site

E.T.C

How to cite im2col? #4154

References

Nmhkahn.github.io_-_CNNs_in_Practice.pdf ↩

1	3	11	13
2	4	12	14
3	5	13	15
6	8	16	18
7	9	17	19
8	10	18	20
11	13	21	23
12	14	22	24
13	15	23	25

1	3	11	13
2	4	12	14
3	5	13	15
6	8	16	18
7	9	17	19
8	10	18	20
11	13	21	23
12	14	22	24
13	15	23	25