Bikubická interpolace

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 26. listopadu 2018; kontroly vyžadují 16 úprav .

Bikubická interpolace je rozšířením kubické interpolace ve výpočetní matematice na případ funkce dvou proměnných, jejichž hodnoty jsou uvedeny na dvourozměrné pravidelné mřížce. Plocha vyplývající z bikubické interpolace je hladká funkce na hranicích sousedních čtverců, na rozdíl od ploch vyplývajících z bilineární interpolace nebo interpolace nejbližšího souseda .

Při zpracování obrazu se často používá bikubická interpolace , která poskytuje lepší kvalitu obrazu než bilineární interpolace. Bikubická interpolace se také používá v řídicích algoritmech pro CNC stroje , aby se zohlednily nepravidelnosti povrchu, například při frézování desek plošných spojů.

Princip metody

V případě bikubické interpolace se hodnota funkce v požadovaném bodě vypočítá prostřednictvím jejích hodnot v 16 sousedních bodech umístěných ve vrcholech čtverců roviny . $x, y$

Při použití níže uvedených vzorců k programové implementaci bikubické interpolace nezapomeňte, že hodnoty a jsou relativní, nikoli absolutní. Například pro bod se souřadnicemi . Pro získání relativních hodnot souřadnic je nutné zaokrouhlit skutečné souřadnice dolů a získaná čísla odečíst od skutečných souřadnic. $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)$ ,

kde

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)

Podobným způsobem lze použít interpolace vyššího řádu, které počítají hodnoty funkce ze sousedních bodů. $4k^{2}$

Bikubická spline interpolace

Předpokládejme, že je nutné interpolovat hodnotu funkce v bodě ležícím uvnitř čtverce a hodnotu funkce známe v šestnácti sousedních bodech . $f(x,y)$ $P(x,y)$ $[0,1]\krát [0,1]$ $F$ $(i,j),i=-1\ldots 2,j=-1\ldots 2$

Potom lze obecný tvar funkce, která definuje interpolovanou plochu, zapsat následovně:

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

Pro nalezení koeficientů je nutné dosadit hodnoty funkce ve známých šestnácti bodech do výše uvedené rovnice. Například: $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_{{0}}&+&2a_{{10}}&+&4a_{{20}}&+&8a_{{30}}\\\end{aligned}}$ .

Kompletně v maticové podobě:

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

kde

$\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&1&1\\1&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&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} }\že jo]$ .

Při řešení výsledného systému lineárních algebraických rovnic můžete explicitně najít hodnoty: $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 & 0-12 & -12 & 2 & 6 & 9 & -18 &-6 &-6 & &-& 18 & 6 & 6 & 6 &-6 & &-6 & &-6 & &-6 & &-6 & &-6 & &-6 & &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 &-6 & 3 & 3 & 3 & 3 & 3 & 6 &-6 & 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&-9&9&-3&1&-1&9&-3-3&0&9&9&-3 3&-1&3&-3&1\\\konec{malá matice}}\vpravo]\gama ^{T}$ .

Jednou nalezené koeficienty lze nyní použít k opakovanému výpočtu interpolované hodnoty funkce v libovolných bodech čtverce . $a_{{ij}}$ $[0,1]\krát [0,1]$

Nutno podotknout, že tato metoda zajišťuje návaznost samotné funkce a její druhé derivace na hranicích sousedních čtverců, ale vede k přerušení prvních derivací na hranicích 4×4 buněk. Pro zajištění kontinuity samotné funkce a její první derivace je nutné dosadit hodnoty funkce a hodnoty prvních derivací ve směru x a y ve vrcholech centrální buňky do původní derivace jsou vypočteny prostřednictvím centrálních rozdílů. Chcete-li dosadit deriváty, musí být výraz odpovídajícím způsobem diferencován.

Sekvenční kubická interpolace

Další výklad metody spočívá v tom, že pro nalezení interpolované hodnoty je možné nejprve provést kubickou interpolaci v jednom a poté ve druhém směru.

Pro funkci se známými hodnotami , , , můžete sestavit kubický spline: , nebo ve formě matice: $f(x)$ $f(-1)$ $f(0)$ $f(1)$ $f(2)$ $p(x)=\textstyle \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]$ ,

kde

$\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}} \že jo]$ .

Chcete-li tedy najít interpolovanou hodnotu ve čtverci , můžete nejprve vypočítat čtyři hodnoty , , , pro pevné , poté sestavit kubický spline ze čtyř získaných bodů, a tím dokončit výpočet : $p(x,y)$ $[0,1]\krát [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{smallmatic}&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)\\\konec{malá matice}}\vpravo ]\vpravo)^{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)\ konec{smallmatrix}}\right]A^{T}\left[{\begin{smallmatrix}1\\x\\x^{2}\\x^{3}\end{smallmatrix}}\right]$ .

Je třeba poznamenat, že tento přístup zajišťuje kontinuitu funkce samotné a jejích druhých derivací na hranici buňky, ale nezajišťuje návaznost první derivace. Aby byla zajištěna kontinuita první derivace, je nutné dosadit hodnoty funkce a jejích prvních derivací na hranici centrální buňky. Spline koeficienty pak budou vypadat takto:

$\left[{\begin{smallmatrix}b_{0}\\b_{1}\\b_{2}\\b_{3}\end{smallmatrix}}\right]=B^{{-1}}\ left[{\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]$ .

Viz také

Literatura

R. Klíče. Interpolace kubické konvoluce pro digitální zpracování obrazu // Transakce IEEE v oblasti akustiky, řeči a zpracování signálu : deník. - 1981. - Sv. 29 , č. 6 . - S. 1153-1160 . - doi : 10.1109/TASSP.1981.1163711 .