Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz  

obrazek

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

obrazek

Interpolacja

Interpolacja do najbliższego sąsiada

SPIS TREŚCI
Podrozdziały

Definicje

Interpolacja do najbliższego sąsiada (ang. nearest-neighbor interpolation, proximal interpolation, point sampling) jest prostym sposobem aproksymacji, 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):

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 xi, aby wartość modułu | xi - x  | była najmniejsza. Geometrycznie oznacza to, iż na osi OX argument xi leży najbliżej argumentu x, czyli jest jego najbliższym sąsiadem. Wtedy przyjmujemy, że:

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

Na początek:  podrozdziału   strony 

Algorytm 1

W pierwszym algorytmie nie będziemy nic zakładać na temat aproksymowanej 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).

Algorytm interpolacji do najbliższego sąsiada

Dane wejściowe:

n liczba punktów funkcji.
X tablica n elementowa zawierająca argumenty x dla aproksymowanej funkcji.
Y tablica n elementowa zawierająca wartości funkcji dla argumentów z tablicy X.
x argument, dla którego mamy znaleźć aproksymowaną wartość funkcji.

Dane wyjściowe

aproksymowana wartość funkcji w punkcie x.

Zmienne pomocnicze

i indeks
xmin najmniejsza odległość argumentu z X od wartości x
imin pozycja najbliższego argumentu w X

Lista kroków

K01: imin ← 0 inicjujemy zmienne
K02: xmin ← | X [ 0 ] - x |  
K03: Dla i = 1,2,...,n-1,
wykonuj krok K04
szukamy najbliższego sąsiada
K04:     Jeśli | X [ i ] - x | < xmin,
    to xmin ← | X [ i ] - x |
        imin ← i
zapamiętujemy pozycję najbliższego elementu
K05: Zakończ z wynikiem Y [ imin ]  

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.

Przykładowy program w języku C++
// Interpolacja do najbliższego sąsiada
// (C)2019 mgr Jerzy Wałaszek
// Metody numeryczne
//-------------------------------------

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

// Stałe

const int N = 10; // Liczba próbek
const int M =  5; // Liczba interpolacji

// Program główny
//---------------

int main()
{
    setlocale(LC_ALL,"");
    cout << fixed << setprecision(4);

    // Inicjujemy generator pseudolosowy

    srand(time(NULL));

    // Próbki

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

    // Wyświetlamy próbki:

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

    // Interpolujemy
    cout << endl;
    cout << "Interpolacje:" << endl;
    double x, xmin, xabs;
    int imin,j;
    for(j = 0; j < M; j++)
    {
        x = 7 * (rand() / (double) RAND_MAX);
        imin = 0;
        xmin = fabs(X[0] - x);
        for(i = 1; i < M; i++)
        {
            xabs = fabs(X[i] - x);
            if(xabs < xmin)
            {
                xmin = xabs;
                imin = i;
            }
        }
       cout << "f(" << x << ") = " << setw(7) << Y[imin]
            << ", interpolacja do x = " << X[imin] << endl;
    }
    return 0;
}
Wynik
Interpolacja do najbliższego sąsiada
------------------------------------
Próbki funkcji:
f(4.0346) = -0.7790
f(3.2164) = -0.0747
f(1.9291) =  0.9365
f(5.9654) = -0.3125
f(1.9836) =  0.9160
f(2.0957) =  0.8654
f(3.1164) =  0.0252
f(3.9103) = -0.6952
f(4.6823) = -0.9995
f(1.2410) =  0.9461

Interpolacje:
f(0.4302) =  0.9365, interpolacja do x = 1.9291
f(6.2935) = -0.3125, interpolacja do x = 5.9654
f(1.8274) =  0.9365, interpolacja do x = 1.9291
f(0.1060) =  0.9365, interpolacja do x = 1.9291
f(2.3773) =  0.9160, interpolacja do x = 1.9836
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.