2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Поиск максимумов функции двух переменных
Сообщение29.12.2011, 20:37 


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

 Профиль  
                  
 
 Re: Поиск максимумов функции двух переменных
Сообщение29.12.2011, 22:16 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Поиск максимумов функции двух переменных
Сообщение29.12.2011, 23:01 


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

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

 Профиль  
                  
 
 Re: Поиск максимумов функции двух переменных
Сообщение29.12.2011, 23:39 
Аватара пользователя


31/10/08
1244
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 
Заблокирован
Аватара пользователя


11/09/11

650
Зачем изобретать велосипед? Есть уже готовые процедуры даже в 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 


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

 Профиль  
                  
 
 Re: Поиск максимумов функции двух переменных
Сообщение24.03.2014, 20:36 
Заслуженный участник
Аватара пользователя


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

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


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

 Профиль  
                  
 
 Re: Поиск максимумов функции двух переменных
Сообщение25.03.2014, 18:21 
Аватара пользователя


31/10/08
1244
Думаю вам подойдёт non-maximum suppression.

 Профиль  
                  
 
 Re: Поиск максимумов функции двух переменных
Сообщение25.03.2014, 20:59 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group