Spline-interpoláció A matematikában a numerikus analízis területén a spline egy olyan speciális függvény, amely szakaszonként polinomokból áll. Interpolációs feladatok megoldásához gyakran el nyben részesítik a spline-interpolációt a polinom interpolációval szemben, mert még alacsony fokú polinomok esetén is hasonló eredményeket szolgáltat, a magasabb fokszámú polinomokkal végzett interpoláció rosszul kondicionáltsága és numerikus instabilitása nélkül. A „spline” megnevezést a függvények egy olyan tág csoportjára használják, amelyeket akár egy, akár többdimenziós adatok interpolációjára és simítására alkalmaznak. Az interpoláló spline függvényeket alkalmas simasági mértéket (például integrált négyzetes görbületet) minimalizáló függvényekként határozzák meg. A számítógéppel segített tervezésben (CAD) és a számítógépes grafikában a spline megnevezéssel gyakrabban egy szakaszonként polinomokból álló paraméteres görbére utalnak. Ezek a görbék népszer ek, mivel egyszer az el állításuk, könnyen és pontosan számíthatók és bonyolult alakzatokat képesek jól közelíteni görbe illesztéssel és interaktív görbe tervezéssel. Általánosan elfogadott, hogy a spline-okra történ els matematikai hivatkozás Schoenberg egy 1946-ban írt cikkében található, ahol valószín leg el ször utalt ez a szó egy szakaszonként polinomokból álló sima közelít függvényre. A gyökerek azonban a repül gép és hajó épít iparig nyúlnak vissza. Évekig a hajók tervezésben az volt a gyakorlat, hogy ebben a fázisban kicsinyített modelleket építettek. Rögzített, elfordítható pöckökön keresztül fából készült hajlékony és rugalmas csíkokat helyeztek el és ezek minimális mechanikai energiájú állapotot vettek fel. A spline szó tehát eredetileg ilyen csíkokra, illetve a k m ves mesterek rugalmasan alakítható vonalzójára utalt. A spline-ok használata az autók karosszériájának tervezéséhez úgy t nik, egymástól függetlenül nyert teret különböz helyeken. Megemlítjük e tekintetben de Casteljau-t a Citroënnél, Pierre Bézier-t a Renault-nál, Birkhoffot, és de Boor-t a General Motors-nál, akik az 1950-es évek végén, a 60-as évek elején dolgoztak. De Boor munkái a General Motors-nál cikkek egész sorát eredményezték a 60-as évek elején, többek között a B-spline-okról szóló alapvet tanulmányokat. A spline-ok bemutatását a paraméteres görbékkel kezdjük, mivel talán így lehet a legszemléletesebben megismerni a spline interpoláció sajátosságait. Ebb l egyrészt az egyváltozós eset speciális esetként származtatható, másrészt így az ún. tenzorszorzat interpoláció segítségével a több dimenziós interpoláció is könnyen kezelhet .
Alapfogalmak Egy síkgörbe a következ paraméteres alakban általában kényelmesen kezelhet
Q( u ) = ( X ( u ), Y ( u )) ,
1.ábra Paraméteresen adott síkgörbe
ahol X ( u ) , Y ( u ) az u paraméter egyérték függvényei. Egy adott u paraméter érték a görbe egy pontjának x ill. y koordinátáit adja meg az X ( u ) , Y ( u ) függvények révén. Habár polinomokkal egyszer dolgozni, általában nem lehet egy görbét kielégít en megadni csupán egyetlen polinomot használva X ( u ) , Y ( u ) -hoz. Ehelyett szokásos a görbét kisebb szakaszokra, szegmensekre felosztani, mindegyik szegmensre egy-egy polinomot megadni, és ezeket összekapcsolva szakaszonkénti polinom görbét definiálni. Így tehát amint az u paraméter valamilyen kezd minimális u min és maximális u max között változik, az u változó bizonyos kitüntetett értékei, az ún. csomópontok kapcsolják össze a polinom szegmenseket. A csomópontok (csomók) sorozata az u paraméter értéke szerint nem csökken , és a csomó sorozatot vagy más néven a csomóvektort alkotja. u min = u 0 ≤ ⋯ ≤ u j ≤ ⋯ ≤ u max
Az X ( u ) , Y ( u ) általában ki kell, hogy elégítsen bizonyos folytonossági feltételeket a csomópontokban; ha a 0-adiktól a d-edik deriváltak mindenhol, de különösen a csomópontokban folytonosak, akkor X és Y ún. Cd - folytonosak. Bizonyos esetekben feltételezzük majd, hogy a csomópontok mind különböz ek és egymástól adott egyenl távolságban vannak
u i +1 = u i + ∆ . Ezt egyenletes csomó sorozatnak nevezik. Gyakran kényelmes feltételezni, hogy u i = i , amib l nyilvánvaló, hogy = 1. Sok esetben egyszer bb X –et és Y –t az u i -t l u i +1 -ig tartó intervallumon
u=
u − ui u i +1 − u i
0
u
1
függvényében lokális paraméterezéssel kifejezni u helyett. A felülvonás arra fog utalni, hogy az egész görbére egységes, egyetlen paraméterezéssel dolgozunk. A felülvonás hiánya pedig azt fogja jelenteni, hogy a paraméterezés az adott csomók közötti intervallum bal oldali végpontjára vonatkozik. Egy görbét többféle módon adhatunk meg. Ezek nagyjából az „interpoláció” ill. „approximáció” kategóriáiba sorolhatók. Mindkét mód pontok egy sorozatának a megadásával kezd dik, amelyeket a rajzokon „•”, illetve „+” fognak jelölni. Az interpoláció esetében a görbének át kell haladnia egy megadott sorrendben a Pi adatpontokon (lásd a 2. ábrát).
2.ábra Interpolációval megadott görbe Akár interpolációról, akár approximációról legyen szó, ha elmozdítjuk a pontokat, megváltozik a görbe. Viszont van olyan approximációs eljárás, amikor a görbének csak egy adott szakasza és nem az egész görbe változik meg akkor, ha egyetlen pontot elmozdítunk.
3. ábra Olyan görbe, amely „+”-szal jelölt pontok sorozatát approximálja. A folytonos és s r n pontozott görbék különálló szegmensek, amelyeket csuklópontok (joint) csatlakoztatnak egymáshoz. Az u paraméter megfelel értékei a csomópontok (knot).
Hermite és köbös spline interpoláció Tegyük fel, hogy (m + 1) számú P0 … Pm adatponttal rendelkezünk, amelyeken keresztül egy görbét szeretnénk rajzolni, például a 2. ábrán láthatót (ahol m = 6). Két egymás utáni pontot egy-egy különálló görbeszakasz köt össze. Az i-edik szegmens Pi és Pi +1 között fut, ennek megfelel en pedig az u paraméter az u i csomótól az u i +1 csomóig változva generálja a szegmenst. Mivel minden egyes ilyen Q i ( u ) szegmenset X ( u ) , Y ( u ) paramétereznek, igazából az érdekel minket, hogyan határozzuk meg X ( u ) , Y ( u ) -t a Pi = (xi, yi) pontok segítségével. Általánosságban véve X ( u ) -t, ami az x koordináta, egyedül az adatpontok x0, … , xm koordinátái (x koordináták) határozzák meg. Ehhez hasonlóan Y ( u ) -t, ami az y koordináta, egyedül az adatpontok y0, … , ym koordinátái (y koordináták) határozzák meg. Továbbá mivel X ( u ) és Y ( u ) hasonlóak, csak az Y ( u ) -val foglalkozunk. Valójában három dimenziós görbe esetén egyszer en megadjuk Z ( u ) -t és Q i ( u ) -t pedig X ( u ) , Y ( u ) , Z ( u ) segítségével. A számítás egyszer sége érdekében X ( u ) , Y ( u ) , Z ( u ) tekintetében polinomokra fogunk szorítkozni. A harmadfokú (köbös) polinomok sok alkalmazás szempontjából ésszer ráfordítással megfelel rugalmasságot tesznek lehet vé. A 2. ábrán látható görbére Y ( u ) így néz ki:
A számítások megkönnyítése céljából az el z ekben mondottak szerint átparaméterezünk minden egyes Yi szegmenset külön-külön u helyett u-t használva. Ez azt jelenti, hogy u = u i - i lesz az ábrán látható csomóponti sorozatra. Minden egyes Yi (u) az u paraméter harmadfokú polinomja
Yi (u ) = a i + bi u + ci u 2 + d i u 3 .
Két dolgot ismerünk a függvénnyel kapcsolatosan:
Yi (0) = y i
= ai
Yi (1) = y i +1 = ai + bi + c i + d i Mivel négy együtthatót kell meghatározni, két további feltétel szükséges egy adott Yi (u) teljes megadásához. Ennek egyik egyszer módja Y (u) els deriváltjainak, Di-nek tetsz leges értéken történ megkötése minden egyes u i csomópontban az alábbiak szerint Yi (1) (0) = Di
= bi
Yi (1) = Di +1 = bi + 2ci + 3d i (1)
.
Ezt a négy egyenletet meg tudjuk oldani egyszer és mindenkorra. A következ eredményre jutunk:
ai = y i bi = Di ci = 3( y i +1 − y i ) − 2 Di − Di +1
.
d i = 2( y i − y i +1 ) + Di + Di +1 Mivel Di-t használjuk az i-edik szegmens bal oldalán deriváltként (azaz Yi (1) (0) -t) és az (i – 1)-edik szegmens jobb oldalán is (mint Yi -(1) 1 (1) ), Y (u)-nak folytonosak az els deriváltjai. Ez az eljárás az Hermite interpoláció, és általánosítható magasabb fokszámú polinomokra is. Hogyan határozhatjuk meg a Di-ket? Ennek egyik lehet sége az, hogy automatikusan kiszámítjuk ket, például az yi-1, yi, yi+1, pontokon keresztül egy parabola illesztéssel, az yi-nél vett deriválttal definiálva Di-t; tetsz leges értékeket (például 0-t) adhatunk meg a végpontokban. Esetleg mi magunk adhatjuk meg közvetlenül a deriváltakat. Lehet ségünk van úgy illeszteni a csuklópontokban az egymásra következ szegmenseket, hogy mind az els , mind a második deriváltak megegyezzenek, mindössze harmadfokú polinomokat felhasználva ehhez. Tegyük fel, mint korábban, úgy most is hogy (m + 1) számú P0 … Pm adatponttal rendelkezünk, amelyeken keresztül egy görbét szeretnénk interpolálni. Az m darab szegmens Y0 (u) , … , Ym (u) mindegyike harmadfokú polinom, négy együtthatóval. Ezért 4m darab ismeretlent kell kiszámítanunk. Az összesen (m - 1) darab bels u1 , ⋯ , u m−1 csomópont mindegyikében négy feltételt írhatunk fel:
Yi −1 (1) = y i Yi (0) = y i
Yi −(11) (1) = Yi (1) (0) Yi −( 21) (1) = Yi ( 2) (0)
Mivel még megköveteljük
Y0 (0) = y 0 Ym −1 (1) = y m teljesítését is, így összesen 4(m – 1) + 2 = 4m – 2 feltételünk van, amelyb l 4m darab ismeretlent kell kiszámítani. Ezért még két feltételre van szükség. Ezeket változatos módon adhatjuk meg. Általánosan szokásos módszer a végpontokban zérus értéket felvenni a második deriváltak számára; ez a választás eredményezi az ún. természetes köbös spline-t.
A természetes köbös spline meghatározása Nem kell ezt a 4m egyenletet közvetlenül megoldani – a probléma egyszer síthet . Vegyük észre, hogy a természetes köbös spline valójában az Hermite-féle interpoláció speciális esete; egyszer en úgy fogjuk megválasztani az els deriváltak vektorát, hogy a második deriváltak is megegyezzenek. Ha ki tudjuk számítani a szükséges Di-ket, máris megkapjuk az ai, bi, ci, di értékeit is a Di-k függvényében. Így minden egyes bels csuklópontban úgy akarjuk felvenni Di-t, hogy (2) Yi (2) (0) −1 (1) = Yi
vagy 2ci −1 + 6d i −1 = 2ci . Behelyettesítve ezt az el z megoldásunkba ci-1, di-1, ci –re, az alábbi egyenletet kapjuk: 2 [3 ( yi − y i −1 ) − 2 Di −1 − Di ] + 6 [2 ( yi −1 − y i ) + Di −1 + Di ]
= 2 [3 ( y i +1 − yi ) − 2 Di − Di +1 ] Egyszer sítve és az ismeretleneket a bal oldalra rendezve az eredmény
Di −1 + 4 Di + Di +1 = 3 ( yi +1 − yi −1 ) . Mivel m – 1 bels csuklópontunk van, ezért az egyenletek száma is m – 1. Ha el írjuk azt, hogy a második derivált zérus legyen a görbe kezdetén, akkor ebb l következik, hogy 2c0 = 0 2 [3 ( y1 − y 0 ) − 2 D0 − D1 ] = 0 . 2 D0 + D1 = 3 ( y1 − y 0 ) Ehhez hasonlóan, ha el írjuk azt, hogy a második derivált zérus legyen a görbe végén, akkor
Dm −1 + 2 Dm = 3 ( y m − y m −1 ) . Most m + 1 egyenletünk van m + 1 ismeretlennel. Mátrixos alakban az egyenletrendszer 2 1 D0 3 ( y1 − y 0 ) 1 4 1 D 3( y − y ) 2 0 1 1 4 1 . . . 1 4 1 . . = . . . . . . 1 4 1 . 3 ( y m − y m − 2 ) 1 2 Dm 3 ( y m − y m −1 )
Felülr l elkezdve minden sorban az els 1-est kiküszöbölhetjük a közvetlenül felette lev sort felhasználva és átskálázzuk a mátrix f átlóját: 0
1/2
for i
1 step 1 until m – 1 do i
endfor
1/4 (4 –
i – 1)
m
1/(2 –
m – 1)
A megfelel m veleteket elvégezzük a jobb oldal elemein is; például az y komponensekre 0
3(y1 – y0)
0
1 step 1 until m – 1 do
for i
(3(yi + 1 – yi – 1 –
i
i – 1)
i
endfor m
(3(ym – ym – 1) –
m – 1)
m
Ennek az el re haladó kiküszöbölésnek az eredménye 1 γ 0 1
γ1 1
γ2
.
.
. 1 γ m− 2 1
D0 δ 0 D δ 1 1 . . . = . . . . γ m −1 . δ m −1 1 Dm δ m
Innen közvetlenül kiszámíthatjuk Dm értékét és egyszer az egyenletrendszert megoldani Dm-1 , … , D0 –ra fokozatos visszahelyettesítéssel:
Dm
m
for i
m – 1 step -1 until 0 do Di
i
– i Di – 1
endfor Az el re haladó kiküszöbölést megvalósító i szorzókat elég egyszer kiszámítani. Viszont a i –ket ki kell számítani és a visszahelyettesítést el kell végezni külön minden egyes koordinátára. Ha egy adatpont megváltozik, a j , … , m értékeket ismét el kell állítani, és a visszahelyettesítéseket újból teljesen ki kell számítani.
Klasszikus és általánosított interpoláció Az interpoláció definíció szerint folytonos adatok valamilyen modellen alapuló el állítása diszkrét adatokból egy adott abszcissza tartományon belül. A kardinális bázis kifejezést (vagy kib vítve az interpoláció kardinális bázisa) a spline függvények egy olyan bázisára alkalmazzuk, amely az interpolációs problémát triviálisan egyszer vé teszi olyan értelemben, ahogyan a
u −uj Pi (u ) = Π j =0 u − u j j ≠i i M
i = 0, … , M
Lagrange polinomok triviálisan egyszer vé teszik a polinom interpolációt. Ezeknek a polinomoknak ugyanis megvan az a tulajdonságuk, hogy
1 ha i = j , Pi (u j ) = 0 ha i ≠ j
és ennek az az eredménye, hogy a cj interpolációs együtthatókat, amelyek biztosítják a M
∑ c P (u i =0
i i
j
) = yj
j = 0, … , M
alakú interpolációt, egyszer en minden i-re így számíthatjuk ki: ci = yi . Általánosítva a polinom interpoláció esetét, azt mondhatjuk, hogy a klasszikus interpoláció esetén f (u ) = ∑ f i ϕint (u − u i )
(1)
i∈Z
az interpolált f (u ) érték az fj minta elemek lineáris kombinációjaként írható fel, ahol a súlyok a ϕint (u − u j ) magfüggvény vagy szintetizáló függvény értékei, Z pedig az egész számok halmazát jelöli. A magfüggvény kielégíti a Lagrange polinomokhoz hasonló interpolációs feltételt, vagyis az értéke 1 az u = u j helyen, egyébként pedig a diszkrét j index más értékeire
zérus (tehát ϕint (u k − ui ) =0, ha k
i) .
Ha az interpolációt diszkrét u = u k értékekre írjuk fel, akkor f k = ∑ f i ϕ int (k − i ) .
k ∈Z
(2)
i∈Z
Ez az egyenlet az interpolációs feltétel. Nagyon fontos észrevétel az, hogy ez az összefüggés diszkrét konvolúció. Ezért átírhatjuk az alábbi formában f k = ( f ∗ p )k ,
k ∈Z
(3)
ahol bevezettük a pk = ϕ int (k ) jelölést, ezzel hangsúlyozva azt, hogy csak diszkrét sorozatok konvolúciójáról beszélünk. Ebben az értelemben az eredeti (1) összefüggés nem konvolúció, mert nem csak egész értékekre számítjuk ki. Világos az, hogy (2) egyenérték azzal, hogy pk = δ k , ahol δ k a Kronecker-féle delta szimbólum, melyre δ 0 = 1 és máshol mindenütt zérus. Most beszéljünk az általánosított interpolációról. Az (1) interpolációs összefüggés általánosításaként tekintsük a következ alakot f (u ) = ∑ ci ϕ(u − ui ) .
(4)
i∈Z
Az alapvet különbség a klasszikus (1) alak és az általánosított alak (4) között a ci együtthatók bevezetése az fi minta elemek (függvényértékek) helyett. Ez új lehet ségeket teremt olyan értelemben, hogy az interpolációt most két lépésben határozhatjuk meg: el ször meghatározzuk a ci együtthatókat az fi minta elemekb l; másodszor, a kívánt f (u ) interpolált értékeket határozzuk meg a ci együtthatók segítségével. Ennek a szétválasztásnak az el nye az, hogy a szintetizáló függvényt általánosabb módon vehetjük fel és így az kedvez bb tulajdonságokkal rendelkezhet mint a klasszikus interpoláció esetében, ahol ck = f k . Hátránya, hogy egy további lépésre van szükség, de ezt nagyban kompenzálja az, hogy jobb min ség interpolációra van lehet ségünk, mivel a szintetizáló függvényeket b vebb körb l választhatjuk ki. Tegyük fel, hogy az általánosított interpoláció esetében el akarunk írni egy, a (2)-hez hasonló feltételt. Megint egész u = u k = k argumentum értékekre szorítkozva
f k = ∑ ci p k −i ,
k ∈Z
(5)
i∈Z
ahol pk = ϕ(k ) . Ha ismerjük el re a ϕ függvényt, akkor ez az összefüggés az ismeretlen ci együtthatókra vonatkozóan egy egyszer lineáris egyenletrendszer. Ennek az egyenletrendszernek a dimenziója alapesetben végtelen, az egyenletek számát tekintve, mivel az összes k ∈ Z értéket figyelembe vesszük. Ezenkívül az ismeretlenek számát tekintve is végtelen, mert minden i ∈ Z értéket az összegben felírtunk. Hogyan csökkenthetjük ezt az egyenletrendszert kezelhet méret re? Egyrészt úgy, hogy tudjuk, a gyakorlati esetekben a rendelkezésre álló mintaelemek k száma véges (ami korlátozza az egyenletek számát), ugyanakkor a ϕ függvényt véges tartójú függvényként vesszük fel (ami korlátozza az ismeretlenek számát). Így tehát egy c = P −1f alakú problémával szembesülünk, és a szakirodalom jó része olyan hatékony számítási eljárásokkal foglalkozik, amelyek megoldják ezt az egyenletrendszert valamely konkrétan választott ϕ szintetizáló függvényre. Az általánosított interpoláció egyenl köz adatpontok esetén digitális sz rési feladatként is megfogalmazható. Ez a megoldás onnan indul, hogy felismerjük, az (5) kifejezés is diszkrét konvolúció: f k = (c ∗ p )k .
k ∈Z
(6)
Ebb l rögtön az következik, hogy az együtthatók végtelen {ck } sorozata az {fk } végtelen sorozat és a (p)-1 konvolúció-inverz konvolúciójaként számítható ki. Ez utóbbi egyszer en a {( p)−k 1} számok olyan sorozata, amelyre ( p ∗ ( p)−1 )k = δ k teljesül. Ez a sorozat egyértelm en meghatározott és a számunkra érdekes esetekben valóban létezik. A (6) összefüggés mindkét oldalát konvolválva ( p ) −k 1 -val azt kapjuk, hogy ck = (( p) −1 ∗ f )k .
k ∈Z
(7)
Mivel egy diszkrét konvolúció egyben digitális sz rést is jelent, ezért azt várjuk, hogy a diszkrét sz rés a P mátrix invertálásának egy lehetséges alternatívája a {ck } ismeretlen együtthatók meghatározása szempontjából. Ennek nagyon hatásos számítási eljárása ismert például az ún. B-spline függvények esetében. A számításigénye a népszer köbös B-spline esetében mindössze két összeadás és három szorzás együtthatónként. Ha összevetjük (1)-et (4)-gyel, akkor azt kapjuk, hogy a klasszikus interpoláció az általánosított interpoláció egy speciális esete, ahol ck = f k és ϕ = ϕint . Megmutatjuk, hogy ennek a megfordítottja is igaz, mivel az általánosított interpoláció egyúttal klasszikus interpoláció is. Hogy ezt megmutathassuk, meg fogjuk határozni a ϕint interpoláló függvényt a neki megfelel nem-interpoláló függvény segítségével. A (4) és (7) egyenletekb l következik az, hogy
(
)
f (u ) = ∑ ( p) −1 ∗ f i ϕ (u − ui ) = ∑ ∑ ( p) i−21 f i1 −i2 ϕ (u − ui1 ) . i∈Z
i1∈Z i2∈Z
Végül a ϕint interpoláló függvény, amely mintegy „el van rejtve” a nem-interpoláló –ben
ϕint (u ) = ∑ ( p) i−1ϕ (u − ui ) .
(8)
i∈Z
Igen lényeges azt megérteni, hogy ez az ekvivalencia lehet vé teszi, hogy a végtelen tartójú ϕint interpoláló függvénnyel végzett m veleteket kicseréljük a véges tartójú, neminterpoláló függvénnyel végzett m veletekre. Az, hogy szabadon megválaszthatjuk a szintetizáló függvényt, megnyitja annak a lehet ségét, hogy olyan szintetizáló függvényt válasz-
szunk, amely sokkal jobb interpolációt tesz lehet vé, mint bármely explicit ϕint interpoláló függvény.
Egyenköz B-spline interpoláció A szintetizáló függvények egész családja alkotható meg a B-spline-ok segítségével. Egyezményes jelölésük n , ahol az n ∈ N nem hatvány, hanem egy index, a spline fokszáma. Ezek a függvények szakaszonként n-edfokú polinomok és (n – 1)-szer folytonosan differenciálhatók, valamint megadhatók a 1 0 β ( x ) = 12 0
x≤
1 2
x = 12 x > 12
és (−1) k (n + 1) n+1 ( 2 + x − k )+n k = 0 ( n + 1 − k )!k! n +1
β n ( x) = ∑
∀x ∈ R ,
∀n ∈ N ∗ ,
kifejezésekkel, ahol definíció szerint ( x ) n+ = (max( 0, x )) n
n > 0.
Az n = 0 és n = 1 esetben a B-spline szintetizáló
0
és
1
függvények így néznek ki:
Az n > 1 esetben egyetlen szintetizáló n B-spline függvény sem rendelkezik az interpoláló tulajdonsággal, tehát nem elégíti ki az (1)-es összefüggést. Ehelyett a (4)-es általánosított interpoláció képletét kell minden esetben használni. Sajnos néhány szerz elfeledkezett err l és valójában az interpolációt összekeverte az approximációval, ami teljesen abszurd eredményekhez vezetett. Tehát semmi esetre sem hagyható ki a B-spline interpolációnál az a lépés, amikor az {fk } adatokat transzformáljuk a {ck } együtthatók sorozatába. Ez egyenköz interpoláció (adatpontok) esetében igen hatékony digitális rekurzív (IIR) sz réssel megvalósítható. A gyakorlatban sokszor köbös B-spline-okat alkalmaznak. Ezek definíciója 2 − 1 x 2 − (2 − x ) 0 ≤ x < 1 3 21 3 3 β ( x) = 1≤ x < 2 . 2 (2 − x ) 0 2≤ x
Ez a szintetizáló függvény nem interpoláló. Amint azt a (8) egyenlettel kapcsolatban már el3 mondtuk, mindenesetre lehetséges egy olyan végtelen tartójú ϕint = β card szintetizáló függvényt megadni, amellyel pontosan ugyanazt az f függvényt tudjuk el állítani. Ezt konkrétan illusztrálni tudjuk a következ ábrával, amelyen együtt láthatjuk a nem interpoláló 3 köbös
3 B-spline-t a vele egyenérték interpoláló szintetizáló párjával. Ez utóbbi β card függvény elnevezése kardinális köbös spline. A B-spline függvény hasonló a Gauss-féle haranggörbéhez, és ez nem véletlen, mert megmutatható, hogy a B-spline-ok a fokszám növelésével konvergálnak a Gauss-féle normál eloszlás függvényhez. Már az n = 3 esetén a B-spline a vele megegyez szórású Gauss-eloszlástól csak 3.5%-kal tér el. Az ábra jobb oldalán a kardinális spline csökken oszcillációt mutat, amely hasonlít a sinc függvényhez. Ez sem véletlen, mivel a fokszám növelésével a kardinális spline egyre jobban konvergál a sinc függvényhez. Világos tehát, hogy minél magasabb a fokszáma, annál jobb a spline interpoláció, mivel a frekvencia tartományban az „ideális” interpolációt a sinc függvény valósítja meg.
3 β card
3
Érdekes tulajdonsága a B-spline függvényeknek az, hogy a zérus fokszámú kiindulva egymásból rekurzív konvolúcióval is el állíthatók
β n = β 0 ∗ β n−1 ,
0
spline-ból (9)
ezért a B-spline függvények frekvencia tartománybeli jellemzése egyszer en (a Fourier transzformáció konvolúció tétele miatt)
sin( πf ) B (ω ) = B (2πf ) = πf (10) n
n
n+1
ω = sinc n+1 ( f ) = sinc n+1 . 2π
A B-spline interpoláció és approximáció közötti különbség egészen nyilvánvaló a frekvencia tartományban. Az n-edrend B-spline approximáció frekvencia átviteli függvényét a (10) öszszefüggés adja meg. Másrészt az n-edrend B-spline interpoláció H n( ) frekvencia átviteli függvénye kiegészül még egy tényez vel: a (7) egyenlet szerinti (p)-1 inverz sz r Fourier transzformáltjával. Az alábbi táblázat az n = 1-t l 5-ig tartalmazza ezeket a H n( ) függvényeket, és az ábrán B 5( ) valamint H 5( ) látható.
H 1( )
sinc 2 (ω / 2π ) 1
H 2( )
4 sinc3 (ω / 2π ) 3 + cos( ω )
H 3( )
3 sinc 4 (ω / 2π ) 2 + cos( ω )
H 4( )
192 sinc5 (ω / 2π ) 115 + 76 cos(ω ) + cos( 2ω )
H 5( )
60 sinc6 (ω / 2π ) 33 + 26 cos(ω ) + cos( 2ω )
