Просто о SIF-е.

Данная статья – это популярное изложение сути разработанной технологии для тех, кому не хочется разбираться в патенте.

Для наглядного и понятного описания сути SIF-а, а также для понятного изложения различий между SIF-ом и другими технологиями сжатия воспользуемся “строительной” аллегорией.

Предположим, что нам надо написать инструкцию о том, как построить дом очень сложной формы, при этом в этом доме все стены кривые, а также нет ни одного одинакового окна, комнаты или двери. Конечно, такой дом будет мало походить на нормальное человеческое жилье ;), но в рамках этой задачи нам важны не архитектурные достоинства дома, а минимальный объем проектной документации.

• Например, можно построить весь дом из кирпичей, но тогда нам нужно описать расположение каждого из тех кирпичей, из которых мы сложим дом. В результате документация будет просто огромной ;).
• Другим подходом к решению этой задачи будет разбиение сложной формы исходного проекта на большое количество универсальных блоков. Эти блоки имеют различную форму, но в целом весь набор блоков подобран таким образом, что из них можно собрать стену практически любой формы, а сами они очень точно подогнаны друг к другу. С помощью таких блоков можно написать гораздо более компактное руководство по сборке дома, но для каждого участка стены придется решать сложную задачу – в каком конкретно порядке и какими конкретно блоками можно оптимально передать форму стены, затратив минимум текста. Таким образом, можно получить очень компактную документацию, но ее создание будет делом очень трудоемким и неоднозначным.
• Ну и наконец, можно применить чисто российский подход к проблеме – взять большое количество крупных блоков сложной формы, но не точно пригнанных друг к другу. Затем быстро составить из них описание подобия строящегося дома, а в тех местах, где блоки не плотно прилегают друг к другу, написать «для точного соответствия нужной форме доработать напильником» ;). Таким образом, и размер документации будет маленьким и написать ее можно будет быстро и просто.

Так вот, если считать вышеописанный дом аллегорией изображения, а написание документации – аллегорией процесса сжатия, то:

• Первый представленный способ – это стандартные неадаптивные алгоритмы сжатия, основанные на DCT или Wavelet-ах. Он всем хорош и быстр, только большие коэффициенты сжатия получить с его помощью не получится.
• Второй способ – это объектный метод представления изображения, а также разложение изображения на разные адаптивные базисы вроде Matching Pursuit или всяких «курвелетов». Проблема с этим подходом в том, что для разбиения изображения на объекты необходимо произвести очень большой объем вычислений. При этом непонятно, какие использовать алгоритмы, чтобы все всегда правильно работало. На разработку эффективных объектных методов сжатия изображения были потрачены и тратятся сейчас большие деньги, но воз пока и ныне там – ни одного практического кодека, эффективно разбивающего изображение на объекты сделано не было.
• Ну а последний метод собственно и передает суть SIF-а. Из-за того, что нам не надо заботиться о точной подгонке блоков друг к другу, сжатие изображений можно сделать очень быстрым – практически с такой же скоростью, что и в неадаптивных алгоритмах первого типа. При этом изображение разбивается на набор стандартных элементов, состоящих из описания базовой “грубой” формы блока, а также из описания методики “доработки напильником” этого блока в конкретном изображении . Подобный элемент в патенте назван “паттерном передискретизации” (resampling pattern), а я для простоты называю их графическими примитивами, хотя по сути это никакие не графические примитивы, а невесть что ;).

Основными задачами SIF проекта было создание практичных, быстрых и универсальных алгоритмов для разбиения изображения на графические примитивы и для синтеза его обратно с получением качественного изображения. Обе эти задачи были успешно решены. Причем алгоритм синтеза оказался настолько универсальным, что позволяет сшивать без швов и дополнительной постфильтрации графические примитивы, полученные из межкадровой разницы, с графическими примитивами, полученными прямо из текущего кадра, чего никакой алгоритм вроде Matching Pursuit никогда сделать не сможет. Кстати, именно отсутствие способа совмещения в одном кадре участков, закодированных прямым и межкадровым способом, делает неконкурентоспособными новые эффективные алгоритмы сжатия изображения в задачах сжатия видео – за исключением SIF-а конечно ;).

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

Сам класс SIF-подобных алгоритмов очень обширен и в зависимости от числа используемых графических примитивов конкретная реализация SIF-а может приближаться либо к Wavelet-подобным кодекам, либо к чисто объектным алгоритмам. При этом можно приблизительно приравнять реализацию SIF-а с тремя графическими примитивами к неадаптивному Wavelet-преобразованию, использующему квантование в виде вложенного нульдерева. То есть, трехэлементное SIF-преобразование сжимает чуть хуже чем JPEG2000 где применен более качественный битплановый квантователь. При этом текущий движок сжатия использует всего семь графических примитивов, что позволяет получать достаточно высокую, но не рекордную эффективность сжатия. Дело в том, что главная задача, решенная при создании текущего движка сжатия, была в отработке универсальных алгоритмов разбиения и синтеза изображения из графических примитивов, а увеличение числа графических примитивов приводило к увеличению объема кода и замедлению решению основной задачи.

Таким образом, текущий движок сжатия SIF-core6 – не более чем прототип реально рекордных движков следующей генерации. По моим оценкам, оптимальное число графических примитивов для SIF-образных алгоритмов находится в диапазоне от 32 до 128, а эффективность сжатия подобных движков должна быть гораздо выше, чем у текущего.

Еще одним путем увеличения эффективности сжатия у SIF-подобных алгоритмов является совершенствование правил подгонки графических примитивов в процессе сжатия. Разработанный универсальный алгоритм синтеза сводит задачу восстановления изображения к хорошо проработанной задаче эффективной интерполяции изображения с равномерно расположенными на нем отсчетами. Для решения этой задачи было разработано множество качественных адаптивных алгоритмов, существенно превосходящих тот алгоритм интерполяции, который используется в текущем ядре сжатия.

Еще одним крайне полезным свойством SIF-подобных алгоритмов является их крайняя гибкость и адаптивность. Дело в том, что SIF, как и объектные алгоритмы разбивает входное изображение на «геометрию» и «текстуры». При этом способ, которым получается ”геометрия”, на выход не передается. Это позволяет использовать чрезвычайно гибкие и адаптивные психовизуальные модели. На практике имеется возможность установить свой порог сжатия для любого из графических примитивов, на которые разбивается изображение, при практической бесплатности такой психовизуалки для сжатия – т.к. никаких дополнительных данных в сжатое изображение не передается. Для текущего движка сжатия минимальная возможная зона адаптивности это 2 на 2 пиксела! При этом психовизуалка напрямую встроена в движок разбиения изображения на графические примитивы, поэтому она еще и практически бесплатна с точки зрения вычислительной сложности алгоритма. Собственно, поэтому в SIF-е возможна реализация таких псховизуальных моделей, которые невозможно реализовать ни в одном другом алгоритме сжатия, что и демонстрируется в текущем видеокодеке.

Таким образом, по сумме полезных свойств именно SIF-подобные алгоритмы являются наиболее перспективными для создания видеокодеков следующего поколения.