Bilineaarinen interpolaatio

Kuvassa on yksikköneliön sisälle interpoloitu bilineaarisella menetelmällä neliön nurkissa olevat arvot (meritty z:lla). Arvot on väritetty sateenkaaren eli spektrin väreillä siten, että sininen on nolla ja punainen on yksi. Spektrin värit "nousevat" siten sininen, syaani, vihreä, keltainen, oranssi ja punainen.

Bilineaarinen interpolaatio on matematiikassa approksimaatiomenetelmä, joka on lineaarisen interpolaatiomenetelmän kaksiulotteinen laajennus. Siinä tasoalueen pisteiden arvoja lasketaan lähimpien pisteiden arvojen avulla sovittamalla kahdessa suunnassa lineaarisia polynomeja eli interpolaatiosuoria. Koska lineaarisia sovituksia on kaksi, kutsutaan menetelmää bilineaariseksi. Yleisessä käytössä on ollut kaksi menetelmää, joista toinen hyödyntää kolme ja toinen neljä näytepistettä. Interpoloinnin seurauksena syntyy silloin joko lineaarisia- tai kvadraattisia pintoja. Näitä pintoja kutsutaan interpolanteiksi tai interpolaatiopinnoiksi.

Tasoalueella satunnaisesti sijaitsevat pisteet voidaan aina yhdistää toisiinsa kolmioiksi, jotka sivuavat toisensa tiiviisti. Kolmion sisällä tapahtuva bilineaarinen interpolaatio on siksi aina mahdollista toteuttaa yksinkertaisella tavalla. Satunnaisia tason pisteitä ei aina ole helppo yhdistää nelikulmioiksi, jotka olisivat aina konvekseja. Bilineaarinen interpolaatiomenetelmässä nelikulmion vastakkaisten sivujen väliset suorat tulisi leikata toisensa nelikulmion sisällä, mikä ei aina onnistu ei-konveksissa nelikulmiossa. Neljän pisteen bilineaarinen interpolaatio totetutetaankin yleensä pisteille, jotka sijaitsevat suorakulmion kärjissä. Silloin näytepisteet on otettu hilamaisen verkon solmukohdissa.

Aiemmin bilineaarista interpolaatiota käytettiin kartografiassa, luonnontieteellisessä tutkimuksessa ja numeerisessa matematiikassa. Nykyään yleisimpiä sovelluskohteita ovat sekä digitaalisten valokuvien kuvankäsittely, tietokonepelien hahmojen käsittely ja elokuva-alan tehosteet. Nykyään nelikulmiossa totetutetut bilineaariset interpolaatiot ovat suoritetuista algoritmeista yleisimpiä, koska esimerkiksi monet kuvankäsittelyohjelmat hallitsevat bilineaarisen kuvankäsittelyn.

Lineaarinen interpolaatio janalla

Alkuun voidaan esitellä lyhyesti yksiulotteisen lineaarisen interpolaation lausekkeet. Ensin muodostetaan interpolaatio lyhyellä välillä [0,1], jonka päätepisteissä funktio saa arvokseen $f(0)=f_1$ ja $f(1)=f_2$. Silloin välin sisäpisteiden arvoksi saadaan

$f(x)\approx a_0+a_{1}x=f_1+(f_2-f_1)x.$

Kun interpolaatio viedään toiseen väliin $[x_1,x_2]$, missä $f(x_1)=f_1$ ja $f(x_2)=f_2$, saadaan sisäpisteen arvoksi

$f(x)\approx a_0+a_{1}x=(f_1{x}_2-f_2{x}_1)+\frac{f_2-f_1}{x_2-x_1}x.$

Bilineaarinen interpolaatio kolmiossa

Vaikka kolmella näytepisteellä toteutettu lineaarinen interpolaatio jää suosiossa neljän pisteen menetelmälle, on sillä vielä etulyöntiasema tietyissä tilanteissa. Jokainen pinta, esimerkiksi tasot, pallopinnat tai aaltoilevat pinnat, voidaan miehittää epäsäännöllisellä näytepopulaatiolla. Tällaisellä pistejoukolla voidaan aina muodostaa kolmioita, jotka peittävät pinnan tarkasti ja joilla voidaan suorittaa bilineaarinen interpolaatio kaikille tason pisteille.

Kolmiomenetelmässä valitaan kaksi sivua, joihin merkitään kumpaankin yksi sisäpiste. Sisäpisteiden arvot lasketaan lineaarisella interpolaatiolla, jossa hyödynnetään sivujensa päätepisteiden arvoja. Toisessa vaiheessa yhdistetään sivujen sisäpisteet suoralla, jonka pisteet lasketaan lineaarisella interpolaatiolla edellisessä vaiheessa laskettujen arvojen avulla. Kolmion sisäpisteen arvo selviää kolmella interpolaatiolla.

Yksikkökolmiossa: bilineaarisesti

Edellinen laskentamenetelmä ei sovellu tilanteisiin, jossa on tilattu bilineaarinen interpolaatio tiettyyn kolmion sisäpisteeseen. Siinä on ongelmana määrittää sivujen pisteet, jotta niiden lineaarinen interpolaatio voidaan suorittaa. Edullinen lähestymistapa on suorittaa kolmiolle affiinimuunnos suorakulmaiselle tasakylkiselle kolmiolle, jonka sivut ovat origon vieressä sijaitsevan yksikköneliön [0, 1]×[0, 1] sivuilla. Tätä kolmiota kututaan tässä yksikkökolmioksi ja sen kärkien koordinaatit ovat (0, 0), (1, 0) ja (0, 1).

Yksikkökolmion sisäpisteen (x, y) interpoloitua arvoa merkitään tässä f(x, y). Merkitään kolmion kärkien tunnetut funktion arvot f(0, 0) = f₀₀,f(0, 1) = f₀₁ ja f(1, 0) = f₁₀. Kohtisuorilla sivuilla suoritetut lineaarit interpoloinnit tuottavat arvot f(a, 0) = f_a0 ja f(0, b) = f_0b seuraavasti

$f_{a0}\approx f_{00}+(f_{10}-f_{00})a$

$f_{0b}\approx f_{00}+(f_{01}-f_{00})b$

Kun interpoloidaan haluttua pistettä f(x, y) = f_xy, kannattaa interpolointiin valita kolmion hypotenuusan suuntainen suora, koska sen päätepisteet ovat yhtä etäällä origosta. Mainittu etäisyys pisteen (x, y) interpoloimiseksi on a = b = x + y. Edelliset tulokset kirjoitetaan silloin

$f_{(x+y)0}\approx f_{00}+(f_{10}-f_{00})(x+y)$

$f_{0(x+y)}\approx f_{00}+(f_{01}-f_{00})(x+y).$

Koska pisteen (x, y) etäisyys päätepisteestään hypotenuusan suuntaisella suoralla on verrannollinen koordinaatin x ja matkan x + y suhteeseen, voidaan haluttu interpolaatio kirjoittaa (pisteestä (0, x + y) lukien)

$f_{xy}=f(x,y)\approx f_{0(x+y)}+(f_{(x+y)0}-f_{0(x+y)})\frac{x}{x+y}.$

Yksikkökolmiossa: tasopinnan sovitys

Vaikka pinnansovitus ei ole billineaarista interpolointia, voidaan asiaa sivuta myös tässä. Menetelmän tuottaman pinnan laatu selviää, kun sieventää edellisen laskelman viimeinen lauseke:

$f_{xy}=f(x,y)\approx f_{00}+(f_{10}-f_{00})x+(f_{01}-f_{00})y.$

Interpolaatiopisteet muodostavat (lausekkeen muodon mukaisesti) tason, jossa kolmion sisäpisteen arvo saadaan yhtälöstä

$f(x,y)\approx a_{00}+a_{10}x+a_{01}y,$

missä vakiot ovat

$a_{00}=f_{00}$,

$a_{10}=f_{10}-f_{00}$ ja

$a_{01}=f_{01}-f_{00}.$

Bilineaarinen interpolaatio nelikulmiossa

Pisteen P (vihreä) interpolointi, kun tunnetaan arvot suorakulmion kulmissa (punainen). Pisteet R₁ ja R₂ (sininen) ovat ensimmäiset apupisteet, joidan arvo interpoloidaan ensimmäiseksi.

Tässä esitettävä menetelmä perustuu suorakulmioon, koska sen avulla on helppo demostroida suorakulmaisessa koordinaatistossa menetelmän perusperiaatteet. Sillä ratkeaa myös suorakulmioista affiinikuvauksella muodostettavien muiden nelikulmioiden bilineaariset interpolaatiot. Affiinikuvauksia ei käsitellä tässä.

Yksikköneliössä: bilineaarisesti

Interpoloidan bilineaarisesti origosta alkavan yksikköneliön, eli alueen [0, 1]×[0, 1], sisäpisteen (x, y) arvo f(x, y). Merkitään neliön kärjissä sijaitsevat funktion arvot f(0, 0) = f₀₀,f(0, 1) = f₀₁, f(1, 0) = f₁₀ ja f(1, 1) = f₁₁. Vaakasuorilla sivuilla suoritetut lineaarit interpoloinnit tuottavat arvot f(x, 0) = f_x0 ja f(x, 1) = f_x1 seuraavasti

$f_{x0}\approx f_{00}+(f_{10}-f_{00})x,$

$f_{x1}\approx f_{01}+(f_{11}-f_{01})x.$

Kun interpoloidaan pystysuoraan f(x, y) = f_xy, saadaan

$f_{xy}=f(x,y)\approx f_{x0}+(f_{x1}-f_{x0})y.$

Suorakulmiossa: bilineaarisesti

Valitaan suorakulmiosta yksi sivu ja sivulta piste. Lasketaan tämän pisteen arvo lineaarisella interpolaatiolla sivunsa päätepisteiden avulla. Piirretään sivun pisteestä normaali suorakulmion vastakkaiselle sivulle. Normaalin leikkauspiste vastakkaisen sivun kanssa on seuraavan interpolaation kohde. Se suoritetaan vastakkaista sivua pitkin. Kun molempien pisteiden interpoloidut arvot tunnetaan, voidaan pisteiden väliset suorakulmion sisäpisteet interpoloida lineaarisesti.

Interpoloidaan bilineaarisesti pisteessä (x, y) olevaa arvoa suorakulmion kärjissä (viereinen kuva) Q₁₁ = (x₁, y₁), Q₁₂ = (x₁, y₂), Q₂₁ = (x₂, y₁), and Q₂₂ = (x₂, y₂) olevien arvojen f(x₁, y₁) = f₁₁, f(x₁, y₂) = f₁₂, f(x₂, y₁) = f₂₁ ja f(x₂, y₂) = f₂₂ avulla (viereinen kuva).

Aluksi interpoloidaan lineaarisesti x-akselin suuntaan. Kohdassa x, ylä- ja alasivulla, sijaitsevat pisteet R₁ = (x, y₁) ja R₂ = (x, y₂). Näihin pisteisiin interpoloidaan arvot f(x,  y₁) = f_x1 ja f(x,  y₂) = f_x2

$\begin{array}{cc}{f}_{x1}=f(x,y_1)& \approx \frac{x_2-x}{x_2-x_1}{f}_{11}+\frac{x-x_1}{x_2-x_1}{f}_{21}\\ f_{x2}=f(x,y_2)& \approx \frac{x_2-x}{x_2-x_1}{f}_{12}+\frac{x-x_1}{x_2-x_1}{f}_{22}\end{array}$

Viimeisessä vaiheessa interpoloidaan lineaarisesti pisteen P = (x, y) arvo f(x, y)

$\begin{array}{cc}f(x,y)& \approx \frac{y_2-y}{y_2-y_1}f(x,y_1)+\frac{y-y_1}{y_2-y_1}f(x,y_2)\\ & \approx \frac{y_2-y}{y_2-y_1}(\frac{x_2-x}{x_2-x_1}{f}_{11}+\frac{x-x_1}{x_2-x_1}{f}_{21})+\frac{y-y_1}{y_2-y_1}(\frac{x_2-x}{x_2-x_1}{f}_{12}+\frac{x-x_1}{x_2-x_1}{f}_{22})\\ & =\frac{1}{(x_2-x_1)(y_2-y_1)}(f_{11}(x_2-x)(y_2-y)+f_{21}(x-x_1)(y_2-y)+f_{12}(x_2-x)(y-y_1)+f_{22}(x-x_1)(y-y_1))\end{array}$

Yksikköneliössä: pinnansovitus

Nelikulmaisessa bilineaarisessa interpoloinnissa syntyy pinta, jonka laatu selviää sieventämällä edellisiä lausekkeita. Nisstä saadaan

$f_{xy}=f(x,y)\approx f_{00}+(f_{10}-f_{00})x+(f_{01}-f_{00})y+(f_{11}-f_{01}-f_{10}+f_{00})xy.$

Tämä yhtälö voidaan kirjoittaa kompaktiin muotoon sijoittamalla muuttujien eteen vain kertoimet

$f(x,y)\approx a_{00}+a_{10}x+a_{01}y+a_{11}xy,$

missä kertoimet ovat

$a_{00}=f_{00}$ ja

$a_{10}=f_{10}-f_{00}$ ja

$a_{01}=f_{01}-f_{00}$ ja

$a_{11}=f_{11}-f_{01}-f_{10}+f_{00}.$

Muodostunutta pintaa kutsutaan hyperboliseksi paraboloidiksi, mikä se yleisesti onkin. Joskus funktion arvot ovat sellaiset, että pinta onkin taso.

Suorakulmiossa: pinnansovitus

Vaikka pinnansovitus ei ole bilineaarinen interpolaatio, esitetään vaihtoehtoisena ratkaisutapana samassa yhteydessä. Kun valitaan tasolta mitkä tahansa neljä kulmapistettä $(x_1,y_1),(x_2,y_1),(x_1,y_2)\text{ ja }(x_2,y_2),$ voidaan niiden kautta sovittaa kulkemaan tasopinta

$f(x,y)=ax+by+cxy+d.$

Tasopinnan lausekkeen kertoimet voidaan määrittää ratkaisemalla yhtälöryhmä, jossa lausekkeeseen on sijoitettu koordinaatit ja jossa funktion arvoiksi merkitään kulmapisteiden funktion arvot. Yhtälöryhmä on tällöin

$\{\begin{array}{c}f(x_1,y_1)=a{x}_1+b{y}_1+c{x}_1{y}_1+d\\ f(x_2,y_1)=a{x}_2+b{y}_1+c{x}_2{y}_1+d\\ f(x_1,y_2)=a{x}_1+b{y}_2+c{x}_1{y}_2+d\\ f(x_2,y_2)=a{x}_2+b{y}_2+c{x}_2{y}_2+d\end{array}$

Sovellus: Digitaalisen valokuvan käsittely

Digitaalista valokuvaa pienennettäessä voidaan neliön vierekkäiset neljä kuvapikseliä kutistaa yhdeksi pikseliksi bilineaarisella interpolaatiolla. Pikselien numeeriset arvot interpoloidaan yhdeksi numeeriseksi arvoksi, joka sijoitetaan kopiokuvaan vastaavalle paikalle pienennöksessä. Valokuvia suurennettaessa osa pikseleistä kopioidaan alkuperäisestä valokuvasta ja osa pikseleistä luodaan tyhjinä. Tyhjät pikselit täytetään interpoloimalla viereisiä pikseleitä bilineaarisesti. Samalla voidaan interpoloida kopioituja pikseleitä uudelleen sahalaitaisuuden välttämiseksi.

Katso myös

• Trilineaarinen interpolaatio