Bikubisk interpolation

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 26 november 2018; kontroller kräver 16 redigeringar .

Bikubisk interpolation är en utvidgning av kubisk interpolation i beräkningsmatematik till fallet med en funktion av två variabler, vars värden ges på ett tvådimensionellt regelbundet rutnät. Ytan som härrör från bikubisk interpolation är en jämn funktion på gränserna för intilliggande kvadrater, till skillnad från ytor som resulterar från bilinjär interpolation eller närmaste granne-interpolation .

Bikubisk interpolation används ofta i bildbehandling , vilket ger bättre bildkvalitet än bilinjär interpolation. Bikubisk interpolation används också i styralgoritmer för CNC- maskiner för att ta hänsyn till ytoregelbundenheter, till exempel vid fräsning av kretskort.

Metodprincip

I fallet med bikubisk interpolation beräknas värdet på funktionen vid den önskade punkten genom dess värden vid 16 angränsande punkter belägna vid hörnen på planets kvadrater . $x,y$

När du använder formlerna nedan för att programmatiskt implementera bikubisk interpolation, kom ihåg att värdena för och är relativa, inte absoluta. Till exempel för en punkt med koordinater . För att få relativa värden på koordinater är det nödvändigt att avrunda de reella koordinaterna nedåt och subtrahera de erhållna talen från de reella koordinaterna. $x$ $y$ $(100,3 100,8)$ $x=0,3, y=0,8$

f(y,x)=b_{{1}}f(0,0)+b_{{2}}f(0,1)+b_{{3}}f(1,0)+b_{{4 }}f(1,1)+b_{{5}}f(0,-1)+b_{{6}}f(-1,0)+b_{{7}}f(1,-1) +b_{{8}}f(-1,1)+

$+b_{{9}}f(0,2)+b_{{10}}f(2,0)+b_{{11}}f(-1,-1)+b_{{12}}f( 1,2)+b_{{13}}f(2,1)+b_{{14}}f(-1,2)+b_{{15}}f(2,-1)+b_{{16 }}f(2,2)$ ,

var

b_{{1}}={\frac {1}{4}}(x-1)(x-2)(x+1)(y-1)(y-2)(y+1)

b_{{2}}=-{\frac {1}{4}}x(x+1)(x-2)(y-1)(y-2)(y+1)

b_{{3}}=-{\frac {1}{4}}y(x-1)(x-2)(x+1)(y+1)(y-2)

b_{{4}}={\frac {1}{4}}xy(x+1)(x-2)(y+1)(y-2)

b_{{5}}=-{\frac {1}{12}}x(x-1)(x-2)(y-1)(y-2)(y+1)

b_{{6}}=-{\frac {1}{12}}y(x-1)(x-2)(x+1)(y-1)(y-2)

b_{{7}}={\frac {1}{12}}xy(x-1)(x-2)(y+1)(y-2)

b_{{8}}={\frac {1}{12}}xy(x+1)(x-2)(y-1)(y-2)

b_{{9}}={\frac {1}{12}}x(x-1)(x+1)(y-1)(y-2)(y+1)

b_{{10}}={\frac {1}{12}}y(x-1)(x-2)(x+1)(y-1)(y+1)

b_{{11}}={\frac {1}{36}}xy(x-1)(x-2)(y-1)(y-2)

b_{{12}}=-{\frac {1}{12}}xy(x-1)(x+1)(y+1)(y-2)

b_{{13}}=-{\frac {1}{12}}xy(x+1)(x-2)(y-1)(y+1)

b_{{14}}=-{\frac {1}{36}}xy(x-1)(x+1)(y-1)(y-2)

b_{{15}}=-{\frac {1}{36}}xy(x-1)(x-2)(y-1)(y+1)

b_{{16}}={\frac {1}{36}}xy(x-1)(x+1)(y-1)(y+1)

På ett liknande sätt kan högre ordningens interpolationer användas för att beräkna funktionens värden från närliggande punkter. $4k^{2}$

Bikubisk spline-interpolation

Låt oss anta att det är nödvändigt att interpolera värdet på funktionen i en punkt som ligger innanför kvadraten , och värdet på funktionen är känt vid sexton intilliggande punkter . $f(x,y)$ $P(x,y)$ $[0,1]\ gånger [0,1]$ $f$ $(i,j),i=-1\ldots 2,j=-1\ldots 2$

Då kan den allmänna formen av funktionen som definierar den interpolerade ytan skrivas på följande sätt:

${\displaystyle p(x,y)=\sum _{i=0}^{3}\sum _{j=0}^{3}a_{ij}x^{i}y^{j))$ .

För att hitta koefficienterna är det nödvändigt att ersätta funktionens värden vid kända sexton punkter i ovanstående ekvation. Till exempel: $a_{{ij}}$

${\begin{aligned}f(-1,0)&=a_{{00}}&-&a_{{10}}&+&a_{{20}}&-&a_{{30}}\\f(0 ,0)&=a_{{00}}\\f(1,0)&=a_{{00}}&+&a_{{10}}&+&a_{{20}}&+&a_{{30} }\\f(2,0)&=a_{{00}}&+&2a_{{10}}&+&4a_{{20}}&+&8a_{{30}}\\\end{aligned}}$ .

Helt i matrisform:

$M\alpha ^{T}=\gamma ^{T}$ ,

var

$\alpha =\left[{\begin{smallmatrix}a_{{00}}&a_{{01}}&a_{{02}}&a_{{03}}&a_{{10}}&a_{{11}}&a_{ {12}}&a_{{13}}&a_{{20}}&a_{{21}}&a_{{22}}&a_{{23}}&a_{{30}}&a_{{31}}&a_{{32 }}&a_{{33}}\end{smallmatrix}}\right]$ ,

$\gamma =\left[{\begin{smallmatrix}f(-1,-1)&f(0,-1)&f(1,-1)&f(2,-1)&f(-1,0)&f( 0,0)&f(1,0)&f(2,0)&f(-1,1)&f(0,1)&f(1,1)&f(2,1)&f(-1,2)&f( 0,2)&f(1,2)&f(2,2) \end{smallmatrix}}\right]$ ,

$M=\left[{\begin{smallmatrix}1&-1&1&-1&-1&1&-1&1&1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1&1-1&&1&1&1&1&1&1&1&1&1&1&1&1&1&1& -1&1&-1\\1&-1&1&-1&2&-2&2&-2&4&-4&4&-4&8&-8&8&-8\\1&0&0&0&-1&0&0&0&1&0&0&0&-1&0&0&0\\1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0\\1&0&0&0&2&0&0&0&4&0&0&0&8&0&0&0\\1&1&1&1&-1&-1&-1&-1&1&1&1&1& -1&-1&-1&-1\\1&1&1&1&0&0&0&0&0&0&0&0&0&0&0&0\\1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\\1&1&1&1&2&2&2&2&4&4&4&4&8&8&8&8\\1&2&4&8&-1&-2&-4&-8&1&2&4&8&-1&-2&-4&-8\\1&2&4&8&0&0&0&0&0&0&0&0&0&0&0&0\\1&2&4&8&1&2&4&8&1&2&4&8&1&2&4&8\\1&2&4&8&2&4&8&16&4&8&16&32&8&16&32&64\end{smallmatrix} }\höger]$ .

Genom att lösa det resulterande systemet med linjära algebraiska ekvationer kan du hitta värdena explicit: $a_{{ij}}$

$\alpha ^{T}={\frac {1}{36}}\left[{\begin{smallmatrix}0&0&0&0&0&36&0&0&0&0&0&0&0&0&0&0\\0&-12&0&0&0&-18&0&0&0&36&0&0&0&-6&0&0\\0&18&0&0&0&-36&0&0&0&18&0&0&0&0&0&0\\0&-6&0&0&0&18&0&0&0&-18&0&0&0&6&0&0\\ 0&0&0&0&-12&-18&36&-6&0&0&0&0&0&0&0&0\\4&6&-12&2&6&9&-18&3&-12&-18&36&-6&2&3&-6&1\\-6&-9&18&-3&12&18&-36&6&-6&-9&18&-3&0&0&0&0\\2&3&-6&1&-6&-9&18&-3&6&9&- 18&3&-2&-3&6&-1\\0&0&0&0&18&-36&18&0&0&0&0&0&0&0&0&0\\-6&12&-6&0&-9&18&-9&0&18&-36&18&0&-3&6&-3&0\\9&-18&9&0&-18&36&-18&0&9&-18&9&0&0&0&0&0\\-3&6&-3&0&9&-18&9&0&-9&18&- 9&0&3&-6&3&0\\\0&0&0&0&-6&18&-18&6&0&0&0&0&0&0&0&0\\\2&-6&6&-2&3&-9&9&-3&-6&18&-18&6&1&-3&3&-1\9---&3&9&9&9-1&3&9&3&9&9-1 3&-1&3&-3&1\\\end{smallmatrix}}\right]\gamma ^{T}$ .

En gång hittade koefficienter kan nu användas för att upprepade gånger beräkna det interpolerade värdet av funktionen vid godtyckliga punkter i kvadraten . $a_{{ij}}$ $[0,1]\ gånger [0,1]$

Det bör noteras att denna metod säkerställer kontinuiteten för själva funktionen och dess andra derivata på gränserna för intilliggande kvadrater, men leder till ett brott i de första derivatorna vid gränserna för 4×4 celler. För att säkerställa kontinuiteten för själva funktionen och dess första derivata, är det nödvändigt att ersätta funktionens värden och värdena för de första derivatorna i x- och y-riktningarna vid hörnen av den centrala cellen med originalet uttryck beräknas derivaten genom centrala skillnader. För att ersätta derivat måste uttrycket differentieras i enlighet därmed.

Sekventiell kubisk interpolation

En annan tolkning av metoden är att för att hitta det interpolerade värdet kan man först utföra kubisk interpolation i en riktning och sedan i den andra.

För en funktion med kända värden , , , kan du konstruera en kubisk spline: , eller i matrisform: $f(x)$ $f(-1)$ $f(0)$ $f(1)$ $f(2)$ $p(x)=\textstil \sum _{{i=0}}^{3}b_{i}x^{i}$

$p(x)=\left[{\begin{smallmatrix}1&x&x^{2}&x^{3}\end{smallmatrix}}\right]\left[{\begin{smallmatrix}b_{0}\\b_{ 1}\\b_{2}\\b_{3}\end{smallmatrix}}\right]$ ,

var

$\left[{\begin{smallmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{smallmatrix}}\right]=A\left[{\begin{smallmatrix }f(-1)\\f(0)\\f(1)\\f(2)\end{smallmatrix}}\right]$ ,

$A={\frac {1}{3}}\left[{\begin{smallmatrix}0&6&0&0\\-2&-3&6&-1\\3&-6&3&0\\-1&3&-3&1\end{smallmatrix}} \höger]$ .

För att hitta det interpolerade värdet i kvadraten kan du alltså först beräkna fyra värden , , , för fix , sedan bygga en kubisk spline genom de fyra erhållna punkterna och på så sätt slutföra beräkningen : $p(x,y)$ $[0,1]\ gånger [0,1]$ $p(x,-1)$ $p(x,0)$ $p(x,1)$ $p(x,2)$ $x$ $p(x,y)$

$p(x,y)=\left[{\begin{smallmatrix}1&y&y^{2}&y^{3}\end{smallmatrix}}\right]A\left(\left[{\begin{smallmatrix} }1&x&x^{2}&x^{3}\end{smallmatrix}}\right]A\left[{\begin{smallmatrix}&f(-1,-1)&f(0,-1)&f(1,- 1)&f(2,-1)\\&f(-1,0)&f(0,0)&f(1,0)&f(2,0)\\&f(-1,1)&f(0,1 )&f(1,1)&f(2,1)\\&f(-1,2)&f(0,2)&f(1,2)&f(2,2)\\\end{smallmatrix}}\right ]\right)^{T}=$

$=\left[{\begin{smallmatrix}1&y&y^{2}&y^{3}\end{smallmatrix}}\right]A\left[{\begin{smallmatrix}f(-1,-1)&f(- 1,0)&f(-1,1)&f(-1,2)\\f(0,-1)&f(0,0)&f(0,1)&f(0,2)\\f(1 ,-1)&f(1,0)&f(1,1)&f(1,2)\\f(2,-1)&f(2,0)&f(2,1)&f(2,2)\ end{smallmatrix}}\right]A^{T}\left[{\begin{smallmatrix}1\\x\\x^{2}\\x^{3}\end{smallmatrix}}\right]$ .

Det bör noteras att detta tillvägagångssätt säkerställer kontinuiteten för själva funktionen och dess andraderivator vid cellgränsen, men säkerställer inte kontinuiteten för den första derivatan. För att säkerställa kontinuiteten för den första derivatan är det nödvändigt att ersätta funktionens värden och dess första derivator vid gränsen för den centrala cellen. Då kommer splinekoefficienterna att se ut så här:

$\left[{\begin{smallmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{smallmatrix}}\right]=B^{{-1}}\ vänster[{\begin{smallmatrix}f(0)\\f(1)\\{\frac {f(1)-f(-1)}{2}}\\{\frac {f(2)- f(0)}{2}}\end{smallmatrix}}\right]$ ,

$B=\left[{\begin{smallmatrix}1&0&0&0\\1&1&1&1\\0&1&0&0\\0&1&2&3\end{smallmatrix}}\right],B^{{-1}}=\left[{\begin{smallmatrix}1&0&0&0 \\0&0&1&0\\-3&3&-2&-1\\2&-2&1&1\end{smallmatrix}}\right]$ .

Se även

Litteratur

R. Nycklar. Kubisk faltningsinterpolation för digital bildbehandling // IEEE-transaktioner på akustik, tal och signalbehandling : journal. - 1981. - Vol. 29 , nr. 6 . - P. 1153-1160 . - doi : 10.1109/TASSP.1981.1163711 .