Wpisany przez Tomasz Lubiński,
03 kwietnia 2006 20:07
Algorytm interpolacji dwuliniowej (ang. Bilinear Interpolation), zwany inaczej metodą podwójnej interpolacji liniowej jest algorytmem zmiany wielkości obrazu (ang. resampling) nieco bardziej zawansowanym niż algorytm najbliższego sąsiedzta (ang. Nearest Neighbour). Każdy piksel obrazu wynikowego przyjmuje wartość na podstawie wartości czterech sąsiednich punktów obrazu wejściowego. Nazwa algorytmu bierze się z fatu, iż interpolację liniową przeprowadzamy dwukrotnie - jeden raz w poziome i jeden raz w pionie.
Najpierw należy obliczyć, w którym miejscu w obrazie wejściowym znajduje się rozpatrywany punkt obrazu wyjściowego. Schemat poniżej pokazuje dwa nałożone na siebie obrazy (4x4 oraz 5x5)

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:

Teraz przeprowadzimy interpolację liniową w kierunku poziomym:
Należy przekształcić obraz 4x10 w obraz 5x16.
Obliczamy współczynniki powiększenia:
ratiox = widthsrc / widthdst = 4/5 = 0.8
ratioy = heightsrc / heightdst = 10 / 16 = 0.625
Obliczmy wartość dla punktu (3, 7).
x = i*ratiox = 3 * 0.8 = 2.4
y = j*ratioy = 7 * 0.625 = 4.375
A więc będziemy musieli wziąć pod uwagę w naszych obliczeniach wartości w punktach (2, 4), (2, 5), (3, 4) oraz (3, 5). Niech wynoszą one odpowiednio 20, 29, 42, 58. Obliczymy teraz współczynniki a i b - są to częsci dziesiętne odpowiednich składowych.
a = 0.4
b = 0.375
Przeprowadzimy teraz interpolację liniową w kierunku poziomym:
Fa,0 = (1-a)*F0,0 + a*F1,0 = (1-0.4)*20 + 0.4*42 = 12 + 16.8 = 28.8
Fa,1 = (1-a)*F0,1 + a*F1,1 = (1-0.4)*29 + 0.4*58 = 17.4 + 23.2 = 40.6
A następnie na podstawie tych wyników w kierunku pionowym:
Fa,b = (1-b)*Fa,0 + b*Fa,1 = (1-0.375)*28.8 + 0.375*40.6 = 18 + 15.225 = 33.225
A więc wartość składowej w punkcie (3, 7) wynosić będzie 33.225. Obliczenia takie należy powtórzyć dla wszystkich punktów i wszystkich składowych.
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
Najpierw należy obliczyć, w którym miejscu w obrazie wejściowym znajduje się rozpatrywany punkt obrazu wyjściowego. Schemat poniżej pokazuje dwa nałożone na siebie obrazy (4x4 oraz 5x5)

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. Przykładowe umiejscowienie tak wyliczonego punktu pokazano na schemacie poniżej. W wyjątkowej sytuacji - np. dla punktów znajdujących się na krawędziach obrazu odległość a i/lub b wynosi zero. Zuważyć należy też iż, do obliczeń na krawędziach lewej i dolnej obrazu potrzebny będzie piksel leżący poza obrazem wejściowym. Jego wartość podczas obliczeń nie będzie brana jednak pod uwagę co wynika z przytoczonych poniżej wzorów interpolacji dwuliniowej.
Teraz przeprowadzimy interpolację liniową w kierunku poziomym:
F_{a,0} = (1-a)*F_{0,0} + a*F_{1,0}\\\\
F_{a,1} = (1-a)*F_{0,1} + a*F_{1,1}
A następnie na podstawie tych wyników w kierunku pionowym:
F_{a,b} = (1-b)*F_{a,0} + b*F_{a,1}
Obliczenia takie należy przeprowadzić dla każdej składowej koloru z osobna.Przykład:
Należy przekształcić obraz 4x10 w obraz 5x16.
Obliczamy współczynniki powiększenia:
ratiox = widthsrc / widthdst = 4/5 = 0.8
ratioy = heightsrc / heightdst = 10 / 16 = 0.625
Obliczmy wartość dla punktu (3, 7).
x = i*ratiox = 3 * 0.8 = 2.4
y = j*ratioy = 7 * 0.625 = 4.375
A więc będziemy musieli wziąć pod uwagę w naszych obliczeniach wartości w punktach (2, 4), (2, 5), (3, 4) oraz (3, 5). Niech wynoszą one odpowiednio 20, 29, 42, 58. Obliczymy teraz współczynniki a i b - są to częsci dziesiętne odpowiednich składowych.
a = 0.4
b = 0.375
Przeprowadzimy teraz interpolację liniową w kierunku poziomym:
Fa,0 = (1-a)*F0,0 + a*F1,0 = (1-0.4)*20 + 0.4*42 = 12 + 16.8 = 28.8
Fa,1 = (1-a)*F0,1 + a*F1,1 = (1-0.4)*29 + 0.4*58 = 17.4 + 23.2 = 40.6
A następnie na podstawie tych wyników w kierunku pionowym:
Fa,b = (1-b)*Fa,0 + b*Fa,1 = (1-0.375)*28.8 + 0.375*40.6 = 18 + 15.225 = 33.225
A więc wartość składowej w punkcie (3, 7) wynosić będzie 33.225. Obliczenia takie należy powtórzyć dla wszystkich punktów i wszystkich składowych.
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 | ***** / 6 |
Tomasz Lubiński | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 3 |
Tomasz Lubiński | JavaScript | Firefox 3.0+, Safari 3.0+, Chrome 3.0+, Opera 9.5+, IE 9.0+ | .js | .js | ***** / 1 |
Poprawiony: 26 sierpnia 2012 08:40
Komentarze

-4
#
Tomek
2009-08-26 00:46
a co ze zmniejszaniem rozdzielczości tym algorytmem?
Odpowiedz | Odpowiedz z cytatem | Cytować

+5
#
kot_chaosa
2013-06-25 12:01
Panie, pan tu pomylił a z b, kruca-fuks pół życia straciłem na tym błędzie.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz