КОДИРОВАНИЕ/ДЕКОДИРОВАНИЕ ЦИФРОВОГО МУЛЬТИМЕДИА НА ОСНОВЕ ПЕРЕКРЫВАЮЩЕГОСЯ SIMD-ПРЕОБРАЗОВАНИЯ Российский патент 2011 года по МПК G06K9/36 

Разрешение по авторским правам

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

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

Блочное кодирование, основанное на преобразовании

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

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

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

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

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

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

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

Многие системы сжатия изображений и видео, такие как MPEG и Windows Media, помимо прочих используют преобразования на основе дискретного косинусного преобразования (DCT). DCT, как известно, имеет подходящие свойства энергетического сжатия, что приводит к практически оптимальному сжатию данных. В этих системах сжатия обратное DCT (IDCT) используется в циклах восстановления как в кодере, так и в декодере системы сжатия для восстановления отдельных блоков изображений.

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

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

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

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

Инверсии перекрывающихся преобразований (к примеру, ILT 220 по Фиг.2), в общем, просто вычислять и реализовывать. Граф потоков сигналов разворачивается, при этом каждая элементарная операция инвертируется. Одна классическая формулировка перекрывающегося преобразования - это последовательность смесителей частот, после которой идет последовательность блочных преобразований. Альтернативная формулировка содержит последовательность блочных преобразований, за которой следуют операции пост-фильтрации, применяемые на границах блоков.

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

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

Раскрытие изобретения

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

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

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

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

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

Фиг.3 - блок-схема последовательности операций типичного кодера, содержащего адаптивное кодирование коэффициентов широкого диапазона.

Фиг.4 - блок-схема последовательности операций декодера, содержащего декодирование адаптивно кодированных коэффициентов широкого диапазона.

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

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

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

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

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

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

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

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

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

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

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

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

Фиг.17 - блок-схема подходящего вычислительного окружения для реализации распараллеленной SIMD-версии типичного кодера/декодера по Фиг.3 и 4.

Осуществление изобретения

Нижеприведенное описание относится к методикам кодирования и декодирования, которые предоставляют более быструю реализацию перекрывающегося преобразования как распараллеленных или SIMD-операций (далее "методика распараллеливания преобразований"). Нижеприведенное описание поясняет примерную реализацию методики в контексте системы сжатия цифрового мультимедиа или кодека. Цифровая мультимедийная система кодирует цифровые мультимедийные данные в сжатую форму для передачи или хранения и декодирует данные для воспроизведения или другой обработки. Иллюстрацией этой примерной системы сжатия, содержащей данную методику распараллеливания преобразований, является система сжатия изображений или видео. Альтернативно, методика также может быть включена в системы сжатия или кодеки для других двумерных данных. Методика распараллеливания преобразований не требует того, чтобы система сжатия цифрового мультимедиа кодировала сжатые цифровые мультимедийные данные в конкретном формате кодирования.

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

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

Кодер 300 2D-данных вырабатывает сжатый битовый поток 320, который является более компактным представлением (для типичного ввода) 2D-данных 310, представленных в качестве входных данных кодеру. Например, входным сигналом 2D-данных может быть изображение, кадр видеопоследовательности или другие данные, имеющие два измерения. Кодер 2D-данных фрагментирует 330 входные данные на макроблоки, которые имеют размер 16×16 пикселей в этом иллюстративном кодере. Кодер 2D-данных дополнительно фрагментирует макроблок на блоки 4×4. Оператор 340 "прямого перекрытия" применяется к каждому краю между блоками, после чего каждый блок 4×4 преобразуется с помощью блочного преобразования 350. Этим блочным преобразованием 350 может быть обратимое безразмерное двумерное преобразование, описанное Srinivasan в Патентной заявке №11/015707 (США), озаглавленной "Reversible Transform For Lossy And Lossless 2-D Data Compression", зарегистрированной 17 декабря 2004 года, раскрытие которой содержится в данном документе по ссылке. Оператор 340 перекрытия может быть оператором обратимого перекрытия, который подробно описан Tu et al., Патентная заявка (США) номер 11/015148, озаглавленная "Reversible Overlap Operator for Efficient Lossless Data Compression", зарегистрированная 17 декабря 2004 года, раскрытие которой включено в состав данного документа по ссылке; и Tu et al., Патентная заявка (США) номер 11/035991, озаглавленная "Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform", зарегистрированная 14 января 2005 года, раскрытие которой включено в состав данного документа по ссылке. Оператор перекрытия и преобразование вместе дают эффект перекрывающейся биортогональной трансформации. В качестве альтернативы, могут быть использованы дискретное косинусное преобразование или другие блочные преобразования и операторы перекрытия. Вслед за преобразованием DC-коэффициент 360 каждого блока 4×4 преобразования подвергается аналогичной цепочке обработки (разбиению, прямому перекрытию, сопровождаемому блочным преобразованием 4×4). Результирующие DC-коэффициенты преобразования и AC-коэффициенты преобразования квантуются 370, кодируются 380 по энтропии и пакетируются 390.

Декодер выполняет обратную последовательность операций. На стороне декодера биты коэффициентов преобразования извлекаются 410 из их соответствующих пакетов, из которых декодируются 420 и деквантуются 430 сами коэффициенты. DC-коэффициенты 440 регенерируются посредством применения обратного преобразования, и плоскость DC-коэффициентов «инверсно перекрывается» с использованием подходящего сглаживающего оператора, применяемого по границам DC-блоков. В дальнейшем все данные регенерируются посредством применения обратного преобразования 450 4×4 к DC-коэффициентам и AC-коэффициенты 442 декодируются из потока битов. В заключение, границы блока в плоскостях результирующего изображения фильтруются 460 с обратным перекрытием. Это вырабатывает выходной сигнал восстановленных 2D-данных.

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

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

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

Как описано выше, кодер 300 разбивает входное изображение или рисунок на макроблоки. В примерной реализации кодер 300 разбивает входное изображение на макроблоки 16×16 в канале Y (которыми могут быть области 16×16, 16×8 или 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. Для изображения формата цвета YUV4:2:2 каждый макроблок содержит 16 блоков Y 4×4 и по 8 блоков цветности (U и V) 4×4.

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

2. Обзор быстрого перекрывающегося биортогонального SIMD-преобразования

Одна из наиболее вычислительно сложных операций в вышеописанном типичном кодере 300 (Фиг.3) и декодере 400 (Фиг.4) - это перекрывающееся биортогональное преобразование. Сложность этой операции влияет на производительность как кодера, так и декодера.

Реализация перекрывающегося биортогонального преобразования, которая описана в Патентных заявках (Srinivasan, Патентная заявка (США) номер 11/015707, озаглавленная "Reversible Transform For Lossy And Lossless 2-D Data Compression", зарегистрированная 17 декабря 2004 года; Tu et al., Патентная заявка (США) номер 11/015148, озаглавленная "Reversible Overlap Operator for Efficient Lossless Data Compression", зарегистрированная 17 декабря 2004 года, и Tu et al., Патентная заявка (США) номер 11/035991, озаглавленная "Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform", зарегистрированная 14 января 2005 года), разработана так, чтобы минимизировать сложность. Тем не менее, методики распараллеливания преобразований, описанные в данном документе, достигают дополнительного ускорения за счет формулирования операций перекрывающегося преобразования способом, оптимизированным для SIMD (архитектуры с одним потоком команд и множественными потоками данных) или параллельных команд. Операции SIMD могут быть использованы для того, чтобы вычислять несколько команд параллельно. Эти команды SIMD поддерживаются для множества процессоров, в том числе процессоров семейства Pentium® компании Intel, различных x86-совместимых процессоров компании AMD, PowerPC® и множества других DSP (процессоров цифровых сигналов).

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

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

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

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

2.1. SIMD-реализация одномерного перекрывающегося биортогонального преобразования

Со ссылкой на Фиг.5 рассмотрим общий случай перекрывающегося преобразования 500, сформулированного как предварительный фильтр (оператор перекрытия) 510 и блочное преобразование 520. В случае проиллюстрированного примера блочное преобразование 520 имеет размер блока 4, а предварительный фильтр 510 также имеет размер перекрытия 4. Размер перекрытия задается как длина предварительного/пост-фильтра. Таким образом, если последовательность данных пронумерована x₀, x₁, x₂, x₃ и т.д., перекрывающееся преобразование выполняется следующим образом:

1. Предварительный фильтр 510 применяется к каждому набору входных данных [x_4i+2, x_4i+3, x_4i+4, x_4i+5], и

2. Блочное преобразование 520 применяется к каждому набору [x_4i, x_4i+1, x_4i+2, x_4i+3]. В альтернативных реализациях перекрывающееся преобразование может быть задано с другим отличным размером блочного преобразования и размером перекрытия.

Фиг.6 иллюстрирует более конкретный пример перекрывающегося биортогонального преобразования 600, который имеет формулировку предварительного фильтра и блочного преобразования, как проиллюстрировано на Фиг.5. Перекрывающееся биортогональное преобразование 600 - это преобразование, описанное выше как используемое в типичном кодере 300 (Фиг.3) и декодере 400 (Фиг.4), реализация которых подробнее поясняется в следующих Патентных заявках: Srinivasan, Патентная заявка (США) номер 11/015707, озаглавленная "Reversible Transform For Lossy And Lossless 2-D Data Compression", зарегистрированная 17 декабря 2004 года; Tu et al., Патентная заявка (США) номер 11/015148, озаглавленная "Reversible Overlap Operator for Efficient Lossless Data Compression", зарегистрированная 17 декабря 2004 года, и Tu et al., Патентная заявка (США) номер 11/035991, озаглавленная "Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform", зарегистрированная 14 января 2005 года. Для простоты предварительный фильтр и блочное преобразование кодера 300 проиллюстрированы на Фиг.6. Пост-фильтр и обратное блочное преобразование для обратного перекрывающегося преобразования в декодере - это инверсия прямого перекрывающегося преобразования 600. Как показано на Фиг.6, предварительный фильтр имеет реализацию как набор операций "бабочки" или этапов лифтинга, организованных как первая стадия 610 "бабочки", вращение/масштабирование 620 и вторая стадия 630 "бабочки". Блочное преобразование имеет реализацию как третья стадия 640 "бабочки" и вращение 650.

Один способ того, чтобы распараллелить операции для реализации, использующей команды SIMD, заключается в простой группировке аналогично проиндексированных сигнальных компонентов по блокам. Другими словами, компоненты формы x_4i+j для некоторого j группируются вместе. Для конкретного примера перекрывающегося биортогонального преобразования 600, рассмотренного в данном документе, векторами из 2 компонентов могут быть: [x₁₄ x₁₈], [x₁₅ x₁₉], [x₁₆ x₂₀] и [x₁₇ x₂₁].

Данная группировка оптимально подходит для предварительного фильтра. Тем не менее, для блочного преобразования векторы [x₁₄ x₁₈] и [x₁₆ x₂₀] охватывают три, а не два блока. Это означает, что данная группировка не может быть использована для того, чтобы достичь полного ускорения перекрывающегося преобразования. На стадии преобразования требуемая группировка отличается: [x₁₆ x₂₀], [x₁₇ x₂₁], [x₁₈x₂₂] и [x₁₉ x₂₃].

Сравнивая требуемые группировки для предварительного фильтра и блочного преобразования, можно видеть, что два вектора являются общими для обеих группировок (т.е. [x₁₆ x₂₀] и [x₁₇ x₂₁]). Тем не менее, оставшиеся два вектора различаются между группировками, что должно потребовать перегруппировку векторов между предварительным фильтром и блочным преобразованием. Это не является желательным решением.

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

Фиг.7 иллюстрирует модифицированную реализацию 700 перекрывающегося биортогонального преобразования по Фиг.6, которое распараллелено согласно методике распараллеливания преобразований, описанной в данном документе. Эта модифицированная реализация 700 перекрывающегося преобразования функционально идентична реализации 600 перекрывающегося биортогонального преобразования по Фиг.6, но она включает в себя сворачивание или перестановку 710 компонентов на первой стадии, за которой следует немного отличающаяся сеть "бабочек" 720, 740 и 750. Эти стадии "бабочек" могут быть реализованы параллельно с векторами с двумя компонентами, поскольку для этих стадий нечетные компоненты взаимодействуют только с нечетными компонентами, а четные компоненты взаимодействуют только с четными компонентами. Дополнительно, операции для нечетных компонентов и четных компонентов идентичны на этих стадиях. Таким образом, группировка соседних нечетных и четных компонентов реализует параллельную реализацию.

Тем не менее, некоторые из стадий SIMD-реализации 700 перекрывающегося биортогонального преобразования по-прежнему являются нераспараллеливаемыми. Этап 730 вращения/масштабирования в предварительном фильтре и этап 760 вращения в блочном преобразовании реализуются последовательно.

Фиг.9 иллюстрирует реализацию 900 перекрывающегося биортогонального преобразования 700 (Фиг.7), использующего компоновку данных в векторы с двумя компонентами, как показано на Фиг.8. На Фиг.9 тракты данных имеют значения векторов с двумя компонентами и полужирные стрелки - это внутривекторные операции (т.е. операции между компонентами одного вектора). Векторная группировка, показанная на Фиг.8, используется для ввода, который основан на следующем правиле отображения компонент-вектор:

v_2i = [x_4i x_4i+1]

v_2i+1 = [x_4i+3 x_4i+2]

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

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

Двумерное перекрывающееся биортогональное преобразование (2D LBT) может быть реализовано с помощью только что описанного одномерного перекрывающегося биортогонального преобразования (1D LBT). В этой реализации 1D LBT применяется к каждой строке изображения, за которой следует 1D LBT, применяемое к каждому столбцу (или наоборот). В этом случае два типа методик векторизации могут быть использованы:

1. В первом типе векторизации та же группировка, которая используется в 1D LBT (как описано в разделе 2.1 выше), может быть использована для горизонтального и вертикального преобразования.

2. Во втором типе векторизации векторы могут быть сформированы посредством группировки похожим образом индексированных компонентов нескольких строк при реализации 1D LBT по строкам и группировки похожим образом индексированных компонентов нескольких столбцов при реализации 1D LBT по столбцам.

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

Дополнительно, 2D LBT, описанное в вышеперечисленных Патентных заявках (т.е. Srinivasan, Патентная заявка (США) номер 11/015707, озаглавленная "Reversible Transform For Lossy And Lossless 2-D Data Compression", зарегистрированная 17 декабря 2004 года, и Tu et al., Патентная заявка (США) номер 11/035991, озаглавленная "Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform", зарегистрированная 14 января 2005 года), реализует LBT непосредственно в двух измерениях. Это преобразование не может быть разделено на две одномерные операции.

Для распараллеленной SIMD-версии этой прямой реализации 2D LBT (а также для отделяемой 2D-реализации) двунаправленно сворачиваемое переотображение 1000-1001 сначала применяется, как показано на Фиг.10. Каждый блок пикселов 4×4 в области 1010 отображается 1000-1001 в четыре вектора с 4 компонентами в области 1020, так что каждый вектор содержит пикселы из субблоков 2×2 блока 4×4. Упорядочивание компонентов в векторах следует двумерному расширению одномерного переотображения (перестановке 710, проиллюстрированной на Фиг.7), описанного выше. Фиг.11 иллюстрирует векторную запись 1100 для результирующего набора векторов с 4 компонентами в области 1020.

Векторы с 4 компонентами, таким образом сформированные, имеют такое свойство, что группы 4 пикселов, к которым применяются преобразования Адамара либо на стадии оператора перекрытия, либо на стадии блочного преобразования прямого 2D LBT, совмещаются в одной позиции в векторах. Это проиллюстрировано на Фиг.12 для оператора перекрытия и на Фиг.13 для архитектуры Photon Core Transform, и подробнее поясняется ниже.

2.2.1. Параллельная реализация оператора перекрытия в SIMD-реализации двумерного перекрывающегося биортогонального преобразования

Со ссылкой снова на Фиг.5 оператор перекрытия (предварительный фильтр 510) в перекрывающемся преобразовании применяется по границам блоков. Это может быть осуществлено до или после блочного преобразования 520.

В случае реализации 2D LBT, описанной в вышеперечисленных Патентных заявках (т.е. Srinivasan, Патентная заявка (США) номер 11/015707, озаглавленная "Reversible Transform For Lossy And Lossless 2-D Data Compression", зарегистрированная 17 декабря 2004 года, и Tu et al., Патентная заявка (США) номер 11/035991, озаглавленная "Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform", зарегистрированная 14 января 2005 года), оператор преобразования применяется до блочного преобразования на стороне кодера. Аналогично, он применяется после обратного блочного преобразования на стороне декодера. Не учитывая специальные случаи на границах изображения, оператор перекрытия применяется к области 4×4, охватывающей 4 блока 4×4.

Со ссылкой на Фиг.14 оператор 1400 перекрытия этой реализации 2D LBT состоит из двух преобразований 1410 Адамара 2×2, применяемых к четверкам пикселов, размещенных симметрично в решетке, после чего следует стадия 1420 и 1430 вращения и масштабирования, после чего следует еще одно преобразование 1440 Адамара 2×2, применяемое к тем же четверкам пикселов. Подробные сведения по операциям представлены в Tu et al., Патентная заявка (США) номер 11/035991, озаглавленная "Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform", зарегистрированная 14 января 2005 года. Дополнительное упрощение может быть использовано в формулировке 2D LBT, как описано в этой Патентной заявке, где стадия масштабирования и одна из стадий Адамара 2×2 сокращает некоторые операции.

Для распараллеленной SIMD-версии этого оператора перекрытия сначала применяется та же процедура векторизации, что и описана в разделе 2.2 выше и показана на Фиг.10 и 11. Со ссылкой на Фиг.15 распараллеленная SIMD-версия оператора перекрытия на основе этих векторизованных данных реализуется согласно следующему процессу 1500:

1. Как указано на этапе 1510, изображение или другая рабочая область двумерных данных векторизуется в векторы с 4 компонентами, как показано на Фиг.10 и 11.

2. Операция перекрытия на этапах 1520-1570 выполняется для каждой области перекрытия 4×4, охватывающей 4 блока 1200 4×4 для изображения, как проиллюстрировано на Фиг.12. Для этой операции используются векторы, идентифицированные как [v₃ v₆ v₉ v₁₂] с помощью векторной записи, показанной на Фиг.11. Эти этапы повторяются для всех таких областей.

3. Сначала выполняется операция Адамара 2×2 для этих 4 векторов на этапе 1530.

4. Для следующего этапа 1540 операция масштабирования (которая подробно описана в Патентных заявках Tu et al., Патентная заявка (США) номер 11/015148, озаглавленная "Reversible Overlap Operator for Efficient Lossless Data Compression", зарегистрированная 17 декабря 2004 года, и Tu et al., Патентная заявка (США) номер 11/035991, озаглавленная "Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform", зарегистрированная 14 января 2005 года) выполняется между векторами V₃ и V₁₂.

5. Вращения 1550 выполняются в рамках компонентов векторов v₆, v₉ и v₁₂. Это наиболее последовательные операции, которые по большей части не используют параллелизм данных.

6. В завершение, операция Адамара 2×2 повторно выполняется на этапе 1560 для векторов [v₃ v₆ v₉ v₁₂] области перекрытия.

В процессе 1500 вышеуказанные операции выполняются все над указанными векторами. Дополнительно, на практике имеются определенные отмены между этапами 3 и 4 выше, которые приводят к дополнительным упрощениям, как подробно описано в Патентных заявках: Tu et al., Патентная заявка (США) номер 11/015148, озаглавленная "Reversible Overlap Operator for Efficient Lossless Data Compression", зарегистрированная 17 декабря 2004 года, и Tu et al., Патентная заявка (США) номер 11/035991, озаглавленная "Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform", зарегистрированная 14 января 2005 года.

2.2.2. Параллельная реализация блочного преобразования в SIMD-реализации двумерного перекрывающегося биортогонального преобразования

После того как оператор перекрытия применяется ко всем субблокам 2×2 в рамках блока, блок 1300 4×4 (Фиг.13) готов к тому, чтобы подвергнуться блочному преобразованию. Операция блочного преобразования сохраняет такую же векторизацию, следовательно, не обязательно перераспределять данные между операциями перекрытия и блочного преобразования.

Со ссылкой на Фиг.16 параллельная реализация блочного преобразования выполняется согласно следующему процессу 1600. Процесс начинается с изображения или рабочей области, по-прежнему векторизованной посредством этапа 1510 (Фиг.15) для оператора перекрытия, как показано на Фиг.10 и 11. С другой стороны, в случаях когда блочное преобразование применяется только к двумерным данным без применения сначала процесса 1500 оператора перекрытия, процесс 1600 вместо этого начинается посредством выполнения этапа 1510, чтобы предоставить такую же векторизацию.

1. В цикле этапов 1610-1640 преобразование применяется к каждому блоку 1300 4×4 изображения. Например, векторы [v₀ v₁ v₂ v₃], показанные на Фиг.13, используются для верхнего левого блока. Эти этапы повторяются для всех блоков.

2. На первом этапе 1620 операция преобразования Адамара 2×2 выполняется для этих 4 векторов.

3. На следующем этапе 1630 вращения выполняются в компонентах векторов v₀, v₁, v₂ и v₃. Это наиболее последовательные операции, которые по большей части не используют параллелизм данных. Выполняемые вращения подробно описаны в Патентных заявках: Srinivasan, Патентная заявка (США) номер 11/015707, озаглавленная "Reversible Transform For Lossy And Lossless 2-D Data Compression", зарегистрированная 17 декабря 2004 года, и Tu et al., Патентная заявка (США) номер 11/035991, озаглавленная "Reversible 2-Dimensional Pre-/Post-Filtering For Lapped Biorthogonal Transform", зарегистрированная 14 января 2005 года.

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

2.3. Расширения

Для процессов оператора 1500 перекрытия и преобразования 1600, четырехстороннее преобразование Адамара 2×2 является фундаментальной и повторяющейся операцией. При компонентах данных, упорядоченных посредством векторизации, проиллюстрированной на Фиг.10 и 11, Адамар 2×2 легко выполняется как SIMD-команды, работающие для этих векторов. Дополнительно, для оператора перекрытия операция масштабирования подобным образом может быть выполнена как SIMD-команды, работающие для этих векторов. Вращения (этапы 1550, 1630) являются частично параллелизованными. Это обусловлено тем, что некоторые из включенных вращений идентичны одномерным операциям, которые выполняются для двух пар точек данных в векторе с 4 компонентами. Эти вращения также могут быть параллелизованы с помощью операций умножения и сдвига.

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

Такая же методика распараллеливания применяется для обратного перекрывающегося биортогонального преобразования за исключением того, что порядок блочного преобразования и оператора перекрытия изменен на противоположный и порядок этапов 1530-1560 и 1620-1630 в соответствующих процессах изменен на противоположный. Переупорядоченный шаблон сканирования используется для того, чтобы заполнять матрицу входных данных, и выходные данные в дальнейшем переотображаются способом, обратным отображению, показанному на Фиг.10.

Методика распараллеливания также применяется для альтернативных реализаций, использующих версии перекрывающихся ортогональных/биортогональных преобразований. Как упоминалось в пояснении к процессу 1600 блочного преобразования, параллелизация также может быть использована для блочных преобразований как таковых (т.е. без оператора перекрытия). Размеры преобразования и перекрытия, отличные от 4, и размерности, превышающие 2, также могут охватываться посредством простого расширения логики распараллеливания.

Затраты на векторизацию минимизируются посредством выполнения переотображения к свернутой структуре в кодере и переотображения от свернутой структуры в декодере в ходе стадии преобразования цветов. Преобразование цветов в декодере, в общем, реализуется последовательно по нескольким причинам, включающим в себя (i) множество форматов цвета, (ii) отсутствие выравнивания по границе слова вследствие 24-битовых пиксельных границ многих форматов цвета, (iii) необходимость выполнять отсечение на стороне декодера и т.д. Дополнительные затраты на переотображение сверх преобразования цветов являются минимальными и упрощают использование этой методики распараллеливания для общего повышения производительности. Дополнительно, когда входное изображение представлено в повернутой и/или горизонтально обращенной ориентации или когда выходное изображение нужно повернуть или горизонтально обратить, это может быть достигнуто практически без увеличения общей вычислительной сложности.

3. Вычислительное окружение

Вышеописанные примерные кодер 300 (Фиг.3) и декодер 400 (Фиг.4), содержащие в себе перекрывающееся биортогональное преобразование, реализованное с помощью технологий распараллеливания преобразований, могут быть выполнены на любом из множества устройств, в котором выполняется обработка цифровых мультимедийных сигналов, в том числе (помимо других примеров) на компьютерах; на оборудовании для записи, передачи и приема изображений и видео; на портативных видеопроигрывателях; в устройствах видеоконференц-связи и т.д. Методики кодирования цифрового мультимедиа могут быть реализованы в аппаратной схемотехнике, а также в программном обеспечении обработки цифрового мультимедиа, исполняемом на компьютере или в другом вычислительном окружении, таком как показанное на Фиг.17.

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

Ссылаясь на Фиг.17, вычислительное окружение (1700) включает в себя, по меньшей мере, один процессор (1710) и память (1720). На Фиг.17 эта самая базовая конфигурация (1730) показана пунктирной линией. Процессор (1710) приводит в исполнение машиноисполняемые инструкции и может быть реальным или виртуальным процессором. В многопроцессорной системе несколько процессоров приводят в исполнение машиноисполняемые инструкции, чтобы повысить вычислительную мощность. Памятью (1720) может быть энергозависимая память (например, регистры, кэш, ОЗУ (оперативное запоминающее устройство, RAM), энергонезависимая память (например, ПЗУ (постоянное запоминающее устройство, ROM), ЭСППЗУ (электрически стираемое и программируемое ПЗУ, EEPROM), флэш-память и т.д.) или некоторое сочетание из двух. Память (1720) сохраняет программное обеспечение (1780), реализующее описанные методики кодирования/декодирования цифрового мультимедиа и распараллеливания преобразований.

Вычислительное окружение может обладать дополнительными признаками. Например, вычислительное окружение (1700) включает в себя запоминающее устройство (1740), устройства (1750) ввода, одно или более устройств (1760) вывода и одно или более соединений (1770) связи. Механизм межкомпонентного соединения (не показан), такой как шина, контроллер или сеть соединяет между собой компоненты вычислительного окружения (1700). В типичном варианте программное обеспечение операционной системы (не показано) предоставляет операционное окружение для другого программного обеспечения, приводимого в исполнение в вычислительном окружении (1700), и координирует действия компонентов вычислительного окружения (1700).

Запоминающее устройство (1740) может быть съемным или несъемным и включает в себя магнитные диски, магнитные ленты или кассеты, CD-ROM (ПЗУ на компакт диске), CD-RW (многократно перезаписываемый компакт диск), DVD (универсальный цифровой диск) или любой другой носитель, который может быть использован, чтобы сохранять информацию и к которому можно осуществлять доступ в пределах вычислительного окружения (1700). Запоминающее устройство (1740) сохраняет инструкции для программного обеспечения (1780), реализующего описанные кодер/декодер с помощью методик распараллеливания преобразований.

Устройством(ами) (1750) ввода может быть устройство сенсорного ввода, такое как клавиатура, мышь, перо или шаровой манипулятор, устройство голосового ввода, устройство сканирования или другое устройство, которое обеспечивает ввод в вычислительное окружение (1700). Для звука устройством(ами) (1750) ввода может быть звуковая плата или аналогичное устройство, которое принимает звуковой входной сигнал в аналоговой или цифровой форме, либо считыватель CD-ROM, который поставляет звуковые выборки в вычислительное окружение. Устройством(ами) (1760) вывода может быть дисплей, принтер, динамик, устройство для записи CD-RW или другое устройство, которое обеспечивает вывод из вычислительного окружения (1700).

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

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

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

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

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

Изобретение относится способам кодирования цифровых данных. Технический результат заключается в повышении скорости кодирования и декодирования цифровых данных. Основанный на блочном преобразовании цифровой мультимедийный кодек достигает большей производительности посредством переотображения компонентов цифровых мультимедийных данных в векторы или параллельные единицы, над которыми многие операции преобразований могут быть выполнены на основе архитектуры с одним потоком команд и множественными потоками данных. В случае одномерного перекрывающегося биортогонального преобразования компоненты цифровых мультимедийных данных переотображаются в векторы, для которых стадии "бабочки" частей предварительного/пост-фильтра перекрытия и блочного преобразования могут быть выполнены на основе SIMD. В случае двумерного перекрывающегося биортогонального преобразования компоненты цифровых мультимедийных данных переотображаются в векторы, над которыми оператор Адамара предварительного/пост-фильтра перекрытия и блочного преобразования может быть выполнен на основе SIMD. 6 н. и 27 з.п. ф-лы, 17 ил.

1. Способ кодирования цифровых мультимедийных данных, содержащий этапы, на которых:
переотображают (710, 1000, 1001) компоненты блоков входных цифровых мультимедийных данных (1010) в набор векторов (1020, 800), к которым операции (720, 730, 740, 750, 760, 1410, 1420, 1430, 1440) перекрывающегося преобразования могут быть применены по компонентам блоков на основе одной команды и множества данных;
применяют перекрывающееся преобразование (350) к блокам цифровых мультимедийных данных, чтобы сформировать набор коэффициентов (360, 362) преобразования для соответствующих блоков, при этом применение перекрывающегося преобразования заключается в том, что выполняют, по меньшей мере, одну операцию на основе одной команды и множества данных над векторами компонентов блока; и
кодируют коэффициенты преобразования (380) в сжатом потоке битов.

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

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

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

5. Способ по п.2, в котором векторами являются векторы с четырьмя компонентами.

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

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

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

9. Способ по п.6, в котором векторами являются векторы с двумя компонентами.

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

11. Машиночитаемый носитель, несущий кодированный поток битов, закодированный согласно способу, который содержит этапы, на которых:
переотображают (710, 1000, 1001) компоненты блоков входных цифровых мультимедийных данных (1010) в набор векторов (1020, 800), к которым операции (720, 730, 740, 750, 760, 1410, 1420, 1430, 1440) перекрывающегося преобразования могут быть применены по компонентам блоков на основе одной команды и множества данных;
применяют перекрывающееся преобразование (350) к блокам цифровых мультимедийных данных, чтобы сформировать набор коэффициентов (360, 362) преобразования для соответствующих блоков, при этом применение перекрывающегося преобразования заключается в том, что выполняют, по меньшей мере, одну операцию на основе одной команды и множества данных над векторами компонентов блока; и
кодируют коэффициенты преобразования (380) в сжатом потоке битов.

12. Цифровой мультимедийный кодер, содержащий:
буфер хранения данных для сохранения цифровых мультимедийных данных (310, 320), которые должны быть закодированы;
процессор (1710), запрограммированный, чтобы:
упорядочивать элементы блоков (1010) цифровых мультимедийных данных в набор векторов (800, 1020), к которым, по меньшей мере, некоторые операции (720, 730, 740, 750, 760, 1410, 1420, 1430, 1440) перекрывающегося преобразования могут быть применены по компонентам блоков на основе одной команды и множества данных;
применять перекрывающееся преобразование (350) к блокам цифровых мультимедийных данных, при этом применение перекрывающегося преобразования заключается в выполнении, по меньшей мере, нескольких операций на основе одной команды и множества данных над векторами блока; и
кодировать (380) цифровые мультимедийные данные в сжатый поток битов.

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

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

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

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

17. Машиночитаемый носитель, хранящий машиноисполняемую программу обработки цифровых мультимедийных данных для осуществления способа обработки цифровых мультимедийных данных, при этом способ содержит этапы, на которых:
переотображают (710, 1000, 1001) компоненты блоков цифровых мультимедийных данных (1010) в набор векторов (1020, 800), к которым операции (720, 730, 740, 750, 760, 1410, 1420, 1430, 1440) перекрывающегося преобразования могут быть применены по компонентам блоков на основе одной команды и множества данных;
применяют перекрывающееся преобразование (350) к блокам цифровых мультимедийных данных, чтобы сформировать набор коэффициентов (360, 362) преобразования для соответствующих блоков, при этом применение перекрывающегося преобразования заключается в том, что выполняют, по меньшей мере, несколько операций на основе одной команды и множества данных над векторами компонентов блока; и
кодируют (380)/декодируют (420) цифровые мультимедийные данные в/из сжатого потока битов.

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

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

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

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

22. Способ по п.21, в котором, по меньшей мере, одна операция инверсного фильтра перекрытия и, по меньшей мере, одна операция инверсного блочного преобразования каждая содержит преобразование Адамара 2×2.

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

24. Способ по п.21, в котором векторами являются векторы с четырьмя компонентами.

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

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

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

28. Способ по п.25, в котором векторами являются векторы с двумя компонентами.

29. Цифровой мультимедийный декодер, содержащий:
буфер хранения данных для сохранения цифровых мультимедийных данных (310, 320), которые должны быть декодированы;
процессор (1710), запрограммированный, чтобы:
декодировать (420) цифровые мультимедийные данные из сжатого потока битов;
применять инверсное перекрывающееся преобразование (450) к блокам (1010) цифровых мультимедийных данных, при этом применение перекрывающегося преобразования заключается в выполнении, по меньшей мере, нескольких операций на основе одной команды и множества данных над векторами (800, 1020) блока; и
упорядочивать элементы блоков цифровых мультимедийных данных из набора векторов.

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

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

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

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