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

Question

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

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

или

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

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

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

---

edit: Вы спрашивали о домене - но это довольно сложно и imho не может помочь с проблемой. На самом деле это массив ArrayLists с трехмерными точками, например ArrayList [] [], а рассматриваемое значение - это размер ArrayList. Каждый пик содержит точки, которые принадлежат одному кластеру (в данном случае плоскости) - этот массив является результатом алгоритма, который сегментирует облако точек. Мне нужно найти самое высокое значение в пике, чтобы я мог подогнать точки от «самого большого» массива к плоскости, вычислить некоторые параметры из него и затем правильно сгруппировать большинство точек из пика.

Answer 1

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

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

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

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

---

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

Answer 2

Возможно, это не оптимальное решение, но, поскольку проблема звучит несколько нестабильно, я запишу ее.

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

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

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

Answer 3

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

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

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