区域提案归一化的最快算法

Question

为了标准化区域提议算法（即，对图像的每个 X-by-Y 区域应用回归），我需要在对每个提议的激活求和时创建区域提议标准化。目前，对于图像的 128x128 补丁，在 Python 我是运行这段代码

region_normalization = np.zeros(image.shape)
for x in range(0,image.shape[0]-128):
    for y in range(0,image.shape[0]-128):
        region_normalization[x:x+128,y:y+128] = 
        np.add(region_normalization[x:x+128,y:y+128],1)`

但这特别低效。这个算法的更快 and/or 更多 pythonic 实现是什么？

谢谢！

Answer 1

对其进行逆向工程！

好吧，让我们看一下小图像和较小 N 情况下的输出，因为我们将尝试对这段循环代码进行逆向工程。因此，对于 N = 4（在原始情况下 N 是 128）和 image.shape = (10,10)，我们将有：

In [106]: region_normalization
Out[106]: 
array([[ 1,  2,  3,  4,  4,  4,  3,  2,  1,  0],
       [ 2,  4,  6,  8,  8,  8,  6,  4,  2,  0],
       [ 3,  6,  9, 12, 12, 12,  9,  6,  3,  0],
       [ 4,  8, 12, 16, 16, 16, 12,  8,  4,  0],
       [ 4,  8, 12, 16, 16, 16, 12,  8,  4,  0],
       [ 4,  8, 12, 16, 16, 16, 12,  8,  4,  0],
       [ 3,  6,  9, 12, 12, 12,  9,  6,  3,  0],
       [ 2,  4,  6,  8,  8,  8,  6,  4,  2,  0],
       [ 1,  2,  3,  4,  4,  4,  3,  2,  1,  0],
       [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0]])

我们确实在那里看到了对称性，这种对称性恰好跨越 X 和 Y 轴。我们突然想到的另一件事是每个元素都是其起始行和列元素的乘积。因此，我们的想法是获取第一行和第一列，并在它们的元素之间执行逐元素乘法。由于第一行和第一列相同，我们只需要获取一次并将其与附加轴一起使用，让 NumPy broadcasting 处理这些乘法。因此，实现将是 -

N = 128
a1D = np.hstack((np.arange(N)+1,np.full(image.shape[0]-2*N-1,N,dtype=int),\
                                                          np.arange(N,-1,-1)))

out = a1D[:,None]*a1D

运行时测试

In [137]: def original_app(image):
     ...:     region_normalization = np.zeros(image.shape,dtype=int)
     ...:     for x in range(0,image.shape[0]-128):
     ...:         for y in range(0,image.shape[0]-128):
     ...:             region_normalization[x:x+128,y:y+128] = \
     ...:             np.add(region_normalization[x:x+128,y:y+128],1)
     ...:     return region_normalization
     ...: 
     ...: def vectorized_app(image):        
     ...:     N = 128
     ...:     a1D = np.hstack((np.arange(N)+1,np.full(image.shape[0]-2*N-1,N,\
     ...:                                        dtype=int),np.arange(N,-1,-1)))
     ...: 
     ...:     return a1D[:,None]*a1D
     ...: 

In [138]: # Input
     ...: image = np.random.randint(0,255,(512,512))

In [139]: np.allclose(original_app(image),vectorized_app(image)) #Verify
Out[139]: True

In [140]: %timeit original_app(image)
1 loops, best of 3: 13 s per loop

In [141]: %timeit vectorized_app(image)
1000 loops, best of 3: 1.4 ms per loop

超级加速！

Answer 2

重归一化中任何给定点 i,j 的值等于包含它的 128x128 windows 的数量。请注意，这是 x 轴和 y 轴上自由度的乘积。所以我们所要做的就是计算出每个可能的 x 和 y 值的自由度，然后使用广播或 np.outer 来获得结果。

import numpy as np
image = np.zeros((200,200))

window=128
region_normalization = np.zeros(image.shape)
for x in range(0,image.shape[0]-window):
    for y in range(0,image.shape[0]-window):
        region_normalization[x:x+window,y:y+window] = np.add(region_normalization[x:x+window,y:y+window],1)

def sliding(n, window=128):
    arr = np.zeros(n)
    for i in xrange(n):
        #want to find all s such that 0<=s<=i<s+128<n
        #thus, s < min(i+1, n-128), s >= max(0, i-window+1) 
        arr[i] = min(i+1, n-window) - max(0,i-window+1)
    return arr


def normalizer(image, window = 128):
    m,n = image.shape   
    res = np.zeros(shape)
    if m < window or n < window: return res
    x_sliding = sliding(m, window)
    y_sliding = sliding(n, window)
    print x_sliding
    res = np.outer(x_sliding,y_sliding)
    return res

print np.allclose(normalizer(image, window=128),region_normalization)

区域提案归一化的最快算法

Quickest Algorithmn for Normalization of Region Proposals

python

performance

numpy

normalization

vectorization