如何快速筛选两张同尺寸二值图中满足距离条件的黑像素索引

我有两张尺寸相同的二值图像，均包含黑色区域（像素值为0）。需要找出两张图像中所有与另一张图像内任意黑像素切比雪夫距离≤指定值的黑像素位置，结果返回两个数组分别存储两张图的符合条件的像素坐标。原实现用双重循环逐个判断距离，在处理5万+张100x100及更大尺寸图像时速度过慢，希望用numpy原生优化函数实现高效方案。

示例图像与原低效实现代码：

import numpy as np

distance = 2

img1 = np.array([[255, 255, 255, 255, 255, 255, 255, 255],
                 [255, 0, 0, 0, 255, 255, 255, 255],
                 [255, 0, 0, 0, 255, 255, 255, 255],
                 [255, 0, 0, 0, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255, 255]]).astype('uint8')

img2 = np.array([[255, 255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 0, 0, 0, 255],
                 [255, 255, 255, 255, 0, 0, 0, 255],
                 [255, 255, 255, 255, 0, 0, 0, 255],
                 [255, 255, 255, 255, 255, 255, 255, 255]]).astype('uint8')

# 原低效实现
img1_row, img1_col = np.where(img1 == 0)
img2_row, img2_col = np.where(img2 == 0)

img1_positions = np.column_stack((img1_row, img1_col ))
img2_positions = np.column_stack((img2_row, img2_col ))

img1_pos_list = []
img2_pos_list = []

for img1_pos in img1_positions:
    for img2_pos in img2_positions:
        if abs(img1_pos[0] - img2_pos[0]) <= distance:
            if abs(img1_pos[1] - img2_pos[1]) <= distance:
                if not any((img1_pos == x).all() for x in img1_pos_list):
                    img1_pos_list.append(img1_pos )
                if not any((img2_pos == x).all() for x in img2_pos_list): 
                    img2_pos_list.append(img2_pos )

原实现的核心问题：双重循环遍历所有黑像素对，还要重复判断元素是否已加入列表，时间复杂度为O(M*N)（M、N为两张图的黑像素数量），在大图像或大数据集下性能极差。

核心思路：利用形态学膨胀操作快速生成「距离目标黑区域≤指定值」的掩码，再通过数组交集直接筛选符合条件的黑像素，全程用numpy/scipy的底层优化操作，无Python层面循环。

实现步骤 #

1. 将二值图像转换为布尔数组（黑像素标记为True）
2. 创建对应指定距离的结构元素（切比雪夫距离对应正方形核，边长为2*distance+1）
3. 对其中一张图的黑区域做膨胀，得到覆盖所有邻近区域的掩码
4. 两张图的符合条件的黑像素，即为各自黑区域与另一张图膨胀掩码的交集
5. 将交集的坐标转换为数组输出

代码实现 #

import numpy as np
from scipy.ndimage import binary_dilation

distance = 2

# 转换为布尔数组：黑像素（0）为True
mask1 = img1 == 0
mask2 = img2 == 0

# 创建正方形结构元素，对应切比雪夫距离≤distance
struct_element = np.ones((2*distance + 1, 2*distance + 1), dtype=bool)

# 对两张图的黑区域做膨胀，得到邻近区域掩码
dilated_mask2 = binary_dilation(mask2, structure=struct_element)
dilated_mask1 = binary_dilation(mask1, structure=struct_element)

# 筛选符合条件的黑像素：自身是黑像素，且在另一张图的膨胀掩码内
img1_valid = mask1 & dilated_mask2
img2_valid = mask2 & dilated_mask1

# 获取坐标并转换为数组
img1_positions = np.column_stack(np.where(img1_valid))
img2_positions = np.column_stack(np.where(img2_valid))

print(img1_positions)
# [[2 2]
#  [2 3]
#  [3 2]
#  [3 3]]
print(img2_positions)
# [[4 4]
#  [4 5]
#  [5 4]
#  [5 5]]

性能优势 #

• 形态学膨胀是C语言实现的底层优化操作，时间复杂度远低于Python循环
• 数组位运算（&）是向量级操作，效率极高
• 无需重复判断元素是否已加入列表，直接通过掩码一次性筛选所有符合条件的像素
• 处理100x100图像时，速度比原实现快数百倍，完全适配5万+张图像的数据集

内容的提问来源于stack exchange，提问作者TheTelefone