Если у вас есть опыт использования некоторых схем пространственной интерполяции, расскажите об этом.
UPD: Чтобы сделать этот вопрос более конкурентоспособным, я переформулировал его. Это были "Какие методы многомерной интерполяции вы когда-либо использовали?"
Я использовал Kriging в прошлом, с разбросанными данными, которые пришли с оценками точности в каждом образце. Казалось, что это мощная техника, которая заслуживает более широкого использования вне мира геостатистики.
(Это будет длинным, если только я не выпью.)
Во-первых, несколько комментариев о нераспределенных данных. (См. Ответ, который ссылается на littleCMS)
Существует два типа цветовой интерполяции, которые являются общими. Несколько лет назад трилинейная интерполяция (линейная интерполяция тензорного произведения) была обычным подходом для интерполяции цветных таблиц. Трилинейная интерполяция действительно может быть реализована как последовательный набор одномерных интерполяций, сначала на одной оси, затем вдоль второй оси и т.д.
Много лет назад мы все поняли, что трилинейная интерполяция вводит артефакты в цветной визуализации при применении к определенным типам преобразований. Проблемы наблюдаются у нейтралов. Решение состоит в том, чтобы перейти к симплициальному интерполятору в 3-й раз, разрезав куб на 6 тетраэдров. В n измерениях единичный куб будет расчленен на факториальные (n) симплексы. Существуют и другие вскрытия куба, но этот особый стиль гарантирует, что основная диагональ всегда является общим краем для всех симплексов. Это, в свою очередь, восстанавливает хорошее поведение нейтралов при применении к определенным таблицам поиска цветов.
Теперь позвольте мне задать вопрос об истинной интерполяции рассеянных данных.
Другие упомянули множество схем. Кригинг, мультиквадрия, дистанционные методы - это несколько. (Когда я делал некоторую работу в прошлом с этими схемами, я фактически предпочел обратные многоквартирные методы.) Все это на самом деле просто вариации радиальных методов базисных функций, общей схемы. Методы RBF имеют свои хорошие и плохие моменты. Они обычно генерируют гладкую интерполяцию, это, конечно, зависит от выбранной конкретной функции функции, а также от того, хотите ли вы ограничить поддержку. Методы RBF также позволяют экстраполировать, по крайней мере, так далеко, как будет расширяться поддержка радиальных базисных элементов. Если базовым элементам разрешено быть бесконечным по размеру, тогда не будет применено явное ограничение на экстраполяцию. (Экстраполяция в целом - это плохо.) Одна из проблем с методами RBF заключается в том, что они требуют решения больших систем линейных уравнений, и эти системы уравнений часто являются плотными матрицами. Это означает, что размер проблемы с точки зрения количества точек данных, которые вы можете обрабатывать, имеет тенденцию ограничиваться линейной алгеброй. Если вместо этого вы ограничиваете поддержку, обрезая базовые элементы, тогда матрицы могут стать разреженными. Это улучшит линейную алгебру, если вы используете разреженный пакет матриц для решения. В то же время, расстояние поддержки становится нелинейным параметром, который необходимо контролировать. Кроме того, методы, такие как multiquadrics и обратные мультиквадрические методы, могут иметь вторичный нелинейный параметр, который управляет формой базовых элементов. У Кригинга есть похожие проблемы, и я объединил бы все эти методы вместе.
По этим вопросам все эти методы, которые я классифицировал как варианты RBF, часто ограничены количеством точек, которые они будут комфортно обрабатывать. В зависимости от того, как вы имеете дело с вещами и объемом доступной памяти, этот предел может часто составлять порядка нескольких тысяч точек.
Еще одна проблема с общим классом методов RBF - это то, что я назову интраполяцией. Это неологизм, который я создал много лет назад, чтобы описать интерполяцию через относительно большую дыру в данных. На самом деле часто могут возникать проблемы даже при интерполяции между меньшими отверстиями в данных. Эти методы, поскольку они в какой-то степени гладкие, могут ввести нежелательные экстремумы (большие пики или долины) в интерполированную поверхность. Это обычная проблема даже с 1-м интерполянтами, часто рассматриваемыми как звонкие артефакты с кубическими сплайнами или полиномиальными интерполяциями и, конечно же, с интерполяторами серии Фурье. Проблема в более высоких измерениях состоит в том, чтобы даже признать, что это действительно произошло, поскольку нанесение поверхностей в более чем трех измерениях затруднено.
Если у вас больше очков, чем этот предел, или если эти мелодии звонка неприемлемы, то другие методы часто являются лучшим выбором. Если вы хотите использовать линейную интерполяцию, то самое простое решение в более высоких измерениях должно начинаться с тесселяции данных. Таким образом, в 3-х измерениях тесселят данные (как правило, тезанелла дельтона) в тетраэдры. Это достаточно эффективно, и для этой цели есть много инструментов. Это простая проблема для интерполирования любой отдельной точки. Просто укажите, в каком симплексе находится точка, вычислите барицентрические координаты как интерполяционные веса внутри симплекса и сформируйте соответствующую линейную комбинацию значений функций в каждой вершине найденного симплекса. Все это очень быстро и эффективно.
Недостатком этих методов на основе тесселяции является то, что они обычно ограничивают вас выпуклой оболочкой точек данных и, как плохо, если ваши данные попадают в не выпуклый домен, то интерполятор может хорошо делать странные вещи в в некоторых регионах вашего домена. Еще одна проблема со схемой, о которой я упоминал выше, заключается в том, что интерполяция будет только кусочно-линейной, но как только вы перейдете к более высоким измерениям, все будет быстро отвратительно. Другие методы можно найти для гладкой интерполяции на основе тесселяции, но они потребуют больше усилий и, следовательно, гораздо менее распространены.
Основные компромиссы должны быть очевидны здесь. Если вам нужна гладкая интерполяция и у вас есть только несколько точек, то часто выбираются методы RBF. Они просты, просты в использовании и т.д. Фактический выбранный метод часто является просто вопросом удобства или даже привычки. Я использовал один инструмент раньше и был счастлив, я, вероятно, буду счастлив с ним снова. Поскольку вопрос был о том, какой метод "лучше всего подходит для практического использования", я укажу, что лучше всего это очень субъективное слово, когда оно применяется вне контекста. Каковы ваши цели в задаче интерполяции? Какие навыки у вас есть? Какой набор инструментов вы знаете, как использовать? В какой среде вы будете работать? Все эти факторы повлияют на выбор наилучшего метода.
Если у вас много точек данных, а скорость имеет значение, но предельная плавность не так важна, тогда вы обычно будете искать симплициальный интерполятор. Конечно, если у вас есть достаточное количество очков, то кусочно-линейная природа зверя имеет меньшее значение. Кусочно-линейная интерполяция здесь имеет большую силу в некоторых случаях, что она никогда не может генерировать экстремумы на вашей поверхности, которых не было в данных. Для некоторых проблем, например, для цветовой характеризации это имеет первостепенное значение.
Еще одна проблема связана с шумом. Хотя наличие шума часто является сигналом о необходимости сглаживания некоторого рода, не все такие поверхности имеют сглаживание. Любой сглаживающий оператор иногда сглаживает важные функции данных. Это происходит потому, что мы можем рассматривать сглаживающий оператор как фильтр нижних частот. Высокочастотное поведение часто представляет собой шум, но также может быть просто резким пальцем или плечом на моей поверхности, который я не могу позволить себе потерять. Если это проблема, вы можете захотеть использовать интерполятор даже при наличии иногда значительного шума. В этом случае я предлагаю, чтобы самый простой интерполятор самого низкого порядка был лучшим. Гладкая, более глобальная интерполяция также будет иметь тенденцию усиливать любой шум в данных, поэтому, если вы посмотрите на интерполяцию с минимальной дисперсией при наличии шума, это будет обычно линейный интерполятор.
Конечно, существует много разновидностей тонких пластинчатых сплайнов, интерполирующих или нет. Когда вы выходите за пределы одного измерения, ваши варианты также расширяются, по крайней мере, если вы готовы выполнять эту работу.
Я закончу здесь, прежде чем превратится в книгу.
(Год спустя) см. inverse-distance-weighted-idw-interpolation-with-python, комбинация взвешивания с обратным расстоянием и scipy.spatial.KDTree.
Единственное приложение, которое я видел, - это код littleCMS (механизм управления цветом с открытым исходным кодом).
В первый раз, когда я проверил его, он просто сделал линейную интерполяцию по одной оси, а затем интерполировал между этим результатом и точкой на другой оси. я только что его перезагрузил, и, кажется, намного сложнее. не может сравниться со статьей, которую вы упомянули, но, возможно, захотите ее проверить, в файле cmslut.c.
Я работал с сглаживанием трехмерных рассеянных данных для обработки поверхности LINK. Это касалось многих точек, и мне нужна была очень гладкая поверхность, поэтому вначале процесс нашел наилучшую посадку поверхности второго порядка для данных, а затем фазу релаксации, где точки были установлены на поверхность. Это не интерполяционная поверхность исходных данных, но это способ уменьшить порядок интерполяции оптимизированным образом.
Метод включал работу на кусочных областях, которые хорошо подходили для приближения второго порядка.
Другая интересная характеристика метода состоит в том, что точки были вершинами треугольников, а связность сохраняется при сглаживании.