Bikubická interpolace - Bicubic interpolation

Srovnání Bikubická interpolace s některými 1- a 2-dimenzionálními interpolacemi. Černé a červené / žluté / zelené / modré tečky odpovídají interpolovanému bodu a sousedním vzorkům. Jejich výšky nad zemí odpovídají jejich hodnotám.

v matematika, bikubická interpolace je příponou kubická interpolace pro interpolovat datové body na a dvourozměrný pravidelná mřížka. Interpolovaný povrch je hladší než odpovídající povrchy získané pomocí bilineární interpolace nebo interpolace nejbližšího souseda. Bikubickou interpolaci lze dosáhnout použitím kteréhokoli z nich Lagrangeovy polynomy, kubické splajny nebo kubická konvoluce algoritmus.

v zpracování obrazu, bikubická interpolace je často volena před bilineární nebo nejbližší sousední interpolací v převzorkování obrazu, když rychlost není problém. Na rozdíl od bilineární interpolace, která trvá pouze 4 pixelů (2 × 2), bikubická interpolace bere v úvahu 16 pixelů (4 × 4). Obrázky převzorkované bikubickou interpolací jsou plynulejší a mají méně interpolace artefakty.

Výpočet

Bikubická interpolace na čtverci

{ displaystyle [0,4] krát [0,4]}

skládající se z 25 jednotkových čtverců dohromady. Bikubická interpolace podle Matplotlib implementace. Barva označuje hodnotu funkce. Černé tečky jsou umístění předepsaných dat, která jsou interpolována. Všimněte si, že vzorky barev nejsou radiálně symetrické.

Bilineární interpolace na stejné datové sadě jako výše. Deriváty povrchu nejsou spojité nad hranatými hranicemi.

Interpolace nejbližších sousedů na stejné datové sadě jako výše.

Předpokládejme funkční hodnoty ${ displaystyle f}$ a deriváty ${ displaystyle f_ {x}}$ , ${ displaystyle f_ {y}}$ a ${ displaystyle f_ {xy}}$ jsou známy ve čtyřech rozích ${ displaystyle (0,0)}$ , ${ displaystyle (1,0)}$ , ${ displaystyle (0,1)}$ , a ${ displaystyle (1,1)}$ jednotkového čtverce. Interpolovaný povrch lze poté zapsat jako

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

Problém s interpolací spočívá v určení 16 koeficientů ${ displaystyle a_ {ij}}$ .Vhodný ${ displaystyle p (x, y)}$ s funkčními hodnotami se získá čtyři rovnice:

${ displaystyle f (0,0) = p (0,0) = a_ {00},}$
${ displaystyle f (1,0) = p (1,0) = a_ {00} + a_ {10} + a_ {20} + a_ {30},}$
${ displaystyle f (0,1) = p (0,1) = a_ {00} + a_ {01} + a_ {02} + a_ {03},}$
${ displaystyle f (1,1) = p (1,1) = textový styl suma limity _ {i = 0} ^ {3} suma limity _ {j = 0} ^ {3} a_ {ij }.}$

Podobně osm rovnic pro deriváty v ${ displaystyle x}$ a ${ displaystyle y}$ Pokyny:

${ displaystyle f_ {x} (0,0) = p_ {x} (0,0) = a_ {10},}$
${ displaystyle f_ {x} (1,0) = p_ {x} (1,0) = a_ {10} + 2a_ {20} + 3a_ {30},}$
${ displaystyle f_ {x} (0,1) = p_ {x} (0,1) = a_ {10} + a_ {11} + a_ {12} + a_ {13},}$
${ displaystyle f_ {x} (1,1) = p_ {x} (1,1) = textový styl suma limity _ {i = 1} ^ {3} suma limity _ {j = 0} ^ {3} a_ {ij} i,}$
${ displaystyle f_ {y} (0,0) = p_ {y} (0,0) = a_ {01},}$
${ displaystyle f_ {y} (1,0) = p_ {y} (1,0) = a_ {01} + a_ {11} + a_ {21} + a_ {31},}$
${ displaystyle f_ {y} (0,1) = p_ {y} (0,1) = a_ {01} + 2a_ {02} + 3a_ {03},}$
${ displaystyle f_ {y} (1,1) = p_ {y} (1,1) = textový styl součet limity _ {i = 0} ^ {3} součet limity _ {j = 1} ^ {3} a_ {ij} j.}$

A čtyři rovnice pro ${ displaystyle xy}$ smíšená parciální derivace:

${ displaystyle f_ {xy} (0,0) = p_ {xy} (0,0) = a_ {11},}$
${ displaystyle f_ {xy} (1,0) = p_ {xy} (1,0) = a_ {11} + 2a_ {21} + 3a_ {31},}$
${ displaystyle f_ {xy} (0,1) = p_ {xy} (0,1) = a_ {11} + 2a_ {12} + 3a_ {13},}$
${ displaystyle f_ {xy} (1,1) = p_ {xy} (1,1) = textový styl součet limity _ {i = 1} ^ {3} součet limity _ {j = 1} ^ {3} a_ {ij} ij.}$

Výše uvedené výrazy používají následující identity:

{ displaystyle p_ {x} (x, y) = textový styl suma limity _ {i = 1} ^ {3} suma limity _ {j = 0} ^ {3} a_ {ij} ix ^ { i-1} y ^ {j},}

{ Displaystyle p_ {y} (x, y) = textový styl suma limity _ {i = 0} ^ {3} suma limity _ {j = 1} ^ {3} a_ {ij} x ^ { i} jy ^ {j-1},}

{ displaystyle p_ {xy} (x, y) = textový styl suma limity _ {i = 1} ^ {3} suma limity _ {j = 1} ^ {3} a_ {ij} ix ^ { i-1} jy ^ {j-1}.}

Tento postup poskytuje povrch ${ displaystyle p (x, y)}$ na jednotkový čtverec ${ displaystyle [0,1] krát [0,1]}$ který je spojitý a má spojité deriváty. Bikubická interpolace na libovolně velké pravidelná mřížka pak lze dosáhnout spojením těchto bikubických povrchů dohromady a zajistit, aby se deriváty shodovaly na hranicích.

Seskupení neznámých parametrů ${ displaystyle a_ {ij}}$ ve vektoru

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

a nechat

{ displaystyle x = left [{ begin {smallmatrix} f (0,0) & f (1,0) & f (0,1) & f (1,1) & f_ {x} (0,0) & f_ {x } (1,0) & f_ {x} (0,1) & f_ {x} (1,1) & f_ {y} (0,0) & f_ {y} (1,0) & f_ {y} (0,1 ) & f_ {y} (1,1) & f_ {xy} (0,0) & f_ {xy} (1,0) & f_ {xy} (0,1) & f_ {xy} (1,1) end {smallmatrix) }} doprava] ^ {T},}

výše uvedený systém rovnic lze přeformulovat do matice pro lineární rovnici ${ displaystyle A alpha = x}$ .

Obrácením matice získáte užitečnější lineární rovnici ${ displaystyle A ^ {- 1} x = alpha}$ , kde

{ Displaystyle a ^ {- 1} = left [{ begin {smallmatrix} 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 - 3 3 0 0 -2 a -1 0 0 0 0 0 0 0 0 0 0 2 a -2 a 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 -3 3 0 0 -2 - 1 0 0 0 0 0 0 0 0 0 0 2 a -2 a 0 0 1 1 0 0 - 3 0 3 0 0 0 0 0 -2 a 0 -1 0 0 0 0 0 0 0 0 0 -3 0 3 0 0 0 0 0 -2 a 0 -1 0 9 -9 a -9 a 9 6 3 -6 -3 6 -6 3 -3 4 2 2 1 - 6 6 6 -6 -3 -3 3 3 -4 4 -2 & 2 & -2 & -2 & -1 & -1 2 & 0 & -2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 0 & 0 & 0 & 0 & 2 & 0 & -2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 - 6 & 6 & 6 & -6 & -4 & -2 & 4 & -3 & 4 & -2 & 4 & -3 & 2 & -2 & 2 & -2 & 2 & -2 & 1 & 1 & 1 & 1 end {smallmatrix}} right],}

což dovoluje ${ displaystyle alpha}$ vypočítat rychle a snadno.

Může existovat další stručná maticová forma pro 16 koeficientů:

{ displaystyle { begin {bmatrix} f (0,0) & f (0,1) & f_ {y} (0,0) & f_ {y} (0,1) f (1,0) & f (1 , 1) & f_ {y} (1,0) & f_ {y} (1,1) f_ {x} (0,0) & f_ {x} (0,1) & f_ {xy} (0,0) & f_ {xy} (0,1) f_ {x} (1,0) & f_ {x} (1,1) & f_ {xy} (1,0) & f_ {xy} (1,1) end { bmatrix}} = { begin {bmatrix} 1 & 0 & 0 & 0 1 & 1 & 1 & 1 0 & 1 & 0 & 0 0 & 1 & 2 & 3 end {bmatrix}} { begin {bmatrix} 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 {bmatrix}} { begin {bmatrix} 1 & 1 & 0 & 0 0 & 1 & 1 & 1 0 & 1 & 0 & 2 0 & 1 & 0 & 3 end {bmatrix}},}

nebo

{ displaystyle { begin {bmatrix} 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 {bmatrix}} = { begin {bmatrix} 1 & 0 & 0 & 0 0 & 0 & 1 & 0 - 3 & 3 & -2 & -1 2 & -2 & 1 & 1 end {bmatrix}} { begin {bmatrix} f (0,0) & f (0,1) & f_ {y} (0,0) & f_ {y} (0,1 ) f (1,0) & f (1,1) & f_ {y} (1,0) & f_ {y} (1,1) f_ {x} (0,0) & f_ {x} (0) , 1) & f_ {xy} (0,0) & f_ {xy} (0,1) f_ {x} (1,0) & f_ {x} (1,1) & f_ {xy} (1,0) & f_ {xy} (1,1) end {bmatrix}} { begin {bmatrix} 1 & 0 & -3 & 2 0 & 0 & 3 & -2 0 & 1 & -2 & 1 0 & 0 & -1 & 1 end {bmatrix}},}

kde

{ displaystyle p (x, y) = { begin {bmatrix} 1 & x & x ^ {2} & x ^ {3} end {bmatrix}} { begin {bmatrix} 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 {bmatrix}} { begin {bmatrix} 1 y y ^ {2} y ^ {3} end {bmatrix}}.}

Rozšíření na přímočaré mřížky

Aplikace často vyžadují bikubickou interpolaci pomocí dat na přímočaré mřížce, spíše než na jednotkový čtverec. V tomto případě identity pro ${ displaystyle p_ {x}, p_ {y},}$ a ${ displaystyle p_ {xy}}$ stát se

{ Displaystyle p_ {x} (x, y) = textový styl suma limity _ {i = 1} ^ {3} suma limity _ {j = 0} ^ {3} { frac {a_ {ij } ix ^ {i-1} y ^ {j}} { Delta x}},}

{ displaystyle p_ {y} (x, y) = textový styl suma limity _ {i = 0} ^ {3} suma limity _ {j = 1} ^ {3} { frac {a_ {ij } x ^ {i} jy ^ {j-1}} { Delta y}},}

{ displaystyle p_ {xy} (x, y) = textový styl sum limity _ {i = 1} ^ {3} sum limity _ {j = 1} ^ {3} { frac {a_ {ij } ix ^ {i-1} jy ^ {j-1}} { Delta x Delta y}},}

kde ${ displaystyle Delta x}$ je ${ displaystyle x}$ rozteč buňky obsahující bod ${ displaystyle (x, y)}$ a podobné pro ${ displaystyle Delta y}$ V tomto případě je nejpraktičtější přístup k výpočtu koeficientů ${ displaystyle alpha}$ je nechat

{ displaystyle x = left [{ begin {smallmatrix} f (0,0) & f (1,0) & f (0,1) & f (1,1) & Delta xf_ {x} (0,0) & Delta xf_ {x} (1,0) & Delta xf_ {x} (0,1) & Delta xf_ {x} (1,1) & Delta yf_ {y} (0,0) & Delta yf_ {y} (1,0) & Delta yf_ {y} (0,1) & Delta yf_ {y} (1,1) & Delta x Delta yf_ {xy} (0,0) & Delta x Delta yf_ {xy} (1,0) & Delta x Delta yf_ {xy} (0,1) & Delta x Delta yf_ {xy} (1,1) end {smallmatrix}} right] ^ {T},}

pak vyřešit ${ displaystyle alpha = A ^ {- 1} x}$ s ${ displaystyle A}$ jako dříve. Dále se normalizované interpolační proměnné počítají jako

{ displaystyle { overline {x}} = { frac {x-x_ {0}} {x_ {1} -x_ {0}}}}

,

{ displaystyle { overline {y}} = { frac {y-y_ {0}} {y_ {1} -y_ {0}}}}

kde ${ displaystyle x_ {0}, x_ {1}, y_ {0},}$ a ${ displaystyle y_ {1}}$ jsou ${ displaystyle x}$ a ${ displaystyle y}$ souřadnice bodů mřížky obklopujících bod ${ displaystyle (x, y)}$ . Poté se stane interpolační povrch

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

Hledání derivátů z funkčních hodnot

Pokud jsou derivace neznámé, jsou obvykle aproximovány z funkčních hodnot v bodech sousedících s rohy jednotkového čtverce, např. použitím konečné rozdíly.

Chcete-li najít jeden z jednotlivých derivátů, ${ displaystyle f_ {x}}$ nebo ${ displaystyle f_ {y}}$ pomocí této metody najděte sklon mezi nimi okolní body v příslušné ose. Například pro výpočet ${ displaystyle f_ {x}}$ pro jeden z bodů najděte ${ displaystyle f (x, y)}$ pro body nalevo a napravo od cílového bodu a vypočítat jejich sklon a podobně pro ${ displaystyle f_ {y}}$ .

Najít křížovou derivaci ${ displaystyle f_ {xy}}$ , vezměte derivaci v obou osách, jednu po druhé. Například lze nejprve použít ${ displaystyle f_ {x}}$ postup k nalezení ${ displaystyle x}$ deriváty bodů nad a pod cílovým bodem, pak použijte ${ displaystyle f_ {y}}$ postup u těchto hodnot (spíše než jako obvykle hodnoty ${ displaystyle f}$ pro tyto body) k získání hodnoty ${ displaystyle f_ {xy} (x, y)}$ pro cílový bod. (Nebo to můžete udělat opačným směrem, nejprve to spočítejte ${ displaystyle f_ {y}}$ a pak ${ displaystyle f_ {x}}$ z těch. Ti dva dávají rovnocenné výsledky.)

Pokud na okrajích datové sady chybí některé z okolních bodů, lze chybějící body aproximovat řadou metod. Jednoduchou a běžnou metodou je předpokládat, že sklon z existujícího bodu do cílového bodu pokračuje bez další změny, a pomocí toho vypočítat hypotetickou hodnotu pro chybějící bod.

Algoritmus bikubické konvoluce

Bikubická spline interpolace vyžaduje řešení lineárního systému popsaného výše pro každou buňku mřížky. Interpolátor s podobnými vlastnostmi lze získat použitím a konvoluce s následujícím jádrem v obou rozměrech:

{ displaystyle W (x) = { begin {cases} (a + 2) | x | ^ {3} - (a + 3) | x | ^ {2} +1 & { text {for}} | x | leq 1, a | x | ^ {3} -5a | x | ^ {2} + 8a | x | -4a & { text {for}} 1 <| x | <2, 0 & { text {jinak}}, end {případy}}}

kde ${ displaystyle a}$ je obvykle nastavena na −0,5 nebo −0,75. Všimněte si, že ${ displaystyle W (0) = 1}$ a ${ displaystyle W (n) = 0}$ pro všechna nenulová celá čísla ${ displaystyle n}$ .

Tento přístup navrhl Keys, který to ukázal ${ displaystyle a = -0,5}$ produkuje konvergenci třetího řádu s ohledem na vzorkovací interval původní funkce.^[1]

Použijeme-li maticovou notaci pro běžný případ ${ displaystyle a = -0,5}$ , můžeme rovnici vyjádřit přátelštěji:

{ displaystyle p (t) = { tfrac {1} {2}} { begin {bmatrix} 1 & t & t ^ {2} & t ^ {3} end {bmatrix}} { begin {bmatrix} 0 & 2 & 0 & 0 -1 & 0 & 1 & 0 2 & -5 & 4 & -1 - 1 & 3 & -3 & 1 end {bmatrix}} { begin {bmatrix} f _ {- 1} f_ {0} f_ {1} f_ {2} end {bmatrix}}}

pro ${ displaystyle t}$ mezi 0 a 1 pro jednu dimenzi. Všimněte si, že pro 1-dimenzionální kubickou konvoluční interpolaci jsou vyžadovány 4 vzorky. U každého dotazu jsou dva vzorky umístěny vlevo a dva vzorky vpravo. Tyto body jsou v tomto textu indexovány od −1 do 2. Vzdálenost od bodu indexovaného 0 k bodu dotazu je označena ${ displaystyle t}$ tady.

Pro dvě dimenze se nejprve aplikuje jednou dovnitř ${ displaystyle x}$ a znovu dovnitř ${ displaystyle y}$ :

{ displaystyle b _ {- 1} = p (t_ {x}, f _ {(- 1, -1)}, f _ {(0, -1)}, f _ {(1, -1)}, f _ {( 2, -1)}),}

{ displaystyle b_ {0} = p (t_ {x}, f _ {(- 1,0)}, f _ {(0,0)}, f _ {(1,0)}, f _ {(2,0) }),}

{ displaystyle b_ {1} = p (t_ {x}, f _ {(- 1,1)}, f _ {(0,1)}, f _ {(1,1)}, f _ {(2,1) }),}

{ displaystyle b_ {2} = p (t_ {x}, f _ {(- 1,2)}, f _ {(0,2)}, f _ {(1,2)}, f _ {(2,2) }),}

{ displaystyle p (x, y) = p (t_ {y}, b _ {- 1}, b_ {0}, b_ {1}, b_ {2}).}

Použití v počítačové grafice

Dolní polovina tohoto obrázku je zvětšením horní poloviny, což ukazuje, jak se vytváří zdánlivá ostrost levé čáry. Bikubická interpolace způsobuje překmit, který se zvyšuje akutance.

Bikubický algoritmus se často používá pro změnu měřítka obrázků a videa pro zobrazení (viz převzorkování bitmap ). Zachovává jemné detaily lépe než běžné bilineární algoritmus.

Kvůli negativním lalokům na jádře to však způsobuje přestřelení (halo). To může způsobit výstřižek, a je artefaktem (viz také vyzváněcí artefakty ), ale zvyšuje se akutance (zdánlivá ostrost) a může být žádoucí.

Viz také

Prostorové vyhlazení
Bézierův povrch
Bilineární interpolace
Cubic Hermite spline, jednorozměrný analog bikubického spline
Lanczos převzorkování
Přirozená interpolace sousedů
Sinc filtr
Spline interpolace
Tricubická interpolace
Směrová kubická konvoluce interpolace

Reference

^ R. Keys (1981). "Interpolace kubické konvoluce pro digitální zpracování obrazu". Transakce IEEE týkající se akustiky, řeči a zpracování signálu. 29 (6): 1153–1160. Bibcode:1981ITASS..29.1153K. CiteSeerX 10.1.1.320.776. doi:10.1109 / TASSP.1981.1163711.

externí odkazy

[Keys-1] R. Keys (1981). "Interpolace kubické konvoluce pro digitální zpracování obrazu". Transakce IEEE týkající se akustiky, řeči a zpracování signálu. 29 (6): 1153–1160. Bibcode:1981ITASS..29.1153K. CiteSeerX 10.1.1.320.776. doi:10.1109 / TASSP.1981.1163711.

[1]