Компресия на изображения без загуби

Навсякъде около нас има изображения, от иконите на приложенията до анимирани GIF-файлове, до снимки. Файловете с изображения могат да заемат много място и затова компютрите използват множество алгоритми, за да ги компресират.

За най-простите изображения компютрите могат да използват компресия, наречена Kодиране по дължина (Run-legth encoding - RLE).

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

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

Нека увеличим изображението и да наложим върху него решетка, за да е по-лесно да видим точно кои пиксели са червени и кои са бели:

Иконата на сърце има само два цвята – червен и бял, така че може да бъде представена в двоичен вид от компютър, като червените пиксели се отбележат с $1$‍, а белите пиксели – с $0$‍. Наричаме това битова карта (bitmap), тъй като тя разчертава пикселите в битове.

Използвайки този метод, ще представим иконата на сърце по следния начин:

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

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

Например първия ред съдържа 3 бели, 2 червени, 5 бели, 2 червени и накрая 4 бели пиксела:

Това може да бъде представено така:

Четвъртъртият ред е интересен, тъй като започва с червен пиксел. Кодирането по дължина започва с броя бели пиксели, така че ето как ще бъде представен той:

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

Да опитаме. Това е представяне на черно-бяла икона с помощта на Кодиране по дължина:

Първият ред съдържа 4 бели пиксела, след това 9 черни пиксела, след това 3 бели пиксела. Ето как изглежда това:

Следващият ред съдържа 4 бели пиксела, след това 7 черни, 2 бели, 1 черен и 2 бели. Изглежда така:

Продължаваме така и накрая иконата е чаша и чинийка:

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

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

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

Какво се случва при изображения с еднакви размери? Следната таблица обобщава резултатите от компресирането на 3 големи икони с помощта на Кодиране по дължина:

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

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

Какво ще кажеш за тази 16х16 икона?

Нека я увеличим, за да можем да видим всеки пиксел:

Всеки пиксел в тази икона е с различен цвят и няма поредици

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

Оказва се, че фотографските изображения са подобни на тази икона – реалният свят е пълен с детайли, които прекъсват поредиците.

Страницата на екипа на Кан Академия включва тази очарователна снимка на куче, гледащо в компютърен екран:

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

Да увеличим и да видим пикселите:

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

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

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

Къде се използва Кодиране по дължина днес? Факс машините все още използват Кодиране по дължина за компресия на факс-документи, тъй като те трябва да преставят само черни и бели букви. JPEG изображенията използват Кодиране по дължина при финалната фаза на компресия, но преди това използват по-сложен алгоритъм, за да компресират фотографските детайли. Скоро ще се запознаем с това в детайли.

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Имаш ли въпроси по темата? Ще се радваме да ти отговорим, просто задай въпросите си по-долу!