Уменьшение ошибок во время вычисления обратного дискретного косинусного преобразования

Уменьшение ошибок во время вычисления обратного дискретного косинусного преобразования

Иллюстрации

Показать все

Реферат

По настоящей заявке на патент испрашивается приоритет по дате подачи предварительной заявки США №60/816697, поданной 26 июня 2006, предварительной заявки США №60/841362, поданной 30 августа 2006, предварительной заявки США №60/847194, поданной 25 сентября 2006, предварительной заявки США №60/829669, поданной 16 октября 2006, и предварительной заявки США №60/869530, поданной 11 декабря 2006, которые полностью включены в этот документ по ссылке.

Область техники, к которой относится изобретение

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

Предшествующий уровень техники

Во многих существующих стандартах кодирования видео и изображения используются способы сжатия для обеспечения возможности сохранения или передачи видео и изображений с высоким разрешением как относительно компактных файлов или потоков данных. Такие стандарты кодирования включают в себя стандарт сжатия неподвижного изображения (JPEG), разработанный группой экспертов по видео, международный стандарт сжатия видео- и аудиоданных (MPEG)-1, MPEG-2, часть 2 MPEG-4, H.261, H.263 и другие стандарты кодирования видео или изображения.

Согласно многим из этих стандартов видеокадры сжимают с использованием "пространственного" кодирования. Эти кадры могут быть исходными кадрами (то есть i-кадрами) или могут быть остаточными кадрами, сформированными посредством временного кодирования, которое использует компенсацию движения. Во время пространственного кодирования кадры разбиваются на блоки пикселей равного размера. Например, несжатый кадр может быть разбит на ряд блоков пикселей 8×8. Для каждого блока пикселей компоненты пикселя разделяются на матрицы значений компонентов пикселя. Например, каждый блок пикселей может быть разделен на матрицу значений компонента пикселя Y, матрицу значений компонента пикселя U и матрицу значений компонента пикселя V. В этом примере, значения компонента пикселя Y указывают значения яркости, и значения компонентов пикселя U и V представляют значения информации о цвете.

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

где s - массив N исходных значений, t - массив N преобразованных значений и коэффициенты c задаются посредством

для 1≤k≤N-l.

Идеальное двумерное FDCT определяется формулой

где s - массив N исходных значений, t - массив N преобразованных значений и c(i,j) задается посредством c(i,j)=c(i)c(j), и причем c(k) определяется, как в одномерном случае.

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

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

где s - массив N исходных значений, t - массив N преобразованных значений и коэффициенты c задаются посредством

для 1≤k≤N-l.

Идеальное двумерное IDCT определяется формулой

Далее получающиеся в результате матрицы значений компонента пикселя снова собираются в блоки пикселей, и эти блоки пикселей снова собираются для формирования декодированного кадра. Если декодированный кадр является i-кадром, то этот кадр теперь полностью декодирован. Однако если несжатый кадр является p- (прогнозным) или b- (бипрогнозным) кадром, то декодированный кадр является только декодированным остаточным кадром. Законченный кадр формируется посредством создания восстановленного кадра с использованием векторов движения, связанных с декодированным кадром, и последующего суммирования восстановленного кадра с декодированным остаточным кадром.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Фиг.6 - блок-схема, изображающая иллюстративные детали модуля обратного дискретного косинусного преобразования ("IDCT").

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

Фиг.8 - блок-схема, изображающая иллюстративные детали модуля прямого дискретного косинусного преобразования ("FDCT").

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

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

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

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

Подробное описание

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

Устройство 2 может включать в себя источник 4 мультимедиа для формирования мультимедийных данных. Источник 4 мультимедиа может содержать цифровую видео- или фотокамеру для ввода данных изображения. Источник 4 мультимедиа может быть встроен в устройство 2 или может быть присоединен к устройству 2 как периферийное устройство. Источник 4 мультимедиа может также содержать микрофон для записи звуковых данных. Источник 4 мультимедиа может обеспечивать мультимедийные данные в процессор 6. Процессор 6 может содержать цифровой сигнальный процессор ("DSP"), микропроцессор или некоторый другой тип интегральной схемы.

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

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

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

Драйвер 13 воспроизведения в устройстве 2 вызывает воспроизведение блоком 14 воспроизведения мультимедиа мультимедийных данных, декодированных модулем 12 декодирования. Например, блок 14 воспроизведения мультимедиа может содержать компьютерный монитор, который воспроизводит мультимедийные данные видео или изображения. В другом примере блок 14 воспроизведения мультимедиа может содержать устройство вывода звука (например, динамик), которое воспроизводит звуковые мультимедийные данные. Блок 14 воспроизведения мультимедиа может быть встроен в устройство 2 или может быть связан с ним через проводную или беспроводную линию связи как периферийное устройство. Драйвер 13 воспроизведения может содержать драйвер устройства или другие программные средства, аппаратный или программно-аппаратный блок или некоторый другой механизм, который вызывает воспроизведение мультимедийных данных блоком 14 воспроизведения мультимедиа.

Устройство 2 может также содержать сетевой интерфейс 16. Сетевой интерфейс 16 может обеспечивать связь между устройством 2 и компьютерной сетью через проводную или беспроводную линию связи. Например, сетевой интерфейс 16 может обеспечивать связь между устройством 2 и сетью мобильной радиотелефонной связи. Устройство 2 может принимать файлы мультимедиа через сетевой интерфейс 16. Например, устройство 2 может принимать фотографии, видеоклипы, потоковое видео (например, телевидение, видеоконференцию, кинофильмы), аудиоклипы (например, мелодии для звонка, песни, файлы MP3), потоковое аудио (например, цифровые радиостанции, речевые вызовы и т.д.) через сетевой интерфейс 16. Когда сетевой интерфейс 16 принимает битовый поток видео или файла мультимедиа, сетевой интерфейс 16 может сохранять этот битовый поток видео или файла мультимедиа в репозитории 10 мультимедиа.

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

Когда модуль 8 кодирования кодирует последовательность видеокадров, модуль 8 кодирования может начинать с выбора тех видеокадров, которые должны быть "i-кадрами". Например, модуль 8 кодирования может выбирать каждый восьмой кадр как i-кадр. I-кадры являются кадрами, которые не ссылаются на другие кадры. После выбора i-кадров модуль 8 кодирования использует "пространственное кодирование" для кодирования i-кадров. Кроме того, модуль 8 кодирования может использовать "временное кодирование" для кодирования оставшихся кадров.

Для использования пространственного кодирования для кодирования кадра модуль 8 кодирования может разбивать данные кадра на блоки пикселей. Например, модуль 8 кодирования может разбивать данные кадра на блоки пикселей, восемь пикселей шириной и восемь пикселей высотой (то есть каждый блок пикселей содержит 64 пикселя). После этого модуль 8 кодирования может разделять значения компонентов пикселя пикселей в каждом блоке пикселей на отдельные матрицы значений компонента пикселя. Значения компонентов пикселя одного пикселя являются значениями, которые характеризуют вид пикселя. Например, каждый пиксель может специфицировать значение компонента пикселя Y, значение компонента пикселя Cr и значение компонента пикселя Cb. Значение компонента пикселя Y указывает яркость пикселя, значение компонента пикселя Cr указывает информацию о красном цвете пикселя, и значение компонента пикселя Cb указывает информацию о синем цвете пикселя. В этом примере, когда модуль 8 кодирования разделяет значения компонентов пикселя блока пикселей, модуль 8 кодирования может получать матрицу значений компонента пикселя Y, матрицу значений компонента пикселя Cr и матрицу значений компонента пикселя Cb.

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

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

где s - массив N исходных значений, t - массив N преобразованных значений и коэффициенты c задаются посредством

для 1≤k≤N-l.

Идеальное двумерное FDCT определяется формулой

где s - массив N исходных значений, t - массив N преобразованных значений и c(i,j) задается посредством c(i,j)=c(i)c(j), и причем c(k) определяется, как в одномерном случае.

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

Для использования временного кодирования для кодирования кадра модуль 8 кодирования может разделять кадр на "макроблоки". В зависимости от используемого стандарта кодирования эти макроблоки могут иметь фиксированный или переменный размер и могут быть перекрывающимися или неперекрывающимися. Например, каждый макроблок может быть блоком пикселей 16×16. Для каждого макроблока в кадре модуль 8 кодирования 8 может пытаться идентифицировать исходный макроблок в одном или нескольких кадрах ссылки. В зависимости от стандарта кодирования кадры ссылки могут быть i-кадрами, p-кадрами или b-кадрами. Если модуль 8 кодирования может идентифицировать исходный макроблок в кадре ссылки, то модуль 8 кодирования записывает вектор движения для этого макроблока. Вектор движения включает в себя значение x, которое указывает горизонтальное перемещение макроблока относительно идентифицированного исходного макроблока, и значение y, которое указывает вертикальное перемещение макроблока относительно идентифицированного исходного макроблока. Если модуль 8 кодирования не может идентифицировать исходный макроблок для упомянутого макроблока, то может не потребоваться запись вектора движения модулем 8 кодирования для этого макроблока. Затем модуль 8 кодирования формирует "восстановленный" кадр. Восстановленный кадр содержит кадр, который получается в результате перемещения макроблоков из кадров ссылки согласно записанным векторам движения для текущего кадра. После формирования восстановленного кадра модуль 8 кодирования вычитает значения компонентов пикселя в каждом пикселе восстановленного кадра из соответствующих значений компонентов пикселя в соответствующих пикселях текущего кадра, в результате чего получается "остаточный" кадр. После этого модуль 8 кодирования может использовать схему энтропийного кодирования для сжатия векторов движения для макроблоков текущего кадра. Кроме того, модуль 8 кодирования использует описанный выше способ пространственного кодирования для сжатия остаточного кадра.

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

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

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

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

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

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

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

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

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

Способы, описанные в этом раскрытии, могут обеспечить несколько преимуществ. Например, уменьшение ошибок округления во время вычисления дискретного косинусного преобразования и обратного дискретного косинусного преобразования может уменьшить видимые ошибки в данных изображения и может уменьшить слышимые ошибки в звуковых данных. Кроме того, так как эти способы можно применять к вычислениям с фиксированной запятой, то эти способы могут быть применены в меньших, менее сложных устройствах, например мобильных телефонах, персональных цифровых секретарях и личных медиаплеерах. В частности, упомянутые способы могут быть применены с использованием чисел с фиксированной запятой, части мантиссы которых имеют очень ограниченное количество битов (например, три бита), при этом выполняются требования по точности, специфицированные стандартом 1180 Института инженеров по электротехнике и радиоэлектроники (IEEE), все содержимое которого включено в этот документ по ссылке. Кроме того, эти способы могут быть применены к форматам, которые включают в себя рекомендации H.261, H.263, H.264, T.81 (JPEG) сектора стандартизации (электросвязи) Международного союза электросвязи (ITU-T), а также форматы мультимедиа Международной организации по стандартизации (ISO)/MEC Группы экспертов по видео (MPEG)-1, MPEG-2 и Части 2 MPEG-4.

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

Как изображено в примере фиг.2, модуль 8 кодирования включает в себя модуль 20 управления кадром, который управляет тем, обрабатывает ли модуль 8 кодирования видеокадр как i-кадр, p-кадр или b-кадр. Например, когда модуль 8 кодирования принимает видеокадр, модуль 20 управления кадром может устанавливать флажок битового потока, связанный с этим видеокадром, указывает, что кадр является i-кадром, p-кадром или b-кадром. Если модуль 20 управления кадром устанавливает, что флажок битового потока указывает, что кадр является i-кадром, то модуль 20 управления кадром может вызвать обработку видеокадра набором модулей, которые непосредственно выполняют пространственное кодирование видеокадра. С другой стороны, если модуль 20 управления кадром устанавливает, что кадр является p-кадром или b-кадром, то модуль 20 управления кадром может вызвать обработку видеокадра набором модулей, которые выполняют временное кодирование.

Модуль 8 кодирования включает в себя последовательность модулей для применения пространственного кодирования к видеокадрам. Эти модули включают в себя модуль 22 разделителя на блоки, модуль 24 выделения компонента, модуль 26 прямого преобразования, модуль 28 квантования и модуль 30 энтропийного кодирования. Модуль 22 разделителя на блоки может п