петля петли очень медленно

Question

У меня есть вопрос, касающийся скорости циклов в Python. Я создал следующие циклы для заполнения значений в моем массиве, но это очень медленно. Есть ли способ сделать это быстрее?

winW = 1    
winH = 200    
runlength = np.zeros(shape=(img.shape[0], img.shape[1]))


for y in range(0, img.shape[0] - winH, 1):
   for x in range(0, img.shape[1] - winW, 1):
      runlength[y, x] += np.sum(img[y:y + winH, x:x + winW]) / (winH * winW)
      runlength[y + winH, x] += np.sum(img[y:y + winH, x:x + winW]) / (winH * winW)

Спасибо за вашу помощь

Изменить: Я точно, что я могу использовать только NumPy, но не Scipy

Answer 1

Позвольте мне описать, как ускорить первую операцию в цикле for, заданную

runlength[y, x] += np.sum(img[y:y + winH, x:x + winW]) / (winH * winW)

По сути, вы перемещаете прямоугольник шириной winW и высотой winH по изображению. Вы начинаете с верхнего левого угла прямоугольника в точке (0,0) изображения, затем суммируете все значения в изображении, которые лежат ниже этого прямоугольника, и делите их на общее количество точек. Выход в позиции (0,0) - это число. Затем вы сдвигаете прямоугольник на один вправо и повторяете процедуру, пока не окажетесь у правого края изображения. Вы двигаетесь на один ряд вниз и повторяете.

В терминах обработки изображений: к изображению применяется маска пространственного фильтра. Фильтр представляет собой средний фильтр ширины winW и высоты winH.

Чтобы реализовать это эффективно, вы можете использовать функцию scipy.ndimage.correlate. input - ваше изображение, weights содержит вес, на который умножается элемент ниже прямоугольника. В данном случае это массив с размерами (winH, winW), где каждый элемент содержит число 1 / (winH * winW). Таким образом, каждая точка изображения, которая лежит ниже прямоугольника, умножается на 1 / (winH * winW), а затем все суммируется.

Чтобы точно соответствовать вашему алгоритму, нам нужно установить origin в (-np.floor(winH/2), -np.floor(winW/2)), чтобы указать, что среднее значение прямоугольника находится в верхнем правом углу прямоугольника в выходных данных.

Наконец, чтобы точно соответствовать вашему алгоритму, мы должны установить все точки ниже (img.shape[0] - winH) или справа от (img.shape[1] - winW) на ноль. Таким образом, цикл for можно заменить на

runlength_corr = correlate(input=img,
                           weights=np.ones((winH, winW)) / (winW * winH),
                           origin=(-np.floor(winH/2), -np.floor(winW/2)))
runlength_corr[(img.shape[0] - winH):, :] = 0
runlength_corr[:, (img.shape[1] - winW):] = 0

Я сравнил время выполнения вложенных циклов for и метод correlate на тестовом изображении размером 512 на 512:

For-loops: Elapsed time: 0.665 sec
Correlate: Elapsed time: 0.085 sec

Таким образом, это дает хорошее ускорение в 8 раз. Сумма абсолютных разностей по всему выходному сигналу составляет всего лишь 7.04e-09, поэтому выходные данные обоих методов по существу одинаковы.

Answer 2

Для начала, вы, кажется, рассчитываете одно и то же количество дважды, внутри своего цикла. Это само по себе может наполовину сократить время работы

Во-вторых, если winW всегда 1, то np.sum(img[y:y + winH, x:x + winW]) просто np.sum(img[y:y + winH, x]). Это должно немного ускорить его.

Остается только то, как вы можете ускорить np.sum(img[y:y + winH, x]). Вы можете начать с расчета

sum0 = np.sum(img[0: 0 + winH, x])

Теперь обратите внимание, что количество

sum1 = np.sum(img[1: 1 + winH, x])

отличается от предыдущего только на два пикселя, поэтому он равен sum0 - img[0, x] + img[1 + winH, x]. Для следующего y

sum2 = sum1 - img[1, x] + img[2 + winH, x]`

и т. Д.