¿Cómo puedo mejorar la eficiencia de este numpy loop?

Question

Tengo un numpy array que contiene etiquetas. Me gustaría calcular un número para cada etiqueta según su tamaño y cuadro delimitador. ¿Cómo puedo escribir esto de manera más eficiente para que sea realista de usar en matrices grandes (~ 15000 etiquetas)?

A = array([[ 1, 1, 0, 3, 3], 
      [ 1, 1, 0, 0, 0], 
      [ 1, 0, 0, 2, 2], 
      [ 1, 0, 2, 2, 2]]) 

B = zeros(4) 

for label in range(1, 4): 
    # get the bounding box of the label 
    label_points = argwhere(A == label) 
    (y0, x0), (y1, x1) = label_points.min(0), label_points.max(0) + 1 

    # assume I've computed the size of each label in a numpy array size_A 
    B[ label ] = myfunc(y0, x0, y1, x1, size_A[label]) 

Answer 1

que no era realmente capaz de implementar esto de manera eficiente el uso de algunas funciones NumPy vectorizado, por lo que tal vez una implementación de Python inteligente será más rápido.

def first_row(a, labels): 
    d = {} 
    d_setdefault = d.setdefault 
    len_ = len 
    num_labels = len_(labels) 
    for i, row in enumerate(a): 
     for label in row: 
      d_setdefault(label, i) 
     if len_(d) == num_labels: 
      break 
    return d 

Esta función devuelve un diccionario mapeo de cada etiqueta con el índice de la primera fila que aparece. La aplicación de la función a A, A.T, A[::-1] y A.T[::-1] también le da la primera columna, así como la última fila y columna.

Si prefiere una lista en lugar de un diccionario, puede convertir el diccionario en una lista usando map(d.get, labels). Alternativamente, puede usar una matriz NumPy en lugar de un diccionario desde el principio, pero perderá la capacidad de abandonar el ciclo tan pronto como se encuentren todas las etiquetas.

Me interesaría si (y cuánto) esto realmente acelera su código, pero estoy seguro de que es más rápido que su solución original.

Answer 2

El cuello de botella performace parece ser la llamada al argmax. Se puede evitarse cambiando el bucle de la siguiente manera (sólo computar y0, y1, pero fácil generalizar a x0, x1):

for label in range(1, 4): 
    comp = (A == label) 
    yminind = comp.argmax(0) 
    ymin = comp.max(0) 
    ymaxind = comp.shape[0] - comp[::-1].argmax(0) 
    y0 = yminind[ymin].min() 
    y1 = ymaxind[ymin].max() 

no estoy seguro acerca de la razón de la diferencia de rendimiento, pero una de las razones podría ser que todas las operaciones como ==, argmax y max puedan preasignar su matriz de salida directamente desde la forma de la matriz de entrada, que no es posible para argwhere.

Answer 3

Algoritmo:

1. cambio de la matriz de una dimensión
2. obtener el índice ordenar por argsort()
3. obtener la versión ordenada de en la matriz de dimensión como sorted_A
4. uso en() y diff() para encontrar la posición de cambio de etiqueta en sorted_A
5. utilice la posición de cambio y el índice de clasificación para obtener la posición original de la etiqueta en una dimensión.
6. calcule la ubicación de dos dimensiones desde la posición de dimensión activada.

para matriz grande como (7000, 9000), se puede completar el cálculo en 30 segundos.

Aquí está el código:

import numpy as np 

A = np.array([[ 1, 1, 0, 3, 3], 
      [ 1, 1, 0, 0, 0], 
      [ 1, 0, 0, 2, 2], 
      [ 1, 0, 2, 2, 2]]) 

def label_range(A): 
    from itertools import izip_longest 
    h, w = A.shape 
    tmp = A.reshape(-1) 

    index = np.argsort(tmp) 
    sorted_A = tmp[index] 
    pos = np.where(np.diff(sorted_A))[0]+1 
    for p1,p2 in izip_longest(pos,pos[1:]): 
     label_index = index[p1:p2] 
     y = label_index // w 
     x = label_index % w 

     x0 = np.min(x) 
     x1 = np.max(x)+1 
     y0 = np.min(y) 
     y1 = np.max(y)+1 
     label = tmp[label_index[0]] 

     yield label,x0,y0,x1,y1 

for label,x0,y0,x1,y1 in label_range(A): 
    print "%d:(%d,%d)-(%d,%d)" % (label, x0,y0,x1,y1) 

#B = np.random.randint(0, 100, (7000, 9000)) 
#list(label_range(B)) 

Answer 4

Otro método:

uso bincount() para obtener etiquetas cuentan en cada fila y columna, y guardar la información en filas y columnas matriz.

Para cada etiqueta solo necesita buscar el rango en filas y columnas.Es más rápido que ordenar, en mi pc, puede hacer el cálculo en unos segundos.

def label_range2(A): 
    maxlabel = np.max(A)+1 
    h, w = A.shape 
    rows = np.zeros((h, maxlabel), np.bool) 
    for row in xrange(h): 
     rows[row,:] = np.bincount(A[row,:], minlength=maxlabel) > 0 

    cols = np.zeros((w, maxlabel), np.bool) 
    for col in xrange(w): 
     cols[col,:] =np.bincount(A[:,col], minlength=maxlabel) > 0 

    for label in xrange(1, maxlabel): 
     row = rows[:, label] 
     col = cols[:, label] 
     y = np.where(row)[0] 
     x = np.where(col)[0] 
     x0 = np.min(x) 
     x1 = np.max(x)+1 
     y0 = np.min(y) 
     y1 = np.max(y)+1   
     yield label, x0,y0,x1,y1 

Answer 5

Utilizando PyPy puede simplemente ejecutar el ciclo y no preocuparse por la vectorización. Debería ser rápido.