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

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

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

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

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

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

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

• 
  15 или 16 бита/пиксел (Red-5, Green-5(6), Blue-5) – 32К или 64К цветове (Higt Color)
  
• 
  24 или 32 бита/пиксел – по един байт на компонент R,G и B, което осигурява създаване на 16 Мб цветове (True Color).
  

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

• 
  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

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

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

2. 
   Информационен блок (Bit Map Info Header)
   
3. 
   Палитра (Color Table)
   
4. 
   Данни за самото изображение (BitMap Array)
   

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

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

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

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

1. 
   Изображенията изискват наличие на значително по-големи обеми от памет за съхранение в сравнение с текстовете. Например илюстрация със средно качество с размер 500Х800 точки заема 1.2 Мб памет – толкова колкото художествена книга от 400 страници стандартен текст (60 знака на ред и 42 реда на страница) Тази особеност на изображението налага актуалността на алгоритмите за компресия на цифровите изображения.
   
2. 
   Втората особеност на изображенията се характеризира с това, че човешкото зрение при анализ на изображенията оперира с контурите, общите изменения на цветовете и е нечувствително към малките изменения в изображението. Това позволява да бъдат използувани такива схеми на компресия, при които благодарение на това, че декомпресираното изображение не се явява точно възстановяване на оригинала, но това остава незабележимо за човешкото око. Тази особеност на човешкото зрение позволява да се създадат специални алгоритми за свиване (компресия), предназначени специално за изображения, в отличие от тези за компресия на текст например. Тези алгоритми позволяват голяма степен на свиване с незначителни от гледна точка на човешкото зрение загуби.
   
3. 
   Лесно може да се забележи, че изображението за разлика от текста притежава свръх информация в две измерения. По хоризонтала и по вертикала по отношение на близките по положение и цвят съседни точки. Освен това в алгоритмите за компресия може да се използува и подобието между цветовите плоскости (матрици) R,G и B, което позволява постигане на още по-голяма ефективност. Т.е при създаване на алгоритмите за компресиране се използуват и структурните особености на изображенията.
   

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

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

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

1. 
   Висока степен на компресия;
   
2. 
   Високо качество на изображението;
   
3. 
   Висока скорост на компресия;
   
4. 
   Висока скорост на декомпресия;
   
5. 
   Лесно мащабиране на изображението;
   
6. 
   Възможност за показване на грубо ( с ниско разрешение) изображение използувайки само началото на файла (preview);
   
7. 
   Устойчивост към грешки – при предаване по линии за свръзка – прекъсванията да не оказват влияние на данните получени след прекъсването на връзката
   
8. 
   Редактируемост – да не се влошава значително изображението при няколко последователни итерации на архивиране, дезархивиране с редакци и последващо архивиране;
   
9. 
   Не скъпа апаратна и ефективна програмна реализация.
   

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тогава компресираното изображение ще изглежда така:
File header, N₁B₁,N₂B₂,N₃B₁,N₄B₃,…………,N_kB_m, End file

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

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

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

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

Нека имаме 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

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

87	1	253		13		154	55
5	10	10		20		25	30

15

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

|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 с цел при последващата обработка да не се получи равномерно разпределение на коефициентите. Получава се нова матрица която има стойности както следва:

| 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 по формулите:

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

| 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|

|-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|

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

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

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

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

Където: 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 на всеки съответен елемент от матрицата МК.

| -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 ….

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

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

(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) ….

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