Bicubická interpolace - Bicubic interpolation

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

V matematice je bikubická interpolace rozšířením kubické interpolace (nezaměňovat s kubickou spline interpolací , metodou aplikace kubické interpolace na soubor dat) pro interpolaci datových bodů na dvourozměrné pravidelné mřížce . Interpolovaný povrch je hladší než odpovídající povrchy získané bilineární interpolací nebo interpolací nejbližšího souseda . Bicubickou interpolaci lze provést buď Lagrangeovým polynomem , kubickým splajnem nebo algoritmem kubické konvoluce .

Při zpracování obrazu je při převzorkování obrazu často volena bicubická interpolace před bilineární nebo nejbližší sousední interpolací . Na rozdíl od bilineární interpolace, která bere v úvahu pouze 4 pixely (2 × 2), bikubická interpolace uvažuje o 16 pixelech (4 × 4). Obrázky převzorkované pomocí bikubické interpolace jsou hladší a mají méně interpolačních artefaktů .

Výpočet

Bicubická interpolace na čtverci skládajícím se z 25 jednotkových čtverců spojených dohromady. Bicubická interpolace podle implementace Matplotliba . Barva označuje hodnotu funkce. Černé tečky jsou umístění interpolovaných předepsaných dat. Všimněte si, že vzorky barev nejsou radiálně symetrické.${\ Displaystyle [0,4] \ times [0,4]}$

Bilineární interpolace na stejné datové sadě jako výše. Deriváty povrchu nejsou přes hranice čtverce spojité.

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

Předpokládejme, že hodnoty funkce a deriváty , a jsou známé ve čtyřech rozích , , , a jednotkové čtverce. Interpolovaný povrch pak lze zapsat jako ${\ displaystyle f}$${\ displaystyle f_ {x}}$${\ displaystyle f_ {y}}$${\ displaystyle f_ {xy}}$${\ displaystyle (0,0)}$${\ displaystyle (1,0)}$${\ Displaystyle (0,1)}$${\ displaystyle (1,1)}$

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

Interpolační problém spočívá v určení 16 koeficientů . Shoda s hodnotami funkce poskytne čtyři rovnice: ${\ displaystyle a_ {ij}}$${\ displaystyle p (x, y)}$

1. ${\ Displaystyle f (0,0) = p (0,0) = a_ {00},}$
2. ${\ Displaystyle f (1,0) = p (1,0) = a_ {00}+a_ {10}+a_ {20}+a_ {30},}$
3. ${\ Displaystyle f (0,1) = p (0,1) = a_ {00}+a_ {01}+a_ {02}+a_ {03},}$
4. ${\ Displaystyle f (1,1) = p (1,1) = \ textstyle \ sum \ limits _ {i = 0}^{3} \ sum \ limits _ {j = 0}^{3} a_ {ij }.}$

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

1. ${\ Displaystyle f_ {x} (0,0) = p_ {x} (0,0) = a_ {10},}$
2. ${\ displaystyle f_ {x} (1,0) = p_ {x} (1,0) = a_ {10}+2a_ {20}+3a_ {30},}$
3. ${\ Displaystyle f_ {x} (0,1) = p_ {x} (0,1) = a_ {10}+a_ {11}+a_ {12}+a_ {13},}$
4. ${\ Displaystyle f_ {x} (1,1) = p_ {x} (1,1) = \ textstyle \ součet \ limity _ {i = 1}^{3} \ součet \ limity _ {j = 0}^ {3} a_ {ij} i,}$
5. ${\ Displaystyle f_ {y} (0,0) = p_ {y} (0,0) = a_ {01},}$
6. ${\ Displaystyle f_ {y} (1,0) = p_ {y} (1,0) = a_ {01}+a_ {11}+a_ {21}+a_ {31},}$
7. ${\ Displaystyle f_ {y} (0,1) = p_ {y} (0,1) = a_ {01}+2a_ {02}+3a_ {03},}$
8. ${\ Displaystyle f_ {y} (1,1) = p_ {y} (1,1) = \ textstyle \ sum \ limits _ {i = 0}^{3} \ sum \ limits _ {j = 1}^ {3} a_ {ij} j.}$

A čtyři rovnice pro smíšenou parciální derivaci : ${\ displaystyle xy}$

1. ${\ Displaystyle f_ {xy} (0,0) = p_ {xy} (0,0) = a_ {11},}$
2. ${\ Displaystyle f_ {xy} (1,0) = p_ {xy} (1,0) = a_ {11}+2a_ {21}+3a_ {31},}$
3. ${\ Displaystyle f_ {xy} (0,1) = p_ {xy} (0,1) = a_ {11}+2a_ {12}+3a_ {13},}$
4. ${\ Displaystyle f_ {xy} (1,1) = p_ {xy} (1,1) = \ textstyle \ sum \ limits _ {i = 1}^{3} \ sum \ limits _ {j = 1}^ {3} a_ {ij} ij.}$

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

${\ Displaystyle p_ {x} (x, y) = \ textstyle \ sum \ limits _ {i = 1}^{3} \ sum \ limits _ {j = 0}^{3} a_ {ij} ix^{ i-1} y^{j},}$

${\ Displaystyle p_ {y} (x, y) = \ textstyle \ sum \ limits _ {i = 0}^{3} \ sum \ limits _ {j = 1}^{3} a_ {ij} x^{ i} jy^{j-1},}$

${\ Displaystyle p_ {xy} (x, y) = \ textstyle \ sum \ limits _ {i = 1}^{3} \ sum \ limits _ {j = 1}^{3} a_ {ij} ix^{ i-1} jy^{j-1}.}$

Tento postup poskytne povrch na jednotkovém čtverci, který je spojitý a má spojité derivace. Bicubickou interpolaci na libovolně velké pravidelné mřížce pak lze provést tak, že se takové bikubické povrchy spojí a zajistí, aby se deriváty shodovaly na hranicích. ${\ displaystyle p (x, y)}$ ${\ Displaystyle [0,1] \ times [0,1]}$

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

${\ 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 }} \ right]^{T},}$

výše uvedený systém rovnic lze přeformulovat na matici pro lineární rovnici . ${\ Displaystyle A \ alpha = x}$

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

${\ 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 a -2 a -1 \\ 2 & -2 & 2 & -2 & 2 & -2 & 1 & 1 & 1 & 1 \ end {smallmatrix}} \ right],}$

což umožňuje rychlý a snadný výpočet. ${\ Displaystyle \ alpha}$

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

${\ 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) \ konec { 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í bicubickou interpolaci pomocí dat na přímočaré síti, nikoli na jednotkovém čtverci. V tomto případě se identity pro a stanou ${\ displaystyle p_ {x}, p_ {y},}$${\ displaystyle p_ {xy}}$

${\ Displaystyle p_ {x} (x, y) = \ textstyle \ sum \ limits _ {i = 1}^{3} \ sum \ limits _ {j = 0}^{3} {\ frac {a_ {ij } ix^{i-1} y^{j}} {\ Delta x}},}$

${\ Displaystyle p_ {y} (x, y) = \ textstyle \ sum \ limits _ {i = 0}^{3} \ sum \ limits _ {j = 1}^{3} {\ frac {a_ {ij } x^{i} jy^{j-1}} {\ Delta y}},}$

${\ Displaystyle p_ {xy} (x, y) = \ textstyle \ sum \ limits _ {i = 1}^{3} \ sum \ limits _ {j = 1}^{3} {\ frac {a_ {ij } ix^{i-1} jy^{j-1}} {\ Delta x \ Delta y}},}$

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

${\ 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 řešit se jako dříve. Dále se normalizované interpolační proměnné vypočítají jako ${\ Displaystyle \ alpha = A^{-1} x}$${\ displaystyle A}$

${\ displaystyle {\ overline {x}} = {\ frac {x-x_ {0}} {x_ {1} -x_ {0}}}}$,

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

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

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

Hledání derivací z funkčních hodnot

Pokud deriváty nejsou známy, jsou obvykle aproximovány z funkčních hodnot v bodech sousedících s rohy jednotkového čtverce, např. Pomocí konečných rozdílů .

Chcete -li najít buď jednotlivé derivace, nebo pomocí této metody najít sklon mezi dvěma okolními body v příslušné ose. Chcete -li například vypočítat pro jeden z bodů, najděte body nalevo a napravo od cílového bodu a vypočítejte jejich sklon a podobně pro . ${\ displaystyle f_ {x}}$${\ displaystyle f_ {y}}$${\ displaystyle f_ {x}}$${\ Displaystyle f (x, y)}$${\ displaystyle f_ {y}}$

Chcete -li najít křížovou derivaci , vezměte derivaci v obou osách, jednu po druhé. Například lze nejprve použít postup k nalezení derivací bodů nad a pod cílovým bodem, poté použít postup pro tyto hodnoty (spíše než jako obvykle pro hodnoty pro tyto body) k získání hodnoty pro cílový bod. (Nebo to lze provést v opačném směru, nejprve vypočítat a poté z nich. Oba poskytují ekvivalentní výsledky.) ${\ displaystyle f_ {xy}}$${\ displaystyle f_ {x}}$${\ displaystyle x}$${\ displaystyle f_ {y}}$${\ displaystyle f}$${\ displaystyle f_ {xy} (x, y)}$${\ displaystyle f_ {y}}$${\ displaystyle f_ {x}}$

Když na okrajích datové sady chybí některé z okolních bodů, chybějící body lze aproximovat několika způsoby. Jednoduchou a běžnou metodou je předpokládat, že sklon od stávajícího bodu k cílovému bodu pokračuje bez dalších změn, a použít to k výpočtu hypotetické hodnoty pro chybějící bod.

Bicubický konvoluční algoritmus

Bicubická 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 aplikací konvoluce s následujícím jádrem v obou dimenzích:

${\ 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 je obvykle nastaveno na -0,5 nebo -0,75. Všimněte si toho a pro všechna nenulová celá čísla . ${\ displaystyle a}$${\ displaystyle W (0) = 1}$${\ Displaystyle W (n) = 0}$${\ displaystyle n}$

Tento přístup navrhl Keys, který ukázal, že vytváří konvergenci třetího řádu s ohledem na interval vzorkování původní funkce. ${\ displaystyle a = -0,5}$

Pokud pro běžný případ použijeme maticový zápis , můžeme rovnici vyjádřit přívětivěji: ${\ displaystyle a = -0,5}$

${\ 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 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 vzorkovací body. 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 dotazovacímu bodu je zde označována . ${\ displaystyle t}$${\ displaystyle t}$

Pro dvě dimenze nejprve aplikované jednou a znovu v : ${\ displaystyle x}$${\ 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 a ukazuje, jak se vytváří zdánlivá ostrost levé linie. Bicubická interpolace způsobuje překročení, což zvyšuje akutnost .

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

Kvůli negativním lalokům na jádře však způsobuje překmit (haloing). To může způsobit oříznutí a je to artefakt (viz také vyzváněcí artefakty ), ale zvyšuje to akutnost (zjevnou ostrost) a může to být žádoucí.

Viz také

• Prostorové vyhlazování
• Bézierův povrch
• Bilineární interpolace
• Cubic Hermite spline , jednorozměrný analog bicubického spline
• Lanczosovo převzorkování
• Interpolace přirozeného souseda
• Zinkový filtr
• Interpolace splajnu
• Tricubická interpolace
• Směrová kubická konvoluční interpolace

Reference

externí odkazy

• Aplikace interpolace na výškové vzorky
• Interpolační teorie
• Vysvětlení a implementace (bi) kubické interpolace v jazyce Java/C ++
• Funkce listu aplikace Excel pro bicubickou Lagrangeovu interpolaci