9

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.

Royi
  • 4,640
  • 6
  • 46
  • 64
  • This may help: http://stackoverflow.com/questions/20336288/for-loop-to-split-matrix-to-equal-sized-sub-matrices – Luis Mendo Aug 22 '14 at 15:10
  • Hi, Not quite, as the create multi dimensional array while the array I'm after (In the `sliding` option) is 2D. – Royi Aug 22 '14 at 15:36

2 Answers2

18

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])
Community
  • 1
  • 1
Divakar
  • 218,885
  • 19
  • 262
  • 358
  • Thank you for your effort. I thought the 'Sliding' mode of operation could be achieved using no `for` loops at all. – Royi Aug 22 '14 at 20:53
  • @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. – Divakar Aug 22 '14 at 20:58
  • I saw the `for` loops in `im2col` and thought with well vectorized code it could be beaten. – Royi Aug 23 '14 at 10:42
  • 1
    @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. – Divakar Aug 24 '14 at 10:20
  • 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. – Royi Aug 24 '14 at 21:38
  • 1
    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. – A. Donda Aug 26 '14 at 00:33
  • @Drazick Finally I think the vectorizations are done! Thank you for not giving up on me! ;) Check out the edits! Let me know! – Divakar Sep 08 '14 at 17:20
  • 1
    @A.Donda Well finally I think we have the vectorized solutions in here in the edited codes ! :) – Divakar Sep 08 '14 at 17:21
  • @Divakar, That's great. I will try it and report. By the way, what about big matrices, is it faster? Thank You. – Royi Sep 09 '14 at 06:28
  • @Divakar, it seems that by removing all the overhead in `im2col` you can get much better results. – Royi Sep 10 '14 at 16:59
  • @Drazick What overhead are we talking about? Not sure I got you there. – Divakar Sep 10 '14 at 17:00
  • 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. – Royi Sep 10 '14 at 17:39
  • 1
    @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. – Divakar Sep 10 '14 at 17:45
  • I used it for images with 11 x 11 size to generate 5 x 5 blocks. – Royi Sep 10 '14 at 17:53
  • @Divakar, Here's a quick analysis I did: http://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. – Royi Sep 10 '14 at 18:19
  • @Divakar - 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! – rayryeng Mar 01 '15 at 02:04
  • @rayryeng 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 `im2col`in terms of using few reshapes and permutes, but let me get back to you on this with more detail if not the actual implementation. – Divakar Mar 01 '15 at 13:38
  • 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: http://area51.stackexchange.com/proposals/66531/computer-vision We need people up vote questions with less than 10 votes. Thank You. – Royi Mar 01 '15 at 17:16
  • @Divakar, Is there a way to contact you? – Royi Jul 01 '16 at 12:32
3

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

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!

Markus
  • 2,998
  • 1
  • 21
  • 28