使用Numpy高效计算累加面积表

Question

我正在尝试用Python和Numpy计算一个特征计数矩阵的累加区域表。现在我使用的代码是：

def summed_area_table(img):

    table = np.zeros_like(img).astype(int)

    for row in range(img.shape[0]):
        for col in range(img.shape[1]):

            if (row > 0) and (col > 0):
                table[row, col] = (img[row, col] +
                                   table[row, col - 1] +
                                   table[row - 1, col] -
                                   table[row - 1, col - 1])
            elif row > 0:   
                table[row, col] = img[row, col] + table[row - 1, col]
            elif col > 0:
                table[row, col] = img[row, col] + table[row, col - 1]
            else:
                table[row, col] = img[row, col]

    return table

上面的代码在一个3200 x 1400的数组上计算大约需要35秒。有没有什么方法可以用Numpy的技巧来加速这个计算？我意识到主要的速度问题出在嵌套的Python循环上，但我不知道怎么避免它们。

Answer 1

NumPy有一个叫做cumsum的函数，用来计算累积和。也就是说，它可以把一系列数字加起来，得到一个新的数字序列。如果你把这个函数用两次，就能得到你想要的表格：

import numpy as np

A = np.random.randint(0, 10, (3, 4))

print A
print A.cumsum(axis=0).cumsum(axis=1)

输出结果：

[[7 4 7 2]
 [6 9 9 5]
 [6 6 7 6]]
[[ 7 11 18 20]
 [13 26 42 49]
 [19 38 61 74]]

性能分析： (https://stackoverflow.com/a/25351344/3419103)

import numpy as np
import time

A = np.random.randint(0, 10, (3200, 1400))

t = time.time()
S = A.cumsum(axis=0).cumsum(axis=1)
print np.round_(time.time() - t, 3), 'sec elapsed'

输出结果：

0.15 sec elapsed