在二维数组中找到亚像素最大值

Question

假设我有一张图片，我想找到一个形状为3x3的子数组，其中包含与其他子数组相比具有最大总和。如何在Python中高效地实现这一点（尽可能快地运行）？如果您能提供示例代码，那就太好了。

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

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

我的一个解决方案是执行卷积操作。但我认为它不够高效，因为它需要将核（只包含1）乘以像素。我正在寻找快速实现，因此无法自己循环，因为我不确定它是否会快。

我想要对50张图像每隔几毫秒执行此算法（图像作为批处理输入）。具体来说，将这些图像视为机器学习模型输出的热图的输出。为了从这些热图中获取坐标，我需要在高强度坐标之间进行某种加权平均。我的想法是在图像的3x3区域周围进行加权平均。我也可以接受其他更快或更优雅的方法。

- off99555

---

你已经打上了 [tag:卷积] 标签，所以显然你已经尝试过卷积/滤波。结果如何？你能确定斑点的范围（边界框，也许？）吗？这些斑点大小总是差不多吗？每张图像只有一个斑点吗？我建议你尽可能地减少搜索区域（或者尽可能快地减少），并找到斑点的加权质心。 - beaker

OpenCV或TensorFlow中的普通卷积实现需要对内核进行乘法运算。虽然可以工作，但不是最快的。我想要一种实现，您不需要进行任何乘法运算，因为仅求和就足够了。此外，我认为可能有比卷积更好的技术来解决这个问题，所以我在这里提问。如果您能够实现无内核卷积（并且运行速度快），那么我也想使用它。 Blob始终大约相同大小。理想情况下，应该只有一个Blob，但模型可能会输出2个Blob（错误）。 - off99555

加载图像，转换为灰度图，奥茨阈值，执行形态学闭运算，查找轮廓并选择最大轮廓面积。 - nathancy

尝试一下ndimage.center_of_mass怎么样？ - Alex

是的，这就是我的意思。我今天遇到了这个问题，很惊讶我找不到一个好的解决方案。 - Alex

Answer 1

寻找“3x3形状的子数组具有最大总和”与使用未归一化的3x3盒式滤波器过滤后查找图像的最大值相同。因此，问题归结为有效地查找图像的最大值，您假设它是底层连续平滑信号的（可能是“嘈杂的”）离散样本 - 因此您希望找到亚像素位置。

你真的需要将问题分成两个部分：

1. 找到图像最大值的像素位置m =（xm，ym）。这仅需要访问图像中的每个像素，并对每个像素进行一次比较，因此它是O（N），因此只要您在本机图像分辨率下操作，就是最优的。在OpenCv中，可以使用minMaxLoc函数完成。

2. 应用您正在使用的图像模型，在m的邻域中找到其（亚像素插值）最大值。

为了澄清第二点：您可以编写

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

尽管这种说法直观上是有道理的，但为了能够计算，需要将其表述得更加精确。也就是说，您需要数学地表达出您对图像所做的假设，从而使您能够在像素采样位置之间搜索“真正”的最大值。

这样假设的一个简单示例是二次平滑性。在这种情况下，您假设在“真正”最大位置的小区域（例如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 方程式预测最大值处的图像值。就计算成本而言，与遍历甚至中等大小的图像相比，所有这些模型估计都非常快速。

- Francesco Callari

---

我认为你的想法是先找到最大像素，然后在该像素周围取平均值，这已经足够好了。 - off99555

Answer 2

一种方法是对图像进行子采样，并找到所需点的邻域。您可以通过在循环中执行每5个像素而不是所有像素(row=row+5和col=col+5)来实现它。在找到附近位置后，考虑该位置周围的特定邻域，并在该特定裁剪的整个像素上循环以找到确切位置。

- MeiH

Answer 3

基于我对图像处理的了解，要得到一个适用于任何一个 blob 的可靠结果，请按照以下步骤进行：

1. 将图像变为灰度图（像素值在0-255之间），如果还没有变成灰度图的话。
2. 对图像进行归一化处理，使像素强度覆盖0-255的全部范围。
3. 将图像转换为二进制格式（像素值只能为0或1）。可以通过阈值处理实现此目的，例如应用这个规则：强度小于或等于127的像素被赋予0的强度值，其他所有像素都被赋予1的强度值。
4. 找到所有像素的加权平均值，其值均为“1”。

或者

4. 对图像进行侵蚀处理，直到只剩下2个像素或1个像素。

情况1

如果有两个像素，则需要找到这两个像素的 u 和 v 坐标。blob 的中心点将位于这两个像素的 u 和 v 坐标的中心点之间。

案例2

如果只剩下一个像素，则该像素的坐标为中心点。

—————

你提到了用Python快速实现这个问题：

Python是一种解释性语言，因此它逐行执行代码，对于像图像处理这样高度迭代的任务来说，它不太适合。然而，你可以利用像OpenCV（https://docs.opencv.org/2.4/index.html）这样的C语言库来缓解这种情况，使手头的任务变得更加容易。 OpenCV还在此领域提供了我上面列出的所有步骤的解决方案，因此你应该能够相当快地实现一个可靠的解决方案，尽管我不能保证它是否能达到你每几毫秒处理50张图片的目标。还有其他需要考虑的因素，比如你正在处理的图像的大小，这将呈指数级增加处理负载。

更新

我刚刚找到了一篇很好的文章，实际上反映了我之前列出的步骤过程：

https://www.learnopencv.com/find-center-of-blob-centroid-using-opencv-cpp-python/

更重要的是，它还表示通过以下数学公式找到质心的公式：

c = (1/n)Σ(n, i=1, x_i)

但是文章中对此进行了更好的阐述，比我在这里能做的更好。

- Matt Woolford

Answer 4

很抱歉，我没有完全理解您最后一段的意思，所以我只停留在获取所有坐标具有最大值的点上。我使用了cv2.filter2D对阈值图像进行卷积，然后使用np.amax和np.where找到了具有最大值的坐标。

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秒

P.S. 您提供的图像有一个白色边框，我不得不将其裁剪掉以适用此方法。

- Vardan Agarwal

---

你的想法与我所想的相似，即尝试卷积图像，然后从新图像中获取最大结果。虽然你用来计算的时间相当长（1毫秒）。我希望能够在50张图像上执行此过程，每个图像的形状约为100x100，每秒钟执行大约50次。简单地说，每秒将卷积大约2,500张图像。 - off99555

我已添加了更多的解释来说明我所说的坐标加权平均值。您可以再次查看问题。 - off99555