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

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

Дозировка история

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

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

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

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

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

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

(subsampling). Това е просто: взима се 2х2 масив от пиксели, след това се взимат 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). В мащабите дори на 2×2 компресията с загуба с коефициент 2:1 звучи сериозно. Това се прилага върху цялото изображение. И така — освобождаваме половината размер. И такъв подход можем да използваме благодарение на нашето цветово възприятие. Човек лесно ще забележи разликата в яркост, но не и в цвета, ако той е среден в малък блок пиксели. Прореждането може да се извършва и в ред, 4 пиксела по хоризонтала и вертикала. Първият вариант се използва по-често. Ако качеството на изображението е важно, то прореждането не се извършва изобщо. Ясна илюстрация на подредбата (Хабр не позволи вмъкване на гифка) —Основна част от подготовката
ДКП https://i.ibb.co/Rg5Th9H/150953010617579181.gif

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

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

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

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

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

Квантоване

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

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

Сжатие

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

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

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

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

Извод

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

Източници

Статия за YCbCr в Wikipedia
Статия за JPEG в Wikipedia
Нещо за ДКП от поста Pikabu
Статия за ДКП в Wikipedia

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