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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

Кодирование с преобразованием - это технология сжатия, используемая во многих системах сжатия звука, изображений и видео. Несжатое цифровое изображение и видео типично представляется или захватывается в виде дискретных выборок элементов или цветов картинки на позициях в кадре изображения или видео, скомпонованном в двумерной (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 года), оператор преобразования применяется до блочного преобразования н