Мультимедиа-сжатие – это использование специальных алгоритмов для упаковки «сырых» графических и звуковых данных. Это достаточно популярная среди пользователей возможность современных архиваторов. Хотя сам я не разделяю энтузиазма по поводу её важности (много ли народа имеет дело с *несжатыми* графикой и звуком?), тем не менее я предпринял изучение этой области и публикую здесь результаты в надежде, что кому-нибудь ещё это может оказаться полезным.

Во-первых, наиболее известные архиваторы, в которых оно реализовано: RAR, SBC, UHARC, CCM, WinRK. Сравнить степень сжатия ими мультимедийных данных можно на страницах тестов, приведённых ниже.

Во-вторых, как его реализовать в своей программе: для начала нужен детектор мультимедийных данных. В самом простом виде это можно делать по расширениям, несколько сложнее – по заголовкам файлов, универсальный способ – анализом самих данных. Универсальный детектор MMDET входит в мой пакет http://www.haskell.org/bz/mm.zip ; трудности корректного обнаружения мультимедии описаны на странице http://www.encode.ru/forums/index.php?a ... &topic=391

Далее, есть простой путь – после определения типа мультимедии просто вычесть последовательные элементы данных в каждом канале (я называю это дискретным дифференцированием) и передать обычному алгоритму сжатия. Как показывает опыт, наилучшие результаты при этом показывают алгоритмы группы BWT/ST (это один из секретов успехов SBC в сжатии мультимедии), на втором месте – PPMD 3-5 порядка, и на последнем – LZMA.

Более приличные результаты даёт, конечно, использование специализированных lossless кодеков, к рассмотрения которых мы и переходим.

ЗВУК
Ориентироваться в результатах специализированных алгоритмов сжатия звука удобно по страничкам:
http://squeezechart.freehost.ag/audio.html
http://uclc.info/lossless_audio_compression_test.htm
Из всех этих программ я прокомментирую только open-source, в порядке уменьшения максимальной степени сжатия:
MPEG-4 ALS: очень медленно работает. Лицензия позволяет использовать его только в MPEG4 продуктах.
APE (Monkey’s Audio): определённой лицензии нет, надо договариваться с автором. Асимметричен, т.е. достаточно медленно сжимает, но быстро распаковывает.
TAK: очень многообещающий кодек, исходники которого пока закрыты, но есть обещания их открыть. Если и когда это произойдёт – станет вероятно наилучшим выбором. Ассиметричен. Сжатие близко к APE, но упаковка/распаковка afair идёт быстрее.
WAVPACK: BSD лицензия, ассиметричен, поддерживает 24/32-битные форматы.
TTA 2.0: GPL лицензия, симметричен, поддерживает 24/32-битные форматы, но имеет с ними небольшие проблемы. По сжатию близок к WAVPACK, по сравнению с ним куда быстрее пакует и медленнее распаковывает. Я использовал именно его в http://www.haskell.org/bz/mm.zip, поскольку он имеет наименьший размер исходников (в несколько раз меньше WAVPACK) и в нём оказалось проще всего разобраться и задействовать в своей программе.
TTA 3.3 от TTA 2.0 отличается двумя вещами: исправлена проблема с вылетом на 24-битном формате и убраны более мощные уровни сжатия, оставлен только один, самый быстрый.
FLAC: BSD лицензия, ассиметричен

ГРАФИКА
Ориентироваться в результатах специализированных алгоритмов сжатия графики удобно по страничкам:
http://squeezechart.freehost.ag/bitmap.html
http://uclc.info/kodak_grey-scale_image ... n_test.htm
Страница http://uclc.info/win32_compressor_builds.htm содержит ссылки на исходники некоторых из упомянутых там программ.

Из этих программ я прокомментирую опять же только open-source, в порядке уменьшения максимальной степени сжатия, и приведу для ориентации время сжатия ими 2 мб файла на 1.2 ГГц процессоре:
MRP: время упаковки – где-то в районе часа, распаковки – несколько секунд, 890 кб
BMFg: время упаковки/распаковки – 5.7 секунды, 907 кб. Правда, исходников на самом деле нет 
MRP: 30/1.3секунд, 950 кб. Использовались опции “-I 1 -h -K 10 -M 2 -V 1”
SLP: 3 секунды, 952 кб. Исходники:
http://web.archive.org/web/200412121212 ... s/slpenc.c
http://web.archive.org/web/200412121210 ... s/slpdec.c
CALIC: 1.9 секунды, 958 кб. Вероятно, разнице в скорости с SLP мы обязаны только более удачному использованию арифметического кодирования. Комментарии в исходники упоминают LOCO-LS, так что возможно это некая производная JPEG-LS
COBALP: 4 секунды, 964 кб.
SLP-RICE: 0.55 секунды, 976 кб. Более быстрая версия SLP, использующая тот же предиктор, но Rice coding вместо арифметики. Вероятно, «арифметическую» версию можно значительно ускорить, использовав более быстрый арифметический кодер. Исходники:
http://web.archive.org/web/200412301602 ... s/enc_0r.c
http://web.archive.org/web/200412301602 ... s/dec_0r.c
JPEG-LS: 0.27 секунд, 990 кб. Принято считать, что JPEG-LS работает довольно медленно, но сжимает лучше JPEG-2000, видимо в данном случае расхождение вызвано тем, что я тестировал код, не использующий арифметического дожатия. Лицензия допускает свободное использование в некоммерческих целях. Исходники:
http://kt.ijs.si/aleks/jpeg-ls/jpeg_ls_v1.1.tar.gz
http://kt.ijs.si/aleks/jpeg-ls/jpeg_ls_v2.2.tar.gz
JPEG-2000 lossless (JASPER): 1.8 секунды, 991 кб. BSD лицензия
FreeArc 0.37 (MM+GRZipII): 3.6 секунд, 1153 кб. Для сравнения – результаты обычного архиватора.

calic должен отличаться от loco предиктором (GAP вместо MED), контекстами и некоторыми трюками. Исторически это два разных алгоритма, хотя, насколько помню, были взаимные заимствования.
Для calic авторы также делали вариант с interframe кодированием, т.е., фактически, адаптацию под видео (статическое).

спасибо за информацию

что меня ещё очень интересует - как можно беспотерьно преобразовать RGB изобраджение, чтобы добиться высокой степени сжатия? я знаю две программы, которые этого добиваются - jasper jpeg-2000 и http://squeezechart.freehost.ag/WaveletCoBALP.wav

на примере последней - один и тот же файл по умолчанию кодируется в 3 мб, с включенной опцией "colorspace conversion" - в 2.6 мб. при этом распакованные данные бит в бит аутентичны

Какие из вышеперечисленных программ для сжатия графики могут сжимать 24-битные цветные изображения? В частности MRP, afaik умеет только 8-битные в оттенках серого сжимать.
Можно для примера привести степень сжатия компрессора UDA - у него есть модели для 24-битных .bmp .tiff и сжимает он относительно PAQ8l быстро и почти так же эффективно.

а исходники UDA есть?

По умолчанию практически всегда кодируют G, R-G, B-G, т.е. зеленка выполняет роль люмы (по понятным причинам, см., например, байеровский паттерн).

Есть также более точное преобразование, но оно требует 9-битного представления результата и возиться с ним неудобно:
Y = |_ (R+2G+B)/4 _|
U = B - G
V = R - G

G = Y - |_ (U+V)/4 _|
R = V + G
B = U + G


Можно также несколько точнее приблизить один из разностных каналов к U или V за счет весов. Тоже может стрелять.

http://wex.cn/dwing/mycomp.htm
http://wex.cn/dwing/download/uda0301s.7z

спасибо за ответы. важность праивльного перекодирования RGB можно продемонстировать на cobalp. в grey редиме он сжимает на 20% лучше, чем diff+grzip. в rgb редиме - всего на 5% лучше в режиме по умолчанию, и на те же 20% лучше, если включить "colorspace conversion" при кодировании. так что без правильного кодирования цветов смысл в специальном кодеке для графики практически теряется

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

посмотрел. он сжимает каждый канал независимо

а как насчет проверить это в ж2к - насколько я помню выигрыш заметен.
тем более, что предикторы (например MED) же вычисляются по каждому каналу отдельно. одно другому никак не мешает

[quote="Булат"]
посмотрел. он сжимает каждый канал независимо[/quote]
А всё-таки, какой результат он показывает на в Вашем вышеприведённом тесте?

2.9 mb, 138 sec. т.е. в 10 раз медленней и на 300 кб хуже, чем cobalp с "convert colorspace"

как именно проверить? я даже не понял, что такое ж2к. и мои поптыки найти colorspace conversion в jasper оказались безуспешны

насчёт "не мешает" - я тоже не понял. предсказания делаются по R, а кодируется R-G, к примеру?

ж2к это я так jpeg2000 обозвал. в нем есть возвожность кодировать как rgb, так и yuv. Для случая песпотерьного сжатия преобразование rgb <-> yuv соответственно тоже беспотерьное. Причем оно очевидно совпадает с тем, что привел Максим во втором варианте.
Ищи, у меня сорцов под рукой нет, может к вечеру освобожусь и покажу где это происходит.

Насчет не мешает - предсказание делается по каналу, которые кодируется - если кодируем rgb, то и предсказываем отдельно r, g, b, а если кодируем yuv, то соответственно y, u, v. Приближенное отображение rgb->yuv ничем особенным не отличается. Внутри каждого канала между пикселами остаются почти те же зависимости.

jpc_mct.c/h:
jpc_rct(), jpc_irct() - беспотерьное преобразование
jpc_ict(), jpc_iict() - потерьное преобразование