2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Поиск максимумов функции двух переменных
Сообщение29.12.2011, 22:16 
Аватара пользователя
В компьютерном зрение обычно делают так.
Вначале сгладить функцию. Потом перебираем все точки функции проверяем с ближайшими соседями. Это обычно хорошо работает.

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

 
 
 
 Re: Поиск максимумов функции двух переменных
Сообщение29.12.2011, 23:01 
Спасибо за ответ, но нельзя ли по-подробнее?
У меня ведь поверхность, а не кривая, так что для скользящего среднего непонятно что с чем складывать и на что делить.

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

 
 
 
 Re: Поиск максимумов функции двух переменных
Сообщение29.12.2011, 23:39 
Аватара пользователя
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 способе.

 
 
 
 Re: Поиск максимумов функции двух переменных
Сообщение30.12.2011, 02:42 
Аватара пользователя
Зачем изобретать велосипед? Есть уже готовые процедуры даже в 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]);

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

Изображение

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

Изображение

 
 
 
 Re: Поиск максимумов функции двух переменных
Сообщение24.03.2014, 20:31 
Вопрос по теме. А как найти "хребты" такой функции. Т.е. слева и справа от линии хребта значение функции меньше чем на хребте? Желательно в аналитическом виде.

 
 
 
 Re: Поиск максимумов функции двух переменных
Сообщение24.03.2014, 20:36 
Аватара пользователя
Хребет - это Вы может имеете ввиду седловые точки? Локально туда, наверное, сходится метод Ньютона ( я не проверял).

 
 
 
 Re: Поиск максимумов функции двух переменных
Сообщение25.03.2014, 15:06 
Нет. Не седловые точки, а именно хребет. Т.е. слева и справа от линии хребта значение функции меньше чем в точке хребта.

 
 
 
 Re: Поиск максимумов функции двух переменных
Сообщение25.03.2014, 18:21 
Аватара пользователя
Думаю вам подойдёт non-maximum suppression.

 
 
 
 Re: Поиск максимумов функции двух переменных
Сообщение25.03.2014, 20:59 
да. это то что нужно. А в аналитическом виде есть формулы? А то везде ссылки на оператор выделения контуров Канни.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group