python - 在 numpy 数组中找到一些缺失点

Question

我有一个图像，我将其描述为由 0 和 1(或 True 和 False)组成的矩阵图像。
有许多 1 个数据(蓝色)形成三角形网格，但缺少一些点。我想做的是发现错过了红点。在python中找红点有没有有效又漂亮的方法？我希望许多python专家帮助解决这个问题。

Answer 1

有趣的问题。这是解决此问题的方法。我首先通过示例提到了完整的代码，然后在下面进行了解释。该解决方案具有以下优点-

1. 处理非方形二维图像
2. 无需事先知道重复模式
3. 可以处理任何形状的方形和非方形重复图案
4. 内存高效且完全(几乎)矢量化

注意:此方法仅在图像中存在至少 1 个完整的纯重复图案时才有效。

import numpy as np
import matplotlib.pyplot as plt

def find_gaps(x):
    #Identifying the size and shape of the repeating pattern
    xpattern = int(x.shape[0]//np.max(x.sum(axis=0))+2)
    ypattern = int(x.shape[1]//np.max(x.sum(axis=1))+2)
    pattern_shape = (xpattern, ypattern)
    
    #Calculating number of rolling windows that exist with that pattern
    num_xpatterns = x.shape[0]//pattern_shape[0]+1
    num_ypatterns = x.shape[1]//pattern_shape[1]+1
    
    #Calculating the stride and shape that needs to be taken with stride_tricks
    shp = (num_xpatterns, num_ypatterns, xpattern, ypattern)  #(2, 2, 3, 5)
    strd = (x.strides[0]*(xpattern-1), x.strides[1]*(ypattern-1), x.strides[0], x.strides[1])  #(144, 32, 72, 8)
    
    #Generating rolling windows/convolutions over the image to separate the patterns.
    convolve_pattern = np.lib.stride_tricks.as_strided(x, shape=shp, strides=strd)
    
    #Assuming at least 1 untouched pattern exists, finding that pure pattern
    pattern_sums = convolve_pattern.sum(axis=(-1,-2))
    idx = np.unravel_index(np.argmax(pattern_sums), pattern_sums.shape)
    truth_pattern = convolve_pattern[idx]
    
    #Identifying the gaps by subtracting the convolved image with the truth pattern
    gaps = convolve_pattern - truth_pattern[None, None, :, :]
    
    #Setting the gaps as -1 directly into the location of memory of the original image
    for i in np.argwhere(gaps==-1):
        convolve_pattern[tuple(i)]=-1
    
    return(x)

这是一个示例，其中包含非正方形重复图案 (3,5) 和 2 个间隙的图像。这里 -1 的值表示间隙或缺失 1，但可以在函数中将其更改为您想要的 -

#Image with non-square repeating patterns

img = np.array([[1., 0., 0., 0., 1., 0., 0., 0., 0.], #One gap added here
                [0., 0., 1., 0., 0., 0., 1., 0., 0.],
                [1., 0., 0., 0., 1., 0., 0., 0., 1.],
                [0., 0., 1., 0., 0., 0., 0., 0., 0.], #One gap added here
                [1., 0., 0., 0., 1., 0., 0., 0., 1.]])

plt.imshow(img)

plt.imshow(find_gaps(img))

这是另一个示例，其中我在具有方形重复图案的较大图像中添加了 4 个间隙 -

img = np.array([[1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1.],
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0.],  #One gap added here
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1.],
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0.],  #One gap added here
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1.],
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0., 0., 1., 0., 0.],
                [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
                [1., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0.]]) #Two gaps added here

plt.imshow(img)

plt.imshow(find_gaps(img))

---

详细说明

让我们假设一个图像具有非正方形(在 axis0 和 axis1 上不同)重复图案。这里的非方形图案显然是 (3,5)

的形状

x = np.array([[1., 0., 0., 0., 1., 0., 0., 0., 0.],  #<- gap in last entry
              [0., 0., 1., 0., 0., 0., 1., 0., 0.],
              [1., 0., 0., 0., 1., 0., 0., 0., 1.],
              [0., 0., 1., 0., 0., 0., 0., 0., 0.],  #<- gap in 3rd last entry
              [1., 0., 0., 0., 1., 0., 0., 0., 1.]])

第一步是找到应该在图像中重复的这种未触及/纯图案的形状。为此，您可以计算两个轴上总和的最大值，并将原始形状除以该值(然后加 +2)得到 (3,5)

xpattern = int(x.shape[0]//np.max(x.sum(axis=0))+2)
ypattern = int(x.shape[1]//np.max(x.sum(axis=1))+2)

pattern_shape = (xpattern, ypattern)

(3,5)

现在您已经有了图案的形状，您想要执行滚动窗口操作来分离原始图像中的这个形状。在这里，您可以看到图像由这种图案组成，重复 4 次，在 x 轴上重复 2 次，在 y 轴上重复 2 次。要计算图案在图像中重复多少次，您可以这样做 -

num_xpatterns = x.shape[0]//pattern_shape[0]+1
num_ypatterns = x.shape[1]//pattern_shape[1]+1

print(num_xpatterns, num_ypatterns)

(2,2)

现在，您拥有了一切，可以让您使用步幅将图像分成图案大小的 block 来构建滚动窗口。这个包含 (3,5) 形状模式 block 的数组的输出形状将是 (2,2,3,5)，即 2 个模式在 x 上重复- 轴和 2 个模式在 y 轴上重复。

您还可以通过将每个方向的字节数乘以每个方向的模式形状来计算实现此输出数组所需的步幅。

shp = (num_xpatterns, num_ypatterns, xpattern, ypattern)   #(2, 2, 3, 5)
strd = (x.strides[0]*(xpattern-1), x.strides[1]*(ypattern-1), x.strides[0], x.strides[1])   #(144, 32, 72, 8)

convolve_pattern = np.lib.stride_tricks.as_strided(x, shape=shp, strides=strd)
convolve_pattern

array([[[[1., 0., 0., 0., 1.],
         [0., 0., 1., 0., 0.],
         [1., 0., 0., 0., 1.]],

        [[1., 0., 0., 0., 0.],
         [0., 0., 1., 0., 0.],
         [1., 0., 0., 0., 1.]]],


       [[[1., 0., 0., 0., 1.],
         [0., 0., 1., 0., 0.],
         [1., 0., 0., 0., 1.]],

        [[1., 0., 0., 0., 1.],
         [0., 0., 0., 0., 0.],
         [1., 0., 0., 0., 1.]]]])

您现在已将图像分成形状为 (3,5) 的潜在纯图案和不纯图案 block 。现在，您所要做的就是找到一个纯模式，并将其与这个模式 block 数组中的所有其他模式进行比较。

这可以通过一个简单的事实来实现，即纯模式将在所有其他模式 block 中拥有最大的总和。

pattern_sums = convolve_pattern.sum(axis=(-1,-2))
idx = np.unravel_index(np.argmax(pattern_sums), pattern_sums.shape)

pure_pattern = convolve_pattern[idx]
pure_pattern

array([[1., 0., 0., 0., 1.],
       [0., 0., 1., 0., 0.],
       [1., 0., 0., 0., 1.]])

使用广播将这个纯模式 block 与其他所有模式 block 相减，您可以使用 -1

揭示每个模式 block 中间隙的位置

gaps = convolve_pattern - pure_pattern[None, None, :, :]
gaps

array([[[[ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.]],

        [[ 0.,  0.,  0.,  0., -1.],
         [ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.]]],


       [[[ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.]],

        [[ 0.,  0.,  0.,  0.,  0.],
         [ 0.,  0., -1.,  0.,  0.],
         [ 0.,  0.,  0.,  0.,  0.]]]])

最后，(这就是使用 stride_tricks 中的 numpy View 的强大功能)，您可以识别间隙的位置 (-1) 并将它们简单地设置为 -1(或者什么-随你喜欢)在 numpy View 中，因此也修改了原始图像，因为分配是直接对原始图像的内存进行的。

for i in np.argwhere(gaps==-1):
    convolve_pattern[tuple(i)]=-1

print(x)

array([[ 1.,  0.,  0.,  0.,  1.,  0.,  0.,  0., -1.],  #<- Found gap 1!
       [ 0.,  0.,  1.,  0.,  0.,  0.,  1.,  0.,  0.],
       [ 1.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  1.],
       [ 0.,  0.,  1.,  0.,  0.,  0., -1.,  0.,  0.],  #<- Found gap 2!
       [ 1.,  0.,  0.,  0.,  1.,  0.,  0.,  0.,  1.]])

这就是您如何识别具有非方形重复图案的图像中的间隙。

---