Transformare Wavelet: definiție, aplicare, exemplu

Apariția camerelor digitale ieftine a dus la faptul că o parte semnificativă a locuitorilor planetei noastre, indiferent de vârstă și sex, a dobândit obiceiul de a captura fiecare pas și de a pune imaginile pe afișe publice în rețelele sociale. În plus, dacă înainte ca arhiva fotografiei de familie să fie plasată într-un singur album, astăzi ea conține sute de imagini. Pentru a facilita stocarea și transmisia lor prin rețele, este necesară reducerea ponderii imaginii digitale. În acest scop, se aplică metode bazate pe diferiți algoritmi, inclusiv transformarea wavelet. Ce este aceasta, va spune articolul nostru.

Ce este o imagine digitală?

Informațiile vizuale din computer sunt reprezentate ca numere. În mod simplu, o fotografie realizată de o cameră digitală este un tabel în care valorile de culoare ale fiecărui pixel sunt inscripționate. Dacă vorbim despre o imagine monocromă, atunci ele sunt înlocuite cu valorile de luminozitate din intervalul [0, 1], unde 0 este folosit pentru a denumi culoarea neagră și 1 este alb. Restul nuanțelor sunt date în numere fracționate, dar cu ele este inconvenient de lucru, astfel încât intervalul este extins și valorile sunt alese din intervalul între 0 și 255. De ce de aici? E simplu! Cu această alegere, într-o reprezentare binară, exact 1 octet este necesar pentru a codifica luminanța fiecărui pixel. Evident, stocarea chiar și a unei imagini mici necesită destulă memorie. De exemplu, o dimensiune a fotografiilor de 256 x 256 pixeli va avea 8 kB.

Câteva cuvinte despre metodele de compresie a imaginilor

Desigur, toată lumea a văzut imagini de calitate slabă, unde există distorsiuni sub formă de dreptunghiuri de aceeași culoare, numite de obicei artefacte. Ele apar ca rezultat al așa-numitei compresii pierdute. Poate reduce semnificativ greutatea imaginii, dar afectează în mod inevitabil calitatea acesteia.

Algoritmii de compresie cu pierderi includ:

• JPEG. În prezent, acesta este unul dintre cei mai populari algoritmi. Se bazează pe aplicarea unei transformări discrete de cosinus. În mod corect, trebuie remarcat faptul că există variante de JPEG care fac compresie fără pierderi. Acestea includ Joss fără pierderi și JPEG-LS.
• JPEG 2000. Algoritmul este utilizat pe platforme mobile și se bazează pe aplicarea unei transformări discrete wavelet.
• Fractal Compression Algorithm. În unele cazuri, vă permite să obțineți imagini de o calitate excelentă, chiar și cu compresie puternică. Cu toate acestea, din cauza problemelor legate de brevetare, această metodă continuă să fie exotică.

Fără pierdere, compresia se realizează prin intermediul algoritmilor:

• RLE (folosit ca metodă principală în formatele TIFF, BMP, TGA).
• LZW (utilizat în format GIF).
• LZ-Huffman (folosit pentru formatul PNG).

Transformarea Fourier

Înainte de a trece la luarea în considerare a wavelet-urilor, este logic să studiem funcția asociată cu aceștia care descrie coeficienții în descompunerea informațiilor inițiale în componente elementare, adică oscilații armonice cu frecvențe diferite. Cu alte cuvinte, transformarea Fourier este un instrument unic care conectează lumile discrete și continue.

Se pare ca aceasta:

Formula inversiunii este scrisă după cum urmează:

Care este valletul

În spatele acestui nume se află o funcție matematică care vă permite să analizați diferitele componente de frecvență ale datelor studiate. Graficul său prezintă oscilații asemănătoare undelor, ale căror amplitudine scade la 0 de origine. În general, coeficienții wavelet, determinați prin transformarea integrală a semnalului, prezintă interes.

Spectrogramele Wavelet diferă de spectrele obișnuite de Fourier, deoarece cuprind spectrul diverselor semnale de semnal cu componenta lor temporală.

Transformarea Wavelet

Acest mod de conversie a semnalului (funcție) vă permite să îl traduceți din timp până la reprezentarea frecvenței în timp.

Pentru ca transformarea wavelet să fie posibilă, trebuie îndeplinite următoarele condiții pentru funcția wavelet corespunzătoare:

• Dacă pentru o anumită funcție psi (t) Transformata Fourier are forma

atunci trebuie îndeplinită următoarea condiție:

În plus:

• valletul trebuie să aibă energie finită;
• trebuie să fie integrat, continuu și să aibă un suport compact;
• Valletul trebuie să fie localizat atât în ​​frecvență, cât și în timp (în spațiu).

tipuri

Pentru semnalele corespunzătoare se folosește o transformare continuă a wavelet-ului. Un interes mult mai mare îl reprezintă analogul său discret. La urma urmei, poate fi folosit pentru a procesa informații în computere. Cu toate acestea, aceasta ridică problema că formulele pentru un DVP discret nu pot fi obținute prin simpla eșantionare a formulelor DNP corespunzătoare.

Soluția la această problemă a fost găsită de Daubechies, care a putut să aleagă o metodă de a construi o serie de wavelet ortogonale, fiecare dintre care este definit de un număr finit de coeficienți. Mai târziu au fost create algoritmi rapizi, de exemplu algoritmul lui Mall. În cererea sa de a se descompune sau de a restabili ordinea necesară pentru a efectua operațiuni cN, unde N - lungimea probei, și cu - numărul de coeficienți.

Vaivlet Haar

Pentru a comprimați imaginea, este necesar să se găsească un anumit model între datele sale, sau chiar mai bine, dacă este un lanț lung de zerouri. Acesta este locul unde algoritmul transformărilor wavelet poate fi util. Cu toate acestea, vom continua să considerăm metoda în ordine.

Mai întâi trebuie să vă amintiți că fotografiile de strălucirea pixelilor vecini diferă, de regulă, cu o sumă mică. Chiar dacă există zone cu diferențe clare, contrastul luminozității pe imagini reale, ele ocupă doar o mică parte a imaginii. De exemplu, să luăm bine imaginea de testare Lenna în tonuri de gri. Dacă luăm o matrice de luminanță de pixeli sale, atunci o parte din prima linie va apărea ca o secvență de numere 154, 155, 156, 157, 157, 157, 158, 156.

Pentru a obține zerouri, se poate aplica o așa-numită metodă delta. Pentru a face acest lucru, se păstrează numai primul număr, iar pentru celelalte sunt luate numai diferențele fiecărui număr de cel precedent cu semnul "+" sau ";".

Rezultatul este secvența: 154,1,1,0,0,1,2.

Dezavantajul codării delta este non-localitatea. Cu alte cuvinte, este imposibil să luăm doar o bucată din secvență și să aflăm care luminozități sunt codificate în ea, dacă toate valorile din fața ei nu sunt decodificate.

Pentru a depăși acest dezavantaj, numărul este împărțit în perechi și fiecare sunt jumătate din suma (v. A) și jumătate din diferența (v. D), m. F. Pentru (154.155) (156.157) (157.157) (158.156) au (154,5, 0,5) (156.5,0.5) (157,0.0), (157, -1.0). În acest caz, este întotdeauna posibil să se găsească valoarea celor două numere într-o pereche.

În cazul general, pentru transformarea discretă a wavelet-ului semnalului S, avem:

Această metodă discretă rezultă din cazul continuu al transformării wavelet Haar și este utilizată pe scară largă în diferite domenii ale procesării și comprimării informațiilor.

comprimare

După cum sa menționat deja, una dintre aplicatiile wavelet algoritm de transformare este metoda de compresie JPEG 2000 folosind Haar bazat pe vectorul de translație a doi pixeli în X și vectorul Y (X + Y) / 2 și (X - Y) / 2. Este suficient să se înmulțească vectorul inițial în matricea de mai jos.

Dacă există mai multe puncte, atunci luați o matrice mai mare cu matricele diagonale H. Astfel, vectorul original, indiferent de lungime, este procesat în perechi.

filtre

"Jumătățile" rezultate sunt valorile medii ale luminozității din perechile de pixeli. Adică valorile la conversia la o imagine ar trebui să dea o copie a acesteia, redusă cu un factor de 2. În acest caz, jumătate de sume medie de luminozitate, care este, "filtru" bursturi aleatoare ale valorilor lor și să joace rolul de filtre de frecvență.

Acum, să analizăm diferențele. Acestea "alocă" "spargere" între pixeli, eliminând componenta constantă, adică "filtrarea" valorilor cu frecvențe joase.

Chiar din transformarea wavelet-ului Haar de mai sus pentru "manechine" devine evident că este o pereche de filtre care împart semnalul în două componente: frecvență înaltă și frecvență joasă. Pentru a obține semnalul original, este suficient să reîncorporați aceste componente.

exemplu

Să ne comprimăm portretul foto (imaginea test Lenna). Luați în considerare un exemplu de transformare wavelet a matricei de luminozitate a pixelilor. Componenta de înaltă frecvență a imaginii este responsabilă pentru afișarea detaliilor mici și pentru descrierea zgomotului. În ceea ce privește frecvența redusă, acesta conține informații despre forma feței și modificările netede ale luminozității.

Particularitățile percepției umane asupra fotografiilor sunt de așa natură încât ultima componentă este mai importantă. Aceasta înseamnă că, în timpul comprimării, o anumită porțiune din datele de înaltă frecvență poate fi aruncată. Mai mult, are valori mai mici și este codificată mai compact.

Pentru a crește raportul de compresie, puteți aplica transformarea Haar de câteva ori la date cu frecvență redusă.

Aplicarea la matrice bidimensionale

Așa cum am menționat deja, o imagine digitală într-un calculator este reprezentată ca o matrice a valorilor intensităților pixelilor săi. Așadar, ar trebui să fim interesați de transformarea de tip wavelet bidirecțional Haar. Pentru ao implementa, pur și simplu trebuie să efectuați o conversie unidimensională pentru fiecare rând și fiecare coloană a matricei de intensitate a pixelilor imaginii.

Valorile apropiate de zero pot fi eliminate fără deteriorarea semnificativă a imaginii decodificate. Un astfel de proces este cunoscut ca o cuantizare. Și în acest stadiu, unele informații sunt pierdute. Apropo, numărul de coeficienți nulibili poate fi modificat, ajustând astfel raportul de compresie.

Toate acțiunile descrise rezultă într-o matrice care conține un număr mare de 0. Ar trebui să fie scrisă linie de linie într-un fișier text și comprimat de orice arhivator.

decodare

Transformarea inversă la imagine se face în conformitate cu următorul algoritm:

• arhiva este despachetata;
• se aplică transformarea Haar inversă;
• Matricea decodificată este transformată într-o imagine.

Avantaje față de JPEG

Când se analizează algoritmul Joint Photographic Experts Group sa spus că se bazează pe DCT. Această transformare este realizată în bloc (8 x 8 pixeli). Ca rezultat, dacă compresia este puternică, atunci structura blocului devine vizibilă în imaginea restaurată. Când se comprima folosind wavelets, această problemă este absentă. Cu toate acestea, pot apărea alte tipuri de distorsiuni, care arată ca niște valuri în apropierea muchiilor ascuțite. Se crede că astfel de artefacte sunt în medie mai puțin vizibile decât "pătratele" create atunci când se aplică algoritmul JPEG.

Acum știți ce sunt wavelet-urile, ce sunt și ce aplicație practică le-a fost găsită în procesarea și comprimarea imaginilor digitale.