Хабрахабр

«Путин каждый день». Исследование многократного перезалива JPEG

Фраза в кавычках — название группы VK со следующим описанием:

Одна и та же фотография каждый день вручную сохраняется на компьютер и снова заливается, постепенно теряя в качестве.

Слева исходная картинка, загруженная 7 июня 2012, справа — какая она сейчас.

КДПВ

Попробуем разобраться, что происходило в течение этих 7 лет. Такая разница очень подозрительна.

Показаны только те операции, которые иллюстрируют основные принципы алгоритма JPEG. Рассмотрим сильно упрощенную схему кодирования и декодирования JPEG.

Основные принципы алгоритма JPEG

Итак, 4 операции:

  • DCT — дискретное косинусное преобразование.
  • Квантование — округление каждого значения до ближайшей величины, кратной шагу квантования: y = [x/h]*h, где h — шаг.
  • IDCT — обратное дискретное косинусное преобразование.
  • Округление — обычное округление. Этот этап можно было не показывать на схеме, так как он очевиден. Но далее будет продемонстрирована его важность.

То есть, потери и артефакты появляются не из-за косинусного преобразования, а из-за простого квантования. Зеленым цветом выделены операции, сохраняющие всю информацию (не принимая во внимание потери при работе с числами с плавающей запятой), розовым — теряющими. В статье не будет рассматриваться важный этап — кодирование Хаффмана, так как оно выполняется без потерь.

Рассмотрим эти шаги подробнее.

DCT

При кодировании каждое изображение разбивается на квадраты 8x8 (для каждого канала). Так как существует несколько вариаций DCT, то на всякий случай уточню, что JPEG использует DCT второго типа с нормализацией. Косинусное преобразование заключается в нахождении координат этого вектора в другом ортонормированном базисе. Каждый такой квадрат можно представить в виде 64-мерного вектора. Можете представлять, что картинка разбивается на блоки 2x1. Сложно визуализировать 64-мерное пространство, поэтому далее будут приведены 2-мерные аналогии. На графиках, которые будут продемонстрированы далее, оси x соответствуют значения первого пикселя блока, оси y — второго.

Нарисуем вектор (3, 4) в исходном базисе, как показано на рисунке ниже. Продолжая аналогию на конкретном примере, допустим, что значения двух пикселей из исходного изображения — 3 и 4. Координаты вектора в некотором новом базисе — (4. Исходный базис отмечен синим цветом. 4). 8, 1.

Пример преобразования вектора в новом базисе

DCT же предлагает вполне конкретный 64-мерный фиксированный базис. В рассмотренном примере новый базис был выбран случайно. Затронем лишь суть. Обоснование того, почему в JPEG используется именно он, очень интересно, и описывалось мной в другой статье. Но если преобразовать их с помощью DCT, то из получившихся 64 координат в новом базисе (называемых коэффициентами DCT-преобразования) мы можем смело обнулить или грубо округлить их некоторую часть, получив минимальные потери. В целом значения всех пикселей равноценны. Это возможно благодаря особенностям сжимаемых изображений.

Квантование

Поэтому, в зависимости от шага квантования, значения 4. В файле нельзя сохранить дробные значения. 4 будут сохранены так: 8, 1.

  • при шаге 1 (самый щадящий вариант): 5 и 1,
  • при шаге 2: 4 и 2,
  • при шаге 3: 6 и 0.

В JPEG-файле есть как минимум один массив, называемый таблицей квантования, хранящий 64 шага квантования. Обычно шаг выбирается разный для каждого значения. Эта таблица зависит от качества сжатия, задаваемое в любом графическом редакторе.

IDCT

Математически, x = IDCT(DCT(x)), поэтому если бы не было квантования, то можно было бы восстанавливать без потерь. То же самое, что DCT, но с транспонированным базисом. Из-за использования квантования исходный вектор не всегда можно вычислить точно. Но не было бы и сжатия. Наклонной сетке соответствует новый базис, прямой — исходный. На следующем рисунке представлены 2 примера с точным и неточным восстановлением.

2 примера с точным и неточным восстановлением векторов

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

Последовательность перекодирований векторов

Для уменьшения информационного шума, уберем сетку исходного базиса и будем напрямую соединять отрезками исходные и восстановленные векторы (без промежуточного шага). Интересно было бы перебрать все целочисленные векторы и посмотреть, к чему приведет их перекодирование. Новый базис на следующем рисунке повернут на 45 градусов и для него имеем 17. Сначала рассмотрим шаг квантования равный 1 для всех координат. Цвета отрезков ничего не означают, но они будут полезны для предотвращения их визуального слияния. 1% неточных восстановлений.

Перебор векторов для нового базиса в 45 градусов

3 градусов с 7. Этот базис — на 10. 4% неточных восстановлений:

3 градусов"/> <img src="https://habrastorage.org/webt/bs/ig/3k/bsig3kc6xvaiympimbjemxmz6ci.png" alt="Перебор векторов для нового базиса в 10.

Вблизи:

3 градусов вблизи"/> <img src="https://habrastorage.org/webt/zz/nx/lk/zznxlkpwk7zcgdjbzotimj5p6ho.png" alt="Перебор векторов для нового базиса в 10.

4 с 6. А этот — на 10. 4%:

4 градусов"/> <img src="https://habrastorage.org/webt/3j/uj/w_/3jujw_15jsspkq_gyi8ke-o-xje.png" alt="Перебор векторов для нового базиса в 10.

5%: 19 градусов с 12.

Перебор векторов для нового базиса в 19 градусов

Это шаг 5: А вот если задать шаг квантования больше 1, то восстановленные векторы начинают явно концентрироваться близко к узлам сетки.

Шаг 5

Это 2:

Шаг 2

Значения как бы «застревают» в узлах сетки и уже не могут «выпрыгнуть» оттуда в другие узлы. Если изображение перекодировать несколько раз, но с одинаковым шагом, то почти ничего не произойдет по сравнению с однократным перекодированием. Это может завести его как угодно далеко. Если же шаг разный, то вектор будет «скакать» из одного узла сетки в другой. Можно разглядеть крупную сетку с шагом 12. На следующем рисунке показан результат 4 перекодирований с шагами 1, 2, 3, 4. Это значение — наименьшее общее кратное 1, 2, 3, 4.

Результат 4 перекодирований с шагами 1, 2, 3, 4

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

результат 4 перекодирований с шагами от 1 до 4

Округление

Ведь если избавиться от этого этапа, то восстанавливаемое изображение будет представлено дробными значениями, и мы ничего не потеряем при повторном кодировании. А зачем округлять значения после IDCT? Здесь необходимо упомянуть о преобразовании цветовых пространств. С математической точки зрения, мы будем просто переходить от одного базиса к другому без потерь. Особенности глаза и все такое. Хотя JPEG не регламентирует цветовое пространство и позволяет сохранять непосредственно в исходном RGB, но в подавляющем количестве случаев используется предварительная конвертация в YCbCr. А такая конвертация тоже приводит к потерям.

Мы не знаем, какой кодек был использован, но обычно кодеки выполняют округление после преобразования RGB -> YCbCr. Предположим, мы получили JPEG-файл, сжатый с максимальным качеством, то есть с шагом квантования 1 для всех коэффициентов. Если округлим, то большинство из них восстановятся в точности. Так как качество максимально, то после IDCT мы получим дробные, но довольно близкие значения к исходным в пространстве YCbCr.

При последующих перекодированиях разрыв будет увеличиваться все больше. Но если не округлим, то из-за таких небольших отличий преобразование YCbCr -> RGB может еще больше отдалить их от исходных значений. Тогда для 1000 перекодирований получим примерно такую последовательность изменений: Чтобы хоть как-то визуализировать этот процесс, воспользуемся методом главных компонент для проецирования 64-мерных векторов на плоскость.

Изменения без округления

Абсолютные значения осей здесь не имеют особого смысла, но по относительным можно оценить существенность искажений.

Исходный кот:

Исходный кот

После одного пересохранения с качеством 50:

Исходный кот после одного пересохранения с качеством 50

Теперь будем плавно снижать качество с 90 до 50 через 1: После любого последующего количества перекодирований с тем же качеством картинка не меняется.

Плавное снижение качества с 90 до 50 через 1

Произошло примерно то же, что и на уже приводимом графике:

результат 4 перекодирований с шагами от 1 до 4

После одного пересохранения с качеством 20:

После одного пересохранения с качеством 20

Плавно с 90 до 20:

Плавное снижение качества с 90 до 20

Теперь 1000 раз со случайным качеством от 80 до 90:

1000 пересохранений со случайным качеством от 80 до 90

10000 раз:

10000 пересохранений со случайным качеством от 80 до 90

Сначала проверим среднее абсолютное отклонение от самой первой. Приступим к анализу более 2000 картинок из группы VK. По оси x — номер картинки (или день), по y — отклонение.

Среднее абсолютное отклонение от первой

Перейдем к дифференциальному графику, показывающему среднее абсолютное отклонение соседних картинок.

Среднее абсолютное отклонение соседних картинок

До 232-й все идет хорошо, картинки полностью идентичны. Небольшие колебания в начале — нормальное явление. 23 для каждого пикселя (по шкале от 0 до 255). А 233-я внезапно отличается в среднем на 1. Возможно просто изменились таблицы квантования. Это много. Проверим.

Изменения качества

Но не раньше чем у 700-х. Да таблицы менялись. Попробуем дважды перекодировать 232-ю. Тогда, возможно, происходило промежуточное скрытое перекодирование с низким качеством. Наша цель — получить картинку максимально похожую на 233-ю. Для первого раза будем перебирать различные уровни качества, а для второго используем ту же таблицу квантования, что и для всех от 1-й до 700-х. На следующем рисунке по оси x — качество промежуточного перекодирования, по y — среднее абсолютное отклонение от 233-й.

Добавление скрытого перекодирования

Добавление 2-го промежуточного этапа и изменение параметров субдискретизации (subsampling) не улучшило ситуацию. Хотя на графике и есть провал при качестве 75%, примерно равный 1, но все еще далеко от желаемого нуля.

То есть, в какой-то момент картинка резко меняется, затем за несколько дней стабилизируется, но только до тех пор, пока не происходит новый всплеск. С остальными картинками все примерно то же самое, плюс еще накладывается изменение таблиц квантования. Не могу полностью исключить и причастность администратора группы. Возможно, происходит изменение самого изображения на серверах.

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

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»