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

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

Иллюстрации

Показать все

Реферат

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

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 с деревом.

При де