with - numpy python tutorial

Implementar im2col ''sliding'' de MATLAB en Python

Question

P: ¿Cómo acelerar esto?

Debajo está mi implementación de im2col ''sliding'' de Matlab con la característica adicional de devolver cada n''th columna. La función toma una imagen (o cualquier 2 matriz difusa) y diapositivas de izquierda a derecha, de arriba a abajo, seleccionando cada subimagen superpuesta de un tamaño determinado y devolviendo una matriz cuyas columnas son las subimágenes.

import numpy as np
def im2col_sliding(image, block_size, skip=1):
rows, cols = image.shape
horz_blocks = cols - block_size[1] + 1
vert_blocks = rows - block_size[0] + 1
output_vectors = np.zeros((block_size[0] * block_size[1], horz_blocks * vert_blocks))
itr = 0
for v_b in xrange(vert_blocks):
for h_b in xrange(horz_blocks):
output_vectors[:, itr] = image[v_b: v_b + block_size[0], h_b: h_b + block_size[1]].ravel()
itr += 1
return output_vectors[:, ::skip]

ejemplo:

a = np.arange(16).reshape(4, 4)
print a
print im2col_sliding(a, (2, 2)) # return every overlapping 2x2 patch
print im2col_sliding(a, (2, 2), 4) # return every 4th vector

devoluciones:

[[ 0 1 2 3]
[ 4 5 6 7]
[ 8 9 10 11]
[12 13 14 15]]
[[ 0. 1. 2. 4. 5. 6. 8. 9. 10.]
[ 1. 2. 3. 5. 6. 7. 9. 10. 11.]
[ 4. 5. 6. 8. 9. 10. 12. 13. 14.]
[ 5. 6. 7. 9. 10. 11. 13. 14. 15.]]
[[ 0. 5. 10.]
[ 1. 6. 11.]
[ 4. 9. 14.]
[ 5. 10. 15.]]

El rendimiento no es muy bueno, especialmente considerando si llamo im2col_sliding(big_matrix, (8, 8)) (62001 columns) o im2col_sliding(big_matrix, (8, 8), 10) (6201 columnas, manteniendo solo cada 10mo vector) tomará la misma cantidad de tiempo [donde big_matrix tiene el tamaño de 256 x 256].

Estoy buscando ideas para acelerar esto.

Answer 1

No creo que puedas hacerlo mejor. Claramente, tienes que ejecutar un bucle de tamaño

cols - block_size[1] * rows - block_size[0]

Pero estás tomando un parche de 3, 3 en tu ejemplo, no un 2, 2.

Answer 2

Para deslizar la ventana sobre diferentes canales de imagen, podemos usar una versión actualizada del código proporcionado por Divakar @ Implement MATLAB im2col ''sliding'' en Python , es decir

import numpy as np
A = np.random.randint(0,9,(2,4,4)) # Sample input array
# Sample blocksize (rows x columns)
B = [2,2]
skip=[2,2]
# Parameters
D,M,N = A.shape
col_extent = N - B[1] + 1
row_extent = M - B[0] + 1
# Get Starting block indices
start_idx = np.arange(B[0])[:,None]*N + np.arange(B[1])
# Generate Depth indeces
didx=M*N*np.arange(D)
start_idx=(didx[:,None]+start_idx.ravel()).reshape((-1,B[0],B[1]))
# Get offsetted indices across the height and width of input array
offset_idx = np.arange(row_extent)[:,None]*N + np.arange(col_extent)
# Get all actual indices & index into input array for final output
out = np.take (A,start_idx.ravel()[:,None] + offset_idx[::skip[0],::skip[1]].ravel())

Prueba Ejecución de muestra

A=
[[[6 2 8 5]
[6 4 7 6]
[8 6 5 2]
[3 1 3 7]]
[[6 0 4 3]
[7 6 4 6]
[2 6 7 1]
[7 6 7 7]]]
out=
[6 8 8 5]
[2 5 6 2]
[6 7 3 3]
[4 6 1 7]
[6 4 2 7]
[0 3 6 1]
[7 4 7 7]
[6 6 6 7]

Answer 3

Para mejorar aún más el rendimiento (por ejemplo, en la convolución), también podemos usar la implementación por lotes basada en el código extendido, provisto por M Elyia @ Implement Matlab im2col ''sliding'' en python , es decir,

import numpy as np
A = np.arange(3*1*4*4).reshape(3,1,4,4)+1 # 3 Sample input array with 1 channel
B = [2,2] # Sample blocksize (rows x columns)
skip = [2,2]
# Parameters
batch, D,M,N = A.shape
col_extent = N - B[1] + 1
row_extent = M - B[0] + 1
# Get batch block indices
batch_idx = np.arange(batch)[:, None, None] * D * M * N
# Get Starting block indices
start_idx = np.arange(B[0])[None, :,None]*N + np.arange(B[1])
# Generate Depth indeces
didx=M*N*np.arange(D)
start_idx=(didx[None, :, None]+start_idx.ravel()).reshape((-1,B[0],B[1]))
# Get offsetted indices across the height and width of input array
offset_idx = np.arange(row_extent)[None, :, None]*N + np.arange(col_extent)
# Get all actual indices & index into input array for final output
act_idx = (batch_idx +
start_idx.ravel()[None, :, None] +
offset_idx[:,::skip[0],::skip[1]].ravel())
out = np.take (A, act_idx)

Prueba de ejecución de prueba :

A =
[[[[ 1 2 3 4]
[ 5 6 7 8]
[ 9 10 11 12]
[13 14 15 16]]]
[[[17 18 19 20]
[21 22 23 24]
[25 26 27 28]
[29 30 31 32]]]
[[[33 34 35 36]
[37 38 39 40]
[41 42 43 44]
[45 46 47 48]]]]
out =
[[[ 1 2 3 9 10 11]
[ 2 3 4 10 11 12]
[ 5 6 7 13 14 15]
[ 6 7 8 14 15 16]]
[[17 18 19 25 26 27]
[18 19 20 26 27 28]
[21 22 23 29 30 31]
[22 23 24 30 31 32]]
[[33 34 35 41 42 43]
[34 35 36 42 43 44]
[37 38 39 45 46 47]
[38 39 40 46 47 48]]]

Answer 4

También puede agregar más optimización a la respuesta de M Eliya (aunque no tan significativa)

En lugar de "aplicar" el salto al final, puede aplicarlo al generar matrices desplazadas, por lo que en lugar de:

# Get offsetted indices across the height and width of input array
offset_idx = np.arange(row_extent)[:,None]*N + np.arange(col_extent)
# Get all actual indices & index into input array for final output
out = np.take (A,start_idx.ravel()[:,None] + offset_idx[::skip[0],::skip[1]].ravel())

Agregaría omisiones usando el parámetro step de la función arange de numpy:

# Get offsetted indices across the height and width of input array and add skips
offset_idx = np.arange(row_extent, step=skip[0])[:, None] * N + np.arange(col_extent, step=skip[1])

y luego simplemente agregue la matriz offset sin indexación [::]

# Get all actual indices & index into input array for final output
out = np.take(A, start_idx.ravel()[:, None] + offset_idx.ravel())

En valores de omisión pequeños, apenas ahorra tiempo:

In[25]:
A = np.random.randint(0,9,(3, 1024, 1024))
B = [2, 2]
skip = [2, 2]
In[26]: %timeit im2col(A, B, skip)
10 loops, best of 3: 19.7 ms per loop
In[27]: %timeit im2col_optimized(A, B, skip)
100 loops, best of 3: 17.5 ms per loop

Sin embargo, con valores de omisión más grandes, ahorra un poco más de tiempo:

In[28]: skip = [10, 10]
In[29]: %timeit im2col(A, B, skip)
100 loops, best of 3: 3.85 ms per loop
In[30]: %timeit im2col_optimized(A, B, skip)
1000 loops, best of 3: 1.02 ms per loop

A = np.random.randint(0,9,(3, 2000, 2000))
B = [10, 10]
skip = [10, 10]
In[43]: %timeit im2col(A, B, skip)
10 loops, best of 3: 87.8 ms per loop
In[44]: %timeit im2col_optimized(A, B, skip)
10 loops, best of 3: 76.3 ms per loop

Answer 5

Enfoque # 1

Podríamos usar algunas broadcasting aquí para obtener todos los índices de todas esas ventanas deslizantes de una sola vez y así, con la indexación, lograr una vectorized solution . Esto está inspirado en la Efficient Implementation of im2col and col2im .

Aquí está la implementación -

def im2col_sliding_broadcasting(A, BSZ, stepsize=1):
# Parameters
M,N = A.shape
col_extent = N - BSZ[1] + 1
row_extent = M - BSZ[0] + 1
# Get Starting block indices
start_idx = np.arange(BSZ[0])[:,None]*N + np.arange(BSZ[1])
# Get offsetted indices across the height and width of input array
offset_idx = np.arange(row_extent)[:,None]*N + np.arange(col_extent)
# Get all actual indices & index into input array for final output
return np.take (A,start_idx.ravel()[:,None] + offset_idx.ravel()[::stepsize])

Enfoque # 2

Usando el conocimiento recién adquirido de los NumPy array strides que nos permite crear ventanas deslizantes, tendríamos otra solución eficiente:

def im2col_sliding_strided(A, BSZ, stepsize=1):
# Parameters
m,n = A.shape
s0, s1 = A.strides
nrows = m-BSZ[0]+1
ncols = n-BSZ[1]+1
shp = BSZ[0],BSZ[1],nrows,ncols
strd = s0,s1,s0,s1
out_view = np.lib.stride_tricks.as_strided(A, shape=shp, strides=strd)
return out_view.reshape(BSZ[0]*BSZ[1],-1)[:,::stepsize]

Enfoque n. ° 3

El método stristed enumerado en el enfoque anterior se ha incorporado en el módulo scikit-image para un menos desordenado, como tal -

from skimage.util import view_as_windows as viewW
def im2col_sliding_strided_v2(A, BSZ, stepsize=1):
return viewW(A, (BSZ[0],BSZ[1])).reshape(-1,BSZ[0]*BSZ[1]).T[:,::stepsize]

Ejecuciones de muestra -

In [106]: a # Input array
Out[106]:
array([[ 0, 1, 2, 3, 4],
[ 5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19]])
In [107]: im2col_sliding_broadcasting(a, (2,3))
Out[107]:
array([[ 0, 1, 2, 5, 6, 7, 10, 11, 12],
[ 1, 2, 3, 6, 7, 8, 11, 12, 13],
[ 2, 3, 4, 7, 8, 9, 12, 13, 14],
[ 5, 6, 7, 10, 11, 12, 15, 16, 17],
[ 6, 7, 8, 11, 12, 13, 16, 17, 18],
[ 7, 8, 9, 12, 13, 14, 17, 18, 19]])
In [108]: im2col_sliding_broadcasting(a, (2,3), stepsize=2)
Out[108]:
array([[ 0, 2, 6, 10, 12],
[ 1, 3, 7, 11, 13],
[ 2, 4, 8, 12, 14],
[ 5, 7, 11, 15, 17],
[ 6, 8, 12, 16, 18],
[ 7, 9, 13, 17, 19]])

Prueba de tiempo de ejecución

In [183]: a = np.random.randint(0,255,(1024,1024))
In [184]: %timeit im2col_sliding(img, (8,8), skip=1)
...: %timeit im2col_sliding_broadcasting(img, (8,8), stepsize=1)
...: %timeit im2col_sliding_strided(img, (8,8), stepsize=1)
...: %timeit im2col_sliding_strided_v2(img, (8,8), stepsize=1)
...:
1 loops, best of 3: 1.29 s per loop
1 loops, best of 3: 226 ms per loop
10 loops, best of 3: 84.5 ms per loop
10 loops, best of 3: 111 ms per loop
In [185]: %timeit im2col_sliding(img, (8,8), skip=4)
...: %timeit im2col_sliding_broadcasting(img, (8,8), stepsize=4)
...: %timeit im2col_sliding_strided(img, (8,8), stepsize=4)
...: %timeit im2col_sliding_strided_v2(img, (8,8), stepsize=4)
...:
1 loops, best of 3: 1.31 s per loop
10 loops, best of 3: 104 ms per loop
10 loops, best of 3: 84.4 ms per loop
10 loops, best of 3: 109 ms per loop

¡Alrededor de 16x aceleración allí con el método strided sobre la versión original de loopy!