Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Быстрое постронеие сглаживающей точки поверхности

Автор: _Y_ 17.11.2014, 22:39

Имеется довольно большой 2-мерным массив действительных чисел, представляющий собой некую поверхность.

Разброс величин относительно этой поверхности определяется не только статистическим шумом, но и массой других факторов.

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

В принципе, задача решаема и решена (последовательная аппроксимация рядов и колонок полиномом). Проблема в том, что использованный алгоритм жрет немеряно времени.

Подскажите, пожалуйста, какой алгоритм делал бы работу с оглядкой на сроки исполнения.

Спасибо!

Автор: Akina 18.11.2014, 09:46

Цитата(_Y_ @ 17.11.2014, 23:39

)

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

Для плоскости всё элементарно и быстро считается по МНК - все необходимые суммы произведений считаются за 1 проход, и система из 4 линейных уравнений решается чисельно.
Далее - задаётся параметр допустимого отклонения и начинается отбрасывание наиболее сильно отклоняющихся от плоскости точек, сама плоскость при этом пересчитывается. При этом наиболее отклоняющаяся точка считается за 1 проход, после нахождения суммы просто корректируются и система пересчитывается.
Когда максимальное отклонение перестанет превышать заданный параметр, отброшенные точки (вернее, их отклонение от окончательной плоскости) аппроксимируются на некую куполообразную поверхность (с нулевыми асимптотами по всем направлениям - нечто типа вероятностной кривой в сечении через максимум) - если повертеть карандашом, вряд ли аналитическое решение получится сложнее МНК, то же накопление сумм, только не произведений. Итогом будет сумма уравнений плоскости и купола.

Автор: _Y_ 18.11.2014, 10:38

Цитата(Akina @ 18.11.2014, 09:46

)

Когда максимальное отклонение перестанет превышать заданный параметр, отброшенные точки (вернее, их отклонение от окончательной плоскости) аппроксимируются на некую куполообразную поверхность (с нулевыми асимптотами по всем направлениям - нечто типа вероятностной кривой в сечении через максимум)

Спасибо, но хотелось бы подробностей: как это считать?

Автор: Akina 18.11.2014, 11:19

Да как обычно - по МНК. Задаёшь аналитическое выражение для желаемого уравнения поверхности, в коем у тебя будет некое количество констант. Суммируешь отклонения расчётных точек от вычисленных для этого желаемого уравнения по всему массиву. Производная этой суммы по любой из констант при оптимальных значениях констант равна нулю. Преобразовываешь аналитически уравнения производных, получаешь систему уравнений, где количество уравнений равно количеству констант. Если функция уравнения поверхности не очень сложна, как правило удаётся получить аналитически систему линейных уравнений относительно этих констант, где коэффициенты являются сложными суммами экспериментальных значений. И решение системы даёт оптимальные значения констант.

Автор: _Y_ 18.11.2014, 20:34

Hу тогда остается спросить про подходящее уравнение smile

Автор: Akina 18.11.2014, 21:04

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

Автор: _Y_ 18.11.2014, 23:51

По логике вещей, мне надо минимизировать такую функцию:

Код


s = s + ( z[i] - L / ( (X-x[i])^2 + (Y-y[i])^2 + Z^2 ) )^2

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

PS: Извиняюсь, что привел формулу в таком псевдокодовом виде. http://ipicture.ru почему-то не хочет загружать картинку с красиво набранным уравнением.

Автор: Akina 19.11.2014, 08:51

Цитата(_Y_ @ 19.11.2014, 00:51

)

не хочет загружать картинку с красиво набранным уравнением

А локальный JPG загрузить в сообщение - не?

Автор: Pavia 19.11.2014, 21:22

_Y_,
Рассмотрим одномерный случай.
Существует несколько подходов:
- Аппроксимация полиномом.
- Аппроксимация сплайном.
- Фильтрация вч
- Фильтр Кальмана
- Оптимизация ломанной

Двухмерный аналогичен. Решается выполнением отдельно по Х и Y.
1) Аппроксимация требует. 81*N умножений и столько же сложений. И решения матричного уравнения.
Скорость регулируется степенью p. 81=p^2 но более p=6 не советую.
2) Тоже самое, но точность аппроксимации выше так как нет проблем со степенью. А скорость и гладкость регулируется разбиением на число полиномов(участков).
3) Фильтрация зависит от множества факторов. Но от 10-100 умножений на точку. В зависимости от степени.
4) Не в курсах как там.
5) Оптимизация ломанной этот тот же МНК что в 1 и 2, только линейный.
p*N умножений. Гладкость определяется коэффициентом допустимого отклонения.

Автор: _Y_ 19.11.2014, 21:41

Pavia,

Цитата(Pavia @ 19.11.2014, 21:22

)

- Аппроксимация полиномом.
............
Двухмерный аналогичен. Решается выполнением отдельно по Х и Y.

Именно так и делаю. Полиномом 4-й степени занимает 1,9 секунды на моем нотбуке, полиноммом 3-й 1,5 секунды (но результат уже не очень хороший). Можно, в принципе, подключить комп помощнее, но надо ускорить не в два раза, а в десять, наверное.

Цитата(Akina @ 19.11.2014, 08:51

)

А локальный JPG загрузить в сообщение - не?

А про это я забыл smile

Вот она:

Автор: Pavia 19.11.2014, 22:32

_Y_,
А размерность данных какая и какая сложность алгоритма? Просто я думаю где-то ошибка, из-за этого скорость маленькая.
А вот качество да. Там хромает, поэтому я и предложил сплайн, тем более он может быть 3 порядка.

Автор: _Y_ 20.11.2014, 12:02

Алгоритм, собственно, предельно простой.

Имеем 2-мерный массив значений. Все значения наличествуют, ни одного не пропущено.
Проходим по рядам исходного массива, аппроксимируя полиномом каждый ряд как одномерный массив. Для аппроксимации используем библиотечную функцию.
Полученый сглаженный по рядам массив пропускаем через ту же процедуру еще раз, но теперь сглаживая по колонкам.
Вот и все - получилась поверхность, которая всех устраивает.

Собственно, сам я это не придумал: нашел в сети несколько готовых процедур. Эта дала ожидаемый результат. Единственно, что я в ней поменял, разрешил параллелизацию обработки рядов/колонок. иначе процедура работала еще раза в два медленнее.