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

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

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

Една супена лъжица статия в Уикипедия:

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

Този стандарт е разработен от Joint Photographic Experts Group през 1991 г. за ефективно компресиране на изображения.

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

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

Първо, цветовият модел се променя от RGB на YCbCr. Дори има специален алгоритъм за това - тук. Y не се докосва, тъй като е отговорен за яркостта и промяната му ще бъде забележима.

Първото нещо, което трябва да направите с изображението е "изтъняване" (подизвадка). Лесно е да се разбере: взема се масив от пиксели 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 пиксела хоризонтално и вертикално. Първият вариант се използва по-често. Ако качеството на изображението е важно, децимацията изобщо не се извършва.
Визуална илюстрация на изтъняване (Habr не ми позволи да вмъкна gif) - https://i.ibb.co/Rg5Th9H/150953010617579181.gif

Основната част от подготовката

DCM

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

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

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

Квантуване

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

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

компресия

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

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

Когато се използва

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

Продукция

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

източници

Статия за YCbCr в Wikipedia
Статия в Wikipedia за JPEG
Малко за PrEP от публикацията на Pikabu
Статия в Wikipedia за PrEP

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