JPEG2000

4.4.1 Общая характеристика стандарта и основные принципы сжатия

Отправной точкой для стандарта JPEG2000 стало предложение М. Болиека 1996 года. Разработанный Болиеком алгоритм должен был стать основой нового стандарта сжатия изображений без потерь JPEG-LS, но был отвергнут в пользу более перспективного алгоритма LOCO-I. Алгоритм Болиека, тем не менее, обладал рядом очень привлекательных возможностей, что послужило причиной создания нового стандарта JPEG2000.

На данный момент документация стандарта представлена двумя частями (в будущем планируются дополнительные разделы).

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

Разделение стандарта на основную и дополнительную часть лучше всего иллюстрируется на примере алгоритмов квантования. Сжатие по стандарту JPEG2000 основано на ставшем уже классическим алгоритме пирамидального вейвлет-преобразования. Обработка вейвлет-коэффициентов осуществляется методом контекстно-зависимого бит-ориентированного арифметического кодирования.

Первоначально изображение подвергается чередующимся последовательностям вертикальных и горизонтальных одномерных вэйвлет преобразований. Сначала преобразуются все строки, а затем все столбцы. На следующем этапе левая верхняя четверть матрицы получившейся в результате предыдущего преобразования опять преобразуется (сначала все строки, затем все столбцы). И так далее. Количество этапов соответствует количеству уровней вейвлет-декомпозиции. В результате преобразования мы получаем множество прямоугольных диапазонов вейвлет-коэффициентов, которые принято называть частотными диапазонами, так как они содержат информацию о том, как ведет себя исходный двухмерный сигнал (изображение) при разном разрешении (то есть набор коэффициентов при разной частоте). Для преобразования могут использоваться различные вейвлет-фильтры. Обязательная часть стандарта предписывает использование только двух фильтров: обратимый.5/3.. для сжатия без потерь и необратимый.9/3.. для сжатия с потерями (оба фильтра являются классическими вейвлет-фильтрами). Расширение допускает любые другие фильтры.

Представление информации, полученное в результате вейвлет-преобразования, очень удобно тем, что оно обеспечивает возможность получения приблизительных копий изображения без осуществления полного обратного преобразования. Обратное преобразование осуществляется в порядке, обратном порядку прямого преобразования.

 

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

 

Для получения приблизительной копии изображения достаточно декодировать всего лишь часть информации, а затем произвести частичное обратное преобразование. Таким образом, формат хранения изображения обеспечивает масштабируемость как по разрешению, так и по качеству.

Другим важным преимуществом нового стандарта является возможность доступа к отдельным элементам изображения без полного декодирования его представления. Обеспечивается такая возможность двумя факторами. Во-первых, разбиением исходного изображения на непересекающиеся области (тайлы), которые кодируются как отдельные изображения. Во-вторых, представлением кода отдельного тайла в виде частей (слоев), каждая из которых является суммарным кодом коэффициентов, соответствующих некоторой его (тайла) области (отметим, что слои в свою очередь делятся на так называемые пакеты, содержащие код блоков коэффициентов на разных уровнях декомпозиции). Для того, чтобы декодировать какую-либо область изображения достаточно определить, каким тайлам она принадлежит и какие слои, относящиеся к этим тайлам содержат код блоков коэффициентов, необходимых для восстановления требуемой области. Безусловно, «удобное» представление изображения не может быть выгодным с точки зрения эффективности сжатия. Действительно, с уменьшением размера структурных элементов (тайлов, областей тайлов, образующих слои и др.) эффективность сжатия несколько снижается. Стандарт в данном случае оставляет нам выбор: с одной стороны, мы имеем возможность получать информационные представления, позволяющие достаточно быстро извлекать и редактировать части изображения, с другой стороны, стандарт не препятствует созданию информационных представлений, эффективных по объему.

Для обеспечения помехоустойчивости информационного представления и удобства доступа к информации в стандарте JPEG2000 предусмотрена система маркеров и маркерных сегментов. Маркеры играют роль разграничителей внутри информационного потока; маркерные сегменты содержат в себе параметры фрагментов информации ограниченных маркерами. Данные, начинающиеся с маркера, как правило, могут быть корректно проинтерпретированы без какой-либо дополнительной информации (это, естественно, не означает возможность восстановления целого по фрагментам), что обеспечивает возможность частичного восстановления изображения, представление которого было повреждено. Введение элементов помехоустойчивости дает зеленый свет использованию стандарта во всевозможных телекоммуникационных приложениях.

В JPEG2000 реализовано:

· Кодирование на низких скоростях. Существующие стандарты великолепно работают на средних и высоких битовых скоростях, но при низких - искажение изображений становится недопустимым.

· Сжатие без потерь и сжатие с потерями. Ни один из существующих стандартов не предполагает сжатие без потерь и сжатие с потерями в одном потоке данных.

· Обработка больших по объему изображений. На текущий момент, алгоритм сжатия обычного JPEG не позволяет обрабатывать изображения, большие 64К, без их деления на куски.

· Единая архитектура декомпрессии. Существующий стандарт JPEG имеет как минимум 44 модели, которые не поддерживаются большинством декодеров.

· Минимальные искажения при передаче данных с некоторыми помехами. Существующий стандарт JPEG имеет такую особенность, что изображение довольно значительно страдает даже при небольшом числе ошибочно переданных битов.

· Эффективная работа с искусственными изображениями (сгенерированными компьютерами). Предыдущий формат великолепно позволяет обрабатывать естественные изображения, но плохо обеспечивает кодирование искусственных.

· Эффективная обработка составных документов. Обычный, JPEG редко используется для работы с составными документами из-за его слабой эффективности при наличии текстовых элементов в изображении.

Основными недостатками стандарта являются:

· Алгоритм JPEG 2000 неэффективен по времени выполнения, так как входящие в него вейвлет-преобразование и побитовая обработка коэффициентов требуют больших временных затрат. Время выполнения можно сократить для одного частного случая, когда сжимаются снимки природного происхождения и зафиксирована степень сжатия. В этом случае существует устойчивая связь между кодированием низких и высоких частот, что позволило оптимизировать длину R-D кривых. В среднем это дает экономию времени 20%.

 

4.4.2 Информационные потери в jpeg2000 на разных этапах обработки

· Предварительная обработка. Изображение, как правило, представляет собой набор неотрицательных целых чисел. На этапе предварительной обработки из него вычитают среднее. Кроме того, если изображение большого размера, то оно может быть разбито на части. Тогда каждая часть сжимается отдельно, а для предотвращения появления заметных линий на стыке восстановленных частей применяются специальные меры. Для преобразования изображения из стандартного цветового представления RGB в яркостно-цветовое представление YCrCb стандартом предусмотрены две процедуры: обратимая и необратимая. Необратимая процедура в точности повторяет классическое преобразование RGB-> YCrCb, которое использовалось, например, в старом стандарте JPEG. Обратимая процедура представляет собой достаточно грубое приближение к классической необратимой процедуре.

 

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

 

· Вейвлет-преобразование. В первой части определены два вейвлет-фильтра - фильтр Добеши для сжатия с потерями и тоже биортогональный фильтр с целочисленными коэффициентами для сжатия без потерь. Во второй части стандарта разрешается применение любых фильтров, а также не только октавополосное разбиение, но и произвольное (вейвлет-пакеты и т.д.) В стандарте определено, что вейвлет-преобразование осуществляется не путем свертки с импульсными характеристиками фильтров, а на основе алгоритма, известного как лифтинговая схема. Обязательная часть стандарта предписывает использование только двух фильтров: обратимый.5/3.. для сжатия без потерь и необратимый.9/3.. для сжатия с потерями (оба фильтра являются классическими). Фильтр представляет собой небольшое «окно». Значения яркости и цветности попавших в него пикселей умножаются на заданный набор коэффициентов, а полученные значения суммируются, и «окно» сдвигается для расчета следующего значения. Каждый канал проходит фильтрацию низкочастотным и высокочастотным фильтрами отдельно по строкам и по рядам, в результате чего после первого прохода в каждой части формируются четыре более мелких изображения (subband). Все они несут информацию об исходном изображении, но их информативность сильно отличается. Например, изображение, полученное после низкочастотной фильтрации по строкам и рядам (вверху слева), несет наибольшее количество информации, а полученное после высокочастотной — минимальное. Информативность у изображений, полученных после НЧ-фильтрации строк и ВЧ для столбцов (и наоборот), средняя. Наиболее информативное изображение опять подвергается фильтрации, а полученные составляющие, как и при jpeg-компрессии, квантуются. Так происходит несколько раз: для сжатия без потерь цикл обычно повторяется 3 раза, с потерями — разумным компромиссом между размером, качеством и скоростью декомпрессии считается 10 итераций. В результате получается одно маленькое изображение и набор картинок с мелкими деталями, последовательно и с определенной точностью восстанавливающих его до нормального размера.

· Квантование. В первой части стандарта определен равномерный квантователь с мертвой зоной, описанный, например, по вейвлетам. В случае сжатия без потерь размер шага квантователя равен 1, иначе он выбирается в зависимости от требуемой степени сжатия. Шаг квантователя постоянен в пределах субполосы. Во второй части стандарта определена возможноть применения решетчатого квантователя - TCQ. Именно на этапе квантования возникают основные информационные потери, и именно за счет квантования возможно существенное уменьшение объема представления изображения. (в квантовании нет необходимости, если производится сжатие без потерь.)

· Энтропийное кодирование. Применяется адаптивный арифметический кодер (а в JPEG был кодер Хаффмана). Ввиду патентных ограничений используется не QM-кодер разработки IBM, а чуть худший MQ-кодер, специально разработанный для JPEG2000.

Кодирование ведется не всего изображения в целом и даже не отдельных субполос, а более мелких объектов - кодируемых блоков (КБ).

Размер кодируемого блока может быть не более 4096 пикселов, высота не менее 4 пикселов. Такое разбиение хотя и снижает несколько коэффициент сжатия, но повышает устойчивость сжатого потока к ошибкам канала связи: ошибка испортит лишь небольшой блок. Кодирование блоков ведется в три этапа, битовыми плоскостями. Каждая битовая плоскость кодируется в три прохода. Существенной деталью, предусмотренной стандартом, является возможность пропуска кодовых проходов, что является еще одним источником повышения эффективности за счет информационных потерь. Использование методов кодирования, учитывающих структуру вейвлет - преобразования, может существенно повысить степень сжатия. Один из широко используемых методов такого типа - метод нуль - дерева (zero - tree compression). Он основан на предположении, что если некоторая область изображения не содержит нетривиальной информации на некотором уровне разрешения, то с большой вероятностью она не будет информативной и на более тонком уровне разрешения. Вейвлет - преобразование изображения можно хранить в виде дерева, корнем которого является сильно сглаженная версия оригинала, а ветви, представляющие отдельные блоки, обрываются на том уровне, где дальнейшая обработка не дает заметного уточнения. Такое дерево можно с успехом сжать обычными методами типа хаффменовского или арифметического кодирования, которые используются почти во всех алгоритмах сжатия.