Làm thế nào để tìm minima địa phương của một mảng đa chiều trơn tru trong NumPy hiệu quả?

Question

Giả sử tôi có một mảng trong NumPy chứa các đánh giá của một hàm có khả năng liên tục khác nhau và tôi muốn tìm minima cục bộ. Không có tiếng ồn, vì vậy mọi điểm có giá trị thấp hơn giá trị của tất cả các nước láng giềng đều đáp ứng tiêu chí của tôi cho một mức tối thiểu địa phương.

Tôi có hiểu danh sách sau đây mà làm việc cho một mảng hai chiều, bỏ qua tiểu tiềm năng về ranh giới:

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 

Tuy nhiên, điều này là khá chậm. Tôi cũng muốn làm việc này cho bất kỳ số thứ nguyên nào. Ví dụ, có một cách dễ dàng để có được tất cả những người hàng xóm của một điểm trong một mảng của bất kỳ kích thước? Hoặc tôi đang tiếp cận vấn đề này một cách sai lầm hoàn toàn? Tôi có nên sử dụng numpy.gradient() để thay thế không?

Answer 1

Vị trí của cực tiểu địa phương có thể được tìm thấy cho một loạt các khía cạnh tùy ý sử dụng Ivan 's detect_peaks function, với những thay đổi nhỏ:

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)  

mà bạn có thể sử dụng như thế này:

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

Điều này nói rằng cực tiểu xuất hiện tại các chỉ số [0,0,3], [0,4,0], [1,1,1] và [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

Hãy thử điều này cho 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))) 

này sẽ trả lại cho bạn một mảng array2d giống như với True/False nơi cực tiểu địa phương (bốn người hàng xóm) đang nằm.