Interpolacja

Interpolacja do najbliższego sąsiada (ang. nearest-neighbor interpolation, proximal interpolation, point sampling) jest prostym sposobem interpolacji, który czasem wykorzystuje się w grafice komputerowej przy transformacjach obrazu.

Mamy ciąg wartości pewnej funkcji dla określonego ciągu jej argumentów (w praktyce dane te mogą pochodzić z pomiarów: argumentami są np. czasy dokonania pomiarów, a wartościami funkcji są wyniki tych pomiarów) :

\[\{x_1, x_2, ..., x_n\} \to \{f(x_1), f(x_2), ..., f(x_n)\}\]

Mamy pewien argument \(x\), dla którego chcemy oszacować wartość funkcji na podstawie ciągu jej wartości.

W ciągu argumentów znajdujemy taki argument \(x_i\), aby wartość modułu \(|x_i - x|\) była najmniejsza. Geometrycznie oznacza to, iż na osi OX argument \(x_i\) leży najbliżej argumentu \(x\), czyli jest jego najbliższym sąsiadem. Wtedy przyjmujemy, że:

\[f(x) = f(x_i)\]

Dokonaliśmy interpolacji do najbliższego sąsiada.

W algorytmie nie będziemy nic zakładać na temat interpolowanej funkcji i jej argumentów. Nasze dane wejściowe będą zadane jako \(n\) par liczb: argument \(x\) oraz wartość funkcji dla tego argumentu:

Kolejność argumentów \(x\) jest dowolna. Tego typu dane można przechowywać w dwóch tablicach: \(X\) – argumenty, \(Y\) – wartości funkcji. Tablice są \(n\) elementowe. Zadanie algorytmu polega na wyszukaniu w tablicy \(X\) pozycji argumentu najbliższego zadanemu \(x\), po czym algorytm zwraca z tablicy \(Y\) wartość funkcji dla wyszukanego argumentu. Algorytm ma liniową klasę złożoności obliczeniowej \(O(n)\), jest zatem bardzo szybki.

Algorytm interpolacji do najbliższego sąsiada

Dane wejściowe:

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Poniższy program generuje 10 pseudolosowych argumentów funkcji \(\sin(x)\) w przedziale od \(0\) do \(7\) i zapamiętuje je w tablicach \(X\) i \(Y\). Następnie generuje \(5\) losowych argumentów \(x\) w przedziale od \(0\) do \(7\) i interpoluje je za pomocą powyższego algorytmu.

// Interpolacja do najbliższego sąsiada
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne 0070
//-------------------------------------

#include <iostream>
#include <windows.h>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

// Stałe
//------
// Liczba próbek
const int N = 10;
// Liczba interpolacji
const int M =  5;
// 2*pi
const double PI2 = 2 * M_PI;

// Program główny
//---------------
int main()
{
  SetConsoleOutputCP(CP_UTF8);
  SetConsoleCP(CP_UTF8);
  cout << setprecision(6)
       << fixed;

  // Inicjujemy generator
  // pseudolosowy
  srand(time(nullptr));

  // Próbki
  double X[N],Y[N];
  int i;
  for(i = 0; i < N; i++)
  {
    X[i] = PI2 * (rand() /
           (double)RAND_MAX);
    Y[i] = sin(X[i]);
  }

  // Wyświetlamy próbki:

  cout <<
  "Interpolacja do najbliższego sąsiada\n"
  "------------------------------------\n"
  "\nPróbki funkcji:\n\n";
  for(i = 0; i < N; i++)
    cout << "f(" << X[i] << ") = "
         << setw(9) << Y[i]
         << endl;

  // Interpolujemy
  cout << "\nInterpolacje:\n\n";

  double x, xmin, xabs;
  int imin,j;

  for(j = 0; j < M; j++)
  {
    x = PI2 * (rand() /
        (double)RAND_MAX);
    imin = 0;
    xmin = fabs(X[0] - x);
    for(i = 1; i < N; i++)
    {
      xabs = fabs(X[i] - x);
      if(xabs < xmin)
      {
        xmin = xabs;
        imin = i;
      }
    }
    cout << "f(" << setw(9)
         << x << ") = "
         << setw(9) << Y[imin]
         << ", interpolacja do x = "
         << setw(9) << X[imin]
         << endl;
  }

  cout << endl;
  system("pause");
  return 0;
}

Interpolacja do najbliższego sąsiada
------------------------------------

Próbki funkcji:

f(1.915617) =  0.941136
f(1.208238) =  0.934993
f(2.721940) =  0.407443
f(6.139370) = -0.143320
f(0.737292) =  0.672286
f(1.039879) =  0.862343
f(4.777154) = -0.997903
f(5.152607) = -0.904659
f(2.654060) =  0.468448
f(5.207065) = -0.880123

Interpolacje:

f( 4.997670) = -0.904659, interpolacja do x =  5.152607
f( 2.270361) =  0.941136, interpolacja do x =  1.915617
f( 4.378115) = -0.997903, interpolacja do x =  4.777154
f( 5.007833) = -0.904659, interpolacja do x =  5.152607
f( 0.358387) =  0.672286, interpolacja do x =  0.737292

# Interpolacja do najbliższego sąsiada
# (C)2019 mgr Jerzy Wałaszek
# Metody numeryczne 0070
#-------------------------------------

from math import pi,sin
from random import uniform

# Stałe
#------
# Liczba próbek
N = 10
# Liczba interpolacji
M =    5
# 2*pi
PI2 = 2 * pi

# Program główny
#---------------

# Próbki
x = [uniform(0,PI2)
     for _ in range(N)]
y = [sin(z) for z in x]

# Wyświetlamy próbki:
print()
print("Interpolacja do "
      "najbliższego sąsiada\n"
      "------------------"
      "------------------\n\n"
      "Próbki funkcji:\n\n")
for i in range(N):
    print(f"f({x[i]:9.6f}) = "
          f"{y[i]:9.6f}")

 # Interpolujemy
print("\nInterpolacje:\n")

for j in range(M):
    xi = uniform(0,PI2)
    imin = 0
    xmin = abs(x[0] - xi)
    for i in range(1,N):
        xabs = abs(x[i] - xi)
        if xabs < xmin:
            xmin = xabs
            imin = i
    print(f"f({xi:9.6f}) = "
          f"{y[imin]:9.6f}"
          f", interpolacja do x = "
          f"{x[imin]:9.6f}")

print()
input("Naciśnij Enter...")