Как интерполировать между точками данных?

Question

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

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

Answer 1

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

Существует несколько распространенных схем интерполяции рассеянных данных в 2-й точке. На самом деле, для тех, кто имеет к ней доступ, доступна очень хорошая статья (Ричард Франке, «Интерполяция разбросанных данных: тесты некоторых методов», Математика вычислений, 1982)

Возможно, самый распространенный метод основан на триангуляции ваших данных. Просто построить триангуляцию домена из ваших точек данных. Тогда любая точка внутри выпуклой оболочки данных должна находиться ровно внутри одного из треугольников, иначе она будет на общем ребре. Это позволяет вам линейно интерполировать внутри треугольника. Если вы используете MATLAB, то для этой экспресс-цели доступна функция griddata.)

Проблема при попытке заполнить полное прямоугольное изображение из рассеянных точек состоит в том, что весьма вероятно, что данные не распространяются на 4 угла массива. В этом случае схема, основанная на триангуляции, потерпит неудачу, поскольку углы массива не лежат внутри выпуклой оболочки рассеянных точек. Альтернативой тогда является использование «радиальных базисных функций» (часто сокращенно RBF). Существует множество таких схем, включая Кригинг, когда они используются сообществом геостатистов.

http://en.wikipedia.org/wiki/Kriging

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

http://en.wikipedia.org/wiki/Inpainting

Идея в рисовании обычно заключается в формулировании краевой задачи. То есть, определить дифференциальное уравнение в частных производных для области, где есть дыра. Используя известные граничные значения, заполните отверстие, решая PDE для неизвестных элементов. Это может быть вычислительно интенсивным, если существует огромное количество неизвестных элементов, так как обычно требуется решение по крайней мере массивной разреженной системы линейных уравнений. Если PDE является нелинейным, то это становится еще более интенсивной проблемой. Простым, достаточно хорошим выбором для PDE является лапласиан, что приводит к линейной системе, которая хорошо экстраполирует. Опять же, я могу предложить решение для пользователя MATLAB.

http://www.mathworks.com/matlabcentral/fileexchange/4551

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

Answer 2

Уф! Большой предмет.

«Правильный» ответ зависит много от вашей проблемной области и различных деталей того, что вы делаете.

Интерполяция в более чем одном измерении требует выбора. Я предполагаю, что вы строите график на обычной сетке, но некоторые из ваших точек сетки не имеют данных. Большой вопрос: редкие недостающие точки, или они делают большие пятна?

Вы не можете добавить информацию, поэтому вы просто пытаетесь установить что-то, что будет выглядеть ОК.

Концептуально простое предложение (но реализация может быть некоторой работой):

Для каждого региона с отсутствующими данными идентифицируют все граничные точки. То есть найдите х на этой фигуре

oooxxooo
oox..xoo 
oox...xo
ox..xxoo
oox.xooo
oooxoooo

, где. - это точки, у которых отсутствуют данные, а у х и о есть данные (для одной отсутствующей точки это будут четыре ближайших соседа). Заполните каждую отсутствующую точку данных средним значением по краевым точкам вокруг этого объекта. Чтобы сделать его гладким, взвесьте каждую точку на 1/d, где d - расстояние таксайдера (дельта х + дельта у) между двумя точками.

---

До этого у нас были какие-либо подробности:

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

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

---

Когда мне нужно что-то более мощное, чем быстрая линейная интерполяция, я обычно использую ROOT (и выбираю один из классов TSpline), но это может потребовать больше ресурсов, чем нужно.

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

---

Линейная интерполяция между (или даже экстраполяцией) двух точек (x1, y1) и (x2, y2) дает вам

 y_i = (x_i-x1)*(y2-y1)/(x2-x1)

Answer 3

Учитывая, что это простой школьный проект, вероятно, самый простой метод интерполяции - «Ближайшие соседи»

Для каждой отсутствующей точки данных вы находите ближайшую «заполненную» точку данных и используете ее в качестве значения.

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

вес может быть пропорционален расстоянию точки от отсутствующей точки данных.

Есть еще миллионы других техник, но ближайший сосед, вероятно, проще всего реализовать.

Answer 4

если я понимаю, что ваша потребность заключается в следующем.

Я думаю, что у вас есть подмножество x, y, Интенсивность для измерения L по W, и вы хотите заполнить для всех X в диапазоне от 0 до L и Y в диапазоне от 0 до W.

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

Я думаю, что фильтр Байера или фильтр Гаусса подойдет вам.

Вы можете погуглить эти фильтры и получить ответы для реализации.

Удачи.