Адаптивный порядок сканирования коэффициентов

Изобретение относится к системам сжатия аудиовизуальных данных, и в частности к основанному на блочном преобразовании сжатию видео и изображений. Техническим результатом является обеспечение адаптивного упорядочивания сканирования коэффициентов для эффективного и быстрого согласования порядка сканирования блочных коэффициентов с локальной статистикой изображения. Указанный технический результат достигается тем, что кодек цифровых аудиовизуальных данных адаптивно перекомпоновывает порядок сканирования коэффициентов преобразования в соответствии с локальной статистикой цифровых аудиовизуальных данных, чтобы коэффициенты могли кодироваться более эффективно с использованием энтропийного кодирования. Адаптивное упорядочивание сканирования применяется причинно-следственным образом при кодировании и декодировании, чтобы избежать явной сигнализации порядка сканирования декодеру в цифровом потоке сжатых аудиовизуальных данных. Адаптивный порядок сканирования перекомпоновывает порядок сканирования, применяя операцию условного обмена к упорядоченным по соседству позициям коэффициентов, посредством одиночного прохода порядка сканирования при каждом обновлении данных статистического анализа. 3 н. и 17 з.п. ф-лы, 13 ил.

 

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

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

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

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

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

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

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

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

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

Используемое преобразование может быть реализовано простым экстраполятором/корректором DPCM-типа (дифференциальной импульсно-кодовой модуляции), или более сложными структурами, такими как вейвлеты (волновые преобразования) или DCT (дискретные косинусные преобразования). Широко применяемые стандарты JPEG/MPEG2/MPEG4, JPEG2000 и Windows Media Video (WMV) используют соответственно DCT, вейвлет и приведенное к целочисленным коэффициентам DCT. В дополнение, WMV использует оператор сглаживания с перекрытием, который обеспечивает преимущества по зрительному восприятию и по искажениям в зависимости от скорости передачи для блоков внутреннего кодирования и кадров внутреннего кодирования. Оператор сглаживания с перекрытием, во взаимосвязи с блочным преобразованием, стремится имитировать преобразование с перекрытием типа, описанного в Н.S.Malvar, Signal Processing with Lapped Transforms, Artech House, Boston, MA, 1992.

Схемы сканирования коэффициентов

Многие основанные на блочном преобразовании кодеки, в том числе JPEG, MPEG2, MPEG4 и WMV, используют технологию кодирования длин серий, чтобы кодировать квантованные коэффициенты, соответствующие конкретному блоку (например, W.В.Pennebaker and J.L.Mitchell, JPEG: Still Image Compression Standard, Van Nostrand Reinhold, New York, 1993). Кодирование длин серий осуществляется сканированием блока квантованных коэффициентов преобразования согласно заранее заданной схеме. Одним из таких примеров является непрерывная «зигзагообразная» схема сканирования, показанная на фиг.3. Нет обязательного требования, чтобы схема сканирования была непрерывной, хотя подобные непрерывные зигзагообразные схемы сканирования широко используются в стандартных JPEG и MPEG2/4.

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

Система сжатия видео, которая осуществляет выбор среди ограниченного набора заранее заданных или статических схем сканирования, к примеру, в зависимости от размеров блока и от того, находится ли изображение в чересстрочном или последовательным формате, описана в патентных заявках США №10/989,844 на имя Lin et al., «Scan Patterns For Interlaced Video Content» («Схемы сканирования для чересстрочного видеоконтента»), от 15.11.2004; и №10/989,594 на имя Liang et al., «Scan Patterns For Progressive Video Content» («Схемы сканирования для последовательного видеоконтента») от 15.11.2004.

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

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

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

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

Есть третья причина для неоптимальности заданного порядка сканирования для ряда блоков изображения. Это основано на изменяющейся результативности «DCAC-предсказание». DCAC-предсказание является инструментальным средством кодирования, которое используется, чтобы минимизировать появление и/или величину коэффициентов «DCAC», которые являются DC по Х или Y-измерениям и AC - по остальным. Они являются коэффициентами, лежащими вдоль осей. Для строго линейных областей DCAC-коэффициенты могут быть предсказаны с большей степенью достоверности, чем для случайно текстурированных областей. Следовательно, наилучший порядок сканирования не только зависит от лежащих в основе данных, но и на него также оказывается влияние тем, насколько хорошо лежащие в основе данные могут быть предсказаны своими DCAC-коэффициентами.

Адаптивный порядок сканирования коэффициентов

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

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

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

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

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

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

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

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

Фиг.6 - блок-схема алгоритма процедуры для адаптации порядка сканирования коэффициентов в кодере по фиг.4 и декодере по фиг.5.

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

Фиг.8 - диаграмма, иллюстрирующая начальный порядок

сканирования горизонтальных коэффициентов для процедуры адаптивного порядка сканирования коэффициентов по фиг.6.

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

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

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

Фиг.12 - диаграмма, иллюстрирующая результирующий порядок сканирования коэффициентов, соответствующий компоновке, показанной на фиг.11 для элементов массивов по фиг.9, после операции перестановки элементов, показанной на фиг.10.

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

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

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

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

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

Кодер 400 2D-данных вырабатывает сжатый битовый поток 420, который является более компактным представлением (для типового ввода) 2D-данных 410, представленных в качестве входного сигнала кодера. Например, входным сигналом 2D-данных может быть изображение, кадр видеопоследовательности или другие данные, имеющие два измерения. Кодер 2D-данных фрагментирует (430) входные данные на макроблоки, которые в этом иллюстративном кодере имеют размер 16×16 пикселей. Кодер 2D-данных дополнительно фрагментирует макроблок на блоки 432 4×4. К каждой границе между блоками применяется оператор 440 «прямого 12 перекрытия», после которого каждый блок 4×4 преобразуется с использованием блочного преобразования 450. Это блочное преобразование 450 может быть обратимым безразмерным 2D-преобразованием, описанным в патентной заявке США на имя Srinivasan, «Improved Reversible Transform For Lossy And Lossless 2-D Data Compression» («Усовершенствованное обратимое преобразование для сжатия 2D-данных с потерями и без потерь»), от 17.12.2004. Оператор перекрытия может быть обратимым оператором перекрытия, описанным в патентной заявке США на имя Tu et al., «Reversible Overlap Operator For Efficient Lossless Data Compression» («Обратимый оператор перекрытия для эффективного сжатия данных без потерь»), от 17.12.2004. В качестве альтернативы могут быть использованы дискретное косинусное преобразование или другие блочные преобразования, преобразования с перекрытием и операторы перекрытия. Вслед за преобразованием, DC-коэффициент каждого блока 4×4 преобразования подвергается аналогичной цепочке обработки (разбиению, прямому перекрытию с последующим блочным преобразованием 4×4). Результирующие коэффициенты DC-преобразования и АС-преобразования квантуются (470), энтропийно кодируются (480) и пакетируются (490).

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

2. Адаптивный порядок сканирования коэффициентов

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

Последующая проиллюстрированная реализация этого метода адаптивного порядка сканирования коэффициентов имеет следующие свойства.

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

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

Фиг.6 показывает процедуру (600) согласно одной из реализаций метода адаптивного порядка сканирования коэффициентов в кодере 400 и декодере 500. Процедура (600) начинается с операции (610) инициализацией порядка сканирования коэффициентов (или порядков - в случаях, где адаптивно изменяются множество порядков сканирования, например, для горизонтальных и вертикальных коэффициентов) в известное упорядочивание, предполагаемое для хорошего выполнения по типовой области данных. В некоторых реализациях метода адаптивного порядка сканирования коэффициентов это начальное упорядочивание может быть разным в разных контекстах порядка сканирования, таких как порядок сканирования коэффициентов для макроблоков, демонстрирующих преимущественно «горизонтальную ориентацию» против «вертикальной» ориентации. В некоторых реализациях процедуры адаптивного порядка сканирования коэффициентов ориентация или контекст сканирования могут сигнализироваться декодеру из кодера явным образом. В других реализациях эта ориентация может быть выведена из ориентации DC-поддиапазона, передаваемого перед АС-коэффициентами. Например, фиг.7 показывает пример начального порядка (700) сканирования для блоков 4×4, имеющих горизонтальную ориентацию. Фиг.8 показывает пример начального порядка 800 сканирования для блоков 4×4, имеющих вертикальную ориентацию. В этом примере порядком (700) сканирования горизонтальной ориентации является начальный порядок сканирования, также используемый для блоков, не демонстрирующих никакой конкретной ориентации.

Как показано на фиг.9, проиллюстрированная процедура (600) отслеживает локальную статистику блочных коэффициентов с использованием двух одномерных массивов: массива 910 Order (порядок) и массива 920 Totals (итоги). Отдельный набор массивов поддерживается для каждого контекста порядка сканирования. В проиллюстрированной реализации этот массив (помеченный «Order») содержит в качестве своих записей обратное сканирование, то есть индекс коэффициента в возрастающем порядке сканирования. Процедура (600) инициализирует этот массив начальным порядком сканирования при операции (610) инициализации. Фиг.9 иллюстрирует значения, сохраненные в массиве 910 Order для примерного начального порядка (800) сканирования коэффициентов, показанного на фиг.8, при инициализации. В этой иллюстрации DC-коэффициент послан перед

АС-коэффициентами, и поэтому не фигурирует в массиве.

Для каждого массива 910 Order обратного сканирования процедура (600) также поддерживает массив, помеченный «Totals» на этой иллюстрации, в котором процедура (600) подводит итог частоты событий появления соответственного коэффициента. В следующей операции (620) процедура (600) инициализирует массив Totals произвольно убывающими значениями. Например, этот массив заполняется значениями {k*N, k*(N-1), k*(N-1), …, k} для некоторого значения k. Это показано в нижней строке таблицы по фиг.9. Значение k в этом примере выбрано небольшим целочисленным, в типовом случае - между 2 и 4. В некоторых реализациях процедуры адаптивного порядка сканирования коэффициентов выбор k может быть основан на параметре квантования, использованном при квантовании (470) (фиг.4).

Во время последовательности операций кодирования процедура (600) проходит коэффициенты текущего блока согласно порядку сканирования, отраженному в элементах массива 910 Order (как показано в цикле (630), (680) «for»). При этом прохождении процедура обновляет статистику частоты событий появления коэффициента, отраженную в массиве 920 Totals. Более точно, процедура (610) в этой проиллюстрированной реализации обновляет массив Totals согласно частоте событий ненулевого значения для соответственного коэффициента. Если n-ый элемент сканирования является ненулевым (то есть коэффициент преобразования с индексом Order[n] является ненулевым), то процедура (600) увеличивает n-ый элемент Totals на 1 (то есть Totals[n]: = Totals[n] + 1), как проиллюстрировано операциями (640) и (650).

Если после увеличения обнаруживается, что Totals[n] > Totals[n-1], то это означает, что ненулевое значение для текущего коэффициента появляется с большей частотой, чем до сих пор для предыдущего коэффициента. При таком событии (операция 660) процедура применяет операцию (670) обмена к порядку сканирования. Во время операции (670) обмена порядок сканирования и соответствующие Totals при n и n-1 обмениваются местами, как показано в следующем псевдокоде:

Temp: = Order[n]

Order[n]: = Order[n-1]

Order[n-1]: = Temp

Temp: = Totals[n]

Totals[n]: = Totals[n-1]

Totals[n-1]: = Temp

Как результат операции (670) обмена коэффициент, индексируемый посредством Order[n] (до обмена), в дальнейшем сканируется раньше коэффициента, индексируемого посредством Order [n-1] (до обмена). Это, в сущности, является «пузырьковой» сортировкой коэффициентов на основании присущей им частоты событий появления ненулевого значения для коэффициента.

Например, фиг.10 показывает ситуацию, где Totals[n] > Totals[n-1]. Стрелки показывают элементы, которые требуют обмена. Фиг.11 показывает массивы Order и Totals, являющиеся результатом обмена, а фиг.12 показывает соответствующие индексы порядка сканирования по блоку 4×4.

В проиллюстрированной процедуре (600) адаптивного порядка сканирования коэффициентов нет никакого дополнительного условного обмена Totals[n-1] и Totals[n-2], и т.д. Это означает, что есть, самое большее, один переход в массиве порядка сканирования для каждого ненулевого коэффициента, и поэтому проиллюстрированная процедура (600) обладает линейным порядком сложности по отношению к количеству ненулевых коэффициентов. Коэффициент может перемещаться, самое большее, на одну позицию в порядке сканирования за каждое прохождение блока внутри цикла (630-680).

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

Поскольку процесс адаптации использует только текущий коэффициент (в цикле 630-680) и предыдущий элемент сканирования (который может или не может становиться ненулевым), и, кроме того, поскольку условное переключение происходит после того, как коэффициент кодирован из/декодирован в матрицу преобразования, адаптация является причинно-следственной. Равным образом весь блок может быть кодирован с использованием текущего порядка сканирования. Затем порядок сканирования может быть модифицирован на основании кодированных ненулевых коэффициентов и массива Totals. Следовательно, нет никакого дополнительного запаздывания, вносимого в процесс кодирования или декодирования.

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

С периодическими интервалами процедура (600) сбрасывает массив Totals в состояние инициализации с тем, чтобы предотвратить арифметическое переполнение и способствовать адаптации. В одной из реализаций процедуры адаптивного порядка сканирования коэффициентов в кодеке сжатия изображения массив Totals сбрасывается в начале каждой порции из 8 макроблоков (макроблоки являются массивами 16×16 пикселей яркости и включают в себя соответствующие пиксели цветности). Максимальное значение любого элемента массива Totals ограничено до 8 (макроблоков) × 16 (коэффициентов определенной частоты в макроблоке) × 3 (цветовых плоскости в макроблоке) = 384 + максимальное значение инициализации, которое с уверенностью меньше 511. В этом случае для массива Totals достаточно 9 битов. Другие интервалы сброса могут быть выбраны для более или менее быстрой адаптации, и интервалы сброса могут быть зависимыми от параметра квантования. Следовательно, с интервалом сброса массива Totals, как проиллюстрировано операцией (692), процедура (600) осуществляет возврат к началу цикла, в операцию (620), где инициализируется массив Totals, перед переходом к обработке следующего блока коэффициентов.

При других (менее частых) периодических интервалах оба массива Totals и Order сбрасываются в состояние инициализации с тем, чтобы способствовать произвольному доступу в этих позициях.

Как проиллюстрировано в операции (693), процедура осуществляет возврат к началу цикла, в операцию (610) инициализации массивов Totals и Order с такими интервалами. Например, в зависимости от реализации кодека процедура может осуществлять сброс в состояние инициализации в точках входа в независимо кодированные участки битового потока изображения, или в начале каждого изображения видеопоследовательности и т.д.

3. Сравнение с пузырьковой сортировкой

Пузырьковая сортировка является традиционной компьютерной процедурой для сортировки массива данных. Процедура пузырьковой сортировки может быть охарактеризована, как изложено ниже. Пусть массив N элементов (который может предполагаться числовым, без потери общности) будет представлен посредством X. X[i] - i-ый элемент, с индексом i, изменяющимся от 1 до N включительно.

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

всякий раз для некоторого i между 2 и N обменивать элементы массива X[i-1] и X[i], когда X[i-1]>X[i].

Во время каждого прохода операция условного обмена применяется для каждого индекса i, принимающего значение по порядку от 2 до N.

При завершении N-1 проходов массив Х отсортирован. Такая же процедура может быть использована с незначительными модификациями, чтобы сортировать в порядке по убыванию, по алфавиту, или вырабатывать индексы рангового порядка. На практике пузырьковая сортировка часто не используется из-за ее неблагоприятного времени выполнения.

Процедура (600) адаптивного порядка сканирования коэффициентов, описанная в настоящем изобретении, основана на аналогичной операции условного обмена, то есть операции (660), (670) условного обмена. Проиллюстрированная реализация процедуры 600 адаптивного порядка сканирования отличается от пузырьковой сортировки тем, что проиллюстрированная процедура (600) придерживается менее строгого регламента обновления. Более конкретно, два отличия от пузырьковой сортировки состоят в том, что:

1) есть только один проход массива на каждый кодируемый/декодируемый блок, и

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

Эти отличия помогают гарантировать, что вычислительная сложность процедуры (600) ограничена и в самом деле находится в пределах возможностей любого кодека изображения/видео. В то же время использование в процедуре (600) операций (660), (670) условного обмена (в виде пузырьковой сортировки) имеет преимущество в том, что оптимальность сохраняется в асимптотическом смысле, когда статистика (которая отражена в массиве Totals) является стабильной.

Было обнаружено, что проиллюстрированная процедура (600) адаптивного порядка сканирования коэффициентов обеспечивает в результате экономию битовой скорости до 2% в сравнении со схемой энтропийного кодирования, которая использует фиксированные таблицы сканирования. В качестве альтернативы, этот метод может быть использован во взаимосвязи с другими усложненными контекстными моделями для выбора одной из нескольких адаптивных таблиц, а также методами кодирования Хаффмана, с разрядной матрицей и методом арифметического кодирования для кодирования длин серий данных. Например, разные адаптивные модели сканирования могут быть использованы с высокочастотными и низкочастотными полосами пропускания.

Метод адаптивного порядка сканирования коэффициентов может быть использован для кодирования больших объемов данных преобразования, а также для кодирования с многочисленными конфигурациями преобразования (например, по блокам размера 4×8 и 8×4, и т.д.). Подобным образом, блоки или макроблоки могут быть разложены по всему изображению любым заранее заданным образом. Этап условного обмена может использовать гистерезис или другие правила для повышения эффективности или для искажения/затемнения данных в целях управления привилегиями.

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

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

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

Согласно фиг.13 вычислительная среда (1300) включает в себя, по меньшей мере, одно устройство (1310) обработки данных и память (1320). На фиг.13 эта наиболее базовая конфигурация (1330) заключена в пределах пунктирной линии. Устройство (1310) обработки данных исполняет машиноисполняемые инструкции и может быть реальным или виртуальным процессором. В многопроцессорной системе несколько устройств обработки данных исполняют машиноисполняемые инструкции, чтобы повысить возможности по обработке данных. Памятью (1320) может быть энергозависимая память (например, регистры, кэш, ОЗУ (оперативное запоминающее устройство, RAM)), энергонезависимая память (например, ПЗУ (постоянное запоминающее устройство, ROM), ЭСППЗУ (электрически стираемое и программируемое ПЗУ, EEPROM), флэш-память и т.д.) или некоторое сочетание этих двух. Память (1320) сохраняет программное обеспечение (1380), реализующее описанный кодер/декодер и процедуру адаптивного порядка сканирования коэффициентов.

Вычислительная среда может обладать дополнительными признаками. Например, вычислительная среда (1300) включает в себя запоминающее устройство (1340), устройства (1350) ввода, одно или более устройств (1360) вывода и одно или более коммуникационных соединений (1370). Механизм взаимного соединения (не показан), такой как шина, контроллер или сеть, осуществляет взаимное соединение компонентов вычислительной среды (1300). В типовом случае программное обеспечение операционной системы (не показано) предоставляет рабочую среду для другого программного обеспечения, исполняемого в вычислительной среде (1300), и координирует деятельность компонентов вычислительной среды (1300).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9. Способ по п.8, в котором упомянутая преимущественная ориентация контекста сканирования явным образом сигнализируется кодером в сжатом битовом потоке.

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

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

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

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

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

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

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

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

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

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

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