2014-02-13
948
JPEG2000
Конечный шаг - кодирование Хаффмана
RunLength кодирование нулей (RLC)
Теперь у нас есть квантованный вектор с длинной последовательностью нулей. Мы можем использовать это, кодируя последовательные нули. ВАЖНО: Вы увидите позже почему, но здесь мы пропускаем кодировку первого коэффициента вектора (коэффициент DC), который закодирован по-другому. (Я представлю его кодирование позже в этом документе) Рассмотрим исходный 64 вектор как 63 вектор (это - 64 вектор без первого коэффициента)
Допустим, мы имеем 57,45,0,0,0,0,23,0,-30,-16,0,0,1,0,0,0,0,0,0, только 0,...,0
Здесь - как RLC JPEG сжатие сделано для этого примера:
(0,57); (0,45); (4,23); (1,-30); (0,-16); (2,1); EOB
Как Вы видите, мы кодируем для каждой величины, отличающейся от 0 количество последовательных ПРЕДШЕСТВУЮЩИХ нулей перед величиной, затем мы добавляем величину. Другое примечание: EOB - короткая форма для Конца Блока, это - специальная кодированная величина (маркер). Если мы достигли в позиции на векторе, от которого мы имеем до конца только нули вектора, мы выделим эту позицию с EOB и завершим сжатие RLC квантованного вектора.
|
|
|
Сначала ВАЖНОЕ примечание: Вместо хранения фактической величины, JPEG стандарт определяет, что мы храним минимальный размер в битах, в котором мы можем держать эту величину (это названо категория этой величины) и затем битно кодированное представление этой величины подобно этому:
Отправной точкой для стандарта JPEG2000 стало предложение М. Болиека 1996 года. Разработанный Болиеком алгоритм должен был стать основой нового стандарта сжатия изображений без потерь JPEG-LS, но был отвергнут в пользу более перспективного алгоритма LOCO-I. Алгоритм Болиека, тем не менее, обладал рядом очень привлекательных возможностей, что послужило причиной создания нового стандарта JPEG2000.
Объявление о начале разработки нового стандарта датируется мартом 1997 года. Традиционно был устроен конкурс алгоритмов сжатия, на котором проводилось численное и визуальное сравнение результатов работы различных программ. Программа-победитель (ею стала разработка аризонского университета, алгоритм WTCQ) была выбрана за основу первой версии стандарта. В ноябре 1998 года с подачи Д. Таубмана в стандарт было внесено существенное изменение. Таубман предложил решение, позволившее сделать стандарт существенно более гибким и менее требовательным к ресурсам вычислительной системы. Алгоритм Таубмнана (алгоритм EBCOT) в результате составил основу финальной версии стандарта. В процессе стандартизации было учтено большое количество различных предложений. Так как все они не могли составить новый стандарт, было принято решение часть из них внести в его базовый вариант, а часть рассматривать как дополнение. На данный момент документация стандарта представлена двумя частями (в будущем планируются дополнительные разделы). Первая описывает основные моменты, которые должны быть в обязательном порядке соблюдены в любой реализации стандарта. Вторая содержит расширения основной части стандарта, которые не являются обязательными. Данный подход выгоден тем, что, во-первых, учитывает большое количество различных предложений и обеспечивает гибкость, а во-вторых, позволяет получать достаточно непритязательные в плане вычислительных ресурсов реализации, совместимые со стандартом.
|
|
|
Разделение стандарта на основную и дополнительную часть лучше всего иллюстрируется на примере алгоритмов квантования. Предложение аризонского университета подразумевало использование сложного алгоритма квантования, получившего название квантование с сетчатой геометрией. Фактически была предложена быстрая реализация векторного квантования. Как известно, векторное квантование обладает большей эффективностью по сравнению со скалярным квантованием, однако, в то же время, оно является существенно менее производительным. В предложенном алгоритме WTCQ векторное квантование реализовано на базе конечного набора скалярных квантователей, выбор которых (для осуществления квантования) производится в соответствии с возможными направлениями обхода заданного графа (сети). Направление обхода одновременно соответствует младшим разрядам квантованных значений, полученных с использованием предыдущих квантователей (выбранных на предыдущем этапе). Путем перебора возможных путей внутри графа можно найти более или менее эффективные способы квантования произвольной по длине последовательности величин. Несмотря на то, что подобный алгоритм весьма прост, его сложность, все же, не идет нив какое сравнение со сложностью алгоритма обычного равномерного квантования. Как следствие, последний (используется равномерный квантователь с мертвой зоной вблизи нуля)является обязательной частью стандарта, а первый (квантование с сетчатой геометрией)представляет собой расширение стандарта и является лишь его опцией. Сжатие по стандарту JPEG2000 основано на ставшем уже классическим алгоритме пирамидального вейвлет-преобразования. Обработка вейвлет-коэффициентов осуществляется методом контекстно-зависимого бит-ориентированного арифметического кодирования.
Первоначально изображение подвергается чередующимся последовательностям вертикальных и горизонтальных одномерных вэйвлет преобразований. Сначала преобразуются все строки, а затем все столбцы. На следующем этапе левая верхняя четверть матрицы получившейся в результате предыдущего преобразования опять преобразуется (сначала все строки, затем все столбцы). И так далее. Количество этапов соответствует количеству уровней вейвлет-декомпозиции. В результате преобразования мы получаем множество прямоугольных диапазонов вейвлет-коэффициентов, которые принято называть частотными диапазонами, так как они содержат информацию о том, как ведет себя исходный двухмерный сигнал (изображение) при разном разрешении (то есть набор коэффициентов при разной частоте). Для преобразования могут использоваться различные вейвлет-фильтры. Обязательная часть стандарта предписывает использование только двух фильтров: обратимый.5/3.. для сжатия без потерь и необратимый.9/3.. для сжатия с потерями (оба фильтра являются классическими вейвлет-фильтрами). Расширение допускает любые другие фильтры. Подразумевается, что для реализации преобразования используется удобная с практической точки зрения лифтинг-схема. После преобразования осуществляется квантование коэффициентов. Именно на этапе квантования возникают основные информационные потери, и именно за счет квантования возможно существенное уменьшение объема представления изображения. (Естественно, в квантовании нет необходимости, если производится сжатие без потерь.) Как уже было сказано, квантование может быть либо равномерным скалярным, либо каким-либо другим (например, векторным). В случае использования равномерного скалярного квантования квант-параметр может меняться в зависимости от квантуемого диапазона. Этап арифметического кодирования является завершающим этапом кодирования. Диапазоны коэффициентов разбиваются на прямоугольные кодовые блоки (как правило, 32x32 или64x64). Каждый из блоков кодируется независимо. Это означает, что состояние арифметического кодера сбрасывается перед кодированием очередного кодового блока. В процессе кодирования коэффициенты в блоке виртуально представляются в виде битовых плоскостей. Одну из таких плоскостей составляют знаки коэффициентов; остальные плоскости соответствуют различным разрядам величин коэффициентов (положение бита в плоскости соответствует положению коэффициента в блоке). Кодирование коэффициентов сводится к кодированию битов, составляющих эти коэффициенты. Таким образом, арифметическое кодирование является бит-ориентированным.
|
|
|
Арифметическое кодирование основано на контекстно-зависимой модели. Контекст формируется как функция от значений битов, окружающих кодируемый бит. Кодирование осуществляется по плоскостям: сначала кодируется плоскость, соответствующая старшему разряду коэффициентов, затем следующая по убыванию, и т.д. Во время кодирования каждому коэффициенту в кодируемом блоке ставится в соответствие параметр значимость. Коэффициент называется значимым, если в уже закодированных на данный момент битовых плоскостях, присутствует хотя бы один ненулевой разряд данного коэффициента. Каждая битовая плоскость кодируется в три прохода. Во время первого кодового прохода осуществляется распространение информации о значимости коэффициентов. Для каждого бита плоскости, если соответствующий коэффициент еще не является значимым, и если хоть один соседний коэффициент уже является значимым, осуществляется кодирование факта значимости для текущего коэффициента, то есть фактически осуществляется кодирование значения данного бита текущей кодируемой плоскости. Если кодируемый бит оказался ненулевым, сразу после его обработки кодируется соответствующий бит битовой плоскости знаков коэффициентов(кодирование знака). Во время второго кодового прохода кодируются все биты, соответствующие значимым на данный момент коэффициентам и не обрабатывавшиеся во время первого прохода. В отличие от предыдущего кодового прохода, когда решение о кодировании принималось на основе информации о значимости соседних коэффициентов, во время данного прохода биты кодируются в обязательном порядке. Цель третьего кодового прохода, обработать те биты, которые не были обработаны во время первого и второго проходов. Во время третьего прохода арифметическое кодирование применяется совместно с групповым кодированием. Существенной деталью, предусмотренной стандартом, является возможность пропуска кодовых проходов, что является еще одним источником повышения эффективности за счет информационных потерь (первым, наиболее явным источником является квантование). Данная возможность активно используется для осуществления контроля над скоростью генерации кода.
|
|
|
Представление информации, полученное в результате вейвлет-преобразования, очень удобно тем, что оно обеспечивает возможность получения приблизительных копий изображения без осуществления полного обратного преобразования. Обратное преобразование осуществляется в порядке, обратном порядку прямого преобразования. Производя ограниченное число обратных декомпозиций (объединение частотных диапазонов), полагая, что все не вовлеченные в преобразование частотные диапазоны содержат исключительно нулевые элементы, мы легко можем получить либо копию изображения в уменьшенном масштабе, либо исходное изображение, но в более низком качестве по сравнению с изображением, полученным в результате полного обратного преобразования. Учитывая тот факт, что блоки вейвлет-коэффициентов кодируются независимо друг от друга, мы получаем возможность частичного декодирования не только на уровне преобразования, но и на уровне интерпретации кода. Для получения приблизительной копии изображения достаточно декодировать всего лишь часть информации, а затем произвести частичное обратное преобразование. Таким образом, формат хранения изображения обеспечивает масштабируемость как по разрешению, так и по качеству.
Другим важным преимуществом нового стандарта является возможность доступа к отдельным элементам изображения без полного декодирования его представления. Обеспечивается такая возможность, во-первых, разбиением исходного изображения на непересекающиеся области (тайлы), которые кодируются как отдельные изображения, а во-вторых, представлением кода отдельного тайла в виде частей (слоев), каждая из которых является суммарным кодом коэффициентов, соответствующих некоторой его (тайла) области (отметим, что слои в свою очередь делятся на так называемые пакеты, содержащие код блоков коэффициентов на разных уровнях декомпозиции). Для того, чтобы декодировать какую-либо область изображения достаточно определить, каким тайлам она принадлежит и какие слои, относящиеся к этим тайлам содержат код блоков коэффициентов, необходимых для восстановления требуемой области. Безусловно, «удобное» представление изображения не может быть выгодным с точки зрения эффективности сжатия. Действительно, с уменьшением размера структурных элементов (тайлов, областей тайлов, образующих слои и др.) эффективность сжатия несколько снижается. Стандарт в данном случае оставляет нам выбор: с одной стороны, мы имеем возможность получать информационные представления, позволяющие достаточно быстро извлекать и редактировать части изображения, с другой стороны, стандарт не препятствует созданию информационных представлений, эффективных по объему.
Все, что было сказано выше, в действительности относится не совсем к сжатию изображений. Речь шла всего лишь о сжатии матриц. Реальные изображения подчас являются более сложными объектами. Как правило, изображение включает в себя сразу несколько компонентов. Чаще всего, оно состоит из трех цветовых компонентов: красного, зеленого и синего. Так как каждый компонент в отдельности представляет собой матрицу, для того, чтобы закодировать изображение целиком, нам необходимо закодировать не одну, а три матрицы. Такой подход, как показывает практика, приемлем, но не является самым удачным. Большей эффективности сжатия можно добиться в случае, когда кодируемые компоненты представлены в яркостно-цветовой форме. Для преобразования изображения из стандартного цветового представления RGB в яркостно-цветовое представление YCrCb стандартом предусмотрены две процедуры: обратимая и необратимая. Необратимая процедура в точности повторяет классическое преобразование RGB-> YCrCb, которое использовалось, например, в старом стандарте JPEG. Обратимая процедура представляет собой достаточно грубое приближение к классической необратимой процедуре. Как следует из названия, данное преобразование не ведет к потере цветовой информации, и может применяться в тех случаях, когда задействуется режим сжатия без потерь. Для обеспечения помехоустойчивости информационного представления и удобства доступа к информации в стандарте JPEG2000 предусмотрена система маркеров и маркерных сегментов. Маркеры играют роль разграничителей внутри информационного потока; маркерные сегменты содержат в себе параметры фрагментов информации ограниченных маркерами. Данные, начинающиеся с маркера, как правило, могут быть корректно проинтерпретированы без какой-либо дополнительной информации (это, естественно, не означает возможность восстановления целого по фрагментам), что обеспечивает возможность частичного восстановления изображения, представление которого было повреждено. Введение элементов помехоустойчивости дает зеленый свет использованию стандарта во всевозможных телекоммуникационных приложениях.
В JPEG2000 реализовано:
· Кодирование на низких скоростях. Существующие стандарты великолепно работают на средних и высоких битовых скоростях, но при низких - искажение изображений становится недопустимым.
· Сжатие без потерь и сжатие с потерями. Ни один из существующих стандартов не предполагает сжатие без потерь и сжатие с потерями в одном потоке данных.
· Обработка больших по объему изображений. На текущий момент, алгоритм сжатия обычного JPEG не позволяет обрабатывать изображения, большие 64К, без их деления на куски.
· Единая архитектура декомпрессии. Существующий стандарт JPEG имеет как минимум 44 модели, которые не поддерживаются большинством декодеров.
· Минимальные искажения при передаче данных с некоторыми помехами. Существующий стандарт JPEG имеет такую особенность, что изображение довольно значительно страдает даже при небольшом числе ошибочно переданных битов.
· Эффективная работа с искусственными изображениями (сгенерированными компьютерами). Предыдущий формат великолепно позволяет обрабатывать естественные изображения, но плохо обеспечивает кодирование искусственных.
· Эффективная обработка составных документов. Обычный JPEG редко используется для работы с составными документами из-за его слабой эффективности при наличии текстовых элементов в изображении.
Основными недостатками стандарта являются:
· Алгоритм JPEG 2000 неэффективен по времени выполнения, так как входящие в него вейвлет-преобразование и побитовая обработка коэффициентов требуют больших временных затрат. Время выполнения можно сократить для одного частного случая, когда сжимаются снимки природного происхождения и зафиксирована степень сжатия. В этом случае существует устойчивая связь между кодированием низких и высоких частот, что позволило оптимизировать длину R-D кривых. В среднем это дает экономию времени 20%.
Преимущество JPEG 2000 над JPEG в качестве алгоритма сжатия в некоторых случаях нельзя однозначно установить, используя показатель среднеквадратической ошибки (MSE). Для космических снимков предложен новый метод – метод тестирования на мирах.
