¿Cómo interpolar entre puntos de datos?

Question

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

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

Answer 1

¡Uf! Gran tema.

El " derecha " La respuesta depende mucho de su dominio del problema y de los diversos detalles de lo que está haciendo.

Interpolar en más de 1 dimensión requiere tomar algunas decisiones. Asumiré que está trazando en una cuadrícula regular, pero que algunos de sus puntos de cuadrícula no tienen datos. Gran pregunta: ¿los puntos faltantes son escasos o hacen grandes manchas?

Usted no puede agregar información, por lo que solo está tratando de establecer algo que se vea OK.

Sugerencia conceptualmente simple (pero la implementación puede ser un trabajo):

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

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

donde los. son los puntos que faltan datos, y los x y o tienen datos (para un solo punto faltante, estos serán los cuatro vecinos más cercanos). Complete cada punto de datos que falta con un promedio sobre los puntos de borde alrededor de este blob. Para que sea suave, pondere cada punto con 1 / d donde d es la distancia del taxista (delta x + delta y) entre los dos puntos ..

---

Desde antes teníamos detalles:

En ausencia de ese tipo de información, ¿ha intentado una interpolación lineal directa? Si sus datos son razonablemente densos, esto lo puede hacer por usted, y es lo suficientemente simple como para codificarlo en línea cuando lo necesite.

El siguiente paso suele ser una spline cúbica, pero para eso probablemente querrás tomar una implementación existente.

---

Cuando necesito algo más poderoso que una interpolación lineal rápida, generalmente uso ROOT (y escojo 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 aunque es rápido, intenta forzarte a hacer las cosas de la manera ROOT, por lo que puede tener un gran efecto en tu programa.

---

Una interpolación lineal entre (o incluso extrapolación de) dos puntos (x1, y1) y (x2, y2) te da

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

Answer 2

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

Hay varios esquemas comunes para la interpolación de datos dispersos en 2-d. En realidad, para aquellos que tienen acceso a él, hay un excelente artículo disponible (Richard Franke, "Interpolación de datos dispersos: Pruebas de algunos métodos", Matemáticas de la computación, 1982.)

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

El problema al intentar llenar una imagen rectangular completa desde puntos dispersos es que es muy probable que los datos no se extiendan a las 4 esquinas de la matriz. En ese caso, un esquema basado en triangulación fallará, ya que las esquinas de la matriz no se encuentran dentro del casco convexo de los puntos dispersos. Entonces, una alternativa es usar funciones de base radial. (a menudo abreviado RBF). Existen muchos esquemas de este tipo, incluido Kriging, cuando los utiliza la comunidad de geoestadística.

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

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

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

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

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

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

Answer 3

Teniendo en cuenta que este es un proyecto escolar simple, probablemente la técnica de interpolación más fácil de implementar es el "Vecinos más cercanos"

Para cada punto de datos faltantes, se encuentra el " más lleno " Punto de datos y usar eso como el valor.

Si desea mejorar un poco más los retults, puede decir, encontrar K puntos de datos más cercanos y usar su promedio ponderado como el valor de su punto de datos perdido.

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

Existen miles de otras técnicas, pero el vecino más cercano es probablemente el más fácil de implementar.

Answer 4

si entiendo que su necesidad es la siguiente.

Creo que tiene un subconjunto de x, y, Intensidad para una dimensión de L por W y desea completar todas las X que van de 0 a L e Y que van de 0 a W.

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

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

Puedes buscar estos filtros en Google y obtendrás respuestas para implementar.

La mejor de las suertes.