Syllabus Lesson 116 of 246 · Module 10: Networks that see (CNNs)
Module 10: Networks that see (CNNs)

Fast convolution: one big matrix multiply (im2col)

Why it matters Your loop convolution visits each output pixel in Python, which is slow. Real libraries turn the whole convolution into one matrix multiply, the operation computers are best at.

See it

Play the animation. Cut out every k by k patch the filter would visit and lay each one flat as a row: that is im2col ("image to columns"). Lay the filter flat as a column. Now one matrix multiply, rows times column, computes every output at once. With many filters, the column becomes a matrix and still one multiply does it all.

The cost: the patches overlap, so the patch matrix repeats pixels and takes more memory. Speed for memory is a trade you will meet again and again.

Words and symbols in this lesson
convolution
sliding a small grid of weights (a filter) across an image, one dot product per position
filter, feature map
the small learned grid of weights; and the image of its responses
im2col
laying every patch flat as a row so a convolution becomes one matrix multiply
Your turn

Write im2col(img, k) returning a (number of positions, k*k) matrix of flattened patches in row-by-row order, and conv_fast(img, filt) computing the valid convolution with one matrix multiply. You may loop over the k by k offsets, but not over output pixels.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.