Come interpolare tra i punti dati?

StackOverflow https://stackoverflow.com/questions/609297

Domanda

Attualmente sto sviluppando un software usando opencv e qt che tracciano punti dati. Devo essere in grado di compilare un'immagine da dati incompleti. Voglio interpolare tra i punti che ho. Qualcuno può raccomandare una libreria o una funzione che potrebbe aiutarmi. Ho pensato forse al metodo reMap di 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.

È stato utile?

Soluzione

Accidenti! Grande argomento.

Il " giusto " la risposta dipende molto dal dominio del problema e da vari dettagli di ciò che stai facendo.

L'interpolazione in più di 1 dimensione richiede alcune scelte. Presumo che tu stia tramando su una griglia normale, ma che alcuni dei tuoi punti della griglia non abbiano dati. Grande domanda: i punti mancanti sono sparsi o creano grandi macchie?

Non puoi aggiungere informazioni, quindi stai solo cercando di stabilire qualcosa che sembrerà OK.

Suggerimento concettualmente semplice (ma l'implementazione potrebbe essere un lavoro):

Per ogni regione in cui mancano i dati, identificare tutti i punti del bordo. Cioè trova le x in questa figura 

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

dove i punti. sono i dati mancanti punti e le xe o hanno dati (per un singolo punto mancante, questi saranno i quattro vicini più vicini). Riempi ogni punto di dati mancante con una media sui punti di margine attorno a questo BLOB. Per renderlo uniforme, pesa ogni punto di 1 / d dove d è la distanza del taxidriver (delta x + delta y) tra i due punti ..

Da prima avevamo dettagli:

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

Il prossimo passo è di solito una spline cubica, ma per questo probabilmente vorrai afferrare un'implementazione esistente.

Quando ho bisogno di qualcosa di più potente di una rapida interpolazione lineare, di solito utilizzo ROOT (e scelgo uno di le classi TSpline), ma questo potrebbe essere più sovraccarico del necessario.

Come notato nei commenti, ROOT è grande , e mentre è veloce, cerca di forzarti a fare le cose nel modo ROOT, quindi può avere un grande effetto sul tuo programma.

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

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

Altri suggerimenti

L'interpolazione è un argomento complesso. Esistono infiniti modi per interpolare un insieme di punti, e questo presuppone che tu desideri veramente fare l'interpolazione e non livellare di alcun tipo. (Un interpolante riproduce esattamente i punti di dati originali.) E, naturalmente, la natura 2-d di questo problema rende le cose più difficili.

Esistono diversi schemi comuni per l'interpolazione di dati sparsi in 2-d. In realtà, per coloro che hanno accesso ad esso, è disponibile un ottimo documento (Richard Franke, "Interpolazione di dati sparsi: Test di alcuni metodi", Mathematics of Computation, 1982.)

Forse il metodo più comune utilizzato si basa su una triangolazione dei dati. Crea 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. Ciò consente di interpolare linearmente all'interno del triangolo. Se si utilizza MATLAB, la funzione griddata è disponibile per questo scopo esplicito.)

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 dell'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 radiale" (spesso abbreviato RBF). Esistono molti di questi schemi, incluso Kriging, quando viene utilizzato dalla comunità di geostatistica.

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

Infine, inpainting è il nome di uno schema di interpolazione in cui gli elementi sono indicati in un array, ma in cui mancano elementi. Il nome si riferisce ovviamente a quello fatto da un conservatore d'arte che ha bisogno di riparare una lacrima o strappare un'opera d'arte preziosa.

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

L'idea alla base della pittura è in genere quella di formulare un problema al valore limite. Cioè, definire un'equazione differenziale parziale sulla regione in cui è presente un buco. Utilizzando i valori limite noti, riempire il buco risolvendo il PDE per gli elementi sconosciuti. Questo può essere intensivo dal punto di vista computazionale se esiste un numero enorme di elementi sconosciuti, poiché richiede in genere la soluzione di almeno un massiccio sistema sparso di equazioni lineari. Se il PDE non è lineare, diventa ancora un problema più intenso. Una scelta semplice, ragionevolmente buona per il PDE è il Laplacian, 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

Le scelte migliori per la PDE possono provenire da PDE non lineari. Una volta tale è l'equazione di Navier / Stokes. È adatto per modellare i tipi di superfici normalmente visti, ma è anche più difficile da gestire. Come in molte sfaccettature della vita, ottieni ciò per cui paghi.

Considerando che si tratta di un semplice progetto scolastico, probabilmente la tecnica di interpolazione più semplice da attuare è il "vicino più vicino"

Per ogni punto di dati mancante trovi il "riempimento" più vicino punto dati e usalo come valore.

Se vuoi migliorare un po 'di più i risultati, allora puoi dire, trovare K punti 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.

Esistono migliaia di altre tecniche, ma il vicino più vicino è probabilmente il più facile da implementare.

se capisco che il tuo bisogno è il seguente.

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

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

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

Puoi google questi filtri e otterrai risposte da implementare.

Buona fortuna.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top