Bikubisk interpolation

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 26. november 2018; checks kræver 16 redigeringer .

Bikubisk interpolation er en udvidelse af kubisk interpolation i beregningsmatematik til tilfældet med en funktion af to variable, hvis værdier er givet på et todimensionelt regulært gitter. Overfladen som følge af bikubisk interpolation er en glat funktion på grænserne af tilstødende kvadrater, i modsætning til overflader som følge af bilineær interpolation eller nærmeste nabointerpolation .

Bikubisk interpolation bruges ofte i billedbehandling , hvilket giver bedre billedkvalitet end bilineær interpolation. Bikubisk interpolation bruges også i styrealgoritmer til CNC- maskiner for at tage højde for overfladeuregelmæssigheder, for eksempel ved fræsning af printplader.

Metodeprincip

I tilfælde af bikubisk interpolation beregnes værdien af funktionen på det ønskede punkt gennem dens værdier ved 16 tilstødende punkter placeret ved hjørnerne af kvadraterne i planet . $x,y$

Når du bruger formlerne nedenfor til programmatisk at implementere bikubisk interpolation, skal du huske, at værdierne af og er relative, ikke absolutte. For eksempel for et punkt med koordinater . For at opnå relative værdier af koordinater er det nødvendigt at runde de reelle koordinater ned og trække de opnåede tal fra de reelle koordinater. $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)$ ,

hvor

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å lignende måde kan højere ordens interpolationer bruges til at beregne værdierne af funktionen fra nabopunkter . $4k^{2}$

Bikubisk spline interpolation

Lad os antage, at det er nødvendigt at interpolere værdien af funktionen i et punkt, der ligger inde i kvadratet , og værdien af funktionen er kendt i seksten tilstødende punkter . $f(x,y)$ $P(x,y)$ $[0,1]\ gange [0,1]$ $f$ $(i,j),i=-1\ldots 2,j=-1\ldots 2$

Så kan den generelle form af funktionen, der definerer den interpolerede overflade, skrives som følger:

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

For at finde koefficienterne er det nødvendigt at erstatte funktionens værdier ved kendte seksten punkter i ovenstående ligning. For eksempel: $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 matrixform:

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

hvor

$\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 =\venstre[{\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=\venstre[{\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&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&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} }\ret]$ .

Ved at løse det resulterende system af lineære algebraiske ligninger kan du finde værdierne eksplicit: $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&3&3&9&9-1 3&-1&3&-3&1\\\end{smallmatrix}}\right]\gamma ^{T}$ .

Når først fundet koefficienter kan nu bruges til gentagne gange at beregne den interpolerede værdi af funktionen ved vilkårlige punkter i kvadratet . $a_{{ij}}$ $[0,1]\ gange [0,1]$

Det skal bemærkes, at denne metode sikrer kontinuiteten af selve funktionen og dens anden afledte på grænserne af tilstødende kvadrater, men fører til et brud i de første afledede ved grænserne af 4×4 celler. For at sikre kontinuiteten af selve funktionen og dens første afledede, er det nødvendigt at erstatte værdierne af funktionen og værdierne af de første afledede i x- og y-retningerne ved hjørnerne af den centrale celle i originalen udtryk beregnes de afledte gennem centrale forskelle. For at substituere derivater skal udtrykket differentieres i overensstemmelse hermed.

Sekventiel kubisk interpolation

En anden fortolkning af metoden er, at man for at finde den interpolerede værdi først kan udføre kubisk interpolation i den ene retning og derefter i den anden.

For en funktion med kendte værdier , , , kan du konstruere en kubisk spline: , eller i matrixform: $f(x)$ $f(-1)$ $f(0)$ $f(1)$ $f(2)$ $p(x)=\textstyle \sum _{{i=0}}^{3}b_{i}x^{i}$

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

hvor

$\venstre[{\begin{smallmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{smallmatrix}}\right]=A\venstre[{\begin{smallmatrix }f(-1)\\f(0)\\f(1)\\f(2)\end{lillematrix}}\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}} \ret]$ .

For at finde den interpolerede værdi i firkanten kan du derfor først beregne fire værdier , , , for fixed , derefter bygge en kubisk spline gennem de fire opnåede punkter og dermed fuldføre beregningen : $p(x,y)$ $[0,1]\ gange [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\venstre[{\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}=$

$=\venstre[{\begin{smallmatrix}1&y&y^{2}&y^{3}\end{smallmatrix}}\right]A\venstre[{\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)\ ende{smallmatrix}}\right]A^{T}\venstre[{\begin{smallmatrix}1\\x\\x^{2}\\x^{3}\end{smallmatrix}}\right]$ .

Det skal bemærkes, at denne tilgang sikrer kontinuiteten af selve funktionen og dens anden afledte ved cellegrænsen, men sikrer ikke kontinuiteten af den første afledte. For at sikre kontinuiteten af den første afledte er det nødvendigt at erstatte værdierne af funktionen og dens første afledte ved grænsen af den centrale celle. Så ser spline-koefficienterne ud som:

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

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

Se også

Litteratur

R. Nøgler. Kubisk foldningsinterpolation til digital billedbehandling // IEEE-transaktioner på akustik, tale og signalbehandling : journal. - 1981. - Bd. 29 , nr. 6 . - S. 1153-1160 . - doi : 10.1109/TASSP.1981.1163711 .