在2D数组上查找最大子集和

Question

假设我有一个图像，我想找到一个形状为3x3的子数组，与其他子数组相比，该子数组包含最大和。

我如何在python中高效地做到这一点（尽可能快地运行）？如果您可以提供一个示例代码，那就太好了。

我的具体问题：我想在此热图中提取斑点中心的位置

我不想获得最大点，因为那样会导致坐标不太精确。斑点的真实中心实际上可能在2个像素之间。因此，最好在许多点之间进行加权平均以获得子像素精度。例如，如果有两个点（x1，y1）和（x2，y2），其值分别为200和100。则平均坐标为x=(200*x1+100*x2)/300 y=(200*y1+100*y2)/300

我的解决方案之一是进行卷积运算。但是我认为它不够高效，因为它需要乘以内核（仅包含一个）。我正在寻找一种快速的实现方式，因此我无法循环播放自己的内容，因为不确定是否会很快。

我想将此算法每隔几毫秒处理50张图像。 （图像批量出现）。具体而言，将这些图像视为输出热图的机器学习模型的输出。为了从这些热图获得坐标，我需要在具有高强度的坐标之间进行某种加权平均。我的想法是对图像的3x3区域进行加权平均。我也欢迎其他更快或更优雅的方法。

Answer 1

import cv2
import numpy as np
from timeit import default_timer as timer

img = cv2.imread('blob.png', 0)
start = timer()
_, thresh = cv2.threshold(img, 240, 1, cv2.THRESH_BINARY)
mask = np.ones((3, 3), np.uint8)
res = cv2.filter2D(thresh, -1, mask)
result = np.where(res == np.amax(res))
end = timer()
print(end - start)

我不确定效率是否如您所愿，但输出为0.0013461999999435648 s

P.S。您提供的图像带有白色边框，为此方法我必须将其裁剪掉。

Answer 2

子采样图像并找到所需点的邻域。您可以通过不在所有像素上循环，例如在每5个像素（循环中的row=row+5和col=col+5）。找到附近位置后，请考虑该位置附近的特定邻域，并对该特定作物的整个像素进行循环以找到确切位置。

Answer 3

找到图像最大值的像素位置m=(xm, ym)。这只需要访问图像中的每个像素，每个像素进行一个比较，因此它是O（N），因此只要您以原始图像分辨率进行操作就可以达到最佳。

应用您要使用的图像模型，以在m的邻域中找到（子像素内插的）最大值。

澄清点（2）：您写

我不想获得最大点，因为那样会导致坐标不太精确。斑点的真正中心实际上可能在2个像素之间

虽然直观上合理，但此断言需要变得更加精确才能计算。也就是说，您需要以数学方式表达您对图像所做的假设，从而使您能够在像素采样位置之间搜索“真实”最大值。

这种假设的一个简单例子是二次平滑度。在这种情况下，您假设在“真实”最大位置的较小区域（例如3x3，在5x5中），图像信号z很好地由二次近似：

z = A00 dx^2 + A01 dx dy + A11 dy^2 + A02 dx + A12 dy + A22
where:
dx = x - xm; dy = y - ym

由于泰勒级数定理，如果预期基础信号至少是三阶连续且可微的，则此假设是有意义的。从几何上讲，这意味着您假设（希望？）信号看起来像是最大附近的二次曲线（抛物面或椭圆形）。

然后您可以为m附近的每个像素评估上述方程式，替换z的实际图像值，从而获得未知Aij中的线性系统，其中的方程式与相邻像素（因此，即使是3x3邻域也会产生过度约束的系统）。在最小二乘意义上求解系统会给您“最佳”系数Aij。该模型预测的理论最大值是一阶偏导数消失的地方：
del z / del dx = 2 A00 dx + A01 dy = 0
del z / del dy = A01 dx + 2 A11 dy = 0

这是两个未知的(dx, dy)中的线性系统，对其求解可得出最大值的估计位置，并通过上述z的等式得出最大值的预测图像值。

就计算成本而言，与遍历大小适中的图像相比，所有此类模型估计都非常快。