Comments 46
Все, победил задачу, вернулся через пару дней и сходу нашел баг.
вот вектор с ошибкой округления 
, правда координаты к сожалению вылезли до 
.
Забавно что решить помог тот самый алгоритм о котором смутно помнил, и спрашивал о нем чуть выше.
На удивление высокое качество решения относительно возможного перебора: Положим результат округления случайным (-0.5,0.5). У моего решения они находятся в интервале [0.473, 0.5), таким образом шанс что все попадут в такой интервал (или лучший) порядка 
. Биткоину до такого еще далеко :)
Сейчас запустил перебор по координатам, наверняка что-то получше найдёт.
P.S. Пока писал комментарий нашлось лучшее решение - 
.
P.S. Отдельное спасибо комментариям в соседнем посте, после прочтения которых пришлось собраться с силами и вернуться к нерешенной проблеме.
Спасибо
Не используйте JPEG
Кстати, воспользуюсь случаем и порекламирую JPEG XL, который хоть и появился только недавно, но по совокупности особенностей, наверное, лучший формат сжатия.
Он поддерживает перекодирование существующих JPEG без потерь, но размер при этом уменьшается на 20—30 %.
Но и без этого формат очень перспективный (высокая степень сжатия, большая скорость, многоканальность, поддержка HDR, анимация и так далее). С нетерпением жду его более широкой поддержки.
Настолько перспективный, что гугель решил выкинуть его из Хрома на мороз.
у него был фатальный недостаток: его писали не они.
googl маму сбросит с поезда бортанёт что угодно ради своего WebP.
Начнём с того, что до выкидывания они его всё же в браузер добавили. Да и они когда выкидывали, не писали же, что формат плохой. Мотивировали тем, что у сообщества, якобы слишком малый интерес. Хотя откуда интересу взяться, если браузер не поддерживает? Ну и так случайно совпало, что гугл разрабатывает WebP 2.
Но даже если Chrome поддерживать не будет, формат от этого бесполезным не становится. Картинки не только в браузерах есть. Я на работе занимаюсь цифровой обработкой изображений (среди прочего) и этот формат мне подходит идеально (особенно радует многоканальность). Поддержка софта подтянется через какое-то время, и домашние фото тоже сконвертирую.
Запасаемся попкорном (ну или скрещиваем пальцы, кому как нравится) - https://chromium-review.googlesource.com/c/chromium/src/+/4095497 . Индустрия - "ЗА" использование JPEG-XL - https://bugs.chromium.org/p/chromium/issues/detail?id=1178058#c189 .
Он поддерживает перекодирование существующих JPEG без потерь
Совсем-совсем без потерь?
AVIF значительно медленнее, качество сжатия для типичных режимов хуже, есть ограничения на размер изображения, хуже поддержка HDR. Многие особенности и вовсе не поддерживаются, так как это, фактически, часть видеокодека, и AVIF никогда не проектировался как формат для изображений. Ну и без потерь свою коллекцию фотографий не сконвертировать.
Из плюсов: лучшая поддержка браузерами (но это не совсем свойство формата) и немногим лучшее качество при очень сильных степенях сжатия.
Осталось найти софт, который безбажно сконвертирует все картинки в хранилище в этот новый формат. И, желательно, не только под вин-11
Шо? Никогда такого не было и вот опять?
Заходим, забиваем двойками матрицу квантования.
defaultQuantMatrix
defaultQuantMatrix = [
2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2
]Смотрим результат
Видим что байтовой точности вполне хватает для сохранения без потерь. Ну, а если зайти в документацию по JPEG то там используется табличные значения синуса, плюс вычисления в целочисленной форме с фиксированной точкой, что избавляет от погрешности в единицу совсем.
сохранения без потерь
Во первых почему двойками а не единицами? Во вторых у вас потери в вашем же скриншоте -- целых 18 штук (из 64 возможных). В прочем на этом же примере с единицами (т.е один байт на входе - один на выходе) остаются 5 ошибок.
Двойки просто для аналитики и наглядности не больше, можете хоть 0.5 написать в погоне за точностью все равно будут неточности. Погрешность один бит на компоненту (разница между изображением оригинальным и фильтрованным через DCT), которую можно решить используя более точную таблицу для DCT как я описал раньше.
можно убрать второе округление (оно там лишнее) и получить без погрешности, но таблицу dct лучше все же брать из документации.
dequant = (v,i) -> (v * quantMatrix[i])результат
Справедливости ради, в jpeg используется минимум 16 битная точность для расчета DCT квантизации и последующей упаковки Хаффмана, не зависимо от входящих 8 битных компонент (по крайней мере в кодеках 90-x). Благодаря тому же Хаффману и DCT (без RLE Для нулей) объем информации не вылезет дальше оригинального размера файла, это уже говорит что в среднем байта хватает. Кроме этого в оригинальном формате есть теги описывающие начало блока 8x8, а это лишняя информация, которая помогает восстановить повреждение файла.
Ну и главное не будем изобретать велосипед: https://ru.wikipedia.org/wiki/JPEG-LS
Еще один пример и пища для размышления. Если взять не 64 значения, а всего лишь два, и считать для них своеобразный аналог DCT то упремся в ту же проблему. Коэффициенты будут получаться в диапазоне +127.5 -128.5, что потребует на 1 бит больше для их хранения. В то же время эта пара коэффициентов будет взаимосвязана по величинам как единичный вектор. То есть чем больше значение одного из коэффициентов тем меньше возможный диапазон другого, это автоматом сокращает несущую часть битов, и благодаря тому же Хаффману возвращает к максимальным 8 битам на значение.
Также нужно не упустить пример где эти два коэффициента считаются несмотря на переполнения байта. Средний с отсечением дробной части, а разница с отсечением старшего бита. Тут также возможно восстановить значения без погрешности используя те же 8 бит. Отмасштабировать это на 64 коэффициента будет проблематично, но сделать преобразование yuv без потери и лишних бит будет возможно. Конечно, это будет не тоже самое.
И для них все перебранные отклонения оказались меньше 0.25.
Плохо искали, жадный покоординатный перебор за секунду нашел 0.259, а за две минуты 0.31.
Вот вектор.
Никак не могу сообразить как искать оптимальнее, не подскажите? Вроде есть какой-то крутой оптимизационный алгоритм (~наименьшей привязки, или что-то типа того) на сетках, но он про чуть другую функцию
def q_error(A, x, step):
t = np.dot(A, x)
y = quant(t, step)
return np.max(np.abs(y-t))
Во, я ждал такой коммент, спасибо! Можете сказать в двух словах, как именно вы искали?
Берем 256^2 случайных векторов, из них оставляем лучший по функции.
Перебираем координату (0..63), перебираем все возможные значения (-128..127), считаем функцию, если улучшилось - улучшаем.
Начинаем заново, делаем так 256 раз.
Теперь с лучшим решением повторяем часть с координатами, только перебираем их парами, в порядке увеличения разности между ними (1..63, 0..63), и все возможные пары значений (-128..127, -128..127), если улучшилось - улучшаем.
Забываем все, начинаем с начала, так как три компоненты не перебрать.
На самом деле отжиг должен работать лучше, но вообще мне сейчас не понятно почему такой поиск работает значительно лучше случайного, но при этом не достаточно хорошо. Сейчас смотрю на возможность улучшения путем замены на мягкий максимум, или что-то подобное, кажется не работает.
Забавно что стандартное ml не находит никаких зависимостей между исходным вектором и ошибкой дискретизации, в то время как уже с чистой ошибкой квантования появляется слабая корреляция.
Причем с максимальной величиной ошибки R2=0.8%, а для средней абсолютной уже добрые R2=13%.
Чем то напоминает классический 2-opt(можно и 3-opt) в https://en.wikipedia.org/wiki/Local_search_(optimization). Как мне кажется можно попытаться улучшить, если для двух пар значений считать оптимум не перебором, а как-то аналитически или более хитрым алгоритмом.
От произвольной точки даже изменение по одной координате абсолютно произвольно меняет дробную часть после линейного оператора по всем измерениям, сомневаюсь что можно что-то придумать.
У меня появилась идея, формально A это оператор поворота с перекошенной метрикой, то есть он может уникально перевести исходный X в любую точку и назад. Соответственно, можно попробовать идти от обратного. Для заданного A*X найти максимально возможную ошибку, в данном случаи это будет С = max(q(X) - X). Теперь надо найти такое обратное преобразование, которое переведет данную точку С в ближайшую к X. Вроде бы шило на мыло, но мы избавились от оператора квантования, а так же можно использовать свойство, что A^-1 = A^T. Конечно если мы будем искать A в реальных числах это не даст глобальный оптимум, но возможно еще что-то можно придумать чтобы продвинуться.
PS: мы можем взять для C лишь одну координату с максимальной ошибкой и соответственно надо подобрать лишь одну строку матрицы действующую на эту координату
Ну и формально как я понял, даже в рамках исходной задачи:
max abs (q(A*X) - A*X). так, как мы ищем максимум по каждой координате независимо, то и влиять на одну координату будет лишь одна строка матрицы. Соответственно, достаточно перебрать все строки матрицы и для каждой из них найти максимум по соответствующей координате. Максимум от максимумов для каждой из строк и будет ответом.
А MCMC плохо работает?
И вот тут читаем местную статейку https://habr.com/ru/post/704432/?amp%3Butm_source=habrahabr&%3Butm_medium=rss Решаем как подбор гиперпараметров, ищем максимум (некоторое извращение, конечно, но должно сработать).
PNG настолько неудобен — сложен и громоздок (по размеру файлов), что понадобились альтернативы в виде WebP, AVIF, JPEG XL, которые сжимают усерднее и тщательнее?
Лично я давно стараюсь хранить картинки именно в PNG, если есть возможность (не считая собственноручно сделанных фоток). Про JPEG забыл, использую только в камерах смартфонов.
Тут в комментах жалуются, что JPEG XL всё равно создаёт артефакты, ну да ладно, может, какая альтернатива привычному джипегу победит. AVIF, WebP 2.0, JPEG XL...
В режиме lossless (который аналог PNG) не создаёт, а для сжатия с потерями нет кодека, который сжимал бы без артефактов.
Если вы про комментарий, автор которого пишет: «Jpeg XL — тот же Jpeg только в профиль», то он, скажем так, слишком поверхностно изучил вопрос.
Насчёт того, кто победит. Тут больше всё зависит от поддержки большими компаниями и поддержки софтом. Если фотоаппараты на телефонах сохраняют всё в старый JPEG, то у всех будет JPEG.
Помню еще был тифф со сжатием от сканера для распознавания текста. Так он графический файл со сканом текста делал меньше самого распознанного теста, на лист А4 можно было получить всего пару кБ
Как тут не вспомнить злую шутку, которую сыграл алгоритм JBIG2 с копирами Xerox.
Осспаде! Даже всего лишь от прокручивания вниз, до конца - аж устал!
Скажите, если мне от такой статьи безмерно о скучно, значит программизм - не моё?
когда публикую картинке в вэб всегда загоняю в Paint.Net и нажимаю Сохранить, обычно там стоит качество 95, меняю на 85. Файлы с 5-8 мб ужимаются до 0.8-1.5 Мб. На качестве визуально никак не отражается, часто еще делаю кроп и даунскейл. Чему я должен удивиться в таком процессе?
Цифровая деградация
в чём? если я из картинки 3200х2000 делаю 320х200 то даже если исходник в PNG и результат в PNG - это в любом случае будет изображение обработанное фильтром. Если я развернутый JPG уменьшаю в 10 раз по каждой стороне, то есть фактически убиваю 99 пикселей из 100, а потом точно так же в памяти я получаю НОВУЮ картинку, которую ПЕРВЫЙ раз сжимаю в JPG.
Кстати, у PNG размер может сильно изменяться от того, чем сжато, столкнулся с этим, когда думал хранить в PNG двоичные данные. Новый браузер сжимает хуже, чем старый FastStone Viewer.
Формату JPEG в этом году исполнилось 30 лет, нужно отдать должное его разработчикам, т.к. он до сих пор имеет свою нишу.
Впрочем, интерес представляет даже не сам JPEG, а возможность использования линейных преобразований для сжатия без потерь.
В сжатии изображений преобразование предназначено для минимизации среднеквадратичной ошибки, вносимой квантованием. Оптимальным считается преобразование Карунена-Лоэва, а DCT-II является его наилучшим приближением для сжатия изображений. То есть, пеобразование является необходимым этапом при сжатии с Потерями.
Если интерес представляет именно сжатие без потерь, стоит обратить внимание на соответсвующие инструменты кодирования:
предсказание DCT коэффициентов по соседним (уже закодированным) блокам (H.263/MPEG-4 Part 2)
предсказание пикселей текущего блока, по восстановленным соседним (Intra predict, H.264 и т.п.)
сегментация изображения с целью кодирования больших равномерных областей бОльшими блоками (квадро-дерево H.265 и т.п.)
для "Screen" контента использовать сжатие с палитрой (H.265)
продвинутые алгоритмы энтропийного сжатия остаточной информации Huffman (с фиксированными таблицами) -> CAVLC -> CABAC
В современных форматах сжатия изображений это реализовано в том или ином виде.
Все, победил задачу, вернулся через пару дней и сходу нашел баг.
вот вектор с ошибкой округления , правда координаты к сожалению вылезли до .
Забавно что решить помог тот самый алгоритм о котором смутно помнил, и спрашивал о нем чуть выше.
На удивление высокое качество решения относительно возможного перебора: Положим результат округления случайным (-0.5,0.5). У моего решения они находятся в интервале [0.473, 0.5), таким образом шанс что все попадут в такой интервал (или лучший) порядка . Биткоину до такого еще далеко :)
Сейчас запустил перебор по координатам, наверняка что-то получше найдёт.
P.S. Пока писал комментарий нашлось лучшее решение - .
P.S. Отдельное спасибо комментариям в соседнем посте, после прочтения которых пришлось собраться с силами и вернуться к нерешенной проблеме.
Земля круглая, вода мокрая, JPEG шакалит, небо голубое… Или нет?