Comment interpoler entre les points de données?

Question

Je développe actuellement un logiciel utilisant opencv et qt pour tracer les points de données. Je dois pouvoir remplir une image à partir de données incomplètes. Je veux interpoler entre les points que j'ai. Quelqu'un peut-il recommander une bibliothèque ou une fonction qui pourrait m'aider? Je pensais que peut-être la méthode opencv reMap mais je n'arrive pas à obtenir que ça fonctionne.

Les données sont une matrice à deux dimensions de valeurs d'intensité. Je veux créer une image de quelque sorte. C'est un projet d'école.

Answer 1

Ouf! Grand sujet.

Le " right " La réponse dépend beaucoup de votre domaine de problèmes et de divers détails de ce que vous faites.

Interpoler dans plus d'une dimension nécessite de faire des choix. Je suppose que vous tracez sur une grille régulière, mais que certains de vos points de la grille ne contiennent aucune donnée. Grande question: les points manquants sont-ils rares ou font-ils de gros blobs?

Vous ne pouvez pas ajouter des informations, vous essayez donc simplement d'établir quelque chose qui aura l'air , OK.

Suggestion conceptuelle simple (mais la mise en oeuvre peut être un peu difficile):

Pour chaque région sur les données manquantes, identifiez tous les points périphériques. C'est trouver les x dans cette figure

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

où les. sont les points où il manque des données, et les x et o ont des données (pour un seul point manquant, ce seront les quatre plus proches voisins). Renseignez chaque point de données manquant avec une moyenne sur les points périphériques autour de ce blob. Pour le rendre lisse, pondérez chaque point par 1 / d où d est la distance entre les deux points du taxidriver (delta x + delta y).

D'avant, nous avions des détails:

En l’absence de ce type d’informations, avez-vous essayé une interpolation linéaire directe? Si vos données sont raisonnablement denses, cela pourrait le faire pour vous et il est assez simple de coder en ligne lorsque vous en avez besoin.

La prochaine étape est généralement une spline cubique, mais pour cela, vous voudrez probablement récupérer une implémentation existante.

Lorsque j'ai besoin de quelque chose de plus puissant qu'une interpolation linéaire rapide, j'utilise généralement ROOT (et choisissez l'une des options suivantes: les classes TSpline), mais cela risque d’être plus long que nécessaire.

Comme indiqué dans les commentaires, ROOT est big , et même s’il est rapide, il essaie de vous forcer à faire les choses à la racine, de sorte que cela puisse avoir un impact important sur votre programme.

Une interpolation linéaire entre (ou bien une extrapolation à partir de) deux points (x1, y1) et (x2, y2) vous donne

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

Answer 2

L’interpolation est un sujet complexe. Il existe une infinité de façons d'interpoler un ensemble de points, et ceci en supposant que vous souhaitiez réellement effectuer une interpolation et non un lissage d'aucune sorte. (Un interpolant reproduit exactement les points de données d'origine.) Et bien sûr, la nature 2D de ce problème rend les choses plus difficiles.

Il existe plusieurs systèmes d’interpolation de données dispersées en 2D. En fait, pour ceux qui y ont accès, un très bon article est disponible (Richard Franke, "Interpolation de données dispersées: tests de certaines méthodes", Mathematics of Computation, 1982.)

La méthode la plus couramment utilisée est peut-être basée sur une triangulation de vos données. Construisez simplement une triangulation du domaine à partir de vos points de données. Ensuite, tout point à l'intérieur de la coque convexe des données doit se trouver exactement dans l'un des triangles, sinon ce sera sur un bord partagé. Cela vous permet d'interpoler linéairement à l'intérieur du triangle. Si vous utilisez MATLAB, la fonction griddata est disponible à cette fin.)

Le problème lorsque vous essayez de remplir une image rectangulaire complète à partir de points dispersés est qu’il est très probable que les données ne s’étendent pas aux 4 coins du tableau. Dans ce cas, un schéma basé sur la triangulation échouera, car les coins du tableau ne sont pas situés à l'intérieur de la coque convexe des points dispersés. Une alternative consiste alors à utiliser des "fonctions de base radiales". (souvent abrégé RBF). Il existe de nombreux systèmes de ce type, notamment le Kriging, lorsqu'il est utilisé par la communauté géostatistique.

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

Enfin, inpainting est le nom d’un schéma d’interpolation dans lequel les éléments sont donnés dans un tableau, mais où il manque des éléments. Le nom fait évidemment référence à celui d'un conservateur d'art qui doit réparer une déchirure ou déchirer une œuvre d'art de valeur.

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

L’idée derrière inpainting est généralement de formuler un problème de valeur limite. C'est-à-dire, définissez une équation différentielle partielle sur la région où il y a un trou. En utilisant les valeurs limites connues, remplissez le trou en résolvant l’EDP des éléments inconnus. Cela peut nécessiter beaucoup de calcul s’il ya un grand nombre d’éléments inconnus, car cela nécessite généralement la solution d’un système d’équations linéaires au moins très volumineux. Si le PDE est un non linéaire, alors il devient un problème plus intensif pour le moment. Le laplacien est un choix simple et raisonnablement bon pour l’EDP: il en résulte un système linéaire qui s’extrapole bien. Encore une fois, je peux proposer une solution pour un utilisateur MATLAB.

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

Les meilleurs choix pour les PDE peuvent provenir des PDE non linéaires. Une fois telle est l’équation de Navier / Stokes. Il est bien adapté à la modélisation des types de surfaces généralement vus, mais il est également plus difficile à gérer. Comme dans de nombreux domaines de la vie, vous en avez pour votre argent.

Answer 3

Considérant qu'il s'agit d'un projet scolaire simple, la technique d'interpolation la plus simple à implémenter est probablement le "plus proche voisin"

.

Pour chaque point de données manquant, vous trouvez le " rempli " le plus proche point de données et l'utiliser comme valeur.

Si vous souhaitez améliorer un peu plus les résultats, vous pouvez alors trouver les K points de données les plus proches et utiliser leur moyenne pondérée comme valeur de votre point de données manquant.

le poids pourrait être proportionnel à la distance du point par rapport au point de données manquant.

Il existe d'innombrables autres techniques, mais le plus proche voisin est probablement la plus facile à mettre en œuvre.

Answer 4

si je comprends que votre besoin est le suivant.

Je pense que vous avez un sous-ensemble de x, y, intensité pour une dimension de L par W et que vous souhaitez remplir pour tout X allant de 0 à L et Y allant de 0 à W.

Si telle est votre question, la solution consiste à obtenir d'autres intensités à l'aide de filtres.

Je pense qu'un filtre Bayer ou un filtre gaussien ferait le travail à votre place.

Vous pouvez rechercher ces filtres dans Google et obtenir des réponses à mettre en œuvre.

Bonne chance.