Tiesinės prognozės metodas ir jo taikymai

• Tiesinė prognozė
• LPC metodo idėja
• Formantės
• Apie vamzdelius
• Šaltinio kodavimas
• Apie balsius ir priebalsius
• Prognozės paklaidos kodavimas
• Formulės
• Plokštumos taškų tiesinė prognozė
• Praktiniai patarimai
• Levinsono-Durbin algoritmas
• LPC kodavimo/dekodavimo schema
• Koeficientų kodavimas
• LSP (Line Spectral Pairs) - spektrinės poros tiesėje
• Sintezė
• CELP koderis
• MPE-LPC koderis
• Java kodas
• LPC klasės aprašymas
• Praktinė užduotis
• Literatūra

Įvadas

Tiesinė prognozė (angl. LPC - LinearPredictionCoefficients arba LinearPredictionCoding) yra vienas galingiausių signalų analizės metodų. Ypač jis gerai užsirekomendavo kalbos analizėje, tiesine prognoze paremtas kalbos kodavimas duoda geriausius kalbos ir kompresijos kokybės parametrus. Šiuo metodu gaunami kalbą aprašantys parametrai, jų skaičius yra nedidelis ir jie apskaičiuojami greitai. Čia aprašysime pagrindines tiesinės prognozės metodo idėjas ir aptarsime kai kurias metodo realizacijos ypatybes.

Pagrindinė metodo idėja

LPC metode daroma prielaida, kad kalbos signalas yra sužadinamas garso šaltiniu patalpintu kintamo skerspjūvio vamzdelio gale. Sužadintos garso bangos plinta vamzdeliu ir išsiveržia į aplinką priešingame gale. Pas žmogų garso šaltinis yra plaučiuose sudarytas atmosferinis viršslėgis ir virpančios balso stygos. Šis šaltinis charakterizuojamas intensyvumu (garsumu) ir dažniu (pagrindiniu tonu). Gerklės ir burnos kalbos traktas formuoja kintamo skersmens vamzdelį. Kalbos traktas charakterizuojamas rezonansiniais dažniais, vadinamais formantėmis.

Tiesinė prognozės metodu yra įvertinamos formantės, atskiriant jas nuo kalbą generuojančio šaltinio, lemiančio kalbos garsumą ir toną. Formančių eliminavimas iš kalbos signalo kartais vadinamas atvirkštiniu filtravimu, ir likęs signalas vadinamas liekamuoju.

Skaičiai aprašantys formantes ir liekamasis signalas gali būti saugojami ir siunčiami atskirai. Kalbos sintezavimas tiesinės prognozės metodu gaunamas apgręžiant metodą: liekamasis signalas tampa kalbos signalą generuojančiu šaltiniu, o iš formančių gaunamas filtras, atspindintis kalbos trakto geometriją. Filtruojant liekamąjį signalą ir gaunamas sintezuotas garsas.

Kadangi kalbą generuojantis traktas kinta laike, tiesinė prognozė atliekama trumpais laiko tarpais, vadinamais fragmentais, langais (frames). Kaip taisyklė, vienos sekundės trukmės kalbos signalas skaidomas į 30-50 langų.

Formančių įvertis

Pagrindinė LPC metodo problema yra įvertinti formantes remiantis įrašytu kalbos signalu. Metodu tikslas yra gauti tam tikrą diferencialinę lygtį, kurios esmė yra išreikšti kuo tiksliau eilinę garso slėgio imtį remiantis keliom prieš tai žinomom kalbos signalo reikšmėm. Kadangi naudojama tiesinė aproksimacija, tai gaunama skirtuminė diferencialinė lygtis yra vadinama tiesine prognoze, o pats signalo kodavimo metodas vadinamas tiesinės prognozės metodu.

Diferencialinės išraiškos koeficientai vadinami prognozės (tiesinės) koeficientais. Šie koeficientai aprašo formantes, taigi metodo esmė yra apskaičiuoti tiesinės prognozės koeficientus. Formulės apskaičiuoti LPC koeficientus yra gaunamos minimizuojant liekamojo signalo vidutinę kvadratinę paklaidą.

Rezultate yra gaunama atžvilgiu prognozės koeficientų tiesinė algebrinių lygčių sistema. Praktiškai tenka spręsti tokias problemas:

• Apskaičiuoti pagal kalbos signalo fragmento duomenis tiesinių lygčių sistemos matricos koeficientus ir laisvuosius narius.
• Išspręsti gautą tiesinę lygčių sistemą.

Niuansai: vamzdelis nelygus vamzdeliui

Gali atrodyti keista, kad kalbos signalas gali būti aprašytas tokiu paprastu vamzdelio modeliu. Kad toks paprastas modelis galiotų, vamzdelis turi neturėti nei vieno išsišakojimo. Kiekviena šaka aprašoma antirezonansiniais dažniais, kurie pasižymi tam tikro ilgio bangų slopinimu. Matematine prasme vamzdelį su išsišakojimais geriau aprašinėti tokiu modeliu, kuris leistų reguliuoti signalo nulius spektro srityje.

Įprasti balsiai gerai aprašomi paprastu kintamo skerspjūvio vamzdeliu. Tačiau nosiniai garsai, kurių suformavime aktyviai dalyvauja šoninis nosies ertmės kanalas, reikalauja kiek sudėtingesnio modelio. Tačiau praktiškai į tai dažnai neatsižvelgiama ir problemos sprendimas nukeliamas į liekamojo signalo valdymą.

Šaltinio kodavimas

Jei prognozės koeficientai gerai apskaičiuoti, kita yra paprasta: atlikti atvirkštinį filtravimą ir gauti gryną liekamąjį narį. Remiantis gautu liekamuoju nariu įvertinamas pagrindinis tonas ir jo galia, bei jie užkoduojami (įsimenami).

Tačiau kai kurie priebalsiai yra suformuojami turbulentinėmis oro srovėmis, dėl ko gaunasi frikatyviniai (šnypščiamieji) ir sprogstamieji garsai.
Laimei, tiesinės prognozės lygčiai yra nesvarbu kokios rūšies garsas yra aproksimuojamas (kvazi-periodinis ar chaotinis).

Kiekvienam fragmentui reikia nuspręsti su kokiu garsu dirbama. Jei tai kvaziperiodinis - įvertinti pagrindinį toną; bet kuriuo atveju įvertinti liekamojo nario galią. Ši kokybinė informacija apie garsą taip pat yra užkoduojama (glaustai užrašoma). Sintezės metu ši informacija naudojama imituojant garso šaltinio modelį. LPC-10e standarte 1 žymimi vokaliniai fragmentai, LPC-10e sugeba perteikta geros kokybės kalbą 2400 bitų per sekundę greičiu.

Niuansai: balsiai - ne balsiai, priebalsiai - nepriebalsiai

Deja, ne viskas taip paprasta. Daugelis garsų nėra grynai vokaliniai arba nevokaliniai. Pavyzdžiui, r, z, v turi ir balsio ir priebalsio bruožų. Tokius garsus generuodami dviejų būsenų tiesinės prognozės metodu paremtu sintezatoriumi negausime geros garso kokybės.

Kita problema yra mažas formančių kiekis, aprašomas tiesinės prognozės koeficientais. Tai pasireiškia tuo, kad dalis garso informacijos pereina į liekamąjį narį. Pavyzdžiui, nosiniai garsai pasižymi antirezonansiniais dažniais ir ši informacija persikelia į liekamąjį narį. Liežuvio sudaromi tarpai veikia panašiai kaip ir nosies ertmės. Dėl to praktiškai visi garsai vien tik rezonansiniais dažniais (formantėmis) aprašomi netiksliai.

Todėl liekamasis narys yra svarbus ir menkas jo aprašymas negali garantuoti geros sintezuojamo garso kokybės. Geriausia kokybė pasiekiama, jei, kartu su tiesinės prognozės koeficientais, pilnai perduotume ir liekamąjį narį. Deja visa esmė yra suspausti kalbos signalą; jei perduotumėme pilnai ir liekamąjį narį, tai iš esmės perduodamas signalas užimamų bitų skaičiumi mažai skirtųsi nuo pradinio kalbos signalo. Taigi reikia ieškoti būdų kaip glaustai perduoti esminę informaciją apie liekamąjį narį.

Liekamojo signalo (prognozės paklaidos) kodavimas

Yra aibė pasiūlymų kaip koduoti liekamąjį narį. Tai labai svarbi vieta lemianti kompresijos ir sintezuojamo signalo kokybės santykį. Dabar labai populiarios yra kodų lentelės, tai yra tam tikri dažnai pasitaikantys liekamųjų signalų pavyzdžiai, kurių sudarymo principai ir lemia konkretaus LPC sintezatoriaus ypatybes. Dirbant su kodų lentelės, kodavimo metu yra parenkamas iš lentelės pavyzdys, kuris mažiausiai skiriasi nuo gautos tuo momentu konkrečios paklaidos ir įsimenamas tik išrinkto lentelės kodo numeris. Sintezavimo metu pagal numerį iš kodų lentelės pasiimamas kodas su atitinkamu numeriu ir vėliau jis naudojamas sužadinti tiesinės prognozės koeficientais aprašomam filtrui. Tokios schemos vadinamos CELP - CodeExcitedLinearPrediction.

Kad CELP dirbtų gerai, kodų lentelė turi būti pakankamai turtinga, kad iš jos būtų galima parinkti artimą įvairiems liekamiesiems signalams. Bet jei lentelė yra didelė, tampa sunku parinkti artimą ir vėl mažėja kompresijos laipsnis. Didžiausia problema yra, kad skirtingų kalbos fragmentų pagrindiniams tonams reikės skirtingų kodų lentelių.

Šią problemą galima spręsti sudarant dvi mažas kodų lenteles vietoje vienos didelės. Viena lentelė yra sudaroma iš anksto LPC sistemos kūrėjo ir joje saugomos vieno periodo (laiko tarpo tarp balso stygų susitraukimo) trukmės liekamieji nariai. Kitas lentelė yra adaptyvi. Ji inicializuojama tuščia aibe ir yra užpildoma palaipsniui, saugant paskutinių įvairios trukmės liekamųjų narių pavyzdžius.

Naudojant tokį CELP metodą gaunama gera natūraliai skambanti kalba su sąnaudom 4800 bitai per sekundę.

Matematinė dalis

Tarkime {x_n}_n=0,...,N-1 yra signalo fragmento duomenys. Pažymėkime {a_m}_1<m<M tiesinės prognozės koeficientus. Čia M žymi ieškomų prognozės koeficientų skaičių. Patogumo dėlei pažymėsime a₀=1. Pagal tiesinės prognozės metodą eilinė duomenų reikšmė x_n yra aproksimuojama keletu prieš tai žinomų duomenų reikšmių tiesine išraiška. Tiesinės išraiškos koeficientai pasirinktam duomenų fragmentui nekeičiami (jie nepriklauso nuo indekso n). Taigi, pažymėję tiesinės prognozės paklaidą e_n, gausime tokią išraišką:

x_n = S _1<m<M a_mx_n-m+ e_n.

Šioje išraiškoje nenurodėme indekso n kitimo sritį. Užrašyti n=0,...,N-1 būtų ne visai tikslu, nes pradiniams n<M, duomenys x_n-m, kai m>M, būtų neapibrėžti. Populiariausi yra tokie šios problemos sprendimai būdai:

1. Formulėje parašyti n=M,...,N-1;
2. Imti n=0,...,N-1 ir laikyti, kad x_n-m=0, kai n-m<0;
3. Imti n=0,...,N-1 ir laikyti, kad x_n, kai n=-M,...,-1, yra paskutinės M prieš tai ėjusio duomenų fragmento reikšmės.

Dirbant su kalbos signalu, pirmojo fragmento atveju galima naudoti 1-ąjį variantą, o vėliau, kai jau žinomi prieš fragmentą einantys duomenys, galima pereiti prie 3-iojo varianto.
Lygtis tiesinės prognozės koeficientams {a_m}_1<m<M gaunamos minimizuojant atžvilgiu prognozės koeficientų (vidutinę) kvadratinę paklaidą, t.y.

Err = S_n (x_n- S_1<m<M a_mx_n-m)² (=S_n (e_n)²).

Čia n kitimo srities vėl nenurodėme dėl anksčiau minėtų priežasčių. Minimizuojant funkciją Err reikia apskaičiuoti jos išvestines kintamųjų a_matžvilgiu ir prilyginti jas 0. Taip gaunama tokia tiesinių lygčių sistema:

S_n x_n-k(x_n- S_1<m<M a_mx_n-m) = 0, k=1,2,...,M.

S_1<m<M a_mR_k-m = R_k, k=1,2,...,M.

R_n = S_k x_n+kx_k.

Plokštumos taškų tiesinė prognozė

Tiesinės prognozės koeficientų metodą nesunku apibendrinti plokštumos taškams aproksimuoti.
Tarkime plokštumos taškai žymi spausdintinio simbolio kontūro taškus ir sunumeruoti kontūro apėjimo prieš arba pagal laikrodžio rodyklę tvarka. Tikėtina, kad eilinį kontūro tašką galima neblogai aproksimuoti tiesiniu dariniu sudarytu iš prieš tai jau žinomų kontūro taškų. Eilės tvarka pažymėtus kontūro taškus patogu laikyti kompleksiniais skaičiais
z_n = x_n+Iy_n, n=0,1,...,N-1, (I menamasis vienetas, t.y. šaknis iš -1).
Prognozės koeficientus a_m, m=1,2,...,M taip pat laikysime kompleksiniais skaičiais:
a_m = a_m+ Ib_m.

Prognozės metodo tikslas rasti tokius kompleksinius skaičius a_m, kad įstačius juos į prognozės paklaidos išraiškas

z_n - S _1<m<M a_mz_n-m = e_n

gautume minimalią bendrą paklaidą, t.y. reikia minimizuoti

Err = S_n |z_n- S_1<m<M a_mz_n-m|² (=S_n |e_n|²).

S_n [ (x_n-k+Iy_n-k)((x_n-Iy_n) - S_1<m<M (a_m-I b_m)(x_n-m-Iy_n-m)) +
(x_n-k-Iy_n-k)((x_n+Iy_n)- S_1<m<M (a_m+I b_m)(x_n-m+Iy_n-m)) ] = 0,

S_n [ (x_n-k+Iy_n-k)((x_n-Iy_n)- S_1<m<M (a_m-I b_m)(x_n-m-Iy_n-m)) -
(x_n-k-Iy_n-k)((x_n+Iy_n)- S_1<m<M (a_m+I b_m)(x_n-m+Iy_n-m)) ] = 0,

k=1,2,...,M.

Jei z_n=0, kai n<0, tai pastarąją lygčių sistemą galima perrašyti taip:

S_1<m<M [ a_mRe(R_m-k) + b_mIm(R_m-k) ] = Re(R_-k),

S_1<m<M [ a_mIm(R_m-k) - b_mRe(R_m-k) ] = Im(R_-k),

k=1,2,...,M.

Čia R_n = S_k z_k+nConj(z_k) ( = S_k (x_k+n + Iy_k+n)(x_k - Iy_k) ).

Išsprendę gautą tiesinę lygčių sistemą rasime nežinomuosius a_m ir b_m, m=1,2,...,M, ir kompleksinius tiesinės prognozės koeficientus

a_m = a_m + Ib_m.

Levinsono-Durbin algoritmas

Analizuojant gautą lygčių sistemą atžvilgiu nežinomųjų, kurie ir yra tiesinės prognozės koeficientai, matyti kad:

1. Lygčių sistemos matrica yra Tioplico, t.y. matricos gretimos eilutės ir stulpeliai yra panašūs ir skiriasi tik poslinkiu.
2. Dešinė lygčių sistemos pusė yra specifinė ir yra poslinkis pirmojo stulpelio.

Lygčių sistemom su tokia specifika spręsti egzistuoja efektyvus metodas, vadinamas autorių vardu Levinson-Durbin algoritmu. Metodas rekursyviai ieško tiesinės prognozės koeficientus.

1. E⁰ = R₀
2. i=1,2,...,M
   • k_i = [ R_i- S_1<m<i-1 a_m^i-1 R_i-m ] / E^i-1 ;

   • a_iⁱ = k_i ;

   • m=1,2,...,i-1

     a_mⁱ = a_m^i-1 - k_ia_i-m^i-1 ;

     Eⁱ = (1-(k_i)²) E^i-1;

Atlikus paskutinę iteraciją gaunamas galutinis sprendinys:

a_m = (a^M)_m, 1<m<M .

Levisono-Durbin algoritmo sudėtingumas yra O(M²) eilės. Tai eile mažiau, nei tiesioginio lygčių sistemos sprendimo metodo sudėtingumo, kuris gaunasi lygčių sistemą sprendžiant kintamųjų eliminavimo metodu. Grubiai kalbant, kadangi Tioplico matricai aprašyti pakanka tik jos pirmosios eilutės elementų, tai galima tikėtis, kad specifinei lygčių sistemai spręsti kurios koeficientai prie nežinomųjų sudaro Tioplico matricą, galima surasti efektyvų sprendimo metodo. Levisono-Durbin algoritmas šį teiginį patvirtina.

Kitas Levisono-Durbin algoritmo privalumas yra tai, kad rekurentinių skaičiavimų eigoje mes paeiliui surandame tiesinės prognozės koeficientus eilės M=1, M=2 ir t.t. Koeficientai k_i turi fizikinę interpretaciją ir yra vadinami atspindžio koeficientais. Atspindžio koeficientų modulis turi neviršyti 1; jei skaičiavimų eigoje gavote k_i reikšmes nepatenkančias į intervalą [-1;1], tai arba tai atsitiko dėl skaičiavimo paklaidų arba formulės pagal kurias skaičiavote autokoreliacijos koeficientus R_m davė fizikine prasme blogą rezultatą.

Praktiniai patarimai

Kokias N ir M reikšmes pasirinkti?
Laikantis taisyklės, kad vienos sekundės trukmės kalbos signalas būtų skaidomas į 30-50 langų, gauname, jog N reikšmė priklauso nuo signalo imčių dažnio FS (FrequencySampling - kiek kartų per sekundę įrašoma garso slėgio reikšmių). Tipinės FS reikšmės yra

• FS=8192 - žema kokybė;
• FS=11025 - telefoninė kokybė;
  
• FS=22050 - radijo kokybė;
  
• FS=44100 - kompaktinių diskų kokybė;
  (44100 = 2²3²5²7⁷)

Tarkime FS=22050. Tuomet galima pasirinkti N=FS/30=735 ar N=FS/50=441. Tačiau praktiškai geriau imti N sveikąjį dvejeto laipsnį, kad būtų naudotis greitais koreliacijos apskaičiavimo algoritmais. Šiuo atveju būtų tikslinga imti N=512.

Plokštumos taškų atveju reikėtų kontūrą suskaidyti į atskiras dalis, pvz. grupes atskirti kampiniais ar kitais ypatingais kontūro taškais, ir aproksimuojant kiekvienos grupės taškus naudoti neaukštos eilės (M=2-4) tiesinės prognozės modelį. LPC metodas yra pagrindinė efektyvi kalbos signalų kompresijos priemonė. Plačiau apie šį metodą galima paskaityti nurodytoje literatūroje.

LPC kodavimo/dekodavimo schema

Koeficientų kodavimas

LSP (Line Spectral Pairs) - spektrinės poros tiesėje

Sintezė

CELP (Code Excited Linear Prediction ) koderis

MPE-LPC koderis

LPC Java kodas

LPC klasės aprašymas

Praktinė užduotis

Literatūra

1. 1015 standartas atspausdintas 1984.
   
2. 1016 standartas atspausdintas 1991.
   

   LPC10e ir CELP programų kodai prieinami ftp://ftp.super.org/pub/speech/.

3. comp.speech FAQ aprašyti kitų algoritmų standartai.

4. Digital Processing of Speech Signals.
   L. R. Rabiner and R. W. Schafer.
   Prentice-Hall (Signal Processing Series), 1978.

5. "The Government Standard Linear Predictive Coding Algorithm: LPC-10"
   Thomas E. Tremain.
   Speech Technology Magazine, April 1982, p. 40-49.

6. "The Proposed Federal Standard 1016 4800 bps Voice Coder: CELP"
   Joseph P. Campbell Jr., Thomas E. Tremain and Vanoy C. Welch.
   Speech Technology Magazine, April/May 1990, p. 58-64.

7. Speech Analysis, Tony Robinson

8. Adio compression & coding, Dan Ellis

9. Warped Linear Predictive Coding, Aki Harma & Unto K. Line

2004 m. kovo 22 d.