Comments 70
Благодарю за очередную интересную статью.

p.s. такую статью в один заход не осилить)
Ничего себе. Спасибо вам за такой большущий труд, очень познавательно!
Пожалуйста! Если читателям понравится подобный стиль изложения, то планируются еще статьи.
Я вот особо не углублялся раньше в эту тему, но ваши статьи написаны интересно и понятно. Теперь буду следить за новыми статьями.
Приятно слышать :) Кстати, жду в комментариях пожелания о тематиках статей (прислушаюсь, но не обещаю :)
было бы интересно почитать так же подробно про lossless сжатие звука (flac/ape)
так же очень мало освещена тема wavelet сжатия изображений
Алгоритм FLAC примерно в таком же духе (только разве что без картинок) рассмотрен в его документации.
Я подумал, скорее буду копать в сторону вейвлетов и MPEG, так как они относительно знакомы и у них есть довольно много общего с jpeg.
Нам действительно нравится, а вы немного обрисуйте темы будущих статей, пожалуйста, если, конечно, есть уже задумки.
Как предлагают ниже, можно затронуть Wavelet-сжатие и JPEG2000. Хотя на Хабре есть хорошие статьи про них. Еще можно про MPEG, у него с JPEG много общего.
UFO landed and left these words here
Wavelet-сжатие и JPEG2000. С отсылкой к этой статье. Тут можно будет найти много общего :)
Думаю даже этого бы хватило, чтобы защитить диссертацию… :)
Спасибо Вам за проделанную работу!
На здоровье! На самом деле в ней нет ничего нового, просто попытка рассказать понятным языком. Хотя поработать пришлось много — систематизировать, описать, придумать примеры и подходы.
Маловата сумма, за столь солидный пост! Но с правилами, увы, не поспоришь.
Если они различаются по цветам, или видна только одна картинка, то, скорее всего, у вас IE (любой версии).

Или Safari.
Я что-то не подумал еще и о мобильных браузерах. Сейчас проверил — стандартный браузер Андроид не показывает.
Алгоритм Хаффмана создает оптимальные коды по весу символов. Но арифметическое кодирование учитывает еще и их расположение.

Нет. Арифметическое кодирование — тоже исключительно энтропийное. Просто Хаффман ограничил нас только целочисленной длиной символа, а вот арифметическое позволяет делать как бы дробное число бит на символ, как раз ровно, сколько нужно, чтобы получить оптимальный код. Поэтому оно эффективнее.

А данные с распределением вида 4 «a», 2 «b», 1 «c» и 1 «d» (т.е. хорошие для Хаффмана) они закодируют одинаково, арифметическое даст на один бит больше. В принципе реальна такая реализация, что даже выход этих двух алгоритмов совпадёт побитово (за исключением этого лишнего бита).
спасибо огромное! знал как это програмить, но никогда не знал, какие страшные формулы за этим скрываются :)
пишите еще, очень интересно!
Потрясающая статья, прочитал запоем, но обязательно перечитаю ещё, вооружившись матлабом или mathematica. Вам потрясающе удаётся подавать материал, не удивлюсь, если вы преподаёте где-нибудь. Однозначно, пишите ещё.
Спасибо! Не преподаю. Но нравится поразбираться в чем-то и объяснить это (поэтому написание статей для меня вроде отдушины :) И сам лучше начинаю понимать пока пишу
Черт, как бы я хотел понимать такие статьи…
Положу пока на полку.
ОМГ, у вас книгу издательство не приняло, наверно, поэтому тут пишете ;)
Можно поподробней про самый первый график? Что значит «два соседних пикселя» (по всем направлениям?) и по какому принципу ставятся синие точки на графике? Не хочется читать дальше не поняв основу.
По графику въехал. Просто путаница из-за того, что градаций серого 256 и картинка 256х256.
UFO landed and left these words here
Четвертый черный канал загружается, но, в итоге, не используется. Вот если бы мы добавили его ко второй картинке, то цвета стали бы правильными (темнее).
Использует, дело в конвертации профилей. Вот пример CMYK, где информация в последнем ряду содержится именно в чёрном канале:

Вот его каналы:

А вот разница между CMYK и RGB:

В Safari точно так же, в Chrome и Firefox эти изображения одинаковые.
Чёрный цвет здесь выглядит именно чёрным, а не иначе. Ваш пример картинки с отключённым чёрным каналом будет выглядеть так:
Спасибо за поправку! То есть, если я правильно понимаю, преобразование CMYK -> RGB может производиться по разным формулам?
Да. Так как формат это предназначенный для разных устройств, то и конвертировать его надо по-разному. Формулы определяются цетовыми профилями. Цветовые профили, грубо говоря, говорят о том, какого цвета тот жёлтый, который производитель принтера назвал жёлтым. Есть ещё gamut — какой диапазон цвета можно напечатать, имея те или иные чернила. Например, вот эти серые области — out-of-gamut, то есть в них вы можете ожидать неправильные цвета при отображении на других устройствах (принтер, например):

Опять же, они определяются настройками профиля устройства (того, где вы их собираетесь печатать).
Пример настроек формул
и того, что с ними получилось
Получается, что у кодера второй картинки и у большинства декодеров совпадают цветовые профили? И, скорее всего, они (кодер и декодеры) предполагают, что картинка будет отображаться на rgb-экране? И разработчики IE использовали какой-то свой профиль?
Цветовой профиль можно или применять, или не применять (don't color manage). Если он не применяется — всё просто: берём картинку, читаем значения цветов, переводим в rgb (считая, что жёлтый, соответствующий y=100 — это и есть жёлтый в rgb, то есть #ffff00). Скорее всего, Chrome и Firefox так и конвертируют картинки.
Можно сохранить профиль в саму картинку, тогда будет ясно, что с ней делать. Вот картинка без профиля, вот — с профилем (U.S. Web Coated (SWOP) v2). Хром отреднерил её одинаково, Сафари — по-разному (обратите внимание на чёрный цвет). Почему хром не прочитал профиль — для меня загадка, я не понимаю (может кто поскажет?).
Если профиля в картинке нет, браузер не знает, как сконвертировать её в свой родной профиль (всмысле, профиль монитора, который пользователь вообще говоря тоже может поменять), поэтому он волен сделать то, что хочет (например, выбрать один из дефолтных).
Они есть не только в cmyk, они есть и в rgb, часто ещё бывает, что фотки в виндовом просмотрщике выглядят плохо, а при редактировании нормально.
Ага профиль нашел
Секция APP2

(9 таких же секций, по одной на каждый скан в прогрессивном кодировании)
Содержимое секций APP не описывается стандартом.
Пишут, что в винде надо запускать хром с ключом --enable-monitor-profile, но у меня все равно картинки одинаковые, что с профилем, что без. Ладно, переживу :)
Это немножко не то. Есть профиль input-устройства (как закодировано), а есть — output (во что надо закодировать для просмотра). Там как раз предлагают, как сделать так, чтобы хром учитывал бы профиль output-устройства (монитора). В нашем случае, по какой-то причине игнорируется input-профиль (вернее, тут у нас не input и output, а document и monitor, здесь подробно рассказано о них).
Я думаю, что это всё-таки баг: потому что в rgb их отлично читают все браузеры, а вот в cmyk почему-то нет. Хотя кому придёт в голову сохранять картинки для веба в cmyk? Поэтому могли просто не делать по ненадобности.
Спасибо за ликбез! Почитаю, у меня в этой области пробел.
Спасибо за статью.
Можно ещё добавить про chroma subsampling (цветовая субдискретизация).
В пункте «цветное изображение» я описал это. Только вместо «субдискретизация» мне нравится использовать слово «прореживание», причем не только мне.
UFO landed and left these words here
Прочитал статью и понял, насколько я туп… Вот на этой картинке, что по осям?
Скрытый текст
image

Что значит «значение точки по оси X — значение первого пикселя, по оси Y — второго»? Какого — первого? Какого — второго? Что такое «значение пикселя»? На картинке с енотом есть пиксели, они могут быть представлены как (x,y,a), где a — яркость. Как из этих троек получилась картинка в спойлере?
Для начала проверим насколько зависимы два соседних пикселя. <...> Отметим их на координатной плоскости точками так, что значение точки по оси X — значение первого пикселя, по оси Y — второго.
Картинка с енотом у нас чёрно-белая, значит, используется значение единственного параметра K (или как его там в grayscale обозначают).
Каждый пиксель в grayscale можно однозначно определить тремя цифрами — (x,y,k) — где k — это яркость. если мы отводим 1 байт на яркость, то да, это 0..255

На картинке из спойлера каждый пиксель тоже можно определить тройкой чисел — (x', y', k'). Вот мне и интересно, как преобразовыаются пиксели из первой картинки во вторую. У автора написано «для всех пар изображения» — это значит, всего будет (256*256)*(256*256-1)/2 пар. Или я как-то иначе понимаю слова «для всех пар»?
Картинку порезали на блоки 2x1 пикселей. Каждый блок я назвал парой пикселей. И каждую такую пару отметил на графике.
Как уже ответили ниже, значение пикселя серого изображения — одно число от 0 до 255. Мы же рассматриваем по 2 соседних пикселя. На графике одной точке соответствуют именно эти 2 пикселя. По X на графике — значение первого пикселя, по Y — второго.
Все равно туплю. Каких соседних? По горизонтали? Вертикали? Диагонали? Или вообще каждый с каждым?
В данном случае по горизонтали. То есть: x0y0 и x1y0, x2y0 и x3y0..., итого 256*256/2 = 32768 точек. Но вообще, не так уж важно — по вертикали или горизонтали, потому что нас интересует выявление зависимостей между соседними. Попробуйте сделать подобный график но для вертикали и вы увидите, что графики почти не отличаются.
Не знаю, обсуждалось ли выше, но
Для примера подумайте, как будет выглядеть дискретная функция, коэффициенты разложения которой равны нулю, кроме последнего.

Как же выглядит эта дискретная функция? На ум лишь приходит чередование чёрных и белых пикселей, но тогда 1-й коэффициент будет 0.5? Или я что-то не понимаю?
Правильно понимаете, но тут уже можно думать без привязки к пикселям. Ответ — такая функция полностью совпадает с последним базисом (с точность до коэффициента), а «проекции» функции на остальные базисы равны нулю.
А теперь, точно так же поделим на четверки и визуально определим базис в четырехмерном пространстве…

Очень подняло настроение. Огромное спасибо за статью.

Заметил маленькую ошибку:


Для нашего изображения размером 256 на 256 получим 256*256/2 точек:

Но получим мы 256*255/2 точек.
Количество пар из 256 элементов есть С2n = n!/(2 × (n-2)!)

Под точкой понимается точка на плоскости XY с координатами:
x = get_pixel(2*n, m);
y = get_pixel(2*n+1, m);
где n ∈ [0, 127], m ∈ [0, 255]
То есть просто рассматриваются соседние пары пикселей

Спасибо за разъяснение! От понимания этого построения зависят все нижеследующие рассуждения, а у меня на этом месте случился «затык».
Осталось уточнить деталь: а как быть, если строках и столбцах исходного изображения нечетное количество пикселей?
Моё собственное предположение: считывать пары не строкам слева направо, а в попеременном направлении, методом «бустрофедон».

Да, можно так. Но задумываться над такими тонкостями нужно только для реализации (не очень хорошей) альтернативы JPEG, в которой разбитие изображение производится не по 8x8, а по 2x1. В контексте этой статьи это не важно. Целью являлось показать то, что на фотографиях существует корреляция соседних пикселей. И, грубо говоря, если есть корреляция, значит есть избыточность, которую мы можем убрать для уменьшения размера.
Кстати, если JPEG-ом закодировать изображение со сторонами не кратными 8, то оно будет расширено кодером до кратного и заполнено каким-либо цветом, или просто мусором, чтобы не тратить время на очистку буфера. Этот излишек просто не показывается просмотрщиками.
Only those users with full accounts are able to leave comments. Log in, please.