基于连通邻域的布尔交集 - NumPy / Python

Question

有这两个数组：

import numpy as np

arr1 = np.array([[0,0,0,0,1,0],
                 [0,0,0,0,0,0],
                 [0,0,0,0,0,0],
                 [0,1,0,0,1,0],
                 [0,0,0,0,0,0]], dtype=bool)

arr2 = np.array([[0,1,1,0,0,0],
                 [0,1,1,0,0,0],
                 [0,0,0,0,1,1],
                 [1,1,0,0,1,1],
                 [1,1,0,0,0,0]], dtype=bool)

我需要一种逻辑运算，使 returns 中被 arr1[=22= 拦截的任何连接特征 arr2 为真].结果应该是这样的：

arr3 = np.array([[0,0,0,0,0,0], [0,0,0,0,0,0], [0,0,0,0,1,1], [1,1,0,0,1,1], [1,1,0,0,0,0]], dtype=bool)

我检查了 python 和 numpy logic functions 中的逻辑操作，但似乎没有任何效果。有任何想法吗？谢谢:)

Answer 1

方法 #1

我们可以使用基于image-processing的标注函数对基于connected-ness的图像进行标注，然后使用masking得到我们想要的输出。要进行标记，我们可以使用 skimage.measure.label. Alternatively, we can also use scipy.ndimage.label 来获取标记的图像。因此，一种解决方案是 -

from skimage.measure import label as sklabel

def func1(arr1,arr2):
    # Get labeled image
    L = sklabel(arr2)

    # Get all present labels (this would also include zero label)
    present_labels = L[arr1]

    # Get presence of these labels in the labeled image. Remove the zero regions
    # by AND-ing with arr2.
    return np.isin(L,present_labels) & arr2

给定样本的输出 -

In [141]: func1(arr1,arr2)
Out[141]: 
array([[False, False, False, False, False, False],
       [False, False, False, False, False, False],
       [False, False, False, False,  True,  True],
       [ True,  True, False, False,  True,  True],
       [ True,  True, False, False, False, False]])

方法 #2

对于大斑点，我们应该在使用 np.isin 成为 performance-efficient 之前寻找唯一的当前标签。为了有效地获得那些独特的，我们可以利用 pandas.factorize。此外，标签部分可以通过使用 SciPy 版本来提高性能。因此，对于这种情况，另一种更有效的解决方案是 -

from scipy.ndimage import label as splabel
import pandas as pd

def func2(arr1,arr2):
    L = splabel(arr2)[0]
    pL = pd.factorize(L[arr1])[1]
    return np.isin(L,pL[pL!=0])

基准测试

我们将使用给定的示例数据，沿行和列按 1000x 扩展，同时保持相同数量的 blob。为了扩大规模，我们将使用 np.repeat -

In [147]: arr1 = arr1.repeat(1000, axis=0).repeat(1000, axis=1)

In [148]: arr2 = arr2.repeat(1000, axis=0).repeat(1000, axis=1)

In [149]: %timeit func1(arr1,arr2)
     ...: %timeit func2(arr1,arr2)
1.75 s ± 7.01 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
226 ms ± 5.99 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Answer 2

如果您不想使用除 Numpy 之外的任何其他库，我建议您对矩阵进行洪水填充，这可以通过 DFS 或 BFS 来完成。主要思想是迭代 arr1 的每个元素，如果元素为真，则将位置添加到 stack/queue。然后对于这些位置中的每一个，您将在 arr2 上开始泛洪填充，并且对于生成的每个新位置，您必须在 arr3 中写入一个 1。代码将是这样的：

from collections import deque
#arr3 start empty
arr3 = np.zeros((5,6))
rows = 5
cols = 6
#here i will use a deque as a queue
q = deque()
for i in range(len(arr1)):
    for j in range(len(arr1[i])):
        if arr1[i][j]:
            #for every true element in arr1
            #i add it to the queue
            q.append((i,j))
#bfs transversal
while q:
    i,j = q.popleft()
    if not arr3[i][j] and arr2[i][j]:
        #check on arr3 to avoid infinite looping
        #check on arr2 to see if it's part of a component
        arr3[i][j] = True
        #here i assume diagonals are neighbors too
        #but you can change these fors to define neighbors
        for ii in range(i-1,i+2):
            for jj in range(j-1,j+2):
                if ii==i and jj==j:
                    #we dont want to check the same element again
                    continue
                if ii<0 or ii>=rows or jj<0 or jj>=cols:
                    #we dont want to access an invalid position either
                    continue
                q.append((ii,jj))
print(arr3)

基于连通邻域的布尔交集 - NumPy / Python

Boolean intersection based on connected neighborhood - NumPy / Python

python

boolean

numpy

intersection

image-processing

基准测试