ДЕРЕВЬЯ ПОСТРОЕНИЯ ДЛЯ АДАПТИВНОГО КОДИРОВАНИЯ ИЗОБРАЖЕНИЙ И ВИДЕОИЗОБРАЖЕНИЙ С ИСПОЛЬЗОВАНИЕМ УСТАНОВЛЕННОГО РАЗДЕЛЕНИЯ В ОБОБЩЕННЫХ ИЕРАРХИЧЕСКИХ ДЕРЕВЬЯХ, ОБЛАДАЮЩИХ НАПРАВЛЕННОСТЬЮ

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

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

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

2. Описание предшествующего уровня техники

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

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

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

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

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

Что касается потерь 2-D зависимости, на примере можно видеть, что места размещения 2 и 6 коэффициента на фиг.1В близки по спектру частот, как показано в блоке 4×4, хотя они не расположены рядом и фактически расположены далеко друг от друга, в соответствии с порядком зигзагообразного сканирования, показанным на фиг.1А.

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

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

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

Настоящее изобретение обеспечивает адаптацию дерева для использования в способе адаптивного кодирования для изображений, в которых используется установленное разделение в пределах обобщенных иерархических деревьев (SPRIGHT). С целью простоты описания Set PaRtitioning in Generalized Hierarchical Trees (установленное разделение в обобщенных иерархических деревьях) сокращенно обозначено здесь как "SPRIGHT". Способ кодирования SPRIGHT может использоваться для внедренного кодирования, поскольку в нем совместно используются аналогичные свойства, в то время как он может обеспечить улучшенную эффективность кодирования. Настоящее изобретение адаптирует разные типы деревьев для разных направленных структур, в которых конкретное дерево, предназначенное для использования, выбирают из множества деревьев.

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

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

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

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

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

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

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

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

Один вариант осуществления изобретения представляет собой способ генерирования множества кандидатов деревьев кодирования для использования в пределах кодера при кодировании изображения и/или видеоизображения, содержащий этапы, на которых (а) генерируют ненаправленное дерево кодирования с использованием разделения на полосы-октавы; (b) генерируют горизонтальные и вертикальные деревья кодирования в ответ на

(b)(i) масштабирование частотных компонент по меньшей мере в горизонтальном и вертикальном направлениях, и (b)(ii) разделение на полосы-октавы для формирования множества кандидатов деревьев кодирования, адаптированных по меньшей мере для горизонтального и вертикального направлений.

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

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

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

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

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

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

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

Еще один дополнительный аспект изобретения представляет собой способ кодирования и декодирования, который можно использовать как во встроенных, так и в невстроенных системах кодирования изображения/видеоизображения.

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

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

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

На фиг.1А и 1В показаны массивы блоков коэффициентов 4×4, представляющие зигзагообразный порядок сканирования на фиг.1А и размещение коэффициента на фиг.1В.

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

На фиг.3А-3С показаны схемы данных коэффициентов для блока коэффициента размером 2×2, как показано на фиг.2А-2С, и операции иерархии дерева, выбранные для блока в соответствии с аспектом настоящего изобретения.

На фиг.4А-4С показаны схемы данных коэффициентов несколько отличающегося блока коэффициентов от фиг.3А и ее ассоциированные операции иерархии дерева, выбранные для блока в соответствии с аспектом настоящего изобретения.

На фиг.5А-5Е показаны блоки коэффициентов размером 4×4, представляющие разделения на полосы-октавы, и ассоциированные конструктивные деревья, представляющие четыре уровня разделения блока на квадраты, L-образные формы и дополнительные разделения, такие как в квадраты половинного размера.

На фиг.6 показан график, представляющий гипотетическую форму спектра, представляющую симметричную амплитуду спектра.

На фиг.7 показан график, представляющий блоки спектра, имеющие горизонтальное смещение.

На фиг.8 показана схема разделения блока для блоков, представляющая L-образные формы относительно горизонтального и вертикального спектров, в соответствии с аспектом настоящего изобретения.

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

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

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

На фиг.12А-12D показана блок-схема разделения направленного DCT, в котором диагональная структура повернута в горизонтальную структуру и сдвинута в соответствии с аспектом настоящего изобретения.

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

На фиг.14 показан график, представляющий положение направленных коэффициентов DCT перед масштабированием, в соответствии с аспектом настоящего изобретения.

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

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

На фиг.17 показана схема разделения блока для первого примера, представляющего разделение коэффициентов на L-образные формы в соответствии с аспектом настоящего изобретения.

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

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

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

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

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

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

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

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

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

1. Введение.

Адаптация деревьев кодирования на основе направленности описана для использования с устройством адаптивного энтропийного кодирования и декодирования и способом, описанных в нашей заявке на патент США, регистрационный номер 12/758,981, поданной 13 апреля 2010 г., которая полностью приведена здесь по ссылке, в которой используется набор разделений в пределах обобщенных иерархических деревьев (SPRIGHT) для кодирования и декодирования изображений и видеоизображений. В настоящем изобретении подробно описан способ генерирования таких направленно адаптированных деревьев кодирования, которые могут быть выбраны с помощью SPRIGHT, на основе устройства или способа кодирования видеоизображения. При кодировании на основе SPRIGHT выбирают из множества кандидатов деревьев кодирования, сгенерированных в соответствии с настоящим изобретением, при кодировании блоков изображения.

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

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

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

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

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

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

Настоящее изобретение обеспечивает обобщение множества кандидатов деревьев кодирования для использования при кодировании SPRIGHT.

2. Структура дерева в SPRIGHT.

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

На фиг.2А представлен для простоты малый преобразованный блок 10 размером 2×2, имеющий коэффициенты A-D. Типично, размеры блока находятся в диапазоне от 4×4, 8×8 и 16×16, 32×32 и т.д., хотя блок может быть выполнен с любой требуемой формой и размером.

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

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

На фиг.2В и фиг.2С иллюстрируются примеры двух возможных структур деревьев для преобразованного блока, показанного на фиг.2А. В дереве 12 на фиг.2В показан одиночный неконцевой узел 16, который также представляет собой корень дерева, от которого непосредственно группируются четыре коэффициента A-D 18a-18d. В дереве 14 по фиг.2С показан неконцевой узел 20, который также представляет собой корень 20, от которого ассоциированы концевой узел А, как 24а, и другой, неконцевой узел 22, который ассоциирует три концевых узла В, С и D, как 24b, 24 с, 24d. Таким образом, на фиг.2В все коэффициенты сгруппированы вместе одновременно, в то время как на фиг.2С коэффициенты В-D сгруппированы вместе на самом низком уровне.

3. Кодирование SPRIGHT с деревом кодирования.

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

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

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

На фиг.3А представлен блок 30, имеющий четыре коэффициента 5, 0, 0, 0. На фиг.3В представлена установка первого кодирования 32 для блока 50, который имеет один неконцевой узел 36 и четыре концевых узла 38a-38d на одном уровне 39. Выходные данные кодирования на фиг.3В генерирует последовательность из пяти значений 1, 5, 0, 0, 0. В отличие от этого данные кодирования отличаются от представленного на фиг.3С использованием определенной двухуровневой структуры дерева. В дереве 34 на фиг.3С, корневой узел 40 имеет один концевой узел 44а, содержащий коэффициент со значением 5, в качестве примера, и неконцевой узел 42, который объединяет нулевые узлы, содержащие три вершины 44b, 44с и 44d в группе 46. Поскольку все эти концевые узлы равны нулю, их можно пропустить, в результате чего соответствующий корень 42 кодируют с 0. В соответствии с таким кодированием, выходные данные данной последовательности кодирования составляют 1, 5, 0; что, конечно, короче, чем кодирование, используемое на фиг.3В. Меньшие размеры блока 2×2 показаны в качестве примера, и следует понимать, что большего размера блоки могут обеспечить более высокие уровни повышения эффективности кодирования. Кроме того, следует понимать, что хотя коэффициенты представлены с целью иллюстрации как целые числа с одним знаком, фактические коэффициенты требуют намного большего пространства в битовом представлении.

Однако, если взаимосвязь между коэффициентами в блоке несколько отличается так, как представлено в блоке на фиг.4А, в котором было перемещено положение одного из коэффициентов, тогда эффективность кодирования в отношении структуры дерева существенно изменяется. На фиг.4В представлен блок 50, имеющий четыре коэффициента 0, 0, 5, 0. На фиг.4А представлено кодирование в соответствии с первой выбранной структурой 52 дерева кодирования, имеющей одиночный неконцевой узел 56 и четыре концевых узла 58а - 58d на одном уровне 60. Выходные данные такого кодирования генерируют последовательность из пяти значений 1, 0, 0, 5, 0. На фиг.4С выбирают другую структуру 54 дерева кодирования, имеющую корень 62, с концевым узлом 66а (коэффициент 0) и неконцевым узлом 64 на первом уровне 70 и на втором уровне 68 с концевыми узлами 66b (0), 66с (5) и 66d (0). В соответствии с ненулевым значением коэффициента в концевым узле 66с группа коэффициентов не может быть пропущена без ввода ошибки, и не концевой узел 64 кодируют с 1, обозначающей, что ее концевые узлы должны быть включены в кодирование. Кодирование с использованием такого дерева генерирует шесть выходных значений 1,0, 1,0, 5,0 и является менее эффективным, чем представленное на фиг.4В.

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

4. Декодирование SPRIGHT с деревом.

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

5. Нулевая кластеризация.

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

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

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

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

6. Деревья, основанные на разделении на полосы-октавы в пределах множества типов деревьев.

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

Аспекты разделения на полосы-октавы описаны и адаптированы для построения набора множества деревьев, для использования с разными направленными структурами, которые могут быть выбраны при выполнении кодирования изображения, в соответствии со SPRIGHT.

На фиг.5А-5Е иллюстрируется пример варианта осуществления деревьев на основе адаптивного разделения на полосы-октавы для генерирования множества деревьев кодирования, из которых дерево кодирования может быть выбрано в соответствии со SPRIGHT, в соответствии с геометрией кодируемого блока.

При разделении на полосы-октавы корень (то есть весь блок) разделяют на один малый квадрат и одну большую L-образную область. В существующих вариантах осуществления размер малого квадрата составляет 2×2, в то время как предпочтительный размер, используемый в настоящем варианте осуществления изобретения, представляет собой квадрат размером 1×1 (только постоянный ток). Настоящее изобретение адаптирует разделение полос-октав для генерирования множества деревьев кодирования, для использования при кодировании SPRIGHT блоков изображения, имеющих направленный компонент.

На фиг.5А представлен корень (весь блок) после того, DCT разделяют на малый квадрат и большую L-образную форму.

На фиг.5В иллюстрируется L-образная форма, итеративно разделенная на три квадрата, и другую меньшую L-образную форму.

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

На фиг.5D иллюстрируется итеративное разделение каждого неконцевого квадрата на четыре квадрата половинного размера.

На фиг.5Е представлено дерево построения, ассоциированное со способом разделения на полосы-октавы, описанным со ссылкой на фиг.5A-5D. Следует отметить, что неконцевые узлы помечены либо как "корень", "L" (L-образная форма), или как "S" (квадрат), в соответствии с их типом.

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

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

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

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

Используя деревья разделения на полосы-октавы, включая в себя модифицированные деревья разделения на полосы-октавы, для генерирования множества кандидатов для использования при кодировании SPRIGHT, обеспечивается множество преимуществ в соответствии со следующими условиями. Разделение на полосы-октавы хорошо подходит для случаев, в которых коэффициенты преобразования малы, даже когда они находятся далеко от места происхождения (DC). Поэтому, если на определенном битовом уровне L-образная форма становится ненулевой (или она содержит, по меньшей мере, один ненулевой коэффициент), существует высокая вероятность того, что ненулевой коэффициент (коэффициенты) не находится в меньшей L-образной форме. Если указанное выше справедливо, ноль все еще можно использовать для представления всех 0 в меньшей L-образной форме. Хотя такое предположение является часто справедливым, возможно множество исключений, в частности, в отношении направленных геометрических структур, в которых настоящее изобретение также выполнено с возможностью выбора различных деревьев в соответствии с различными направленными структурами.

7. Деревья построения на основе 3-режимного DCT.

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

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

8. Неэффективность исходного разделения на полосы-октавы.

Следует понимать, что после выполнения 2-D DCT каждый коэффициент соответствует 2-D частоте и их положения можно пометить в области частот.

На фиг.6 представлен симметричный спектр амплитуды, который представляет собой основные предположения технологии разделения на полосы-октавы.

На фиг.7 представлен пример спектра для горизонтального блока, представляющий, как предположение разделения на полосы-октавы не соответствует направленным структурам. Следует отметить, что спектр является "более белым" вертикально (то есть однородная спектральная плотность мощности), в то время как амплитуда коэффициента понижается медленнее относительно ω_y.

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

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

9. Масштабирование частоты перед разделением на полосы-октавы.

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

Пусть ω=[ω_x, ω_y]^T представляет собой 2-D пространственную частоту. Операцию масштабирования выполняют как ω=Sω, где S=diag[s_x, s_y] представляет собой матрицу масштабирования. Коэффициенты s_x и s_y масштабирования выбирают таким образом, что после масштабирования спектр будет более надежно разделен, используя разделение на полосы-октавы. Такое масштабирование адаптирует технологию разделения полосы-октавы для генерирования деревьев кодирования, которые имеют направленное свойство, хорошо пригодное для SPRIGHT, который выбирает одно дерево кодирования из множества деревьев кодирования, на основе направленных характеристик кодируемого блока изображения.

На фиг.9 иллюстрируется пример варианта осуществления масштабирования в горизонтальном направлении, в котором вертикальное расстояние до места происхождения "сжимают" или "масштабируют". Это дерево показано слева на чертеже перед масштабированием. Матрица масштабирования показана в центре чертежа, которая используется при применении результатов в масштабированном дереве, показанном справа на чертеже. В показанном случае коэффициент масштабирования был выбран равным 0,5 (то есть s_x=1, s_y=0,5) для 3 режимного DCT. После масштабирования и разделения, как представлено справа на чертеже, кружок, заполненный точками, переместился вверх в направлении корня и затем на более высокий уровень относительно расстояния от корня, чем затушеванный кружок.

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

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

10. Конструирование деревьев на основе 5-режимного DCT.

В 5-режимном DCT два диагональных режима добавляют к конструкции дерева 3 режимного DCT. В частности, добавлены диагональ +45° и диагональ -45°. Следует отметить, что 2-D DCT не различает структуры ±45°. Аналогично, спектр формируется в домене DCT из структур ±45°. Одна возможность преодоления этой проблемы состоит в обработке этих двух структур в одном режиме. Однако 2-D DCT не представляют собой хороший выбор для декорреляции блоков изображения в ±45°. Настоящее изобретение преодолевает эту проблему путем использовании направленного DCT и новых деревьев, которые выполнены с возможностью обработки структур ±45°.

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

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

11. Деревья построения на основе горизонтальных/вертикальных деревьев в 5-режимном DCT.

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

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

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

12. Деревья построения на основе направленного DCT.

На фиг.12А-фиг.12D иллюстрируется использование формы направленного DCT, имеющего множество этапов. Поворот представлен, в котором диагональная структура фиг.12А преобразуется в горизонтальную структуру, как можно видеть на фиг.12В. Затем выполняют сдвиг, в результате чего получается показанное на фиг.12С. Затем выполняют DCT вдоль горизонтальной и вертикальной линий, в результате чего получается фиг.12D.

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

13. Установка положения и масштабирование коэффициентов направленного DCT.

В одном аспекте изобретения применяют эвристический подход для локализации положений частоты для направленных коэффициентов DCT. Для горизонтальной частоты (ω_x) общее количество столбцов подсчитывают после поворота и сдвига, как обозначено, например, буквой N. Затем, для коэффициентов в n-ом столбце (n=0,…, N-1), ω_x=n*π/N. Для вертикальной частоты (ω_y) общее количество коэффициентов подсчитывают в текущем столбце, как обозначено буквой М. Затем для m-го коэффициента в столбце (m=0,…,М-1), ω_y=m*π/М.

Аналогично, ω масштабируют для компенсации спектра, обозначенного заполнением точками. В соответствии с предпочтительным аспектом изобретения, блок поворачивают в горизонтальной структуре таким образом, что он становится ω_y, который масштабируют. При использовании 5-режимного DCT коэффициент масштабирования предпочтительно выбирают так, чтобы он составлял 1/4 (то же, что и в горизонтальной и в вертикальной структурах).

На фиг.13 представлена масштабированная и повернутая структура коэффициента, представляющая уровни ω_x вдоль нижней части при ω_x={0, π/4, 2π/4 и 3π/4}, при ω_y представленным масштабированным на первом уровне (самом левом), как ω_y={0, 2π/7,…, 6π/7}, и ω_y={0, π/5…, 4π/5} на втором уровне (втором слева).

На фиг.14 иллюстрируются положения направленных коэффициентов DCT перед масштабированием.

14. Построение дерева для кодирования SPRIGHT.

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

Корень (весь блок) разделяют на один малый квадрат и один большой L-образный участок. Квадрат охватывает низкочастотную полосу, такую как задана:

|ω_x|<π/2^K|ω_y|<π/2^K

где К выбирают так, что малая область содержит только DC (или LL поддиапазон для DWT), в то время как большая L-образная форма содержит все коэффициенты АС.

После разделения корня (К-1) применяют разделение полос-октав для L-образного участка для получения трех квадратов и одной L-образной малой формы. Каждый квадрат, имеющий полосу пропускания большую, чем π/2^K, разделяют на четыре меньших квадрата. Следует понимать, что при использовании термина "разделение", отношения родитель - потомок также принудительно устанавливают между исходной полосой частот и разделениями.

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

На фиг.15-фиг.21 представлен примерный вариант осуществления настоящего изобретения, показанный с этапами для кодирования коэффициентов. На фиг.15 коэффициенты отображают на область частоты и масштабируют в области частоты по фиг.16. Разделение на полосы-октавы показано на фиг.17, при котором корень (то есть весь блок) разделяют на один меньший квадрат и одну большую L-образную область. Дерево кодирования строят по фиг.18 и итеративно разделяют на фиг.19. Следует отметить, что первые два уровня на фиг.19, как представлено в пределах верхнего "овала", имеют наименьший размер, в котором не требуется дополнительное разделение, в то время, как на нижнем уровне, представленном как нижние два "овала", показаны квадраты, которые должны быть итеративно разделены на меньший размер. Дерево построения также представляет соединение концевого узла (коэффициентов) с верхними двумя уровнями дерева на фиг.20. Ненужные узлы затем отбрасывают, как и на фиг.21 из разделенного блока и дерева построения, как можно видеть в блоках, имеющих вертикальные полосы (планки).

15. Деревья построения на основе 9-режимного DCT.

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

Во время кодирования SPRIGHT кодер выбирает один режим из девяти, сгенерированных в соответствии с настоящим изобретением, кодирует блок и передает как сигналы в декодер, как кодированный поток битов, так и индекс режима. Расположение направленных коэффициентов DCT и конструкция дерева кодирования являются аналогичными определенным в 5-режимном DCT. Частота каждого коэффициента масштабирована, как в 3-режимном DCT или в 5-режимном DCT, в то время как коэффициент масштабирования изменяется до 1/8 в 9-режимном DCT.

16. Выбор режима.

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

(1) Предварительное кодирование.

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

(2) Последующее кодирование.

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

17. SPRIGHT. Устройство и способ

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

На фиг.23 иллюстрируется вариант 150 осуществления кодера 136 на основе SPRIGHT, выполненного для выбора дерева кодирования из множества деревьев кодирования, и декодер 142 для декодирования этой структуры дерева. Кодер 136 показан как содержащий компьютерный процессор (CPU) 152 и запоминающее устройство 154. Следует понимать, что эти компоненты обработки могут быть воплощены в единичном экземпляре или в виде многопроцессорных устройств, и/или с любым требуемым уровнем ускоряющих аппаратных средств, без выхода за пределы описаний настоящего изобретения. Программы, выполняемые в процессоре 152, выполняют кодирование 156 источника 158 изображения, выполняют прогнозирование 160, преобразование 162, квантование 164, выбор 166 дерева и кодирование 168 для вывода кодированных данных изображения (или сигнала) 170. Выбор дерева выполняют более конкретно в соответствии с двумерными геометрическими взаимосвязями между коэффициентами в блоке, после которых блок кодируют, используя выбранное дерево. Использование выбранной структуры дерева позволяет существенно повысить эффективность кодирования по сравнению с вариантами воплощения, в которых структура дерева является присущей (фиксированной) в технологии кодирования, используемой для выполнения кодирования.

Декодер 142 показан, воплощенный аналогично, с элементом 172 процессора и запоминающим устройством 174, и он также может содержать любые требуемые компоненты обработки и комбинации с цифровыми аппаратными средствами ускорения, без выхода за пределы описания настоящего изобретения. В соответствии с выполнением программы выполняют процесс 176 декодирования, в котором сигнал 170 принимают и декодируют с помощью блока 178 декодирования, который выполняет выбор 180 структуры дерева перед декодированием. Выходные данные блока 178 декодирования затем подвергают обратному преобразованию 182, и изображение реконструируют так же, как для блока 184, для получения конечных, декодированных выходных данных 186 изображения.

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

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

Во время декодирования, декодер вначале определяет, является ли текущий узел концевым или нет, затем считывает БИТ из потока битов, когда он не является концевым, или считывает символ из потока для концевого узла. Символ может содержать один или больше битов, в зависимости от того, как он был кодирован, например, используя экспоненциальный код Голомба.

На фиг.24 иллюстрируется вариант осуществления способа для генерирования деревьев построения, для использования в установленных разделениях, в обобщенных иерархических деревьях с направленностью. Ненаправленное дерево кодирования генерируют 190, используя разделения на полосы-октавы. Дерево горизонтального кодирования генерируют 192, и дерево 194 вертикального кодирования в соответствии с направленным масштабированием перед выполнением разделения на полосы-октавы. В случае необходимости, деревья кодирования для дополнительных направлений также генерируют 196 в соответствии с вращением и масштабированием, выполняемыми перед разделением на полосы-октавы.

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

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

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

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

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

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

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

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

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

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

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

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

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

10. Устройство по варианту 9 осуществления, в котором упомянутое преобразование содержит ненаправленное или направленное преобразование.

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

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

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

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

15. Устройство по варианту 11 осуществления, дополнительно содержащее программы, выполненные с возможностью применения матрицы масштабирования для блока перед разделением; в котором масштабирование упомянутой матрицей масштабирования выполняют в соответствии с геометрическими взаимосвязями блока и в котором упомянутое масштабирование содержит либо вертикальное, или горизонтальное масштабирование.

16. Устройство по варианту 11 осуществления, в котором упомянутое кодирование содержит внедренное кодирование, в котором кодирование основано на уровне битов.

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

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

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

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

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