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