Метод сжатие изображений без потерь и почти без потерь, низкой сложности

Краткий обзор

В данной статье будет представлена схема сжатия, комбинирующая высокую эффективность сжатия и низкую сложность схемы сжатия без потерь с гибкостью схемы сжатия почти без потерь. Входное изображение делится на две части: старшую значащую часть, которая сжимается без потерь и младшую, которая будет сжата масштабируемым кодером. Кроме того будет представлен очень низкий, по своей сложности метод сжатия без потерь, который также предназначен, для автоматического определения точки разделения между старшими и младшими значащими частями, для масштабируемого сжатия.

Масштабируемое сжатие почти без потерь

Блок-схема представленного метода, выглядит следующим образом:

Сигнал (цифровой), анализируется и делится на две части: старшую значимую часть и младшую значимую часть. Поделенный сигнал X, может быть описан математически, как Xms = X div k, для старшей значимой части и Xls = X mod k, для младшей значимой части. Параметр k=2^m (где m = 0, 1, 2, ….). Старшая значимая часть сжимается методом сжатия без потерь (в частности JPEG-LS). Младшая часть, сжата масштабируемым кодером, т.е. таким способом при котором, усечение может быть произведено в любой нужной точке. Практический способ реализовать масштабируемый кодер состоит в том, чтобы только перестроить битовые слои, без того, чтобы фактически делать сжатие. Это означает, что масштабируемый кодер сначала помещает все старшие значащие биты (младшей значащей части) в потоке, сопровождаемом соответственно менее существенными битами. Наконец, без потерь и масштабируемо-закодированные части присоединяются/связываются. Усечение сжатых масштабируемых данных, чтобы получить фиксированный коэффициент сжатия, может быть выполнено во время присоединения, или на более позднем этапе в системе.
Чтобы оценить производительность предложенного метода, были выполнены эксперименты по сжатие с помощью JPEG-LS, используя реализацию обеспеченную University of British of Columbia.
Была оценена производительность сжатия без потерь и с потерями алгоритма JPEG-LS и нового метода использующего JPEG-LS в качестве метода сжатия без потерь для старших значащих битов и оставления младших значащих битов несжатыми. Изображения используемые в экспериментах: 24 изображения Kodak PhotoCD PCD0992, размером 768×512 пикселей, каждый.
Ниже, в таблице, показано, как в зависимости от выбора точки «разделения», меняется эффективность сжатия.

Когда никакие LSB не отколоты, схема становится обычным методом сжатия без потерь, без масштабируемости.
На графике, расположенном ниже, можно увидеть графическую зависимость, между JPEG-LS и новым методом (scalable JPEG-LS).

Для JPEG-LS, точки соответствуют сжатию, использующего различные максимально позволенные абсолютные погрешности между исходными и восстановленными изображениями (в пределах от 1 — 7). Для масштабируемого метода точки в кривой были получены, усекая все LSB, и таким образом происходило хранение только части MSB без потерь (скорости передачи для этих точек перечислены в таблице выше).
Декодер заменяет недостающими LSB их математическим ожиданием, принимая случайную универсальную форму распределение LSB. К примеру, когда разделение равно двум, математическое ожидание для LSB = (0 + 1 + 2 + 3)/4 = 1.5, которое реализует для LSB части, для одной половины значение пикселей равным 1, а для другой — 2.
В дополнение к PSNR также было оценено визуальное качество восстановленных изображений. Визуальный контроль показывает, что артефакты сжатия уже видимы для некоторых изображения (изображения с “синими небесами”), когда 2 плоскости LSB удалены или для JPEG-LS, когда максимально разрешенная абсолютная погрешность 2. В этом случае, хотя PSNR оценивает эти два случая — приблизительно одинаково, артефакты для предложенного метода являются более приемлемыми потому что они более подобны шуму чем артефакты «чередования», произведенные JPEG-LS.
Однако, для того, чтобы удалить 3 плоскости LSB, по сравнению с максимальной позволенной абсолютной погрешностью 4 для JPEG-LS, где снова значения PSNR — приблизительно одинаково, предложенный метод производит артефакты «очерчивания», которые являются визуально более негативно сказываются на изображении, чем артефакты чередования JPEG-LS.
В проведенных экспериментах точка «разбиения» MSB/LSB, была установлена вручную, и была одна и та же для каждого изображения, и была постоянна, при анализе всего изображения. Однако, есть несколько преимуществ, связанный с автоматическим и адаптивным определением точки разделения.
Вообще «более плоские» части изображения, такие как синие небеса, намного более чувствительны к сжатию, поэтому артефакты появляются на них чаще, чем на других частях изображения. Эти же самые части изображения также несут большие потери эффективности сжатия, когда их LSB отколоты. Поэтому, чуть поздже, будет предложен метод для того, чтобы автоматически выбирать число плоскостей LSB, для каждой строки, каждого изображение. Этот метод основан на низко сложном методе сжатия изображений без потерь, о котором сейчас будет рассказано.

Метод сжатия без потерь, «очень низкой сложности»

Данный метод сжатия без потерь следует за известной установкой DPCM+VLC. Однако, чтобы получить очень низкую сложность, для части DPCM и части VLC, выберем очень низкое решение для сложности. Для прогноза, используется прогнозирующее устройство «Paeth». Это прогнозирующее устройство использует три левых, верхний левый и верхний пикселя, с помощью которых предсказывает значение текущего пикселя, путем выбора одного из значений этих пикселей.
Предсказанный сигнал ошибки после «Paeth», преобразуется в знаковую величину и без потерь кодируется, используя модифицированный «Rice» код, адаптивный энтропийный код с очень низкой сложностью. Этот энтройпийный код, сначала удаляет m LSB величин из выборки. Оставшаяся MSB часть кодируется в унарный код, т.е. кодовая комбинация для MSB состоит из k нулевых битов, сопровождаемых единичным битом (например, кодовая комбинация для k = 3, равняется 0001). Затем m LSB битов добавляются к кодовой комбинации MSB, как знаковые биты, для ненулевой величины. К примеру, ошибочное значение прогноза равняется 15, при m=3, преобразовано в кодовую комбинацию 011110, состоя из кода 01, k = 15 div 8 = 1, m LSB битов 111, и знакового бита 0. Параметр m выбирается оптимально ( т.е. так, что он приводит к самому низкому числу битов требуемых для того, чтобы без потерь был закодирован сигнал ошибки прогноза), как m = floor(log2(mean(abs(e)))), где e — сигнал ошибки прогноза. В нашей реализации m, выбран однажды на строку изображения, но оно могло обновляться более часто.
В таблице ниже, показана эффективность сжатия «нового» алгоритма, по сравнения с JPEG-LS, PNG и JPEG2000:

Несмотря на очень низкую сложность метода, наш метод требует только на 11 % больше битов чем JPEG-LS, чтобы сжать набор тестов с 24 изображениями. Различие с PNG, который также использует очень низкие по сложности фильтры прогноза, но сложный энтропийный метод кодирования, является довольно маленьким. Для JPEG2000 была использована реализация University of New South Wales. Согласно этому эксперименту, JPEG2000 почти столь же эффективен как и JPEG-LS. Поэтому, в этом случае неэффективность, упомянутая в начале статьи, кажется не происходит.

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

Как было заявлено ранее в статье, нам хотелось бы автоматически определять точку разделения MSB/LSB для масштабируемого метода сжатия почти без потерь. Данное действие выполняется в «блоке контроля». Анализ, предложенный здесь, основан на очень низком по своей сложности методе сжатия изображения без потерь, который был описан в предыдущем разделе.
Чтобы определить точку разделения, сначала «Paeth», выполняет прогноз и получает ошибку прогноза e, как описано в разделе выше. Далее, параметр m определяется снова, как m = floor(log2(mean(abs(e)))). Параметр m, теперь непосредственно обеспечивает точку разделения: m LSB отправлены масштабируемому кодеру, а оставшиеся MSB отправлены кодеру без потерь. Этот выбор точки разделения основан на наблюдении, что энтропийный код, который применен в предложенном методе сжатия без потерь изображений, описанный в разделе выше, не применил бы сжатие на этих битах (т.к. они просто скопированы непосредственно в кодовую комбинацию). Следовательно эти LSB, как предполагается, более или менее случайны и нет таким образом никакой потери эффективности сжатия, когда они не используются для прогноза в кодировании без потерь
MSB.

Заключение

Была представлена методика, расширяющая сжатие без потерь с помощью функции масштабируемого сжатия почти без потерь, при сохранении высокой эффективности сжатия и низкой сложности. Метод работает разделяя сигнал на MSB и LSB. MSB сжимается без потерь, в то время как LSB сжимается масштабируемым методом. Также была представлена методика автоматического и адаптивного, разделения MSB/LSB, так, что масштабируемая строка битов получалась, без влияния на эффективность сжатия и не приводя артефакты сжатия для метода сжатия почти без потерь. Несмотря на простоту, этот метод очень эффективен.

Список литературы и ссылки

1. Об алгоритмах LOCO-I/JPEG-LS: www.hpl.hp.com/loco/
2. Исходные коды JPEG-LS и LOCO-I: www.compression-links.info/JPEGLS

P.S. Статья написана на основе доклада, представленного на конференции компании Philips.