在2D阵列中找到峰值的算法

Question

假设我在java中有一个2D累加器数组int[][] array.该数组可能如下所示:

(x和z轴表示数组中的索引,y轴表示值 - 这些是int[56][56]具有0~4500值的图像)

要么

我需要做的是在阵列中找到峰值 - 第一个峰值有2个峰值,第二个阵列有8个峰值.这些峰值总是"明显的"(峰值之间始终存在间隙),但它们不必像这些图像那样相似,它们可能或多或少是随机的 - 这些图像不是基于真实数据,只是样本.真正的阵列可以有5000x5000的大小,峰值从几千到几十......算法必须是通用的,我不知道阵列或峰值有多大,我也不知道那里有多少个峰值是.但我确实知道某种阈值 - 峰值不能小于给定值.

问题是,一个峰可以由附近的几个较小的峰组成(第一个图像),高度可以是非常随机的,并且在一个阵列中大小可以显着不同(大小 - 我的意思是它在阵列中占用的单位数 - 一个峰值可以包含6个单位,其他峰值可以包含90个单位.它也必须快速(所有在1次迭代中完成),阵列可能非常大.

任何帮助表示赞赏 - 我不希望你的代码,只是正确的想法:)谢谢!

---

编辑:你询问了域名 - 但它很复杂,而且它无法解决问题.它实际上是一个带有3D点的ArrayLists数组,如ArrayList <Point3D> [] [],并且有问题的值是ArrayList的大小.每个峰包含属于一个簇的点(在这种情况下为平面) - 该数组是算法的结果,该算法对点云进行分段.我需要在峰值中找到最高值,这样我就可以将"最大"的arraylist中的点拟合到一个平面,从中计算一些参数,然后从峰值中正确地聚集大部分点.

Answer 1

他对使用某种优化启发式估计全局最大值不感兴趣 - 他只想在多个独立的簇中找到最大值.

这些峰值总是"明显的"(峰值之间始终存在差距)

基于你的图像,我假设你的意思是总是有一些值0分离簇？如果是这种情况,您可以使用简单的泛洪填充来识别集群.您还可以在执行洪水填充时跟踪每个群集的最大值,因此您既可以识别群集又可以同时找到它们的最大值.

这也是你可以获得的速度,而不依赖于启发式(可能会返回错误的答案),因为每个群集的最大值可能是群集中的任何值,因此您必须至少检查一次.

请注意,这将遍历数组中的每个项目.这也是必要的,因为(根据您提供给我们的信息),阵列中的任何单个项目都可能成为其自己的集群(这也会使其成为峰值).阵列中有大约2500万个项目,这在现代计算机上只需要几秒钟.