Алгоритм RLE: опис, особливості, правила і приклади

Алгоритм RLE — це алгоритм стиснення даних, який підтримується більшістю форматів файлів растрових зображень: TIFF, BMP і PCX. RLE підходить для стиснення будь-якого типу даних незалежно від його вмісту, але зміст даних впливає на коефіцієнт стиснення. Незважаючи на те, що більшість алгоритмів RLE не можуть забезпечити високі коефіцієнти стиснення більш складних методів, даний інструмент легко реалізувати і швидко виконати, що робить його гарною альтернативою.

На чому заснований алгоритм стиснення RLE?

RLE працює, зменшуючи фізичний розмір повторюваної рядка символів. Ця рядок, звана run, зазвичай кодується в два байти. Перший байт являє кількість символів у пробігу і називається лічильником прогону. На практиці кодований прогін може включати від 1 до 128 і 256 символів. Лічильник зазвичай містить число символів мінус один (значення в діапазоні значень від 0 до 127 і 255). Другий байт — це значення символу в прогоні, яке міститься в діапазоні значень від 0 до 255 і іменується значенням запуску.


Без стиснення символьний пробіг у 15 символів зазвичай вимагає 15 байтів для зберігання: AAAAAAAAAAAAAAA. В тому ж рядку після RLE-кодування потрібно тільки два байти: 15А. Кодування 15A, згенерована для позначення символьного рядка, називається RLE-пакетом. В даному коді перший байт, 15 є лічильником прогону і містить необхідну кількість повторень. Другий байт, A, є значенням run і містить фактичне повторюване значення у пробігу. Новий пакет генерується кожен раз, коли символ запуску змінюється, або кожен раз, коли кількість символів у пробігу перевищує максимальну кількість. Припустимо, що 15-символьний рядок згідно з умовами містить 4 різних символи:


AAAAAAbbbXXXXXt Використовуючи кодування з довжиною рядка, вона може бути стиснута в чотири двобайтових пакету: 6A3b5X1t Після кодування по довжині рядка 15-байтовій рядка потрібно всього вісім байтів даних для представлення рядка, на відміну від вихідних 15 байтів. У цьому випадку кодування під час виконання давало коефіцієнт стиснення майже 2 до 1.

Особливості

Довгі прогони рідкісні в деяких типах даних. Наприклад, відкритий текст ASCII рідко містить довгі прогони. У попередньому прикладі останній пробіг (містить символ t) був тільки одним символом в довжину. 1-символьний прогін все ще працює. І рахунок запуску, і значення запуску повинні бути записані для кожного пробігу в 2 символи. Для кодування пробігу з допомогою алгоритму RLE потрібна інформація, яка складається не менш ніж з двох символів. У зв'язку з чим запуск одиночних символів насправді займає більше місця. З тих же причин дані, що складаються повністю з 2-символьних прогонів, залишаються незмінними після кодування RLE. Схеми алгоритму стиснення RLE відрізняються простотою і високою швидкістю виконання, але їх ефективність залежить від типу кодованих даних зображення. Чорно-біле зображення, яке в основному білого кольору, наприклад, сторінки книги, буде дуже добре кодуватися з-за великої кількості суміжних даних, що мають однаковий колір. Однак зображення з багатьма кольорами, наприклад, фотографія, не буде кодуватися так само добре. Це пов'язано з тим, що складність зображення виражається у вигляді великої кількості різних кольорів. І з-за цієї складності буде відносно мало пробігів одного кольору.

Варіанти кодування по довжині

Існує кілька варіантів кодування під час виконання. Дані зображення, як правило, закодовані у послідовному процесі, який обробляє візуальний контент як 1D-потік, а не як 2D-карту даних. При послідовній обробці растрове зображення кодується, стартуючи з верхнього лівого кута, і прямує зліва направо по кожному рядку сканування в нижній правий кут растрового зображення. Але альтернативні схеми RLE також можуть бути записані для кодування даних по довжині растрового зображення вздовж стовпців для стиснення в 2D-плитки або навіть для кодування пікселів по діагоналі зигзагоподібним способом. Непарні варіанти RLE можуть використовуватися в вузькоспеціалізованих додатках, але зазвичай зустрічаються досить рідко.

Алгоритм кодування з помилкою довжини пробігу

Іншим рідкісним варіантом є алгоритм кодування RLE з помилкою довжини пробігу. Дані інструменти зазвичай виконують стиснення без втрат, однак відкидання даних під час процесу кодування, як правило, шляхом обнулення одного або двох молодших значущих бітів в кожному пікселі, може збільшити коефіцієнти стиснення, не впливаючи негативно на якість складних зображень. Ця програма алгоритму RLE добре працює тільки із зображенням реального світу, що містять багато тонких варіацій значень пікселів.

Крос-кодування

Крос-кодування — це об'єднання рядків сканування, яке відбувається, коли процес стиснення втрачає відмінність між вихідними лініями. Якщо дані окремих ліній об'єднані алгоритмом кодування повторів RLE, точка, де одна лінія сканування зупинена, а інша - втрачена, є вразливою і складною для визначення.
Іноді відбувається перехресне кодування, яке ускладнює процес декодування, додаючи вартість часу. Для форматів файлів растрових зображень цей метод ставить за мету організувати растрове зображення по лініях сканування. Хоча багато специфікації формату файлів явно вказують, що дані рядка повинні бути індивідуально кодовані, багато додатків кодують ці зображення як безперервний потік, ігноруючи кордону рядків.

Як за допомогою алгоритму RLE закодувати зображення?

Індивідуальне кодування рядків сканування має переваги в тих випадках, коли додаток повинен використовувати лише деяку частину зображення. Припустимо, що фото містить 512 рядків розгортки, і необхідно відображати тільки рядки від 100 до 110. Якщо ми не знали, де рядка сканування починалися і закінчувалися даними кодованого зображення, нашого додатком довелося б декодувати рядки з 1 по 100 перш ніж знайти десять рядків, які потрібні. Якщо переходи між лініями сканування були відзначені якимось легко впізнаваним маркером розмежування, додаток могло б просто зчитувати закодовані дані, підраховуючи маркери, поки не дійде до потрібних йому рядків. Але цей підхід був би досить неефективним.

Альтернативний варіант

Іншим варіантом для визначення початкової точки будь-якої конкретної рядка сканування в блоці кодованих даних є побудова таблиці рядків розгортки. Ця таблична структура зазвичай містить один елемент кожного рядка сканування на зображенні, і кожний елемент містить значення зміщення відповідного рядка сканування. Щоб знайти перший RLE-пакет рядка 10 сканування, все, що потрібно зробити декодеру, — це знайти значення позиції зсуву, який зберігається у десятому елементі таблиці пошуку рядка сканування. Таблиця рядків розгортки також може містити кількість байтів, які використовуються для кодування кожного рядка. Використовуючи цей метод з метою знайти перший RLE-пакет рядка сканування 10 ваш декодер буде об'єднувати значення перших 9-ти елементів таблиці рядків розгортки. Перший пакет для рядка 10 сканування буде починатися з цього зміщення байту від початку даних зображення з кодуванням RLE.

Одиниці виміру

Частини алгоритмів кодування по довжині, які різняться, — це рішення, які приймаються на основі типу даних, які декодуються (наприклад, довжина прогону даних). Схеми RLE, що використовуються для стиснення растрової графіки, зазвичай поділяються на класи за типом атомних (тобто найбільш фундаментальних елементів, які вони кодують. Три класи, використовувані більшістю графічних форматів файлів, — це біти, байти і піксельні RLE.

Якість стиснення

Бітові рівні RLE-схем кодують прогони декількох біт у рядку сканування і ігнорують кордону байтів і слів. Лише монохромні (чорно-білі), 1-бітні зображення містять достатню кількість біт, щоб зробити цей клас RLE-кодування ефективним. Типова схема RLE на рівні біт кодує від одного до 128 біт в однобайтовом пакеті. Сім молодших значущих біт містять лічильник запуску мінус один, а старший біт містить значення бітового прогону, рівне 0 або 1. Прогін довжиною понад 128 пікселів розбитий на кілька RLE-кодованих пакетів.

Виключення

Схеми RLE на рівні байта кодують прогони однакових байтових значень, ігноруючи деякі біти і межі слів у рядку сканування. Найбільш поширена схема RLE на байтовому рівні кодує прогони байтів у 2-байтові пакети. Перший байт містить лічильник від 0 до 255 а другий — містить значення байтового запуску. Також поширене додаток dbcs схеми кодування з можливістю зберігання литеральных, незаписаних прогонів байтів в потоці кодованих даних. У такій схемі сім молодших значущих біт першого байта містять лічильник прогону мінус один, а найстарший біт першого байта є індикатором типу запуску, який слідує за байтом підрахунку прогону. Якщо старший біт встановлений в 1 він позначає кодований прогін. Закодовані прогони декодуються шляхом зчитування значення пробігу і повторення його кількості разів, зазначеного числом циклів. Якщо найстарший біт встановлений в 0 відображається литеральный прогін, а це означає, що байти підрахунку наступного прогону зчитуються буквально з даних кодованого зображення. Потім байт лічильника виконання містить значення в діапазоні від 0 до 127 (лічильник запуску мінус один). Схеми RLE на рівні байта гарні для даних зображення, які зберігаються як один байт на піксел. Схеми RLE на рівні пікселів використовуються, коли два або більше послідовних байта даних зображення використовуються для зберігання значень одного пікселя. На рівні пікселів біти ігноруються, а байти підраховуються тільки для ідентифікації кожного значення пікселя. Розмір кодованих пакетів залежить від розміру кодованих значень пікселів. Кількість біт або байтів на піксель зберігається в заголовку файлу зображення. Запуск даних зображення, збережені у вигляді 3-байтових значень пікселів, кодується 4-байтовий пакет, з одним байтом підрахунку кількості операцій, за яким слідують три байти з байтами. Метод кодування залишається таким же, як і з байтовим RLE.