Всем привет! Курс компьютерной графики в том или ином виде присутствует в образовательной программе любой ИТ-специальности. В числе прочего там обязательно проходят форматы графических файлов и затрагивают алгоритмы сжатия изображений. Сегодня я расскажу о новом, современном методе сжатия изображений, который ещё не вошёл ни в один учебник.
▍ Существующие методы сжатия изображений
Как гласит Википедия (да и остальные источники):
Сжатие изображений — применение алгоритмов сжатия данных к изображениям, хранящимся в цифровом виде. В результате сжатия уменьшается размер изображения, из-за чего уменьшается время передачи изображения по сети и экономится пространство для хранения.
Сжатие изображений подразделяют на сжатие с потерями качества и сжатие без потерь. Сжатие без потерь часто предпочтительней для искусственно построенных изображений, таких как графики, иконки программ, либо для специальных случаев, например, если изображения предназначены для последующей обработки алгоритмами распознавания изображений. Алгоритмы сжатия с потерями при увеличении степени сжатия, как правило, порождают хорошо заметные человеческому глазу артефакты.
Алгоритмы сжатия изображений без потерь базируются на стандартных алгоритмах компрессии данных (rle, huffman, lz и т. д.), а также их вариациях и комбинациях. В общем тут всё хорошо исхожено до нас и придумать что-либо новое практически невозможно. И, как мне кажется, в связи с ростом разрешения и размеров изображений движение в данном направлении полностью прекратилось.
Алгоритмы сжатия изображений с потерями спекулируют на «несовершенстве» человеческих органов зрения и применяют «читерские» приёмы снижения объёма конечной картинки. Как следствие результат будет чуточку (или не чуточку — всё зависит от степени сжатия) отличаться от оригинального изображения. Но мы этого не замечаем, т. к. мозг незаметно восполняет/додумывает недостающее и игнорирует помехи.
Предлагаемый метод как раз относится ко второму «классу» методов сжатия изображений, но при этом не использует аппаратные особенности наших глаз и баги в их прошивке. Пора пояснить суть метода, а также рассказать про уже реализованные(!) энкодеры и декодеры изображений для него.
▍ Суть нового метода сжатия/кодирования изображений
Унылая пора! Очей очарованье!
Приятна мне твоя прощальная краса —
Люблю я пышное природы увяданье,
В багрец и в золото одетые леса.
Помните?
Конечно, помните! Всего 4 строфы от великого Александра Сергеевича, а воображение уже рисует яркую картину осеннего леса. Да что там воображение — я только что запустил «Кандинский 2.0» и нейросеть сгенерировала картинку в цифровом виде за какие-то жалкие 2 минуты.
Думаю, вы уже догадались, в чём суть экстремально сильного метода сжатия изображений. Да, теперь сжатое изображение — это описание на родном языке в простом текстовом виде. Соответственно, энкодер по какому-либо изображению должен генерировать художественное, достаточно подробное текстовое представление, а декодер по этому тексту восстанавливает картинку. Не забыть бы ещё придумать расширение файла и зарезервировать content-type.
▍ Декодеры
Начнём с конца, тем более я уже заспойлерил использование «Кандинского». Помимо «Кандинского» есть ещё некоторое количество публичных нейрохудожников — перечислять их не буду, гугл с этим справится лучше меня. Как правило, на вход подаётся описание изображения в текстовом виде, возможно, даже на родном языке, а на выходе получаем финальную картинку.
«Декодеры» в настоящее время не слишком хороши: медленные, входной текст короткий, итоговый размер изображения фиксированный, результат не всегда радует глаз (вернее сильно зависит от качества «сжатого изображения»), но это мы ещё обсудим, когда перейдём к тестам.
▍ Энкодеры
Их нет. Возможно, реализация формирования художественного описания изображения пока не представляет интереса для общества или технологии не созрели — в общем пока так. Казалось бы, статью можно завершать, но мы воспользуемся очередным хаком — пока искусственный интеллект не созрел, его будет заменять интеллект человеческий! Ловите флешбэк: класс в полнейшей тишине пишет сочинение по репродукции, приколотой на доску или с разворота учебника, выдавливая из себя «на переднем плане изображено...». Мы, конечно, не Пушкины и не Толстые, но пару абзацев набросать сумеем. Есть ещё один нюанс, связанный с декодером, а конкретно с Кандинским — текст не более 300 символов (полагаю, и в остальных местах не лучше).
▍ Тестирование
Исходное изображение — легендарная, эталонная Лена Сёдерберг. Кто не в курсе, марш в Википедию!
Энкодеры — три очаровательные, весьма близкие мне особы, которые любезно согласились поучаствовать в этом безумном эксперименте.
Энкодер 1 — поколение «ТикТока». Выражается весьма лаконично, молодёжно. Экономит своё время и буквы — то, что нужно, с учётом ограничения на 300 символов.
Сегодня мы рассмотрим фотографию с прекрасной девушкой — брюнеткой. Она смотрит прямо на нас своими большими голубыми глазами. Мы видим, что на ней надета панама бежевого цвета с синим пером, которое, безусловно, дополняет её образ. Девушка сфотографирована напротив стены, покрытой лучами заката.
Энкодер 2 — по классификации Википедии типичный «зумер». Очень старательный и умный человечек. В 300 символов уложилась с трудом — не хватило :(
В центре мы видим портрет девушки в широкополой шляпе песочного цвета. Незнакомка оборачивается через правое плечо. Взгляд исподлобья карих глаз загадочный и уверенный. Лицо обрамляют тёмные волосы и ниспадающее с полей шляпы фиолетовое боа. Солнечные лучи ложатся на плечо, оттеняя светлую кожу.
Энкодер 3 — имеет приличное, ещё советское образование — моя главная надежда :)
С фотографии на нас смотрит красивая девушка. На заднем плане мы видим зеркало, в котором она мгновением раньше любовалась собой, примеряя прекрасную широкополую шляпу, богато украшенную пышным страусиным боа. Её взгляд загадочен и в то же время игрив, она прекрасно осознаёт свою привлекательность.
Энкодер 4 — а это сюрприз даже для меня. Начал готовить статью и вспомнил про незрячих. Онлайн-сервисов не нашёл, зато скачал и установил мобильное приложение TapTapSee — наводишь на объект, тапаешь по экрану и получаешь озвучку с текстом. Достаточно быстро, но весьма лаконично:
Женщина в бело-коричневой шляпе.
Декодер, как уже писал выше, «Кандинский» версии 2.0 (да, я ленивый — пробовать остальных не стал :) Декодеру мы немного поможем и будем указывать в настройках стиль генерации «Портретное фото». На страничке с «Кандинским 2.0» есть и просто «Кандинский» (без версии) и «Малевич». Тестировал обоих, но решил не перегружать статью, впрочем, и работают они менее задорно, чем «Кандинский 2.0».
Скорость кодирования/декодирования оценивать пока бессмысленно. Скорость кодирования зависит от настроения/вдохновения наших дам, в общем всё, что называется «человеческим» фактором. Сюда же приплюсуем время, затраченное на их уговоры :) Декодирование также не поддаётся точной оценке — «на глазок» примерно 2 минуты. Пока проигрываем классическим методам.
Степень сжатия колоссальная. Исходное изображение Лены — 512х512 пикселей и занимает 474Kb, а «компрессированное» изображение — 300 символов — это не более 600 байт текста на русском языке в UTF-8. При этом прошу учесть, что мы жмём изображение, уже поджатое алгоритмами PNG! Здесь безусловная победа.
Качество изображения после декодирования. Ввиду того, что нейросеть выдаёт нам результат в формате JPG, то ни о какой цветопередаче, зашумлённости в области перьев и прочих артефактах речи быть не может. Когда разработчики будут готовы предоставить результат в RAW или BMP, тогда и будем это обсуждать.
Напоследок ещё одна несерьёзная метрика — степень схожести исходной Лены и того, что нам сгенерировала нейросеть. Случайно нашёл один ресурс, вернее это первый из выборки гугла, в общем, почему бы и не попробовать?
Результаты привожу ниже:
| Изображение | Похожесть картинок |
|---|---|
Энкодер 1  |
40.64 % |
Энкодер 2  |
34.51 % |
Энкодер 3  |
36.27 % |
Энкодер 4  |
43.69 % |
▍ Выводы
Вот вроде и всё, что я хотел написать про алгоритм экстремального сжатия изображений. Небольшие артефакты выходной картинки связаны с несовершенством современных нейросетей, но мы только в начале большого пути и всякие выводы выводить рано.
Если материал показался сложным, то видимо потому, что статья немного опередила своё время — планировал выпустить где-нибудь в первых числах апреля.
Играй в наш скролл-шутер прямо в Telegram и получай призы! ????️????
Комментарии (96)
Writer
02.02.2023 16:13+53Анекдот:
- Так мне Паваротти не понравился, картавит, в ноты не попадает...
- Вы были на концерте Паваротти?
- Нет, мне Рабинович по телефону напел.
Mishootk
02.02.2023 16:51+3Вы еще "Лена Сёдерберг" вбейте в генератор.
Потихоньку начинает проясняться механика возникновения ночных кошмаров.
akakoychenko
02.02.2023 17:00+7
вбил в midjourney Lena Soderberg
странно, но, нейросеть, реально, не поняла прикола, и показала, что вообще не в теме
MiraclePtr
02.02.2023 17:16+9Но при этом уловила, что фамилия скандинавская, и на вторые две картинки сгенерировала сероглазых белокожих блондинок, что прям очень похоже на жителей северной Европы.
Aniro
02.02.2023 18:28+4Это mj? Stable Diffusion тоже не знает кто это, ни первая версия ни вторая:
SD 2.1
alef13 Автор
02.02.2023 19:46+8Попробуй вбить Lenna Söderberg :)
Aniro
03.02.2023 14:10Все равно не знает. Лены слишком мало в датасете, одной картинки недостаточно. Где-то видел исследования что SD удовлетворительно рисует только порядка сотни селебрити, причем совсем хорошо только пару десятков наиболее известных типа Эммы Уотсон и Харисона Форда. И это была первая версия, до того как датасет почистили от персоналий.
SD 1.5
boolive
02.02.2023 16:53Мне какую-то хрень сгенерировала http://rudalle.ru/check_kandinsky2/9e4b4401796b456da845116784436e7f
Popadanec
02.02.2023 17:13+9Вспомнился лабиринт отражений, Лукьяненко. Там в игре была простая графика, а встроенная в мозг нейросеть(она есть у каждого, называется зрительная кора), достраивает картинку. Естественно что конечное изображение у каждого игрока немного отличается.
ykira
02.02.2023 17:27+1
Stable duffusion
Lena Soderberg in brown hat
negative: (deformed, distorted, disfigured: I 3), poorly drawn, bad anatomy, wrong anatomy, etfra limb, missing limb, floating limb a (mutated hands and fingers 1.4), disconnected limbs, mutation, mutated, ugly disgusting, blurry amputation
seed 3193650323
s_f1
02.02.2023 17:27+32Это не «революционный» метод, а, пожалуй, самый первый. Тысячи лет назад люди «записывали» то, что видят, чтобы потом другие люди могли это раскодировать у себя в голове непосредственно в картинку. Разумеется, получающаяся картинка у каждого будет своя, прямо как… oh, wait…
Strange_R
02.02.2023 18:54+2Думаю, максимальной схожести оригинала и дешифрованного изображения можно добиться если использовать паттерны по аналогии с компьютерными шрифтами когда на принимающем устройстве уже содержатся шаблоны шрифтов (правила их графического вывода), а из источника достаточно передать лишь название шрифта и текст. В итоге принимающее устройство "нарисует" текст требуемым начертанием шрифта. Аналогично если будет некий строгий стандарт классификаций изображений (грубо говоря, по художественным стилям +каким-либо другим уточняющим признакам), то любое изображение можно разложить на этот ряд признаков, а затем достаточно точно воссоздать по ним оригинал. Это напоминает обычное языковое описание изображения, но будет более точным и лаконичным, без разночтений и искажений интерпретации.
Нейросети, генерирующие картинки по описанию, сперва создают миниатюру в низком разрешении, а затем уже другие нейросети повышают разрешение этой миниатюры и дополняют менее значимыми деталями. Аналогично и в способе сжатия помимо описательной части может быть сгенерирована миниатюра оригинального изображения, отображающая сам образ и взаиморасположение основных объектов, и в таком виде миниатюра + описательная часть представлять сжатый файл.
А можно пойти ещё дальше: и передающее, и принимающее устройство могут хранить не только абстрактные художественные паттерны, а вообще целостную библиотеку образов-аватаров - это как Википедия, но из графических образов, в том числе и трёхмерных. И уже оперировать этими образами, подставляя их в самые разные сцены - как совместимые (например, живая рыба в аквариуме), так и любые фентезийные.
vagonovozhaty
02.02.2023 19:36+28Я давно для бэкапов скачал архиватор, который сжимает любой объем данных до 1 байта. Делаю, как и положено, три копии.
Надеюсь, к тому времени, как данные мне понадобятся, автор архиватора, наконец, допилит обещанный разархиватор.
Akon32
02.02.2023 19:39+1Почему "революционный"? Идея сжатия автокодировщиками (autoencoder) известна давно.
BugM
02.02.2023 22:18+10Размер архива считается как файл архива + размер разархивирова. У вас с коэффициентом сжатия все очень печально.
zanuda mode off
vassabi
03.02.2023 00:35-1это если архив самораспаковывающийся ( т.е. с бинарником распаковщика и приданными к нему модулями)
BugM
03.02.2023 01:04+2Нет. Всегда. С бесконечным размером разархиватора размер любого архива составит байт 8 примерно. Ладно пусть 16 байт.
trinxery
03.02.2023 02:10+1Нет. В 16 байтах информации, больше чем на эти самые 16 байт не влезет. (Доказательство, если нужно: жмём все числа подряд)
Заодно и вопрос-претензия к исходному комментарию: почему размер архива обязан считаться с учётом архиватора?
BugM
03.02.2023 02:20+3Нет. В 16 байтах информации, больше чем на эти самые 16 байт не влезет. (Доказательство, если нужно: жмём все числа подряд)
В смысле не влезет? Туда много чего влезет.
uint128 это довольно много. С учетом бесконечного размера разархиватора можно много интересного придумать. Здоровые предрассчитанные таблицы меняющие память на время даже в обычной разработке бывают полезны, а уж а такой специфичной теме как сжатие они совсем магию творить могут. С нейросетями все еще интереснее становится. Подробностей довольно много в интернете. Тема сложная в комментарии не описать. Начать стоит отсюда https://habr.com/ru/post/570694/ и далее по ссылкам.
Заодно и вопрос-претензия к исходному комментарию: почему размер архива обязан считаться с учётом архиватора?
Нет. Ибо это дает легкую возможность накрутить коэффициент сжатия бесплатно.
Readme
03.02.2023 12:21+7Всё-таки не влезет. См. идею про "всё уже записано в числе пи" (Нормальное число). Проблема в том, что для кодирования смещения в таком бесконечном архиве нужно число с энтропией порядка самих закодированных данных.
Ну и вообще, для интересующихся советую познакомиться с понятием Колмогоровская сложность — очень расширяет сознание архиваторостроителям.
mrsantak
03.02.2023 13:00uint128 это довольно много. С учетом бесконечного размера разархиватора можно много интересного придумать. Здоровые предрассчитанные таблицы меняющие память на время даже в обычной разработке бывают полезны, а уж а такой специфичной теме как сжатие они совсем магию творить могут.
Ну расскажите нам, какая магия позволит пожать случайное 32 байтное число в 16 байт без потери информации.
BugM
03.02.2023 13:15https://cs.stackexchange.com/questions/40239/compression-of-random-data-is-impossible
Не стоит проверять алгоритмы сжатия на случайных числах. Вы так ничего не получите. Принято проверять на чем-то структурированном, вроде всего текста Википедии.
trinxery
03.02.2023 14:49Т.е. ваш алгоритм не работает на произвольных данных? Степень сжатия на рандомах проверять действительно не стоит, но тут вопрос в самой возможности сжатия.
mrsantak
03.02.2023 15:04Ну вы же сами утверждали, что
С бесконечным размером разархиватора размер любого архива составит байт 8 примерно. Ладно пусть 16 байт.
32 байтные случайные числа можно прогнать через архиватор и получившийся архив подпадает под квантор "любой".
Не стоит проверять алгоритмы сжатия на случайных числах.
Очень даже можно, упомянутые вами же тексты Википедии вполне себе представимы в виде чисел. И с точки зрения архиватора это будут вполне себе случайные числа, просто с неравномерным распределением. Это на равномерно распределенных случайных числах проверять архиватор бесполезно.
И структурированность тут не причем. Найдутся текст/картинка/etc, что не сожмется ни в 16 байт, ни в любое заранее заданное. Это прямое следстиве обратной теоремы Шеннона для источника общего вида.
trinxery
03.02.2023 15:10+1вполне себе случайные числа, просто с неравномерным распределением
Произвольные -- да, случайные -- нет. При таком подходе все числа можно считать случайными, просто "с неравномерным распределением". Важнейшее качество Г[П]СЧ это как раз таки равномерность и непредсказуемость.
BugM
03.02.2023 18:10+1Множество случайных чисел с хорошим распределением это подмножество любых чисел. Архиваторы общего вида хорошо работают с множеством любых неслучайных чисел. Частные случаи архиваторов работают вообще с конкретными наборами чисел, например видео или текст или голос. С полностью случайными числами не работает ничего.
Для псевдослучайных чисел можно как обычно подобрать вырожденный пример. Ваш ГСЧ инициализируется seed int64. Просто передаем его и длину нужной последовательности и генерируем точно такие же псевдослучайные числа на другой стороне.
mrsantak
03.02.2023 19:35С полностью случайными числами не работает ничего.
Что значит не работает? Алгоритмы сжатия работают с потоками байт, им плевать случайные они или нет. Коэффициент сжатия может получиться равным 1, но работать он будет.
Ну и полностью случайные числа - это прям классный термин. Я так понимаю под ним понимается величина с равномерным распределением? Если да, то таки вы правы - его сжать не получится. И поэтому ваше утверждение про возможность сжать всё в 16 байт при неограниченном размере компилятора - это чушь.
BugM
03.02.2023 20:07Подзравляю вы сумели докопаться к всеобщности.
Коэффициент сжатия 1 это и есть не работает. Будем реалистами.
Ладно вношу поправку: Любые существующие в мире данные. Вроде известного среза Википедии, или всех мемов или всех фильмов в мире.
trinxery
04.02.2023 09:32Коэффициент сжатия 1 это и есть не работает
Коэффициент сжатия ≤1 значит, что не сжимает. Архиватор обязан преобразовывать любые данные на входе к читаемому им же самим формату на выходе, бывает, что и без сжатия.
trinxery
03.02.2023 15:05Нет. Ибо это дает легкую возможность накрутить коэффициент сжатия бесплатно.
В том и смысл, что архиватор-то в одном экземпляре, размер его константен, а сжатой информации потенциально бесконечно много.
Более того: если считать по вашей методике, то коэффициент можно поднять просто архивируя склеенные файлы, верно?
BugM
03.02.2023 18:05Конечно. Зипбомбы давно изобретены.
Но сравнение архиваторов все равно будет честным. Любой приличный архиватор такое сожмет с огромным коэффициентом сжатия. В отличии от бесконечно большого размера запаковщика, который можно взять и накрутить для своего архиватора.
Soukhinov
04.02.2023 19:46+3Давайте, я разрешу ваш спор. (Извините, не знаю, кто вы, какие у вас компетенции и возраст. Также я не читал всю ветку дискуссии, но увидел, что она длинная).
Вопрос: взяли архиватор, сжали файл размером 1 гигабайт до размера 1 байт. Следует ли включить размер разархиватора (например, 2 гигабайта) в размер архива при вычислении степени сжатия?
Ответ: это зависит от информации, которой обладали разработчики (раз)архиватора на момент его разработки.
Если разработчики знали заранее, что (раз)архиватору будет подан на вход именно этот файл, то размер разахиватора следует включить в размер архива при вычислении степени сжатия.
Если же разработчики разрабатывали (раз)архиватор только на основе априорной информации (известной до того, как будет получена хоть какая-то информация о том, что именно мы собираемся сжимать), то следует смотреть только на размер архива, игнорируя размер разархиватора.
Пояснение: на практике мы не имеем полной информационной независимости между разработкой (раз)ахиватора и файлами, которые мы собираемся сжимать. Даже если предположить, что (раз)архиватор был разработан инопланетянами, не знающими ровным счётом ничего о нашей планете, информационная зависимость между разархиватором и сжимаемым файлом может возникнуть в ситуации, когда пользователь знает, что конкретный тип информации лучше сжимается именно этим архиватором, и подсознательно использует его в «подходящих» случаях.
Обычно этой информационной зависимостью можно пренебречь, особенно когда сжимается новая информация, созданная через несколько лет после разработки (раз)архиватора.
Но можно представить и противоположный случай: разархиватор размером несколько петабайт, содержит в себе кучу картинок из Интернета, и сжимаемая картинка вдруг оказалась в базе (раз)архиватора. Есть ли здесь информационная независимость? Очевидно, нет.
Доказательство очень сложно. Но можно представить себе, что мы межгалактически передаём информацию информационно-независимым от нас инопланетянам (например, это первая передача). Тогда нам нужно передать разахиватор и сжатые файлы. Ввиду того, что количество передаваемых сжатых файлов не ограничено, при большом количестве этих файлов размер разархиватора в итоге станет пренебрежимо малым относительно общего количества переданной информации.
Примечание: тут кто-то приводил пример «сжатия» информации путём передачи ссылки на картинку в Интернете. Это невалидный пример, ибо отправитель и получатель не являются информационно-независимыми (в том смысле, что мессенджер, через который отправлена ссылка, не является единственной переданной информацией). Эту ситуацию следует рассматривать скорее так, что третья сторона (Интернет) передаёт информацию двум получателям. Аналогично, если мы с инопланетянами будем наблюдать некий общий объект во Вселенной, и обмениваться информацией, касающейся этого объекта, то «правильную» степень сжатия этой информации посчитать будет очень непросто из-за возникшей информационной зависимости.
trinxery
04.02.2023 20:34оффтоп: жаль, что карма пользователя без статей ограничена. такие люди, как вы, дают надежду на светлое будущее Хабра.
BugM
05.02.2023 00:43Вы ввели новое понятие. Знал или не знал. Которое дает огромное преимущество в соревновании. То есть всем выгодно доказать что он не знал.
Как будете определять знал или не знал? Темная комната, яркая лампа в глаза, паяльник? Я других способов не знаю. И этот на самом деле не очень надежный.
Akon32
03.02.2023 21:09+1Размер архива считается как файл архива + размер разархивирова.
Неправда. Для такого архиватора бесконечного размера, архив тоже должен быть бесконечного размера!
Эти ваши 16 байт позволят адресовать всего лишь 2^128 разных вариантов содержимого, а не бесконечность. Соответственно, если в архиваторе нет бесконечных файлов, его размер не будет бесконечным при конечном размере ключа.
BugM
04.02.2023 13:58Неправда. Для такого архиватора бесконечного размера, архив тоже должен быть бесконечного размера!
Почему?
Эти ваши 16 байт позволят адресовать всего лишь 2^128 разных вариантов содержимого, а не бесконечность. Соответственно, если в архиваторе нет бесконечных файлов, его размер не будет бесконечным при конечном размере ключа.
2^128 это немного больше чем люди способны создать за любое время. Если брать опять любые реальные вещи, а не абстрактный набор байт.
Я могу согласиться что этот архиватор будет эффективно сжимать только любой существующий в мире файл. Вроде нестрашное ограничение?
trinxery
04.02.2023 14:58Если брать опять любые реальные вещи, а не абстрактный набор байт.
Если случайные значения не есть реальная вещь, то что насчёт зашифрованных данных? Весов для нейросетки? Вы, как я понял, предлагаете индексировать вообще всю информацию на свете и использовать пресловутый 128-битный индекс как результат "сжатия"?
BugM
04.02.2023 15:28Хорошо шифрованные данные неотличимы от случайных. И поэтому несжимаемы. Это никто и не пытается делать. В начале данные сжимают, потом шифруют.
У вас опять абстрактный и неприменимый в реальности пример.
trinxery
04.02.2023 15:45И поэтому несжимаемы.
В каком моменте данные становятся достаточно случайными, чтобы не быть сжатыми вашим архиватором?
Обычный архиватор с условием выброса ошибки при длине результата, большей 16ти байт, попадает под определение вашего архиватора. Все ошибки оправдываются слишком большой случайностью входных данных.
BugM
04.02.2023 16:14Да в общем как и сейчас. Попробуйте сжать что-то нормально шифрованное. Это приведет к полному провалу. Ничего нового.
Зачем? Любой обычный файл сожмется без проблем. Фильмы, музыка, картинки, тексты, да примерно все что угодно что нужно в реальной жизни. Это заметно лучше любого специализированного типа архиваторов и очень близко к универсальным алгоритмам сжатия. Результат вполне себе достойный.
trinxery
04.02.2023 16:25Это приведет к полному провалу.
Архиваторы обычные можно применять для сжатия всего подряд -- как, например, сжатие страниц в интернете. Обычно сжимает хорошо, но если попало что-то не то и сжатия не вышло -- не проблема, пусть будет так -- файл выйдет байт на десять больше. Ваш архиватор просто откажется сжимать -- см. вторую часть моего прошлого комментария.
Фильмы, музыка, картинки
Есть сжатие с потерями. Без потерь сжимается отвратительно и вообще сжимать так нет необходимости.
примерно все что угодно что нужно в реальной жизни
было бы неплохо пожать веса к сетке, знаете ли
На мои вопросы вы не ответили -- критерии случайности данных и про равенство архиватора "с вылетом ошибки" вашему.
BugM
04.02.2023 16:46Ваш архиватор просто откажется сжимать -- см. вторую часть моего прошлого комментария.
Написать ифчик который выдаст тот же файл + заголовок совсем несложно. Результат будет сравним с любым текущим существующим архиватором. Почему вы считаете это проблемой?
Есть сжатие с потерями. Без потерь сжимается отвратительно и вообще сжимать так нет необходимости.
С чего бы это? С бесконечным размеров разархиватора я готов сжимать все фильмы без потерь до нескольких байт. Вообще не вижу проблем. Это заметно лучше любого текущего алгоритма сжатия видео.
На мои вопросы вы не ответили -- критерии случайности данных и про равенство архиватора "с вылетом ошибки" вашему.
А оно вам надо? Зайдите лучше с другой стороны. Можно сжать до пару байт любой существующий в мире файл. В конце концов что-то новое появляется не так часто и можно просто выпустить обновление моего архиватора чтобы он это поддержал.
trinxery
04.02.2023 17:06Почему вы считаете это проблемой?
Мой "вариант" и есть исключение таких случаев ради умещения в 16 байт.
С бесконечным размеров разархиватора я готов сжимать все фильмы без потерь до нескольких байт.
Можно сжать до пару байт любой существующий в мире файл.
Как вы будете сжимать файл, не находящийся в вашей базе?
Ваш бесконечного размера архиватор включает же сам себя? Сжимаем его самого -- получаем число икс. Сжимаем его самого кроме последнего байта -- число другое. Так как длина бесконечная, мы упрёмся в 2^128 значений.
В конце концов что-то новое появляется не так часто и можно просто выпустить обновление моего архиватора чтобы он это поддержал.
Т.е. предыдущие версии просто не будут разжимать что угодно новое? Отличный выход.
BugM
04.02.2023 17:20Т.е. предыдущие версии просто не будут разжимать что угодно новое? Отличный выход.
И? К автообновленияем все привыкли. Опять ничего нового.
Как вы будете сжимать файл, не находящийся в вашей базе?
Сжимать легко. Разжимать только обновления распаковщика.
Это опять не является проблемой. Основной трафик это видео. Которого конечное количество. Вчерашнее видео доступное все это приемлемый результат. В конце концов подождать один день и получить все видео сжатое до пары байт. Вместо того чтобы качать эти жутко неэффективные текущие архивы.
Ваш бесконечного размера архиватор включает же сам себя? Сжимаем его самого -- получаем число икс. Сжимаем его самого кроме последнего байта -- число другое. Так как длина бесконечная, мы упрёмся в 2^128 значений.
А зачем? Посмотрите начало ветки. Размер разархиватора люди предлагают не учитывать. Он любой. Просто не паримся.
trinxery
04.02.2023 17:50К автообновленияем все привыкли.
В конце концов подождать один день и получить все видео сжатое до пары байт.
Хороший архиватор -- если скачать весь интернет, то второй раз качать не придётся!! вот это да
Размер разархиватора люди предлагают не учитывать.
...при подсчёте коэффициента сжатия. В цитируемом вами отрывке речь идёт о принципиальной неработоспособности архиватора.
(Весело обсуждать невозможный технически архиватор)
BugM
04.02.2023 18:05Это неплохой пример краевого случая почему размер архива надо считать вместе с размеров разархиватора. Тогда таких проблем не будет, все решено на уровне правил подсчета и они соответствуют реальному миру.
В обратную сторону краевые случаи обрабатываются по правилам без проблем. С типичным размером cli разархиватора около мегабайта-двух его размер почти не влияет на эффективность сжатия даже одного гигабайта. Оптимизировать и уменьшать его размер дальше нет смысла.
MagisterAlexandr
04.02.2023 18:22Для сжатия текстов/исходников/html наверное было бы хорошо иметь какой-нибудь словарь на блокчейне на несколько гигабайт.
BugM
04.02.2023 18:33Выкиньте блочейн (он как обычно любую задачу решает хуже любого другого способа) и получите довольно типичный способ сжатия со словарем. Обычный zstd так умеет. Что-то экспериментальное наверняка и с гигабайтными словарями умеет работать прилично.
trinxery
04.02.2023 19:01Это неплохой пример краевого случая почему
...нужно пользоваться нормальными архиваторами, алгоритмическими, а не пытающимися утянуть частовстречающиеся куски файлов.
С типичным размером cli разархиватора около мегабайта-двух его размер почти не влияет на эффективность сжатия даже одного гигабайта.
Обратная сторона: сжимаем миллион нулевых байт в, например, тридцать байт -- коэффициент сжатия меньше одного; сжимаем терабайт -- ситуация друга, хотя сжатия абсолютно подобны друг другу.
BugM
04.02.2023 19:28...нужно пользоваться нормальными архиваторами, алгоритмическими, а не пытающимися утянуть частовстречающиеся куски файлов.
А почему? Сделать словарь из часто встречающихся кусков и пользоваться им это разумная идея. Она реализована на практике и неплохо работает. Не всегда, но применимость есть. Размер архива уменьшается.
Дальше эту идею можно развить в ширь и хранить все файлы вообще. Тогда размер архива уменьшится до единиц байт.
Обратная сторона: сжимаем миллион нулевых байт в, например, тридцать байт -- коэффициент сжатия меньше одного; сжимаем терабайт -- ситуация друга, хотя сжатия абсолютно подобны друг другу.
Конечно. Поэтому тесты коэффициента на таких маленьких файлах стараются не проводить. Типичный объем данных для тестирования алгоритмов сжатия сейчас это около гигабайта.
trinxery
04.02.2023 19:36Сделать словарь из часто встречающихся кусков и пользоваться им это разумная идея.
Только если что для каждого отдельного случая, в сам архиватор вписывать словарь бесполезно, достаточно длинных и встречающихся везде кусков нет.
Дальше эту идею можно развить в ширь и хранить все файлы вообще. Тогда размер архива уменьшится до единиц байт.
Даже архивом назвать сложно -- сжатия-то нет. Ntfs/ext4 мои тоже архивы тогда, только вместо двухбайтовых значений -- пути и inode'ы.
Поэтому тесты коэффициента на таких маленьких файлах стараются не проводить.
Мой абзац был про то, что даже гениальный архиватор, сжимающий мегабайт рандома в байт по вашему коэффициенту выдающимся не будет.
Akon32
03.02.2023 21:04Размер архива считается как файл архива + размер разархивирова.
С чего бы? Бывают схемы сжатия, где например словарь хранится отдельно от архива, или даже схема данных хранится отдельно от данных, что тоже экономит место.
В теории-то да, можно представить "распаковщик бесконечного размера", но на практике это невозможно, а размер архиватора не всегда важен. Когда данные куда-то передаются, архиватор не всегда передаётся - он может быть передан 1 раз заранее.
BugM
04.02.2023 14:01Иначе непонятно как считать. Вот есть у вас разархиватор размером в терабайт. Он эффективнее всех существующих процентов на 50. Он достоин считаться лучшим и рекомендованным к использованию?
Для типичных случаев где cli версия весит килобайты или единицы мегабайт это не критично. Это важно именно для краевых случаев.
vassabi
04.02.2023 17:39ко мне приходил человек из авиации - он был бы согласен возить разархиватор и в 10 терабайт, если бы только
1) ролики с ютуба\тиктока влезали в радиоканал в самолете (т.е. чтобы каждый пассажир мог смотреть свой хотя бы в 420р)
2) не сильно долго бы распаковывал (ну там секунды)
Akon32
04.02.2023 18:36Вот есть у вас разархиватор размером в терабайт. Он эффективнее всех
существующих процентов на 50. Он достоин считаться лучшим и
рекомендованным к использованию?При определённых условиях (если работает достаточно быстро и экономит, например, от пары терабайт) - вполне.
Zara6502
03.02.2023 06:02+5Курс компьютерной графики в том или ином виде присутствует в образовательной программе любой ИТ-специальности
Нет
В числе прочего там обязательно проходят форматы графических файлов и затрагивают алгоритмы сжатия изображений
Нет
Скажу больше - большинство того что на Хабре обсуждается на уровне "библий для ИТ" или "это должен знать каждый" - в образовательных программах в принципе отсутствует. Можно сколько угодно рассуждать о качестве такого образования, но факт остается фактом.
Refridgerator
03.02.2023 06:08+2Идея-то вполне рабочая, если к ней подойти строго математически, а не надеяться на ИИ в нейросетях. В частности, если сжимается фотография лица, то система должна уметь распознавать и восстанавливать (навскидку):
1) определить пол (1 бит)
3) определить возраст (1 байт должно хватить)
4) определить положение (фас/профиль/etc)
5) определить цвет/разрез/etc глаз
6) определить форму губ
7) определить фокусное расстояние
8) определить положение и источник освещения
и т.д.
То есть иметь небольшой набор чисто числовых (а не текстовых!) характеристик, гарантирующих узнавание закодированного человека вне зависимости от того, участвовал он в обучающей выборке для нейросети или нет.
Deosis
03.02.2023 07:30+1Идея интересная, но дьявол кроется в деталях. На кодирование всех веснушек уйдет много места, либо декодер восстановит не ту фотографию.
Refridgerator
03.02.2023 07:44Веснушки можно считать отдельно и фиксировать их количество. Декодер на основе биг-дата анализа разместит их в наиболее вероятных местах. Если они достаточно большого размера — их не может быть много, то их можно просто дискретным списком с координатами передавать. Заодно можно ввести дополнительные категории типа доброкачественная, недоброкачественная, прыщ, бородавка, фурункул и т.д.
Syzd
03.02.2023 08:08+6Вы придумали современную версию фоторобота для полиции, там где подбородки меняются, брови, глаза.
Arlekcangp
03.02.2023 17:17+1Не, слишком примитивно. Сейчас можно пропустить через 'автоэнкодер'. Он выявит значимые характеристики. Из них сделать вектор, который потом можно подавать на половину автоэнкодера для декодирования. И так уже пробуют. Тут нужно найти баланс. Целиком изображение если пропустить, то он его "обобщит" до вектора из которого только мыльные пузыри получить назад можно. А вот если таким макаром кодировать результат, который выдает сверточная сеть, то м б можно что то пытаться получить вменяемое. Тут ещё было бы интересно представить изображение в виде основного вектора и добавок к нему. Основные вектора уже могут быть зашиты в декодере. (Например набор характерных лиц) А набор "добавок" - это само кодированные изображение. Его подаем на вход декодера и получаем первоначальный вариант с некоторыми искажениями. Чем больше векторов вшито в декодер и чем жирнее добавка тем лучше качество.
FanatPHP
03.02.2023 09:14+3Когда очень нужно нагнать трафика в корпоративный блог, но писать совсем уж нечего.
MagisterAlexandr
03.02.2023 11:15
diogen4212
03.02.2023 11:16+5Загрузил Лену в WebUI от Automatic1111, нажал «Interrogate CLIP»: «a woman wearing a hat with a feather on it's brim and a mirror behind her back, Barbara Nessim, kodachrome, a colorized photo, american barbizon school»
Потом сгенерировал по этому описанию несколько картинок с восстановлением лиц, больше всего понравилась вот эта..
Ещё есть модель ALTClip, которая понимает русский язык, но с лицами часто треш выходит. Загрузил 4 описания из статьи.1 (сегодня мы рассмотрим фотографию..
2 (в центре мы видим портрет..)
3
4
pda0
03.02.2023 12:12+1Такую идею высказывали не раз и не два. Даже помню кто-то видеокодек хотел так сделать. Показать нейросети фильм, а потом попросить её "вспомнить" его. :)
Если отжать магию нейросетей, то то, что вы предлагаете, лишь обычное сжатие со словарём, только со статическим, разделяемым между всеми участниками. Для музыки аналогичный метод вполне себе существовал в виде midi. Надо садиться и считать какой размер базы шаблонов будет достаточен для значительного обгона степени сжатия по сравнению с другими методами. Возможно её размер будет порядка сотни гигабайт, что делало бы её непрактичной для 90-х, но подходящей для современных компьютеров. (Но не для мобильных устройств.) А может размер окажется порядка петабайт или даже экзабайт и идея всё ещё будет непрактичной.
carbonarium
03.02.2023 13:04+1Некоторые специалисты называют это "словесный портрет".
Спасибо, автор, повеселил ))
piuzziconezz
03.02.2023 16:22Все люди одинаковые со степенью достоверности 99,9%, судя по нашему геному.
julicq
03.02.2023 18:48+1Господа, VQ-VAE нас спасет. Использование латентного пространства очень хорошо подходит для создания качественных энкодеров-декодеров. Соответственно, их суть отлично ложится на теорию и практику сжатия изображений. Очень часто - практически без потерь там, где имеющиеся алгоритмы ухудшают картинку.
Soukhinov
03.02.2023 23:05+4Я специалист по обработке изображений, и я очень недоволен, когда при сжатии изображения «с потерями» изображение становится хуже. Почему «теряется» всё самое хорошее, а плохое остаётся, да ещё и добавляются артефакты? Пусть теряются дефекты!
Правильный алгоритм сжатия с потерями в случае сильного сжатия должен работать так:
Шума на сжатой фотографии нет, потому как для хранения всех «шуминок» в файле не осталось места. Вместо этого идеально чистое и чёткое изображение.
Хроматических аберраций тоже нет — не сохранились.
Разрешение бесконечное. Зачем нужны пиксели? Достаточно соотношения сторон. Разрешение — это лишнее число; его можно не сохранять.
Если на фотографии запечатлён человек, то его кожа будет без дефектов и морщин — ведь нужно много лишних байт, чтобы записать координаты каждой морщины, прыща, пятна и шрама. Аналогично, если запечатлён какой-то предмет (например, автомобиль), то он тоже будет без дефектов (без царапин, чистый) — на хранение дефектов не хватило места.
Повреждение файла обнаружить невозможно. Ведь сама возможность обнаружения повреждений означает, что кодирование избыточно. Если мы выжимаем каждый бит, то любая комбинация байтов должна быть валидным изображением. Изменился какой-нибудь бит в файле — и, например, человек на фотографии из мужчины превратился в женщину. В идеале, увеличивать степень сжатия можно, просто отбрасывая байты с конца файла.
Если изображение сгенерировано алгоритмически, то после сжатия без потерь «правильным» алгоритмом размер изображения не должен превышать размер исходного кода (или исполняемого) файла, который это изображение породил. Например, если какая-нибудь демка (EXE-файл на 64 килобайта) генерирует пятиминутное видео, то такое видео должно сжаться вообще без потерь в 64 килобайта (или меньше).
И так далее. В будущем, когда такие алгоритмы будут разработаны, будет так:
—Я тебе послал фотку моей девушки. Как тебе?
—Что-то я не пойму, она действительно такая красивая, или это просто Телеграм так сильно фотку зашакалил?
Или:
—Я тебе послал фотку моей девушки. Как тебе?
—Там какой-то мужик-алкаш на фотографии.
—Странно. Наверное, файл повредился при передаче.MagisterAlexandr
04.02.2023 09:12Не знаю, зачем нужно будет аж так экономить место и трафик в эпоху сильного ИИ, но определённая красота в этом есть.
nikalone555
04.02.2023 16:25А уместно ли вообще говорить о сжатии в данном случае, когда от исходного файла не остается ничего? Тут скорее копирование. Вроде ерунда, но если подумать про авторские права и уникальность, то останутся ли они?
wyfinger
Еще лучше метод сжатия - ссылку на картинку в интернете даете и все.
Zara6502
Удивительно что когда я написал про это статью, то засрали карму так что я уже никогда не вернусь. А вам вон плюсиков настрочили.
Oplkill
Суть Хабра в том, что тебе могут накинуть в карму, даже если рейтинг комментария высокий
FanatPHP
Тут понимать надо: статьи ни о чем можно писать только в корпоративных блогах.
niwir
но у вас нет опубликованных статей...
Popadanec
Скрытые в черновики даже в списке количества не отображаются.
alef13 Автор
держи плюсик, мне не жалко. А статья шуточная, и я об этом написал
Zara6502
данке
dyadyaSerezha
Есть еще короче. Описание для декодера: баба в шляпе.
Гораздо короче ссылки.
steff
Укорачиватель ссылок ещё несколько десятков процентов к уровню сжатия даст))