¿Cómo se interpola entre los puntos de datos?

Question

Actualmente estoy desarrollando una pieza de software usando opencv y qt que traza puntos de datos. Necesito poder completar una imagen a partir de datos incompletos. Quiero interpolar entre los puntos que tengo. ¿Alguien puede recomendar una biblioteca o una función que podría ayudarme? Pensé que tal vez el método opencv reMap pero parece que no puedo hacer que funcione.

Los datos son una matriz de 2 d de valores de intensidad. Quiero crear una imagen de algún tipo. Es un proyecto escolar.

Answer 1

¡Uf! Gran tema.

La respuesta "correcta" depende mucho en el dominio de su problema y varios detalles de lo que está haciendo.

La interpolación en más de 1 dimensión requiere tomar algunas decisiones. Asumiré que estás tramando en una grilla regular, pero que algunos de tus puntos de grilla no tienen datos. Gran pregunta: ¿faltan los puntos faltantes o forman grandes manchas?

Usted no puede añadir información, por lo que está tratando de establecer algo que va a mirar OK.

sugerencia conceptualmente simple (pero la implementación puede ser un poco de trabajo):

Para cada región en los datos que faltan, identificar todos los puntos de borde. Eso es encontrar las x en esta figura

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

en los años. Son los puntos de datos faltantes, y los xyo de disponer de datos (para un único punto que falta, esto será los cuatro vecinos más cercanos). Complete cada punto de datos faltante con un promedio sobre los puntos de borde alrededor de este blob. Para que sea suave, el peso de cada punto por 1/d donde d es la distancia taxidriver (delta x + delta y) entre los dos puntos ..

---

Desde antes teníamos ningún detalle:

En la ausencia de ese tipo de información, ¿has probado la interpolación lineal en línea recta? Si sus datos son razonablemente densos, esto podría hacerlo por usted, y es lo suficientemente simple como para codificar en línea cuando lo necesite.

El siguiente paso es generalmente una spline cúbica, pero para eso es probable que desee obtener una implementación existente.

---

Cuando necesito algo más poderoso que una interpolación lineal rápida, que suelen utilizar ROOT (y recoger una de las clases TSpline), pero esto puede ser más sobrecarga de lo que necesita.

Como se señaló en los comentarios, ROOT es grande, y si bien es rápido, trata de forzarte a hacer las cosas al estilo ROOT, por lo que puede tener un gran efecto en tu programa.

---

una interpolación lineal entre (o, de hecho extrapolación de) dos puntos (x1, y1) y (x2, y2) le da

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

Answer 2

si entiendo que su necesidad es la siguiente.

yo creo que hay un subconjunto de X, Y, La intensidad de una dimensión de L por W y que desea rellenar para todo x varía de 0 a L e Y que va de 0 a W.

Si esto es su pregunta, entonces la solución es obtener otras intensidades mediante el uso de filtros.

Creo que el filtro Bayer o el filtro Gaussian harían el trabajo por usted.

Puede google estos filtros y obtendrá respuestas para implementar.

Lo mejor de la suerte.

Answer 3

La interpolación es un tema complejo. Hay infinitas maneras de interpolar un conjunto de puntos, y esto suponiendo que realmente desea hacer interpolación y no suavizar de ninguna manera. (Un interpolante reproduce exactamente los puntos de datos originales). Y, por supuesto, la naturaleza bidimensional de este problema hace que las cosas sean más difíciles.

Existen varios esquemas comunes para la interpolación de datos dispersos en 2-d. En realidad, para aquellos que tienen acceso a él, hay disponible un documento muy bonito (Richard Franke, "Interpolación de datos dispersos: pruebas de algunos métodos", Matemáticas de Computación, 1982.)

Quizás el método más común utilizado se basa en una triangulación de sus datos. Simplemente crea una triangulación del dominio desde tus puntos de datos. Entonces, cualquier punto dentro del casco convexo de los datos debe estar dentro de exactamente uno de los triángulos, o estará en un borde compartido. Esto le permite interpolar linealmente dentro del triángulo. Si está utilizando MATLAB, entonces la función griddata está disponible para este propósito expreso.)

El problema al tratar de rellenar una imagen rectangular completa desde puntos dispersos es que muy probablemente los datos no se extienden a las 4 esquinas del formación. En ese caso, un esquema basado en la triangulación fallará, ya que las esquinas de la matriz no se encuentran dentro del casco convexo de los puntos dispersos. Una alternativa entonces es usar "funciones de base radial" (a menudo abreviado RBF). Hay muchos esquemas similares que se pueden encontrar, incluido Kriging, cuando lo usa la comunidad de geoestadística.

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

Finalmente, inpainting es el nombre para un esquema de interpolación donde los elementos se dan en una matriz, pero donde no son elementos que faltan. El nombre obviamente se refiere al hecho por un conservador de arte que necesita reparar una rasgadura o una rasgadura en una valiosa obra de arte.

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

La idea detrás de inpainting es típicamente de formular un problema de contorno. Es decir, defina una ecuación diferencial parcial en la región donde hay un agujero. Usando los valores de límite conocidos, complete el agujero resolviendo el PDE para los elementos desconocidos. Esto puede ser computacionalmente intensivo si hay una gran cantidad de elementos desconocidos, ya que normalmente requiere la solución de al menos un sistema escaso masivo de ecuaciones lineales. Si el PDE no es lineal, entonces se convierte en un problema aún más intenso.Una elección simple, razonablemente buena para el PDE es el Laplaciano, que da como resultado un sistema lineal que extrapola bien. De nuevo, puedo ofrecer una solución para un usuario de MATLAB.

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

opciones mejores para el PDE pueden venir de PDE no lineales. Una vez que tal es la ecuación de Navier/Stokes. Es adecuado para modelar los tipos de superficies que se ven normalmente, pero también es más difícil de manejar. Como en muchas facetas de la vida, obtienes lo que pagas.

Answer 4

Considerando que este es un proyecto escolar sencillo, probablemente la técnica de interpolación más fácil de implementar es el "vecinos más cercanos"

Para cada uno de los datos que faltan apuntan a encontrar el "lleno" punto de datos más cercano y usar eso como el valor.

Si quieres mejorar los ritults un poco más, puedes decir, encontrar los puntos de datos K más cercanos y usar su promedio ponderado como el valor de tu punto de datos faltante.

el peso podría ser proporcional a la distancia del punto del punto de datos faltante.

Hay un trillón de otras técnicas, pero el vecino más cercano es probablemente el más fácil de implementar.