Come interpolare tra punti dati?

Question

Attualmente sto sviluppando un software utilizzando opencv e qt che tracciano punti dati. Devo essere in grado di riempire un'immagine da dati incompleti. Voglio interpolare tra i punti che ho. Qualcuno può consigliare una biblioteca o una funzione che potrebbe aiutarmi. Ho pensato forse al metodo reMap opencv ma non riesco a farlo funzionare.

I dati sono una matrice 2-d di valori di intensità. Voglio creare un'immagine di qualche tipo. È un progetto scolastico.

Answer 1

Phew! Grande argomento.

La risposta "giusta" dipende da un numero di lotto sul dominio del problema e vari dettagli su ciò che si sta facendo.

L'interpolazione di più di una dimensione richiede alcune scelte. Immagino che tu stia pianificando su una griglia regolare, ma che alcuni dei tuoi punti della griglia non abbiano dati. Grande domanda: i punti mancanti sono scarsi o fanno grossi blob?

È Non possibile aggiungere informazioni, in modo che stai solo cercando di stabilire qualcosa che guardare OK.

Concettualmente semplice suggestione (ma l'implementazione può essere un certo lavoro):

Per ciascuna regione sui dati mancanti, identificare tutti i punti di bordo. Cioè trovare le x in questa figura

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

dove i. Di sono i punti mancanti di dati, e le X e O sono i dati (per un singolo punto mancante, questo sarà i quattro vicini più prossimi). Riempi tutti i punti dati mancanti con una media sui punti di bordo attorno a questo blob. Per rendere più agevole, peso ogni punto da 1/d dove d è la distanza tassista (delta x + y delta) tra i due punti ..

---

Dalla prima abbiamo avuto alcun dettaglio:

In l'assenza di questo tipo di informazioni, hai provato in modo lineare l'interpolazione lineare? Se i tuoi dati sono ragionevolmente densi questo potrebbe farlo per te, ed è abbastanza semplice codificare in linea quando ne hai bisogno.

Il passo successivo è in genere una spline cubica, ma per questo probabilmente vorrai prendere un'implementazione esistente.

---

Quando ho bisogno di qualcosa di più potente di un'interpolazione lineare veloce, io di solito uso ROOT (e scegliere una delle classi TSpline), ma questo potrebbe essere più in alto del necessario.

Come notato nei commenti, Root è grande, e mentre è veloce, lo fa cercare di forzare a fare le cose nel modo ROOT, quindi può avere un grande effetto sul vostro programma.

---

Un'interpolazione lineare tra (o addirittura estrapolazione da) due punti (x1, y1) e (x2, y2) ti dà

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

Answer 2

se capisco che la vostra esigenza è la seguente.

Penso che tu abbia un sottoinsieme di x, y, intensità per una dimensione di L da W e si desidera riempire per tutte le X che va da 0 a L e Y da 0 a W.

Se questo è la tua domanda, quindi la soluzione è ottenere altre intensità usando i filtri.

Penso che il filtro Bayer o il filtro gaussiano farebbero il lavoro per voi.

Puoi google questi filtri e otterrete risposte da implementare.

Buona fortuna.

Answer 3

L'interpolazione è un argomento complesso. Ci sono infiniti modi per interpolare un insieme di punti, e questo presupponendo che tu voglia veramente fare interpolazione e non lisciare alcun tipo. (Un interpolante riproduce esattamente i punti dati originali.) E, naturalmente, la natura bidimensionale di questo problema rende le cose più difficili.

Esistono diversi schemi comuni per l'interpolazione di dati dispersi in 2-d. In realtà, per coloro che vi hanno accesso, è disponibile una carta molto bella (Richard Franke, "Interpolazione dei dati sparsi: test di alcuni metodi", Matematica del calcolo, 1982.)

Forse il metodo più comune utilizzato è basato su una triangolazione dei tuoi dati. Costruisci semplicemente una triangolazione del dominio dai tuoi punti dati. Quindi qualsiasi punto all'interno dello scafo convesso dei dati deve trovarsi esattamente all'interno di uno dei triangoli o sarà su un bordo condiviso. Questo ti permette di interpolare linearmente all'interno del triangolo. Se si utilizza MATLAB, la funzione griddata è disponibile per questo scopo espresso.

Il problema quando si tenta di popolare un'immagine rettangolare completa da punti sparsi è che molto probabilmente i dati non si estendono ai 4 angoli del array. In tal caso, uno schema basato sulla triangolazione fallirà, poiché gli angoli dell'array non si trovano all'interno dello scafo convesso dei punti sparsi. Un'alternativa quindi è usare "funzioni di base radiali" (spesso RBF abbreviato). Esistono molti schemi di questo tipo, incluso Kriging, quando vengono utilizzati dalla comunità geostatistica.

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

Infine, inpainting è il nome di uno schema di interpolazione in cui elementi sono indicati in una matrice, ma dove ci sono elementi mancanti. Il nome si riferisce ovviamente a quello fatto da un conservatore d'arte che ha bisogno di riparare una lacrima o strappare un prezioso pezzo d'arte.

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

L'idea alla base inpainting è tipicamente di formulare un problema al contorno. Cioè, definire un'equazione differenziale parziale sulla regione in cui vi è un buco. Usando i valori limite conosciuti, riempire il buco risolvendo il PDE per gli elementi sconosciuti. Questo può essere intensivo dal punto di vista computazionale se vi è un numero enorme di elementi sconosciuti, poiché in genere richiede la soluzione di almeno un massiccio sistema di equazioni lineari sparse. Se la PDE è non lineare, diventa un problema ancora più intenso.Una semplice, ragionevolmente buona scelta per il PDE è il laplaciano, che si traduce in un sistema lineare che estrapola bene. Ancora una volta, posso offrire una soluzione per un utente MATLAB.

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

scelte migliori per il PDE possono provenire da PDE non lineari. Una volta tale è l'equazione di Navier/Stokes. È adatto per modellare i tipi di superfici tipicamente visibili, ma è anche più difficile da gestire. Come in molti aspetti della vita, ottieni ciò per cui paghi.

Answer 4

considerando che questo è un progetto scolastico semplice, probabilmente la tecnica di interpolazione più semplice da implementare è la "Casa più vicina"

per ciascuno dei dati mancanti puntano a trovare il "pieno" punto dati più vicino e l'uso che come valore.

Se si desidera migliorare un po 'di più i risultati, allora si può dire, trovare K punti di dati più vicini e usare la loro media ponderata come valore del punto dati mancante.

il peso potrebbe essere proporzionale alla distanza del punto dal punto dati mancante.

Ci sono altre zillion tecniche, ma il vicino più vicino è probabilmente il più facile da implementare.