在2D阵列中找到峰值的算法 [英] Algorithm to find peaks in 2D array
问题描述
假设我在java int [] [] array 中有一个2D累加器数组。数组可能如下所示：
Let's say I have a 2D accumulator array in java int[][] array. The array could look like this:
（x和z轴表示数组中的索引，y轴表示值 - 这些是 int的图像[56] [56] ，值为0~4500）
(x and z axes represent indexes in the array, y axis represents values - these are images of an int[56][56] with values from 0 ~ 4500)
或
我需要做的是在数组中找到峰值 - 有2个第一个峰值和第二个阵列中的8个峰值。这些峰值总是明显的（峰值之间始终存在间隙），但它们不必像这些图像那样相似，它们可能或多或少是随机的 - 这些图像不是基于真实数据，只是样本。真正的阵列可以有5000x5000的大小，峰值从几千到几十......算法必须是通用的，我不知道阵列或峰值有多大，我也不知道那里有多少个峰值是。但我知道某种阈值 - 峰值不能小于给定值。
What I need to do is find peaks in the array - there are 2 peaks in the first one and 8 peaks in the second array. These peaks are always 'obvious' (there's always a gap between peaks), but they don't have to be similar like on these images, they can be more or less random - these images are not based on the real data, just samples. The real array can have size like 5000x5000 with peaks from thousands to several hundred thousands... The algorithm has to be universal, I don't know how big the array or peaks can be, I also don't know how many peaks there are. But I do know some sort of threshold - that the peaks can't be smaller than a given value.
问题是，一个峰值可能包含几个较小的峰值在附近（第一幅图像），高度可以是相当随机的，并且在一个阵列中尺寸可以显着不同（尺寸 - 我的意思是它在阵列中所占的单位数量 - 一个峰值可以由6个单位组成，其他峰值可以由90个单位组成） 。它也必须很快（全部在1次迭代中完成），数组可能非常大。
The problem is, that one peak can consist of several smaller peaks nearby (first image), the height can be quite random and also the size can be significantly different within one array (size - I mean the number of units it takes in the array - one peak can consist from 6 units and other from 90). It also has to be fast (all done in 1 iteration), the array can be really big.
感谢任何帮助 - 我不希望你的代码，只是正确的想法:)谢谢！
Any help is appreciated - I don't expect code from you, just the right idea :) Thanks!
编辑你问过这个域 - 但它很复杂， imho它无法解决问题。它实际上是一个具有3D点的ArrayLists数组，如ArrayList< Point3D> [] []和有问题的值是ArrayList的大小。每个峰包含属于一个簇的点（在这种情况下为平面） - 该数组是算法的结果，它对点云进行分段。我需要在峰值中找到最高值，这样我就可以将最大的arraylist中的点拟合到一个平面上，从中计算一些参数，然后从峰值中正确地聚集大部分点。
edit: You asked about the domain - but it's quite complicated and imho it can't help with the problem. It's actually an array of ArrayLists with 3D points, like ArrayList< Point3D >[][] and the value in question is the size of the ArrayList. Each peak contains points that belong to one cluster (plane, in this case) - this array is a result of an algorithm, that segments a pointcloud . I need to find the highest value in the peak so I can fit the points from the 'biggest' arraylist to a plane, compute some parameters from it and than properly cluster most of the points from the peak.
推荐答案
他对使用某种优化启发式估计全局最大值不感兴趣 - 他只想在多个独立的簇中找到每个最大值。
He's not interested in estimating the global maximum using some sort of optimization heuristic - he just wants to find the maximum values within each of a number of separate clusters.
这些峰值总是明显的（峰值之间总是存在差距）
These peaks are always 'obvious' (there's always a gap between peaks)
根据你的图片，我认为你的意思是总是有一些 0 - 分隔集群的值？如果是这种情况，您可以使用简单的泛洪填充来识别群集。您还可以在进行填充填充时跟踪每个群集的最大值，这样您就可以识别群集并同时找到它们的最大值。
Based on your images, I assume you mean there's always some 0-values separating clusters? If that's the case, you can use a simple flood-fill to identify the clusters. You can also keep track of each cluster's maximum while doing the flood-fill, so you both identify the clusters and find their maximum simultaneously.
这也是 as您可以快速获取，而不依赖于启发式（可能会返回错误的答案），因为每个群集的最大值可能是群集中的任何值，因此您必须至少检查一次。
This is also as fast as you can get, without relying on heuristics (which could return the wrong answer), since the maximum of each cluster could potentially be any value in the cluster, so you have to check them all at least once.
请注意，这将迭代数组中的每个项目。这也是必要的，因为（来自你给我们的信息）它有可能使数组中的任何一个项目成为它自己的集群（这也会使它成为一个峰值） 。数组中大约有2500万个项目，现在只需几秒钟就可以使用现代计算机。
Note that this will iterate through every item in the array. This is also necessary, since (from the information you've given us) it's potentially possible for any single item in the array to be its own cluster (which would also make it a peak). With around 25 million items in the array, this should only take a few seconds on a modern computer.
这篇关于在2D阵列中找到峰值的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
