Pull to refresh

Опубликованы спецификации графического формата QOI, который в 20–50 раз быстрее PNG

ITSumma corporate blog Open source *Algorithms *Image processing *Data compression *
Примерно месяц назад польский программист Доминик Шаблевски представил на суд публики новый графический формат QOI (Quite OK Image). Формат сжимает без потери качества, ориентируется на максимальную скорость кодирования/декодирования изображений, и по бенчмаркам значительно превосходит libpng и stbi. Разница в сжатии составляет 20−50 раз, в декомпрессии — 3−4 раза.

Кроме того, формат сжатия исключительно простой, закодирован буквально в 300 строчек кода, и работает по простым правилам типа кодирования повторов (RLE). Естественно, он не связан никакими лицензионными соглашениями и ограничениями.

И вот вчера после исправления всех недочётов наконец-то опубликованы финальные спецификации, так что теперь QOI документально забетонирован и его можно начинать использовать в продакшне. Что примечательно, полные спецификации QOI поместились на одной странице!
Читать дальше →
Total votes 43: ↑39 and ↓4 +35
Views 4.4K
Comments 14

Нейросетевое сжатие данных

.NET *
Sandbox
imageВ этой статье я хочу поведать о еще одном классе задач, решаемых нейронными сетями – сжатии данных. Алгоритм, описанный в статье, не претендует на использование в реальных боевых условиях по причине существования более эффективных алгоритмов. Сразу оговорюсь, что речь пойдет только о сжатии без потерь.
Большинство источников в Интернете утверждают, что есть 3 основных популярных архитектур нейронных сетей, решающих задачу сжатия данных.

1. Сеть Кохонена и ее вариации. Часто используется для сжатия изображений с потерей качества, не является алгоритмом сжатия без потерь.

2. Ассоциативная память (Сеть Хопфилда, Двунаправленная ассоциативная память и др.). «Сжатие данных» для этого класса сетей является «фичей», побочным явлением, так как главным их предназначением есть восстановление исходного сигнала/образа из зашумленных/поврежденных входных данных. Чаще всего, на вход этих сетей поступает зашумленный образ той же размерности, потому о сжатии данных речь не идет.

3. Метод «Бутылочного горлышка».

О последнем методе и пойдет речь в статье.
Читать дальше →
Total votes 41: ↑38 and ↓3 +35
Views 21K
Comments 25

Новости формата WebP

IT-companies
Можно смело утверждать, что этой осенью формат WebP переживает второе рождение. Сообщения о новых возможностях следуют буквально одно за другим. Здесь я приведу перевод самых интересных новостей, касающихся формата WebP и перспектив его развития и поддержки. Топик сознательно не оформляется как перевод, так как данные приведены сразу из нескольких источников. Итак, полупрозрачность, сжатие без потерь, поддержка IE6+ и так далее!
Читать дальше →
Total votes 75: ↑73 and ↓2 +71
Views 2.1K
Comments 49

Простейшие алгоритмы сжатия: RLE и LZ77

Algorithms *
Tutorial
Давным-давно, когда я был ещё наивным школьником, мне вдруг стало жутко любопытно: а каким же волшебным образом данные в архивах занимают меньше места? Оседлав свой верный диалап, я начал бороздить просторы Интернетов в поисках ответа, и нашёл множество статей с довольно подробным изложением интересующей меня информации. Но ни одна из них тогда не показалась мне простой для понимания — листинги кода казались китайской грамотой, а попытки понять необычную терминологию и разнообразные формулы не увенчивались успехом.

Поэтому целью данной статьи является дать представление о простейших алгоритмах сжатия тем, кому знания и опыт пока ещё не позволяют сходу понимать более профессиональную литературу, или же чей профиль и вовсе далёк от подобной тематики. Т.е. я «на пальцах» расскажу об одних из простейших алгоритмах и приведу примеры их реализации без километровых листингов кода.
Читать дальше →
Total votes 102: ↑95 and ↓7 +88
Views 113K
Comments 8

Сжатие информации без потерь. Часть первая

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

В этой статье я коснусь фундаментальных моментов сжатия и основных типов алгоритмов.
Читать дальше →
Total votes 40: ↑36 and ↓4 +32
Views 71K
Comments 18

Сжатие информации без потерь. Часть вторая

Algorithms *
Первая часть.

Во второй части будут рассмотрены арифметическое кодирование и преобразование Барроуза-Уилера (последнее часто незаслуженно забывают во многих статьях). Я не буду рассматривать семейство алгоритмов LZ, так как про них на хабре уже были неплохие статьи.

Итак, начнем с арифметического кодирования — на мой взгляд, одного из самых изящных (с точки зрения идеи) методов сжатия.
Читать дальше →
Total votes 30: ↑28 and ↓2 +26
Views 21K
Comments 7

x264 или как кодировать видео

Working with video *
Sandbox
Tutorial
Проблема с кодированием видео и его сжатием его из гигабайтов в мегабайты, по-моему, всегда была актуальной. Если более менее профессиональные операторы, монтажники и т.д. уже не одну кошку съели на этой теме, то например любители и те, кто записывают видео с экрана своего монитора, порой долго чешут затылок, прежде чем добиться каких либо серьезных результатов. В итоге куча потерянного времени, никому не нужные гигабайты исходящего трафика для загрузки домашнего видео на ютуб. Конечно, можно использовать в какой-то степени готовые решения в лице одной программы, и сжать видео буквально тремя кликами, но это не наш подход, когда абсолютно все шаги можно контролировать и влиять на них. Покопавшись в поиске, Хабр так и не выдал ничего похожего. Хотя возможно, что просто плохо поискал.
Читать дальше →
Total votes 71: ↑46 and ↓25 +21
Views 208K
Comments 71

Простой пример кодирования текстовой строки по Хаффману

Algorithms *
Translation
Вы, наверное, слышали о Дэвиде Хаффмане и его популярном алгоритме сжатия. Если нет, то предлагаю вам самостоятельно поискать в интернете — в этой статье я не буду донимать вас уроками истории или математики. Я попробую показать вам на практике, как применить этот алгоритм к текстовой строке. Наше приложение просто сгенерирует значения кода для символов из введенной строки и наборот — воссоздаст оригинальную строку из представленного кода.
Читать дальше →
Total votes 26: ↑17 and ↓9 +8
Views 42K
Comments 3

Метод фрагментарного сжатия видеопотока

Algorithms *
Я решил представить на суд уважаемого хабрасообщества свою разработку — метод фрагментарного сжатия видеопотока. Особенностью предлагаемого метода является полное соответствие сжатого видеопотока исходному, то есть метод осуществляет сжатие без потерь.
Читать дальше →
Total votes 29: ↑27 and ↓2 +25
Views 14K
Comments 24

Как сжать плоского кота

Algorithms *Image processing *C *
Sandbox
Однажды в студеную зимнюю пору… ровно год назад, у нас появилась нетривиальная задача. Есть экран на электронных чернилах, есть процессор 16МГц (да-да, во встраиваемой электронике, особенно сверхнизкого энергопотребления, встречаются и такие) и совсем нет памяти. Ну, т.е. килобайтов 8 RAM и 256 Flash. Килобайтов, Карл. И в эти унылые килобайты необходимо запихнуть несколько изображений 800х600 в четырех оттенках серого. Быстро перемножив в уме 800 на 600 и на 2 бита на пиксель получаем 120 тысяч байтов. Несколько не влезает. Надо сжимать.

Так перед нами появилась задача: «как сжать плоского кота»? Почему кота? Да потому, что на котиках тестировали, на чем же еще черно-белые картинки проверять. Не на долларовых банкнотах же.
Читать дальше →
Total votes 85: ↑80 and ↓5 +75
Views 39K
Comments 65

Сказ о компрессоре, который можно называть, но не помню, как

Assembler *Reverse engineering *
Вашему вниманию предоставляется не совсем новогодняя история, в которой есть завязка, интрига, детективное расследование, погоня, коварство, мудрость древних и счастливый финал. Под катом вас ожидают археологические раскопки Хабра эпохи перестройки и щепотка ассемблера x86 по вкусу.

Читать дальше →
Total votes 66: ↑64 and ↓2 +62
Views 23K
Comments 15

Алгоритм сжатия без потерь Broo и дельта-кодирование, сравнение с Xdelta3. Развитие домашнего проекта

Programming *Algorithms *Data compression *

Рады Вас приветствовать. Прошел почти год с момента публикации последней статьи и мы готовы рассказать, что происходило с самим алгоритмом и как тут замешано дельта-кодирование.


image


Вступление


После выпуска статьи об улучшениях алгоритма Broo, мы столкнулись с преградой в улучшении уровня компрессии и производительности, а именно нельзя было улучшить уровень компрессии не ухудшив скорость распаковки и наоборот. Сразу сделаю оговорку, улучшения были сделаны без ущерба для других характеристик алгоритма, но эти изменения незначительные, дальше мы напишем об этих изменениях. Так вот, после, мы задумались, где мы можем применить накопленную экспертизу и знания в похожем направлении. И выбор пал на

Читать дальше →
Total votes 15: ↑14 and ↓1 +13
Views 8.4K
Comments 27

Топология и комплексный анализ для ничего не подозревающего разработчика игр: сжатие единичных 3D-векторов

Client optimization *Working with 3D-graphics *Game development *Mathematics *
Translation
image

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

  • процесс достаточно нагляден
  • он намного быстрее, чем обычная техника, выполняющая ту же задачу
  • он использует очень необычное свойство представления вещественных чисел в формате с плавающей запятой, что подразумевает, что...
  • он не работает в классическом анализе. Чтобы этот алгоритм работал в теории, нужно попасть в удивительный мир неклассической математики! И если уж это не разбудило ваше любопытство, то я уж и не знаю, что ещё поделать.

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

Немного о контексте (GPU)


Один из важных аспектов, на который стоит обращать внимание в разработке игр, а в более широком смысле — и в любой области с активным использованием графики — это пропускная способность GPU. Центральный процессор и GPU — отдельные физические устройства, и для обмена данными им требуется синхронизация. Если вы уже занимались параллельной обработкой, то знаете, что когда двум устройствам нужно синхронизироваться, это означает потерю значительного количества времени. Взаимодействие CPU-GPU в этом плане ничем не отличается, поэтому мы стремимся минимизировать передачу данных, как в количестве операций, так и в объёме передаваемых данных.
Читать дальше →
Total votes 31: ↑31 and ↓0 +31
Views 8.9K
Comments 12

Профессор Яаков Зив: автор метода сжатия данных без потерь

CloudMTS corporate blog Data compression *History of IT Popular science Biography of geeks

Яаков Зив разработал то, что мы привыкли называть термином lossless data compression — сжатие данных без потерь. Его работы стали основой для технологий, которыми мы пользуемся и по сей день, от GIF и PDF до ZIP и MP3. 

Должно быть, Зив сказочно богат? Увы, нет.

Читать далее
Total votes 68: ↑64 and ↓4 +60
Views 20K
Comments 24