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

Następny program wykorzystuje podaną w poprzednim rozdziale funkcję graph2D() do zaprezentowania algorytmu w sposób graficzny. W programie generowana jest funkcja sin(x) w przedziale [0,2π]. Następnie program generuje 1000 punktów należących do przedziału [2,4] i wyznacza wartość funkcji algorytmem interpolacji do najbliższego sąsiada.

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

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <graphics.h>

using namespace std;

// Przybliżenie zera
double const EPS = 0.0000000001;

// Zmienne globalne
const int NX = 51;       // Liczba punktów na wykresie

double xg[NX],yg[NX];    // Współrzędne punktów wykresu, posortowane wg x
double xgs,ygs,xge,yge;  // Współrzędne obszaru wykresu na płaszczyźnie

const int NV = 9;        // Przybliżona liczba działek + 2
double xvlow,xvhigh,xdv; // Zmienne do opisu osi x
double yvlow,yvhigh,ydv; // Zmienne do opisu osi y

// Szerokość i wysokość obszarów wykresu na ekranie i na płaszczyźnie
int W,H;
double Wg,Hg;

// Funkcja, której wykres będzie tworzony
//---------------------------------------
double f(double x)
{
    return sin(x);
}

// Funkcja oblicza parametry działek
// vmin,vmax - przedział działkowany
// vlow  - pierwsza działka
// vhigh - ostatnia działka
// dv    - odstęp pomiędzy działkami
//----------------------------------
void get_v(double vmin, double vmax,
           double & vlow, double & vhigh, double & dv)
{
    double ldv,pdv,mdv,len;

    // Jeśli przedział ma zerową długość, to modyfikujemy jego końce
    if(fabs(vmin - vmax) < EPS)
    {
        vmin -= 1;
        vmax += 1;
    }

    // Obliczamy długość przedziału
    len = vmax - vmin;

    // Obliczamy wstępną odległość pomiędzy działkami
    dv = len / ( NV - 1 );

    // Modyfikujemy dv do "ładnej wartości"
    ldv = floor(log10(dv));
    pdv = pow(10,ldv);
    mdv = (int)(dv/pdv + 0.5);

    // Modyfikujemy współczynnik mdv do wartości 1, 2 lub 5
    if(mdv > 5.0)      mdv = 10.0;
    else if(mdv > 2.0) mdv = 5.0;
    else if(mdv > 1.0) mdv = 2.0;
    else               mdv = 1.0;

    // Obliczamy ostateczną odległość pomiędzy działkami
    dv = mdv * pdv;

    // Obliczmy pozycję pierwszej działki
    vlow = dv * floor(vmin / dv);

    // Obliczamy pozycję ostatniej działki
    vhigh = dv * ceil(vmax / dv);
}

// Funkcja wylicza punkty wykresu oraz ustala wstępne wartości
// współrzędnych xgs,ygs,sge,yge.
// W parametrach przekazywany jest przedział argumentów funkcji.
//--------------------------------------------------------------
void set_xy(double xp, double xk)
{
    double dx = (xk - xp) / (NX - 1); // Obliczamy odległość dwóch punktów x
    int i;

    for(i = 0; i < NX; i++)
    {
        xg[i] = xp + i * dx; // Współrzędna x punktu i-tego
        yg[i] = f(xg[i]);    // Współrzędna y punktu i-tego

        // Wyznaczamy max i min funkcji w przedziale, aby objąć ją prostokątem
        if(!i) // tzn. jeśli i == 0
            ygs = yge = yg[i];
        else
        {
            if(yg[i] > ygs) ygs = yg[i];
            if(yg[i] < yge) yge = yg[i];
        }
    }
    // Obliczamy działki na osi OX i OY

    get_v(xp,xk,xvlow,xvhigh,xdv);
    xgs = xvlow;
    xge = xvhigh;
    get_v(yge,ygs,yvlow,yvhigh,ydv);
    ygs = yvhigh;
    yge = yvlow;
}

// Funkcja rysuje wykres w zadanym przedziale
// xp,xk - początek i koniec przedziału
//-------------------------------------------
void graph2D(double xp, double xk)
{
    // Najpierw ustawiamy tablicę współrzędnych punktów wykresu wraz z danymi globalnymi
    set_xy(xp,xk);

    // Ustalamy rozmiary obszaru wykresu w oknie graficznym
    int xs = 0;
    int xe = getmaxx() - 80;
    int ys = 0;
    int ye = getmaxy() - 32;

    // Obliczamy szerokość i wysokość obszarów
    W = xe - xs + 1;
    H = ye - ys + 1;
    Wg = xvhigh - xvlow;
    Hg = yvhigh - yvlow;

    // Obszar wykresu wypełniamy kolorem białym
    setfillstyle(SOLID_FILL,WHITE);
    bar(xs,ys,xe+2,ye+2);

    // Rysujemy linie podziałkowe w kolorze jasnoniebieskim
    // Na końcach linii umieszczamy wartość podziałki

    int xd,yd;
    double x,y;

    // Pionowe
    x = xvlow;
    while(x <= xvhigh)
    {
        xd = (x - xgs) * W / Wg;
        setlinestyle(DOTTED_LINE,0,NORM_WIDTH);
        setcolor(LIGHTCYAN);
        line(xd,ys,xd,ye);
        setcolor(YELLOW);
        bgiout << x;
        outstreamxy(xd, ye+16);
        x += xdv;
    }

    // Poziome
    y = yvlow;
    while(y <= yvhigh)
    {
        yd = (ygs - y) * H / Hg;
        setlinestyle(DOTTED_LINE,0,NORM_WIDTH);
        setcolor(LIGHTCYAN);
        line(xs,yd,xe,yd);
        setcolor(LIGHTRED);
        bgiout << y;
        outstreamxy(xe+4, yd);
        y += ydv;
    }

    // Ustawiamy parametry linii osi współrzędnych
    setcolor(BLUE);
    setlinestyle(SOLID_LINE,0,NORM_WIDTH);

    // Jeśli oś wpada w obszar wykresu, to ją rysujemy
    // Najpierw oś OX
    yd = ygs * H / Hg;
    if((yd >= 0) && (yd <= ye)) line(xs,yd,xe,yd);

    // Następnie oś OY
    xd = -xgs * W / Wg;
    if((xd >= 0) && (xd <= xe)) line(xd,ys,xd,ye);

    // Ustawiamy parametry linii wykresu
    setcolor(GREEN);
    setlinestyle(SOLID_LINE,0,THICK_WIDTH);

    // Rysujemy wykres
    int i;
    for(i = 0; i < NX; i++)
    {
        // Obliczamy współrzędne ekranowe punktu wykresu
        xd = (xg[i] - xgs) * W / Wg;
        yd = (ygs - yg[i]) * H / Hg;

        // W pierwszym punkcie ustawiamy pozycję, w kolejnych rysujemy linie
        if(!i) moveto(xd,yd);
        else   lineto(xd,yd);
    }
}

//----------------
// PROGRAM GŁÓWNY
//----------------
int main()
{
   int x1,x2,y1,i,j,imin;
   double x,xmin,xabs;

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

   // Tworzymy okno graficzne o wybranym przez użytkownika rozmiarze
   initwindow(800, 600,"Wykres dla algorytmu aproksymacji do najbliższego sąsiada");

   // Ustawiamy parametry strumienia wyjściowego (potrzebne do opisu osi)
   bgiout << setprecision(4) << fixed;

   // Rysujemy wykres
   graph2D(0,6.28);

   // Na osi OX oznaczamy przedział [3,5]
   x1 = (2.0 - xgs) * W / Wg;
   x2 = (4.0 - xgs) * W / Wg;
   y1 = ygs * H / Hg;
   setcolor(LIGHTRED);
   line(x1,y1,x2,y1);
   line(x1,y1-10,x1,y1+10);
   line(x2,y1-10,x2,y1+10);
   setbkcolor(WHITE);
   bgiout << "2.00";
   outstreamxy(x1+2,y1+12);
   bgiout << "4.00";
   outstreamxy(x2+2,y1+12);

   // Generujemy 1000 punktów w przedziale [2,4]
   // i wyznaczamy dla nich wartość funkcji
   // po czym wartości te umieszczamy na wykresie
   for(j = 0; j < 1000; j++)
   {
       // Generujemy punkt w przedziale [2,4]
       x = 2 + 2 * (rand() / (double) RAND_MAX);

       imin = 0;
       xmin = fabs(xg[0] - x);
       for(i = 1; i < NX; i++)
       {
           xabs = fabs(xg[i] - x);
           if(xabs < xmin)
           {
               xmin = xabs;
               imin = i;
           }
       }

       // Rysujemy znaleziony punkt na wykresie
       x1 = (x - xgs) * W / Wg;
       y1 = (ygs - yg[imin]) * H / Hg;
       putpixel(x1,y1,BLACK);

   }

   // Czekamy na klawisz
   getch();

   // Zamykamy okno graficzne i kończymy
   closegraph();
   return 0;
}

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.