Come trovare i minimi locali di un array multidimensionale uniforme in NumPy in modo efficiente?

Question

Supponiamo di avere un array in NumPy contenente valutazioni di una funzione continua differenziabile, e voglio trovare i minimi locali. Non c'è rumore, quindi ogni punto il cui valore è inferiore ai valori di tutti i suoi vicini soddisfa il mio criterio per un minimo locale.

Ho la seguente lista di comprensione, che lavora per una matrice bidimensionale, ignorando il potenziale minimi sui confini:

import numpy as N 

def local_minima(array2d): 
    local_minima = [ index 
        for index in N.ndindex(array2d.shape) 
        if index[0] > 0 
        if index[1] > 0 
        if index[0] < array2d.shape[0] - 1 
        if index[1] < array2d.shape[1] - 1 
        if array2d[index] < array2d[index[0] - 1, index[1] - 1] 
        if array2d[index] < array2d[index[0] - 1, index[1]] 
        if array2d[index] < array2d[index[0] - 1, index[1] + 1] 
        if array2d[index] < array2d[index[0], index[1] - 1] 
        if array2d[index] < array2d[index[0], index[1] + 1] 
        if array2d[index] < array2d[index[0] + 1, index[1] - 1] 
        if array2d[index] < array2d[index[0] + 1, index[1]] 
        if array2d[index] < array2d[index[0] + 1, index[1] + 1] 
        ] 
    return local_minima 

Tuttavia, questo è piuttosto lento. Mi piacerebbe anche farlo funzionare per qualsiasi numero di dimensioni. Ad esempio, esiste un modo semplice per ottenere tutti i vicini di un punto in un array di qualsiasi dimensione? O sto affrontando questo problema nel modo sbagliato del tutto? Dovrei usare numpy.gradient()?

Answer 1

La posizione dei minimi locali può essere trovato per una vasta gamma di dimensione arbitraria utilizzando Ivan s' detect_peaks function, con piccole modifiche:

import numpy as np 
import scipy.ndimage.filters as filters 
import scipy.ndimage.morphology as morphology 

def detect_local_minima(arr): 
    # https://stackoverflow.com/questions/3684484/peak-detection-in-a-2d-array/3689710#3689710 
    """ 
    Takes an array and detects the troughs using the local maximum filter. 
    Returns a boolean mask of the troughs (i.e. 1 when 
    the pixel's value is the neighborhood maximum, 0 otherwise) 
    """ 
    # define an connected neighborhood 
    # http://www.scipy.org/doc/api_docs/SciPy.ndimage.morphology.html#generate_binary_structure 
    neighborhood = morphology.generate_binary_structure(len(arr.shape),2) 
    # apply the local minimum filter; all locations of minimum value 
    # in their neighborhood are set to 1 
    # http://www.scipy.org/doc/api_docs/SciPy.ndimage.filters.html#minimum_filter 
    local_min = (filters.minimum_filter(arr, footprint=neighborhood)==arr) 
    # local_min is a mask that contains the peaks we are 
    # looking for, but also the background. 
    # In order to isolate the peaks we must remove the background from the mask. 
    # 
    # we create the mask of the background 
    background = (arr==0) 
    # 
    # a little technicality: we must erode the background in order to 
    # successfully subtract it from local_min, otherwise a line will 
    # appear along the background border (artifact of the local minimum filter) 
    # http://www.scipy.org/doc/api_docs/SciPy.ndimage.morphology.html#binary_erosion 
    eroded_background = morphology.binary_erosion(
     background, structure=neighborhood, border_value=1) 
    # 
    # we obtain the final mask, containing only peaks, 
    # by removing the background from the local_min mask 
    detected_minima = local_min - eroded_background 
    return np.where(detected_minima)  

che può essere utilizzato in questo modo:

arr=np.array([[[0,0,0,-1],[0,0,0,0],[0,0,0,0],[0,0,0,0],[-1,0,0,0]], 
       [[0,0,0,0],[0,-1,0,0],[0,0,0,0],[0,0,0,-1],[0,0,0,0]]]) 
local_minima_locations = detect_local_minima(arr) 
print(arr) 
# [[[ 0 0 0 -1] 
# [ 0 0 0 0] 
# [ 0 0 0 0] 
# [ 0 0 0 0] 
# [-1 0 0 0]] 

# [[ 0 0 0 0] 
# [ 0 -1 0 0] 
# [ 0 0 0 0] 
# [ 0 0 0 -1] 
# [ 0 0 0 0]]] 

Questo dice che i minimi si verificano agli indici [0,0,3], [0,4,0], [1,1,1] e [1,3,3]:

print(local_minima_locations) 
# (array([0, 0, 1, 1]), array([0, 4, 1, 3]), array([3, 0, 1, 3])) 
print(arr[local_minima_locations]) 
# [-1 -1 -1 -1] 

Answer 2

Prova questo per 2D:

import numpy as N 

def local_minima(array2d): 
    return ((array2d <= N.roll(array2d, 1, 0)) & 
      (array2d <= N.roll(array2d, -1, 0)) & 
      (array2d <= N.roll(array2d, 1, 1)) & 
      (array2d <= N.roll(array2d, -1, 1))) 

Questo lo restituisca una matrice array2d simile con cui minimi locali Vero/Falso (quattro vicini di casa) si trovano.