Na podlagi transformacij DFT, Walsh-Hadamard in Haar je mogoče konstruirati številne druge transformacije ortogonalne transformacije. Določimo jih lahko z uporabo Kroneckerjevega produkta ali kot vsoto Kroneckerjevih produktov. Na primer, predlagana je hibridna Hadamard-Haarjeva transformacija, katere matrika je velikosti velikosti, ki je definirana kot
Prispevek podaja rekurzivno definicijo ti modificirane Hadamardove transformacije
in prikazana je njegova povezava s Haarjevo transformacijo.
Upoštevamo matriko tako imenovane posplošene Walsheve transformacije reda dimenzije (transformacija z Vilenkin-Chrestensonovimi funkcijami), definirano kot Kroneckerjeva potenca matrike
Delo opisuje tako imenovano -transformacijo, ki je zgrajena na podlagi Walsh-Hadamardove transformacije z zamenjavo vsake vsote v izrazu (3.114) z njeno absolutno vrednostjo. Ta preobrazba je nepovratna.
Omeniti velja tudi poševno transformacijo, poševno-Haarjevo transformacijo in diskretno bazno transformacijo, predlagano za kodiranje slike.
Lahko se pokaže, da je večino enotnih transformacij, ki se trenutno uporabljajo pri obdelavi slik, mogoče predstaviti kot vsote Kroneckerjevih produktov elementarnih matrik, permutacijskih matrik in nekaterih drugih. Ta predstavitev matrik Haar, Hadamard, Walsh, Walsh-Paley, modificirana matrika Hadamard, matrika Hadamard-Haar, matrika DFT, posplošena matrika Walsh je prikazana v tabeli. 3.5 z naslednjim zapisom:
Razsežna permutacijska matrika, pri kateri so njeni elementi pomnoženi z vektorjem prerazporejeni v skladu z binarno invertirano kodo njihovega števila; - dimenzijska permutacijska matrika, ki izvaja permutacijo vektorskih elementov v skladu z inverzno Grayovo kodo njihovih števil; - Kroneckerjev produkt matrik; Kroneckerjeva moč matrice.
(glej skeniranje)
Nadaljevanje tabele. 3.5 (glej skeniranje)
Ta predstavitev zagotavlja priročno osnovo za primerjavo transformacij. Ko primerjamo predstavitve za matriko, lahko »opazimo, da se razlikujejo v obratnem vrstnem redu matrik v vsakem členu; matrika MHAD se razlikuje od Hadamardove matrike HAD po tem, da ni zgrajena
In naprej itd. Za vse te matrike obstajajo hitri algoritmi za njihovo množenje z vektorjem pri izvajanju transformacije. To dejstvo je najbolj neposredno povezano z možnostjo predstavitve matrik v obliki vsot Kroneckerjevih matrik (glej 4. poglavje).
Na podlagi opisanih enodimenzionalnih transformacij lahko ustrezne dvodimenzionalne ločljive transformacije konstruiramo kot dvojne enodimenzionalne:
kjer je M ena od zgoraj opisanih transformacijskih matrik; a - dvodimenzionalni diskretni signal; a je njegova transformacija.
Upoštevajte, da so vse enotne transformacije slike, ki se trenutno uporabljajo v digitalni obdelavi slik, ločljive, tj. izvajajo se ločeno vzdolž stolpcev in vrstic dvodimenzionalnega signala. To zmanjša število operacij, potrebnih za njihovo dokončanje. Ločljive transformacije je mogoče sestaviti tudi z izbiro različnih matrik za transformacije vzdolž vrstic in stolpcev:
Tako se izkaže mešane transformacije, ki se uporablja v specializiranih napravah za kodiranje digitalnih slik (glejte na primer).
Uporabe enotnih transformacij pri obdelavi slik lahko razdelimo v tri skupine:
Kodiranje slik;
Ekstrakcija funkcij za pripravo in prepoznavanje slike;
Generalizirano filtriranje.
Kodiranje slik je trenutno glavna uporaba transformacij (razen DFT). Poleg tega so bile nekatere transformacije (na primer poševna transformacija in diskretna linearna bazična transformacija itd.) uvedene posebej za uporabo pri kodiranju.
Koeficiente predstavitve signala, dobljene kot rezultat njegove transformacije, je mogoče obravnavati kot njegove znake in uporabiti pri pripravi slike (glej II. del, 7. poglavje) in za prepoznavanje. Primer transformacije, izumljene posebej za označevanje funkcij med prepoznavanjem, je -transformacija. Uporabi transformacij za kodiranje in prepoznavanje sta povezani. Praviloma so transformacije, ki dajejo boljše rezultate za kodiranje, boljše tudi za ekstrakcijo funkcij.
Uporaba enotnih transformacij za filtriranje signalov temelji na posplošitvi koncepta filtriranja v frekvenčni domeni diskretna transformacija Fourier. Pri filtriranju signalov z uporabo DFT se izvede naslednja transformacija signala:
Prehodne matrike iz T transformacije v DFT in obratno.
Ta pristop je bil predlagan za posplošitev optimalnega linearnega (Wienerjevega) filtriranja (glejte tudi).
Odvisno od vrste transformacije T in lastnosti zahtevanega filtra se lahko kompleksnost izvajanja operacije filtracije (3.139), ocenjena, recimo, s številom operacij, spreminja. Zlasti se lahko izkaže, da je bolj donosno uporabiti hitrejšo Walsh-Hadamardovo transformacijo namesto DFT, kljub večji zapletenosti množenja z nediagonalno matriko filtrov v tem primeru (glej tudi § 6.5).
Eno najpogostejših načinov obdelave tako enodimenzionalnih kot večdimenzionalnih signalov, vključno s slikami, so ortogonalne transformacije. Vloga ortogonalnih transformacij je še posebej velika pri reševanju problema zmanjševanja hitrosti prenosa binarnih simbolov v digitalni televiziji in posledično zmanjšanja zahtevanega frekvenčnega pasu komunikacijskih kanalov. Bistvo ortogonalnih transformacij je predstaviti izvirni signal kot vsoto ortogonalnih baznih funkcij.
Spomnimo se, da se funkciji x(t) in y(t) imenujeta pravokotni na segmentu (t 1, t 2), če je njun skalarni produkt enak nič
To definicijo je mogoče razširiti na diskretne signale, ki jih predstavljajo zaporedja številk. Diskretna signala x(n) in y(n), ki imata po N vzorcev, se imenujeta ortogonalna, če je pogoj izpolnjen
Eden najbolj slavni primeri Uporaba ortogonalne transformacije je razširitev periodičnega signala x v Fourierjev niz
Kje: ; T - perioda ponavljanja signala x(t).
Realni koeficienti Fourierove vrste so določeni z razmerji
V kompleksni obliki ima razširitev Fourierjeve vrste obliko:
kompleksne harmonične amplitude;
j je imaginarna enota.
Ne le periodični signal s periodo T je mogoče razširiti v Fourierjev niz, ampak tudi signal, ki se razlikuje od 0 samo v časovnem intervalu (-T/2, T/2). V tem primeru se uporablja periodično nadaljevanje signala vzdolž celotne časovne osi s periodo T.
Oglejmo si diskretni signal x(n), ki je drugačen od 0 za n = 0,1, ..., N-1. Za takšen signal je mogoče uvesti tudi bazno razširitev sinusnih funkcij. Ker mora biti frekvenčni spekter vzorčenega signala omejen od zgoraj v skladu s pogojem Kotelnikovega izreka, je končno število frekvenčnih komponent, ki ostanejo pri razgradnji diskretnega signala, diskretne kompleksne harmonične funkcije. Ta razširitev, imenovana diskretna Fourierjeva transformacija (DFT), ima obliko
N=0, 1...N-1,(2,6)
kjer so koeficienti DFT X(k) določeni z razmerjem
K=0, 1...N-1,(2,7)
Spomnimo se, da se običajno imenuje iskanje koeficientov X(k) iz (2.7). neposredni DFT, pridobivanje signala iz teh koeficientov v skladu z (2.6) pa je inverzni DFT.
V teh relacijah so se namesto integralov pojavile vsote, saj izvorni signal ni zvezen, temveč diskreten. Pogostost, uporabljena pri razgradnji analogni signali in ima dimenzijo rad/s, v DFT ustreza brezdimenzijski količini, kjer je k=0, 1…N-1. Razmerje kaže, kolikšen del frekvence vzorčenja je frekvenca danega diskretnega harmonika.
DFT koeficienti Х(k) in eksponentni faktorji v (2.6), (2.7) so kompleksna števila. Vsako kompleksno število je shranjeno v digitalnem pomnilniku kot par realnih števil, ki predstavljata njegov realni in imaginarni del. Seštevanje dveh kompleksnih števil zahteva izvedbo dveh operacij seštevanja realnih števil - realni in imaginarni del se seštevata ločeno. Množenje dveh kompleksnih števil zahteva štiri operacije množenja in dve operaciji seštevanja za realna števila. Tako izvajanje DFT v kompleksni obliki povzroči znatno povečanje potrebnega obsega pomnilnika in časa izračuna.
Ukvarjati se samo z realna števila običajno uporabljajo razgradnjo z diskretno kosinusno transformacijo (DCT), ki jo opisuje relacija:
kjer so koeficienti denarne politike določeni s formulami
Tako kot v primeru DFT se iskanje koeficientov C(k) po (2.9) imenuje direktni DCT, predstavitev signala v obliki (2.8) pa inverzni DCT.
Podobno lahko zapišemo relacije za direktni in inverzni DFT in DCT dvodimenzionalni primer. Dvodimenzionalni diskretni signal, na primer en okvir digitalnega televizijskega signala, je predstavljen z matriko vrednosti x(t,n), kjer je t = 0 ... M-1 - številka vzorca v vrstica, n = 0 .., N-1 - številka vrstice v okvirju.
Neposredni dvodimenzionalni DFT ima obliko:
k=0…M-1, l=0…N-1,
kjer so X(k,l) kompleksni koeficienti DFT, ki odražajo prostorsko-frekvenčni spekter slike.
Inverzni dvodimenzionalni DFT predstavlja razgradnjo slike na osnovne funkcije:
Koeficienti dvodimenzionalne neposredne monetarne politike so določeni s formulami:
Inverzni dvodimenzionalni DCT ima obliko:
Količine in so diskretne prostorske frekvence vzdolž vodoravnih oziroma navpičnih koordinat, ki so izražene kot brezdimenzijske količine, ki imajo enak pomen kot diskretna frekvenca v enodimenzionalnem primeru. Vsaka diskretna prostorska frekvenca je sorazmerna z razmerjem med prostorsko periodo vzorčenja na dani koordinati in prostorsko periodo te frekvenčne komponente. Prostorska obdobja se merijo v enotah razdalje.
Na sl. 2.3 prikazuje osnovne funkcije dvodimenzionalnega DCT za M = 8, N = 8 v obliki poltonskih slik. Svetla področja ustrezajo pozitivnim vrednostim, temna območja pa negativnim.
riž. 2.3.
Prikazani primeri:
- a) k = 1, l = 0; b) k = 0, l = 1; c) k = 1, l = 1;
- d) k = 0, l = 2; e) k = 1, l = 2; e) k = 2,l = 2;
- g) k = 4, l = 2; h) k = 7, l = 1; i) k = 7, l = 7.
Izjemna lastnost razgradnje video signala v osnovi DCT je, da vsaka osnovna funkcija vsebuje informacije o celotni sliki hkrati. Število osnovnih funkcij, uporabljenih za razgradnjo video signala, določa natančnost predstavitve slike.
V skladu z , je na splošno mogoče oceniti stroške računalniških virov pri izvajanju naprej in inverznega DFT kot sorazmerno z N 2 . Podobno se lahko pokaže, da izračun dvodimenzionalnih prednjih in inverznih DFT zahteva številne operacije, sorazmerne z N 2 M 2.
Na primer, izračun DFT za blok kvadratne slike, ki vsebuje 8x8 elementov (pikslov), bo zahteval približno 16 10 3 operacij množenja in seštevanja. In izračun DFT črno-belega televizijskega okvirja običajnega standarda razgradnje, ki vsebuje 720x576 slikovnih pik, bo zahteval približno 8·10 11 operacij. Če se izračuni izvajajo na računalniku, ki izvaja 10 6 operacij na realnih številih na sekundo, bo čas izračuna DFT 8 10 5 s ali več kot 200 ur za izračun DFT televizijskih slik v realnem času, tj. med obdobjem skeniranja okvirja je treba iskati načine za zmanjšanje števila potrebnih operacij.
Najbolj radikalen način za zmanjšanje količine računanja je uporaba hitrih algoritmov DFT, ki so bili odkriti v 60-ih, imenovanih algoritmi za hitro Fourierjevo transformacijo (FFT). Hitri algoritmi za izračun DFT so podrobno opisani v številnih virih literature in tukaj niso obravnavani.
Dvodimenzionalno FFT je mogoče razstaviti na zaporedje enodimenzionalnih. Število potrebnih operacij se izkaže za sorazmerno. Za zgornji primer televizijskega okvirja, sestavljenega iz 720 x 576 slikovnih pik, se izkaže, da je ta vrednost približno 8 10 6, kar je 10 5-krat manj od števila operacij, potrebnih za neposredni izračun DFT.
Obstajajo tudi hitri algoritmi za izračun denarne politike. Kot bo razvidno iz nadaljevanja, ima pri digitalni televiziji glavno vlogo DCT blokov pikslov 8x8, ki uporablja algoritem za hiter izračun enodimenzionalnega DCT segmenta digitalnega signala, ki vsebuje osem elementov. V tem primeru se DCT najprej izračuna za vsak stolpec bloka slikovnih elementov, nato pa se DCT izračuna za vsako vrstico v dobljeni matriki števil 8x8.
V sodobni opremi, vključno z digitalno televizijo, se DFT in DCT običajno izvajata v realnem času z uporabo digitalnih signalnih procesorjev (DSP) ali posebne strojne opreme, na primer vzporednih računalniških naprav.
DCT je osnova trenutno najpogosteje uporabljenih metod kodiranja JPEG, MPEG-1, MPEG-2, katerih opis bo podan v razdelku 2.2.
Algoritmi za stiskanje digitalne slike z ortogonalnimi transformacijami
Kot rokopis
Umnjaškin Sergej Vladimirovič
UDK 004.932: 004.421: 519.722
Matematične metode in digitalni algoritmi
uporabo kompresije slike
ortogonalne transformacije
Posebnost 05.13.11 - »Matematika in programska oprema računalniki, kompleksi in računalniška omrežja”
Moskva – 2001 2
Delo je bilo opravljeno na Moskovskem državnem inštitutu za elektronsko tehnologijo (tehnična univerza)
Znanstveni svetovalec: doktor fizikalnih in matematičnih znanosti, profesor Pospelov A.S.
Uradni nasprotniki:
Doktor fizikalnih in matematičnih znanosti, profesor Ososkov G.A.
Doktor fizikalnih in matematičnih znanosti, profesor Selishchev S.V.
Doktor tehničnih znanosti, profesor Koekin A.I.
Vodilna organizacija: Zvezni državni enotni podjetniški raziskovalni inštitut Radio (Moskva)
Zagovor bo potekal 19. februarja 2002 ob 14.30 na seji disertacijskega sveta D.212.134.02 na Moskovskem državnem inštitutu za elektronsko tehnologijo na naslovu: 103498, Moskva, Zelenograd, MIET (TU).
Diplomsko delo je na voljo v knjižnici MIET (TU).
Znanstveni tajnik disertacije /Vorobiev N.V./ prof
Splošne značilnosti dela
Ustreznost teme. Shranjevanje in prenos slik z neposredno digitalno predstavitvijo v obliki matrike slikovnih pik (slikovnih točk) zahteva obdelavo ogromnih količin podatkov.
Vendar je neposredna predstavitev slike neučinkovita: zaradi znatne korelacije matričnih elementov neodvisno kodiranje slikovnih pik ustvari odvečne kode. Zato je med drugimi problemi digitalne obdelave slik še posebej pomemben problem stiskanja slik, ki je sestavljen iz iskanja načinov za učinkovito kodiranje vizualnih podatkov.
Namen dela. Kompleksnost algoritmov, ki se uporabljajo za stiskanje slik, vztrajno narašča - to ne zadeva le obsega izračunov, temveč tudi ideološke temelje za konstrukcijo algoritmov, ki večinoma temeljijo na uporabi diskretnih ortogonalnih transformacij za predprocesiranje podatkov. Hkrati problem kompresije slike predstavlja praksa, ki pri reševanju zahteva stalno pozornost na zmožnosti realne opreme. Namen Delo je vključevalo proučevanje teoretičnih vprašanj učinkovitega kodiranja slike z ortogonalnimi transformacijami ter razvoj ustreznih kompresijskih algoritmov, primernih za praktično uporabo na osnovi univerzalnih računalniških orodij za splošno uporabo.
Smer raziskovanja. Raziskava, opravljena v disertaciji, je vključevala obravnavo naslednjih vprašanj:
1. Raziskovanje in razvoj metod za teoretično analizo in sintezo diskretnih transformacij za korelirane sheme stiskanja podatkov;
2. Razvoj novih hitrih algoritmov za izračun diskretne Chrestenson-Levyjeve transformacije (DCLT) in algoritma za stiskanje poltonske slike na osnovi statističnega kodiranja spektrov DPCL;
3. Študija posebnosti in formalizacija splošne sheme stiskanja z uporabo blokovne obdelave fragmenti slike z ortogonalno transformacijo, ki ji sledi kvantizacija in statistično kodiranje transformacijskih koeficientov;
4. Razvoj algoritmov za stiskanje valovne slike in preučevanje možnosti fraktalnega kodiranja v spektru valčkov;
5. Razvoj algoritma za stiskanje video sekvenc (dinamičnih slik), primernega za uporabo v obliki programske implementacije na osnovi univerzalnih univerzalnih računalniških orodij (multimedijski osebni računalniki).
Raziskovalne metode. Kot glavno teoretično raziskovalno orodje so bile uporabljene metode matematične in funkcionalne analize, linearna algebra, teorija verjetnosti in matematična statistika, teorija informacij. Pomemben del raziskav so predstavljali tudi računalniški eksperimenti obdelave realnih mirujočih in dinamičnih slik, namenjeni pridobivanju potrebnih statističnih podatkov in določanju značilnosti končnih algoritmov stiskanja. Izvedeni poskusi so potrdili točnost teoretične rešitve in učinkovitost predlaganih algoritmov stiskanja.
Znanstvena novost. Kot rezultat disertacije so bile pridobljene nove metode za analizo učinkovitosti ortogonalnih transformacij, namenjenih stiskanju koreliranih podatkov; posebej za stiskanje podatkov je bila uvedena diskretna psevdokozinusna transformacija (DPCT) (konstruirana prvič). Razviti so bili novi hitri algoritmi za izračun DPCL, na podlagi katerih je bila prvič pridobljena kompresijska shema za statične slike, ki ima podobne lastnosti kot metoda JPEG.
Za obdelavo mirujočih in dinamičnih slik so bili predlagani tako novi algoritmi kot splošni teoretični pristopi, ki formalizirajo postopke za analizo in sintezo kompresijskih shem digitalne slike na podlagi diskretnih ortogonalnih transformacij.
Za zagovor disertacije so predloženi naslednji glavni rezultati:
Metoda za ocenjevanje dekorelacijske učinkovitosti ortogonalnih transformacij in na njej zasnovani algoritmi združevanja v gruče za korelirano DPKP ter hiter algoritem za njen izračun;
Nov hitri algoritem DPCL in njegova modifikacija - algoritem z nepopolnim izračunom; algoritem kombiniranih izračunov DPKL za obdelavo realnih nizov v bazi (1,exp(-2i/3));
Metoda stiskanja slike, ki temelji na posebni metodi aritmetičnega kodiranja DPCL spektrov slikovnih blokov;
Deterministični in verjetnostne ocene koeficienti diskretne kosinusne transformacije (DCT);
Algoritem za kontekstualno kodiranje slikovnih spektrov DCT;
Splošna shema kompresije slike na osnovi adaptivne vektorske kvantizacije na področju ortogonalnih transformacij;
Valoviti kompresijski algoritmi za statične slike;
Algoritem za iskanje premaknjenih slikovnih blokov;
Eksperimentalna tehnika za konstruiranje razdelitvenih spektrov v neodvisna področja kodiranja;
Algoritem stiskanja videa.
Praktična vrednost. V splošnem je vsebina dela aplikativna, zato pridobljeni teoretični rezultati služijo tudi doseganju ciljev, povezanih z razvojem specifičnih algoritmov in shem za kompresijo digitalne slike. Uporaba pridobljenih algoritmov za stiskanje slike je možna za širok razred sistemov za shranjevanje in prenos vizualnih informacij, predvsem v multimedijskih in omrežnih računalniških aplikacijah. Razviti algoritmi, kot so potrdili eksperimenti, imajo visoke lastnosti glede hitrosti, kakovosti obdelave in stiskanja podatkov, ki ustrezajo sodobni svetovni ravni.
Implementacija rezultatov dela. Teoretični rezultati dela in algoritmi za stiskanje video slik so bili predstavljeni v Državnem raziskovalno-proizvodnem kompleksu "Tehnološki center" MIET (http://www.tcen.ru) in uporabljeni v znanstvenih in proizvodnih dejavnostih Znanstveno-proizvodnega podjetja "Tehnologija" (Moskva).
Potrditev dela. Glavni rezultati O delu so poročali in razpravljali na naslednjih znanstvenih konferencah in srečanjih:
1. VII Saratovska zimska šola o teoriji funkcij in približkov (SSU, januar 1994).
2. medn. konferenca o teoriji funkcij in aproksimacij, posvečena 90-letnici akad. S. M. Nikolsky (Moskva, MI RAS, maj 1995).
3. Vseslovenske znanstvene in tehnične konference "Elektronika in informatika" (Moskva, MIET, 1995-2000).
4. medn. konferenca o teoriji aproksimacije funkcij, posvečena spominu na prof. P.P. Korovkina (Kaluga, KSPU, 26.-29. junij 1996).
5. Mednarodne konference "Metode za optimizacijo izračunov" (Kijev, 1997, 2001).
6. Mednarodna konferenca “Problemi matematičnega izobraževanja”, posvečena. 75-letnica dopisnega člana. RAS prof. L.D. Kudrjavceva (1998).
7. Mednarodna konferenca "Teorija približevanja in harmonična analiza" (Tula, 26.-29. maj 1998).
8. Mednarodna konferenca "Informacijske tehnologije v inovativnih projektih" (Iževsk, 20.-22. april 1999).
9. VII mednarodna konferenca “Matematika. Gospodarstvo. Ekologija. Izobraževanje” – mednarodni simpozij “Fourierjevi nizi in njihove aplikacije”
(Novorosijsk, 1999).
10. VII mednarodna konferenca “Matematika. Računalnik. izobraževanje"
11. Mednarodna konferenca, posvečena 80. obletnici rojstva S.B. Stečkina (Ekaterinburg, 28. februar - 3. marec 2000).
Publikacije. Glavna vsebina disertacije se odraža v 30 delih.
Zgradba in obseg disertacije. Diplomsko delo obsega strani (od tega 26 strani prilog) in je sestavljeno iz uvoda, šestih poglavij, zaključka in 6 prilog. Bibliografski seznam obsega 178 naslovov. Dodatki zagotavljajo številčni rezultatištevilne poskuse obdelave slik, kot tudi osnovne informacije in kopije dokumentov o uporabi rezultatov disertacije.
V uvodu(28 strani) so utemeljeni relevantnost, znanstvena novost in uporabna vrednost raziskave. Na kratko je povzeta vsebina poglavij.
V prvem poglavju(35 strani) vsebuje predhodne informacije, potrebne za nadaljnjo predstavitev, ponuja kratek pregled in razvrstitev glavnih pristopov k izvajanju učinkovitega kodiranja slike.
Uporaba algoritmov stiskanja z izgubo za poltonske slike je zelo razširjena: če dopustite napako v rekonstruirani sliki, lahko dosežete veliko več visoki ravni stiskanje podatkov. Najpogosteje se kakovost obdelave slike ocenjuje z X = (xi, j) – matrika originalne slike, X = (xi, j) – matrika slike, dobljene po obdelavi (stiskanje in obnovitev podatkov). Za logaritemsko vrednost standardnega odklona se uporablja splošno sprejeta mera PSNR (peak signal to noise ratio). Metode stiskanja slike je priročno obravnavati v obliki splošne sheme, ki je sestavljena iz treh glavnih stopenj: zmanjšanje vmesnega elementa. korelacija podatkov, kvantizacija podatkovnih elementov, statistično kodiranje . Kvantizacija je glavno orodje, ki se uporablja pri stiskanju podatkov z izgubo. V bistvu je kvantizacija ekstrakcija nekega osnovnega dela informacije iz vhodnih podatkov, ko jih je manj. pomemben del pade.
Uporabljata se tako skalarna kot vektorska kvantizacija.
Pretvorba slike v generalizirano spektralno območje z uporabo linearna transformacija F lahko bistveno zmanjša medelementno korelacijo v transformacijski matriki Y=F(X) v primerjavi s korelacijo elementov v diskretni slikovni matriki. Potem postane neodvisno komponentno kodiranje matrike Y namesto matrike X. učinkovito. Podamo lahko tudi energijsko razlago namena uporabe transformacij, ki je v tem razumevanju koncentriranje največjega dela energije prvotnega diskretnega signala (matrike X) v najmanjšem številu spektralnih koeficientov (elementov matrike Y). Obstaja določena povezava med porazdelitvijo energije v posplošenem spektru in dekorelacijskimi lastnostmi transformacij. Preučevanje učinkovitosti dekorelacijskih lastnosti je zato pomembna naloga pri izbiri transformacije za uporabo v shemi stiskanja.
Realne fotografske slike so dvodimenzionalni signali, ki imajo nehomogenosti (lastnosti) v območjih kontur objekta, zato mora biti osnova funkcij, ki se uporabljajo za dekompozicijo, dobro lokalizirana v originalni sliki. Vendar pa je v območjih ozadja sliko mogoče obravnavati kot realizacijo stacionarnega signala, zaradi česar je bolje uporabiti frekvenčno lokalizirano osnovo za razširitev (dobro je znano, da so Fourierjevi koeficienti trigonometrične ekspanzije stacionarnega signala brez korelacije).
Zaradi Heisenbergovega načela negotovosti je nemogoče doseči istočasno visoko ločljivost v frekvenčni in časovni domeni. Rešitev je uporaba funkcionalnih valovnih (burst) baz, ki imajo spremenljivo časovno-frekvenčno ločljivost. Pristopi, ki temeljijo na brizganju, trenutno prevladujejo pri obdelavi fotografij in postopoma nadomeščajo tradicionalno orodje za dekorelacijo, diskretno kosinusno transformacijo.
Prvo poglavje ugotavlja, da se za optimizacijo algoritmov stiskanja podatkov z izgubo pogosto uporablja pristop, ki temelji na minimiziranju Lagrangeove RD funkcije. Naj bo X nek vhodni niz podatkov, ki je kot rezultat postopka stiskanja-obnovitve povezan z izhodnim nizom podatkov enake narave, Y=F(X,u), kjer je u=(u1,... ,un) je množica kontrolnih parametrov stiskanja algoritma F. Upoštevamo elemente X, Y nekega prostora z metriko D(X,Y), množico vseh možne vrednosti krmilni vektor u označimo z U. Problem optimizacije kodiranja je najti takšne parametre u* = u1,..., un algoritma F za dano množico vhodnih podatkov X in največje dovoljene bitne stroške Rb, tako da podatki napaka kodiranja D(X, Y)=D(X,F(X,u)). najmanjša vrednost. To je, kjer je R(X,u) število bitov, potrebnih za kodiranje nabora podatkov X s parametri u.
Iskanje rešitve naloge(1) se v večini primerov zmanjša na okorne numerične postopke iterativne narave. Če omejitev R(X,u)Rb ni podana, je za določitev optimalnih parametrov kodiranja u*, ki ustrezajo rešitvi problema (1) za neko (prej neznano) vrednost Rb, poenostavljena različica minimiziranja Lagrangeovega RD uporablja se funkcija:
kjer je nenegativen parameter, določen od zunaj. Parameter v funkciji J(u) nastavi ravnotežje med kakovostjo in stopnjo stiskanja podatkov. Vrednost =0 ustreza najmanjši napaki kodiranja, z večanjem vrednosti dobimo pri optimizaciji parametrov algoritma F po (2) manjšo dolžino kode, a večjo napako. Tako lahko algoritem kodiranja F prilagodite zahtevanim karakteristikam. Da bi našli rešitev problema (1), se minimizacija (2) ponovi iterativno, z različne pomene– ta postopek se imenuje optimizacija RD1.
V prvem poglavju so na kratko opisane tudi funkcije, povezane z obdelavo (stiskanje-obnavljanje) dinamičnih slik. Glavna transformacija, ki se uporablja za video kompresijo, je še vedno DCT, saj je enostavnejša v smislu količine izračunov v primerjavi z valovnimi transformacijami.
Tako kot pri statičnem stiskanju so tudi algoritmi za kodiranje videa pogosto bolj zapleteni kot algoritmi za dekodiranje.
Implementacija programske kompresije videa v realnem času, Berger T. Rate Distortion Theory. – Endlewood Cliffs, NJ: Prentice Hall, 1971.
Tako nalaga precejšnje omejitve glede dovoljene kompleksnosti izračunov.
Drugo poglavje(52 strani) je namenjen študiju učinkovitosti in sintezi ortogonalnih transformacij, namenjenih uporabi pri stiskanju podatkov. Predlagana nova metoda za analizo učinkovitosti temelji na naslednjem sklepanju. Naj bo znana kovariančna matrika KX izvornega podatkovnega vektorja X = (x0, x1,..., x N 1)T, dobimo vektorski spekter Y kot rezultat neke ortogonalne transformacije z matriko W: Y= WX.
Povprečno brezpogojno entropijo koeficienta vektorskega spektra lahko zapišemo kot:
kjer je fk(mk,k,x) funkcija gostote verjetnosti za spektralno karakteristiko yk (k-ta komponenta vektorja Y), mk – matematično pričakovanje, k – standardni odklon, f k0 (x) = f k (0,1, x). Nižja kot je povprečna entropija (3), bolj učinkovito bo naknadno neodvisno kodiranje komponent spektra. Po uvedbi omejitve, da je za razred to za optimalno Karhunen-Loeve transformacijo (ko je matrika W=Wopt sestavljena iz lastni vektorji KX in matrika KY=WKXWT ima diagonalno obliko N 1 N končna oblika) dekorelacijske učinkovitosti, bomo upoštevali vrednost povprečne presežne entropije H (W, K X) = H cp (W, K X) H cp (Wopt , K X), ki je izražen preko elementov matrik K X = (cov(xi, x j))i, j = 0 in W = (wi, j)i, j =0, kot sledi:
Večja kot je vrednost H(W,KX), manjša je učinkovitost dekorelacijske transformacije z matriko W. Numerični izračuni vrednosti (4) za različne transformacije in vrste kovariančnih matrik so pokazali rezultate, ki so popolnoma skladni z znanimi podatki. pridobljeni z drugimi metodami, na primer po Pearlu (Pearl J. O kodiranju in filtriranju stacionarnih signalov z diskretnimi Fourierjevimi transformacijami // IEEE Trans. Inf. Theory. - 1973. - Vol. ITP. 229-232.).
Za analizo je zelo zanimiv model diskretnega signala (vektor X), ki ima statistiko diskretnosti Markov proces prvega reda, ko ima kovariančna matrika naslednjo obliko:
Ta model se pogosto uporablja za opis korelacije med vrsticami in stolpci v diskretnih slikah. Pri =1, ko so vse komponente v izvirnem vektorju X enake (za katera koli dva vzorca vektorja je korelacijski koeficient enako ena), je izračun vpeljanega kriterija (4) za matriko (5) nemogoč, ker v tem primeru imamo det K X = 0. Hkrati pa v ozadju slike 1. V 2. poglavju je bil dokazan naslednji izrek.
Izrek 2.1. Za kogarkoli pravokotna matrika W (NN), tako da je j = 0,1,... N 1: w0, j = (bazisna funkcija z ničelnim indeksom je normalizirana konstantna komponenta) in kovariančna matrika (5) Različne študije, vključno s tistimi, izvedenimi v 2. poglavju , kažejo, da so med diskretnimi transformacijami, ki imajo hitre računalniške algoritme (za dimenzijo N, implementirano v ~NlogN aritmetičnih operacijah), dekorelacijske značilnosti za Markovljev proces (5), ki so najbližje optimalni transformaciji Karhunen-Loeve, pridobljene z uporabo DCT.
Kljub razpoložljivosti dobro razvitih hitrih algoritmov za izračun DCT v bistvu zahteva operacije množenja za njegovo izvajanje in je opazno slabši glede obsega izračunov, na primer s transformacijami Haar, Walsh in Chrestenson-Levy. Ločeno vprašanje, ki mu je v 2. poglavju namenjeno veliko pozornosti, je konstrukcija nove transformacije, ki ima visoke dekorelacijske značilnosti za model (5) in računske algoritme, ki so veliko hitrejši kot za DCT. Nastala diskretna psevdokozinusna transformacija je definirana za vektorje dimenzije N, ki omogoča razširitev N=N1…Nn, s k Nk(2,3,4). Predstavitev N=N1…Nn je treba zapisati z najmanjšim številom faktorjev Nk, ki jih razporedimo brez zmanjševanja, tj. k, m>k: NkNm. Na primer, za N=8 imamo N1=2, N2=4 (vendar ne N1=4, N2=2 in ne N1=N2=N2=2). Nato je matrika DPKP WN (v tem primeru indeks označuje dimenzijo transformacije) konstruirana kot neposredni produkt2 WN = WN 1 ... WN n elementarnih matrik DPKP WN k (W2,W3,W4), k=1 ,...,n, kjer sta elementarni matriki pravokotni pod tenzorskim (direktnim) produktom matrik D=(dl,m) (l=0,…,-1; m=0,…,-1) in in sta dobljeno kot rezultat določenih modifikacij iz matrik DCT ustrezne dimenzije. Elementarne matrike lahko predstavimo kot zmnožek določene diagonalne matrike D z matriko C, struktura C pa omogoča, da se množenje s poljubnim vektorjem U izvaja samo z uporabo operacij seštevanja in odštevanja števil (množenje z 2 je enakovredno seštevanju , 2x=x+x). Točno:
Iz lastnosti tenzorskega produkta sledi predstavitev WN = D N C N, C N = C N 1 ... C N n. Matrike C2, C3, C4, D2, D3, D4 so podane zgoraj. Tako je izvedba DPKP Y = WN X = D N C N X sestavljena iz izvajanja množenja matrike CN z vektorjem, Y = C N X, in kasnejše normalizacije nastalega vektorja Y, Y = D N Y. Za izračun DPKP, priročno je uporabljati hitre algoritme, ki temeljijo na faktorizirani predstavitvi za matrike3:
enotska matrika dimenzije N j N j. Ker so matrike TN j) na določen način sestavljene iz redkih blokov matrik C N j, se tudi množenje matrike TN j) z vektorjem zmanjša le na operaciji seštevanja in odštevanja števil. Hitri algoritmi povratni DPCP so zgrajeni na podoben način, ker zaradi opT) () Upoštevajte, da normalizacija (množenje z matriko DN), ki je potrebna pri izračunu DPKP in inverznega DPKP za kompresijsko shemo s skalarno kvantizacijo transformacijskih koeficientov, ne povzroča nobenih zapletov pri izračunih.
Normalizacijo je mogoče kombinirati med stiskanjem podatkov s stopnjo skalarja, imenovano vektor Y posameznega koraka kvantizacije qj=q/djj (kjer je d jj element diagonalne normalizacijske matrike D N). Pri dekvantizaciji y j = m~ j je treba množitelj za element y j izbrati v obliki mj=qdjj.
Kot kažejo izračuni povprečne presežne entropije (4) in rezidualne korelacije po Pearlu, je za podatke s statistiko Markovovega procesa prvega reda (5) DPKP bolj učinkovit pri dekorelaciji v primerjavi z drugimi hitrimi transformacijami, katerih izvajanje tudi zmanjša samo za operacije seštevanja in odštevanja števil.
Tretje poglavje(48 strani) je posvečen študiju uporabe diskretne Chrestenson-Levyjeve transformacije (DCLT) za stiskanje slike in je razvoj raziskave avtorjevega doktorskega dela.
Za utemeljitev te ideje glej str. 84-85 iz monografije »Abstract algebrski sistemi in digitalna obdelava signalov” / Varichenko L.V., Labunets V.G., Rakov M.A. - Kijev: Naukova Dumka, 1986. - 248 str.
Zamisel za algoritem stiskanja, predlagan v 5. poglavju, temelji na delu Lewis-Knowles6 (LK) in Xiong-Ramchandran-Orchard7 (XRO). Ko je kodirano Lewis A.S., Knowles G. Stiskanje slike z uporabo 2-D Wavelet Transform // IEEE Trans.
Image Proc. – 1992. – Letn. 1. - št. 2. – Str.244-250.
Pri razvoju topologije S v XRO je bil uporabljen binarni zemljevid (ni) za vsa drevesna vozlišča razen za liste: če je ni=0, je drevo v tem vozlišču obrezano, in če ni=1, so vsaj neposredni potomci ohranjena. To je prikazano na sl. 2A. Kodiranje statističnih značilnosti (ni) se ne uporablja v algoritmu XRO. Hkrati so atributi (ni) sosednjih (po položaju v podpasu) vozlišč korelirane količine. Da bi upoštevali to korelacijo, je v razvitem algoritmu predlagano, da značilnosti za sosednja vozlišča (ni )iC j združimo v en element podatkov, tako da je zemljevid obrezovanja (topologija drevesa) opisan z novo podatkovno abecedo s simboli Ni=(ni1,ni2,ni3,ni4)=ni1+2ni2+4ni3+8ni4, ki so tudi statistično kodirani. Izkazalo se je, da je nova razširjena funkcija Nj povezana z vozliščem j višje ravni, glej sl. 2B.
Obrezovanje vej Slika 2. Metoda obrezovanja vej pri ogledu vozlišč plast za plastjo: A – algoritem XRO, B – kodiranje predlagane topologije. Ci=(i1,i2,i3,i4) Ideja, ki sega v delo LK in se v enaki obliki uporablja v XRO, je naslednja: večja kot je absolutna vrednost valovnega koeficienta wi (ali energije, wi2) nadrejenega vozlišča i, manjša je verjetnost, da se bo na tem vozlišču pojavila ničelna (tj. obrezana) veja. Natančnejšo napoved pojava ničelne veje je mogoče narediti z uporabo Xiong Z., Ramchandran K. in Orchard M.T. Prostorsko-frekvenčna kvantizacija za valovito kodiranje slik // IEEE Trans. Image Proc. – V.6 – maj 1997, str. 677-693.
napovedane vrednosti Pi je vsota, ki vključuje poleg wi2 tudi kvadrate vrednosti v vozlišču i. Za predvideno vrednost vozlišča i je predlagana uporaba naslednje količine absolutne vrednosti valovni koeficienti:
kjer so nizi za indekse seštevanja določeni med sosedi vozlišča i v podpasu v skladu s sl. 3. Utežni koeficienti, vključeni v vsoto, so bili pridobljeni kot rezultat statistične obdelave številnih testnih slik, da bi ugotovili največjo vrednost vzorca za korelacijski koeficient med predvideno vrednostjo (10) in energijo kvantiziranih valičnih koeficientov neposrednih potomcev Ci: Pi, w2 max.
Predlagani algoritem valčkovega stiskanja uporablja več statističnih modelov. Funkcijo aritmetičnega kodirnika, ki z uporabo notranjih statističnih modelov oceni število bitov, potrebnih za kodiranje simbola c v k-tem toku, bomo označili s H(k,c). Oznaka Hspec se nanaša na tokove, v katerih so kodirani kvantizirani valični koeficienti, Hmap - na tokove, v katerih so kodirani znaki začetka ničelne veje. Drevesa spektra se obdelujejo zaporedno; Po optimizaciji topologije naslednjega drevesa ga je treba kodirati in s tem prilagoditi statistične modele aritmetičnega kodirnika.
Korak 0. /* inicializacija */ i Ln1: /* ogledana so vsa vozlišča predzadnje ravni */ /* prilagoditev kvantiziranih koeficientov */ /* izračun funkcij RD za shranjevanje in obrezovanje listov */ Korak 2. i Ll: /* ogled trenutne ravni s poskusom obrezovanja vej */ Če i0 potem /* niso dosegli začetka drevesa */ /* določanje optimalne topologije vej */ /* prilagajanje kvantiziranih koeficientov */ /* priprava na ogled naslednje stopnje */ drugače /* i=0, dosežen začetno drevo */ /* določanje optimalne topologije drevesa */ Korak 3. /* generiranje in prikaz rezultata */ Konec Vozlišča drevesa so prikazana iz listi do korenine. V prvem (pripravljalnem) koraku se pregledajo tista vozlišča i, ki imajo samo neposredne potomce (Ci=Ui), iz vrednosti funkcij RD, ki ustrezajo možnostima rezanja (J U i) in ohranjanja (J U), se oblikujejo nizi. i) listi. Predhodno, v koraku 1.1, je za vsako listno vozlišče analizirana možnost dodatne Lagrangeove minimizacije, ki označuje skalarno kvantizacijo koeficientov valčkov. Ta postopek temelji na znanih lastnostih verjetnostne porazdelitve valičnih koeficientov, po katerih so bitni stroški R za kodiranje koeficienta a priori manjši, čim manjša je njegova absolutna vrednost (zaradi tega je za primer w = 0, dodatni postopek minimizacije ni uporabljen). V drugem koraku, ki se izvede za vsa vozlišča i naslednjih nivojev, iLl (l=n-2,...,0), se izbere RD-optimalen način obrezovanja vej (koraki 2.1-2.2) začenši z vozlišča jCi. Koraka 2.3 in 2. imata enak pomen kot koraka 1.1, 1.2. Upoštevajte, da uvedba dodatne optimizacije skalarne kvantizacije (koraka 1.1 in 2.3) omogoča, da pri isti stopnji stiskanja dodatno povečate PSNR za 0,02–0,03 dB.
Za vsa vozlišča, razen za korensko, se izbira modela za kodiranje značilnosti Ni (v koraku 2.1) izvede s pomočjo pravila, ki ga definira funkcija IndMap(i). Za kodiranje funkcije N0, povezane s korenom drevesa, se uporablja ločen podatkovni tok, ki mu je običajno dodeljena številka 0 (glejte korak 2.6).
Kot izhaja iz zgornjega opisa optimizacijskega algoritma, življenjsko pomembno vlogo pri njegovem delu imata vlogo funkciji IndMap(Pi) in IndSpec(i), ki določata pravila za izbiro tokov za kodiranje podatkov. Prva funkcija izbere model kodiranja funkcij Ni=(ni1,ni2,ni3,ni4) na podlagi povprečne vrednosti predvidenih vrednosti Pi (10), i=i1,i2,i3,i4, in ima naslednjo obliko :
Pragovi (t1,t2,t3)=(0,3;1,1;4,0) za izbiro modelov so bili ugotovljeni kot rezultat minimiziranja dolžine izhodne bitne kode R(t1,t2,t3) pri obdelavi dobro znanih testnih slik Lena, Barbara, Goldhill. Eksperimenti so tudi pokazali, da uvajanje večjega števila modelov za lastnosti ni smiselno.
Druga ključna funkcija algoritma stiskanja valčkov, IndSpec(i), je pravilo izbire modela za kodiranje koeficientov valčkov, ki ne spadajo v ničelne veje. Za kodiranje spektralnih koeficientov je učinkoviteje uporabiti napovedno vrednost, pridobljeno ne le iz nadrejenega vozlišča, ampak tudi iz koeficientov valčkov vozlišč, ki so v istem podpasu, poleg tistega, ki se obdeluje8. V obravnavanem algoritmu je zaporedje kodiranja in dekodiranja vozlišč valčkovega spektra določeno z diagramom na sliki 4 (številke označujejo vrstni red obdelave podpasov). Za uporabo v funkciji IndSpec(j) se predvidena vrednost trenutnega vozlišča j (označeno s črno) oblikuje s j = 0,36 Pi + 1,06 w j y + w jx + 0,4 w jd, kjer je jy navpično sosednje vozlišče, jx je ideja o uporabi konteksta koeficientov sosednjih valčkov je bila predlagana v delu Chrysafis S., Ortega A. Efficient Context-Based Entropy Coding for Lossy Wavelet Image Compression // Proc. Konferenca o stiskanju podatkov. – Snowbird (Utah), 1997. – Str. 241-250.
horizontalno sosednje vozlišče, jd – diagonalno sosednje vozlišče (ki sta bila že obdelana, glej sliko 4), Pi je določen za nadrejeno vozlišče i (jCi) z (10). V tem primeru so rezultati obdelave testnih slik.
Ničelni model se nanaša na kodiranje spektralnih koeficientov pod skalirnimi funkcijami in je ponovno izoliran. Prvi model vključuje najnižje frekvenčne valovne koeficiente (nivo L1) ter koeficiente, za katere je napoved sj največja.
Značilnosti, podane v tabeli. 1. Vrednost PSNR (v dB), v skladu s predlaganim algoritmom stiskanja, dobljena pri stiskanju testnih slik za standardne testne slike v skladu s predlaganim algoritmom, je podana v tabeli. 1. V poskusih je Lena Barbara Goldhill uporabila petstopenjske valovne transformacije iz dela Wei D., Pai H.-T. in Bovik A. C., Antisymmetric Biorthogonal Coiflets for Image Coding // Proc. Mednarodna konferenca IEEE o Obdelava slik. – Chicago, 1998. – V. 2. – Str. 282-286. Primerjava dosežene lastnosti z rezultati uporabe drugih znanih algoritmov kaže, da ima predlagani algoritem zelo visoko zmogljivost.
Končne študije 5. poglavja se nanašajo na konstrukcijo hibridne kodirne sheme za valovni spekter, ko je poleg zgoraj opisane metode obrezovanja vej valičnih koeficientov dovoljena tudi možnost vektorske »samokvantizacije« vej. , kar je mogoče razlagati kot fraktalno kodiranje na področju valovnih transformacij9. Nastali hibridni algoritem zahteva bistveno več računanja, vendar se je izkazalo, da je fraktalna komponenta kodiranja skoraj popolnoma potlačena z osnovno shemo stiskanja v valovih, ki temelji na obrezovanju vej. Treba pa je poudariti, da je bila kombinacija obeh pristopov v hibridnem algoritmu izvedena na preprost način, možnosti za nadaljnji razvoj pa puščajo tukaj ogromno raziskovalnega polja.
Šesto poglavje (45 strani) je namenjeno proučevanju algoritmov dinamične kompresije slike z namenom izdelave sheme kompresije videa, primerne za programsko implementacijo, ki omogoča procesiranje v realnem času na osebnih računalnikih.
Okvir video zaporedja je matrika slikovnih pik, sestavljena iz M1 vrstic in M2 stolpcev: B=(bk,l), k=0,1,…,M1-1, l=0,1,…,M2-1, in z video sekvenco mislimo na urejen niz okvirjev B0,B1,…,Bi,…. Imenujmo (y,x)-blok okvirja B (y, x – cele koordinate) neko podmatriko By,x=(bk,l), kjer je k=y,y+1,…,y+N1-1, l=x ,x+1,…,y+N2-1. V razvitem algoritmu se vsak okvir video sekvence med obdelavo razdeli na sosednje matrične bloke (Bm,n) velikosti 88, m,n=0,8,16... Če kateri koli blok Biy,x video sekvence se izkaže, da je v določenem smislu "podoben" izvirnemu bloku Bim, n, predpostavljamo, da je blok Bim,n premaknjen fragment Biy,x Glej, na primer, Davis G.M., A wavelet-based analysis of fractal image compression // IEEE Trans. Image Proc. – 1998. – V.7 – št.2. – Str.141-154.
prejšnji okvir, za kodiranje (m,n)-bloka slike pa je dovolj, da nastavimo koordinate bloka v prejšnjem okvirju, y in x, ali spremenimo koordinate y-m in x-n. Poseben primer premaknjenega bloka je mirujoči blok, ko je m=y, n=x. Če bloka Bim,n ni mogoče najti podobnega v prejšnjem okviru, mora biti blok kodiran kot nov. Za izbiro načina kodiranja za naslednji obdelani blok Bim, n nas ponovno vodi minimalni kriterij Lagrangeove funkcije J(b)=D(b)+R(b). Predpostavimo, da argument b= ustreza kodiranju premaknjenega (fiksnega) bloka in b=1 – novega. Tisti. če je J(1)>J(0), je blok kodiran kot premaknjen, drugače pa kot nov.
Pri uporabi optimizacije RD je problem iskanja premaknjenih blokov formuliran na naslednji način. Za dani (m,n)-blok Bim, n i-tega okvira, poiščite v prejšnjem rekonstruiranem okvirju tak (y,x)-blok B iy,x, tako da funkcija Lagrange RD zavzame najmanjšo vrednost. Pri tem se upošteva, da bodo koordinate najdenega bloka kodirane kot relativne, tj. vektor premika r=(y-m,x-n). Da bi lahko iskanje potekalo v realnem času, je treba kot regijo obravnavati samo točke (v,u), ki so dovolj blizu točke (m,n). Povečanje učinkovitosti iskanja s širitvijo območja dosežemo z uporabo različnih algoritmov usmerjenega iskanja, katerih cilj je minimiziranje napake reprezentacije premaknjenega bloka Bim, n Biy,1, kar ustreza posebnemu primeru (11) pri =0. Da bi upoštevali prispevek bitnih stroškov k funkciji RD J*, bomo korak za korakom izvedli minimizacijo (11), pri čemer bomo na vsaki stopnji približno predpostavili, da obravnavani vektorji premika povzročajo enake stroške za statistično kodiranje. Poleg tega bomo za povečanje univerzalnosti algoritmov iterativnega iskanja natančneje iskali majhne premike. Dejansko, če se je določen blok slike premaknil na precejšnjo razdaljo v primerjavi s prejšnjim okvirjem, potem človeško oko zazna ustrezen del slike kot zamegljen in ni treba natančno določiti vektorja gibanja. Majhni premiki blokov niso samo prevladujoči, ampak jih je zaradi specifičnosti vizualne percepcije treba tudi natančno slediti. Predlagani iskalni algoritem RD ima naslednjo obliko.
Korak 0. Izračun vrednosti funkcije RD fiksnega bloka, r=(0,0):
Korak 1. Natančno iskanje majhnih premikov, ki je blizu brutalne sile.
1.1. Med devetimi (y,x)-bloki prejšnjega okvirja je 1.2. Med devetimi (y,x)-bloki prejšnjega okvirja je 1.3. Izračun vrednosti funkcije RD Korak 2. Grobo iskanje velikih premikov.
2.1. Med osmimi (y,x)-bloki prejšnjega okvirja je 2.2. Med devetimi (y,x)-bloki prejšnjega okvira (y 4, x 4)((0,0), (2,2), (2,2), (2,2), (2,2), (3,0), (0,3), (3,0), ( 0,3)) 2,3. Izračun vrednosti funkcije RD Korak 3. Izbira najboljše možnosti za premikanje bloka.
Konec Za izračun vrednosti funkcije J0 je treba upoštevati bitne stroške za kodiranje predznaka premaknjenega bloka: J 0 = J * log2 (mov), kjer je mov frekvenca pojavljanja premaknjenih blokov v že obdelanih podatkov.
Glavni obseg izračunov v danem algoritmu je povezan z izračunom odstopanj B im, n Biy, x. Med izračuni se ena poskusna točka premakne iz koraka 0 v korak 1.1, ena – iz koraka 1.1 v 1.2, ena – iz koraka 2.1 v 2.2. Posledično je treba izračun odstopanja izvesti 33-krat.
Za povečanje učinkovitosti danega algoritma iskanja za vektor (y, x) obdelanega bloka je treba narediti napoved z uporabo vektorjev () in () dveh že obdelanih sosednjih blokov (navpičnega soseda oziroma vodoravnega soseda) . Sama napoved so relativne koordinate y 0, x 0, ki določajo prenos središča območja iskanja: od točke (m, n) do točke (m, n) = m + y 0, n + x 0. Eksperimenti kažejo, da se število novih slikovnih blokov zmanjša za 5...25 %, če sprejmemo naslednje pravilo za izdelavo napovedi:
Po ideologiji standarda MPEG obdelujemo tudi nove bloke s kvantizacijo, ki ji sledi statistično kodiranje dvodimenzionalnih koeficientov DCT. Naj bo S=F(Bm,n) rezultat DCT bloka Bm,n. Označimo SQ = (~k,l = round(sk,l / qk,l))k,l =0, SQ = (sk,l = qk,l ~k,l )k,l =0, kjer je Q = (qk,l )k,l =0 – ena od kvantizacijskih matrik JPEG. Za statistično kodiranje matrike S se uporablja kontekstualni algoritem kodiranja, obravnavan v 4. poglavju, ki vključuje dodatno stopnjo optimizacije RD. Naj bo spet ZQ = (z0,..., z63) vektor, dobljen kot rezultat cik-cak branja podatkov iz matrike SQ po pravilu, ki ga določa standard JPEG (SQ ZQ), G (ZQ) = (g k ) C=1 (0,..., 63) je množica indeksov neničelnih elementov vektorja ZQ, tj. z g k 0, če je gkG; gkG: z g k = 0. RD optimizacija statističnega kodiranja je mogoča s podaljšanjem ničelne serije z zmanjšanjem števila elementov v množici G (dodatno ničevanje komponent vektorja ZQ). Da bi se zaradi tega izognili opaznemu zapletu kodirnega algoritma, bomo analizirali le možnost povečanja končne ničelne serije, ki največ prispeva k minimizaciji funkcije J(ZQ)=D(ZQ)+R(ZQ ). Naj bo ZQ vektor, dobljen iz vektorja ZQ kot rezultat ničevanja zadnjih komponent (zk )k = g m +1, tj.
G (ZQ) = (g k )m=1 G (ZQ), m=1,…,C. Potem je najenostavnejša optimizacija RD sestavljena iz iskanja indeksa g m * G (ZQ), tako da postopek za kodiranje novega slikovnega bloka, obravnavan zgoraj, predpostavlja uporabo dane kvantizacijske matrike Q. Univerzalni kodirni algoritem mora delovati z določenim nizom kvantizacijske matrike (Qj) z možnostjo izbire zahtevanega za specifične pogoje.
Če je nabor dovolj velik, se izbira kvantizacijske matrike Q po principu minimiziranja funkcije JQ (12) spremeni v okoren postopek, ki ga s standardnimi sredstvi ni mogoče izvesti v realnem času. Poleg tega z velikim obsegom možnih vrednosti za indeks j njegovo kodiranje ločeno za vsak nov blok povzroči nesprejemljivo visoke dodatne bitne stroške. Zato smo iz nabora, ki ga priporoča JPEG, izbrali le nekaj matrik, ki ustrezajo najboljši, najslabši in nekaterim vmesnim stopnjam kakovosti. V poskusih je bilo izbrano število matrik |(Qj)|=4. Za pospešitev izvajanja operacij deljenja, ki so potrebne za kvantizacijo, smo elemente matrik (Qj) zaokrožili na najbližjo vrednost 2k, k=0,1,... Ta pristop nam omogoča zamenjavo operacij celega števila deljenje in množenje s premiki bitov binarne predstavitve števil, ki jih običajno realna oprema izvaja veliko hitreje.
Ob upoštevanju bitnih stroškov, ki so potrebni za kodiranje indeksa kvantizacijske matrike, je Lagrangeova funkcija, ki ustreza kodiranju novega slikovnega bloka, definirana takole:
J = min (J Q log 2 Q) log 2 new, kjer je JQ v skladu z (12), Q je frekvenca pojavljanja matrike Q, new je frekvenca pojavljanja novih blokov med predhodno obdelavo.
Pri preučevanju značilnosti končnega algoritma za stiskanje videa je bilo za oceno velikosti napake kodiranja v rekonstruiranem zaporedju B0, B1,..., B K 1 uporabljeno razmerje med vrednostjo vrha signala in šuma, ki je bilo določeno kot sledi:
kjer M1 in M2 nastavita velikost okvirja v slikovnih pikah. Za poskuse so bile izbrane znane testne sekvence News, Container ship, Hall monitor, Akiyo, Claire. Vsi imajo velikost okvirja 144176 slikovnih pik. Pred poskusi so bila prvotna zaporedja razredčena: le vsaka tretja sličica, B3k (k=0,...,24), je bila uporabljena za oblikovanje teh 25-obličnih video sekvenc, ki so bile nato obdelane. To časovno redčenje je bilo zasnovano tako, da simulira hitrost zajema videa 10 sličic na sekundo, namesto prvotnih (za vse zgornje sekvence) 30 sličic na sekundo. Obdelana je bila samo komponenta svetlosti Y in samo komponenta svetlosti je bila uporabljena za analizo napake v realnem času.
Rezultati numeričnih poskusov, ki jih je pridobil podiplomski študent F.V. Strelkov, so prikazani v tabeli 2. Vrednost PSNR (13), dosežena na istih redčenih 25-sličnih testnih video sekvencah z uporabo javno dostopnega kodirnika MPEG - http://www.mpeg .org. /MSSG. Dolžina stisnjene podatkovne datoteke, pridobljene v vsakem poskusu, je natančno enaka zmnožku velikosti bitnega toka podatkov (prikazano v tabeli) s faktorjem 2,5. V vseh testih daje predlagana shema stiskanja dobri rezultati, ki presega značilnosti določenega kodirnika MPEG-2, kljub dejstvu, da je kodek mpeg2encode uporabil izčrpno iskanje na območju 2323 slikovnih pik, da bi našel premaknjene slikovne bloke.
Tabela 2. Značilnosti stiskanja predlaganega algoritma Opisani algoritem stiskanja videoposnetkov je bil implementiran v programsko opremo kot del dela, opravljenega v Državnem raziskovalnem in proizvodnem kompleksu "Tehnološki center" v Moskvi državni zavod elektronske opreme in v NPP "Tehnologija"
Implementacija razvitih knjižnic za stiskanje videa je bila izvedena v številnih programskih sistemih, med katerimi je najbolj praktičen sistem za nadzor in registracijo videa Visual Security (glej.
http://www.tcen.ru/vs).
Rezultati raziskave, opravljene v diplomskem delu, so povzeti v zadnji del– »Glavne ugotovitve in sklep« (3 strani).
Predstavljeno diplomsko delo preučuje različne vidike uporabe diskretnih ortogonalnih transformacij za kompresijo digitalne slike, tako iz povsem formalne teoretične analize kot iz zahtev in omejitev, ki jih praksa nalaga specifičnim računalniškim shemam in algoritmom. Na splošno je vsebina dela aplikativna, zato je večina teoretični rezultati podprto z računalniškimi eksperimenti, katerih rezultati pa niso služili le kot ponazoritev ali preizkus teorije, temveč so pogosto dajali zagon in predstavljali izvorno gradivo za nadaljnje raziskave. Na podlagi rezultatov raziskave, ki je bila opravljena v disertaciji, lahko sklepamo naslednje.
1. Ortogonalne transformacije so glavno orodje, ki se uporablja za dekorelacijo podatkov med stiskanjem slike. V primeru matematični model diskretni signal podaja kovariančna matrika, zato je za analizo učinkovitosti obdelave dekorelacije priporočljivo uporabiti merilo povprečne presežne entropije, predlagano v delu.
2. Posebej za stiskanje koreliranih podatkov je bila pridobljena in prvič uvedena diskretna psevdokozinusna transformacija (DPCT). V kompresijski shemi, ki predpostavlja prisotnost stopnje skalarne kvantizacije transformacijskih koeficientov, med obravnavanimi hitrimi transformacijami, katerih izvedba je zmanjšana le na operacije dodajanja in odštevanja (Walsh, Haar, psevdokosinus), DPKP daje najboljše rezultate dekorelacije za diskretni signal, ki ga opisuje Markovljev model.
3. Z uporabo dobljenih hitrih algoritmov DPCL, ki upoštevajo specifiko obdelave realnih nizov, dosega predlagana shema kompresije slike na osnovi aritmetičnega kodiranja koeficientov DPCL lastnosti, ki so blizu različici JPEG, ki temelji na DCT, glede kakovosti obdelave in računska kompleksnost.
4. Pri uporabi statističnega kodiranja koeficientov DCT z metodo JPEG je prisotnost "skokov" v diskretnem signalu najmanj zaželena v osrednjem območju obdelave fragmentov.
5. Večmodelna (multi-stream) aritmetična metoda kodiranja je zelo učinkovita pri uporabi v različnih shemah in algoritmih stiskanja podatkov, ena ključnih točk pri razvoju shem stiskanja pa je določitev pravil za izbiro trenutnega modela kodiranja. na podlagi konteksta že obdelanih podatkov. Tako uporaba večmodelnega kontekstualnega aritmetičnega kodirnega algoritma koeficientov DCT, predlaganega v 4. poglavju v shemi JPEG, poveča učinkovitost stiskanja podatkov za 10 %.
6. Pri stiskanju slik z uporabo večmodelnega kodiranja drevesnih struktur spektrov valovnih valov mora pravilo izbire modela temeljiti na kombiniranem kontekstu, ki upošteva okolje samega koeficienta valovnih valov v podpasu in okolje »nadrejenega ” koeficient. Na tej osnovi dobljen nov učinkovit algoritem za kompresijo digitalne slike z izgubo, ki je bil razvit na podlagi rezultatov proučevanja statističnih lastnosti spektrov diskretnih valovnih transformacij, kaže visoke kompresijske karakteristike s kompleksnostjo izvedbe, ki je sprejemljiva za širok spekter aplikacij.
7. Za odpravo interframe (časovne) redundance video podatkov bi moral biti za praktično uporabo med proučevanimi algoritmi za blokovno kompenzacijo gibov najprimernejši predlagani hibridni algoritem usmerjenega iskanja, v katerem se majhni gibi iščejo natančno in skrbno, in velika gibanja - bolj grobo.
8. Pri uporabi predlaganega algoritma za stiskanje videa, ki je bil razvit na osnovi optimizacijskega pristopa RD ob upoštevanju zahtev in posebnosti implementacije programske opreme, se kompresija in obnavljanje videa v realnem času doseže na osnovi sodobnih osebnih računalnikov, z visoke kakovosti predelava.
Na splošno je disertacija pridobila nove znanstvene rezultate, katerih teoretične določbe so omogočile pomemben razvoj in formalizacijo postopkov za analizo in sintezo shem stiskanja digitalne slike, ki temeljijo na uporabi diskretnih ortogonalnih transformacij. Razviti pristopi in priporočila so pripeljali do konstrukcije specifičnih kompresijskih shem in algoritmov, od katerih so bili številni implementirani v programsko opremo in eksperimentalno potrdili učinkovitost njihove uporabe.
Seznam glavnih del na temo disertacije 1. Efimov A.V., Umnyashkin S.V. Hitri algoritmi za izračun diskretne Chrestenson-Levyjeve transformacije in ocenjevanje njenih spektralnih karakteristik // Teor. funkcij in pribl.: Tr. 7. Saratov. pozimi šola (1994). Del 2. - Saratov: Založba SSU, 1995. - Str. 9-20.
2. Efimov A.V., Pospelov A.S., Umnjaškin S.V. Uporaba transformacije Chrestenson-Levy v problemih obdelave digitalnih informacij // International.
konf. "Funkcijski prostori, teorija aproksimacije, nelinearna analiza", posvečen. 90-letnica akademika S.M. Nikolsky (27. april - 3. maj 1995): Povzetek.
poročilo - M .: Založba MIPT, 1995. - P.124-125.
3. Umnjaškin S.V. Uporaba diskretne Chrestenson-Levyjeve transformacije (DCLT) za kodiranje slike: primerjava z diskretno Fourierjevo transformacijo (DFT) // Vseros. znanstveno-tehnično konf. »Elektronika in računalništvo« od 15. do 17. novembra. 1995: Povzetek. poročilo - M.: MGIET (TU), 1995. - Str. 265-266.
4. Umnjaškin S.V. Ocena disperzije elementov spektra diskretne kosinusne transformacije stacionarnega Markovskega procesa prvega reda Int. konf. po teoriji pribl. funk., posvečen v spomin na prof. P.P. Korovkina (Kaluga, 26.-29. junij 1996): Povzetek. poročilo -T.2.-Tver: TSU, 1996. - Str. 217-218.
5. Umnjaškin S.V. Ocena učinkovitosti uporabe enotnih transformacij za kodiranje diskretnih signalov // Informatika in komunikacije: Sat.
Znanstvena dela ur. V.A. Barhotkina. M.: MIET 1997. P.73-78.
6. Umnjaškin S.V. Ocenjevanje učinkovitosti uporabe diskretnih transformacij za stiskanje podatkov // “Elektronika in informatika – 97”. Druga vseslovenska znanstvena in tehnična konferenca z mednarodna udeležba(Zelenograd, 25.-26. november 1997): Povzetek. doc. Del 2. - Str.79.
7. Efimov A.V., Pospelov A.S., Umnjaškin S.V. Teoretične osnove in nekatere značilnosti uporabe diskretnih multiplikativnih transformacij pri problemih stiskanja digitalne slike // Zbornik mednarodnih konferenc "Izračun optimizacije prehrane" (6-8 junij 1997, Kijev) Kijev: Inštitut za kibernetiko po imenu V.M. Glushkov, 1997. - strani 108-112.
8. Efimov A.V., Pospelov A.S., Umnjaškin S.V. Nekatere lastnosti multiplikativnih ortonormiranih sistemov, ki se uporabljajo pri digitalni obdelavi signalov // Proceedings matematični inštitut njih. V.A. Steklov RAS.
- T.219. - 1997. - Od 137-182.
9. Efimov A.V., Umnjaškin S.V. O nekaterih lastnostih posplošenega Haarjevega sistema in oceni učinkovitosti uporabe ortogonalnih transformacij za stiskanje podatkov // Funkcionalni prostori. Diferencialni operatorji. Problemi matematične vzgoje: zbornik medn. konf., posvečen 75-letnica dopisnega člana. RAS prof. L.D. Kudrjavceva. - Zvezek 1. - M.: Ros. Univerza za prijateljstvo ljudi, 1998. - str. 70-73.
10. Umnjaškin S.V. O modifikaciji diskretne kosinusne transformacije // Teorija aproksimacije in harmonična analiza: Proc. poročilo mednarodni konf.
11. Umnjaškin S.V. O modifikaciji diskretne kosinusne transformacije // Izv. Tul. stanje un-ta. Ser. Matematika. Mehanika. Informatika. Tula: TulGU, 1998. T. 4. Izd. 1. str. 143-147.
12. Umnjaškin S.V., Kočetkov M.E. Analiza učinkovitosti uporabe diskretnih ortogonalnih transformacij za digitalno kodiranje koreliranih podatkov // Novice univerz. elektronika. - št. 6. - 1998. - Str. 79-84.
13. Umnjaškin S.V. O združevanju koreliranih podatkov. // Informacijske tehnologije v inovativnih projektih. medn. konf. (Izhevsk, 20.-22. april 1999): Materiali poročil. - Izhevsk, IzhSTU, 1999. - str. 59-65.
14. Umnjaškin S.V. Algoritem za združevanje koreliranih podatkov v gruče // VII Int. konf. Matematika. Gospodarstvo. Ekologija. izobraževanje. medn. simp. Fourierjeve vrste in njihove uporabe: Proc. doc. – Rostov: Rost. stanje gospodarstvo akad., 1999. – Str. 211-212.
15. Efimov A.V., Pospelov A.S., Umnjaškin S.V. Nekatera vprašanja uporabe multiplikativnih sistemov in transformacij v problemih digitalne obdelave slik // VII Intern. konf. Matematika. Gospodarstvo.
Ekologija. izobraževanje. medn. simp. Fourierjeve vrste in njihove uporabe: Proc.
doc. – Rostov: Rost. stanje gospodarstvo akad., 1999. – pp. 154-155.
16. Umnjaškin S.V. Psevdokozinusna transformacija za stiskanje diskretnih signalov // Informacijske tehnologije in problemi mikroelektronike.
sob. znanstveni tr. – M.: MIET. – 1999. – Str.158-170.
17. Umnjaškin S.V. Algoritem za stiskanje mirujočih slik na podlagi diskretne valovne transformacije // VII mednarodna konferenca “Matematika. Računalnik. Izobraževanje" (Dubna, JINR, 24.-29. januar 2000):
Povzetek. doc. – Moskva: Progress-Tradition, 2000. – P.327.
18. Efimov A.V., Umnjaškin S.V. O strukturi nekaterih direktnih in inverznih valovnih transformacij // Teorija približevanja funkcij in operatorjev: Zbornik.
poročilo medn. konf., posvečen star 80 let. od dneva rojstva S.B. Stečkina (Ekaterinburg, 28. februar – 3. marec 2000). -Ekaterinb.: UrSU, 2000. – P.74-75.
19. Umnjaškin S.V., Strelkov F.V., Žukov V.G. Tristopenjski algoritmi za iskanje premaknjenih slikovnih blokov // Informacijske tehnologije in nadzorni sistemi. sob. znanstveni tr. uredil V.A. Barhotkina. – M: MIET, 2000.
– 47-55 strani.
20. Umnjaškin S.V. Kompresija digitalne slike z uporabo diskretne transformacije Chrestenson-Levy // Medindustrijska znanstvena in tehnična revija “Obrambni kompleks - znanstveni in tehnični napredek Rusije”, št. 2, 2000. Str.28-39.
21. Umnjaškin S.V., Kosmač M.V. Optimizacija kodiranja digitalne slike z metodo JPEG // Izv. univerza elektronika. -Št. 4-5. -2000. -P.139-141.
22. Umnjaškin S.V. Kompenzacija gibanja objektov pri stiskanju video podatkov // “Electronics and Informatics - XXI Century” Third International Scientific and Technical Conference: Proc. doc. – M.: MIET, 2000. – Str. 365-366.
23. Umnjaškin S.V. Algoritem za iskanje premaknjenih blokov za kodiranje digitalnih video slik // Interbranch. n.-t. revija “Obrambni kompleks - znanstveni in tehnološki napredek Rusije”, št. 3, 2001. – str. 38-41.
24. Umnyashkin S.V. Uporaba kontekstualnega aritmetičnega kodiranja za povečanje stiskanja podatkov s shemo JPEG // Novice univerz. elektronika. - št. 3. - 2001. – Str. 96-99.
25. Umnyashkin S.V. Wavelet stiskanje digitalnih slik z napovedjo statističnih modelov // Izv. univerze elektronika. - št. 5. - 2001. Str.86-94.
26. Umnyashkin S.V. Algoritem za fraktalno kodiranje slik na področju valovnih transformacij // Računalniška matematika. Optimizacija izračunov: Zbornik znanstvenih del. – Zvezek 1. – Kiv: Inštitut za kibernetiko im.
V. M. Gluškova, 2001. – Str. 385-391.
27. Umnjaškin S.V. Stiskanje slike, ki temelji na mešanem napovednem modeliranju valovnih dreves // Poročila univerze Vxj (Švedska) – Matematika, naravoslovje in tehnika. – št.11 (september), 2001. – 18 str.
28. Umnjaškin S.V., Strelkov F.V. RD-optimizirana shema za kompresijo videa v realnem času // Poročila univerze Vxj (Švedska) – Matematika, naravoslovje in tehnika. – št.12 (september), 2001. – 15 str.
29. Razvoj algoritmov in programske opreme za izvajanje digitalne analize in kompresije video slik v realnem času na osnovi splošnega strojno-programskega sistema: Raziskovalno poročilo (končno) / NPP “Tehnologija”; roke – Umnjaškin S.V. - "Varuh"; Državna št.
reg. 01990011697; inv. št. 01077. – Moskva, 1999. – 74 str.
30. Raziskave in razvoj algoritmov kompresije podatkov z izgubo programske opreme za digitalno video obdelavo: Raziskovalno poročilo (končno) / NPP “Tehnologija”; roke – Umnjaškin S.V. - "Ura"; Državna št. reg.
01200004624; inv. št. 100704. – Moskva, 2000. – 48 str.
Podpisano za objavo: 25.12.2001 Ukaz št. 332. Naklada 100 izvodov. Akademik-ur.l. 2.4. Format 6084 1/
enačbe Povzetek disertacije za diplomo doktorja fizikalnih in matematičnih znanosti Moskva 2007 Delo je bilo opravljeno na Raziskovalnem inštitutu za uporabno matematiko in avtomatizacijo...”
“KORNILOV Dmitrij Aleksandrovič RAZISKAVE LASTNOSTI FULERENOV IN NANOCEVK Z METODO MOLEKULARNE DINAMIKE Specialnost 01.04.07 – Fizika kondenziranih snovi Povzetek disertacije za znanstveno stopnjo kandidata fizikalnih in matematičnih znanosti St. Petersburg 2003. Delo je bilo opravlja na državni visokošolski ustanovi poklicno izobraževanje Državna politehnična univerza v Sankt Peterburgu Znanstveni vodja: doktor...”
“CHIRIKOV ANTON MIKHAILOVICH NOVI TEOREMI EDINSTVENE POTENCNE VRSTE 01.01.01 - realna, kompleksna in funkcionalna analiza Povzetek disertacije za znanstveno stopnjo kandidata fizičnih in matematičnih znanosti SANKT PETERBURG 2011 Delo je bilo opravljeno na Oddelku za matematično analizo Fakulteta za matematiko Ruska država Pedagoška univerza njih. Herzen Znanstveni vodja, doktor fizikalnih in matematičnih znanosti, profesor Nikolaj Širokov...”
„Sidorov Evgeniy Nikolaevič Značilnosti optičnih lastnosti težkih dopiranih Gaas: TE pod pogoji korelirane nečistoče, posebnost 01.04.10 - Podvoja Fizika Izvleček disertacije za stopnjo kandidata za fizične in matematične vede Tomsk - 2010 Dokončano delo OSCOW - 2010 Inštituta za fiziko polprevodnikov poimenovana po. A.V. Rzhanova SB RAS Znanstveni nadzornik: kandidat fizikalnih in matematičnih znanosti Davletkildeev Nadim Anvarovich Uradni ..."
“LYASHEDKO ANDREY DMITRIEVICH Termooptična popačenja v neodimovih laserjih na osnovi ploščatih aktivnih elementov z vzdolžnim diodnim črpanjem Posebnost: 01.04.21 - laserska fizika IZVLEČEK disertacije za znanstveno stopnjo kandidata fizikalnih in matematičnih znanosti Moskva - 2012 Delo je bilo opravljeno na Zvezna državna proračunska ustanova Znanstvenega inštituta za splošno fiziko poimenovana po A.M. Prokhorov RAS Znanstveni vodja: doktor fizikalnih in matematičnih znanosti Tsvetkov...”
“UDC: 535.326, 534.18 Pyatakova Zoya Aleksandrovna AKUSTO-OPTIČNA INTERAKCIJA V DVODIMENZIONALNIH FOTIČNIH KRISTALIH Specialnost 01.04.03 – radiofizika Povzetek disertacije za diplomo kandidata fizikalnih in matematičnih znanosti Moskva - 2011 Delo je bilo opravljeno na fakulteti fizike v Moskvi državna univerza njih. M.V. Lomonosov Znanstveni vodja: kandidat...”
“Alla Aleksandrovna KRUTIKOVA SPEKTRALNA ANALIZA KOMPOZITNIH MATERIALOV NA OSNOVI NANOKRISTALNEGA SILICIJA Posebnost: 02.00.02 – Analizna kemija IZVLEČEK disertacije za znanstveno stopnjo kandidata kemijskih znanosti Moskva–2007 Delo je bilo opravljeno na oddelku analizna kemija Moskovska državna akademija za fino kemijsko tehnologijo poimenovana po. M.V. Lomonosov Znanstveni vodja: doktor kemijskih znanosti, profesor Anatolij Aleksandrovič Iščenko Uradnik..."
“MATVENKO Sergej Ivanovič PERIODIČNE STRUKTURE V KORELACIJSKIH SISTEMIH NIZKE DIMENZIJE Posebnost 01.04.02 - teoretična fizika IZVLEČEK disertacije za doktorat fizikalnih in matematičnih znanosti Chernogolovka - 2012 Delo je bilo opravljeno na Zvezni državni proračunski inštitut Znanstvenega inštituta teoretične fizike poimenovana po ... ."
“UDC 004.896 AKSENOV Konstantin Aleksandrovič TEORIJA IN PRAKSA PODPORE ODLOČANJU NA PODROČJU PROCESOV PRETVORBE VIROV Posebnost 05.13.01 – Sistemska analiza, upravljanje in obdelava informacij Povzetek disertacije za diplomo doktorja tehničnih znanosti Ekaterinburg - 2011 Delo opravljeno na kavarna Oddelek za avtomatizirane nadzorne sisteme Zvezne državne avtonomne izobraževalne ustanove za visoko strokovno izobraževanje Ural zvezna univerza imenovan po prvem predsedniku Rusije B. N. Jelcinu. Znanstveno ..."
“Voskov Alexey Leonidovich IZRAČUN FAZNEGA RAVNOTEŽJA Z METODO KONVEKSNIH LOPIN Posebnost 02.00.04 - fizikalna kemija IZVLEČEK disertacije za diplomo kandidata kemijskih znanosti Moskva - 2010 Delo je potekalo v laboratoriju za kemijsko termodinamiko na Oddelku fizikalne kemije Fakultete za kemijo Moskovske državne univerze po imenu M.V. Znanstveni vodja: doktor kemijskih znanosti, profesor Genadij Fedorovič Voronin Uradni ..."
“Kravchenko Igor Vitalievich ZNAČILNOSTI STRUKTURIRANJA PLASTISTIH IN DISPERZNIH SISTEMOV NEZDRUŽLJIVIH POLIMEROV POD STRIŽNIM TOKOM. NUMERIČNO MODELIRANJE 02.00.06 – Visokomolekularne spojine Povzetek disertacije za diplomo kandidata fizikalnih in matematičnih znanosti Moskva 2010 www.sp-department.ru Delo je bilo opravljeno na Instituciji Inštituta za probleme Ruske akademije znanosti kemijska fizika Znanstveni vodja RAS: doktor fizikalnih in matematičnih znanosti Patlazhan...”
“Gribov Andrey Gennadievich ANALIZA IZMENJAV INFORMACIJ V SISTEMIH UPRAVLJANJA Posebnost 05.13.01 – Sistemska analiza, upravljanje in obdelava informacij (industrija) POVZETEK disertacije za znanstveno stopnjo kandidata fizičnih in matematičnih znanosti Moskva - 2011 Delo je bilo opravljeno na Institucija računalniškega centra Ruske akademije znanosti. A.A. Dorodnitsyna RAS na Oddelku za uporabne optimizacijske probleme. Znanstveni mentor: doktor fizikalnih in matematičnih znanosti..."
“Jardimalieva Gulzhian Iskakovna (CO)POLIMERIZACIJA IN TOPLOTNE TRANSFORMACIJE MONOMEROV, KI VSEBUJEJO KOVINE, KOT NAČIN ZA USTVARJANJE METALOPOLIMEROV IN NANOKOMPOZITOV 02.00.06 – spojine z visoko molekulsko maso IZVLEČEK disertacije za znanstveni naziv doktorja kemijskih znanosti Chernogolovka - 2009 www.sp-department.ru Delo je bilo opravljeno na Inštitutu za probleme kemijske fizike Ruske akademije znanosti doktor kemijskih znanosti, profesor znanstveni svetovalec : Doktor kemijskih znanosti Anatolij Dmitrijevič je pomagal ..."
“GAVRILOV Aleksey Andreevich RAZISKAVE LINEARNIH IN MREŽNIH NAKLJUČNIH POLIMERNIH SISTEMOV Z METODAMA RAČUNALNIŠKEGA MODELIRANJA Specialitete 02.00.06 visokomolekularne spojine, 01.04.07 – fizika kondenzirane snovi Povzetek disertacije za znanstveno stopnjo kandidata fizikalnih in matematičnih znanosti Moskva – 201 3 Delo je bilo opravljeno na Oddelku za fiziko polimerov in kristalov Fakultete za fiziko Moskovske državne univerze poimenovane po M.V. Lomonosovu..."
“NGUYEN XUAN NGIA DIELEKTRIČNA RELAKSACIJA SUPRAMOLEKULARNIH STRUKTUR V BIOLOŠKIH TEKOČINAH PRI NIZKIH IN INFRANIOZNIH FREKVENCAH Specialnost - 01.04.04. Fizična elektronika IZVLEČEK disertacije za diplomo kandidata fizičnih in matematičnih znanosti Sankt Peterburg - 2011 Delo je bilo opravljeno na državni izobraževalni ustanovi visokega strokovnega izobraževanja Državna politehnična univerza Sankt Peterburga Znanstveni vodja:...”
"Naymushina Ekaterina Aleksandrovna. UDK 538.945 UPORABA METODE RTG ELEKTRONSKE SPEKTROSKOPIJE ZA PREUČEVANJE KEMIJSKE STRUKTURE KOMPLEKSNIH BAKROVIH OKSIDA V SUPERPREVODNEM STANJU Specialnost 01.04.01. – instrumenti in metode eksperimentalna fizika POVZETEK disertacije za diplomo kandidata fizikalnih in matematičnih znanosti Izhevsk - 2004 Delo je bilo opravljeno v laboratoriju za elektronsko spektroskopijo Inštituta za fiziko površin v državi Udmurt ..."
“Daškov Evgenij Vladimirovič O propozicijskih računih, ki predstavljajo koncept dokazljivosti 01.01.06 – matematična logika, algebra in teorija števil POVZETEK disertacije za znanstveno stopnjo kandidata fizičnih in matematičnih znanosti Moskva - 2012 Delo opravljeno na oddelku matematična logika in teorija algoritmov Fakultete za mehaniko in matematiko Moskovske državne univerze po imenu M.V.
“Rusakov Dmitry Mikhailovich PROGRAMSKI DIAGRAMI S KONSTANTAMI Posebnost 01.01.09 – diskretna matematika in matematična kibernetika IZVLEČEK disertacije za akademsko stopnjo kandidata fizikalnih in matematičnih znanosti Moskva - 2008 Delo je bilo opravljeno na Oddelku za matematično kibernetiko fakultete računalniške matematike in kibernetike Moskovske državne univerze po imenu M.V. Lomonosov. Znanstveno ..."
“REMEEVA ALFIA NILOVNA METODE POUČEVANJA FIZIKE V RAZREDIH SOCIALNO-EKONOMSKEGA PROFILA 13.00.02 – teorija in metode poučevanja in izobraževanja (fizika) POVZETEK disertacije za znanstveno stopnjo kandidata pedagoške vede Chelyabinsk - 2008 Delo je bilo izvedeno na Oddelku za teorijo in metode poučevanja fizike v državi izobraževalna ustanova visoko strokovno izobraževanje Država Sterlitamak pedagoško akademijo Znanstveni mentor: dr.
Transformacije, ki se uporabljajo za stiskanje slik, morajo biti hitre in po možnosti enostavno implementirane na računalniku. To predvsem predpostavlja, da morajo biti takšne transformacije linearni. Se pravi pretvorjene vrednosti Z( so linearne kombinacije (vsote z nekaterimi faktorji ali utežmi) prvotnih količin (pikslov) dj, in ustrezen množitelj ali utež je določeno število Wij(pretvorbeni faktor). pomeni, Z (-]G\- djWij, kjer je r, j= 1,2,..., str. Na primer, kdaj n= 4 to transformacijo lahko zapišemo kot matrična oblika ki bo v splošnem primeru imel naslednjo obliko: C = W D. Vsak stolpec vektorja matrike W se imenuje "bazni vektor".
Pomembna naloga je določitev pretvorbenih koeficientov wij. Glavna zahteva je, da po preoblikovanju vrednost z\ bi bila velika, vse ostale količine C2, сз,... pa bi postale majhne. Osnovno razmerje С( = Ylj djWij predvideva, da Z( bo velika, če teža Wij bo povečala ustrezne vrednosti dj. To se bo zgodilo na primer, če so komponente vektorjev wij in dj imajo podobne pomene in enake znake. obratno, Z( bo majhna, če so uteži majhne in jih ima polovica predznak nasproten predznaku ustreznega števila dj.Če torej dobimo velike c*, potem vektorji W(j so podobni izvirnemu vektorju dj in majhni Z( pomeni, da komponente wij zelo drugačen od dj. Zato so osnovni vektorji wij lahko razlagamo kot orodje za ekstrakcijo nekaterih značilnih lastnosti izvirnega vektorja.
V praksi uteži Wij ne bi smelo biti odvisno od izvornih podatkov. V nasprotnem primeru jih bo treba dodati v stisnjeno datoteko za uporabo v dekoderju. Ta premislek, kot tudi dejstvo, da so izvorni podatki slikovne pike, to je nenegativne količine, določa način izbire baznih vektorjev. Prvi vektor, tisti, ki generira z\, mora biti sestavljen iz podobnih, po možnosti ujemajočih se številk. Povečal bo nenegativne vrednosti slikovnih pik. In vsi drugi bazični vektorji morajo biti sestavljeni iz polovice pozitivnih števil in druge polovice iz negativnih števil. Po množenju z pozitivne vrednosti in njihov seštevek bo rezultat majhno število. (To še posebej velja, če so izvorni podatki blizu in vemo, da imajo sosednje slikovne pike ponavadi blizu vrednosti.) Spomnimo se, da osnovni vektorji zagotavljajo orodje za pridobivanje funkcij iz izvornih podatkov. Zato bi bila dobra izbira bazni vektorji, ki se med seboj zelo razlikujejo in zato lahko izločijo različne lastnosti. To vodi do ideje, da bi morali biti bazni vektorji medsebojno pravokotni.Če je transformacijska matrika W sestavljena iz pravokotni vektorji, potem se imenuje transformacija pravokoten. Druga ugotovitev, ki omogoča pravilno izbiro baznih vektorjev, je, da morajo imeti ti vektorji čedalje višje frekvence sprememb predznaka, da lahko pri izračunu transformiranih količin izluščimo tako rekoč visokofrekvenčne značilnosti stisnjenih podatkov.
Prvi bazični vektor (zgornja vrstica W) je vse enice, zato je njegova frekvenca nič. Vsi drugi vektorji imajo dva +1 in dva -1, zato bodo ustvarili majhne pretvorjene vrednosti, njihove frekvence (merjene s številom sprememb predznaka v vrstici) pa se povečajo. Ta matrika je podobna transformacijski matriki Hadamard-Walsh (glej enačbo (3.11)). Na primer, transformirajmo začetni vektor (4,6,5,2)
Rezultat je precej spodbuden, saj je število z\ postala velika (v primerjavi z izvirnimi podatki), drugi dve številki pa sta postali majhni. Izračunajmo energije originalnih in transformiranih podatkov. Začetna energija je 4 2 + b 2 + 5 2 + 2 2 = 81, po transformaciji pa je energija postala 17 2 + 3 2 + (-5) 2 + I 2 - 324, kar je štirikrat več. Energijo lahko prihranimo tako, da transformacijsko matriko W pomnožimo s faktorjem 1/2. Novi produkt W-(4,6,5,2) t bo enak (17/2,3/2, -5/2,1/2). Torej je energija ohranjena in koncentrirana v prvi komponenti in zdaj znaša 8,5 2 /81 = 89 % celotne energije prvotnih podatkov, v katerih je prva komponenta predstavljala le 20 %.
Druga prednost matrike W je, da izvaja tudi inverzno transformacijo. Izvirni podatki (4,6,5,2) so obnovljeni z uporabo produkta W-(17/2,3/2, -5/2,1/2) t.
Zdaj lahko cenimo prednosti te preobrazbe. Transformirani vektor (8.5,1.5,-2.5,0.5) kvantiziramo tako, da ga zaokrožimo na celo število in dobimo (9,1,-3,0). Naredimo inverzno transformacijo in dobimo vektor (3.5,6.5,5.5,2.5). V podobnem poskusu preprosto odstranimo dve najmanjši števili in dobimo (8,5,0, -2,5,0), nato pa izvedemo inverzno transformacijo tega grobo kvantiziranega vektorja. Posledica tega so rekonstruirani podatki (3,5.5,5.5,3), ki so tudi precej blizu originalu. Torej, naš zaključek: tudi ta preprosta in intuitivna transformacija je dobro orodje za »iztiskanje« odvečnosti iz izvirnih podatkov. Bolj sofisticirane transformacije dajejo rezultate, ki omogočajo obnovitev podatkov z visoko stopnjo podobnosti tudi z zelo grobo kvantizacijo.
“Slika v tisku” - Posebnosti slike v tisku. Glavna lastnost natisnjene slike. Knjiga. Posebnost večina finih tiskarskih del. Pluralnost Masivnost Javna dostopnost. Povezovanje slik z besedilom. Umetnost knjige. Pisava.
“Vektorska in rastrska grafika” - Vektorski primitivi so podani z opisi. Principi konstruiranja vektorskih in rastrskih slik. Vektorske slike zavzamejo razmeroma malo pomnilnika. Vrste računalniške grafike. Vektorske slike opisujejo desetine in včasih tisoče ukazov. Slabosti rastrske grafike.
"Računalniška grafika" - Glavne težave pri delu z rastrsko grafiko. Vrste računalniške grafike se razlikujejo po načelih oblikovanja slike. Računalniška grafika. Fraktalna grafika. Vrste računalniške grafike. Velike količine podatkov. Pixel. Primerjalne značilnosti rastrske in vektorske grafike. Vsaka točka na zaslonu ima lahko samo dve stanji - "črno" ali "belo".
"Ustvarjanje grafičnih podob" - meje platna. Naloga 4. Ustvarite risbo, sestavljeno iz samooblik. Ustvarite risbo z orodno vrstico Draw. Položaj grafične podobe v besedilu. V besedilo vstavite sliko iz zbirke. Platno. Primerjalne značilnosti rastrske in vektorske grafike. Značilnosti ustvarjanja vektorske slike v Wordu 2003.
"Podoba moške glave" - drugi hladni, mrtvi obrazi so zaprti z rešetkami, kot ječa. Drugi so kot stolpi, v katerih dolgo nihče ne živi ali gleda skozi okno. Katere vrste portretov obstajajo? Proporcije obraza osebe. Slika obraznih potez. Človeški obraz in čustva. N. Zabolotski. Katere vrste obrazov obstajajo? Risba človeške glave. Res je svet hkrati velik in čudovit!
"Rasterske slike" - Zaključki iz eksperimenta. Rdeča. Katere osnovne barve uporablja računalnik? Rastrsko kodiranje grafičnih informacij. Raster slika. Piksli različne barve. Modra (turkizna). siva. Roza. Paleta sodobnih računalnikov. Vse barve je mogoče oštevilčiti in vsako številko pretvoriti v binarno kodo.
