Алгоритм поиска пиков в 2D-массиве

Скажем, у меня есть 2D-накопитель в java int[][] array. Массив может выглядеть так:

(оси x и z представляют собой индексы в массиве, ось y представляет значения - это изображения int[56][56] со значениями от 0 до 4500)

или

Что мне нужно сделать - найти пики в массиве - в первом есть 2 пика и 8 пиков во втором массиве. Эти пики всегда "очевидны" (всегда есть промежуток между вершинами), но они не должны быть похожими на эти изображения, они могут быть более или менее случайными - эти изображения не основаны на реальных данных, просто образцы, Реальный массив может иметь размер 5000x5000 с пиками от тысяч до нескольких сотен тысяч... Алгоритм должен быть универсальным, я не знаю, насколько велики могут быть массивы или пики, я также не знаю, сколько пиков там находятся. Но я знаю какой-то порог - пики не могут быть меньше заданного значения.

Проблема заключается в том, что один пик может состоять из нескольких меньших пиков рядом (первое изображение), высота может быть довольно случайной, а также размер может быть существенно различен в пределах одного массива (размер - я имею в виду количество единиц, которое требуется в массиве - один пик может состоять из 6 единиц, а другой из 90). Он также должен быть быстрым (все сделано в 1 итерации), массив может быть действительно большим.

Любая помощь приветствуется - я не ожидаю от вас кода, просто правильная идея:) Спасибо!

edit:. Вы спрашивали о домене - но это довольно сложно, и imho это не может помочь с проблемой. Это фактически массив ArrayLists с 3D-точками, например ArrayList < Point3D > [] [] и значение, о котором идет речь, это размер ArrayList. Каждый пик содержит точки, принадлежащие одному кластеру (в данном случае плоскости) - этот массив является результатом алгоритма, который сегментирует pointcloud. Мне нужно найти наивысшее значение в пике, чтобы я мог поместить точки от "самого большого" arraylist в плоскость, вычислить некоторые параметры из нее и правильно класть большинство точек с пика.

Ответ 1

Он не заинтересован в оценке глобального максимума, используя какую-то эвристику оптимизации - он просто хочет найти максимальные значения в каждом из нескольких отдельных кластеров.

Эти пики всегда "очевидны" (всегда существует разрыв между пиками)

На основе ваших изображений, я полагаю, вы имеете в виду, что всегда есть 0 -значения, разделяющие кластеры? Если это так, вы можете использовать простую заливку-заливку для идентификации кластеров. Вы также можете отслеживать максимальный максимум кластера при выполнении заливки потока, так что вы оба идентифицируете кластеры и находите их максимум одновременно.

Это также так быстро, как вы можете получить, не полагаясь на эвристику (которая может вернуть неверный ответ), так как максимальное количество кластера потенциально может быть любым значением в кластере, поэтому вы должны проверить их все хотя бы один раз.

Обратите внимание, что это будет проходить через каждый элемент массива. Это также необходимо, так как (из информации, которую вы нам предоставили), потенциально возможно, чтобы любой отдельный элемент в массиве был его собственным кластером (что также сделало бы его пиком). Примерно с 25 миллионов элементов в массиве это займет всего несколько секунд на современном компьютере.

Ответ 2

Это может быть не оптимальное решение, но так как проблема звучит немного жидкой, я запишу ее.

Создайте список всех значений (и координат), которые превышают минимальный уровень.
Сортировка в порядке убывания высоты.
Первый элемент будет самым большим пиком, добавьте его в список пиков.
Затем опуститесь вниз по списку, если текущий элемент больше минимального расстояния от всех существующих пиков, добавьте его в список пиков.

Это линейное описание, но все этапы (кроме 3) могут быть тривиально параллельны. На шаге 4 вы также можете использовать карту покрытия: 2D-массив булевых, которые показывают, какие координаты были "покрыты" ближайшим пиком.

(Предостережение emptor: как только вы уточните критерии, это решение может стать совершенно неосуществимым, но в целом оно работает.)

Ответ 3

Имитированный отжиг или восхождение по холму - это то, что сразу приходит в голову. Эти алгоритмы, однако, не гарантируют, что все пики будут найдены.

Однако, если ваши "пики" будут разделены значениями 0 в качестве разрыва, возможно, анализ связанных компонентов поможет. Вы бы назвали регион "подключенным", если он связан со значениями, превышающими 0 (или если у вас есть определенный порог, области ярлыков, которые связаны с этим порогом), то количество ваших компонентов будет вашим числом пиков. Затем вы можете выполнить другой проход массива, чтобы найти максимальный размер каждого компонента.

Следует отметить, что связанные компоненты могут выполняться в линейном времени, и найти пиковые значения можно также в линейном времени.