Хороший алгоритм сжатия для изображения с низкой энтропией

Question

В настоящее время я пытаюсь сжать очень простое изображение. Изображение использует 2 набора цветов, а также 1 символ на «пиксель». каждый набор цветов может быть 1 из 16 вариантов. Из-за этого я уже объединил оба цвета в 1 байт на пиксель, представляющий их оба. Я уже реализовал методы кодирования MTF и BWT, чтобы помочь в RLE. Я уверен, что могу получить еще больше компрессии, но я не уверен, какой алгоритм использовать. Я пробовал huffman, однако из-за того, что изображение имеет тенденцию быть маленьким уже, и RLE сжимает большую часть из-за отсутствия энтропии, хаффман в два раза увеличивает размер, добавляя свою таблицу декодирования в файл. Обратите внимание, что это также будет работать на более медленной системе, поэтому любые действительно тяжелые алгоритмы могут не работать.

Answer 1

Во-первых, похоже, что вы должны сжимать фоновое изображение и цветные изображения персонажей отдельно. Во-вторых, вы говорите, что «цвета не меняются слишком часто с пикселя на пиксель». Некоторые цвета «ближе» друг к другу, чем другие? I.e., когда цвет изменяется от цвета x, более вероятно, что он изменится на небольшое подмножество оставшихся цветов? Если это так, вы можете сопоставить цвета, чтобы они были более смежными с теми, с которыми они могут измениться, и с учетом различий перед кодированием. Затем пробеги одного цвета становятся прогонами нулей, а изменения в «следующем» цвете становятся единичными.

Как только у вас есть хорошее представление в виде серии байтов с большим количеством прогонов и перекошенной вероятностью появления значений байтов, например. много нулей и один, затем примените zlib или gzip, чтобы воспользоваться очевидной избыточностью и перекосом.