Implementation of MATLAB's `im2col`

Question

The function im2col in MATLAB is very useful to vectorize Patch based Image Processing algorithms. The problem is the function isn't optimized and doesn't use C Code. I'm trying to build efficient C code for that.

This is the code I created:

function [ mColumnImage ] = ImageToColumns( mInputImage, blockRadius )
% ----------------------------------------------------------------------------------------------- %
% [ mColumnImage ] = ImageToColumns( mInputImage, blockRadius )
% Creates an column image from the sliding neighborhood in mInpuImage
% Input:
% - mInputImage - Input image.
% Matrix, 1 Channels, Floating Point
% - blockRadius - Local Window Radius.
% Scalar, Floating Point, {1, 2, ..., inf}.
% Output:
% - mColumnImage - Input image.
% Matrix, 1 Channels, Floating Point, [0, 1]
% Remarks:
% 1. Prefixes:
% - 'm' - Matrix.
% - 'v' - Vector.
% 2. C
% TODO:
% 1. I
% Release Notes:
% - 1.0.000 22/08/2014 R
% * First release version.
% ----------------------------------------------------------------------------------------------- %
numRows = size(mInputImage, 1);
numCols = size(mInputImage, 2);
blockSize = (2 * blockRadius) + 1;
numPixelsToProcess = (numRows - blockSize + 1) * (numCols - blockSize + 1);
mColumnImage = zeros((blockSize * blockSize), numPixelsToProcess);
colImageColIdx = 0;
for iColIdx = (blockRadius + 1):(numCols - blockRadius)
 for jRowIdx = (blockRadius + 1):(numRows - blockRadius)
 colImageColIdx = colImageColIdx + 1;
 colImageRowIdx = 0;
 for kPixelColIdx = -blockRadius:blockRadius
 for lPixelRowIdx = -blockRadius:blockRadius
 colImageRowIdx = colImageRowIdx + 1;
 mColumnImage(colImageRowIdx, colImageColIdx) = mInputImage((jRowIdx + lPixelRowIdx), (iColIdx + kPixelColIdx));
 end
 end
 end
end
end

It is MATLAB code written in C style. Imagine it was C code: what would you do make it faster? What would you do to allow compiler optimizations (loop unrolling, vectorization, parallelization, etc...)?

I posted vanilla C code I created and have a few questions about it:

1. How can I make the memory access more efficient (hence make the code faster)?
2. Any place to utilize vectorization?
3. How can I assist the compiler and tell it no aliasing will happen?
4. What would be the right way to utilize OpenMP?

• Royi: @CrisLuengo, The reason the inner loop are on the rows is because MATLAB is Column Major.
• Cris Luengo: Sorry, I must have had a brain fart when I wrote that.

Answer 1

This is a valid C code which implements the above:

void ImageToColumns(float* mO, float* mI, int numRows, int numCols, int blockRadius)
{
 int blockSize, blockNumElements, colImageColIdx, colImageRowIdx;
 int ii, jj, kk, ll;
 blockSize = (2 * blockRadius) + 1;
 blockNumElements = blockSize * blockSize;
 colImageRowIdx = -1;
 for (ii = blockRadius; ii < (numRows - blockRadius); ii++)
 {
 for (jj = blockRadius; jj < (numCols - blockRadius); jj++)
 {
 colImageRowIdx = colImageRowIdx + 1;
 colImageColIdx = -1;
 for (kk = -blockRadius; kk <= blockRadius; kk++)
 {
 for (ll = -blockRadius; ll <= blockRadius; ll++)
 {
 colImageColIdx = colImageColIdx + 1;
 mO[(colImageRowIdx * blockNumElements) + colImageColIdx] = mI[((ii + kk) * numCols) + jj + ll];
 }
 }
 }
 }
}

Clearly this a memory bounded algorithm.