Metode DE Compresie A Imaginilor

CAPITOLUL 1

REPREZENTAREA IMAGINILOR

1.1 Imaginile statice

1.1.1 Reprezentările vectoriale

1.1.2 Hărțile de biți (bitmap) sau hărțile de pixeli (pixmap)

1.1.3 Formate uzuale de fișiere

1.2 Funcții MATLAB pentru manipularea imaginilor

1.2.1 Tipuri de imagine

1.2.2 Exemple de prelucrari de imagini in MATLAB

1.3 Imagini dinamice

Formate uzuale de fișiere video

CAPITOLUL 2

METODE GENERALE DE COMPRESIE A IMAGINILOR STATICE

2.1 Tehnici de compresie a imaginilor

2.1.1 Măsuri de apreciere cantitativă

2.1.2 Măsuri de apreciere subiective

2.2 Algoritmul de compresie JPEG

2.2.1 Imparțirea imaginii în blocuri de 8×8

2.2.2 Transformarea Cosinus Discretă (DCT)

2.2.3 Prelucrarea în zig-zag

2.2.4 Cunatificarea

2.2.5 Codificarea binară

CAPITOLUL 3

METODE DE COMPRESIE A IMAGINILOR DINAMICE

3.1 Componenta MPEG Video

3.1.1 Algoritmul de bază

  3.1.2Reprezentarea secvențelor video

  3.1.3Predicția

3.2 Generalitati despre standardul MPEG-4

CAPITOLUL 4

PROIECTARE SOFTWARE ȘI REZULTATE EXPERIMENTALE

Implementarea programului

Rezultate experimentale

capitolul 6

CALCULUL ECONOMIC

6.1 Generalități

Costul Software – ului

6.3 Calculul economic pentru programe

50 pagini

Lipsa cap5

=== CAPITOLUL 1 ===

CAPITOLUL 1

REPREZENTAREA IMAGINILOR

Fie că este vorba de fotografii, grafice, ori de figuri animate sau clipuri video, imaginea este, alături de text și de sunet, componenta de bază a oricărui sistem multimedia modern.

Caracterizate prin marea cantitate de informație pe care o pot transmite extrem de rapid și de comod omului, imaginile – statice sau dinamice – ar trebui să fie mediul preferențial de comunicare a informației în sistemele multimedia.

De cealaltă parte a balanței atârna destul de greu costurile de producere a acestora, problemele tehnice legate de stocarea și manipularea lor cu ajutorul calculatorului și nu în ultimul rând, de faptul ca de multe ori interpretarea acestora este subiectivă.

Continuând subiectul "multimedia" articolul de fața trateaza problemele și soluțiile implicate de utilizarea în cadrul sistemelor multimedia a celui mai puternic purtător de informație – imaginea.

1.1 Imaginile statice

Imaginile statice sunt în general limitate ca și posibilitați de comunicare a diverselor tipuri de informații și se utilizează în special pentru a sublinia o anumită idee, sau pentru descrieri și exemplificari grafice.

1.1.1 Reprezentările vectoriale

Imaginile reprezentate vectorial sunt construite de obicei cu ajutorul unor primitive – instrucțiuni de desenare ca linie, dreptunghi, elipsă. Aceste primitive pot fi grupate impreună pentru a forma obiecte.

Toate imaginile reprezentate vectorial sunt generate de calculator prin utilizarea a diferite pachete software specializate, cum ar fi cele de Proiectare Asistată de Calculator (CAD – Computer Aided Design), folosite de catre arhitecți, de exemplu, sau pachetul de editare grafică "CorelDraw!". Într-o imagine reprezentată vectorial, toate primitivele grafice (linii, dreptunghiuri, elipse, arce de cerc, etc.) ce formează obiectele componente, sunt definite prin perechile de coordonate ale punctelor lor esențiale. De exemplu, pentru un dreptunghi, se vor defini perechile de valori (x1, y1) și (x2, y2), acestea fiind coordonatele a două colțuri diagonal opuse ale respectivului dreptunghi. Această informație e suficientă nu numai pentru a defini dimensiunile dreptunghiului in discuție, ci și poziția acestuia în cadrul imaginii. În plus, pentru fiecare primitivă grafică componentă se mai pot furniza informații suplimentare, cum ar fi culoarea conturului, culoarea interiorului, tipul de hasura pentru interior, etc.

Aceasta permite ca figuri complexe să poată fi stocate în fișiere foarte compacte. Dimensiunea acestor fișiere depinde în mod direct proporțional cu numarul de obiecte ce compun imaginea, iar un fișier cu multe obiecte componente nu este numai mare ca dimensiune, ci și necesită un timp mare pentru afișarea imaginii.

Modificarea dimensiunilor unei imagini reprezentate vectorial se poate face cu usurința și fără pierderi de informație, fiind vorba doar de operații de scalare a parametrilor primitivelor grafice componente.

Grafica vectorială poate fi utilizată pentru reprezentarea imaginilor "din realitatea inconjurătoare", dar acest lucru necesită o cantitate impresionantă de procesare, imparțirea în primitive grafice fiind foarte dificila.

1.1.2 Hărțile de biți (bitmap) sau hărțile de pixeli (pixmap)

Hărțile de biți, cunoscute de asemenea ca și grafică cu rastru (raster graphics), sunt formate dintr-o matrice de puncte denumite pixeli. De fapt, ele reprezinta aproape fidel, bit cu bit, conținutul memoriei video in momentul afisării imaginii respective pe ecranul monitorului. De exemplu, pentru o imagine monocromă (alb-negru), fiecărui punct fizic al imaginii îi corespunde un singur bit în matrice, pe rândul și coloana corespunzatoare poziției reale a acestuia din cadrul imaginii. Valoarea "0" a unui bit din matrice corespunde unui punct negru din imagine (stins) iar "1" corespunde unui punct alb (aprins).

Din exemplul de mai sus se deduce faptul ca matricea trebuie să includă și informații despre culoarea punctului corespondent din imagine. Acest lucru se traduce prin faptul că matricile de pixeli au – pe langă linii și coloane – și o a treia dimensiune: adâncimea de culoare a pixelului respectiv. De exemplu, pentru un număr total de 256 de culori dintr-o imagine, adâncimea de culoare necesară va fi 8. Rezultă un set de 8 matrici de tipul celei corespunzătoare unei imagini monocrome cu aceeași suprafață.Cele mai uzuale adâncimi de culoare sunt: 4 biți (16 culori), 8 biți (256 culori), 16 biți (32768 culori) și 24 biți (16.7 milioane culori).

Principalul avantaj al hărților de pixeli este ca pot stoca imagini reale până la cel mai mic detaliu. Principalul dezavantaj îl constituie necesarul foarte mare de spatiu de stocare. Acesta depinde de dimensiunile imaginii (pe x si pe y), cât și de numărul total de culori din imagine (rezultând "adâncimea de culoare" a reprezentării).

Dimensiunea – în număr de biți – a fisierului rezultat se obține prin înmulțirea celor trei parametri anteriori. Al doilea dezavantaj îl reprezintă degradarea imaginii reprezentate, dacă este redimensionată. În cazul micșorării dimensiunilor, o parte din pixeli se va inlătura, rezultând în pierdere de informație, iar dacă se măresc dimensiunile imaginii, vor trebui creati noi pixeli. Acest lucru se rezolvă uzual prin a-i atribui noului pixel o culoare apropiată de cea a vecinilor săi. Solutia tinde să genereze efectul de imagine compusă din blocuri.

Majoritatea pachetelor software specializate în editarea de imagini, pot genera reprezentări grafice tip rastru.

1.1.3 Formate uzuale de fișiere

GIF (GIF87a, GIF89a): GIF – Graphics Interchange Format, propus inițial de către corporația UNISYS si Compuserve, pentru transmiterea de imagini pe linii de telefon utilizând modem- urile. Implementează algoritmul de compresie Lempel-Ziv Welch, modificat puțin pentru grupări de pixeli de dimensiunea unei linii de scan. Utilizarea sa se limitează doar la imagini cu maxim 256 culori (adâncimea de culoare maximă: 8). Suportă intreteserea liniilor de imagine, putându-se trasa imaginea, plecând de la conturul complet și neclar al său, și mărind detaliul pâna când apare imaginea completă. Specificațiile GIF89a suportă efecte simple de animație și transparență.

JPEG: un standard pentru compresii de imagini statice, creat de Joint Photographics Experts Group. Metoda de compresie este de tip "cu pierderi", fiind concepută astfel încât să se profite de limitările în percepția video a ochiului uman. Permite setarea raportului calitate/compresie. Lucreaza cu aceeași adâncime de culoare, 24 (16.7 milioane de culori), indiferent de numarul total de culori din imagine. Este în momentul de fața unul dintre cele mai frecvent întâlnite formate de fișiere grafice.

TIFF: TIFF – Tagged Image File Format este capabil a stoca imagini de la cele monocrome și până la cele cu 16.7 milioane de culori. A fost conceput de corporația Aldus în anii 1980, după care a fost adoptat și de Microsoft. Tipul de compresie implementat – fără pierderi, fără posibilitatea de control a raportului calitate/compresie. Nu ofera nici un avantaj major fată de JPEG și pare să piardă din popularitate.

Post-Script si Encapsulated Post-Script: este mai degrabă un limbaj specializat în tipărirea la imprimantă, dezvoltat de firma Adobe. Include atât text, cât și grafică vectoriala și imagini tip hartă de biți.

BMP: Microsoft Windows Bitmap, este utilizat de pachetul software Microsoft Windows ca format grafic standard, putând lucra cu adâncimi de culoare de 24 (16.7 milioane de culori).

PICT: standard de format grafic utilizat de calculatoarele Apple Macintosh. Lucreaza cu reprezentări vectoriale de imagini.

XBM: XBM – X Window Bitmap, format grafic standard pentru sistemul X Window sub UNIX. Suportă hărți de biți cu adâncimi de culoare de până la 24 biți.

DXF: format vectorial de fisiere grafice utilizat de pachetele de proiectare asistată de calculator.

1.2 Funcții MATLAB pentru manipularea imaginilor

1.2.1 Tipuri de imagine

MATLAB suporta patru tipuri de imagine:

Imagini indexate

Imagini de intensitate

Imagini binare

Imagini RGB

Imagini indexate

O imagine indexată conține două tabele, o matrice de imagine și o hartă de culori. Harta de culori este un set ordonat de valori care reprezintă culorile din imagine.

Pentru fiecare pixel din imagine, matricea de imagine conține o valoare care este un index în harta de culori. Harta de culori este o matrice m x 3 de clasă double. Fiecare linie a matricei hărții de culori specifică valorile de roșu, verde și albastru (RGB) pentru o singură culoare:

culoare = [ R G B ]

R, G și B sunt scalari reali care variază între 0 (negru) și 1.0 (intensitate maximă). Relația dintre valorile din matricea imaginii și harta de culori este condiționată de apartenența la clasa double sau uint8 a matricei de imagine. Dacă matricea imaginii este de clasă double, valoarea 1 conduce spre prima linie din harta de culori, valoarea 2 indică linia a doua, ș.a.m.d.. Dacă matricea imaginii este de clasă uint8, există o diferență: valoarea 0 indică prima linie din harta de culori, valoarea 1 indică al doua linie, ș.a.m.d.. Convenția uint8 este de asemenea folosită în formatul fișierelor grafice, și face posibil ca imaginea indexată pe 8 biți să suporte până la 256 de culori.

Imagini de intensitate (imagini cu nivele de gri)

MATLAB memorează imaginea de intensitate ca matrice unică, fiecărui element al matricii corespunzându-i un pixel imagine. Matricea poate fi de clasa double, în acest caz ea conținând valori cuprinse în intervalul [0,1]. Când matricea este de clasă uint8, intervalul este [0,256]. Elementele din matricea de intensitate reprezintă diferite intensități, sau nivele de gri, unde intensitatea 0 reprezintă negrul și intensitatea 1 (sau 255) reprezintă intensitatea maximă, sau albul.

Imagini binare

Într-o imagine binară, fiecare pixel primește doar una dintre cele două valori discrete, 0 sau 1. Aceste două valori corespund stărilor inactiv (off) și activ (on). O imagine binară este memorată ca o matrice bidimensională de 0-uri (pixeli inactivi) și 1-uri (pixeli activi). Această poate fi considerată un tip special de imagine de intensitate, conținând numai negru și alb. Imaginea binară poate fi depozitată într- un vector de clasă double sau uint8. Totuși un vector uint8 este preferabil, deoarece necesită mult mai putină memorie. În pachetul Prelucrarea Imaginilor, toate funcțiile care proiectează o imagine binară, o proiectează ca un vector logic uint8. Pachetul de programe folosește prezența unui indicator logic pentru a marca dacă datele sunt cuprinse în intervalul [0,1] (dacă indicatorul logic este inactiv, pachetul de programe folosește intervalul de date [0,255]).

Imagini RGB

Ca și imaginea indexată, o imagine RGB reprezintă fiecare pixel de culoare ca un set de 3 valori, constând în intensitățile de roșu, verde și albastru care alcătuiesc culoarea. Spre deosebire de imaginea indexată, aceste valori de intensitate sunt stocate direct în vectorul imagine, nu indirect în harta de culori. În MATLAB componentele de roșu, verde și albastru ale unei imagini RGB rezidă într-o tabela unică de tip m x n x 3, m și n reprezentând numerele de linii și coloane ale pixelilor din imagine, iar a treia dimensiune presupune trei planuri, conținând valori intensitate de roșu, verde și albastru. Pentru fiecare pixel din imagine elementele de roșu, verde și albastru se combină pentru a crea culoarea reală a pixelului. De exemplu pentru a determina culoarea pixelului (112,86), este necesar a se cerceta tripletul RGB stocat în (112,86,1:3). Să presupunem că (112,86,1)conține valoarea 0.1238, (112,86,2) conține 0.9874 și (112,86,3) conține 0.2543. Culoarea pixelului este:

0.1238 0.9874 0.2543

O tabelă RGB poate fi de clasă double, în acest caz ea conținând valori în intervalul[0,1], sau de clasă uint8, în acest caz intervalul de date fiind [0,255].

1.2.2 Exemple de prelucrari de imagini in MATLAB

Afișarea de imagini.

Transformata cosinus discretă

Conversia imaginilor

Afișarea de imagini

Se urmărește descrierea unor funcții de afișare a imaginilor. De exemplu, funcția imshow afișează orice tip de imagine la o singură apelare de funcție.

Afișarea unei imagini reprezentate matriceal .

Sintaxa principală a funcției imshow este: imshow (filename)

Această comanda afișează imaginea stocată în fișierul grafic filename. Pentru a realiza acest lucru, imshow apelează funcția imread pentru a citi informația din fișierul grafic filename. De exemplu:

imshow(’flowers.tif ’)

sau

I = imread(’ flowers.tif ’);

Imshow

Afișarea imaginilor multiple (subimage)

Aceasta funcție afișează mai multe imagini în cadrul aceleiași figuri. Pentru a realiza acest lucru, subimage se folosește alături de subplot. Exemplu:

load trees

[X2, map2] = imread('forest.tif');

subplot(1,2,1), subimage(X,map)

subplot(1,2,2), subimage(X2,map2)

Transformarea cosinus discretă(DCT)

DCT este adesea utilizată în aplicațiile de compresie a imaginilor. De exemplu, DCT stă la baza algoritmului internațional standard pentru compresia imaginilor, cunoscut sub numele de JPEG. Codul exemplificat mai jos calculează DCT bidimensională pentru blocuri 8×8 în imaginea de intrare; se păstrează numai 10 dintre cei 64 de coeficienți DCT din fiecare bloc, apoi reconstruiește imaginea utilizând inversa DCT bidimensională a fiecărui bloc.

I = imread ('cameraman .tif');

I = double ( I ) / 255;

T = dctmtx ( 8 );

B = blkproc ( I , [ 8 8 ] , 'P1 * x * P2' , T , T ');

mask= [ 1 1 1 1 0 0 0 0

1 1 1 0 0 0 0 0

1 1 0 0 0 0 0 0

1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0];

B2 = blkproc ( B , [ 8 8 ] , 'P1 . * X' , mask );

I2 = blkproc ( B2 , [ 8 8 ] , 'P1 * X * P2' , T , T' );

imshow ( I ), figure, imshow ( I2 )

Comenzile de mai jos calculează transformata cosinusoidală discretă pentru o imagine. Notăm că majoritatea energiei se află în colțul stânga sus.

RGB=imread('autumn.tif');

I = rgb2gray (RGB);

J = dct2 (I);

imshow (log (abs (J) , [ ] ), colormap ( jet ( 64 ) ), colorbar

Conversia imaginilor în alte tipuri de imagine

Pentru anumite operații, este folositor ca o imagine să fie convertită într-un tip diferit de imagine. De exemplu, dacă vrem să filtrăm o imagine colorată care este stocată ca imagine indexată, trebuie ca în primul rând să o convertim în format RGB, MATLAB filtrind valorile de intensitate ale imaginii. Dacă încercăm să filtrăm imaginea indexată, MATLAB doar va aplica filtrul indicilor din matricea imaginii indexate, și rezultatul nu ar avea nici un sens. Pachetul de programe oferă câteva funcții care fac posibilă convertirea oricărei imagini într-un alt tip de imagine. De exemplu, ind2gray convertește o imagine indexată într-un format cu nivele de gri. A se remarca faptul că atunci când se convertește o imagine dintr-un format în altul, imaginea rezultată poate apărea diferită față de original. De exemplu, dacă se convertește o imagine indexată de culoare într-o imagine de intensitate, imaginea rezultată este o imagine cu nivele de gri, nu colorată. Tabelul de mai jos rezumă aceste funcții ale conversiei de imagine:

Funcția Scop

Dither Crearea unei imagini binare dintr-o imagine cu nivele de gri sau a unei imagini indexate dintr-o imagine RGB (dithering)

Gray2ind Crearea unei imagini indexate dintr-o imagine cu nivele de gri

Grayslice Crearea unei imagini indexate dintr-o imagine cu nivele de gri, prin utilizarea unui prag

im2bw Crearea unei imagini binare dintr-o imagine de intensitate, imagine indexată sau imagine RGB bazată pe un prag de luminozitate

ind2gray Crearea unei imagini cu nivele de gri dintr-o imagine indexată

ind2rgb Crearea unei imagini RGB dintr-o imagine indexată

mat2gray Crearea unei imagini cu nivele de gri, folosind datele dintr-o matrice

rgb2gray Crearea unei imagini cu nivele de gri dintr-o imagine RGB

rgb2ind Crearea unei imagini indexate dintr-o imagine RGB

Exemplu: Conversia unei imagini de intensitate intr-o imagine indexată

I=imread(’rice.tif ’);

[X, map]=gray2ind(i,100);

imshow(I)

figure,imshow(X)

1.3 Imagini dinamice

Formate uzuale de fișiere video

La fel ca in cazul imaginilor statice, și aici există o varietate destul de mare de formate video digitale, majoritatea fiind concepute de companii comerciale. Din cauza ca fișierele ce conțin video sunt foarte mari, toate tipurile de formate includ o formă de compresie a datelor, iar formate ca AVI(Audio Video Interleaved – formatul Microsoft pentru video sub Windows) sau QuickTime al luiApple utilizează mai multe tipuri diferite de compresie.

Standardul ISO pentru compresia video se numeste MPEG (Moving Pictures ExpertsGroup). Standardul prevede existența a trei tipuri de cadre: I (Intra), P (Prezise) și B(Bidirectionale).

Cadrele I sunt codificate ca imagini statice, utilizând metoda DCT (Direct Cosine Transform – transformata cosinus directa). Cadrele P se obțin printr-un algoritm de predicție din cel mai recent cadru I sau P. Cadrele B sunt prezise din cele mai apropiate doua cadre I sau P(anteriorul si urmatorul). O secvența tipică de cadre ar putea fi: "IBBPBBPBBPBBIBB…". Din cauză că pentru a decodifica un cadru B se cer cadrele I sau P anterioare și ulterioare acestuia, cadrele nu sunt transmise în ordine secvențială.

Formatul MJPEG sau Moving JPEG specifică faptul ca video-clipul este stocat în fisier cadru cu cadru, fiecare cadru fiind comprimat cu metoda JPEG.

Formatul DVI este un standard bazat pe chipset-ul Intel i750, și a fost utilizat de un numar de placi de captură video, cum ar fi de exemplu Action Media. În prezent este considerat depăsit.

Un alt standard specificat de ISO (International Standards Organization) pentru compresii video este "H.261". Este conceput a fi utilizat în aplicatii de video-conferință, unde cadrele video de obicei constau în imagini cu bustul participanților la conferință. Informația de la un cadru la altul nu se schimbă prea mult astfel ca predicția unuia din celelalte anterioare lui poate conduce la rate de compresie ridicate.

=== CAPITOLUL 2 ===

CAPITOLUL 2

METODE GENERALE DE COMPRESIE A

IMAGINILOR STATICE

De ce este necesară compresia imaginilor? – Deoarece pentru reprezentarea unei imagini în format numeric (în scopul transmiterii sau stocării) este necesară o cantitate foarte mare de informație. Să luăm de exemplu cazul unei imagini cu o rezoluție 640×480 pixeli, imaginea conține 307200 puncte, fiecare punct necesitând 24 biți (pentru o reprezentare de calitate a culorii). Rezultă o dimensiune de 921600 octeți (900KB) ceea ce este destul de mult.Din acest motiv cel mai frecvent imaginile se codifică într-o formă comprimată existând în momentul de față un număr mare de tehnici de compresie și un număr și mai mare de formate (GIF, JPEG, WIF…).

2.1 Tehnici de compresie a imaginilor

Metodele de compresie pot fi clasificate în următoarele categorii:

metode care elimină redundanță informațională a imaginii de bază;

metode care elimină irelevanța informațională bazându-se pe modelul percepției vizuale a omului, deci a porțiunilor sau parametrilor imaginii care nu sunt percepute de om;

metode care trunchiază imaginea originală, astfel încât imaginea refacută după compresie este o aproximație a imaginii originale.

Algoritmii de compresie folosesc una sau mai multe tehnici din categoriile menționate anterior.

Din punctul de vedere al pierderii de informație, metodele de compresie pot fi:

fără pierdere de informație; se mai numesc metode de compresie reversibile sau cu păstrarea biților (bit-preserving). Aceste metode se pot folosi în cazul imaginilor din aplicațiile medicale, când nu este permisă o degradare a informației bilologice reprezentate de pixeli, întrucât altfel pot afecta diagnosticul. Rapoartele de compresie sunt foarte mici și nesemnificative. Există 3 strategii de bază: codarea plană a biților, codare predictivă fără pierdere de informație și codarea fără erori a diferențelor. Compresia fără pierdere de informație pleacă de la reprezentarea binară a imaginilor și se aplică unul din algoritmii de codare entropică: Huffman sau Lempel-Ziv. Nu se admite pierdere de informație. Rata de compresie depinde de algoritmul entropic folosit și nu este foarte mare. Aplicațiile importante ale acestui tip de compresie se referă la imaginile binare (Fax) și imagini medicale.

cu pierdere de informație, cunoscută și sub numele de compresie ireversibilă. Imaginea reconstruită nu este identică cu imaginea originală. Se pot obtine rapoarte de compresie mai mari. Raportul de compresie este cu atat mai mare cu cât gradul de distorsiune acceptat este mai mare.

Orice componentă a unei metode de compresie cu pierdere de informație poate fi implementată într-o manieră adaptivă sau ne-adaptivă. O schemă de compresie este adaptivă dacă structura (numarul și/sau valorile parametrilor) se schimbă local în cadrul imaginii pentru a folosi anumite particularitați ale statisticii locale. Metodele adaptive oferă performanțe mai bune dar cu cresterea complexitații.

Dupa tipul imaginii de intrare pot fi:

imagini binare (cum sunt cele de tip text);

continue (8 biti video, 12-biți medicale).

Figura de mai jos reprezintă clasificarea tehnicilor de compresie a imaginilor.

Figura 2.1- clasificarea tehnicelor de compresie a imaginilor

2.1.1 Măsuri de apreciere cantitativă

Măsurile de apreciere cantitativă nu sunt cei mai importanți în evaluarea calitații unei imagini reconstruite după compresie. Se folosesc numai pentru evaluarea eficienții codării a diferiților algoritmi. Măsurile de bază se bazează pe rapoartele semnal-zgomot și pe eroarea medie pătratică. Fie o imagine de dimensiune NxM. Fie s(i,j) intensitatea imaginii în punctul aflat la intersecția liniei i cu coloana j și intensitatea imaginii refăcute în același punct.

Următoarele mărimi sunt cele mai importante:

Eroarea medie pătratică (MSE = Mean Square Error)

(1)

Eroarea medie pătratică normalizată (NMSE = Normalized Mean Square Error) se obține prin raportare la energia semnalului de la intrare

(2.a)

sau prin raportare la intensitatea imaginii vârf-vârf

(2.b)

Pentru o imagine cu rezoluție de 8 biti PCM, xpp este 255. Dacă se consideră și momentele de timp prin indicele k, se poate calcula eroarea medie pătratică pe un domeniu de timp caracterizat de P momente cu relația:

(3)

Eroarea medie absolută (MAE = Mean Absolute Error)

(4)

Eroarea medie absolută normalizată (NMAE = Normalized Mean Absolute Error)

(5)

Coeficientul de corelație normalizat (NCC = Normalized Correlation Coefficient)

(6)

care trebuie să fie 1 pentru o reconstrucție ideală.

2.1.2 Măsuri de apreciere subiective

Pentru evaluări subiective, se consideră un grup de observatori, considerând că sunt experți în codarea imaginilor, analizează imaginile originale și procesate în condiții de iluminare și de distanță adecvate.Se calculează, ca și în cazul audio, un scor mediu al opiniilor (MOS) pe baza unei scări de apreciere, așa cum este – de exemplu – în tabelul 1.

Tabel 1 – Exemplu de scară de apreciere subiectivă

Exemplu: Figura de mai jos prezintă 4 imagini in format “jpg” in format gray (8 biti), deci de la 0 la 255. Dimensiunile matricilor ce reprezintă imaginile sunt de 200 x 200. Imaginile au indicii de calitate, dupa formatul jpg, de 90%, 40, 10% si 1%. Se prezintă, de asemenea, valorile masurilor de apreciere cantitativă a calității: NMSE, NMSEp, NMAE și NCC.

Figura 2.2 – Imagini cu diferite calitați: 90, 40, 10 si 1% din imaginea de referință

Figura 2.3 – Valorile celor mai importante măsuri cantitative

2.2 Algoritmul de compresie JPEG

JPEG (Joint Photographic Experts Group) este unul dintre cei mai eficienți algoritmi de compresie al imaginilor fotografice.Algoritmul a apărut în 1987 ca rezultat al echipei PEG (Photographic Experts Group) ce avea ca scop conceperea de standarde pentru transmiterea de imagini prin rețele mari de calculatoare.

JPEG este un algoritm de compresie a imaginilor cu pierdere de informație: între imaginea restaurată (după compresie ) și cea originală există mici diferențe, neobservabile însă cu ochiul liber.Aceasta este de fapt principala caracteristică exploatată de algoritm,datorită căreia fisierele JPEG au lungime atât de mică.

Este posibil ca și imaginea să rămână neschimbata(să nu existe pierdere de informații),însă în acest caz, algoritmul își va pierde mult din eficiență.

Fazele algoritmului JPEG:

2.2.1 Imparțirea imaginii în blocuri de 8×8

Pentru a putea fi prelucrată imaginea grafică este împărțită mai întâi în blocuri de 8×8 puncte. Blocurile sunt analizate de la stânga la dreapta și de sus în jos, până când întreaga imagine este parcursă.

Următorul pas constă în transformarea valorilor punctelor în frecvențe.

2.2.2 Transformarea Cosinus Discretă (DCT)

Transformata DCT este utilă la compresia imaginilor. Relațiile de calcul sunt:

,

,

În notație matricială:

.

Refacerea informației originale înseamnă

Fiecare matrice de bază este produsul a doi vectori de bază. Fiecare matrice de bază poate fi considerată ca o imagine. În figura 2 se prezintă cele 64 de matrici de bază. (Se recomandă scalarea matricilor de baza pentru folosirea întregului domeniu de variație al nivelului de gri [0 255] pentru [min max], la reprezentarea pe 8 biți a valorii unui pixel).

Figura 2.4 – Matricele de bază ai transformatei cosinus bidimensionale, n=8

Fiecare matrice de bază este caracterizată de o frecvență spațială, orizontală și verticală. Matricile din figură sunt aranjate de la stânga la dreapta și de sus în jos în ordinea crescătoare a frecvențelor.

Fiecare pixel din imaginea DCT descrie ponderea fiecarei matrici de bază în semnalul (imagine) de la intrare. Pixelii sunt aranjați, în ordinea crescătoare a frecențelor de la stânga la dreapta și de sus în jos. Cel mai strălucitor pixel din coltul din dreapta sus este cunoscut ca termenul de curent continuu, sau componenta medie, cu frecvența {0,0}.

El este media pixelilor de la intrare, și este – tipic – cel mai mare coeficient în DCT al imaginilor naturale.

Figura 2.5 – Compresia unei imagini prin DCT; raportul de compresie este

20

2.2.3 Prelucrarea în zig-zag

După calcularea frecvențelor se va observa un lucru foarte interesant: dacă frecvențele sunt dispuse într-o matrice 8×8,adică la fel ca și blocul inițial atunci se va observa ca valorile cele mai mari ale frecvențelor se vor înregistra în colțul din stăâga-sus , iar cele mai mici în colțul din dreapta-jos,

Prin prelucrarea în zig-zag obținem un șir de frecvențe aranjate relativ în ordine descrescătoare, prima valoare având valoarea medie a intensității blocului de 8×8 puncte, ultimele având valori apropiate de 0.

Figura 2.6 – Parcurgere în zig-zag

2.2.4 Cunatificarea

În cadrul acestei faze, fiecare frecvență va fi cuantificată, utilizând un coeficient care se găsește într-unul din tabelele JPEG de cuantificare. Fiecare din cele 64 de frecvențe este impărțită la un ” coeficient de cuantificare ” (C.C) și rezultatele sunt rotunjite la întregi.

Acesta este un pas fundamental în care se pierde informație.Un C.C. egal cu 1 nu implică nici o pierdere de informație; cu cât C.C. este mai mare, cu atât pierderea de informație este mai mare.

Toți cei 64 de C.C. reprezintă parametri ai procesului de compresie, alegerea celor mai potrivite valori pentru ei fiind extrem de dificilă.Multe din programele de codificare JPEG existente folosesc în acest pas valorile din tabelele standardului JPEG (sau multipli ale acestora).

Aceste tabele au fost astfel elaborate încât dacă , frecvențele au valori apropiate , ele sa rămână neschimbate iar în cazul existenței unei frecvențe cu valoare mai deosebită, aceasta să fie transformată într-o valoare convenabilă algoritmului de compresie binară ce va urma.

Urmatoarea matrice de cuantizare este folosită intens pentru imaginile mono-crome și pentru componenta de luminanță a imaginii color. Ea se folostește în compresia JPEG. Vizualizând matricea pe o scară a nivelelor de gri se vede dependența factorilor de cuantizare de frecvență.

La efectuarea compresiei, se transformă matricea în blocuri și se cuantizeaza fiecare bloc. La de-compresie se înmulțește fiecare bloc cu matricea de cuantizare și se obține imaginea reconstruită.

2.2.5 Codificarea binară

Se codifică coeficienții reduși folosind codificarea Huffman sau codificarea aritmetică. Acest pas este fără pierderi, el nu afectează calitatea imaginii.

Codarea Huffman

Compresia dinamică (sau adaptivă) Huffman folosește un arbore de codare ce este actualizat de fiecare dată când un simbol este citit din fișierul de intrare. Arborele crește (se dezvoltă, evoluează) la fiecare simbol citit din fișierul de intrare. Modul de evoluție al arborelui este identic la compresie și la de-compresie. Eficiența metodei se bazează pe o proprietate a arborilor Huffman cunoscută sub numele de proprietatea „copiilor” („sibling property”)

Proprietate (sibling): Fie T un arbore huffman cu n frunze. Atunci nodurile lui T pot fi aranjate într-o secvență (x0, x1, …, x2n-2) astfel încât:

Secvența ponderilor (weight(x0), weight(x1), …, weight(x2n-2)) să fie în ordine descrescătoare;

Pentru orice i (0 ≤ i ≤ n-2) , nodurile consecutive x2i+1 și x2i+2 sunt siblings (fii ai aceluiași părinte).

Compresia și decompresia utilizează arborele dinamic Huffman pornind de la un caracter virtual, nototat – de exemplu – prin VIRT, sau ART. Acesta este întotdeuana nod terminal (frunza).

Descrierea codarii: de fiecare data când un simbol este citit din fișierul de intrare se efectuează următoarele operații:

1). se scrie în fișierul destinație codul simbolului: dacă simbolul citit este nou, atunci se scrie codul caracterului virtual (VIRT) (determinat din arborele de codare ) urmat de codificarea în binar (ASCII) pe 9 biți a caracterului; în caz contrar se scrie cuvântul de cod al simbolului, determinat din arborele de codare.

2). Se introduce simbolul citit în arborele de codare: dacă simbolul curent citit este nou, atunci din nodul virtual vor pleca doi fii: unul pentru simbolul citit și unul pentru simbolul virtual. Nodul care a fost folosit ca nod virtual devine nod intermediar; în caz contrar, se incrementează frecvența de apariție a acestuia, prin mărirea ponderii nodului corespunzător simbolului citit;

3) Se ajustează arborele pentru îndeplinirea proprietății sibling. Trebuie considerate următoarele două aspecte:

la creșterea ponderii unui nod, frunza sau intermediar, trebuie modificate și ponderile ancestorilor sai;

pentru a păstra ordinea descrescătoare a ponderilor se judecă astfel: fie nodul frunză n ce are ponderea cu unu mai mare decât anterior, deci el este cel care s-a modificat la pasul curent. Pentru îndeplinirea condiției (1) a proprietății sibling, nodul n este schimbat cu cel mai apropiat nod m (m < n) din lista, astfel încât weight(m) < weight(n). Apoi, aceeași operație este efectuată asupra părintelui lui n, până când se obține nodul rădăcina sau este îndeplinită condiția (1).

De obicei se numerotează nodurile iar corespondența număr nod – etichetă se obține folosind un vector ale cărui elemente sunt chiar etichetele arborelului de codare.

Descrierea de-codării: La decompresie, textul comprimat este verificat cu arborele de codare. Tehnica se numeste „parsing”. La începutul decompresiei, nodul curent este inițializat cu rădăcina, ca la algoritmul de compresie, și – apoi – arborele evoluează simetric. La fiecare citire a unui simbol 0 se parcurge arborele în jos spre stanga; se parcurge arborele spre dreapta dacă simbolul citit este 1. Cand se ajunge la un nod terminal (frunza) simbolul asociat este scris în fișierul de ieșire și se ajustează arborele, la fel ca în faza de compresie.

Codarea aritmetică

Codarea aritmetică elimină necesitatea codarii fiecarui simbol al alfabetului sursei. În timpul codării algoritmul generează un cod pentru întreg mesajul de intrare, lucru ce este facut în mod secvențial, simbol cu simbol.

În comparație cu alte câmpuri din sfera codarii, codarea aritmetică este foarte tânără (1970), matură și completă și eficientă în compresia fără pierdere de informație.

Folosirea reprezentării binare pe un numar fix de simboluri este suficientă pentru toate calculele. Mai mult, raportul de compresie obținut este mai bun decât în cazul folosirii codului Huffman .

Descrierea algoritmului de bază:

Se consideră intervalul curent [L,H) inițializat cu [0,1).

Pentru fiecare simbol, ai, din fișier, se parcurg doi pași:

2.1: Se împarte intervalul curent în subintervale, câte unul pentru fiecare simbol din alfabetul sursei; marimea subintervalului unui simbol din alfabet este proporțional cu probabilitatea estimată, considerată în cadrul modelului.

2.2: Se selectează subintervalul corespunzator simbolului care apare în fisierul de comprimat, și se consideră ca fiind noul interval curent.

Se scriu în fișierul comprimat suficiente simboluri binare pentru a putea identifica (reconstitui) intervalul curent final din mulțimea tuturor intervalelor finale, posibil a fi considerate.

Observatii:

1). O descriere geometrică a evoluției mărimii și locului intervalului curent este prezentată în figura 2.7.

Figura 2.7- Diviziunea intervalului curent este bazată pe probabilitatea simbolului de intrare ai, care apare în fișierul de comprimat

Fie sursa dată prin distribuția

Figura 2.8 arată modul de realizare a partițiilor pentru mesajul „iou”.

Figura 2.8 – Reprezentarea codarii aritmetice a secvenței „iou”. Caracterele succesive determină subdiviziune din ce in ce mai fine ale intervalului inițial, [0,1). (dupa Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING – ISBN 0-521-43108-5)

2). Lungimea intervalului final este egală cu produsul probabilitaților simbolurilor individuale ce apar în fișierul/secvență de comprimat

unde Ns este numărul de simboluri din fișierul de intrare (cel care trebuie comprimat).

3). Se calculează numarul de biți care trebuie memorați în fișierul comprimat (cel de ieșire) după relația

[biti]

unde paranteza are semnificația de parte întreagă, obținută prin rotunjire. În acest fel, numărul de biți generați de codarea aritmetică este egal cu entropia, H (evident, daca nu se consideră rotunjirea). În acest fel, codarea aritmetica atinge compresia care este indicată de entropia sursei, de este optimală.

4). Trebuie introdus un simbol suplimentar în alfabetul sursei, pentru a indica sfarșitul de fișier.

5). La pasul 2 al algoritmului se calculeaza în mod efectiv numai subintervalul corespunzător simbolului care apare în fișier, de exemplu ai. Sunt necesare probabilitățile cumulative

Fie k indicele alfabetului și i indicele simbolurilor mesajului/secvenței. Relațiile de calcul ale sub-intervalului nou sunt

unde L’ și H’ sunt limitele intervalului curent. Pentru primul pas se consideră L=0 și H=1;

6). Intersecția intervalelor obținute este vidă pentru simboluri diferite, deci

7) În mod curent, codarea aritmetică poate fi implementată sub forma a două module, care separă modelul sursei de procesul de codare. Modelul sursei este un modul de program și este consultat atat de codor cât și de decodor, la fiecare pas al procesării. Posibilitatea separării modelului în două sub-modele, unul pentru estimarea probabilităților și unul pentru codare, permite cuplarea codării aritmetice cu orice metodă statica sau dinamică de estimare a probabilitaților (sau frecvențelor) mesajelor sursei.

8). Pentru realizarea decodării trebuie să se cunoască modelul sursei utilizate de codor (mesajele și intervalele asociate) și un singur număr din intervalul determinat de codor. Decodarea constă într-o serie de comparații a numărului i cu valorile reprezentând mesajele sursei.

Decodarea aritmetică

Pentru a decoda o secvență, trebuie aplicate operațiile efectuate la codare însă în ordine inversă. Se cunosc:

-modelul sursei, prin alfabet și probabilități;

-secvența/mesajul codat sub formă de interval sau sub forma mediei intervalului, V;

-numarul de simboluri primare din secvența codată.

Algoritmul va parcurge doi pași:

1). Se compară media intervalului cu fiecare din intervalele inițiale (așa cum s-a făcut la codare) și se determină simbolul căruia îi aparține intervalul găsit.

2) Se caută urmatorul simbol prin modificarea probailității partiției, așa cum s-a făcut și la codare:

unde i trebuie să fie ales astfel încât să fie îndeplinită inegalitatea

deci ai este următorul simbol din secvența codată.

=== CAPITOLUL 3 ===

CAPITOLUL 3

METODE DE COMPRESIE A IMAGINILOR DINAMICE

Secventele video contin o redundantă mare, atât statistică cât și subiectivă, atât în interiorul fiecărui cadru cât și între cadre. Scopul codării surselor video este reducerea ratei de informație (numită și rată de bit) pentru stocare și transmisie, prin exploatarea redundanțelor statistice și subiective și de a codifica informatia de imagine folosind tehnici entropice (bazate pe entropie).

Raportul de compresie depinde de redundanța conținută în mesaj precum și de tehnica de compresie folosită. Pentru tehnicile de compresie un rol important îl are disponibilitatea tehnologiei VLSI pentru implementarea algoritmilor de compresie.

Există două tehnici de codare a surselor video: cu si fără pierdere de informație. Scopul codării fără pierdere de informație este de a reduce mărimea imaginii pentru stocare și/memorare cu menținerea calității imaginii originale, astfel încât calitatea imaginii decodate să fie egală cu calitatea imaginii originale. În contrast, tehnicile de codare cu pierdere de informație, (MPEG-1, MPEG-2 si MPEG-4) au scopul de a a obține o anumită rată de informație pentru stocare și/sau memorare. Criteriile de optimizare folosite la compresie au două componente: una obiectivă, care se referă la măsura informațională, și o componentă subiectivă, care se referă la percepția aparatului vizual al omului.

3.1 Componenta MPEG Video

MPEG (Moving Pictures Experts Group) este un comitet internațional de standardizare, specializat în standardizarea compresiei datelor audio și video. Pornindu-se inițial de la metode de compresie video pentru rate de 1.2 MBps având ca mediu de stocare CD-ROM-ul, standardele MPEG sunt în prezent cele mai uzitate instrumente pentru compresia audio-video de înaltă calitate

3.1.1 Algoritmul de bază

În figura 3.1 este prezentată diagrama bloc a codorului MPEG (a), respectiv decodorului MPEG Video (b).

a) schema bloc a codorului MPEG Video

b) schema bloc a decodorului MPEG Video

  Figura 3.1 Schema bloc a codorului/decodorului MPEG Video

Așa cum se poate observa din figura 1.a, intrarea video este prevăzută cu un bloc de preprocesare (interpolare și filtrare), urmată de blocul de estimare a mișcării folosit pentru determina predictorul imaginii (cadrului) curente, din cadrele transmise anterior.

Vectorii de mișcare reprezintă o parte de informație și sunt transmiși blocului de codare entropică. Predictorul este scăzut din fiecare bloc în parte, rezultând eroarea de predicție care este trimisă blocului transformării cosinus discrete DCT. Coeficienții DCT sunt cuantizați în blocul de cuantizare și apoi codați entropic pentru a putea fi transmiși.

Totodată coeficienții cuantizați sunt folosiți pentru a reconstrui cadrele de referință. Aceștia sunt trimiși blocului de cuantizare inversă (decuantizare), urmat apoi de blocul transformării cosinus inverse IDCT, și adunate apoi cu eroarea de predicție. În felul acesta se obține un cadru de referință (asemănător cu cel obținut la decodare) folosit pentru viitoarea estimare a mișcării. Decodorul MPEG video conține un bloc care realizează decodarea entropică, urmat apoi de blocul de cauntizare inversă (decuantizare) și respectiv blocul transformării cosinus inverse IDCT. Informația obținută de la ieșirea acestui bloc este sumată cu cadrul de referință. La ieșirea sumatorului avem cadrul curent refăcut.

Acesta este trecut în final printr-un bloc de postprocesare (interpolare și filtrare).

  3.1.2Reprezentarea secvențelor video

Secvențele video care vor fi prelucrate în procesul de compresie MPEG se compun dintr-o succesiune de cadre și câmpuri de luminanță și crominanță.

Reprezentarea pe cadre

Standardul MPEG-1 folosește doar reprezentarea pe cadre a semnalului video digital. Fiecare cadru constă din trei plane de pixeli, unul pentru luminanță (Y, alb-negru) și celelalte două pentru crominanță (câte unul pentru fiecare componentă CR, CB). Cele trei plane de pixeli se pot obține din semnalele primare R, G, B folosind același algoritm de descompunere ca și în televiziunea clasică.Pentru MPEG-1 cele două plane de crominanță sunt eșantionate cu un factor egal cu 2 atât pe orizontală cât și pe verticală, relativ la planul de luminanță.

Deoarece standardul MPEG-1 nu specifică modul de subeșantionare, se poate considera ca metodă implicită cea prezentată in figura 3.2.a.

Standardul MPEG-2 specifică subeșantionarea orizontală prescrisă de CCIR-601, ceea ce din punct de vedere spațial implică o reprezentare asemănătoare celei din figura3.2.b.

a) b)

Figura 3.2 Relația spațială între luminanță și crominanță subeșantionată pentru:

a)      standardul MPEG-1

b)      standardul MPEG-2

Reprezentarea pe câmpuri

Standardul MPEG-2 este optimizat pentru o serie largă de aplicații, incluzând cele care folosesc reprezentarea pe câmpuri.

Câmpurile sunt create prin divizarea fiecărui cadru în două câmpuri (semicadre) întrețesute, ce conțin liniile (rândurile) pare respectiv impare dintr-un cadru. Câmpurile sunt întrețesute unul după altul și se succed la intervale de timp egale cu durata unui cadru.

Se exploatează aici faptul că HVS (Human Visual System) este mai puțin sensibil la frecvențele spațiale și temporale înalte. Această metodă de întrețesere este în de fapt o metodă de compresie a semnalului video digital.

  3.1.3Predicția

Predicția temporală exploatează redundanța care există între două cadre succesive dintr-o secvență video. De exemplu, putem avea o secvență video în care fundalul nu se modifică, modificându-se doar poziția anumitelor obiecte din prim-plan. În acest caz prin aplicarea unui simplu algoritm de codare DPCM (Differential Pulse Code Modulation) se poate obține un grad mare de compresie. Acest algoritm de predicție folosește ca predictor pentru imaginea curentă, imaginea anterioară și se face o scădere între cele două imagini.

Totuși există și secvențe video în care întregul conținut al imaginii se modifică de la un cadru la altul. În astfel de cazuri se poate aplica un algoritm de estimare al mișcării obiectelor, care să poată fi folosit pentru predicția imaginii curente. Nu întotdeauna algoritmul de estimare al mișcării folosit pentru predicția cadrului curent este eficient. Spre exemplu, va fi greu să determinăm particularitățile de mișcare în cazul în care o imagine se rotește sau este zoom-ată.

  Compensarea mișcării

Modelul de mișcare folosit în standardul MPEG este cel al translației blocurilor de pixeli. Pentru simplitate s-a ales dimensiunea blocului ca fiind 16×16 pixeli, pentru componenta de luminață și 8×8 pixeli (datorită subeșantionării cu 2) pentru componenta de crominață.

"Reuniunea" dintre un bloc de 16×16 pixeli din planul de luminanță și blocurile de 8×8 pixeli corespunzătoare din planurile de crominanță formează un macrobloc.

Compensarea mișcării constă din luarea unui macrobloc din cadrul (imaginea) curent și determinarea offset-ului spațial al acestuia față de poziția din cadrul de referință.

În felul acesta macroblocul curent poate fi prezis din cadrul de referință. Offset-ul se numește vector de mișcare. Algoritmul de compensare a mișcării folosește vectorul de mișcare pentru a determina blocul de predicție din cadrul de referință. Odată găsit acest bloc se face diferența dintre cele două blocuri și eroarea de predicție (după aplicarea DCT și cuantizării) este trimisă împreună cu vectorul de mișcare blocului de codare. Vectorul de mișcare obținut se aplică în mod direct pentru a determina predictorul blocului de luminață.

Pentru a determina predictorii blocurilor de crominanță vectorul este scalat la jumătate (datorită subeșantionării inițiale) pe ambele direcții (verticală și orizontală).

Procesul de determinare, a celui mai bun vector care să fie folosit pentru prezicerea blocului curent, este cel mai complex din lanțul de prelucrare MPEG. În acest punct însă se obține cea mai mare compresie a secvenței video. Există mai multe metode de alegere a vectorului de mișcare dintr-o arie de căutare prestabilită. În practică cel mai folosit criteriu este cel al determinării erorii medii absolute (MAE – Mean absolute error) dintre macroblocul curent și cel determinat de vectorul de mișcare din cadrul precedent. Ca și algoritmi de estimare a mișcării, cel mai folosit în practică este algoritmul de căutare piramidal pentru o arie de căutare de 32×32 pixeli. Utilizarea unei astfel de dimensiuni pentru aria de căutare reprezintă un compromis între precizia estimării (care este cu atât mai exactă cu cât aria de căutare este mai mică) și rata de bit necesară transmiterii vectorilor de mișcare. În afară de algoritmul de estimare al mișcării piramidal se mai pot folosi și alți algoritmi de mișcare cum ar fi: algoritmul de căutare bidimensional logaritmic, algoritmul de căutare exhaustivă, algoritmul de căutare pe direcții conjugate, algoritmul de căutare paralel.

Tipuri de cadre

Una din principalele probleme care necesită a fi rezolvate o reprezintă accesul aleator la cadrele unei secvențe video. Accesul aleator la o imagine este destul de dificil de realizat în cazul unei secvențe de cadre care folosește compensarea mișcării. Ca și în cazul modulației delta sau a codării DPCM, secvența recepționată constă dintr-un șir de informații despre modificările care apar de la o imagine la alta. Deci pentru a putea accesa o imagine trebuie decodată întreaga secvență de imagini. Totodată în cazul apariției unei erori în transmisie imaginea nu mai poate fi refăcută cu exactitate, iar eroarea se propagă în tot lanțul de cadre.

Pentru a înlătura aceste neajunsuri există două posibilități:

Folosind cele două strategii se rezolvă o altă problemă și anume aceea a accesului aleator la cadrele unei secvențe video. De exemplu, dacă vrem să vizualizăm cadrul 53 dintr-o secvență și știm că fiecare al zece-lea cadru, pornind de la zero, este codat fără predicție, atunci se decodează direct cadrul 50, urmat de decodarea cadrelor 51, 51 și respectiv 53. În felul acesta pentru a accesa un cadru, nu va trebui sa decodăm mai mult de 10 cadre.

Pentru a facilita implementarea celor două concepte standardul MPEG a definit trei tipuri de cadre după cum urmează:

–         cadre de tip I, cadre ce se codează fără a folosi tehnica de predicție. Practic aceste cadre se codează asemănător cu o imagine statică codată JPEG.

–         cadre de tip P, care sunt imagini prezise și folosesc predicția cu salt înainte față de un cadru de referință ce poate fi un cadru I, sau P.

–         cadre de tip B, cadre interpolate, folosind două cadre de referință de tip I sau P.

În figura 3.3 este prezentată o succesiune de cadre dintr-o secvență video și tipurile de predicție folosite pentru fiecare cadru în parte. Cadrele de tip I, și P se mai numesc cadre sau imagini ancoră deoarece ele vor fi folosite ca și cadre de referință pentru predicția celorlalte tipuri de cadre.

Figura 3.3 Tipurile de cadre și predicția folosită

  Afișarea și ordinea de transmisie

Așa după cum se observă din figura 3.3, pentru a putea reface cadrele de tip P, și B avem nevoie de cadrele de referință corespunzătoare. Pentru a nu stoca informația în mod neeficient la decodor, ordinea de transmisie a cadrelor MPEG, va fi diferită, astfel încât orice cadru recepționat să poată fi imediat decodat și afișat. În felul acesta se reduce capacitatea de memorare necesară la decodare.

În figura 3.4 este exemplificat ordinea de transmisie a cadrelor MPEG și ordinea de decodare a acestora.

Putem defini aici termenul de GOP – Group of Pictures – ca fiind o secvență continuă de cadre, care începe cu un cadru de tip I (inclusiv) și se termină cu următorul cadru de tip I (exclusiv). Această definiție este aplicabilă pentru secvența cadrelor așa cum sunt ele pregătite pentru transmisie. Evident la afișare (figura3.3) ordinea este cu totul alta. In exemplul prezentat în figura 3.4 un GOP este definit de cadrele: I0, B-2, B-1, P3, B1, B2, P6, B4, B5. În exemplul dat in figura 3.3 GOP – conține o configurație de 2 cadre B între două cadre ancoră (I,P) și două cadre P. Această configurație poate fi însă realizată și cu mai multe cadre B și/sau P.

Figura 3.4 Ordinea de codare, transmisie și decodare a cadrelor dintr-o secvență

video

Secvențele încadrate I0…B5 reprezintă un GOP.

Așa cum sunt definite cadrele de tip B, pentru a le reface se folosește predicția bidirecțională. În general pentru refacerea primelor două cadre de tip B dintr-un GOP (în cazul nostru B-2, respectiv B-1) este nevoie atât de cadrul I care urmează cât și de cadrul P anterior aflat în GOP-ul precedent. Deci dacă am dori să începem decodarea de la începutul unui GOP, adică cu cadrul I0, atunci cadrele B-2, B-1, nu ar putea fi decodate corect lipsind cadrul P-3. Standardul MPEG rezolvă acest neajuns prin introducerea conceptului de GOP – închis, care stipulează că toate cadrele B care preced un cadru de tip I dintr-un GOP nu vor putea folosi ca și ancoră un cadru dintr-un GOP anterior (în cazul nostru cadrul P-3). În figura 3.3 am arătat acest concept prin punctarea săgeților care fac legătura dintre un GOP la altul. De fapt nu se face predicție între cadre. În felul acesta se aplică conceptul de predicție cu întreruperi.Pornind de la definirea tipurilor de cadre, se poate stabili numărul biților folosiți pentru reprezentarea fiecărui tip de cadru. Având în vedere faptul că imaginile de B nu vor mai fi folosite pentru predicția altor imagini, acesta vor putea fi reprezentate folosind un număr minim de biți/pixel. Nu același lucru se întâmplă pentru cadrele I și P care sunt folosite ca imagini de referință, și deci necesită o calitate superioară pentru menținerea detaliilor imaginii. S-a stabilit că un raport de 5:3:1 pentru reprezentarea cadrelor I, P, respectiv B este satisfăcătoare, mărindu-se în acest fel raportul de compresie. Evident acest raport poate fi modificat în funcție de dinamica secvenței video.

După procesul de compensare a mișcării, informația obținută (eroarea de predicție) este transformată folosind transformata cosinus discretă DCT – Discrete Cosine Transform. Pentru a aplica DCT, macroblocul este împărțit în 6 blocuri de 8×8 pixeli, 4 corespunzătoare planului de luminanță, și câte unul pentru fiecare componentă de crominanță. În figura 3.5.a este prezentată descompunerea blocului de luminanță pentru standardul MPEG-1 și MPEG-2 varianta de reprezentare pe cadre. În figura 3.5.b este prezentat modul de descompunere a blocului de luminanță pentru standardul MPEG-2 varianta de reprezentare pe câmpuri.

a)

b)

Figura 3.5 Descompunerea blocului de luminanță (16×16) în blocuri de 8×8 pixeli

a) pentru reprezentarea pe cadre

b) pentru reprezentarea pe câmpuri

După blocul transformării DCT, coeficienții obținuți sunt cuantizați folosind matricile de cuantizare din tabelele 1 (pentru cadrele codate fără predicție) respectiv tabelul 2 (pentru cadrele codate cu predicție). În urma procesului de cuantizare, acei coeficienți care sunt irelevanți din punct de vedere al calității imaginii vor fi practic eliminați. Se poate observa în tabelul 1 că primul element (stânga-sus) nu are valoare de cuantizare.

Acest element corespunde cu coeficientul DC din matricea coeficienților DCT, și deci fiind cel mai important coeficient nu se cuantizează.

Tabelul 1 Matricea de cuantizare pentru Tabelul 2 Matricea de cuantizare

pentru cadre ce nu folosesc predicția cadre care folosesc predicția

Atât coeficienții cuantizați cât și celelalte tipuri de informații (tipul de predicție, vectorii de mișcare, etc.) vor fi codați entropic pentru a se obține o rată de bit cât mai mică. Procesul codării entropice conține trei etape:

–         conversia 2D la domeniul unidimensional

–         codarea lungimii curselor (codarea RLC)

–         codarea Huffman

  Conversia 2D – > 1D

După cuantizare o mare parte din coeficienții DCT vor avea valoarea zero, așa cum se poate observa și din figura 3.6. Pentru a exploata acest aspect (frecvențele înalte sunt zero) in procesul de codare RLC, trebuie realizată o conversie a blocului 8×8 pixeli într-un șir unidimensional de coeficienți în care coeficienții nuli să fie grupați.

Pentru a realiza acest deziderat se pot folosi două tehnici de conversie:

–         scanarea zig-zag (utilizată atât pentru MPEG-1 cât și pentru MPEG-2)

–         scanarea verticală (utilizată în MPEG-2 – este mai eficient pentru cazul în care se folosește reprezentarea pe câmpuri)

În figura 3.7 a, b sunt prezentate traictoriile folosite pentru conversia blocului 8×8 de coeficienți cuantizați.

Figura 3.6 Bloc 8×8 coeficienți DCT cuantizați

a) b)

Figura 3.7 Tipuri de scanări pentru conversia 2D -> 1D:

a)      scanare zig-zag

b)      scanare verticală

Dacă aplicăm scanarea zig-zag pentru coeficienții DCT din figura3.6 obținem secvența:

  -42 12 –19 16 14 3 –1 –8 8 3 3 –2 –9 0 0 0 2 3 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 –1 0 … 0

Codare lungimii curselor

După conversia 2D->1D se obține un vector unidimensional de dimensiune 64. Acest vector este trimis blocului de codare a lungimii curselor de zero. Cursa se definește ca fiind zero sau mai mulți de zero urmați o singur coeficient nenul. Fiecare astfel de pereche obținută va reprezenta un simbol pentru codul Huffman modificat. Dacă codăm secvența care se obține după scanarea zig-zag a coeficienților din figura 6 obținem codul RLC:

  (0, -42), (0, 12), (0, -19), (0, 16), (0, 14), (0, 3), (0,-1), (0,-8), (0, 8), (0,3), (0,3), (0,-2), (0,-9), (3,2), (0,3), (10, 1), (2,1), (0,1), (6, -1),(EOB).

De notat faptul că simbolul (EOB) – cod special, semnifică faptul că nu mai există coeficienți nenuli. In felul acesta se elimină informația redundantă din blocul coeficienților DCT.

 Codarea Huffman

Așa după cum se cunoaște codarea Huffman realizează o codare entropică optimală pentru un alfabet dat. Totuși în cazul în care alfabetul este prea mare este prea costisitoare implementarea unui astfel de algoritm. Pentru a folosi însă avantajele oferite de acest mod de codare, s-a dezvoltat un algoritm de codare Huffman modificată. Acest algoritm folosește codarea Huffman clasică pentru un număr (relativ mic) de simboluri (simboluri de categoria I) care au ce mai mare probabilitate de apariție. Celelalte simboluri (simboluri de categoria II-a) sunt codate cu prefix. Adică dacă apare un simbol ce nu este cuprins în prima grupă, acesta se codează trimițând prefixul, urmat de simbolul explicit.

Introducerea codului de prefix va crește rata de bit a codului, dar dacă probabilitatea de apariție a acestor simboluri este suficient de mică atunci această creștere este nesemnificativă.

3.2 Generalitati despre standardul MPEG-4

Standardul MPEG-4 a fost demarat în 1994 și ar trebui finalizat în noiembrie 1998. Spre deosebire de MPEG-1 și MPEG-2, care au folosit algoritmi de compresie cunoscuți de mulți ani, MPEG-4 este mult mai apropiat de cercetare, explorând domenii noi în compresia audio-video. În MPEG-4 nu mai avem de a face cu o succesiune de imagini și sunete ci cu o colecție de obiecte audio-video naturale și sintetice. Partea cea mai importantă din MPEG-4 este MSDL (MPEG-4 Syntax Description Language), un limbaj de tipul "object oriented" cu o structură binară folosit pentru comunicația dintre emițător și receptor. În viitor, comitetul MPEG va face disponibil un translator din MSDL în C++.

În configurația minimală, emițătorul transmite obiecte audio-video și un "composing script" pentru compunerea și prezentarea lor. În configurații mai sofisticate, emițătorul va transmite și algoritmi de decompresie necunoscuți receptorului. Acești algoritmi vor fi descriși în MSDL și vor fi compilați sau interpretați de receptor în propriul limbaj. Acesta oferă o flexibilitate enormă pentru MPEG-4. Atâta timp cât un emitător și un receptor sunt capabili să comunice în MSDL, acest limbaj poate fi folosit pentru transmiterea oricărui conținut informațional. Progrese viitoare în algoritmi pentru compresia, manipularea și prelucrarea obiectelor pot fi comunicate receptorului fără a fi nevoie de un nou standard.

În momentul de fată nu este clar dacă MPEG-4 va avea același succes comercial ca și MPEG-2.

=== CAPITOLUL 4 ===

CAPITOLUL 4

PROIECTARE SOFTWARE ȘI REZULTATE EXPERIMENTALE

Implementarea programului

Programul JPEG.m, a fost implementat folosind limbajul de programare MATLAB 6.5. Acest program funcționează pentru compresia imaginilor cu nivele de gri de dimensiune 256×256.

Pașii urmăriți la implementare sunt cei ilustrați în figura 4.1.

Programul cuprinde 2 părți:

A). COMPRESIE

Se citește imaginea dintr-un fișier format .tif și se introduce într-o matrice, ce va conține valorile pixelilor (65.536 valori).

Se împarte matricea în care s-a citit imaginea în blocuri de dimensiune 8×8, obținându-se 1024 de astfel de blocuri.

Se calculează transformata cosinus discretă (DCT), pentru un bloc de 8×8, conform relațiilor din capitolul 2 (2.2.2). Secvența de program care calculează DCT – ul este următoarea:

for i=1:8,

for k=1:8,

if k==1

C(k)= 1/sqrt(2);

else

C(k) = 1;

end;

A(k,i) = sqrt(2/8)* C(k)*cos((2*i-1)* (k-1) * pi / 2 /8);

end;

end;

Pentru fiecare bloc de 8×8 se aplică, pe rand, următoarele operații:

Cuantizarea: (yy=A * y *A') – operație la care are loc pierdere de

informație.

Normalizarea: (yy=[yy./NORM]), unde NORM este o matrice constantă.

Zig-Zag: (SNx = yy(SCAN)) – se parcurge blocul în zig-zag conform figurii folosind matricea constantă SCAN. După aplicarea acestei operații toate elementele diferite de 0 se vor situa în partea superioară a diagonalei secundare (colțul stânga sus).

Se aplica procedura run-length pe matricea obținută după parcurgerea operațiilor de mai sus deoarece se observă un număr mare de zerouri, din care se păstrează unul singur iar informația adiacentă va conține numărul de zerouri care au fost șterse, până la următoarea valoare nenulă. Rezultatul va fi memorat într-un vector, folosit la generarea codului binar.

Codarea aritmetică – este implementată de funcția arithenco(), existentă în MATLAB versiunea 6.5. Aceasta funcție primeste ca parametri, alfabetul sursei (calculată cu funcția alfabet.m) și un vector cu poziția din alfabet al fiecărui caracter care se codeaza. Deoarece această funcție nu acceptă valori negative se va face următoarea convenție: toate valorile egale cu -1 se trec în 0 și zerourile devin 1.

B). DECOMPRESIE

Pentru decompresie se vor parcurge aceiași pași în ordine inversă:

Decodarea aritmetică – se realizează cu funcția arithdeco() care primește ca parametri codul binar ( rezultat din funcția de codare), precum și cei doi vectori (alfabetul și vectorul cu pozițiile). Se respectă convenția de mai sus pentru a reface vectorul obținut după aplicarea procedurii run-length.

Se reface vectorul ințial, prin aplicarea procedurii run-length inverse, adică la găsirea unui 0, se citește valoarea urmatoare și se adaugă în vector atâtea zerouri câte indică ea.

Reconstrucția imaginii cuantizate. Se aplică operațiile în ordine inversă:

Se reface zig-zag-ul conform unui algoritm propriu:

Se ia o matrice 8×8, care se parcurge în zig-zag (conform figurii 2.6) și se memorează indicii pentru linie, respectiv pentru coloană în 2 vectori (SNl și SNc), atâta timp cât este îndeplinită condiția ca un element să se situeze pe diagonala secundară:

k = i+j ,

unde i = numărul liniei;

j = numărul coloanei;

k = numărul de elemente luate la fiecare pas.

Când s-au parcurs k elemente, înseamnă că s-a ajuns într-un capăt al zig-zag-ului și trebuie schimbată direcția (fig. 2.6)

SNl = 1,1,2,3,1,….

SNc = 1,2,1,1,2,…

Pentru a obține blocul de 8×8 refăcut după zig-zag, se urmărește o matrice după cei doi vectori, de linie, respectiv de coloană.

Pseudocodul algoritmului este următorul:

k = 2; nre = 0;

Cât timp k<8 execută

Pentru i = 1 ÷ 8

Pentru j = 1 ÷ 8

Dacă (i+j = k) atunci

nre=nre+1

dacă k = nr. impar ATUNCI „se schimbă direcția”

SNl(nre)=j

SNc(nre)=i

ALTFEL

SNl(nre)=i

SNc(nre)=j

End

End

k = k+1

Sfârșit

Denormalizare;

Decuantizare;

Se lipesc blocurile pe care s-au aplicat operațiile de mai sus, obținându-se matricea imaginii refăcute.

Se exportă imaginea obținută în format JPEG, pentru a fi deschisă direct din Windows, folosindu-se funcția imwrite

Rezultate experimentale

S-a rulat programul JPEG.m pe mai multe imagini cu nivele de gri de dimensiune 256×256 (existente în toolbox-ul MATLAB –lui), obținându-se următoarele rezultate:

Exemplul 1: ic.tif

Imaginea originală (64.4Kb) Imaginea refăcută (8.15Kb)

Se obține o rată de compresie RC = 8.0098

Exemplul 2: cameraman.tif

Imaginea originală(63.7 Kb) Imaginea refăcută(9.49 Kb)

Se obține o rată de compresie RC =6.7567

Exemplul 3: testpat1.tif

Imaginea originală(64.4 Kb) Imaginea refăcută(13.9 Kb)

Se obține o rată de compresie RC =4.6181

Exemplul 4:lenna.tif

Imaginea originală(64.2Kb) Imaginea refăcută(9.40 Kb)

Se obține o rată de compresie RC =6.7567

=== CAPITOLUL 6 ===

capitolul 6

CALCULUL ECONOMIC

6.1 Generalități

Costul de producție este o categorie economică legată de existența producției de mărfuri, de procesul de formare a valorii și de prețuri.

Calculul economic reprezintă un calcul foarte amănunțit al costului de producție al programelor respective.

În sfera producției materiale, costul de producție este forma bănească a unui conținut ce reprezintă consumul de mijloace materiale și forță de muncă, necesare pentru producerea și desfacerea bunurilor materiale. El include tot ceea ce înseamnă cheltuială de producție suportată de întreprinzător pentru producerea și desfacerea bunului respectiv.

Între costul de producție și prețul de vânzare există deosebiri atât cantitative, cât și calitative. Astfel prețul este mai mare decât costul de producție incluzând în plus și profitul. Deosebirea calitativă este că, în timp ce prețul asigură mijloacele necesare producției lărgite, costul de producție asigură doar recuperarea cheltuielilor de producție.

Potrivit legislației în vigoare, în țara noastră costul de producție este împărțit în următoarele grupe de cheltuieli:

Cheltuieli materiale (materii prime, energie, materiale și combustibili) Cmp.

Cheltuieli directe cu munca vie (retribuții directe plătite muncitorilor,impozit pe fondul de retribuții directe Ifr, contribuții pentru asigurări sociale Cas).

Cdmv = Rd + Ifr + Cas

Contribuții la fondul de cercetări științifice;

Impozite (pe clădiri);

Fond pentru ajutor de șomaj, alte cheltuieli.

Elementele componente ale costului de producție se modifică de la o perioadă de timp la alta sub influența factorilor externi și interni.

Mărimea costului de producție exprimă toate cheltuielile cu mijloacele de producție și plata salariilor, cheltuieli ce se efectuează pentru producerea și desfacerea bunurilor de materiale.

Reducerea costului de producție înseamnă micșorarea cheltuielilor pe unitatea de produs și este o necesitate obiectivă impusă de creșterea rentabilității, sporirea profitului și a productivității muncii.

Reducerea costului de producție atrage după sine creșterea calității produsului, realizarea unor specializări suplimentare.

Diminuarea costului de producție se poate face pe mai multe căi:

Prin reducerea costului materialelor;

Prin utilizarea eficientă a capitalului fix;

Prin creșterea productivității muncii;

Prin reducerea cheltuielilor administrativ – gospodărești.

La efectuarea calculului economic se poate ține cont și de o serie de costuri, cum ar fi:

Costul fix se referă la cheltuieli independente de volumul producției

(chirii, amortizarea mașinilor, a clădirilor, etc.);

Costul variabil se modifică odată cu modificarea volumului de

producție;

Costul marginal exprimă sporul de cheltuieli necesare pentru obținerea

unei unități suplimentare de produs;

Costul cercetării științifice este dat de cheltuielile pentru cercetarea

propriu – zisă și pentru aplicarea în practică a rezultatelor activității de cercetare- -proiectare în vederea realizării prototipului;

Costul tehnologic se caracterizează prin individualizarea cheltuielilor

directe și a unei părți însemnate din cheltuielile indirecte, în special cu întreținerea și folosirea utilajelor.

Procesul de formare al costului de producție este dat de nivelul secției de cheltuielile directe la care se adaugă cheltuielile cu întreținerea și funcționarea utilajelor (CIFU), cheltuieli generale ale secției cu munca vie (CMDV), care sunt necesare în scopul asigurării necesităților de iluminare și încălzire, etc.

Cd – reprezintă cheltuieli directe la care se adaugă cheltuielile necesare pentru materii și materiale și cheltuielile directe cu munca vie, din care se scade costul materialelor refolosibile și recuperabile (C)

Cd = Cmp + Cdmv – C

unde: – Cmp – cheltuieli directe cu materii prime și materiale.

Valoarea aparatului se calculează cu relația următoare:

I = Pa + Cm + Pc + Ct

Unde:

I – investiția;

Pa – prețul aparatului;

Cm – cheltuieli de montaj (asamblare);

Ct – cheltuieli pentru transport.

În prețul aparatului intră: prețul pentru circuite integrate, pentru componente pasive, pentru cablajul imprimat, cheltuieli pentru carcasă, cheltuieli pentru probe, etc.

Costul Software – ului

Statisticile arată că în țările puternic industrializate ponderea ocupată de costul software-ului în produsul național brut este în continuă creștere. Acest cost este influențat, și determinat totodată, de o serie de factori cum ar fi: productivitatea de programare, predicția în care se va realiza produsul final, costul hardware-ului în raport cu cel al software-ului, utilizarea generatoarelor de programe,etc.

Costul software-ului este în mare parte determinat de nivelul salariilor celor implicați în producția de software. Productivitatea medie a programatorilor este de 10 – 20 instrucțiuni (într-un limbaj de programare) pe zi.

Acestea includ clarificarea specificațiilor problemei, proiectarea programului, codificare, testare și documentare. Surprinzător, această productivitate nu depinde de limbajul utilizat.

Productivitatea este influențată de lucrul individual sau în echipă al programatorului și de tipul aplicației proiectate (software de aplicații sau software de bază). Se știe, de exemplu, că sistemele de operare se realizează mai greu decât diversele aplicații software.

6.3 Calculul economic pentru programe

Deoarece tema proiectului implică numai realizare soft, va trebui să calculăm costul economic al tuturor programelor realizate în Matlab 6.5.

Pentru realizarea acestor programe este nevoie de:

Un computer cu sistem de operare WINDOWS XP preinstalat care se evaluează la circa 1000$.

Licența pentru Matlab 6.5. se estimează la circa 2000$.

Programarea ca formă de muncă este plătită cu circa 25Euro/zi la o normă de 40 de linii de program, această sumă fiind variabilă în funcție de țară, nivel de trai, etc.

În cazul nostru avem circa 280 de linii de program realizate în Matlab 6.5.

Nr. linii program la zi = 20

Nr. total linii = 280

Nr. zile = Nr. total linii / Nr. linii program la zi

Nr. zile = 280 / 20 = 14 zile

Considerăm că un programator lucrează, astfel, 14 zile pentru care retribuția sa este de:

Retribuție = Nr. zile *25Euro = 350 Euro

Această sumă poate varia de la firmă la firmă în funcție de prețul pe linia de program sau de norma pe care o are un programator.

=== organigrama1 ===

bloc de 8×8 DCT bloc de 8×8

Imaginea originala

Zig-Zag bloc de 8×8 Cuantizare

Run-length

Code

Figura 4.1 – Pașii urmăriți în compresia JPEG