Im2col

lastmod 2018-10-18created 2017-08-3017 edits

im2col means 'image to column', that is, 'from image to matrix'.

Implementing the Convolution operation literally results in deeply nested for loops. Libraries such as NumPy lose performance when for loops are used in succession. So the data has to be transformed into a form that makes weight computation easy, and this operation is called im2col.

How to work

CNNs in Practice ¹

Im2col_how_to_work.png

In the figure above, N is the number of patches (Kernel/Window) and D is the number of filters.

Caffe sample

One important point in Caffe is that the Feature Map above is laid out in C*K*K*N order (the order matters!). This means it is inserted in the vertical order of the array.

Assume the following conditions.

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;

Assume the image array is as follows.

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

As an array, it looks like this.

[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]

After im2col, it is transformed as follows.

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

As an array, it looks like this.

[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]

If there are two or more channels, im2col outputs an array in the following style.

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

The reason for transforming it this way is BLAS compatibility.

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

Caffe's implementation of the pseudocode above in C/C++ is as follows. (See the src/util/im2col.cpp file)

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

The result of im2col for fitting a 5×5 data matrix into a 3×3 one is as follows.

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 ↩

author Zer0 sitemap

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