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).
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
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é.
Applications
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
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Nearest-neighbor interpolation » (voir la liste des auteurs).
- Patrick Bonnin, Les Bases du Traitement d'Image et de la Vision Industrielle et Robotique (lire en ligne)