Wpisany przez Tomasz Lubiński,
29 marca 2006 20:12
Algorytm najbliższego sąsiedzta (ang. Nearest Neighbour) jest najprostszym algorytmem zmiany wielkości obrazu (ang. resampling). Każdy piksel obrazu wynikowego przyjmuje niezmodyfikowaną wartość piskla obrazu wejściowego położonego najbliżej aktualnie rozpatrywanego punktu. Schemat poniżej pokazuje dwa nałożone na siebie obrazy (4x4 oraz 5x5)
W przypadku przejścia z obrazu 4x4 na obraz 5x5 zdarza się, że cztery punkty obrazu wynikowego przyjmują wartość tego samego punktu obrazu wejściowego (jest on najbliższym sąsiadem dla czterech punktów).
W przypadku przejścia z obrazu 5x5 na obraz 4x4 zdarza się, że niektóre punkty obrazu wejściowego nie mają swoich odpowiedników w obrazie wynikowym, są one tracone.
Matematycznie można to zapisać następująco:
niech, widthsrc oraz widthdst oznaczają odpowiednio szerokość obrazu wejściowego i obrazu wyjściowego, a heightsrc oraz heightdst odpowiednio wysokość obrazu wejściowego i wyjściowego.
Przyjmiemy wówczas, że:
Należy przekształcić obraz 4x10 w obraz 2x16.
Obliczamy współczynniki powiększenia:
ratiox = widthsrc / widthdst = 4/2 = 2
ratioy = heightsrc / heightdst = 10 / 16 = 0.625
Punkt (0,0)
x = i*ratiox = 0*2
y = j*ratioy = 0*0.625
Zatem punkt (0,0) obrazu wyjściowego przyjmie wartość punktu (0,0) obrazu wejściowego.
Punkt (0,1)
x = i*ratiox = 0*2
y = j*ratioy = 1*0.625 = 0.625 ~= 1
Zatem punkt (0,1) obrazu wyjściowego przyjmie wartość punktu (0,1) obrazu wejściowego.
Punkt (0,2)
x = i*ratiox = 0*2
y = j*ratioy = 2*0.625 = 1.25 ~= 1
Zatem punkt (0,2) obrazu wyjściowego przyjmie wartość punktu (0,1) obrazu wejściowego.
Punkt (0,3)
x = i*ratiox = 0*2
y = j*ratioy = 3*0.625 = 1,875 ~= 2
Zatem punkt (0,3) obrazu wyjściowego przyjmie wartość punktu (0,2) obrazu wejściowego.
...
Punkt (1,0)
x = i*ratiox = 1*2
y = j*ratioy = 0*0.625
Zatem punkt (1,0) obrazu wyjściowego przyjmie wartość punktu (2,0) obrazu wejściowego.
..., itd
Algorytm ten jest szybki ponieważ nie wymaga wielu obliczeń, jednakże przy dużych powiększeniach widać wyraźnie pojedyncze piksle z obrazu oryginalnego. Dzieje się tak ponieważ dla wielu punktów obrazu wyjściowego brany jest ten sam punkt obrazu wejściowego. Natomiast przy pomniejszaniu w obrazie wynikowym tracimy całe linie punktów z obrazu wejściowego.
Schemat poniżej pokazuje zdjęcie oryginalne (na środku) powiększone czterokrotnie (po prawej) oraz pomniejszone czterokrotnie (po lewej)
Ustaw ścieżkę do pliku (lub pozostaw tą domyślną), wczytaj plik a następnie użyj przycisku "Korekcja gamma" w celu sprawdzenia działania metody.
Ze względu na zabezpieczenia w przeglądarkach, skrypt otwiera wyłącznie pliki graficzne w obrębie naszego serwisu, np:
http://www.algorytm.org/images/stories/po/anaglif_lewy.jpg
http://www.algorytm.org/images/stories/po/orig.gif
http://www.algorytm.org/images/stories/mb/hsv.jpg
niech, widthsrc oraz widthdst oznaczają odpowiednio szerokość obrazu wejściowego i obrazu wyjściowego, a heightsrc oraz heightdst odpowiednio wysokość obrazu wejściowego i wyjściowego.
Przyjmiemy wówczas, że:
ratio_x = \frac{width_{src}}{width_{dst}}\\\\
ratio_y = \frac{height_{src}}{height_{dst}}
Wówczas dla każdego punktu obrazu wyjściowego (i oznacza kolumnę, j oznacza wiersz - zakładamy, że indeksy liczone są od 0 włącznie) przeprowadzamy następujące obliczenia:
x = i*ratio_x\\\\
y = j*ratio_y
Oznacza to, że dla punku o współrzędnych (i, j) obrazu wyjściowego należy użyć wartości punktu o współrzędnych (x, y) obrazu wejściowego. Przy czym x oraz y należy zaokrąglić (bądź obciąć część dziesiętną).Przykład:
Należy przekształcić obraz 4x10 w obraz 2x16.
Obliczamy współczynniki powiększenia:
ratiox = widthsrc / widthdst = 4/2 = 2
ratioy = heightsrc / heightdst = 10 / 16 = 0.625
Punkt (0,0)
x = i*ratiox = 0*2
y = j*ratioy = 0*0.625
Zatem punkt (0,0) obrazu wyjściowego przyjmie wartość punktu (0,0) obrazu wejściowego.
Punkt (0,1)
x = i*ratiox = 0*2
y = j*ratioy = 1*0.625 = 0.625 ~= 1
Zatem punkt (0,1) obrazu wyjściowego przyjmie wartość punktu (0,1) obrazu wejściowego.
Punkt (0,2)
x = i*ratiox = 0*2
y = j*ratioy = 2*0.625 = 1.25 ~= 1
Zatem punkt (0,2) obrazu wyjściowego przyjmie wartość punktu (0,1) obrazu wejściowego.
Punkt (0,3)
x = i*ratiox = 0*2
y = j*ratioy = 3*0.625 = 1,875 ~= 2
Zatem punkt (0,3) obrazu wyjściowego przyjmie wartość punktu (0,2) obrazu wejściowego.
...
Punkt (1,0)
x = i*ratiox = 1*2
y = j*ratioy = 0*0.625
Zatem punkt (1,0) obrazu wyjściowego przyjmie wartość punktu (2,0) obrazu wejściowego.
..., itd
Algorytm ten jest szybki ponieważ nie wymaga wielu obliczeń, jednakże przy dużych powiększeniach widać wyraźnie pojedyncze piksle z obrazu oryginalnego. Dzieje się tak ponieważ dla wielu punktów obrazu wyjściowego brany jest ten sam punkt obrazu wejściowego. Natomiast przy pomniejszaniu w obrazie wynikowym tracimy całe linie punktów z obrazu wejściowego.
Schemat poniżej pokazuje zdjęcie oryginalne (na środku) powiększone czterokrotnie (po prawej) oraz pomniejszone czterokrotnie (po lewej)
Przykład w JavaScript:
Ustaw ścieżkę do pliku (lub pozostaw tą domyślną), wczytaj plik a następnie użyj przycisku "Korekcja gamma" w celu sprawdzenia działania metody.
Ze względu na zabezpieczenia w przeglądarkach, skrypt otwiera wyłącznie pliki graficzne w obrębie naszego serwisu, np:
http://www.algorytm.org/images/stories/po/anaglif_lewy.jpg
http://www.algorytm.org/images/stories/po/orig.gif
http://www.algorytm.org/images/stories/mb/hsv.jpg
Implementacje
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C/C++ | Borland Builder 6 | .cpp | .cpp | ***** / 2 |
Tomasz Lubiński | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 1 |
Tomasz Lubiński | JavaScript | Firefox 3.0+, Safari 3.0+, Chrome 3.0+, Opera 9.5+, IE 9.0+ | .js | .js | ***** / 0 |
Poprawiony: 26 sierpnia 2012 08:38