RLE алгоритъм: описание, характеристики, правила и примери

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

Каква е основата на алгоритъма за компресия на RLE?

RLE работи, като намалява физическия размер на повтарящия се символен низ. Тази линия, наречена Run, обикновено се кодира в два байта. Първият байт представлява броя на символите в теста и се нарича брояч на текущите. На практика кодираното изпълнение може да включва от 1 до 128 и 256 знака. Броячът обикновено съдържа броя знаци минус един (стойност в диапазона от 0 до 127 и 255). Вторият байт е стойността на символа в хода, който се съдържа в диапазона от стойности от 0 до 255 и се нарича начална стойност.

Без компресия, символичното изпълнение от 15 знака обикновено изисква 15 байта да се съхраняват:

AAAAAAAAAAAAAAA.

В същия ред след RLE кодиране са необходими само два байта: 15A.

Кодирането 15А, генерирано за обозначаване на символен низ, се нарича пакет RLE. В този код първият байт, 15, е броячът за теглене и съдържа необходимия брой повторения. Вторият байт, A, е стойността на текущото състояние и съдържа действителната повтаряща се стойност в теста.

Всеки път, когато се променя символът за стартиране, се генерира нов пакет или всеки път, когато броят на символите в теста надхвърля максималния брой. Да предположим, че 15-знаков низ, според условията, съдържа 4 различни символа:

AAAAAAbbbXXXXXt

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

6A3b5X1t

След кодиране на дължината на линията за 15-байтов низ, за ​​да се представя низът, за разлика от оригиналните 15 байта, са необходими само осем байта за данни. В този случай кодирането за време на изпълнение даде съотношение на компресия от почти 2 към 1.

Удобства

Дългите писти са рядкост при някои типове данни. Например обикновеният ASCII текст рядко съдържа дълги писти. В предишния пример последното изпълнение (съдържащо символа t) е само с един знак. Изпълнението на 1 знак все още действа. Както за началното броене, така и за началната стойност трябва да се напише за всяко изпълнение от 2 знака. За кодирането на програмата, използвайки алгоритъма RLE, се изисква информация, състояща се от най-малко два символа. В тази връзка пускането на отделни символи всъщност отнема повече пространство. По същите причини данните, състоящи се изцяло от 2 символа, остават непроменени след кодирането на RLE.

Схемите на алгоритъма за компресия на RLE се различават по опростеност и висока скорост на изпълнение, но тяхната ефективност зависи от вида на кодираните данни за изображения. Черно-бяло изображение, което е предимно бяло на цвят, например книга, ще бъде много добре кодирано, поради големия брой съседни данни със същия цвят. Обаче изображение с много цветове, като снимка, също няма да бъде кодирано. Това се дължи на факта, че сложността на изображението се изразява във формата на голям брой различни цветове. И поради тази сложност ще има сравнително малко писти от един и същи цвят.

Кодиране на опции за дължина

Има няколко опции за кодиране по време на изпълнение. Данните за изображения обикновено се кодират в последователен процес, който обработва визуалното съдържание като 1D поток, а не като 2D карта за данни. В сериен обработка на растерна графика, кодиран, като се започне от горния ляв ъгъл и отива от ляво на дясно на всяка сканиране линия в долния десен ъгъл на растерна графика. УПИ но алтернативно могат също да бъдат записани за кодиране на данни дължина по колони на растерното изображение за компресиране на 2D-плочки или дори за кодиране на пиксела диагонално зигзагообразни начин. Нечетните варианти на RLE могат да се използват при високо специализирани приложения, но обикновено са редки.

Алгоритъм за кодиране с грешка за дължина на изпълнение

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

Cross-кодиране

Кръстосаното кодиране е комбинация от линии за сканиране, които се появяват, когато процесът на компресиране губи разликата между източниците. Ако данните от отделните линии се комбинират с алгоритъма за кодиране на повторяемост 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, а вторият съдържа началната стойност на байтовете. Също така е обичайно да се добави двубайтова схема за кодиране със способността да се съхраняват буквални, неписани байтове в потока от кодирани данни.

В такава схема седемте най-значими битове на първия байт съдържат брояч на текущите минус един, а най-значимият бит от първия байт е индикатор за началния тип, който следва байта от броя на хода. Ако най-значимият бит е настроен на 1, той показва кодирано изпълнение. Кодираните пикове се декодират чрез отчитане на стойността на километража и повтаряне на броя пъти, отбелязани с броя на циклите. Ако най-значимият бит е настроен на 0, се показва буквално изпълнение, което означава, че байтовете за броя на следващата операция се четат буквално от кодираните данни за изображения. Тогава броячът за изпълнение на изпълнение съдържа стойност в диапазона от 0 до 127 (начален брой минус един). Схемите RLE на нивото на байтовете са добри за изображенията, които се съхраняват като един байт на пиксел.

Схемите RLE на нивото на пикселите се използват, когато два или повече последователни байта от изображения се използват за съхраняване на стойностите на един пиксел. На нивото на пикселите битовете се игнорират, а байтовете се отчитат само за идентифициране на всяка пикселна стойност. Размерът на кодираните пакети зависи от размера на кодираните стойности на пикселите. Броят на бита или байтовете на пиксел се записва в заглавката на файла с изображение. Изпълняващите се изображения, съхранявани като 3-байтови пикселни стойности, се кодират в 4-байтов пакет, като един байт брои броя операции, последвани от три байта с байтове. Методът на кодиране остава същият като при байта RLE.