Comment interpoler entre les points de données?

Question

Je développe actuellement un logiciel utilisant opencv et qt qui trace des 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 peut-être à la méthode opencv reMap mais je n'arrive pas à faire marcher ça.

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.

La "bonne" réponse dépend beaucoup sur votre domaine de problème et de divers détails de ce que vous faites.

Interpoler dans plus d'une dimension nécessite de faire quelques choix. Je suppose que vous tracez sur une grille régulière, mais que certains de vos points de grille n'ont pas de données. Grande question: les points manquants sont-ils épars, ou font-ils de gros blobs?

Vous ne pouvez pas ajouter de l'information, de sorte que vous êtes juste essayer d'établir quelque chose qui va regarder OK.

suggestion conceptuellement simple (mais la mise en œuvre peut être un travail):

Pour chaque région sur les données manquantes, identifier tous les points de bord. C'est de trouver les x dans cette figure

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

où les. Ce sont les points de données manquantes, et les x et les O contiennent des données (pour un seul point manquant, ce sera les quatre voisins les plus proches). Remplissez chaque point de données manquantes avec une moyenne sur les points de contour autour de ce blob. Pour le rendre lisse, le poids de chaque point par 1/d où d est la distance taxidriver (delta x + delta y) entre les deux points ..

---

De avant que nous ayons tous les détails:

En l'absence de ce genre d'information, avez-vous essayé directement l'interpolation linéaire? 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.

---

Quand je besoin de quelque chose de plus puissant qu'une interpolation linéaire rapide, j'utilise habituellement ROOT (et de choisir l'une des classes TSpline), mais cela peut être plus frais généraux que vous avez besoin. Comme noté dans les commentaires, ROOT est big, et bien qu'il soit rapide, il essaie de vous forcer à faire les choses de la façon ROOT, de sorte qu'il peut avoir un grand effet sur votre programme.

---

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

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

Answer 2

si je comprends que votre besoin est la suivante.

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

Si cette est votre question, alors la solution est d'obtenir d'autres intensités en utilisant des filtres. Je pense que le filtre Bayer ou le filtre Gaussien ferait le travail pour vous.

Vous pouvez google ces filtres et vous obtiendrez des réponses à mettre en œuvre.

Bonne chance.

Answer 3

L'interpolation est un sujet complexe. Il y a une infinité de façons d'interpoler un ensemble de points, et cela en supposant que vous souhaitiez vraiment faire une interpolation, et non un lissage de quelque sorte que ce soit. (Un interpolant reproduit exactement les points de données d'origine.) Et bien sûr, la nature bidimensionnelle de ce problème rend les choses plus difficiles.

Il existe plusieurs schémas communs pour l'interpolation de données diffusées dans 2-d. En fait, pour ceux qui y ont accès, un très bon article est disponible (Richard Franke, «Interpolation des données dispersées: tests de certaines méthodes», Mathematics of Computation, 1982.)

Peut-être que la méthode la plus couramment utilisée est basée sur une triangulation de vos données. Construire 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, ou sur un bord partagé. Cela vous permet d'interpoler linéairement à l'intérieur du triangle. Si vous utilisez MATLAB, alors la fonction griddata est disponible à cet effet.)

Le problème lorsque vous essayez de remplir une image rectangulaire complète à partir de points dispersés est que très probablement les données ne s'étendent pas aux 4 coins de la tableau. Dans ce cas, un schéma basé sur la triangulation échouera, car les coins du tableau ne se trouvent pas à l'intérieur de la coque convexe des points dispersés. Une alternative consiste alors à utiliser des "fonctions de base radiales" (RBF souvent abrégé). Il y a beaucoup de tels schémas à trouver, y compris Kriging, quand ils sont utilisés par la communauté géostatistique.

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

Enfin, inpainting est le nom d'un schéma d'interpolation où les éléments sont donnés dans un tableau, mais où il y a des éléments manquants. Le nom se réfère évidemment à celui fait par un conservateur d'art qui a besoin de réparer une déchirure ou déchirer dans une œuvre d'art précieux.

http://en.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éfinir 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 la PDE pour les éléments inconnus. Cela peut être très intensif en termes de calcul s'il y a un grand nombre d'éléments inconnus, car cela nécessite généralement la solution d'au moins un système massif d'équations linéaires. Si le PDE est un non linéaire, alors il devient encore un problème plus intensif.Un choix simple et raisonnablement bon pour l'EDP est le Laplacien, qui résulte en un système linéaire qui extrapole bien. Encore une fois, je peux offrir une solution pour un utilisateur MATLAB.

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

choix mieux pour les PDE peuvent provenir de PDEs 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 à traiter. Comme dans de nombreuses facettes de la vie, vous obtenez ce que vous payez.

Answer 4

Compte tenu de c'est un simple projet d'école, sans doute la technique d'interpolation plus facile à mettre en œuvre est le « plus proches voisins »

Pour chaque données manquantes indiquent que vous trouvez le point de données « rempli » le plus proche et l'utiliser comme la valeur.

Si vous voulez améliorer un peu plus les retouches, vous pouvez alors indiquer, trouver 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'autres techniques zillion, mais le plus proche voisin est probablement le plus facile à implémenter.