@SCINER21 сен 2011 в 22:12

Сжатие изображений с использованием вейвлет

11 мин

28K

Алгоритмы *

+111

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

@ayurganov 21 сен 2011 в 22:30

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

@Colwin 22 сен 2011 в 02:02

Средний размер страницы в интернете — порядка 30 Кб.
Размеры картинок в статье — по 50 Кб (мелкие не беру в рассчет).
Итого просмотр картинок обошелся вам в просмотр трех страниц — ну, очень много, чесслово :-)

P.S. А отключать картинки не судьба?

@ayurganov 22 сен 2011 в 03:18

В статье про сжатие изображений, фраза про то, что стоит прятать сжатые картинки под кат, вам кажется нормальной?

@Ginz 22 сен 2011 в 04:00

Грустно когда не могут уловить юмор =\

Тема и результат интересный, с точки зрения практики уже не актуальный.

@Harkonnen 22 сен 2011 в 08:46

медленный небезлимитный интернет = у вас нет интернета

@alexey_lahtadir 22 сен 2011 в 05:29

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

НЛО прилетело и опубликовало эту надпись здесь

@bolk 22 сен 2011 в 06:11

Средний размер страницы в интернете — порядка 30 Кб.

Вы меня сейчас сильно удивили. Это исследование или ваше ощущение, потому что мои ощущения, что эта цифра больше на порядок.

@leshaogonkov 22 сен 2011 в 06:28

Видимо имелся ввиду желаемый максимум.

Лет 5 назад читал статью art_lomov, в ней он оперировал такими же цифрами, если я сейчас не путаю.

@bolk 22 сен 2011 в 06:31

Думаю, лет 5 назад желаемый максимум был сильно ниже. С тех пор каналы расширились и безлимит подешевел.

@taliban 22 сен 2011 в 15:55

Не поверите =)
Размер текущей страницы 36 676 байт + 2 картинки в общей сумме 36 676 байт
Похоже человек проверил перед тем как сказать.

@taliban 22 сен 2011 в 15:56

Картинки в общей сумме 1 042 814 байт

@bolk 22 сен 2011 в 16:03

Я про средний.

@alienator 22 сен 2011 в 16:30

Я вот, кстати, производил замеры год назад.

Медианный размер страницы, по 200 000 сайтам в рунете: 27 679 символов.

@bolk 22 сен 2011 в 17:02

Я не понял что вы считали. Какие символы? Это был UTF-8? Однобайтовые кодировки? Вы считали объём текста или учитывали полный размер страницы?

@alienator 22 сен 2011 в 19:12

Полный объем страницы (со всей разметкой).

Считал в символах, как раз чтобы избежать вопросов с кодировкой. Соответственно, в CP1251 это составило 27,796 байт (с записью отсутствующих символов энтитями), в UTF-8 составило 31,241 байт (поскольку русскоязычные страницы).

@alienator 22 сен 2011 в 19:16

Уточню: страница — это размер тела HTTP-ответа. То есть весь HTML (или что там). Без заголовков, но и без запроса и подсчета зависимостей — скриптов, css, картинок.

@bolk 23 сен 2011 в 03:37

А, ну так надо полную страницу, а не просто весь текст. Ведь никто не грузит страницу без всех зависимостей, разве нет?

@alienator 23 сен 2011 в 07:07

Перечитайте комментарий, с которого вы сами начали эту ветку. Страница отдельно, картинки отдельно. Как бы-то ни было, размер не отличается «на порядок».

@bolk 23 сен 2011 в 07:11

Как бы-то ни было, размер не отличается «на порядок».

Это вряд ли.

webo.in/articles/habrahabr/43-average-web-page-growth/

«Размер средней веб-страницы увеличился более чем втрое с 2003 года. С 2003 по 2008 годы она увеличилась в размере с 93,7Кб до более 312Кб (см. рисунок 1)».

@alienator 23 сен 2011 в 13:14

* пожимает плечами *

Возьмите и сами посчитайте; это несложно.

@alienator 23 сен 2011 в 07:08

Если уж сильно хочется, можете добавить медианный размер стилей и ява-скрипта — около 8 Кб.

@NikoM 22 сен 2011 в 08:06

1) отключи картинки в браузере
2) используй загрузку изображений только из кэша
3) подгружай необходимые изображения по мере надобности
4)…
5) PROFIT!!!

НЛО прилетело и опубликовало эту надпись здесь

@Akson87 21 сен 2011 в 23:13

А где же одно из главных отличий сжатия на основе вейвлетов — возможность получать результат постепенно, увеличивая детализацию с приходом новых данных?

А еще где-то я слышал, что гугл этим делом балуется для своих сервисов вроде просмотра пдфов в гдоках, так что может не такое оно уже и непопулярное:)

@MercurieVV 22 сен 2011 в 00:47

А jpeg 2000 поддерживается браузерами?

@Akson87 22 сен 2011 в 00:52

Не знаю учитывая возраст стандарта не удивлюсь этому. Попробуйте а то у меня только мобильный девайс под рукой.

@bolk 22 сен 2011 в 06:12

Я слышал только о нативной поддержке (без плагинов) только WebKit.

@SiGMan 22 сен 2011 в 01:10

А для этого жать результаты преобразования нужно не GZip'ом. Например, как это сделано в EZW или SPIHT кодерах. Gzip тут совсем не в тему.

@Akson87 22 сен 2011 в 01:47

Не совсем понял при чем тут GZip. Тот же SPIHT как раз на вейвлетах и основан, а гзип — это универсальный алгоритм для всего и вся.

@SiGMan 22 сен 2011 в 01:51

В кодеке, исходники которого приведены в статье, все в результате жмется именно gzip'ом )

@Akson87 22 сен 2011 в 01:59

А… я просто Ваш коммент как прямой ответ на свой коммент прочитал и долго думал, где я упомянул гзип:)

@SCINER 22 сен 2011 в 05:30

Если сжимать чем-то другим, то пришлось бы в листинг добавить кучу кода. Я же хотел его оставить минимальным.

@vibornoff 22 сен 2011 в 07:32

Вам предложение — код перенести на GitHub, а в статье дать обзорное описание метода сжатия вейвлетами. Пелена кода не способствует быстрому пониманию среди новичков, а GitHub по-любому удобнее Хабра для работы с кодом.

@SCINER 22 сен 2011 в 07:36

Это уже будет совсем другая статья. Хорошо, я попробую ее написать в ближайшее время. Как вижу, тема многим интересна.

@CycaHuH 22 сен 2011 в 03:02

>А где же одно из главных отличий сжатия на основе вейвлетов — возможность получать результат
>постепенно, увеличивая детализацию с приходом новых данных?

А как progressive jpeg связан с вейвлетами?

@Akson87 22 сен 2011 в 03:14

А кто сказал, что он связан? Похожий результат не значит одинаковые алгоритмы. Подходы то различные кардинально. Вот Вам ссылочка на статью со сравнением: статья

@Kroligoff 22 сен 2011 в 01:04

Ответьте пожалуйста на вопрос, почему в тексте указаны размеры ~7.8, а на самом деле,

Первый 7,8 KБ (7 959 байт)
второй 55 KБ (55 361 байт)

@Zarikarus 22 сен 2011 в 01:32

Это наверно потому, что второй тоже в jpg, чтобы любой браузер понял и показал. Будь он в JPEG2000, было бы все как надо, но посмотреть мы не смогли бы.

@WiseLord 22 сен 2011 в 04:42

По-хорошему, хотя бы картинку в jpeg2k стоило бы в png потом пережать, чтобы и браузер без сомнений показал, и качество именно jpeg2k увидеть, не боясь, что обычный jpeg к ней добавит ещё чего-то от себя.

@SCINER 22 сен 2011 в 05:31

Я его сжал с качеством 98%, поэтому картинка вполне достоверная.

@SCINER 22 сен 2011 в 05:34

Совершенно верно.

@btd 22 сен 2011 в 04:22

Вы бы написали что такое вейвлет, немного про Добеши. Задача сжатия картинки вейвлетами Добеши различных степеней у меня была на третьем курсе.

@SCINER 22 сен 2011 в 05:33

Всю теорию можно почитать по ссылкам внизу статьи. Здесь только практика.

@guyfawkes 22 сен 2011 в 06:05

Скажу честно: в википедии теория крайне скупа и, глядя на ваш код, лично мне весьма сложно понять, что к чему и где можно найти «почему так».

@guyfawkes 22 сен 2011 в 05:47

А что такое «быстрый лифтинг дискретного биортогонального CDF 9/7 вейвлета»?

@mikhanoid 22 сен 2011 в 06:58

Это особая форма алгоритма подсчёта коэффицентов. Вообще, автору минус, ибо не понятно, к чему эти полукилометровые листинги без объяснения того, что же они делают. Там математика не такая уж и сложная.

@guyfawkes 22 сен 2011 в 07:04

Скажите, а есть более подробные статьи по этой теме? Например, код быстрого лифтинга изобилует всяческими a = -1.586134342f; Что это? Почему?

@mikhanoid 22 сен 2011 в 08:44

Это коэффиценты из значений функций вейвлет-базиса в определённых точках. А почитать, конечно, есть, даже в общем виде: en.wikipedia.org/wiki/Lifting_scheme

@SCINER 22 сен 2011 в 08:52

Как раз оно и есть.

@guyfawkes 22 сен 2011 в 08:58

Я чуть выше уже отмечал, что общие пояснения мало что объясняют. Меня интересует «подноготная», что за вейвлет-базис, что за функции базиса. Если вы даете ответы, скажите, вы действительно нашли их в материале по той ссылке, которую дали мне?

@mikhanoid 22 сен 2011 в 09:53

Ну, я же предполагал, что Вам про вэйвлет-преобразование известно, но не известно про схемы лифтинга. В этой статье на Википедии есть хорошая ссылка «Comprehencive introduction...», где многое объясняется. Но если Вам вообще про вейвлеты надо, то эта тематика так и называется: вейвлет-преобразование. Про него много в интернете. Топикстартеру, конечно, надо бы было хотя бы некие базовые вещи написать.

@guyfawkes 22 сен 2011 в 10:34

Понял, спасибо за наводку.

@SHVV 22 сен 2011 в 05:59

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

На сколько я знаю, его сейчас активно используют в различных ММО играх, где контент создают сами пользователи, например SecondLife. Благодаря возможности постепенно увеличивать детализацию по мере подгрузки, текстуры на объектах появляются почти сразу, и со временем становятся четче.

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

@ArtRoman 23 сен 2011 в 18:27

Браузеры (а пока это лишь Chrome и Opera) поддерживают WebP, тоже вроде неплохой вариант.
А в играх я ещё встречал JNG — jpeg в контейнере png, который позволяет сохранять прозрачность и др.

@seewald 22 сен 2011 в 06:03

приложите, пожалуйста, рядом с jpeg / jpeg 2000 результаты работы вашего алгоритма. Или результат полностью идентичен jpeg 2000?

@SCINER 22 сен 2011 в 06:12

Результаты очень схожи.

@x128 22 сен 2011 в 09:24

Хотелось бы увидеть результат, одно дело на словах, совсем другое дело увидеть глазами. Еще не совсем понятно (может я придираюсь), почему изображения к статье сжаты по схеме 5/3 если речь идет о 9/7? Возможно вы использовали кодер основанный на референсном JasPer, он по умолчанию использует для сжатия с потерями и без целочисленное преобразование 5/3, для 9/7 нужно использовать параметр mode=real, правда не все программы использующие эту реализацию кодера позволяют применить дополнительные параметры. Реализация кодера от Kakadu Software, на мой взгляд, лучшая как по скорости, так и по качеству сжатия, этот кодер используется в ACDSee, которая по качеству сжатия заняла первое место в сравнении кодеков JPEG2000 от MSU Graphics & Media Lab.

@SCINER 22 сен 2011 в 09:31

Я использовал лишь тот листинг на Си, на который есть ссылка в статье.

@SCINER 22 сен 2011 в 09:36

CDF 5/3 в JPEG2000 используется для безпотерьного сжатия. Для сжатия с потерями в нем используется как раз 9/7

@x128 22 сен 2011 в 10:26

Стандарт не обязывает использовать исключительно 9/7 для сжатия с потерями. Многие кодеры используют 5/3 для сжатия без потерь и с потерями. В частности JasPer по умолчанию использует 5/3 в обоих случаях (о чем я и написал), если не указать явно какое преобразование использовать.

Разница не очень большая, но она есть.

@SCINER 22 сен 2011 в 10:52

Согласен, просто я имел в виду стандарт JPEG 2000.
The JPEG 2000 compression standard uses the biorthogonal CDF 5/3 wavelet (also called the LeGall 5/3 wavelet) for lossless compression and a CDF 9/7 wavelet for lossy compression.
en.wikipedia.org/wiki/Cohen-Daubechies-Feauveau_wavelet

@Pavelius 22 сен 2011 в 11:04

Тоже интересно посмотреть.
А размеры тоже очень похожи?

@SCINER 22 сен 2011 в 11:15

Да. Естественно заменив GZip на более серьезный компрессор.

Вот сравнение, правда при сжатии в JPEG 2000 не получилось сжать до точно такого-же размера. Разница составила 165 байт.

(JPEG 2000, 9 409 байт)

(представленный здесь алгоритм, 9 244 байта)

@SCINER 22 сен 2011 в 11:25

В данном случае в качестве пост-компрессора я использовал алгоритм Eliminator, затем LZMA.

@spaceblock 22 сен 2011 в 08:02

Так я не понял, какой вывод — jpg на сайте можно пережимать или нет?)

@SCINER 22 сен 2011 в 08:18

Можно, но браузеры не понимают этого формата.

@SCINER 22 сен 2011 в 08:19

html-страничка с файлом

@xdr 22 сен 2011 в 09:08

Раз уже такой случай, разрешите и мне тоже пропиариться:
EPSILON — (Yet Another Wavelet Coder) — epsilon-project.sourceforge.net/

1. Библиотека используется в GIS-движке GDAL:
— www.gaia-gis.it/raster_benchmark/color-ortho-epsilon.html
— www.gdal.org/frmt_epsilon.html

2. Поддерживает ~30 вейвлетных фильтров (в том числе фильтр Добеши 9/7 упомянутый в статье)

3. Работает с изображениями любой формы и любого размера (>>4Gb)

4. Три механизма распараллеливания:
— можно собрать многопоточную версию (POSIX threads)
— можно собрать MPI-версию (протестировано на реальном кластере в МГУ)
— можно собрать кластерную версию (простой TCP-демон)

Также можно собрать обычную однопоточную последовательную версию без наворотов

5. Лицензия LGPL3

6. Есть тесты на Perl для каждого из билдов.

7. Можно заранее указывать желаемую степень сжатия.

8. Есть официальные DEBы для Debain & Ubuntu, есть RPM-ы для шапочек

@SCINER 22 сен 2011 в 09:25

Жму руку! У вас есть все. Интересно будет поковырять сырцы.

@xdr 22 сен 2011 в 09:36

Спасибо! Будут вопросы — предложения, обращайтесь)

@dmbreaker 22 сен 2011 в 20:41

Если кому интересно, то есть LGPL библиотека для вейвлетного сжатия (не в JPEG2000):
www.libpgf.org
Свой код можно не открывать, если указали в About, что используете PGF.

@xdr 23 сен 2011 в 17:12

Спасибо за инфо, надо посмотреть

@impass 22 сен 2011 в 10:49

есть такая книжка «Вейвлеты в компьютерной графике»

скачать можно, например, здесь

@dmbreaker 22 сен 2011 в 20:44

А можно поинтересоваться — каков смысл данной статьи? «Вейвлеты для самых маленьких»?
Про теорию не рассказано, нормального сравнения с другими алгоритмами нет.
ИМХО данную статью можно на code.google.com постить, а не на хабр.

@tipok 22 сен 2011 в 21:10

Я чота не понял, а чем собс-но гоголькод не угодил-то?

@dmbreaker 22 сен 2011 в 22:19

Да гуглькод не причем. Просто личные проектики нужно хостить на нем и ему подобных.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий