Efektywna identyfikacja sąsiednich elementów w macierzach numpy

Question

Mam macierz od 100 do 100 numpy. Macierz jest w większości wypełniona zerami, ale zawiera również pewną liczbę int. Na przykład:

[0 0 0 0 0 0 0 1] 
[0 2 2 0 0 0 0 0] 
[0 0 2 0 0 0 0 0] False 
[0 0 0 0 0 0 0 0] 
[0 3 3 0 0 0 0 0] 

Co jest najbardziej skutecznym sposobem na określenie, czy macierz zawiera dowolną liczbę sąsiadujących wskazówki z różnych typów?

Powyższy przykład zwróci wartość Fałsz. Oto prawdziwy przykład, z wierszem zawierającym wskazane sąsiedztwo:

[0 0 0 0 0 0 0 1] 
[0 2 2 1 1 0 0 0] <---- True 
[0 0 2 0 0 0 0 0] 
[0 0 0 0 0 0 0 0] 
[0 3 3 0 0 0 0 0] 

Przekątne nie są traktowane jako sąsiadujące. Tak więc ten przykład również zwróciłby fałsz:

[0 0 0 1 1 1 1 1] 
[0 2 2 0 1 0 0 0] 
[0 0 2 0 0 0 0 0] False 
[0 3 0 0 0 0 0 0] 
[3 3 3 0 0 0 0 0] 

Nie muszę identyfikować położenia przylegania, tylko tego, czy istnieje z nie.

Obecnie nie mogę zrobić nic lepszego, niż znaleźć każdy element zerowy w macierzy, a następnie sprawdzić jego 4 elementy flankujące.

Dzięki za wszystkie wspaniałe odpowiedzi.

Answer 1

Jeśli można użyć scipy będzie to dość łatwe przy użyciu ndimage.label i ndimage.labeled_comprehension:

import numpy as np 
from scipy import ndimage 

def multiple_unique_item(array): 
    return len(np.unique(array)) > 1 

def adjacent_diff(array): 
    labeled_array, num_labels = ndimage.label(array) 
    labels = np.arange(1, num_labels+1) 
    any_multiple = ndimage.labeled_comprehension(array, labeled_array, labels, 
               multiple_unique_item, bool, 0) 
    return any_multiple.any() 

label domyślnie etykietuje sąsiednie wartości inne niż 0 bez przekątnych. Następnie zrozumienie przekazuje wszystkie wartości związane z etykietą do funkcji pomocniczej - która sprawdza, czy występuje więcej niż jedna unikalna wartość. Na końcu sprawdza, czy etykieta ma więcej niż jedną wartość i zwraca to.

Aby to przetestować na swoich tablicach testowych wejściowych:

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

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

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

>>> adjacent_diff(arr1) 
True 
>>> adjacent_diff(arr2) 
False 
>>> adjacent_diff(arr3) 
False 

Answer 2

Patrząc na opis problemu, prawdopodobnie nie jest to zbyt dużo wysiłku obliczeniowego, aby sprawdzić każdą możliwą niezerową liczbę całkowitą dla jego pozycji w tablicy i sprawdzić, czy są przecięcia. Teraz jest to generalnie przesada, ale w twojej skali może działać: możesz uzyskać indeksy każdej kolekcji liczb całkowitych i obliczyć ich odległości za pomocą scipy.spatial.distance.cdist. Jestem pewien, że niektóre inteligentne rozwiązanie oparte na diff lub coś innego jest bardziej efektywne, ale i tak miałem zabawy:

import numpy as np 
from scipy.spatial.distance import cdist 
from itertools import combinations 

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

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

def overlaps_eh(M): 
    uniques = np.delete(np.unique(M),0) # get integers present 
    unival_inds = [np.transpose(np.where(M==unival)) for unival in uniques] 
    # unival_inds[k] contains the i,j indices of each element with the kth unique value 

    for i1,i2 in combinations(range(len(unival_inds)),2): 
     if np.any(cdist(unival_inds[i1],unival_inds[i2],'cityblock')==1): 
      return True 
    # if we're here: no adjacencies 
    return False 

Najpierw musimy zebrać niezerowe unikalne elementy do tablicy uniques macierzy. Następnie dla każdej unikalnej wartości znajdujemy indeksy i,j każdego elementu w tablicy wejściowej, która ma tę wartość. Następnie sprawdzamy każdą parę unikatowych wartości (generowanych przy użyciu itertools.combinations) i używamy scipy.spatial.distance.cdist do mierzenia odległości parami każdej pary elementów macierzy. Używając odległości Manhattan, jeśli dowolna para elementów ma odległość 1, sąsiadują ze sobą. Musimy więc tylko zwrócić True, jeśli którakolwiek z tych odległości wynosi 1, w przeciwnym razie zwracamy False.

Answer 3

Oto rozwiązanie przy użyciu masked array:

import numpy as np 
import numpy.ma as ma 
a = np.array([[0,1,0], [0,1,0], [2,2,2]]) # sample data 
x = ma.masked_equal(a, 0)     # mask zeros 
adjacencies = np.count_nonzero(np.diff(x, axis=0).filled(0)) + np.count_nonzero(np.diff(x, axis=1).filled(0)) 

w ostatnim wierszu, diff jest stosowany do zamaskowanego tablicy (zerowe wpisy ignorowane); niezerowe wpisy w diff oznaczają sąsiednie różne niezerowe wpisy w tablicy a. Zmienna adjacencies będzie miała całkowitą liczbę przylegań (może chcesz tylko wiedzieć, czy jest 0, czy nie). W powyższym przykładzie jest to 1.

Answer 4

Oto podejście podejmowania ciężkich wykorzystanie krojenie, że to tylko widoki z naciskiem na wydajność -

def distinct_ints(a): 
    # Mask of zeros, non-zeros as we would use them frequently 
    zm = a==0 
    nzm = ~zm 

    # Look for distint ints across rows 
    row_thresh = (nzm[:,1:] & zm[:,:-1]).sum(1) 
    row_out = ((nzm[:,1:] & (a[:,1:] != a[:,:-1])).sum(1)>row_thresh).any() 

    # Look for distint ints across cols 
    col_thresh = (nzm[1:] & zm[:-1]).sum(0) 
    col_out = ((nzm[1:] & (a[1:] != a[:-1])).sum(0)>col_thresh).any() 

    # Any from rows or cols 
    out = row_out | col_out 
    return out 

Answer 5

Jest możliwe, aby to zrobić z numpy.diff jednak fakt, że Zera nie mają być uważane za nieco komplikuje sprawę.

Można ustawić zera do wartości duże lub wystarczająco małe, aby nie powodować problemy:

a[a == 0] = -999 

lub użyć tablicę pływaka i ustawić je na nan lub inf:

a[a == 0] = numpy.nan 

Następnie wystarczy spojrzeć dla różnic pierwszego rzędu 1 w każdym kierunku:

numpy.any(numpy.abs(numpy.diff(a, axis=0)) == 1) or numpy.any(numpy.abs(numpy.diff(a, axis=1)) == 1)