algorithm - 什么是找到矩阵中所有局部最小值(最大值)的有效算法?

标签 algorithm matrix

我想在 N*N 矩阵中找到所有局部最大值,并有一个限制,即找到的每 2 个峰值必须至少距离 M 个单元格(在两个方向上)。换句话说,对于找到的峰值 P,如果该峰值低于 P,则忽略 P 周围 (2M+1)*(2M+1) 子矩阵内的局部最大值。

我所说的局部最大值是指(2M+1)*(2M+1)子矩阵中以该元素为中心的最大元素。

对于朴素方法,复杂度为O(N*N*M*M)。有没有一种有效的算法来实现这一点?

这是 N=5 和 M=1 的示例矩阵(3*3 网格):

enter image description here

最佳答案

由于您的矩阵看起来像图像,因此使用图像处理技术似乎是自然的选择。

您可以将峰值(局部最大值或最小值)定义为两个局部偏导数均具有零交叉的图像区域。如果您想要在这些位置处寻找负曲率最大值,如果您正在寻找最小值,请注意正曲率(曲率 -> 二阶导数)。

有可用的线性卷积运算符(及其背后的大量理论),可以产生 x 和 y 方向的偏导数(例如 SobelPrewitt )和二阶导数。

甚至还有 blob detection 的算法已经,这似乎与您的任务相关(例如 Laplacian of Gaussian )。

如果您追求速度,您可能想看看是否可以从 linear separability 中受益。 ,过滤器内核的预计算( associativity ),或 DFT 。另请注意,此类任务通常会从并行化中受益匪浅。看看您是否可以利用多个内核、GPU 或 FPGA 来提高性能。

关于algorithm - 什么是找到矩阵中所有局部最小值(最大值)的有效算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42781998/

相关文章:

algorithm - 如何确定任意数量的相等正方形的大小以适应固定大小的二维空间?

java - 在 Android 中表示矩阵 - 2*2

r - 如何通过矩阵索引值检索矩阵列和行名?

python - 随机矩阵,各列值的总和不大于 1

matlab - 如何为矩阵的每个元素设置不同的显示样式?

java - 在 Java 中将 double 转换为 char 数组的算法(不使用 Double.toString 或 StringBuilder 等对象)?

algorithm - 检查一个点是否在一个简单的多边形内

java - 删除链表中等于给定值的所有值

c++ - 如何为 Kronecker-Produkt 实现张量类

c++ - 为什么指向非静态成员函数的指针不能用作标准库算法的一元谓词?