GSoC 2013: imerode and imdilate (update #6)

Since I deviated so much from the original project while fixing the image IO functions in Octave core, I decided to only focus on optimizing the imerode and imdilate in the final phase of GSoC. The reason is that these are at the core of many functions in the image package.

On the original project it was planned to do all the work by expanding the __spatial_filtering__ function and that's where I previously started. While doing so, it became evident that a complete rewrite was necessary. The convn() which could be used in most cases of binary images was performing much faster even though it was performing a more complex operation. As such, performing at least as fast as convn() became the target which was achieved:

octave> se = [0 1 0; 1 1 1; 0 1 0];
octave> im = rand (1000) > 0.5;
octave> t = cputime (); for i = 1:100, a = imerode (im, se, "same"); endfor; cputime() - t
ans = 2.1281
octave> t = cputime (); for i = 1:100, a = convn (im, se, "same") == nnz (se); endfor; cputime() - t
ans = 2.7802

This implementation could be reused in __spatial_filtering__ to also speed up functions such as medfilt2, ordfilt2, and ordfiltn but there are specific algorithms for those cases which should be used instead.

I have tested the new implementation of imerode against the last release (version 2.0.0) and the last development version that was still making use of __spatial_filtering__ (cset 6db5e3c6759b). The tests are very simple (test imerode), just random matrices with different number of dimensions. The new implementation seems to perform much faster in all cases, and shows a performance increase between 1.5-30x (output of test imerode). The differences are bigger for grayscale images (since imerode was already using convn for binary cases), and larger structuring elements (SE) with multiple dimensions.

A couple of things:

--- version 2.0.0 (old) cset 6db5e3c6759b (dev) latest development (new) Performance old/new Performance dev/new
2D binary image (90%) 0.009081 0.024602 0.006240 1.4551 3.9423
2D binary image (10%) 0.007360 0.022881 0.004160 1.7692 5.5000
3D binary image with 2D SE NO! 0.481470 0.079125 n/a 6.0849
3D binary image with 3D SE NO! 0.518032 0.075605 n/a 6.8519
7D binary image with 5D SE NO! 13.940071 0.463229 n/a 30.093
2D uint8 image 0.062324 0.043403 0.029322 2.1255 1.4802
3D uint8 image with 2D SE NO NO 0.430347 n/a n/a
3D uint8 image with 3D SE 3.061951 1.725628 0.791569 3.8682 2.1800
7D uint8 image with 3D SE NO NO 2.005325 n/a n/a
7D uint8 image with 7D SE 4.091456 2.940984 0.541634 7.5539 5.4298
2D uint8 image with a larger SE 0.610678 0.305579 0.087445 6.9835 3.4945