Berechnen von Entfernungen zwischen eindeutigen Python-Array-Regionen?

Question

Ich habe ein Raster mit einer Reihe einzigartiger ID-Patches/Regionen, die ich in ein zweidimensionales Python-Numpy-Array konvertiert habe. Ich möchte paarweise Euklidische Abstände zwischen allen Regionen berechnen, um den Mindestabstand zu erhalten, der die nächstgelegenen Kanten jedes Rasterfeldes trennt. Da das Array ursprünglich ein Raster war, muss eine Lösung diagonale Abstände zwischen den Zellen berücksichtigen (ich kann immer alle in Zellen gemessenen Abstände durch Multiplikation mit der Rasterauflösung in Meter umrechnen).

Ich habe experimentiert mit der cdist Funktion von scipy.spatial.distance wie in this answer to a related question vorgeschlagen, aber bisher konnte ich mein Problem mit der verfügbaren Dokumentation nicht lösen. Als Endergebnis hätte ich idealerweise ein 3 x X-Array in Form von "von ID zu ID, Abstand", einschließlich der Abstände zwischen allen möglichen Kombinationen von Regionen.

Hier ist ein Beispieldatensatz meine Eingangsdaten ähnelt:

import numpy as np 
import matplotlib.pyplot as plt 

# Sample study area array 
example_array = np.array([[0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0], 
          [0, 0, 2, 0, 2, 2, 0, 6, 0, 3, 3, 3], 
          [0, 0, 0, 0, 2, 2, 0, 0, 0, 3, 3, 3], 
          [0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3, 0], 
          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 3], 
          [1, 1, 0, 0, 0, 0, 0, 0, 3, 3, 3, 3], 
          [1, 1, 1, 0, 0, 0, 3, 3, 3, 0, 0, 3], 
          [1, 1, 1, 0, 0, 0, 3, 3, 3, 0, 0, 0], 
          [1, 1, 1, 0, 0, 0, 3, 3, 3, 0, 0, 0], 
          [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
          [1, 0, 1, 0, 0, 0, 0, 5, 5, 0, 0, 0], 
          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4]]) 

# Plot array 
plt.imshow(example_array, cmap="spectral", interpolation='nearest') 

Answer 1

Entfernungen zwischen markierten Regionen eines Bildes, mit dem folgenden Code berechnet werden

import itertools 
from scipy.spatial.distance import cdist 

# making sure that IDs are integer 
example_array = np.asarray(example_array, dtype=np.int) 
# we assume that IDs start from 1, so we have n-1 unique IDs between 1 and n 
n = example_array.max() 

indexes = [] 
for k in range(1, n): 
    tmp = np.nonzero(example_array == k) 
    tmp = np.asarray(tmp).T 
    indexes.append(tmp) 

# calculating the distance matrix 
distance_matrix = np.zeros((n-1, n-1), dtype=np.float) 
for i, j in itertools.combinations(range(n-1), 2): 
    # use squared Euclidean distance (more efficient), and take the square root only of the single element we are interested in. 
    d2 = cdist(indexes[i], indexes[j], metric='sqeuclidean') 
    distance_matrix[i, j] = distance_matrix[j, i] = d2.min()**0.5 

# mapping the distance matrix to labeled IDs (could be improved/extended) 
labels_i, labels_j = np.meshgrid(range(1, n), range(1, n)) 
results = np.dstack((labels_i, labels_j, distance_matrix)).reshape((-1, 3)) 

print(distance_matrix) 
print(results) 

Diese ganze Zahl annimmt IDs, und müsste erweitert werden, wenn dies nicht der Fall ist. Beispielsweise mit den Testdaten über die berechnete Abstandsmatrix ist,

# From 1    2   3   4    5   # To 
[[ 0.   4.12310563 4.   9.05538514 5.  ] # 1 
[ 4.12310563 0.   3.16227766 10.81665383 8.24621125] # 2 
[ 4.   3.16227766 0.   4.24264069 2.  ] # 3 
[ 9.05538514 10.81665383 4.24264069 0.   3.16227766] # 4 
[ 5.   8.24621125 2.   3.16227766 0.  ]] # 5 

während der volle Ausgang here gefunden werden kann. Beachten Sie, dass dies die euklidische Entfernung von der Mitte jedes Pixels ist. Zum Beispiel ist der Abstand zwischen den Zonen 1 und 3 2,0, während sie durch 1 Pixel getrennt sind.

Dies ist ein Brute-Force-Ansatz, bei dem wir alle paarweisen Abstände zwischen Pixeln verschiedener Regionen berechnen. Dies sollte für die meisten Anwendungen ausreichen. Wenn Sie jedoch eine bessere Leistung benötigen, sollten Sie einen Blick auf scipy.spatial.cKDTree werfen, der den Mindestabstand zwischen zwei Regionen im Vergleich zu cdist effizienter berechnen würde.