Внесите MATLAB's im2col 'slide' в Python

Вопрос: Как ускорить это?

Ниже приведена реализация «скользящего» im2col «Matlab» с дополнительной функцией возврата каждого n-го столбца. Функция принимает изображение (или любой 2-мерный массив) и слайды слева направо, сверху вниз, выделяя каждый дублирующий суб-образ заданного размера и возвращая массив, столбцы которого являются суб-изображениями.

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] 

пример:

 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 

возвращает:

 [[ 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.]] 

Производительность im2col_sliding(big_matrix, (8, 8)) , особенно учитывая, называю ли я im2col_sliding(big_matrix, (8, 8)) (62001 столбцов) или im2col_sliding(big_matrix, (8, 8), 10) (6201 столбцов, сохраняя только каждый 10-й вектор) займет столько же времени [где big_matrix имеет размер 256 x 256].

Я ищу любые идеи, чтобы ускорить это.

5 Solutions collect form web for “Внесите MATLAB's im2col 'slide' в Python”

Подход №1

Мы могли бы использовать некоторые broadcasting здесь, чтобы получить все индексы всех этих скользящих окон за один раз и, таким образом, индексирование достигнет vectorized solution . Это вдохновляет Efficient Implementation of im2col and col2im .

Вот реализация –

 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]) 

Подход №2

Используя недавно полученные знания о NumPy array strides которые позволяют нам создавать такие скользящие окна, у нас будет еще одно эффективное решение –

 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] 

Подход №3

Метод strided, указанный в предыдущем подходе, был включен в scikit-image для менее беспорядочного, например,

 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] 

Образцы прогона –

 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]]) 

Тест времени выполнения

 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 

Около 16x -кратного ускорения там с методом strided над исходной петлевой версией!

Для скользящего окна по различным каналам изображения мы можем использовать обновленную версию кода, предоставленного Divakar @ Реализовать im2col «перемещение» MATLAB в Python , т. Е.

 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()) 

Прогон пробного тестирования

 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] 

Для дальнейшего повышения производительности (например, при свертке) мы также можем использовать пакетную реализацию на основе расширенного кода, предоставленную M iLiLi @ Реализация Matlab's im2col «скользящий» в python , т.е.

 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) 

Тестирование пробной пробы:

 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]]] 

Я не думаю, что вы можете сделать лучше. Ясно, что вам нужно запустить цикл размера

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

Но вы берете 3, 3 патча в вашем примере, а не 2, 2.

Вы также можете добавить дальнейшую оптимизацию к ответу М Элии (хотя это и не так важно)

Вместо того, чтобы «применять» пропустить в самом конце, вы можете применить его при создании смещенных массивов, поэтому вместо:

 # 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()) 

Вы добавили бы пропуски, используя параметр шага функции arge of numge:

 # 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]) 

а затем просто добавьте массив смещений без индексирования [::]

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

При небольших значениях пропуска он практически не сохраняет время:

 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 работе 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 

Однако с большими значениями пропуска это экономит немного больше времени:

 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 
  • WindowsError: Система не может найти файл, указанный для pytesseract
  • Как работает сборка мусора с несколькими запущенными процессами / потоками?
  • Как выбрать подмножество тестов в pytest с использованием настраиваемых маркеров в параметрах
  • Как выполнять итерации по значениям, содержащим списки и удалять элементы?
  • Python __init__.py и классы
  • ImportError: нет модуля с именем twisted.persisted.styles
  • Intellij Python не импортирует из .pydevproject
  • Как изменить пароль пользователя Linux из python
  • Python - лучший язык программирования в мире.