Schnellster Algorithmus für die Normalisierung von Regionsvorschlägen

Question

Um den Regionsvorschlagsalgorithmus zu normalisieren (dh Regression auf jeden X-by-Y-Bereich eines Bildes anzuwenden), muss ich eine Regionsvorschlagsnormalisierung erzeugen, wenn die Aktivierung von jeder Vorschlag. Derzeit für eine 128x128-Patch eines Bildes, in Python Ich laufe dieses Stück Code

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

aber dies ist besonders ineffizient. Was wäre eine schnellere und/oder mehr pythische Implementierung dieses Algorithmus?

Danke!

Answer 1

Reverse engineer it!

Nun, werfen wir einen Blick auf die Ausgabe für ein kleines Bild und kleinere N Fall, wie wir versuchen werden, diesen loopy-Code zu rekonstruieren. Also, mit N = 4 (wo N128 im ursprünglichen Fall war) und Bild.Form = (10,10), würden wir haben:

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

Wir sehen eine Symmetrie gibt und diese Symmetrie geschieht über beide X und Y Achsen zu sein . Eine weitere Sache, die bei uns herausspringt, ist, dass jedes Element ein Produkt seiner Startzeile und seines Spaltenelements ist. Die Idee wäre also, die erste Zeile und die erste Spalte zu erhalten und elementweise Multiplikation zwischen ihren Elementen durchzuführen. Da die erste Zeile und die erste Spalte identisch sind, müssen wir sie nur einmal erhalten und sie mit einer zusätzlichen Achse verwenden und NumPy broadcasting diese Multiplikationen verarbeiten lassen. Somit würde die Umsetzung sein -

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 

Runtime Test

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 

super dort Speedup!

Answer 2

Der Wert eines beliebigen Punktes i, j in Ihrer Renormierung ist gleich der Anzahl der 128x128 Fenster, die ihn enthalten. Beachten Sie, dass dies das Produkt der Freiheitsgrade auf der x-Achse und auf der y-Achse ist. Alles, was wir tun müssen, ist, die Freiheitsgrade für jeden möglichen x- und y-Wert herauszufinden und dann Broadcasting oder np.outer zu verwenden, um das Ergebnis zu erhalten.

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)