Efficient Implementation of `im2col` and `col2im`

Question

MATLAB's im2col and col2im are very important function for vectorization in MATLAB when dealing with images.
Yet they require MATLAB's Image Processing Toolbox.

My question is, is there an efficient (Vectorzied) way to implement the using MATLAB's functions (With no toolbox)?
I need both the sliding and distinct mode.

I don't need any padding.

Thank You.

Orthodontics

This may help: #20336788 – Burnette

Hi, Not quite, as the create multi dimensional array while the array I'm after (In the sliding option) is 2D. – Orthodontics

Answer 1

I can only hope that Mathworks guys don't sue you or me or Stackoverflow for that matter, trying to create vectorized implementations of their IP toolbox functions, as they have put price on that toolbox. But in any case, forgetting those issues, here are the implementations.

Replacement for im2col with 'sliding' option

I wasn't able to vectorize this until I sat down to write solution to another problem on Stackoverflow. So, I would strongly encourage to look into it too.

function out = im2col_sliding(A,blocksize)

nrows = blocksize(1);
ncols = blocksize(2);

%// Get sizes for later usages
[m,n] = size(A);

%// Start indices for each block
start_ind = reshape(bsxfun(@plus,[1:m-nrows+1]',[0:n-ncols]*m),[],1); %//'

%// Row indices
lin_row = permute(bsxfun(@plus,start_ind,[0:nrows-1])',[1 3 2]);  %//'

%// Get linear indices based on row and col indices and get desired output
out = A(reshape(bsxfun(@plus,lin_row,[0:ncols-1]*m),nrows*ncols,[]));

return;

Replacement for im2col with 'distinct' option

function out = im2col_distinct(A,blocksize)

nrows = blocksize(1);
ncols = blocksize(2);
nele = nrows*ncols;

row_ext = mod(size(A,1),nrows);
col_ext = mod(size(A,2),ncols);

padrowlen = (row_ext~=0)*(nrows - row_ext);
padcollen = (col_ext~=0)*(ncols - col_ext);

A1 = zeros(size(A,1)+padrowlen,size(A,2)+padcollen);
A1(1:size(A,1),1:size(A,2)) = A;

t1 = reshape(A1,nrows,size(A1,1)/nrows,[]);
t2 = reshape(permute(t1,[1 3 2]),size(t1,1)*size(t1,3),[]);
t3 =  permute(reshape(t2,nele,size(t2,1)/nele,[]),[1 3 2]);
out = reshape(t3,nele,[]);

return;

---

Some quick tests show that both these implementations particularly sliding one for small to decent sized input data and distinct for all datasizes perform much better than the in-built MATLAB function implementations in terms of runtime performance.

How to use

With in-built MATLAB function - 
B = im2col(A,[nrows ncols],'sliding')

With our custom function - 
B = im2col_sliding(A,[nrows ncols])

%// ------------------------------------

With in-built MATLAB function - 
B = im2col(A,[nrows ncols],'distinct')

With our custom function - 
B = im2col_distinct(A,[nrows ncols])

Kersten

Thank you for your effort. I thought the 'Sliding' mode of operation could be achieved using no for loops at all. – Orthodontics

@Drazick It could surely be vectorized with bsxfun and without any loops, but won't be efficient as far as I could imagine. One alternative could be accumarray, but AFAIK, it won't accept matrix for subs for matrix indexing, so even that would involve loop. – Kersten

I saw the for loops in im2col and thought with well vectorized code it could be beaten. – Orthodontics

@Drazick So here are two rules with MATLAB - 1) Not every for loop is vectorizable 2) Not every loop that is vectorizable is guaranteed to work better than its for-loop counterpart. Now with im2col for sliding option it surely looks like the in-built one is a better implementation than the one presented here, but as pointed out in the solution, use this one when you don't have access to IP Toolbox. – Kersten

the original implementation of im2col also uses vectorization. I was under the impression it can be beaten. I have algorithm which is really limited by the time im2col takes. – Orthodontics

Hi @Drazick, I followed your comment, but now I think you've gotten the answers you need. Vectorization for 'distinct' is "straightforward", as Divakar has demonstrated here. As far as I can see, vectorization of 'sliding' uses specially constructed indexing matrices – whether this makes things faster I can't tell. I'd expect the Octave implementations pointed to by Markus to be pretty effective though. – Eason

@Drazick Finally I think the vectorizations are done! Thank you for not giving up on me! ;) Check out the edits! Let me know! – Kersten

@A.Donda Well finally I think we have the vectorized solutions in here in the edited codes ! :) – Kersten

@Divakar, That's great. I will try it and report. By the way, what about big matrices, is it faster? Thank You. – Orthodontics

@Divakar, it seems that by removing all the overhead in im2col you can get much better results. – Orthodontics

@Drazick What overhead are we talking about? Not sure I got you there. – Kersten

Take the original im2col function shipped with MATLAB. remove all lines working on special cases and "distinct" mode. Just keep the sliding mode code. The performance gains are quite big and it even beats your vectorized code. I think bsxfun isn't well optimized. – Orthodontics

@Drazick Thing with bsxfun is that it is resource-hungry. So I would make an estimated guess that it would be better with small sized inputs and I would root for it even against the stripped off im2col version, but if you are talking about bigger inputs, your stripped off version might be the winner. If you would like to post the benchmark results, it might be interesting. – Kersten

I used it for images with 11 x 11 size to generate 5 x 5 blocks. – Orthodontics

@Divakar, Here's a quick analysis I did: pastebin.com/NYbhR8uB Im2ColSliding is a sliding stripped version of MATLAB's im2col, Im2ColSliding2 is your version. As you can see, the stripped version is consistently faster by almost a factor of 2. – Orthodontics

@Kersten - Did you ever get around to making a vectorized version of col2im? I'm curious to see if you can get it to be fast and vectorized as well. FWIW, MathWorks wouldn't sue you at all. This is your own work and you are simply trying to reproduce something that is useful. The concept of transforming neighbourhoods into columns is not subject to copyright or is unique so you're pretty safe. In that same note, that's why Octave was made - to recreate some basic MATLAB functionality as it's a useful tool, and it's free! – Conserve

@Conserve haha I meant that "suing" thing mostly as a joke! :) Well, I need to see why I didn't go for the vectorized version of col2im. From its doc, it seems to be nothing too different from im2colin terms of using few reshapes and permutes, but let me get back to you on this with more detail if not the actual implementation. – Kersten

I'd vote for faster solution. This is what's important. We can give up on vectorization if it not making it faster :-). @Divakar, would you support this forum: area51.stackexchange.com/proposals/66531/computer-vision We need people up vote questions with less than 10 votes. Thank You. – Orthodontics

@Divakar, Is there a way to contact you? – Orthodontics

Answer 2

You can cheat while looking to GNU Octave image package. There are im2col and col2im as script language implemented:

• im2col
• col2im

As far as I see, it differs most in different comment style (# instead of %) and different string style (" instead of '). If you change this and remove the assert test on the bottom, it might be runnable already. If not, go through it with the debugger.

Furthermore, be aware of the License (GPLv3). It's free, but your changes have to be free too!

Epic