Поиск максимумов функции двух переменных

[vilko]

Есть функция двух переменных, заданная в узлах сетки. (Ближайший пример из реальной жизни - топография. Значения функции - высота над уровнем моря.)
Подскажите алгоритм поиска локальных максимумов для такой функции. Можно, конечно, каждую точку тупо сравнивать с соседями, но может есть что-то более продвинутое?

[Pavia]

В компьютерном зрение обычно делают так.
Вначале сгладить функцию. Потом перебираем все точки функции проверяем с ближайшими соседями. Это обычно хорошо работает.

Ещё есть метод скользящего среднего. В гугле легко найдёте
mean shift pdf

[vilko]

Спасибо за ответ, но нельзя ли по-подробнее?
У меня ведь поверхность, а не кривая, так что для скользящего среднего непонятно что с чем складывать и на что делить.

И для первого варианта - чем сгладить поверхность?

[Pavia]

1) Есть у тебя функция f(x,y) вот её и сглаживаем чтобы избавиться от низко частотного шума. $f(x,y)*g(x,y,s)$ здесь * это операция свёртки. Параметр s- cила сглаживания. Им можешь регулировать какой пик считать локальным, а какой нет. g- типичное Гаусовское сглаживание.
Локальные максимумы тогда просто ищутся, тут по 4 соседям

    if  (p1[i]>p1[i-1])and (p1[i]>p1[i+1]) and
        (p1[i]>p0[i]) and (p1[i]>p2[i]) then
         begin
         ...
         end;

2)

Цитата:

У меня ведь поверхность, а не кривая, так что для скользящего среднего непонятно что с чем складывать и на что делить.

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

Только вот не думаю, что вы сильно с экономите на скорости при 2 способе.

[Klad33]

Зачем изобретать велосипед? Есть уже готовые процедуры даже в 3D.
Например, в Maple по команде
restart; with(plots); f := proc (a, b, c) options operator, arrow; c*exp(-(x-a)^2-(y-b)^2) end proc; moon := f(0, 0, -3)+f(2, 2, 2)+f(-2, -2, 2)+f(-1, 2, 3)+f(1, -2, 2)+f(2, 0, 2); plot3d(moon, x = -3 .. 3, y = -3 .. 3, contours = 20, style = patchcontour, axes = frame, shading = ZHUE, orientation = [60, 50]);

получается неплохой рисунок поверхности с изолиниями по высотам:



Изображение можно мышкой поворачивать как угодно, увеличивать, изучать экстремальные точки и т.д. Например, посмотреть в плане:

[D2fDx2]

Вопрос по теме. А как найти "хребты" такой функции. Т.е. слева и справа от линии хребта значение функции меньше чем на хребте? Желательно в аналитическом виде.

[мат-ламер]

Хребет - это Вы может имеете ввиду седловые точки? Локально туда, наверное, сходится метод Ньютона ( я не проверял).

[D2fDx2]

Нет. Не седловые точки, а именно хребет. Т.е. слева и справа от линии хребта значение функции меньше чем в точке хребта.

[Pavia]

Думаю вам подойдёт non-maximum suppression.

[D2fDx2]

да. это то что нужно. А в аналитическом виде есть формулы? А то везде ссылки на оператор выделения контуров Канни.