python convolution with different dimension
<p>I'm trying to implement convolutional neural network in Python.<br>
However, when I use signal.convolve or np.convolve, it can not do convolution on X, Y(X is 3d, Y is 2d). X are training minibatches. Y are filters.
I don't want to do for loop for every training vector like:</p>

<pre><code>for i in xrange(X.shape[2]):
    result = signal.convolve(X[:,:,i], Y, 'valid')
    ....
</code></pre>

<p>So, is there any function I can use to do convolution efficiently?</p>

<p>Scipy implements standard N-dimensional convolutions, so that the matrix to be convolved and the kernel are both N-dimensional.</p>

<p>A quick fix would be to add an extra dimension to <code>Y</code> so that <code>Y</code> is 3-Dimensional:</p>

<pre><code>result = signal.convolve(X, Y[..., None], 'valid')
</code></pre>

<p>I'm assuming here that the last axis corresponds to the image index as in your example <code>[width, height, image_idx]</code> (or <code>[height, width, image_idx]</code>). If it is the other way around and the images are indexed in the first axis (as it is more common in C-ordering arrays) you should replace <code>Y[..., None]</code> with <code>Y[None, ...]</code>.</p>

<p>The line <code>Y[..., None]</code> will add an extra axis to <code>Y</code>, making it 3-dimensional <code>[kernel_width, kernel_height, 1]</code> and thus, converting it to a valid 3-Dimensional convolution kernel.</p>

<p>NOTE: This assumes that all your input mini-batches have the same <code>width x height</code>, which is standard in CNN's.</p>

<hr>

<p>EDIT: Some timings as @Divakar suggested.</p>

<p>The testing framework is setup as follows:</p>

<pre><code>def test(S, N, K):
    """ S: image size, N: num images, K: kernel size"""
    a = np.random.randn(S, S, N)
    b = np.random.randn(K, K)
    valid = [slice(K//2, -K//2+1), slice(K//2, -K//2+1)]

    %timeit signal.convolve(a, b[..., None], 'valid')
    %timeit signal.fftconvolve(a, b[..., None], 'valid')
    %timeit ndimage.convolve(a, b[..., None])[valid]
</code></pre>

<p>Find bellow tests for different configurations:</p>

<ul>
<li><p>Varying image size <code>S</code>:</p>

<pre><code>&gt;&gt;&gt; test(100, 50, 11) # 100x100 images
1 loop, best of 3: 909 ms per loop
10 loops, best of 3: 116 ms per loop
10 loops, best of 3: 54.9 ms per loop

&gt;&gt;&gt; test(1000, 50, 11) # 1000x1000 images
1 loop, best of 3: 1min 51s per loop
1 loop, best of 3: 16.5 s per loop
1 loop, best of 3: 5.66 s per loop
</code></pre></li>
<li><p>Varying number of images <code>N</code>:</p>

<pre><code>&gt;&gt;&gt; test(100, 5, 11) # 5 images
10 loops, best of 3: 90.7 ms per loop
10 loops, best of 3: 26.7 ms per loop
100 loops, best of 3: 5.7 ms per loop

&gt;&gt;&gt; test(100, 500, 11) # 500 images
1 loop, best of 3: 9.75 s per loop
1 loop, best of 3: 888 ms per loop
1 loop, best of 3: 727 ms per loop
</code></pre></li>
<li><p>Varying kernel size <code>K</code>:</p>

<pre><code>&gt;&gt;&gt; test(100, 50, 5) # 5x5 kernels
1 loop, best of 3: 217 ms per loop
10 loops, best of 3: 100 ms per loop
100 loops, best of 3: 11.4 ms per loop

&gt;&gt;&gt; test(100, 50, 31) # 31x31 kernels
1 loop, best of 3: 4.39 s per loop
1 loop, best of 3: 220 ms per loop
1 loop, best of 3: 560 ms per loop
</code></pre></li>
</ul>

<p>So, in short, <code>ndimage.convolve</code> is always faster, except when the kernel size is very large (as <code>K = 31</code> in the last test).</p>

python numpy scipy deep-learning