Tema 4 Формати за представяне на растерни файлове. Компресия на цифровите изображения



Дата18.09.2016
Размер328.25 Kb.
TEMA 4 Формати за представяне на растерни файлове. Компресия на цифровите изображения
1.Въпрос. Общи понятия за структура и формат на растерното изображение.
Растерното изображението на екрана се представя като съвкупност от пиксели (точки) , всяка от които има своя цвят. Цветът на пиксела се образува от съчетанието на трите основни цвята: Red – червен, Green – зелен и Blue – син – т.н. RGB компоненти на цвета.

Интензивността на цвета се описва с 1 байт (8 бита) и може да се променя от 0-255 т.е. 256 нива (степени) – 28 = 256.

Основни параметри на изображението се явяват – неговото разрешение и дълбочина на цвета.

При запис на растерното изображение във файл също се създава матрица от пиксели, която съответства по своите размери на размерите на изображението. Тази матрица е прието да се нарича “растер”.

Способите за създаването и съхранението на такъв растер са най-разнообразни и се определят от т.н. формат за описание на данните в паметта на ЕИМ, наричано за по кратко – приетия формат на файла.

Под формат за представяне на растерни файлове се разбира системата за описание и съхранение на местоположението и цветовата характеристика на всеки един пиксел от изображението.
Първият елемент характеризиращ растера - това е приетият способ за цветовото описание на отделния пиксел.

В практиката съществуват два способа за описание на цветовете:



Първи способ – посредством съхранение на т.н. палитра или таблица на цветовете, която се съхранява във файла заедно с растера като негова добавка. Използуват се едно битови палитри съдържащи 2 цвята, четири битови палитри съдържащи 16 цвята и 8 битови – 256 цвята. Този способ позволява получаването на т.н. “свито BMP изображение”

Втори способ – чрез непосредствено задаване на цветовете на всеки пиксел, при което всяка RGB комбинация се описва в самия растер. При това могат да бъдат използувани различни количество битове за описание на RGB комбинацията:

  • 15 или 16 бита/пиксел (Red-5, Green-5(6), Blue-5) – 32К или 64К цветове (Higt Color)

  • 24 или 32 бита/пиксел – по един байт на компонент R,G и B, което осигурява създаване на 16 Мб цветове (True Color).


Вторият елемент характеризиращ растера – това са количеството плоскости използувани за съхранение на елементите от растера.

Използуват се една, три или четири плоскостни изображения

Една плоскост – растер на изображението се състои от една матрица

Три плоскости – пълният растер на изображението се състои от три матрици – по една за вяска RGB-компонента.

Четири плоскости – пълният растер на изображението се състои от четири матрици, при които всеки пиксел от изображението се съхранява по специален начин.

Съществуват следните основни формати за съхранение на растерни изображения:



  • BMP – бит/мап формат използва прости методи за описание на изображенията, което го прави пригоден за бързо четене и запис на неголеми изображения. Широко се използува в операционната система WINDOWS;

  • TIF - формат осигурява съхранение на графичните данни в структуриран вид, което позволява бърз достъп към различни фрагменти от големи изображения, което го прави предпочитан за използуване при работа с големи сканирани изображения;

  • PCX - един от първите формати за съхранение на растерни палитрови цветни изображения;

  • GIF - универсален графичен формат за съхранение на палитрови цветни изображения, осигуряващ значително свиване на съхраняваната информация;

  • JPG - формат предназначен за работа с пълно цветни (True Color) изображения с фотографско качество използуваш ефективни методи за свиване на съхраняваната информация;

  • VSF – вътрешен формат за съхранение на изображения предназначен за бърза оперативна работа с изображенията; Подобна идея за свой формат използува системата CADIS

  • CEL - вътрешен формат за съхранение на изображения с разбивка на изображението на клетки предназначен за обработка на големи (до десетки и стотици мега байтове) изображения. Подобна идея за свой формат използува системата MKad

За различните формати за съхранение на изображения са валидни следните съчетания от параметри:

Формат на файла

Количество битове на пиксел

Количество плоскости

BMP

1,4,8,24,48

1

TIF







PCX

1,8

1,4

GIF

8

1

JPG

24

1

VSF

1,4,8,15,16,24,32

1,4

CEL

4,8,15,16,24,32

1,4

2.Въпрос. Описание на някои от основните формати за съхра-нение на растерни изображения

Описание на формата BMP - bitmapp – “битова карта”

BMP файла се състои от четири части:

1. Заглавие на файла (Bit Map File Header)


  1. Информационен блок (Bit Map Info Header)

  2. Палитра (Color Table)

  3. Данни за самото изображение (BitMap Array)

Различните части от файла съдържат полета с различно съдържание и различна дължина в байтове а именно:


1. ЗАГЛАВИЕ (14 байта)


Bit Map File Header

  • Type — тип на файла, изразен чрез симвоите 'BM';

  • Size — размер на файла в байтове;

  • Reserved1 – първо резервно поле съдържащо нули;

  • Reserved2 —второ резервно поле содержщо нули.

  • OffsetBits —изместване на изображението спрямо началото на файла.





2. ИНФОРМАЦИОНЕН БЛОК (38 байта)


Bit Map Info Header



  • Size — размер на блока в байтове;

  • Width — ширина на изображението в пиксели;

  • Height — висчина на изображението в пиксели;

  • Planes — количество плоскости – съдържа единица;

  • BitCount — дълбочина на цвета - количество битове на пиксел и дали се използува палитра;

  • Compression — указва тип на компресия или не на изображението;

  • SizeImage — Указва размера изображението в байтове.

  • XPelsPerMeter ,YPelsPerMeter— указва хоризонталното и вертикално разрешение в пиксели/метър- за съхранение на мащаба на сканирани изображения при тяхното възпроизвеждане;

  • ClrUsed — указва количеството исползувани цветове в палитрата.

  • ClrImportant — указва количеството основни цветове, необходими за представяне на изображението.






3. ТАБЛИЦА НА ЦВЕТОВЕТЕ - ПАЛИТРА (1024 байта)


Bit Map Info Header



  • ColorTable — таблица с дължина 1024 байта съдържаща последователност от 4 байтови полета за всеки възможен цвят за 8 битовото изображение (28 = 256 цвята Х 4 байта/цвят = 1024 байта) (0,0,0),(0,0,1),(0,0,2)....(255,255,255).



4. ДАННИ ЗА ИЗОБРАЖЕНИЕТО (промeнливо колич. байтове)

Данните за изображението се записват като поредица от полета записани по редово от долу нагоре. Всеки ред от изображението се допълва с нули до получаване на дължина кратна на четири байта. Съдържанието на полето зависи от това дали BMP файла съдържа палитра или не.

В случай на използуване на палитра всеки пиксел от изображението се описва с един байт, съдържащ номера на полето от палитрата където се съхранява цветът на този пиксел.

Ако файлът не съдържа палитра то във всяко поле с дължина 4 байта се записва пълно цветната RGB комбинация за цвета на съответния пиксел.


3.Въпрос. Компресия на цифрови изображения
Алгоритмите за свиване на цифрови изображения е едно от бурно развиващите се направления за развитие на машинната графика. Необходимостта и възможностите за развитието на това направление се обуславя от следните характерни особености на цифровите изображения:

  1. Изображенията изискват наличие на значително по-големи обеми от памет за съхранение в сравнение с текстовете. Например илюстрация със средно качество с размер 500Х800 точки заема 1.2 Мб памет – толкова колкото художествена книга от 400 страници стандартен текст (60 знака на ред и 42 реда на страница) Тази особеност на изображението налага актуалността на алгоритмите за компресия на цифровите изображения.

  2. Втората особеност на изображенията се характеризира с това, че човешкото зрение при анализ на изображенията оперира с контурите, общите изменения на цветовете и е нечувствително към малките изменения в изображението. Това позволява да бъдат използувани такива схеми на компресия, при които благодарение на това, че декомпресираното изображение не се явява точно възстановяване на оригинала, но това остава незабележимо за човешкото око. Тази особеност на човешкото зрение позволява да се създадат специални алгоритми за свиване (компресия), предназначени специално за изображения, в отличие от тези за компресия на текст например. Тези алгоритми позволяват голяма степен на свиване с незначителни от гледна точка на човешкото зрение загуби.

  3. Лесно може да се забележи, че изображението за разлика от текста притежава свръх информация в две измерения. По хоризонтала и по вертикала по отношение на близките по положение и цвят съседни точки. Освен това в алгоритмите за компресия може да се използува и подобието между цветовите плоскости (матрици) R,G и B, което позволява постигане на още по-голяма ефективност. Т.е при създаване на алгоритмите за компресиране се използуват и структурните особености на изображенията.

Към настоящия момент съществуват най-малко три семейства алгоритми, които са създадени изключително за компресиране на изображения. Преценката на това, кой от тези основни алгоритми, т.е. методи за компресия е най-подходящ зависи от отговора на следните ътри важни въпроса:

  • приложими критерии за сравняване на алгоритмите;

  • какви класове изображения от гледна точка на възможностите за тяхната компресия съществуват;

  • за какви задачи се използуват алгоритмите за компресия и какви са специфичните изисквания към тях.


Критерии за сравнение на алгоритмите

  • степен на компресия – различава се лоша, средна и отлична степен на компресия.

  • приложим клас на изображение – това е класът изображение към което конкретният алгоритъм дава най-добри рзултати;

  • симетричност – това е съотношение между ресурсоемкостта на алгоритъма при етап кодиране и и обратния процес - декодиране на изображението.

  • Съществува ли загуба на качество или не и ако то е налице, за сметка на какъв процент свиване на информацията. При много от алгоритмите за свиване със загуба е възможно да се настройват параметрите на свиване с оглед допустими изисквания за загуби.


Класове изображения от гледна точка на възможностите за компресия

Клас 1. Изображения с малко количество цветове (4-16) и наличие на големи области запълнени с един цвят.

Клас 2. Изображения с плавен преход на цветовете създадени на компютър – графики, презентации, модели на технически устройства – части, разрези технологични процеси и др.

Клас 3. Фотореалистични изображения – сканирани фотографии

Клас 4. Фотореалистични изображения съвместени с делова графика - например рекламни пана.
Изисквания на задачите към степента и скоростта на компресия

Изхождайки от предяваваните изисквания могат да бъдат формулирани три класа приложни задачи изискващи алгоритми за архивиране и разархивиране на изображения:



Клас 1. Високи изисквания към времето за архивиране и разархивиране. Тогава когато е необходимо да се съхранява много голямо количество изображения и се налага търсене на опрдеделно или определени изображения – например при издателите на вестници и др.

Клас 2. Високи изисквания към степента на компресия и времето за разархивиране Например справочници и енциклопедии записани на CD-ROM. За този клас приложения се изисква асиметричност по време на алгоритъма за компресия.

Клас 3. Много високи изисквания към степента на компресия Рзпространение на изображения по Интернет.
Изисквания на конкретните приложения към алгоритмите за компресия

  1. Висока степен на компресия;

  2. Високо качество на изображението;

  3. Висока скорост на компресия;

  4. Висока скорост на декомпресия;

  5. Лесно мащабиране на изображението;

  6. Възможност за показване на грубо ( с ниско разрешение) изображение използувайки само началото на файла (preview);

  7. Устойчивост към грешки – при предаване по линии за свръзка – прекъсванията да не оказват влияние на данните получени след прекъсването на връзката

  8. Редактируемост – да не се влошава значително изображението при няколко последователни итерации на архивиране, дезархивиране с редакци и последващо архивиране;

  9. Не скъпа апаратна и ефективна програмна реализация.


ИЗВОД: На практика за всяка задача може да се формулира пакет изисквания към алгоритъма за архивиране.

4.Въпрос. Описание на някои основни алгоритми за компресия (свиване) на изображения


    1. Методи за обхождане на двумерни масиви - плоскости

Задачата за обхождане на плоскости възниква при обработката на двумерни изображения когато е необходимо двумерния масив Si,j да се представи като едномерен Di. Това е задължително при съхранение на данните за двумерните изображения във вид на файлове където записите за съдържанието на всяка клетка от растера вървят един след друг.

Когато това преобразуване се използува за последващо свиване на информацията (изображението) е необходимо това обхождане да се извършва така, че в новополученият едномерен масив да няма много “прекъсвания” ( наличие на разстояния в местоположението на даден елемент в едномерния спрямо съседите му в двумерния масив – всеки следващ елемент Di , записан в масива D на стъпка i се явява съседен (в плоскостта) за предишния елемент записан на стъпка i-1 – Di-1.



      1. Змейка (сканиране зиг-заг)

Обхождането на масива S започва с единия ъгъл на плоскостта и завършва в противоположния ъгъл по диагонала.
На фигурата е показан ред за обхождане от горния ляв към долния десен


1

2

6

7

15

16

3

5

8

14

17

24

4

9

13

18

23

25

10

12

19

22

26

29

11

20

21

27

28

30

Методът “змейка” е удобен когато в един от ъглите са съсредоточени само големи или само малки стойности на двумерния масив или сходни стойности отговарящи на друг критерии.




      1. Обхождане по редове

Това е най-известният и тривиален метод. Той се използува в най-разпространените формати такива като BMP, TGA RAS и др.


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30



Има много разкъсвания



      1. Обхождане по редове със завъртане


1

2

3

4

5

6

12

11

10

9

8

7

13

14

15

16

17

18

24

23

22

21

20

19

25

26

27

28

29

30


Няма разкъсвания


      1. Обхождане по зони със и без завъртане


1

4

7

10

13

16

2

5

8

11

14

17

3

6

9

12

15

18

36

31

30

25

24

19

35

32

29

26

23

20

34

33

28

27

22

21

Този метод осигурява сравнително добри условия за свиване на информацията защото двумерно изображение не е равномерно разпределено по целия едномерен масив, а е разбито на области и всяка отделна област е разположена компактно.


Без завъртане

Със завъртане

В зависимост от броя на редовете N зоните могат да имат различни размери. При N=1 обхождането по зони се преобразува в обхождане по редове.

Съществуват още редица други методи за обхождане такива като обход по решетка, контурен обход, квадратна “змейка”, обход по спирала и др.


    1. Алгоритми за свиване на изображения без загуби.




      1. Алгоритъм RLE (Running)

Това е така наречения алгоритъм за групово кодиране (Run Lengt Encoding) и се явява един от най-простите и най-стари алгоритми за архивиране на графики. Двумерното изображение при този алгоритъм се преобразува в едномерно чрез обхождане по редове.

RLE свиването се осъществява за сметка на това, че в изходното изображение се срещат последователности от клети с еднакви стойности на цветовите значения.

Тогава компресираното изображение ще изглежда така:
File header, N1B1,N2B2,N3B1,N4B3,…………,NkBm, End file

Този алгоритъм е разчетен за приложение при използуване на т.н. “делова графика” – изображения с големи области повтарящи се цветове.

На практика в определени случаи - (например когато този алгоритъм за свиване се прилага при цветни фотографии) вместо свиване на изходния файл, може да се получи нов файл с по-голям обем.


      1. Алгоритъм на Хофман

Този алгоритъм заменя данните представени посредством битови думи с фиксирана дължина с техните съответни кодови битови думи но с променлива дължина и съставени така, че да отчитат честотата на тяхното появяване. При това, кодовете на по-често повтарящите се думи са с по-малка дължина от кодовете за представяне на по-рядко срещаните думи.



Алгоритъмът е разработен през 1952 г. от Доктора на Масачусетския технологичен институт Дейвид Хофман и носи неговото име.
Същността на алгоритъмът на Хофман се състои в следното:
Както стана ясно в предишните лекции, данните за цифровите изображения се представят във вид на последователности от числа, като обикновено всяко от тези числа представлява поредица от битове с определена - фиксирана дължина.

Нека имаме 8 – битовото изображение което в паметта на ЕИМ се представя като съвкупност от числени стойности на цветовете (0-255) за всяка от която се използува 1 байт информация (8 бита). Т.е. може да се каже че 8-битовото изображение се състои от 8 битови думи.

Числата 1,2,3,4 .. 255 записани в двоичен формат изглеждат така:
000 000 00,000 000 01,000 000 02,000 000 03, 000 000 04,… 111 111 11
Да предположим, че изображението се състои от 6 цвята условно обозначени със стойностите 1,13,55,87,154 и 253 и е с големина 100 думи (100байта или 800 бита).

Свиването на данните по алгоритъма на Хофман преминава през следните стъпки:



Първа стъпка – Определя се честотата на поява на всяка една от изброените стойности, в резултат на което по получените данни се попълва т.н. пълна честотна таблица на честотите. Тя има вида:

Пълна честотнатаблица

0
Числа

Честота



1



13



55



87



154



202



253

254

255

0

10

0

20

0

30

0

5

0

25

0

0

0

10

0

0

В получената таблица ненулеви значения имат стойностите на цветовете 1,13,55,87,154,253. Честотата на появяване на останалите цветове е равна на нула, т.е. те не съществуват в изображението и не представляват по нататъшен интерес.

От пълната честотна таблица се получава ненулева честотна таблица която ще има вида:

Ненулева честотна таблица


1
Числа

Честота



13

55

87

154

253

10

20

30

5

25

10


Втора стъпка – сортиране на стойностите в таблицата по посока на тяхното нарастване:

Сортирана таблица



8
Числа

Честота
7



1

253

13

154

55

5

10

10

20

25

30


Трета стъпка – формиране на т.н. “дърво на възлите”.

За целта чрез сумиране на двете най-ниски честоти се получава нова клетка (възел) в таблицата чието местоположение е съобразено с подредбата по посока на нарастването.Веднъж използуваните клетки по-вече не участвуват в обработката.


Числа

Честота




87

1

253




13

154

55

5

10

10




20

25

30

15





5+10 = 15 –нов възел №1






8
Числа

Честота
7



1

253




13




154

55

5

10

10




20




25

30

15







25


10+15 = 25 – нов възел № 2


Чрез последователни сумирания се получава т.н. “ Хофманово дърво на възлите”

Хофманово дърво на възлите


87

1

253




13




154

55







5

10

10




20




25

30







15





55






25










45









100

Корен на дървото


Четвърта стъпка - кодировка на 8 битовите думи.
Целта е на всяка 8-битова дума – с фиксирана дължина да се постави еднозначен код с променлива дължина.

За постигане на поставената цел кодирането се извършва чрез придвижване от корена на дървото към неговата корона като за всеки преминат възел се записва по един бит със стойност зависеща от посоката на придвижване 0 – на ляво или 1 – на дясно.

По тази логика на най-често срещаната стойност 55 ще се съпостави код 11, на стойността 154 – 10 и т.н.

Извършвайки всички изчисления ще получим следната кодова таблица за съответствие между думите с фиксирана дължина и техните кодове с променлива дължина




стойност

код

дължина

честота

стойност

код

дължина

честота

1

0111

4 бита

10

87

0110

4 бита

5

13

00

2 бита

20

154

10

2 бита

25

55

11

2 бита

30

253

010

3 бита

10

Степен на компресия Компр. = 800/240  0.3 . На практика степента на свиване е по-малко защото освен кодовете в компресирания файл трябва да се съхраняват още указатели към възлите и самото дърво.

Методът на Хофман не винаги е подходящ за свиване на първоначалната информация. Очевидно за изображения в които се срещат всички стойности на цветовете от 0-255 и честотата на появяване за всички са равни, то компресирания код за всяка дума ще бъде с дължина 8 бита, така че не настъпва никакво свиване на първоначалния файл.




    1. Алгоритми за свиване на изображения със загуби.

Едно от основните преимущества на алгоритмите за свиване без загуби е тяхната универсалност на приложение, т.е. те са приложими за всякакъв вид данни (файлове). Известни са редица програми за свиване такива като ZIP, ARJ, RAR StuffIt и др. За съжаление методите за свиване без загуби намаляват размерите на файловете, но не толкова много.

Много по-добри резултати от гледна точка на степента на компресия може да бъдат получени при свиване със загуби.

Свиването със загуби е процес при който размерът на съхраняваната информация за даденото изображение се намалява за сметка на изхвърлянето, отстраняването на част от информацията. Свиването със загуби е възможно (приложимо) само при програми обработващи определен вид данни – графични данни (цифрови изображения) или звукови данни.




      1. JPEG компресия

Първите приложения, целящи намаляване на количеството информация, необходима за кодирането на неподвижни картини, се появяват през 80-те години и имат като основна цел значително намаляване на размера на графичните и фотографските файлове от гледна точка на тяхното съхранение или транспортиране.

През 1990г. Международната организация по стандартизация - ISO създаде международна работна група, наречена JPEG (Joint Photographic Expert Group), на която е била поставена задача да разработи международен стандарт за компресиране на неподвижни картини с различна разделителна способност. Полученият международен стандарт (широко известен като JPEG) е публикуван през 1993г. като ръководство за компресиране на неподвижни картини.

В процеса на създаване на стандарта е бил изучен световният опит за повече от половин век, включващ компютърни, телевизионни и други изследвания.


JPEG компресията използва особеностите на човешкото възприемане за максимално намаляване на размера на фотоизображенията.
Според направените изводи, човешкото око вижда размити образи, които впоследствие се обработват от мозъка и картината се прояснява. Поради това, че формулираното твърдение засега е в рамките на хипотезите, групата експерти съсредоточават своите усилия върху разработването на методика, базираща се на факта, че очите реагират повече на промяна на яркостта, отколкото на цвета.

Затова е било взето решение алгоритъмът да осъществява компресия на данните на база особеностите на човешкото зрение. Т,е свиването на информацията при JPEG компресията се основава на недостатъците на човешкото зрение.

Установено е, че зрението на човека е много чувствително към изменението на яркостта на обекта и много по-малко към цветовата наситеност (разлика в наситеността на цветовете).

На тази база JPEG кодирането преминава през следните основни етапи:



Първи етап. Прекодиране на изображението.

От пълно цветно описание (RGB) за всеки пиксел изображението се преобразува в описание на пиксела посредством яркостта му и двата основни цвята червен (Red) и син (Blue). Т.е. на първия етап на кодирането JPEG методът трансформира изображението в триканална система с един канал за яркост - Y и два цветови канала наречени червена – Cr и синя - Cb цветности.


Матрица на прехода:


Y

=


0.299

0.587

0.114




R




0

Cb

0.5

-0.4187

-0.0813

*

G

+

128

Cr

0.1687

-0.3313

0.5




B




128

Обратно преобразувание



R

=


1

0

1.402




Y




0

G

1

-0.34414

-0.71414

*

Cb

-

128

B

1

1.772

0




Cr




128

Благодарение на това, че човешкото зрение е по слабо чувствително към компонентите Cr и Cb, то техните стойности могат да се показват с разреждане по схемата 4:1:1, при което за група от съседни четири пиксела (2Х2) за всеки пиксел се определя неговата яркост Y, а за тяхната осветеност Cr и Cb се използува една осреднена стойност. Това позволява да се съкрати входната информация два пъти. Вместо за четирите точки да се пазят по 3 байта за всеки цвят (R,G,B) – общо 12 байта, то се използуват само 6 байта – 4 байта за чркостта за свяка точка и по един байт за средните стойности на осветеността Cr и Cb. На практика без съществено влошаване на качеството на образа може да се приложи система за разреждане 16:1:1, която води още на първия етап до свиване на информацията 2.67 пъти.

За по натаъшно облекчаване на изчислителния процес изображението се разделя на блокове (участъци) с размери 8Х8 пиксела. Всеки блок е съставен от 64 числа със стойности, вариращи от 0 до 255 (когато са дигитализирани с 8 бита) за яркост и от -128 до +127 за цветностите Сг и Сь.

Стойностите на цветността Сг например в блока 8Х8 за изображението могат да бъдат представени със следната матрица:


| 95 88 88 87 95 88 95 95|

|143 144 151 151 153 170 183 181|

|153 151 162 166 162 151 126 117|

IMG = |143 144 133 130 143 153 159 175|

|123 112 116 130 143 147 162 189|

|133 151 162 166 170 188 166 128|

|160 168 166 159 135 101 93 98|

|154 155 153 144 126 106 118 133|


За цялото изображение се създават три работни матрици.

Матрицата се завърта чрез изваждане от всеки коефициент на числото 128 с цел при последващата обработка да не се получи равномерно разпределение на коефициентите. Получава се нова матрица която има стойности както следва:


|-33 -40 -40 -41 -33 -40 -33 -33|

| 15 16 23 23 25 42 55 53|

| 25 23 34 38 34 23 -2 -11|

IMG = | 15 16 5 2 15 25 31 47|

| -5 -16 -12 2 15 19 34 61|

| 5 23 34 38 42 60 38 0|

| 32 40 38 31 7 -27 -35 -30|

| 26 27 25 16 -2 -22 -10 5|


Втори етап – Дискретно косинусово преобразувание на стойностите.

На първия етап JPEG кодирането определя полутоновия характер на изображението като цяло – конкретни стойности за всеки пиксел. Чрез прилагане на дискретно косинусово преобразувание се получават нови три матрици в които коефициентите съответстват на честотните характеристики на изображението.

Процесът на Дискретно косинусово преобразуванеи може да се раздели на следните етапи:

- получаване на коефициентите за дискретна косинусова трансформация DCT за всеки от 64 елемента на матрицата IMG по формулите:


DCTi,j = 1/√(N), за i=0
DCTi,j = √ (2/N)*cos[(2j+1)*i*3.14/2N], ако i > 0
N = 8,

0 < i < 7 ,

0 < j < 7
като резултат се получава
DCT=

|.353553.353553.353553.353553 .353553 .353553 .353553 .353553|

|.490393.415818.277992.097887-.097106-.277329-.415375-.490246|

|.461978.191618-.190882-.461673-.462282-.192353.190145.461366|

|.414818-.097106-.490246-.278653.276667.490710.099448-.414486|

|.353694-.353131-.354256.352567.354819-.352001-.355378.351435|

|.277992-.490246.096324.416700-.414486-.100228.491013-.274673|

|.191618-.462282.461366-.189409-.193822.463187-.460440.187195|

|.097887-.278653.416700-.490862.489771-.413593.274008-.092414|
ДКП: RES*IMG*DCT

Първо се определя промеждутъчна матрица : TMP = IMG*DCT


|-103 -3 1 2 4 0 -1 5|

| 89 -40 12 -2 -7 5 1 0|

| 57 31 -30 6 2 0 5 0|

TMP = | 55 -28 24 1 0 -8 0 0|

| 32 -60 18 -1 14 0 -8 1|

| 84 -11 -37 17 -24 4 0 -4|

| 19 81 -16 -20 8 -3 4 0|

| 22 40 11 -22 8 0 -3 2|


след това се получава крайната матрица RES = TMP*DCT
| 91 3 -5 -6 2 0 1|

|-38 -57 9 17 -2 2 2|

|-80 58 0 -18 4 3 4|

RES = |-52 -36 -11 13 -9 3 0|

|-86 -40 44 -7 17 -6 4|

|-62 64 -13 -1 3 -8 0|

|-16 14 -35 17 -11 2 -1|

|-53 32 -9 -8 22 0 2|


Коефициентите в матрицата RES показват разпределението на честотата в изменението на яркостта и цветността на блока. Горният ляв ъгъл съдържа средната яркост или цветност на блока, а останалите коефициенти честотата на изменение на различните нива на яркост или осветеност.

Например ако блокът е с постоянна яркост или с непроменяща се оцветеност, то само най-горният ляв коефициент ще бъде различен от нула, а останалите коефициенти ще бъдат равни на нула.



Трети етап – квантоване на изображението т.е. разпределяне на коефициентите по групи нива

В процеса на изследванията се оказало, че за хората е по-важно цялостното възприемане на полутоновата картина. Ние виждаме, че дървото е зелено, а ябълката - червена и едва като се вгледаме по-внимателно отблизо, различаваме оттенъците и "играта на цветовете".

Именно, чрез процеса на квантоване се отстранява тази част от стойностите за описанието на цветността и яркостта на изображението, промяната в значенията на които е неуловима или приемлива за човешкото око.

Квантоването се извършва посредством използуване на т.н. матрици на квантоване – Q. МК са с размери колкото е размерът на блока (в случая 8Х8) и стойностите на всеки един елемент от матрицата се определя по формулата:


Q[i][j] = 1+((1+i+j)*q)

Където: q – се нарича коефициент на качество иот него зависи степента на компресия.

При q=2 МК има вида:
| 3 5 7 9 11 13 15 17|

| 5 7 9 11 13 15 17 19|

| 7 9 11 13 15 17 19 21|

Q = | 9 11 13 15 17 19 21 23|

|11 13 15 17 19 21 23 25|

|13 15 17 19 21 23 25 27|

|15 17 19 21 23 25 27 29|

|17 19 21 23 25 27 29 31|

Матрицата на квантоване се пази в началото на компресирания файл за да може да се използува при де компресията на данните.

Квантоването се извършва чрез разделяне на всеки елемент от матрицата RES на всеки съответен елемент от матрицата МК.


В резултат на извършеното квантоване се получава матрицата съдържаща компресирани данни за изображението.
| 30 0 0 0 0 0 0 0|

| -7 8 1 1 0 0 0 0|

|-11 6 0 1 0 0 0 0|

A = | -5 -3 0 0 0 0 0 0|

| -7 -3 2 0 0 0 0 0|

| -4 4 0 0 0 0 0 0|

| -1 0 1 0 0 0 0 0|

| -3 1 0 0 0 0 0 0|


Т.е на етап квантоване се извършва най осезателното свиване на информацията, но и най-голяма загуба на качество на изображението.
Четвърти етап – представяне на двумерния масив като едномерен.
За представяне на двумерния масив като едномерен най-удачен метод за обхождане се оказва метода “зиг-заг”. При което се получава следната поредица от стойности:

30,0,-7,-11,8,0,0,1,6,-5,-7,-3,0,1,0,0,0,1,0,-3,-4,-1,-3,0,0,0,0,0,0,0,0,0,0,0, 0,1,1,0,0,0,0,0,0,0,0,0,0 ….





Пети етап – RLE кодиране.

Извършва се като последователността от стойности се представи като последователност от двойки числа при което за всяка двойка първото число показва броя последователни нули, а второто – значещата стойност след първата нула.

За конкретния пример ще имаме:

(0,30) (1,-7) (0,-11) (0,8) (2,1) (0,6) (0,-5) (0,-7) (0,-3) (1,1) (3,1) (1,-3) (0,-4) (0,-1) (12,1) ….


Шест етап –кодиране по Хофман.

Кодиране на стойностите с еднаква дължина като стойности с променлива дължина в зависимост от честотата на появяване. По често появяващите се с по малка дължина, а по рядко появяващите се с по-голяма дължина.



Заключение
Установихме, че JPEG е сложен алгоритъм, формиран от серия различни по-прости алгоритми. Някои от тях са със загуба на данни, а други – без. Алгоритъмът за компресия JPEG се използва като база за други алгоритми като M-JPEG (Motion JPEG), който е последователност от JPEG и се използва за видео. Друга компресия, базирана на JPEG е популярният MPEG.

С JPEG е възможно да записвате изображения с компресия 10:1, но с някои условия.
Каталог: tadmin -> upload -> storage
storage -> Литература на факта. Аналитизъм. Интерпретативни стратегии. Въпроси и задачи
storage -> Лекция №2 Същност на цифровите изображения Въпрос. Основни положения от теория на сигналите
storage -> Лекция 5 система за вторична радиолокация
storage -> Толерантност и етничност в медийния дискурс
storage -> Ethnicity and tolerance in media discourse revisited Desislava St. Cheshmedzhieva-Stoycheva abstract
storage -> Тест №1 Отбележете невярното твърдение за подчертаните думи
storage -> Лекции по Въведение в статистиката
storage -> Търсене на живот във вселената увод
storage -> Еп. Константинови четения – 2010 г някои аспекти на концептуализация на богатството в руски и турски език


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©obuch.info 2019
отнасят до администрацията

    Начална страница