Обратимая двумерная предварительная и постфильтрация для перекрывающегося биортогонального преобразования

Изобретение относится к сжатию цифровых мультимедийных данных с использованием перекрывающегося преобразования. Техническим результатом является увеличение обратимого сжатия данных без потерь. Для достижения технического результата реализован способ кодирования двумерных цифровых мультимедийных данных, содержащий этапы, на которых вводят двумерные цифровые мультимедийные данные и сжимают двумерные цифровые мультимедийные данные в сжатый поток, используя перекрывающееся преобразование, при этом сжатие включает в себя разделение двумерных цифровых мультимедийных данных на макроблоки, применение оператора обратимого двумерного перекрытия к первому массиву цифровых мультимедийных данных, который смещен в обоих направлениях, в горизонтальном и вертикальном, от границ макроблоков, и применяют обратимое двумерное блочное преобразование ко второму массиву цифровых мультимедийных данных, который выровнен с границами макроблоков, при этом применение оператора обратимого двумерного перекрытия и обратимого двумерного блочного преобразования совместно осуществляет перекрывающееся преобразование двумерных цифровых мультимедийных данных. 6 н. и 25 з.п. ф-лы, 47 ил.

 

Информация о связанной заявке

Эта заявка является частичным продолжением патентной заявки США № 11/015148 на имя Tu et al., озаглавленной "Reversible Overlap Operator For Efficient Lossless Data Compression", от 17 декабря 2004 года, включенной в данный документ посредством ссылки.

Область техники

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

Уровень техники

Перекрывающиеся преобразования

Перекрывающееся преобразование является эффективным методом обработки сигналов, который используется при сжатии данных. См., например, H.S. Malvar, "Signal Processing with Lapped Transforms", Boston, MA: Artech House, 1992 г. Однако до настоящего времени эффективные перекрывающиеся преобразования с линейной фазой не были сформулированы и не применялись для сжатия (обратимого) данных без потерь.

Как описано более подробно ниже, известно, что перекрывающееся преобразование может быть сформулировано как предварительная фильтрация, за которой следует преобразование данных (и его инверсия как обратное преобразование данных, за которым следует постфильтрация). См., например, H.S. Malvar, "A pre- and post-filtering technique for the reduction of blocking effects", Proc. Picture Coding Symposium, Стокгольм, Швеция, июнь 1987 г.; и T.D. Tran, J. Liang, C. Tu, "Lapped Transform via Time-Domain Pre- and Post-Filtering", IEEE Trans. on Signal Processing, том 51, номер 6, июнь 2003 г. Преобразование данных без потерь может быть использовано в данной формулировке для достижения хорошей степени обратимости. До настоящего времени считалось, что только определенное ограниченное множество предварительных и постфильтров может быть выбрано для обеспечения обратимости. Этот ограниченный набор имеет существенные ограничения по производительности сжатия (скорость в зависимости от искажения - R-D). В работе W. Dai, T. Tran, "Regularity-constrained pre- and post-filtering for block DCT-based systems", IEEE Trans. on Signal Processing, том 51, стр. 2568-2581, октябрь 2003 г., представлена структура, в которой большинство элементов являются обратимыми и которая имеет хорошие свойства сжатия.

В сжатии аудиосигналов был введен ряд структур для обратимых перекрывающихся преобразований (см., например, R. Geiger, J. Herre, J. Koller и K. Brandenburg, "IntMDCT - A link between perceptual and lossless audio coding", Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, Орландо, штат Флорида, май 2002 г.; и J. Li, "Reversible FFT and MDCT viva matrix lifting", Proc. IEEE Int. Conf. on Acoustics, Speech, and Signal Processing, Монреаль, Канада, май 2004 г.) Однако эти структуры применимы только к модулированному перекрывающемуся преобразованию (MLT), также известному как модифицированное дискретное косинусное преобразование (MDCT), базисные функции которого являются ортогональными и несимметричными (т.е. базисные функции с нелинейной фазой). Эти преобразования не применимы к приложениям сжатия данных, в которых требуются функции линейной фазы (симметричные), таким как цифровое сжатие изображений.

Для сжатия изображений одним из наилучших методов преобразования с точки зрения производительности R-D является перекрывающееся биортогональное преобразование (LBT) (см. S. Malvar, "Biorthogonal and nonuniform lapped transforms for transform coding with reduced blocking and ringing artifacts", IEEE Trans. on Signal Processing, том 46, стр. 1043-1053, апрель 1998 г.) В отличие от MLT базисные функции LBT являются симметричными и неточно ортогональными (в LBT базисные функции анализа являются ортогональными базисным функциям синтеза, отсюда термин "биортогональные"). LBT успешно использовались в приложениях сжатия изображений, но они до сих пор не использовались в сжатии изображений без потерь, поскольку целые обратимые структуры были неизвестны.

Обзор основанного на блочном преобразовании кодирования

Кодирование с преобразованием представляет собой метод сжатия, используемый во многих системах сжатия аудио, изображений и видео. Несжатое цифровое изображение или видео в типовом случае представляется или принимается в виде выборок элементов изображений или цветов в местах на изображении или видеокадре, упорядоченных в двумерной (2D) сетке. Это определяется как представление изображения или видео в пространственной области. Например, типичный формат для изображений состоит из потока 24-битных выборок элементов цветных изображений, упорядоченных в сетке. Каждая выборка является числом, представляющим цветовые компоненты в местоположении пикселя в сетке в цветовом пространстве, таком как RGB или YIQ, помимо прочего. Различные системы изображений и видео могут использовать различные цветовые, пространственные и временные разрешения при дискретизации. Аналогичным образом, цифровое аудио в типовом случае представляется как дискретизированный по времени поток аудиосигналов. Например, типичный формат аудио состоит из потока 16-битных выборок по амплитуде аудиосигнала, взятых с постоянным интервалом времени.

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

Более конкретно, типичный основанный на блочном преобразовании кодек 100, показанный на фиг.1, делит пиксели несжатого цифрового изображения на двумерные блоки фиксированного размера (), при этом каждый блок, возможно, перекрывается с другими блоками. Линейное преобразование 120-121, которое выполняет анализ пространственных частот, применяется к каждому блоку, что преобразует разнесенные выборки в блоке в набор коэффициентов частот (или преобразования), обычно представляющих интенсивность цифрового сигнала в соответствующих полосах частот по блочному интервалу. Для сжатия коэффициенты преобразования могут быть селективно квантованы 130 (т.е. снижены по разрешению, например, посредством отбрасывания наименее значимых битов значений коэффициентов или иного отображения значений в числовом множестве с более высоким разрешением на меньшее разрешение), а также могут кодироваться 130 посредством энтропийного кодирования или кодирования переменной длины для получения сжатого потока данных. При декодировании коэффициенты преобразования подвергаются обратному преобразованию 170-171, чтобы приблизительно восстановить исходный выбираемый по цвету/пространству сигнал изображения/видео (восстановленные блоки ).

Блочное преобразование 120-121 может быть задано как математическая операция над вектором x размера N. Более часто операцией является линейное умножение, генерирующее выходной сигнал области преобразования , где M - матрица преобразования. Когда входные данные имеют произвольную длину, они сегментируются на N векторов определенной длины и блочное преобразование применяется к каждому сегменту. Для целей сжатия данных выбираются обратимые блочные преобразования. Другими словами, матрица M является обратимой. В случае нескольких измерений (например, для изображения и видео) блочные преобразования обычно реализуются как раздельные операции. Матричное умножение применяется раздельно по каждому измерению данных (т.е. и строк, и столбцов).

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

При декодировании в декодере 150 инверсия этих операций (декодированное/энтропийное декодирование 160 и обратное блочное преобразование 170-171) применяется на стороне декодера 150, как показано на фиг.1. При восстановлении данных обратная матрица M ^-1 (обратное преобразование 170-171) применяется в качестве множителя к данным области преобразования. При применении к данным области преобразования обратное преобразование приблизительно восстанавливает исходный цифровой мультимедийный сигнал временной области или пространственной области.

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

Многие системы сжатия изображений и видео, такие как MPEG и Windows Media, помимо прочих, используют преобразования на основе дискретного косинусного преобразования (DCT). DCT, как известно, имеет подходящие свойства энергетического сжатия, что приводит к практически оптимальному сжатию данных. В этих системах сжатия обратное DCT (IDCT) используется в контурах восстановления как в кодере, так и в декодере системы сжатия для восстановления отдельных блоков изображений. DCT описано в публикации N. Ahmed, T. Natarajan, K.R. Rao "Discrete Cosine Transform", IEEE Transactions on Computers, C-23 (январь 1974 г.), на стр. 90-93. Примерная реализация IDCT описана в"IEEE Standard Specification for the Implementations of 8×8 Inverse Discrete Cosine Transform", IEEE Std. 1180-1990, 6 декабря 1990 г.

При сжатии статического изображения (или внутренне закодированного кадра видеопоследовательности) самые распространенные стандарты, такие как MPEG-2, MPEG-4 и Windows Media, разбивают изображение на квадратные мозаики и применяют блочное преобразование к каждому элементу мозаики изображения. Коэффициенты преобразования в данном разделе (общеизвестном как блок) находятся под влиянием только компонентов необработанных данных в блоке. Необратимые операции или операции с потерями на стороне кодера, такие как квантование, служат причиной помех, появляющихся в декодированном изображении. Эти помехи являются независимыми для блоков и генерируют визуально раздражающий эффект, называемый эффектом блокирования. Аналогично для аудиоданных, когда неперекрывающиеся блоки независимо кодируются с преобразованием, ошибки квантования генерируют разрывы в сигнале на границах блоков при восстановлении аудиосигнала в декодере. Для аудио прослушивается эффект периодических щелчков.

Ряд методов используется для противодействия эффекту блокирования. Наиболее популярные среди них - это фильтр деблокирования, который сглаживает границы краев внутренних блоков, и пространственная экстраполяция, которая кодирует различия между необработанными входными данными и прогнозированием от краев соседних блоков. Эти методики имеют свои недостатки. Например, подход с использованием фильтра деблокирования - это "разомкнутый контур", т.е. процесс прямого преобразования не принимает во внимание тот факт, что деблокирование должно выполняться до восстановления на стороне декодера. Кроме того, оба эти метода характеризуются большим объемом вычислений.

Чтобы минимизировать эффект блокирования, могут быть использованы межблочные корреляции. Один способ достижения межблочной корреляции заключается в использовании перекрывающегося преобразования, как описано в публикации H. Malvar, "Signal Processing with Lapped Transforms", Artech House, Норвуд, штат Массачусетс, 1992 г. Перекрывающееся преобразование - это преобразование, входные данные которого распространяется, помимо элементов данных в текущем блоке, на несколько соседних элементов в соседних блоках. Аналогично, на стороне восстановления обратное преобразование влияет на все точки данных в текущем блоке, а также на несколько точек данных в соседних блоках.

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

Обзор перекрывающегося преобразования пространственной области

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

Фиг.2 показывает пример традиционного перекрывающегося преобразования пространственной области. В показанном примере перекрытие составляет два пикселя, и два пикселя, каждый из двух показанных соседних блоков, предварительно обрабатываются на стадии 210 предварительной обработки. Два предварительно обработанных выходных результата отправляются каждому из блоков для кодирования на основе блочного преобразования кодеком 100, как показано на фиг.1. Инверсия стадии предварительной обработки применяется на стадии постобработки 220 после декодирования. При разумном выборе предварительной обработки и блочного преобразования может быть реализован широкий диапазон перекрывающихся преобразований.

Ключевое преимущество реализации в пространственной области перекрывающегося преобразования состоит в том, что используемый основанный на блочном преобразовании кодек может быть модернизирован с помощью стадии предварительной или постобработки для обеспечения преимуществ перекрывающегося преобразования, т.е. уменьшения эффекта блокирования и лучшего сжатия с использованием существующей структуры кодека. Предварительная обработка 210 и постобработка могут быть представлены как матричное умножение, как показано на фиг.3. Традиционно матрицы предварительной и постобработки являются инверсиями друг друга, т.е. перемножение матрицы предварительной обработки (P _f) и инверсной матрицы или матрицы постобработки (P _i) дает единичную матрицу I.

Определения

В общем, длина N преобразования - это число коэффициентов преобразования в конкретном блоке преобразования.

Основа K преобразования - это число точек входных данных, которые оказывают влияние на коэффициенты блока преобразования. Аналогичным образом, это число точек выходных данных, на которые оказывает влияние каждый коэффициент преобразования посредством процесса обратного преобразования.

Для типичных блочных преобразований, таких как дискретное косинусное преобразование (DCT), длина и основа идентичны. Тем не менее, перекрывающиеся преобразования (LT) являются важным классом преобразований, для которых основа K больше, чем длина N. Запись K × N используется для обозначения основы и длины перекрывающегося преобразования. (Преобразования, для которых K < N, являются обширными и поэтому не используются в сжатии данных).

В качестве примера 300 LT 310 6×4, показанное на фиг.3, является преобразованием с шестью входами и четырьмя выходами. Поскольку преобразование является обратимым, два входа совместно используются соседними блоками преобразования. Обратное перекрывающееся преобразование (ILT) 320 генерирует шесть выходных результатов из своих четырех входов. Выходные точки данных рядом с границей блоков (в данном случае одна точка в каждом конце блока) восстанавливаются посредством суммирования соответствующих откликов от двух соседних блоков обратного преобразования.

Ограничения на перекрывающиеся преобразования, используемые в системах сжатия

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

Сущность изобретения

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

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

Эффективное перекрывающееся преобразование реализуется с помощью предварительных и постфильтров, которые определяются в данном документе как "операторы перекрытия". Эта реализация обратимая, хотя очень эффективная по R-D. Среди других приложений эти новые операторы перекрытия позволяют реализовать обратимые LBT, которые могут быть использованы для сжатия изображений без потерь. Предварительные и постфильтры используют обратимые операции. Дополнительно описанные операторы перекрытия включают в себя упрощения для обеспечения вычислительной эффективности.

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

Типичным применением является одномерное перекрывающееся преобразование 8×4, реализованное с использованием вычислительно эффективных аппроксимаций операторов обратимого перекрытия.

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

1) трудность или практически невозможность получения нормализованного предварительного/постфильтра для эффективного сжатия данных,

2) высокая степень сложности, если такое приближение может быть достигнуто, и

3) неточность вследствие нескольких этапов фильтрация/поднятие при реализации этого приближения.

Альтернативная реализация двумерного перекрывающегося преобразования, описанная в данном документе, достигает более высокую вычислительную эффективность, чем подход раздельного горизонтального и вертикального применения оператора одномерного перекрытия. Эта альтернативная реализация разделяет оператор одномерного перекрытия на две стадии и перемежает стадии горизонтального и вертикального применения оператора перекрытия. В рамках каждой стадии операция нормализованного масштабирования, реализованная на этапах поднятия, может быть применена к более ограниченным подмножества блоков данных (например, подмножествам 2×2 или сигнальным парам блока данных 4×4), имея ввиду компенсацию "перекрестных членов" в двумерной структуре с перемежением. Это приводит к эффективному масштабно-инвариантному двумерному предварительному/постфильтру.

Двумерный предварительный/постфильтр может быть объединен с обратимым преобразованием, например эффективным масштабно-инвариантным обратимым двумерным преобразованием, описанным в патентной заявке США 11/015707 на имя Srinivasan, озаглавленной "Reversible Transform For Lossy And Lossless 2-D Data Compression", от 17 декабря 2004 года. Объединенный предварительный/пост-фильтр и преобразование формируют перекрывающееся преобразование, которое может быть использовано для точного и эффективного в вычислительном отношении сжатия изображений и видео, как с потерями, так и без потерь.

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

Краткое описание чертежей

Фиг.1 - блок-схема традиционного основанного на блочном преобразовании кодека согласно предшествующему уровню техники.

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

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

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

Фиг.5 - блок-схема декодера, основанного на перекрывающемся преобразовании.

Фиг.6 - блок-схема, иллюстрирующая пару перекрывающегося преобразования и обратного перекрывающегося преобразования на одномерных данных с использованием операций предварительной и постфильтрации (или оператор обратимого перекрытия) совместно с блочным преобразованием.

Фиг.7 - сигнальный ориентированный граф, иллюстрирующий структуру предварительного или постфильтра линейной фазы для использования в качестве оператора обратимого перекрытия в перекрывающемся преобразовании по фиг.6.

Фиг.8 - сигнальный ориентированный граф масштабирования без потерь в виде четырех этапов поднятия для использования в операторе обратимого перекрытия.

Фиг.9 - сигнальный ориентированный граф масштабирования без потерь в виде пяти этапов поднятия для использования в операторе обратимого перекрытия.

Фиг.10 - сигнальный ориентированный граф каскадного 2-точечного масштабирования, применяемого к матрице большей размерности для реализации единичного детерминантного масштабирования без потерь.

Фиг.11 - сигнальный ориентированный граф оператора обратимого перекрытия (или предварительного/постфильтра), имеющего структуру, показанную на фиг.7, и использующего единичное детерминантное масштабирование без потерь по фиг.10.

Фиг.12 - блок-схема алгоритма работы оператора обратимого перекрытия по фиг.11.

Фиг.13 - сигнальный ориентированный граф, иллюстрирующий пример реализации обратимого перекрывающегося преобразования, использующего оператор обратимого перекрытия по фиг.11.

Фиг.14 - граф импульсной характеристики коэффициента постоянной составляющей примерного перекрывающегося преобразования по фиг.13.

Фиг.15 - схема, иллюстрирующая пиксели, используемые в качестве основы оператора двумерного перекрытия для блоков размером 4×4.

Фиг.16 - схема, иллюстрирующая пиксели, используемые в качестве основы оператора двумерного перекрытия для блоков размером 2×2.

Фиг.17 - блок-схема последовательности операции способа преобразования, применяемого на стороне кодера по фиг.4.

Фиг.18 - блок-схема последовательности операции способа преобразования, применяемого на стороне декодера по фиг.5.

Фиг.19 - сигнальный ориентированный граф, предоставляющий каноническое представление оператора одномерного обратимого преобразования, показанного на фиг.11.

Фиг.20 - сигнальный ориентированный граф, иллюстрирующий двумерный предварительный/постфильтр, реализованный посредством раздельного применения оператора одномерного обратимого преобразования по фиг.19 по горизонтали и по вертикали.

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

Фиг.22 - листинг программы на языке программирования C для реализации нормализованного оператора Адамара 2×2, который формирует часть двумерного предварительного/постфильтра по фиг.21.

Фиг.23 - схема, показывающая соответствие между точками данных, обрабатываемыми с помощью предварительного/постфильтра 2×2.

Фиг.24 - схема, иллюстрирующая точки данных блока данных 4×4, к которому применяется оператор Адамара 2×2 на первой стадии реализации двумерного предварительного/постфильтра 4×4 фиг.21.

Фиг.25 - листинг программы на языке программирования C для реализации прямого поворота, которое формирует часть двумерного предварительного фильтра фиг.21.

Фиг.26 - листинг программы на языке программирования C для реализации обратного поворота, которое формирует часть двумерного постфильтра фиг.21.

Фиг.27 - листинг программы на языке программирования C для реализации прямого 2-точечного поворота, которое формирует часть двумерного предварительного фильтра фиг.21.

Фиг.28 - листинг программы на языке программирования C для реализации обратного 2-точечного поворота, которое формирует часть двумерного постфильтра по фиг.21.

Фиг.29 - схема, иллюстрирующая точки данных блока данных 4×4, к которому применяются повороты по фиг.25-28 на другой стадии реализации двумерного предварительного/постфильтра 4×4 по фиг.21.

Фиг.30 - схема, иллюстрирующая точки данных блока данных 4×4, к которому применяются 2-точечные операции масштабирования на дополнительной стадии реализации двумерного предварительного/постфильтра 4×4 по фиг.21.

Фиг.31 - листинг программы на языке программирования C для реализации прямого масштабирования, которое формирует часть двумерного предварительного фильтра по фиг.21.

Фиг.32 - листинг программы на языке программирования C для реализации обратного масштабирования, которое формирует часть двумерного постфильтра по фиг.21.

Фиг.33 - листинг программы на языке программирования C для реализации двумерного предварительного фильтра 4×4 по фиг.21.

Фиг.34 - листинг программы на языке программирования C для реализации двумерного постфильтра 4×4 по фиг.21.

Фиг.35 - листинг программы на языке программирования C для реализации двумерного предварительного фильтра 2×2.

Фиг.36 - листинг программы на языке программирования C для реализации двумерного постфильтра 2×2.

Фиг.37 - листинг программы на языке программирования C для реализации одномерного 2-точечного предварительного фильтра для применения на краях изображений, имеющих недостаточное число точек данных для двумерного предварительного фильтра по фиг.35.

Фиг.38 - листинг программы на языке программирования C для реализации одномерного 2-точечного постфильтра для применения на краях изображений, имеющих недостаточное число точек данных для двумерного предварительного фильтра по фиг.36.

Фиг.39 - листинг программы на языке программирования C для реализации одномерного 4-точечного предварительного фильтра для применения на краях изображений, имеющих недостаточное число точек данных для двумерного предварительного фильтра по фиг.33.

Фиг.40 - листинг программы на языке программирования C для реализации одномерного 4-точечного постфильтра для применения на краях изображений, имеющих недостаточное число точек данных для двумерного предварительного фильтра по фиг.34.

Фиг.41 - листинг программы на языке программирования C для реализации прямого преобразования, используемого в сочетании с предварительным фильтром по фиг.21 для осуществления перекрывающегося преобразования в кодере по фиг.4.

Фиг.42 - листинг программы на языке программирования C для реализации преобразования, которое формирует часть прямого преобразования по фиг.41.

Фиг.43 - листинг программы на языке программирования C для реализации еще одного преобразования, которое формирует часть прямого преобразования по фиг.41.

Фиг.44 - листинг программы на языке программирования C для реализации прямого преобразования, используемого в сочетании с предварительным фильтром по фиг.21 для осуществления перекрывающегося преобразования в кодере по фиг.5.

Фиг.45 - листинг программы на языке программирования C для реализации преобразования, которое формирует часть обратного преобразования по фиг.44.

Фиг.46 - листинг программы на языке программирования C для реализации другого преобразования, которое формирует часть обратного преобразования по фиг.44.

Фиг.47 - блок-схема подходящей вычислительной среды для реализации основанного на блочном преобразовании кодека с помощью усовершенствованного перекрывающегося преобразования пространственной области по фиг.4 и 5.

Подробное описание изобретения

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

1. Кодер/декодер

На фиг.4 и 5 показана обобщенная диаграмма процессов, используемых в репрезентативном двумерном (2D) кодере 400 и декодере 500 данных, основанном на перекрывающемся преобразовании, использующем оператор обратимого перекрытия. Схемы представляют обобщенную или упрощенную иллюстрацию использования и применения данного оператора обратимого перекрытия в системе сжатия, содержащей кодер и декодер двумерных данных. В альтернативных кодерах, основанных на этом операторе обратимого перекрытия, для сжатия двумерных данных может быть использовано дополнительное или меньшее число процессов, чем проиллюстрировано в репрезентативном кодере и декодере. Например, некоторые кодеры/декодеры могут также включать в себя цветовое преобразование, форматы цветов, масштабируемое кодирование, кодирование без потерь, режимы макроблоков и т.д. Система сжатия (кодер и декодер) может предоставлять кодирование двумерных данных без потерь и/или с потерями, в зависимости от квантования, которое может быть основано на параметре квантования, варьирующемся от варианта без потерь до варианта с потерями.

Кодер 400 двумерных данных генерирует сжатый поток 420 битов, который является более компактным представлением (для типичного ввода) двумерных данных 410, представляемых в качестве входного сигнала кодеру. Например, входными двумерными данными могут являться изображение, кадр видеопоследовательности или другие данные, имеющие два измерения. Кодер двумерных данных разбивает (430) входные данные на макроблоки, которые имеют размер 16×16 пикселей в данном репрезентативном кодере. Кодер двумерных данных дополнительно разбивает каждый макроблок на блоки 432 размером 4×4. Оператор 440 "прямого перекрытия" применяется к каждому краю между блоками, после чего каждый блок 4×4 преобразуется с помощью блочного преобразования 550. Этим блочным преобразованием 450 может быть обратимое масштабно-инвариантное двумерное преобразование, описанное в патентной заявке США 11/015707, озаглавленной "Reversible Transform For Lossy And Lossless 2-D Data Compression", на имя Srinivasan, от 17 декабря 2004 г. Альтернативно, дискретное косинусное преобразование или другие блочные преобразования могут быть использованы с оператором обратимого перекрытия, описанным в данном документе. В результате преобразования коэффициент 460 постоянной составляющей каждого блока преобразования размером 4×4 проходит аналогичную цепочку обработки (разбиение, прямое перекрытие, за которым следует блочное преобразование 4×4). Результирующие коэффициенты преобразования постоянной составляющей и коэффициенты преобразования переменной составляющей квантуются (470), подвергаются энтропийному кодированию (480) и пакетируются (490).

Декодер выполняет обратный процесс. На стороне декодера биты коэффициентов преобразования извлекаются (510) из соответствующих пакетов, из которых сами коэффициенты декодируются (520) и деквантуются (530). Коэффициенты 540 постоянной составляющей регенерируются посредством применения обратного преобразования, и плоскость коэффициентов постоянной составляющей "перекрывается в обратном порядке" с использованием подходящего сглаживающего оператора, применяемого по краям блока постоянной составляющей. В дальнейшем все данные регенерируются посредством применения обратного преобразования 550 размером 4×4 к коэффициентам постоянной составляющей, и коэффициенты 542 переменной составляющей декодируются из потока битов. Наконец, края блока в плоскостях результирующих изображений фильтруются (560) с обратным перекрытием. В результате генерируются восстановленные выходные двумерные данные.

В примерной реализации кодер 400 (фиг.4) сжимает входное изображение для получения сжатого потока 420 битов (например, файла), а декодер 500 (фиг.5) восстанавливает исходные входные данные или их приближение на основе того, какое кодирование (с потерями или без потерь) используется. Процесс кодирования влечет за собой применение прямого перекрывающегося преобразования (LT), описанного ниже, которое реализовано с помощью обратимой двумерной предварительной/постфильтрации, также более подробно описанной ниже. Процесс декодирования осуществляется посредством обратного перекрывающегося преобразования (ILT) с использованием обратимой двумерной предварительной/постфильтрации.

Проиллюстрированные преобразования LT и ILT являются инверсиями друг друга, в точном смысле, и поэтому вместе могут определяться как обратимое перекрывающееся преобразование. В качестве обратимого преобразования пара LT/ILT может быть использована для сжатия изображений без потерь.

Входными данными 410, сжатыми кодером 400/декодером 500, могут быть изображения различных форматов цветов (например, форматы цветных изображений RGB/YUV4:4:4 или YUV4:2:0). В типовом случае входное изображение всегда имеет компонент яркости (Y). Если оно является изображением RGB/YUV4:4:4 или YUV4:2:0, то изображение также имеет компоненты цветности, такие как компонент U и компонент V. Отдельные цветовые плоскости или компоненты изображения могут иметь различные пространственные разрешения. В случае входного изображения, например, в цветовом формате YUV 4:2:0, компоненты U и V имеют половину ширины и высоты компонента Y.

Как описано выше, кодер 400 разбивает входное изображение на макроблоки. В примерной реализации кодер 400 разбивает входное изображение на макроблоки 16×16 в канале Y (которыми могут быть области 16×16 или 8×8 в каналах U и V, в зависимости от цветового формата). Цветовая плоскость каждого макроблока разбита на зоны или блоки 4×4. Поэтому макроблок составляется для различных цветовых форматов следующим образом для этой примерной реализации кодера:

1. Для изображения по шкале серого каждый макроблок содержит 16 блоков яркости (Y) размером 4×4.

2. Для изображения цветового формата YUV4:2:0 каждый макроблок содержит 16 блоков Y размером 4×4 и по 4 блока цветности (U и V) размером 4×4.

3. Для цветного изображения RGB или YUV4:4 каждый макроблок содержит 16 блоков каждого из каналов b Y, U и V.

2. Перекрывающееся преобразование, реализованное с помощью операторов перекрытия

Более обобщенно, оператор 440 перекрытия и блочное преобразование 450 кодера 400 (фиг.4) является примером обширного класса перекрывающихся преобразований 600, которые могут быть факторизованы в операцию 610 предварительной фильтрации, за которой следует блочное преобразование 620 данных, как проиллюстрировано на фиг.6. Фиг.6 иллюстрирует обобщенный пример таких факторизуемых перекрывающихся преобразований. В проиллюстрированном случае перекрывающееся преобразование 310 6×4, показанное на фиг.3, факторизуется в стадии операции 610 предварительной фильтрации и блочного преобразования 620. Операция 610 предварительной фильтрации и блочное преобразование 620 выполняются ступенчатым образом равномерно по точкам данных. В данном примере перекрывающегося преобразования 600 6×4 каждый предварительный фильтр соответствует преобразованию с длиной 2 точек данных, переходящих в соседние блоки. На стороне декодера постфильтр 640 применяется после обратного блочного преобразования вдоль границ блоков. Так же, для общего случая K × N предварительный фильтр применяется к (K-N)/2 точкам данных каждого блока, смежного с границей блока.

Для обратимости предварительный фильтр 610 и постфильтр 640 являются инверсиями друг друга. Однако для реализации перекрывающегося преобразования без потерь этого условия недостаточно. Это дополнительно ограничивает предварительные и постфильтры 610, 640, которые также должны быть преобразованиями без потерь, помимо блочного (базового) преобразования 620, которое должно быть реализовано способом без потерь. DCT может быть реализовано способом без потерь, используя, в том числе, лестничные, решетчатые или основанные на поднятии способы, помимо прочего (см., например, A.A.M.L. Brackens, A.W.M. van den Enden, "New networks for perfect inversion and perfect reconstruction", IEEE J. Selected Areas Communications, том 10, номер l, 1992 г.; и I. Daubechies и W. Sweldens, "Factoring wavelet transform into lifting steps", J. Fourier Anal. Appl., том 4, стр. 247-269, 1998 г.) Обратимое масштабно-инвариантное двумерное преобразование также описано в патентной заявке США 11/015707 на имя Srinivasan, озаглавленной "Reversible Transform For Lossy And Lossless 2-D Data Compression", от 17 декабря 2004 г. Также известны основанные на поднятии обратимые аппроксимации DCT по одному измерению (см., например, J. Liang, T.D. Tran, "Fast multiplierless approximations of the DCT with the lifting scheme", IEEE Trans. Signal Processing, том 49, стр. 3032-3044, декабрь 2001 г.)

Эффективная обратимость дополнительно требует, чтобы оба этапа, т.е. предварительная/постфильтрация и блочное преобразование, были единичными детерминантными.

3. Оператор обратимого перекрытия

Оператор эффективного обратимого перекрытия для использования в качестве предварительного фильтра 610 (фиг.6) перекрывающегося преобразования 600 без потерь, на котором основан кодер 400/декодер 500 (фиг.4 и 5), может быть реализован как предварительный фильтр линейной фазы, который факторизован в структуре 700, показанной на фиг.7. Инверсия данного предварительного фильтра (т.е. постфильтр 640) также имеет такую же структуру, но с другими коэффициентами.

Данная структура 700 фильтра линейной фазы имеет несколько ортогональных компонентов, в том числе разделительную цепь 710 Адамара на своем входе и выходе. Внутренние стрелки в показанной цепи 710 Адамара означают отрицание на данной схеме. Структура 700 также включает в себя ортогональные матрицы U1, U2, V1 и V2. Эти компоненты могут быть реализованы способом без потерь посредством использования решетчатых/основанных на поднятии способов.

Помимо этого, структура 700 имеет ненулевые масштабные коэффициенты s ₁ - s _M . Единичное детерминантное ограничение подразумевает, что . Когда все масштабные коэффициенты равны ±1, предварительные/постфильтры могут быть реализованы в качестве преобразования без потерь, где матрицы компонентов U1, U2, V1 и V2 реализованы как этапы решетки/поднятия без потерь. Однако, когда масштабные коэффициенты не все равны ±1, реализация без потерь вызывает проблему, описанную ниже более подробно.

С помощью данной структуры 700 предварительного фильтра линейной фазы задача реализации пары предварительного/постфильтра сводится к трем следующим этапам:

1) разложение фильтра F в следующую форму для ортогональных матриц U1, U2, V1 и V2:

где I - единичная матрица, а

2) получение реализаций без потерь для U1, U2, V1 и V2 и

3) получение реализации без потерь для матрицы масштабирования.

Что касается этапа 1, первая и последняя матрицы в правой части, которые определяют 2-точечные преобразования Адамара, содержат коэффициент 1/2 в некоторых членах, чтобы сделать эти стадии единичными детерминантными. Остальное переупорядочено в диагональную форму блоков для двух блоков, каждый из половины линейных измерений F. Разложение по особым значениям матрицы (SVD) каждого блока дает ортогональные матрицы U1, U2, V1 и V2, а также масштабы.

Реализации без потерь матриц компонентов могут быть получены на этапе 2 с помощью стандартных методов, основанных на поднятии (см., например, A.A.M.L. Bruekens, A.W.M. van den Enden, "New networks for perfect inversion and perfect reconstruction", IEEE J. Selected Areas Communications, том 10, номер 1, 1992 г.)

Реализация без потерь матрицы масштабирования на этапе 3 осуществляется следующим образом. Для простоты допустим, что имеется некоторый компонент с двумя входами и двумя выходами, который (a) не имеет потерь и (b) реализует масштабирование посредством s (0< s <1) для первого компонента и посредством 1/s для второго компонента (другие случаи могут быть получены посредством перемены знака одного или обоих выходных сигналов). Другими словами, мы имеем отношение входа-выхода, определяемое следующим образом:

(2)

Детерминант матрицы преобразования в уравнении (2) равен s/s = 1. Данная матрица может быть реализована в процедуре 800 с четырьмя этапами поднятия или процедуре 900 с пятью этапами поднятия, показанными на фиг.8 и 9. Обычно все этапы поднятия аппроксимируются как y = (a·x + r) >> b, где x - вход, y - выход, a, b и r - целые числа, и r используется для контроля ошибок округления, чтобы получить уменьшенную на деление целочисленную реализацию. Преобразование, заданное уравнением (2), определено в данном документе как единичное детерминантное масштабное преобразование, сокращенно масштабное преобразование.

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

(3)

При ограничении a ² - b ² = 1 (a > 0, b ≥ 0) операция сдвига имеет единичный детерминант и может быть реализована с помощью трех этапов поднятия:

Следовательно,

(5)

При этом коэффициенты масштабирования 1/2 и 2 в матрицах, окружающих матрицу сдвига, распределены этапам поднятия со сдвигом, а последний этап поднятия первой матрицы объединяется с первым этапом поднятия со сдвигом, тогда как первый этап поднятия последней матрицы объединяется с первым этапом поднятия со сдвигом. Реализация из пяти этапов в виде процедуры 900 масштабного преобразования, показанная на фиг.9, основана на уравнении (5). Упрощения в структуре возможны посредством отмены операций инверсии, где возможно между тремя группами в уравнении, т.е. цепями Адамара, ортогональными матрицами и операциями масштабирования (которые, в свою очередь, могут быть разложены на операции Адамара и сдвига).

Более конкретно, эффективная матрица преобразования в реализации из четырех этапов поднятия для масштабирования без потерь, как процедура 800, имеет вид , где c ² = 1 - s ². С другой стороны, эффективная матрица преобразования в реализации из пяти этапов поднятия, как процедура 900, имеет вид , где c ² = 1 - s ² .

Хотя процедура 800 масштабирования, показанная на фиг.8, имеет на один меньше этапов поднятия чем на фиг.9, вторая процедура 900 имеет только три этапа нетривиального поднятия, в отличие от четырех в первой. По причинам, указанным выше, первый или последний этап тривиального поднятия на фиг.9 может быть объединен с предшествующим или последующими этапами преобразования (например, с помощью цепи 710 Адамара на любом конце на фиг.7) при определенных условиях (например, когда U1, U2 и V1 - единичные).

Процедура масштабирования легко может быть распространена на более крупные матрицы. Это проиллюстрировано на фиг.10, где M, возможно, различных масштабных коэффициентов s ₁ - s _M применяются к M каналам данных в качестве каскада 1000 масштабных преобразований. Для реализации этого обратимым способом в общем случае требуется M - 1 обратимых масштабных преобразований.

Полезный особый случай соответствует случаю, когда M масштабных коэффициентов s ₁ - s_М группируются в M/2 групп формы (s, 1/s). При этом требуется только M/2 обратимых масштабных преобразований. Примером является s ₁ = s ₂ =... = s _M/2 = s и s _M/2+1 = s _M/2+2 =... = s _M = 1/s. Предпочтительный способ группировки - сохранять симметрию относительно центральной оси, другими словами, каждая группа масштабирует коэффициенты s _i и s _M+1-i. Если M нечетное, одним несгруппированным масштабным коэффициентом является 1, что соответствует каналу данных вдоль оси.

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

Согласно фиг.11 оператор обратимого перекрытия, имеющий требуемое эффективное по R-D (т.е. единичное детерминантное) свойство, реализуется в качестве структуры 700 предварительного фильтра линейной фазы (фиг.7), которая включает в себя обратимые единичные детерминантные цепи 710 Адамара, обратимые ортогональные повороты 1110 (для компонентных матриц U1, U2, V1 и V2) и обратимое единичное детерминантное масштабирование 1120 (например, с использованием процедур 800, 900 этапов поднятия или каскада 1100). Постфильтр аналогичен предварительному фильтру и сформирован с использованием той же структуры, хотя и с этапами обратного поднятия в обратном порядке. Это проиллюстрировано на фиг.7, где число значений M данных в блоке, в общем, является любым натуральным числом. Хотя иллюстрация приведена для M с четными значениями, нечетные значения также допустимы, имея в виду, что одноточечное преобразование Адамара центрального значения данных является самим собой. Эта процедура может быть обобщена до данных с более высокой размерности.

Действие оператора обратимого перекрытия проиллюстрировано на фиг.12. На первом этапе 1210 входные двумерные цифровые мультимедийные данные разбиваются на блоки (как показано для кодера 400 на фиг.4). Оператор обратимого перекрытия применяет цепь 710 Адамара к соседним мозаикам на этапе 1220. Затем оператор применяет обратимые повороты к суммам и разностям на этапе 1230, после чего следует обратимое масштабирование на этапе 1240. Затем выполняется еще один обратный блочный поворот (этап 1250) и следует обратимая инверсная цепь Адамара (этап 1260).

Согласно фиг.13 матричные представления обратимых блочных поворотов и операторов масштабирования зависят от требуемого перекрывающегося оператора, использующего, например, арифметику, описанную в уравнении (1). Фиг.13 показывает пример постфильтра, имеющего структуру 700, показанную на фиг.7 и 11, которая предваряется обратимым блочным преобразованием (в данном случае 4-точечным преобразованием Адамара). Передаточная функция постфильтра имеет вид

(6)

Низкочастотный компонент Адамара генерирует импульсную характеристику, показанную в графе на фиг.14.

4. Режимы перекрывающегося преобразования

В одной примерной реализации кодер 400 и декодер 500 поддерживают несколько режимов сжатия с помощью различных типов преобразования (например, описанного в данном документе перекрывающегося преобразования, а также режимы, когда перекрывающаяся фильтрация пропускается). В ходе процесса кодирования внутренний параметр OverlapMode предоставляется пользователем. Этот параметр определяет тип преобразования, используемый для кодирования, и сигнализируется декодеру посредством потока битов. В примерном варианте осуществления допустимы три варианта OverlapMode - "OL_NONE", "OL_ONE" и "OL_TWO", и работают следующим образом:

1. OL_NONE сигнализирует, что блочное преобразование используется для сжатия изображения.

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

3. OL_TWO сигнализирует, что перекрывающееся преобразование используется и для высокочастотного, и для низкочастотного компонента изображения.

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

В примерной реализации перекрывающееся преобразование реализовано как предварительный фильтр размером 4×4 (прямое перекрытие 440), за которым следует блочное преобразование 450 размером 4×4 на стороне кодера, как показано на фиг.17 и подробнее описано ниже. На стороне декодера перекрывающееся преобразование реализовано посредством обратного блочного преобразования 550 размером 4×4, за которым следует пост-фильтр размером 4×4 (обратное перекрытие 560), как показано на фиг.18 и подробнее описано ниже. Когда используется только блочное преобразование (например, режим OL_NONE и для полос низких частот сжатого в режиме OL_ONE изображения), этапы предварительной и постфильтрации пропускаются.

Для специального случая низкочастотных цветовых плоскостей яркости в формате YUV4:2:0 размеры фильтра и блока преобразования составляют 2×2. В последующих описаниях используется термин "4×4" для ссылок на размер фильтра/преобразования, при этом блоки 2×2 будут использоваться для этого специального случая.

Как показано на фиг.15, блочное преобразование в данной примерной реализации кодера выполняется на естественной сетке 4×4, т.е. массиве пикселей в мозаиках 4×4, выровненных с границами макроблока. Процесс фильтрации выполняется на расположенной в шахматном порядке сетке 4×4, т.е. массиве пикселей в мозаиках 4×4, смещенных на 2 в горизонтальном и вертикальном направлениях от границ макроблоков. На диаграмме 1500 на фиг.15 четыре показанных блока 1510-1513 соответствуют натуральной сетке для преобразования, а затененный (серый) блок 1520 в центре - это зона, к которой применяется предварительный/постфильтр. Пиксели в центральном блоке определяются как "основа" оператора преобразования. Фиг.16 иллюстрирует выравнивание 1600 оператора преобразования и перекрытия для специального случая 2×2.

Блочное преобразование, используемое в примерной реализации и применяемое к каждому из блоков 4×4, определяется в данном документе как "базовое" преобразование. Базовое преобразование реализует приблизительное DCT 4x4, описанное в патентной заявке США 11/015707 на имя Srinivasan, озаглавленной "Reversible Transform For Lossy And Lossless 2-D Data Compression", от 17 декабря 2004 года, и также описанной ниже в разделе, озаглавленном "Базовое преобразование". После базового преобразования блок отображается на блок коэффициентов из одного коэффициента 460 постоянной составляющей (DC) и 15 коэффициентов 462 переменной составляющей (АС) (как проиллюстрировано на фиг.4).

Предварительный/постфильтр (прямое перекрытие 440 на фиг.4 и обратное перекрытие 560 на фиг.5) в сочетании с базовым преобразованием вместе реализуют перекрывающееся преобразование, также упоминаемое в данном документе как "оператор перекрытия".

После того как базовое преобразование 450 применено посредством кодера 400 (фиг.4), DC-коэффициенты 460 всех блоков изображения собираются для формирования DC-поддиапазона. Вторая стадия базового преобразования применяется к этому DC-поддиапазону. Если OverlapMode = OL_TWO, оператор перекрытия второй стадии также применяется непосредственно перед базовым преобразованием второй стадии. Если изображение является компонентом Y или компонентом U или V изображения YUV_444, DC-поддиапазон 460 разбивается на блоки 4×4 и используются те же PCT 4×4 и PLO 4×4, что и на первой стадии. Однако, если изображение является компонентом U или V изображения YUV 4:2:0, то DC-поддиапазон разбивается вместо этого на блоки 2×2. Следовательно, используются PCT 2×2 и PLO 2×2. Фиг.16 иллюстрирует основу 1620 2×2 оператора перекрытия 2×2, которая, таким образом, расширена на соседние блоки 1610-1613 2×2.

Как показано на фиг.15, по углам изображения только 1 из 4 блоков, которые охватывает оператор перекрытия, доступен. Это блок 3 для верхнего левого угла, блок 1 верхнего правого угла, блок 2 для нижнего левого угла и блок 0 для нижнего правого угла. В этих случаях оператор перекрытия 4×4 или 2×2 пропускается.

На границах изображения, отличных от 4 углов, доступны 2 из 4 блоков, которые охватывает оператор 1520 перекрытия. В этих областях требуется только одномерный оператор. Поэтому оператор перекрытия 4×4 заменен двумя экземплярами оператора одномерного 4-точечного перекрытия (и аналогично для оператора перекрытия 2×2).

Конкретно, имеется 4 случая (со ссылкой на фиг.15):

- основа 1520, 1620 охватывает верхнюю границу изображения (блоки 0 и 2 не доступны, а блоки 1 и 3 доступны): оператор 4-точечного перекрытия применяется к точкам (i, j, k, l) и к точкам (m, n, o, p), либо оператор 2-точечного перекрытия применяется к точкам (c, d);

- основа 1520, 1620 охватывает нижнюю границу изображения (блоки 1 и 3 не доступны, а блоки 0 и 2 доступны): оператор 4-точечного перекрытия применяется к точкам (a, b, c, d) и к точкам (e, f, g, h), либо оператор 2-точечного перекрытия применяется к точкам (a, b);

- основа 1520, 1620 охватывает левую границу изображения (блоки 0 и 1 не доступны, а блоки 2 и 3 доступны): оператор 4-точечного перекрытия применяется к точкам (c, g, k, o) и к точкам (d, h, l, p), либо оператор 2-точечного перекрытия применяется к точкам (b, d);

- основа 1520, 1620 охватывает правую границу изображения (блоки 2 и 3 не доступны, а блоки 0 и 1 доступны): оператор 4-точечного перекрытия применяется к точкам (a, e, i, m) и к точкам (b, f, j, n), либо оператор 2-точечного перекрытия применяется к точкам (a, c).

Следовательно, перекрывающееся преобразование, используемое в процессе кодирования 1700 (фиг.17) примерной реализации кодера 400 (фиг.4), применяет базовое преобразование 2×2, базовое преобразование 4×4, оператор перекрытия 2×2, оператор перекрытия 4×4, оператор 2-точечного перекрытия и оператор 4-точечного перекрытия. Процесс декодирования 1800 (фиг.18), используемый декодером 500 (фиг.5), реверсирует процесс без потерь. Обратное базовое преобразование является полной инверсией базового преобразования кодера, а оператор обратимого перекрытия является полной инверсией оператора перекрытия кодера. Оператор одномерного 4-точечного перекрытия описан выше в разделе "Оператор обратимого перекрытия". Операторы двумерного перекрытия описаны ниже.

5. Двумерная предварительная/постфильтрация

В одном методе оператор перекрытия 4×4 для двумерной предварительной/постфильтрации 440 (фиг.4) может быть реализован посредством отдельного применения оператора 1900 4-точечного перекрытия по фиг.19 (также описанного выше в разделе "Оператор обратимого перекрытия") по горизонтали и вертикали к основе 1520 оператора 4-точечного перекрытия 4×4 (фиг.15). Эта реализация 2000 разделяемого метода для оператора перекрытия 4×4 проиллюстрирована на фиг.20. Более конкретно, этот метод применяет оператор одномерного 4-точечного перекрытия к вертикальным столбцам основы 1520 оператора перекрытия 4×4 (т.е. столбец a, e, i, m; столбец b, f, j, n; столбец c, g, k, o; и столбец d, h, l, p), после чего следует применение оператора одномерного 4-точечного перекрытия к горизонтальным строкам (т.е. к строке a, b, c, d; строке e, f, g, h; строке i, j, k, l; и строке m, n, o, p). Однако этот метод 2000 имеет ряд недостатков, как пояснено в разделе "Сущность изобретения" выше.

Примерная реализация описанного кодера 400/декодера 500 использует другой метод к реализации двумерной предварительной/постфильтрации (прямое перекрытие 440 и обратное перекрытие 560), которая устраняет эти недостатки. Этот другой метод 2100 (фиг.21) распределяет операции вертикальных и горизонтальных фильтров разделяемого метода на несколько стадий. Кроме того, операции группируются для формирования преобразований 2×2, которые имеют нормализованные масштабно-инвариантные и обратимые реализации "бабочки", как показано на фиг.24, 29 и 30. Кроме того, нормализованная операция масштабирования, реализованная на этапах поднятия, описанных в разделе "Оператор обратимого перекрытия", может быть применена к более ограниченному набору сигнальных пар, имея в виду компенсацию "перекрестных членов" в распределенной двумерной структуре. Это приводит к эффективному масштабно-инвариантному обратимому двумерному предварительному/постфильтру, который вместе с эффективным масштабно-инвариантным обратимым двумерным блочным преобразованием предоставляет перекрывающееся преобразование, которое может быть использовано в кодере/декодере для эффективного, в том числе в вычислительном смысле сжатия изображений и видео, как с потерями, так и без потерь.

Как проиллюстрировано на фиг.21, этот второй метод в проиллюстрированной реализации распределяет вертикальные и горизонтальные операции предварительных/постфильтров на три стадии. В рамках каждой стадии операции дополнительно переупорядочиваются в базовые операции 2×2 над отдельными группами из 4 точек блока данных 4×4.

Более конкретно, первая стадия, а также последняя стадия в предварительных/постфильтрах реализуется как нормализованная 2-точечная бабочка Адамара. Вертикальные и горизонтальные операции на этой стадии переупорядочиваются в нормализованную операцию Адамара 2×2 (которая является _Н-преобразованием, описанным в вышеуказанной заявке 11/015707, как определено в листинге 2200 программы, показанном на фиг.22, которая применяется отдельно к группам из четырех точек в блоке данных 4×4. Эта нормализованная операция Адамара 2×2 применяется к входной матрице 2300 2×2 (точки a, b, c и d), как показано на фиг.23. Затенение используется на фиг.23 и в остальной части данного документа для представления соответствий между точками данных (эквивалентно, пикселями или элементами матрицы) и этапами обработки. Базовая операция 2×2, применяемая к входной матрице [a b; c d], вычисляется на месте, как показано на фиг.23.

Операции стадии 1 и стадии 3 в распределенном методе 2100 (фиг.21) затем могут быть переупорядочены в применения этой нормализованной операции 2200 Адамара 2×2 (фиг.21) к четырем отдельным 4-точечным группам 2400 (фиг.24) в блоке данных, т.е. 4 точкам 2410 по углам, центральным 4 точкам 420, 4 точкам 2430 верхнего/нижнего края и 4 точкам 2440 правого/левого края.

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

Этап поворота реализован посредством повторного переупорядочения операций в раздельные преобразования 2×2. Поскольку низкочастотные элементы являются сквозными для одномерного случая (точки ×0 и ×1 в операторе 1900 4-точечного перекрытия фиг.19), точки "низкие-низкие" (т.е. низкочастотные в обоих направлениях) в двумерных случаях снова являются сквозными (т.е. не фильтруются на этой стадии). Это соответствует верхнему левому субблоку 2910 2×2 на фиг.29.

Элементы 2920 "высокие-высокие" (фиг.29) реализуются с помощью эффективной операции 2500 нормализованного обратимого поворота 2×2, которая является _odd-odd-преобразованием, описанным в упомянутой заявке 11/015707. Это _odd-odd-преобразование может быть реализовано в листинге 2500 на языке программирования C, как показано на фиг.25. Смещения в этапах нетривиального поднятия (т.е. предусматривающих умножение на 3) выбираются таким образом, чтобы минимизировать общий сдвиг. Инверсия этого преобразования для постфильтра может быть реализована в листинге 2600 на языке программирования C, как показано на фиг.26.

Высокие-низкие и низкие-высокие элементы 2930 (фиг.29) предусматривают только одномерную фильтрацию, поскольку операция другого измерения является сквозной. Они реализуются с помощью 2-точечных поворотов, как определено в листинге 2700 на языке программирования C, как показано на фиг.27. Обратная операция для постфильтра реализуется в листинге 2800 на языке программирования C согласно фиг.28. Эти 2-точечные повороты являются простыми приближениями, предусматривающими два вычислительно тривиальных этапа поднятия, которые удовлетворительно работают на практике. Альтернативно могут быть использованы другие приближения. Этот 2-точечный поворот применяется как четыре набора 2-точечных операций к низким-высоким и высоким-низким элементам 2930, как указано затенением на фиг.29.

Что касается этапа масштабирования стадии 2, оператор 1900 одномерного 4-точечного перекрытия (фиг.19) включает в себя масштабирование четырех точек на [f f 1/f 1/f]. Для двумерного случая этап масштабирования реализует внешнее произведение [f f 1/f 1/f] с самим собой. Результирующая матрица масштабирования имеет вид

.

Половина элементов матрицы являются единицами, и поэтому эти точки просто проходятся. Оставшиеся элементы связываются в пары симметрично в 2-точечных операциях относительно центра матрицы (т.е. пары 3010, 3020, 3030 и 3040, как показано затенением на фиг.30). Симметрия необходима для лучшей характеристики "скорость-искажение" для согласованности со стадиями 1 и 3 в распределенном методе 2100 (фиг.21). Операция 2-точечного масштабирования, применяемая к каждой паре, реализована в листинге 3100 на языке программирования C, как показано на фиг.31. Операция обратного 2-точечного масштабирования для постфильтра показана в листинге 3200 на фиг.32. Альтернативно, другие приближения также возможны для процесса 2-точечного масштабирования. Кроме того, процесс масштабирования может быть объединен с операциями Адамара 2×2 стадии 1 или стадии 3, имея в виду компенсации между их конечными операциями.

Фиг.33 иллюстрирует листинг 3300 программы полного оператора преобразования 4×4, использующего распределенный метод 2100, показанный на фиг.21. Как описано выше для реализации кодера 400/декодера 500, показанной на фиг.17 и 18, оператор перекрытия 4×4 применяется к нецентральной и неграничной части изображения, если OL_ONE является истиной. Если OL_TWO является истиной, он также применяется к нецентральной и неграничной части поддиапазона постоянного тока изображения, если он не является компонентом U или V изображения YUV 4:2:0. Возможны другие альтернативные реализации с различными приближениями или объединенными этапами (особенно между масштабированием и преобразованием Адамара).

Как проиллюстрировано на фиг.15 выше, оператор перекрытия 4×4 применяется к основе оператора перекрытия, что может быть представлено как блок входных данных:

.

Оператор прямого перекрытия 4×4 затем задается в этом листинге программы как функция PLO4×4 (a, b, c, d, e, f, g, h, i, j, l, l, m, n, o, p). Как описано выше, эта функция включает в себя применение операции 2200 Адамара 2×2 (фиг.22), прямого масштабирования 3100 (фиг.31), 2-точечных поворотов 2700 (фиг.27) и прямого нечетно-нечетного преобразования 2500 (фиг.25) на трех стадиях к подгруппам входного блока, показанным на фиг.24, 29 и 30.

Фиг.34 показывает листинг 3400 программы реализации оператора обратного перекрытия 4×4 также с использованием распределенного метода. Если блок входных коэффициентов оператора обратного перекрытия 4×4 является блоком

,

то оператор задается в этом листинге программы как функция PLO4×4 (a, b, c, d, e, f, g, h, i, j, l, l, m, n, o, p). Оператор обратного перекрытия 4x4 включает в себя применение операции 2200 Адамара 2×2 (фиг.22) (который является собственной инверсией), обратное нечетное-нечетное преобразование 2600 (фиг.26), обратный 2-точечный поворот 2800 (фиг.28) и обратное масштабирование 3200 (фиг.32) снова на трех стадиях к подгруппам точек блока коэффициентов, как показано на фиг.24, 29 и 30.

Как описанный выше специальный случай, примерная реализация кодера/декодера, показанная на фиг.17 и 18, также применяет операцию предварительной/постфильтрации 2×2. Фиг.35 показывает листинг 3500 программы для предварительной фильтрации 2×2. Предварительная/постфильтрация 2×2 аналогична предварительной/постфильтрации 4×4 за исключением того, что на стадии 2 отсутствует поворот. Предварительная фильтрация 2×2 поэтому может быть реализована для случая 4×4, описанного выше, с исключенными этапами поворота стадии 2. Фиг.36 показывает листинг 3600 программы, реализующей постфильтрацию 2×2.

В примерной реализации кодера/декодера, показанной на фиг.17 и 18, фильтрация по одному измерению также необходима вдоль краев изображения, где недостаточно пикселей для этапа двумерной фильтрации. Одномерные фильтры могут быть более сложными, чем соответствующие двумерные фильтры, вследствие отсутствия кратчайших путей для реализации нормализованного поднятия без потерь. Реализация одномерной предварительной/постфильтрации описана выше в разделе "Оператор обратимого перекрытия".

Фиг.37 показывает листинг 3700 программы (на языке программирования C) оператора одномерного 2-точечного перекрытия, который применяется в примерной реализации кодера/декодера фиг.17 и 18 к границам DC-поддиапазонов компонентов U и V изображения YUV 4:2:0, если OL_TWO является истиной. Фиг.38 показывает листинг 3800 программы для оператора одномерного обратного 2-точечного перекрытия.

Примерная реализация кодера/декодера фиг.17 и 18 также применяет оператор 2-точечного перекрытия к границам изображения, если OL_ONE является истиной. Если OL_TWO является истиной, оператор 4-точечного перекрытия также применяется к границам DC-поддиапазона изображения, если он не является компонентом U или V изображения YUV 4:2:0. Оператор одномерного 4-точечного прямого перекрытия для входных данных, упорядоченных как [a b c d], затем задается в листинге 3900 программы (на языке программирования C), показанном на фиг.39, как функция PLO4 (a, b, c, d). Листинг 4000 программы, показанный на фиг.40, включает в себя функцию IPLO (a, b, c, d), которая задает оператор 4-точечного обратного перекрытия для входных коэффициентов [a b c d].

6. Базовое преобразование

Как упоминалось выше, примерная реализация кодера/декодера реализует перекрывающееся преобразование, которое является сочетанием вышеописанных операторов перекрытия вместе с обратимым приблизительным DCT 4×4, описанным в вышеуказанной заявке 11/015707. Как показано на фиг.17 для процесса 1700 кодирования и на фиг.18 для процесса 1800 декодирования этой примерной реализации, кодер/декодер использует базовое преобразование 2×2, обратное базовое преобразование 2×2, базовое преобразование 4×4 и обратное базовое преобразование 4×4. Реализации этих преобразований заданы в листингах программы (на языке программирования C), показанных на фиг.41-46, как описано ниже.

Прямое базовое преобразование 2×2 для входного блока 2×2

может быть реализовано в два этапа:

1) применить функцию 2200 Адамара 2×2(a, b, c, d) фиг.22;

2) выполнить перестановку точек b и c.

В некоторых реализациях этап 2 может быть объединен с квантованием или зигзагообразным сканированием.

Прямое базовое преобразование 2×2 для блока 2×2 коэффициентов

может быть реализовано в два этапа:

1) выполнить перестановку точек b и c;

2) применить функцию 2200 Адамара 2×2(a, b, c, d) фиг.22.

В некоторых реализациях этап 1 может быть объединен с деквантованием или обратным зигзагообразным сканированием.

Прямое базовое преобразование 4×4, применяемое к блоку входных данных 4×4

может быть реализовано в два этапа:

1. Применить функцию 4100, PCT4×4(a, b, c, d, e, f, g, h, I, j, k, l, m, n, o, p), показанную на фиг.41. Аналогично оператору перекрытия 4×4, эта функция использует распределенный метод, в котором операции дополнительно упорядочиваются в операции 2×2 над подгруппами точек блока данных. Эти операции 2×2 включают в себя четное преобразование, реализованное в функции 4200, показанной на фиг.42, и четное-четное преобразование, реализованное в функции 4300, показанной на фиг.43. Возможны другие приближения, основанные на большем или меньшем числе этапов поднятия для реализации поворота.

2. Перегруппировать блок данных с к . Это может быть объединено с квантованием/зигзагообразным сканированием.

Обратное базовое преобразование 4×4 для блока входных коэффициентов 4×4

может быть реализовано в следующие два этапа:

1. Перегруппировать блок данных с к . Это может быть объединено с деквантованием/обратным зигзагообразным сканированием.

2. Применить функцию 4400 IPCT4×4(a, b, c, d, e, f, g, h, I, j, k, l, m, n, o, p), показанную на фиг.44, которая является инверсией функции 4100 PCT4×4. Функция 4400 включает в себя преобразования 2×2: обратное четное преобразование, реализованное функцией 4500, показанной на фиг.45, и обратное четное-четное преобразование, заданное функцией 4600, показанной на фиг.46.

7. Вычислительная среда

Вышеописанный кодек, основанный на перекрывающемся преобразовании, использующем предварительную и постфильтрацию 4×4, может быть применен в любом из множества устройств, в котором выполняется обработка цифровых мультимедийных сигналов, в том числе (помимо других примеров) на компьютерах; на оборудовании для записи, передачи и приема изображений и видео; на портативных видеопроигрывателях; в устройствах видеоконференцсвязи и т.д. Способы кодирования цифровых мультимедийных сигналов могут быть реализованы аппаратными средствами, а также программным обеспечением обработки цифровых мультимедийных сигналов, исполняемым на компьютере или в другой вычислительной среде, такой как показано на фиг.47.

Фиг.47 иллюстрирует обобщенный пример подходящей вычислительной среды 4700, в котором могут быть реализованы описанные варианты осуществления. Вычислительная среда 4700 не предназначена для ограничения области использования или функциональности изобретения, поскольку настоящее изобретение может быть реализовано в различных вычислительных средах общего или специального назначения.

Согласно фиг.47 вычислительная среда 4700 включает в себя, по меньшей мере, один блок 4710 обработки и запоминающее устройство 4720. На фиг.47 эта наиболее общая конфигурация 4730 показана пунктирной линией. Блок обработки 4710 исполняет машиноисполняемые инструкции и может быть реальным или виртуальным процессором. В многопроцессорной системе несколько блоков обработки исполняют машиноисполняемые инструкции, чтобы повысить вычислительную мощность. Запоминающим устройством 4720 может быть энергозависимая память (например, регистры, кэш, ОЗУ), энергонезависимая память (например, ПЗУ, ЭСППЗУ, флэш-память и т.д.) или какое-либо их сочетание. Запоминающее устройство 4720 сохраняет программное обеспечение 4780, реализующее описанный кодер/декодер и преобразования.

Вычислительная среда может иметь дополнительные признаки. Например, вычислительное окружение 4700 включает в себя память 4740, устройства 4750 ввода, одно или более устройств 4760 вывода и одно или более коммуникационных соединений 4770. Механизм межкомпонентного соединения (не показан), такой как шина, контроллер или сеть, соединяет между собой компоненты вычислительной среды 4700. Типично программное обеспечение операционной системы (не показано) предоставляет операционную среду для другого программного обеспечения, исполняемого в вычислительной среде 4700, и координирует действия компонентов вычислительной среды 4700.

Память 4740 может быть съемной или стационарной и включает в себя магнитные диски, магнитные ленты или кассеты, CD-ROM, CD-RW, DVD или любой другой носитель, который может быть использован, чтобы сохранять информацию, и к которому можно осуществлять доступ в вычислительной среде 4700. Память 4740 сохраняет инструкции для программного обеспечения 4780, реализующего кодек, основанный на перекрывающемся преобразовании, использующем предварительную и постфильтрацию 4×4.

Устройствами 4750 ввода может быть устройство сенсорного ввода, такое как клавиатура, мышь, перо или шаровой манипулятор, устройство голосового ввода, устройство сканирования или другое устройство, которое обеспечивает ввод в вычислительную среду 4700. Для аудиосигналов устройствами 4750 ввода может быть звуковая плата или аналогичное устройство, которое принимает аудиоввод в аналоговой или цифровой форме, либо устройство считывания CD-ROM, которое предоставляет выборки аудиосигнала в вычислительную среду. Устройствами 4760 вывода может быть дисплей, принтер, динамик, пишущее устройство CD-RW или другое устройство, которое обеспечивает вывод из вычислительной среды 4700.

Коммуникационные соединения 4770 обеспечивают обмен данными по среде передачи с другим вычислительным объектом. Среда передачи передает информацию, такую как машиноисполняемые инструкции, сжатую аудио- и видеоинформацию или другие данные в модулированном информационном сигнале. Модулированный информационный сигнал - это сигнал, который имеет одну или более характеристик, установленных или изменяемых таким образом, чтобы кодировать информацию в сигнале. В качестве примера, а не ограничения, среда передачи включает в себя проводные или беспроводные методы, реализованные с помощью электрической, оптической, радиочастотной, инфракрасной, акустической или иной несущей.

Методы обработки цифрового мультимедийного сигнала в данном документе могут быть описаны в общем контексте машиночитаемых носителей. Машиночитаемые носители - это любые доступные носители, к которым можно осуществлять доступ в вычислительной среде. В качестве примера, а не ограничения, в вычислительной среде 4700 машиночитаемые носители включают в себя запоминающее устройство 4720, память 4740, среду передачи и сочетания любого из вышеуказанного.

Методы обработки цифрового мультимедийного сигнала в данном документе могут быть описаны в общем контексте машиноисполняемых инструкций, таких как включенные в программные модули, исполняемые в вычислительной среде на целевом реальном или виртуальном процессоре. В общем, программные модули включают в себя процедуры, программы, библиотеки, объекты, классы, компоненты, структуры данных и т.д., которые выполняют конкретные задачи или реализуют конкретные абстрактные типы данных. Функциональность программных модулей может объединяться или разделяться между программными модулями, как требуется в различных вариантах осуществления. Машиноисполняемые инструкции для программных модулей могут исполняться в локальной или распределенной вычислительной среде.

Для целей представления подробное описание использует такие термины, как "определить", "генерировать", "настроить" и "применить", чтобы описывать операции вычислительной машины в вычислительной среде. Эти термины являются высокоуровневыми абстракциями для операций, выполняемых вычислительной машиной, и их не следует путать с действиями, выполняемыми человеком. Фактические операции вычислительной машины, соответствующие этим терминам, различаются в зависимости от реализации.

4. Вариации и расширения оператора обратимого перекрытия

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

Ортогональные повороты в вышеописанной реализации оператора обратимого перекрытия могут быть заменены их аппроксимацией либо другими преобразованиями, которые могут быть не ортогональными.

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

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

Оператор обратимого перекрытия может быть применен в надлежащим образом модифицированной форме, чтобы реализовать гребенки фильтров с различными скоростями, импульсы, перекрывающиеся преобразования с основой, охватывающей ширину более чем 2 блока (K > 2N).

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

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

1. Способ кодирования двумерных цифровых мультимедийных данных, при этом способ содержит этапы, на которых:
вводят двумерные цифровые мультимедийные данные; и
сжимают двумерные цифровые мультимедийные данные в сжатый поток, используя перекрывающееся преобразование, при этом сжатие включает в себя:
разделение двумерных цифровых мультимедийных данных на макроблоки;
применение оператора обратимого двумерного перекрытия к первому массиву цифровых мультимедийных данных, который смещен в обоих направлениях, в горизонтальном и вертикальном, от границ макроблоков; и применяют обратимое двумерное блочное преобразование ко второму массиву цифровых мультимедийных данных, который выровнен с границами макроблоков, при этом применение оператора обратимого двумерного перекрытия и обратимого двумерного блочного преобразования совместно осуществляет перекрывающееся преобразование двумерных цифровых мультимедийных данных.

2. Способ по п.1, в котором применение оператора обратимого двумерного перекрытия содержит для первого массива цифровых мультимедийных данных: применение последовательности операций на множестве стадий, чередуя горизонтальное и вертикальное отдельное применение оператора одномерного обратимого перекрытия, к первому массиву цифровых мультимедийных данных, при этом операции на соответствующей стадии упорядочены в виде набора элементарных преобразований, реализуемых как этапы поднятия для независимых подгрупп точек в первом массиве цифровых мультимедийных данных.

3. Способ по п.2, в котором применение операций на начальной и последней стадии содержит применение нормализованного оператора Адамара 2×2 к 4-точечным подмножествам первого массива цифровых мультимедийных данных.

4. Способ по п.3, в котором 4-точечные подмножества содержат:
группу из четырех точек по углам первого массива цифровых мультимедийных данных;
группу из четырех точек в центре первого массива цифровых мультимедийных данных;
группу из четырех точек, центрированных по горизонтальным краям первого массива цифровых мультимедийных данных; и группу из четырех точек, центрированных по вертикальным краям первого массива цифровых мультимедийных данных.

5. Способ по п.3, в котором применение операций на стадии между начальной и последней стадией содержит применение преобразований поворота к подмножествам точек в первом массиве цифровых мультимедийных данных.

6. Способ по п.5, в котором применение преобразований поворота содержит этапы, на которых:
проходят через 2×2 низкочастотные точки низкочастотного подмножества первого массива цифровых мультимедийных данных;
применяют преобразование поворота 2×2 к 2×2 высокочастотным точкам высокочастотного подмножества первого массива цифровых мультимедийных данных; и
применяют 2-точечное преобразование поворота к независимым 2-точечным подгруппам 2×2 высокочастотным низкочасточного подмножества и 2×2 низкочастотным высокочастатного подмножества первого массива цифровых мультимедийных данных.

7. Способ по п.3, в котором применение операций на другой стадии между начальной и последней стадией содержит применение операций масштабирования к подмножествам точек в первом массиве цифровых мультимедийных данных.

8. Способ по п.7, в котором при применении операций масштабирования на другой стадии к подмножествам точек в первом массиве цифровых мультимедийных данных и применение оператора Адамара 2×2 на начальной и последней стадиях пропускают, по меньшей мере, некоторые операции, относящиеся к горизонтальному и вертикальному раздельному применению оператора одномерного обратимого перекрытия к первому массиву цифровых мультимедийных данных, причем этими, по меньшей мере, некоторыми операциями являются операции масштабирования другой стадии, которые взаимно компенсируются с операциями оператора Адамара 2×2 начальной и последней стадий.

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

10. Способ по п.7, в котором применение операций масштабирования содержит этапы, на которых:
проходят через 2×2 высокочастотные точки низкочастотного подмножества и 2×2 низкочастотные высокочастотного подмножества первого массива цифровых мультимедийных данных;
применяют операции масштабирования к 2×2 высокочастотным высокочастотного подмножества первого массива цифровых мультимедийных данных и к 2×2 низкочастотным низкочастотного подмножества первого массива цифровых мультимедийных данных.

11. Способ по п.10, в котором применение операций масштабирования к 2×2 высокочастотным высокочастотного подмножества и низкочастотным низкочастотного подмножества первого массива цифровых мультимедийных данных содержит:
применение операции 2-точечного масштабирования к парам точек из двух подмножеств, расположенных симметрично относительно центра первого массива цифровых мультимедийных данных.

12. Машиночитаемый носитель, содержащий программное обеспечение, исполняемое в цифровом мультимедийном процессоре, для обеспечения выполнения процессором способа по любому из пп.1-11.

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

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

15. Двумерный цифровой мультимедийный процессор по п.14, причем процессор дополнительно запрограммирован таким образом, чтобы при применении последовательности операций на множестве стадий применять нормализованный оператор Адамара 2×2 к 4-точечным подмножествам первого массива цифровых мультимедийных данных на начальной и последней стадии,
применять преобразования поворота к подмножествам точек в первом массиве цифровых мультимедийных данных на стадии между начальной и последней стадией и
применять операции масштабирования на стадии между начальной и последней стадией.

16. Двумерный цифровой мультимедийный процессор по п.15, в котором для случая блоков размером 4×4 точек цифровых мультимедийных данных 4-точечные подмножества содержат:
группу из четырех точек по углам первого массива цифровых мультимедийных данных,
группу из четырех точек в центре первого массива цифровых мультимедийных данных,
группу из четырех точек, центрированных по горизонтальным краям первого массива цифровых мультимедийных данных, и
группу из четырех точек, центрированных по вертикальным краям первого массива цифровых мультимедийных данных.

17. Двумерный цифровой мультимедийный процессор по п.15, при этом процессор дополнительно запрограммирован таким образом, чтобы при применении преобразований поворота
проходить через 2×2 низкочастотные точки низкочастотного подмножества первого массива цифровых мультимедийных данных;
применять преобразование поворота 2×2 к 2×2 высокочастотным точкам высокочастотного подмножества первого массива цифровых мультимедийных данных и
применять 2-точечное преобразование поворота к независимым 2-точечным группам 2×2 высокочастотным низкочастотного подмножества и 2×2 низкочастотным высокочастотного подмножества первого массива цифровых мультимедийных данных.

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

19. Способ декодирования двумерных цифровых мультимедийных данных, при этом способ содержит этапы, на которых:
вводят сжатый поток; и
восстанавливают сжатый поток в двумерные цифровые мультимедийные данные, используя инверсию перекрывающегося преобразования, двумерные цифровые мультимедийные данные упорядочены в макроблоки, при этом восстановление включает в себя:
применяют инверсию обратимого двумерного блочного преобразования к первому массиву цифровых мультимедийных данных, который выровнен с границами макроблоков;
применяют инверсию обратимого двумерного блочного преобразования ко второму массиву цифровых мультимедийных данных, который смещен в обоих направлениях, в горизонтальном и вертикальном, от границ макроблоков;
при этом применение инверсии оператора обратимого двумерного перекрытия и инверсии обратимого двумерного блочного преобразования совместно осуществляет инверсию перекрывающегося преобразования.

20. Способ по п.19, в котором применение инверсии оператора обратимого двумерного перекрытия содержит для второго массива цифровых мультимедийных данных: применение последовательности операций на множестве стадий, чередуя горизонтальное и вертикальное отдельное применение оператора одномерного обратимого перекрытия, ко второму массиву пикселей, при этом операции на соответствующей стадии упорядочены в виде набора элементарных преобразований, реализуемых как этапы поднятия для независимых подгрупп точек во втором массиве цифровых мультимедийных данных.

21. Способ по п.20, в котором применение операций на начальной и последней стадии содержит применение нормализованного оператора Адамара 2×2 к 4-точечным подмножествам второго массива цифровых мультимедийных данных.

22. Способ по п.21, в котором 4-точечные подмножества содержат:
группу из четырех точек по углам второго массива цифровых мультимедийных данных;
группу из четырех точек в центре второго массива цифровых мультимедийных данных;
группу из четырех точек, центрированных по горизонтальным краям второго массива цифровых мультимедийных данных; и группу из четырех точек, центрированных по вертикальным краям второго массива цифровых мультимедийных данных.

23. Способ по п.21, в котором применение операций на стадии между начальной и последней стадией содержит применение преобразований поворота к подмножествам точек в первом массиве цифровых мультимедийных данных.

24. Способ по п.23, в котором применение инверсии преобразований поворота содержит этапы, на которых:
проходят через 2×2 низкочастотные точки низкочастотного подмножества второго массива цифровых мультимедийных данных;
применяют преобразование поворота 2×2 к 2×2 высокочастотным точкам высокочастотного подмножества второго массива цифровых мультимедийных данных; и
применяют инверсию 2-точечного преобразования поворота к независимым 2-точечным подгруппам 2×2 высокочастотным низкочасточного подмножества и 2×2 низкочастотным высокочастатного подмножества второго массива цифровых мультимедийных данных.

25. Способ по п.21, в котором применение операций на другой стадии между начальной и последней стадией содержит применение инверсии операций масштабирования к подмножествам точек во втором массиве цифровых мультимедийных данных.

26. Способ по п.25, в котором при применении инверсии операций масштабирования на другой стадии к подмножествам точек во втором массиве цифровых мультимедийных данных и применение оператора Адамара 2×2 на начальной и последней стадиях пропускают, по меньшей мере, некоторые операции, относящиеся к горизонтальному и вертикальному раздельному применению инверсии оператора одномерного обратимого перекрытия ко второму массиву цифровых мультимедийных данных, причем этими, по меньшей мере, некоторыми операциями являются операции масштабирования другой стадии, которые взаимно компенсируются с операциями оператора Адамара 2×2 начальной и последней стадий.

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

28. Способ по п.25, в котором применение инверсии операций масштабирования содержит этапы, на которых:
проходят через 2×2 высокочастотные точки низкочастотного подмножества и 2×2 низкочастотные высокочастотного подмножества второго массива цифровых мультимедийных данных
применяют операции масштабирования к 2×2 высокочастотному высокочастотного подмножества второго массива цифровых мультимедийных данных и к 2×2 низкочастотному низкочастотного подмножества второго массива цифровых мультимедийных данных.

29. Способ по п.28, в котором применение инверсии операций масштабирования к 2×2 высокочастотному высокочастотного подмножества и низкочастотному низкочастотного подмножества второго массива цифровых мультимедийных данных содержит:
применение инверсии операции 2-точечного масштабирования к парам точек из двух подмножеств, расположенных симметрично относительно центра второго массива цифровых мультимедийных данных.

30. Машиночитаемый носитель, содержащий программное обеспечение, исполняемое в цифровом мультимедийном процессоре, для обеспечения выполнения процессором способа по любому из пп.19-29.

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