Открыть список
Как стать автором
Обновить

Комментарии 52

Долго думал, что не так с кодом. И только минуты через две осознан, что написано это на тёплом и ламповом VB6. Да, забавные были времена, когда этот самый VB заставляли делать такие выкрутасы, к которым он, мягко говоря, не был приспособлен.
НЛО прилетело и опубликовало эту надпись здесь
Результаты моего теста пока такие.

i53.tinypic.com/2dr7u51.png
184 577 — PNG
340 509 — SSP

i53.tinypic.com/2dr7u51.png
375 431 — PNG
301 011 — SSP
196 280 — SSP PHOTO
52 186 — JPG

Надо конечно ещё тестировать, но пока я вижу, что SSP не так эффективен на примерах, для которых как раз и рекомендуется PNG. А на фотографиях SSP, круче PNG, но тут уже в бой должен вступать JPG, которому SSP проигрывает с треском.
Прошу прощения. Вторая ссылка: i51.tinypic.com/2quptok.jpg

P.S. Блин. И писать не могу чаще, чем раз в 5 минут. А спать уже охота. =)
Теперь можете писать чаще и спать спокойно )
Лучше всё же не чаще, а внимательнее. =)
Большое спасибо! Тема по-моему очень интересная. Как проснусь, сразу сюда.
Спасибо за первую картинку. Поизучал. :)
За безвизовый режим особое спасибо :)
Да я сам офигел, какая полезная картинка для примера попалась. =)
Там странным образом Марокко не обозначено безвизовым. Видать, весьма устаремшая картинка…
А даты на неё нету :(
Простите, а то что на картинке i53.tinypic.com/2dr7u51.png размер изображения вырос, это не опечатка?
Если не опечатка, то может быть имеет смысл в этом случае сохранять исходное изображение?

К примеру, добавить байт в заголовок формата SSP, определяющий была ли картинка пожата. В будущем этот байт может пригодиться для расширений алгоритма.
Нет. Не опечатка. Как раз так наоборот я получил ожидаемый эффект. Что мудрить то с заголовком формата SSP, если пока самое простое и эффективно решение, которое я вижу — это не испльзовать его вообще. ;)
Тут зависит от того как сравнивать. Если взять не 1, а десяток разнородных файлов, то SSP по идее должен существенно выиграть в сжатии.
Осмелюсь оспорить Ваше возражение. Есть только две причины не мудрить с заголовком. Первая — это лицензия на формат PNG — если лицензия не позволяет инкапсулировать этот формат, то, разумеется, нет смысла расширять формат SSP. Вторая причина несерьёзная — добавление одного байта к заголовку увеличивает размер файла.

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

Наконец, если Вы решите доработать или модифицировать алгоритм, то в «лишнем» байте можно хранить версию этого алгоритма, чтобы программа распаковки знала как обрабатывать изображение.

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

Слава богу, проблем у PNG с лицензией не будет, как это было раньше с GIF. Один бит — это тоже не проблема.

Действительно не факт, что забыть про SSP — это самое эффективное решиен, но не забывайте про то, что PNG — это формат, который уже неплохо отточен, достаточно универсален и очень сильно распространён, т.е. везде поддерживается. SSP — это сейчас чисто 24 битный формат, а PNG поддерживает 16, 24 и 48 бит.

Помнится в прошлом веке я думал «Какого фига HTML файлы передаются в несжатом текстовом формате?!», прошло некоторое время и это исправили. =) Потом я сам придумал свой графический формат с простым групповым сжатием, более эффективным, чем распространённый тогда PCX. =)

Т.ч. я ни в коем случае не против всех этих экпериментов с усовершенствованием. =)
Удачи в этом проекте! Нечасто встречаются люди, способные создавать новые и интересные алгоритмы. Добавил Ваш пост в избранное.
Ещё забыл кое-что. Да выбирать разные алгоритмы сжатия для разных типов данный — это интересных ход. Но не совсем универсальный и значительно увеличивающий время компрессии. Но если времени предостаточно, а размер результата действительно очень важен, то почему бы и нет.

Вот, кстати, цитата из Вики: «Различные реализации алгоритма Deflate дают разную степень сжатия, поэтому были созданы программы для пережатия изображений с несколькими вариантами настроек в целях получения наилучшего сжатия — например, форк pngcrush OptiPNG и advpng из комплекта AdvanceCOMP (использует 7-Zip).»

Т.ч. для чистоты эксперимента нужно пользоваться этими пакетами, чтобы сравнивать SSP не просто с PNG, а с оптимально пожатым PNG.
PNG поддерживает далеко не только 16, 24, 48 битные изображения, а вообще всё что душа пожелает (прозрачность, палитру и т.д.)
Вот заголовок SSP файла, сейчас я вижу, что он сильно избыточен. Туда еще много каких флагов можно записать:
Private Type HeaderType 'Заголовок SPV файла
Signature As Long '= FILE_SIGNATURE - сигнатура файла
DCTQuality As Byte 'значение фильтра квантования
Width As Long
Height As Long
DivU As Byte
DivV As Byte
CRC As Long
CompressType As Integer 'Тип компрессии, 0 = без потерь, 1 с потерями
Reserved(0 To 253) As Byte 'Зарезервировано
End Type
Вы немного не так поняли. Изображение было успешно сжато и стало весить меньше. Расчет степени сжатия идет от BMP файла, а не от PNG. Оригинальный BMP файл весит больше 2,5Мб.
Просто в данном случае PNG сжал лучше, чем SSP.
Простите, действительно не понял. Shame on me.
Привет

в рамках доброжетальной конструктивной критики статьи (бизнес-подход не трогаем) хочу высказаться:

— очень мало про изображения. если не считать пункта 2, то пп. 1 и 3 почти полностью повторяют PNG, правильно?
— п. 4 уже включён в линейный фильтр, разве нет? ведь полностью повторяющиеся пикселы являются частным случаем линейного градиента.
— работает ли это как универсальный алгоритм сжатия данных после п.3? как его можно сравнить с другими?
— «лучшая в мире реализация» звучит анекдотично глупо. особенно без указания критериев оценки и альтернатив.
— 3 раза (экспериментально подобранное значение) — почему? это имеет связь с трёмя каналами RGB? Сколько байт уходит на каждом прогоне?
— вы пытались делать замеры энтропии на каждом этапе? в п.6 к данным добавляется битовая карта — сколько места занимает? растёт линейно с площадью картинки? насколько увеличивает энтропию? Есть ли возможность изменения числа прогонов (вплоть до нуля), если они не улучшают сжатие?

Вообще есть теоретические предпосылки почему данный алгоритм сжатия без потерь работает лучше чем PNG? На каких данных?
Или это тоже «экспериментально подобранный вывод»? =)
Почему алгоритм поставляется в виде EXE-файла? Какой вообще смысл в этом?

В качестве образца статьи об алгоритме сжатия изображений я бы привёл WebP от Гугла.
Если будете писать о своём конкуренте JPEG'у, пожалуйста, просто дорисуйте свои линии к тем графикам сравнения. Будет намного нагляднее.

Спасибо за статью и что поделились изобретением!
Конкурент JPEGу можно ещё сравнить с JPEG XR.
Пункты 5,6 и 7 работают как универсальный алгоритм сжатия.

По поводу 6-го пункта (экспериментально подобранного количества проходов). Это число я подобрал по результатам теста на группе файлов
из 15 различных по характеру изображений.
Количество проходов не связано с количеством каналов RGB. Да, количество прогонов можно варьировать вплоть до 0.
На каждом прогоне если к примеру взять тестовое изображение, замерить выходной поток после 5-го этапа: 567 613 байт,
поток после каждого прогона 6 этапа уменьшается до:
  1. 454 497
  2. 354 575
  3. 302 011
Если добавить к примеру еще 2 прогона, то выигрыш теряется и будут такие результаты:
  1. 309 825
  2. 305 539
Если 6-й этап совсем исключить из цепочки, то тестовый файл сжался бы на 2кб хуже и весил бы 157 317 байт.
Битовая карта растет линейно с размерами изображения.
вы сравниваете jpg, а автор ведет сравнение с png
>беспотерьного

новояз такой новояз.
Алгоритм сжатия изображений:
1) сохраняем изображение в jpeg, png, gif (можно и больше форматов)
2) проверяем размер файлов
3) оставляем файл с меньшим размером.
Затратно. А вообще да — под каждую задачу свой инструмент.
В этом случае всегда победителем будет jpeg
смотрим на гиф и плюёмся)
Ну если это не фотка, то на jpg тоже плюёмся. ;) В общем не по размеру конечного файла на самом то деле нужно выбирать формат.
такой вопрос, а если в конце сжимать не с помощью lzma, а как в PNG — Deflate, на сколько будет разница? А что если вместо deflate в png применить lzma?
Попробовал сжать при помощи zlib.dll размер файла получился 175 457 байт. В режиме lossy — 139 059.
В принципе можете сами попробовать сжать посжимать различными архиваторами. Вот сырой файл без 7-го этапа.
Результаты сравнения BWT реализации Дмитрия Малышева с другими реализациями можно посмотреть на специальной странице. Также можно почитать описание самой реализации.
Несколько вопросов-ответов-советов.

1. Paeth используется так же как и в PNG? Если да (побайтно) — то толку от него чуть.
2. Насколько я понял, Alpha не поддерживается. Плохо.
3. Зачем использовать LZMA после BWT? Понятно, что сжатие скорее всего будет, но с точки зрения и сжатия и распаковки черезчур затратно.
4. Если уж делать сжатие с потерями в YcbCr, то странно не учитывать разницу восприятия цветовых компонент.
5. Делать сравнение сжатия на самовыбранном изображении — то же что и просто назваться «лучшим сжатием». Для борьбы с «самопровозглашением» есть стандартные наборы тестовых изображений.

Вообще сжатие изображений это задача серьёзная, а в данной реализации это больше похоже на «а если взять PCX и сжать его ZIP будет ещё меньше».
И ещё, это конечно личное впечатление, но от использования VB для таких задач меня слегка покоробило.

Да, и последнее — не стоит воспринимать всё это как наезд, скорее это знак, что есть к чему стремиться.
1. да, побайтно. Естественно с разделением по цветовым каналам. Сразу скажу, что этот фильтр чаще всего дает очень большой выигрыш;
2. Альфа в текущем формате предусмотрена, но не реализована. Имхо это можно реализовать, если формат кто нибудь захочет использовать по назначению;
3. Тут скорее всего вы с чем-то путаете BWT, он лишь переставляет байты во входном потоке, но не сжимает его;
4. Вы про квантование цветовых Cr и Cb компонент?
5. Эти файлы я как раз таки взял из набора тестовых изображений, вот часть из них.

Я не воспринимаю это как наезд, просто лично мне тема интересна, рад, что есть единомышленники. Я не претендую на первое место во всех конкурсах и не говорю, что PNG фигня. 5 лет назад я писал на VB, в принципе много чего инетересного на нем понаделал в том числе и HTML рендер и движок БД и игрушки, убедиться в этом можно почитав мой профиль на форуме.
1. Разделение по каналам — гуд. А выключение предусмотрено? Если нет, то не надо делать «по строкам», как в PNG, лучше ух сразу делать для регионов (для начала — прямоугольных).
2. Тут вопрос не столько в практическом применении, сколько в универсальности алгоритма.
3. Часть LZMA это словарное (LZ) сжатие, я о том, что смыст в применении его после BWT как-то неочевиден.
4. Именно.
5. Для тестирование как-то не принято брать один файл из набора. Дабы ни у кого не возникало сомнений, что выбран самый удачный для конкретного алгоритма.

Насчёт VB — это не более чем моё личное вкусо-цвето-ощущение.
Главное, что «тема интересна». )
1. Выключение предусмотрено. Я делаю применяю фильтр для всех строк, т.е. сразу на все изображения;
2. Тут конечно надо тестить, но скорее всего достаточно будет внести коррективы в первые 2 этапа алгоритма;
3. Так ведь после BWT как раз образуются цепочки одинаковых символов;
4. В этом случае появится елезаметное размытие цвета толщиной в 1 пиксель вокруг выдающихся из общего фона одиночных пикселей, а это уже имхо серьезная потеря качества. 2х2 квантование можно при желании добавить в спецификацию. Собственно это уже есть в тестовой программе, только выключено. Думаю надо перекомпилировать тестовую программу добавив доступ к скрытым опциям;
5. Я тогда взял случайным образом штук 10-15 файлов; Вообще конечно стоит скачать все 300 с лишним картинок и прогнать тест для алгоритма по ним всем.
1. Регионы — это идеал )
2. Могу посоветовать подумать над разделением/дифференциальным кодированием каналов.
3. «Цепочки одинаковых символов» != «повторяющиеся фразы». Кстати, шаг 6 с битовой картой выглядит весьма растратным.
4. На практике — бОльшая часть изображений уже с квантованием. А это уже можно использовать и в lossless режиме.
5. Можно взять «Kodak Lossless True Color Image Suite», кстати регионы для фильтров дают очень неплохой результат на «самолёте» и «африканке».
1. Тут кстати вопрос в быстром алгоритме вычисления регионов;
2. Если каналы разделить и расположить друг за другом, то сжатие будет хуже. Проверял уже;
3. вот про это я не совсем понимаю вашу мысль. 6 шаг хоть и выглядит растратным — но таковым не является ни по времени, ни по результатам влияния на выходной поток;
4. в lossless режиме вообще нельзя менять палитру на YCrCb. Один в один уже не восстановится;
5. Ок, прогоню на этом наборе.
1. Это зависит от реализации. Смысл в том, что сейчас можно сделать один тупой регион на всю картинку, а позже можно сделать более умную реализацию не меняя алгоритм распаковки.
2. Поканальная дельта
3. Ну, если битовая карта не растратна…
4. Поток коррекции
2. Это как?
4. Поток коррекции это конечно интересно. Обязательно попробую.
Простейший вариант — один базовый компонент ® и разница между ним м двумя другими (R-G, R-B).
Фильтр применяется либо только к базовому компоненту, либо до дельты.
Alpha обычно хранится как-есть.
Делать такое кодирование неопциональным смысла нет, т.к. выигрыш будет не на всех изображениях.
Можно попробовать ещё scale-delta. Он даёт более стабильный выигрыш.
Кроме того, есть попиксельные варианты Paeth, учитывающие многоканальность цвета.
Возникли вопросы:
1. Я так и не понял, после сжатия мы имеем свой уникальный формат — не поддерживаемый известными графическими редакторами? — если да то о внедрении в практику алгоритма можно забыть. Я имею ввиду массовое внедрение.
2. Допускает ли ваш алгоритм поточный аналог — для использования при передачи по сети? То есть изображение посылается порциями пользователю и как бы уточняется по мере загрузки. Формат PNG это умеет делать более чем хорошо, этим так же объясняется его популярность в web графике. Возможно именно отсутствие «поточности» и позволяет вам обойти PNG.
3. Существуют базовые изображения (тесты) для тестирования алгоритмов сжатия. Например, сжать картинку из белого равномерно шума просто невозможно по физическим причинам — энтропия максимальна. Существуют так же «убийцы» алгоритмов сжатия. Вот ссылка:
Перечень баз данных
По адресу есть ссылка, на базу которой я раньше пользовался и она работала:
«UCID is intended as a benchmark dataset for image retrieval — all images are preserved in their uncompressed form hence making the dataset also useful for evaluating image compression, colour quantisation and other algorithms»
Однако сейчас эта ссылка не работает, возможно вам удастся найти из списка по первой ссылке интересные для вас базы данных.
1. Да после сжатия получается собственный формат. Массово внедрять я и не предлагаю =)
2. PNG вроде бывает максимум с чресстрочным кодированием. Но при таком виде кодирования вырастает и размер результирующего файла. У моего формата такой реализации нет, поэтому здесь и сравнить не получится;
3. Только что провел тесты. Сгенерировал белый шум. Естественно оба алгоритма не смогли его сжать. Но удалось добиться интересного результата при включенной галочке «Photo» изображение сжалось на 5%. Причем даже при сильном увеличении на 3200% на глаз различий найти не удалось. Не спорю, различия есть. Но на глаз их не видно, тем более нет никаких артефактов;
Спасибо за ответ. Думаю дальнейшие исследования, если есть желание, стоит проводить в направлении «поточности» алгоритма, чтобы можно было его использовать в web. и тогда написание плагина для браузера и небольшой сайт с программой позволит вашему алгоритму увидеть свет.
По поводу белого шума — результаты в студию. Выложите пожалуйста картинки которые у вас получились, например в комментариях или как обновление основной статьи.
Вот та сгенерированная картинка с белым шумом:
image
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.