🥇JPEG. Алгоритъм на компресия

Здравейте отново! Намерих тази статия, написана през май 2019 година. Това е продължение на серия от статии за WAVE и JPEG. Ето първата. Тази публикация ще включва информация за алгоритъма за кодиране на изображения и за самия формат в цялост.

Щипка история

Лъжица от статията в Уикипедия:

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

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

Как си преминават изображенията от суров вид до JPEG

Някои смятат, че JPEG изображенията са компресирани чрез метода на Хъфман сурови данни, но това не е така. Преди контролната компресия, данните преминават дълъг път.

Първото нещо, което правят с изображението, е тук.„потискане“

(subsampling). Разбирането е просто: взима се 2x2 масив от пиксели, след това се вземат Cb и Cr - средните стойности на всеки от компонентите YCbCr на тези 4 пиксела. И така, печелим 6 байта , вместо 4 Y, 4 Cb, 4 Cr получаваме 4 Y и еднакви за всеки от тях Cb и Cr (4 + 4 + 4 = 12; 4 + 1 + 1 = 6; 12 - 6 = 6). В мащабите дори на 2x2, компресията с загуби с коефициент на компресия 2:1 звучи солидно. Това се прилага за цялото изображение. И така - намалихме размера наполовина. А такъв подход можем да използваме благодарение на нашето цветово възприятие. Човек лесно забелязва разликата в яркостта, но не и в цвета, ако той е среден в малък блок от пиксели. Освен това потискането може да се извършва по линия, 4 пиксела хоризонтално и вертикално. Първият вариант се използва по-често. Ако качеството на изображението е важно, потискането изобщо не се извършва. Ясна илюстрация на потискането (Хабр не позволи вмъкването на гифка) -Основна част от подготовката
ДКП https://i.ibb.co/Rg5Th9H/150953010617579181.gif

Сега идва най-сложната и необходима част. Цялата картинка се разбива на блокове 8x8 (използва се запълване в случай, че разрешението не е кратно на страната на блока).

Сега на всеки блок се прилага

ДКП (Дискретно косинусно преобразуване)

Сега всеки блок прилага ДКП (Дискретно-косинусно преобразуване). В тази част от изображението се изваждат всички излишни елементи. Използвайки DCT, трябва да разберем дали този блок (8×8) описва някаква монотонна част от изображението: небо, стена; или съдържа сложна структура (коси, символи и т.н.). Логично е, че 64 пиксела със сходен цвят могат да бъдат описани само с 1, тъй като размерът на блока вече е известен. Вот ви и компресия: 64 към 1.

DCT преобразува блока в спектър, и там, където показанията рязко се изменят, коефициентът става положителен, и колкото по-рязък е преходът, толкова по-висок ще бъде изходът. Там, където коефициентът е по-висок, върху изображението са изобразени ясни преходи в цвета и яркостта, а където е по-нисък — слаби (плавни) промени на компонентите YCbCr в блока.

Квантоване

Тук вече се прилагат настройките за компресия. Всеки от коефициентите в матриците 8×8 се дели на определено число. Ако не възнамерявате да намалявате качеството на изображението след всички негови модификации, делителят трябва да бъде единица. Ако е по-важно за вас паметта, която заема тази снимка, делителят ще бъде по-голям от 1, и частното се закръглява. Така се оказва, че след закръглянето често остава много нули.

Квантоването се извършва с цел да се създаде възможност за още по-голямо компресиране. Ето как изглежда това на примера на квантоването на графиката y = sin(x):

JPEG. Алгоритъм за компресия

Сжатие

Първо преминаваме през матрицата зиг-загом:

JPEG. Алгоритъм за компресия

Получаваме едномерен масив с числа. Виждаме, че в него има много нули, които можем да премахнем. За това вместо последователност от много нули записваме 1 нула и след нея число, което обозначава тяхното количество в последователността. По този начин можем да намалим до 1/3 размера на целия масив. А след това просто компресираме този масив с метода на Хъфман и го записваме в самия файл.

Къде се използва

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

Извод

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

Източници

Статия за YCbCr в Уикипедия
Статия за JPEG в Уикипедия
Малко за DCT от пост на Пикабу
Статия за DCT в Уикипедия

Източник: habr.com