Вступление
Кодирование длин серий — это алгоритм сжатия данных, который помогает нам кодировать большие серии повторяющихся элементов, отправляя только один элемент из серии и счетчик, показывающий, сколько раз этот элемент повторяется. К сожалению, этот метод бесполезен при попытке сжать тексты на естественном языке, потому что они не имеют длинных серий повторяющихся элементов. С другой стороны, RLE полезен, когда речь идет о сжатии изображений, поскольку у изображений длинные пиксели одинакового цвета.
Как вы можете видеть на следующем рисунке, мы можем сжимать последовательные пиксели, заменяя только каждый прогон одним пикселем из него и счетчиком, показывающим, сколько элементов в нем содержится.
Хотя RLE без потерь может быть весьма эффективным для сжатия изображений, это все же не лучший подход!
В этом случае мы можем сохранить только счетчики для пикселей, которые повторяются более одного раза. Такой входной поток «aaaabbaba» будет сжат как «[4] a [2] baba».
На самом деле существует несколько способов кодирования длин серий для сжатия изображений. Возможным способом сжатия изображения может быть строка за строкой или столбец за столбцом, как показано на рисунке ниже.
Строка за строкой или столбец за столбцом сжатия.
Проблема на практике заключается в том, что иногда сжатие строка за строкой может быть эффективным, в то время как в других случаях такой же подход очень неэффективен. Это иллюстрируется изображением ниже.
Иногда сжатие изображения может быть сделано только после некоторой предварительной обработки, которая может помочь нам понять лучший подход сжатия!
Очевидно, что кодирование по длине прогона является очень хорошим подходом при сжатии изображений, однако, когда мы говорим о больших изображениях с миллионами пикселей, как-то естественно иметь место с некоторым сжатием с потерями.
обзор
Lossy RLE — очень подходящий алгоритм, когда дело доходит до изображений, потому что в большинстве случаев большие изображения имеют большие пространства одинаковых цветов пикселей, то есть когда половина изображения — голубое небо. Используя сжатие с потерями, мы можем пропустить очень короткие пробеги.
Сначала мы должны сказать, как долго будет самый короткий прогон, который мы будем хранить при сжатии. Например, если 3 — самый короткий прогон, то прогоны 2 последовательных элементов будут пропущены.
Сжатие строки пикселей без потерь в некоторых случаях может быть очень неэффективным!
Конечно, если мы установим самый короткий цикл длиной всего один элемент, это сделает наше сжатие полностью без потерь, что не очень эффективно. Однако, когда мы говорим о миллионах пикселей, даже серии из трех или более элементов очень короткие, поэтому разработчик должен решить, как долго будет самый короткий цикл.
Несколько примеров
Давайте сначала определим кратчайший пробег, который мы оставим нетронутым, чтобы он был длиной не менее трех элементов.
Мы можем потерять некоторую информацию, которая невидима для глаз.
Приведенное выше изображение сжимается более эффективно, чем ряд пикселей без потерь из предыдущего изображения.
Дело в том, как объединить короткие пробеги. Например, следующие три серии должны быть смешаны в одну серию цветов.
Мы должны выбрать, как смешивать короткие пробеги!
Мы можем выбрать средний цвет (вариант № 1) или нет, но это всегда будет зависеть от изображения, и оно будет эффективным в одних случаях и неэффективным в других.
Реализация
Реализация кодирования длин серий в общем проста. Вот простой код PHP, который показывает RLE с потерями.
/** * Compresses an input list of objects by losing some data using * run-length encoding * * @param mixed $objectList * @param int $minLength */ function lossyRLE($objectList, $minLength) { $len = is_string($objectList) ? strlen($objectList) // string as an input stream : count($objectList); // array as an input stream $j = 1; $compressed = array(); // compressed output for ($i = 0; $i < $len; $i++) { if (isset($objectList[$i+1]) && $objectList[$i] == $objectList[$i+1]) { $j++; } else { $l = count($compressed); // This is where RLE is converted to a lossy algorithm! // In case the run is shorter than a predefined length the // algorithm will skip these elements and will stretch the last // saved run. // NOTE: this logic can be changed in order to take other // decisions depending on the goals. if ($j < $minLength && $j < $l) { $compressed[$l-1]['count'] += $j; } else { $compressed[] = array('count' => $j, $objectList[$i]); } $j = 1; } } return $compressed; } $input = 'aaaabbaabbbbba'; // aaaaaaaabbbbbb lossyRLE($input, 3);
Код выше может быть изменен для работы с более сложными данными. Допустим, у нас есть «пиксельная» абстракция, как в примере выше.
/** * Pixel abstraction */ class Pixel { private $_color = null; public function __construct($color = '') { $this->_color = $color; } public function getColor() { return $this->_color; } } /** * Inits the pixels array * * @param array $pixels */ function init(array &$pixels = array()) { $colors = array('red', 'green', 'blue'); for ($i = 0; $i < 100; $i++) { $pixels[] = new Pixel($colors[mt_rand(0, 2)]); } } /** * Compresses an input list of objects by losing some data using * run-length encoding * * @param mixed $objectList * @param int $minLength */ function lossyRLE($objectList, $minLength) { $len = is_string($objectList) ? strlen($objectList) // string as an input stream : count($objectList); // array as an input stream $j = 1; $compressed = array(); // compressed output for ($i = 0; $i < $len; $i++) { if (isset($objectList[$i+1]) && $objectList[$i] == $objectList[$i+1]) { $j++; } else { $l = count($compressed); // This is where RLE is converted to a lossy algorithm! // In case the run is shorter than a predefined length the // algorithm will skip these elements and will stretch the last // saved run. // NOTE: this logic can be changed in order to take other // decisions depending on the goals. if ($j < $minLength && $l > $j) { $compressed[$l-1]['count'] += $j; } else { $compressed[] = array('count' => $j, $objectList[$i]); } $j = 1; } } return $compressed; } $pixels = array(); // initializes the pixels array init($pixels); $compressed = lossyRLE($pixels, 3); print_r($compressed);
сложность
В общем, RLE без потерь линейна — O (n), где n — количество элементов из входного потока. Даже с небольшой модификацией выше сложность остается линейной. Однако мы можем изменить сжатие немного по-другому (чтобы получить среднее значение из последовательных коротких прогонов). Конечно, это как-то повлияет на сложность алгоритма.
заявка
Кодирование по длинам серий не очень эффективно при сжатии текстов, но для изображений, где случаются длинные серии идентичных пикселей, это весьма полезно.
Тем не менее, RLE легко преобразовать в алгоритм с потерями, что делает его очень подходящим для сжатия изображений.
Похожие сообщения: