Interpolation au plus proche voisin

L'interpolation au plus proche voisin (ou interpolation arrondie) est une méthode simple d'interpolation numérique d'un ensemble de points en dimension 1 ou supérieure (interpolation multivariée).

Interpolation au plus proche voisin (fonction bleue) appliquée à un ensemble de points (en rouge) répartis uniformément.

Le problème de l'interpolation consiste à calculer une valeur approchée d'une fonction en un point quelconque à partir des valeurs de la fonction données en des points définis. L'algorithme du plus proche voisin détermine la valeur recherchée comme étant égale à la valeur au point le plus proche, sans considérer les autres valeurs connues, construisant ainsi une fonction constante par morceaux. L'algorithme est très simple à implémenter et couramment utilisé (avec du MIP mapping) pour les rendus 3D en temps réel pour les couleurs d'une surface texturée.

Lien avec les diagrammes de Voronoi

modifier

Pour un ensemble de points dans l'espace, le diagramme de Voronoï est la décomposition de cet espace en cellules, chacune associée à un point, telle que pour tout point de l'espace, le point le plus proche est contenu dans la même cellule. On retrouve ainsi l'idée de l’interpolation au plus proche voisin, en fixant la valeur de la fonction dans une cellule comme constante et égale à la valeur au point associé.

 
Par l'algorithme au plus proche voisin, l'interpolant sera constant par morceaux sur chaque cellule du diagramme de Voronoï de l'ensemble de points (en noir), ici en 2D.

Applications

modifier

L'interpolation au plus proche voisin est une technique simple d'application dans le traitement d'images, mais déconseillée car elle crée un fort effet de crénelage[1].

Voir aussi

modifier

Notes et références

modifier
  1. Patrick Bonnin, Les Bases du Traitement d'Image et de la Vision Industrielle et Robotique (lire en ligne)