Способ сжатия изображений и видеопоследовательностей

Способ сжатия изображений и видеопоследовательностей

Иллюстрации

Показать все

Реферат

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

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

Из уровня техники известны разные подходы и алгоритмы, используемые для сжатия изображений и видеопоследовательностей, в частности, следует упомянуть решение, описанное в выложенной заявке на патент США №2008/0019598 [1]. В описанном способе и устройстве обработке подвергают довольно крупные блоки размером 4×4 пикселя, что подразумевает буферизацию четырех строк (линий) во входящем потоке. При этом формируются четыре цвета и соответствующее растровое отображение (битовая карта). Такой подход обеспечивает сжатие без визуальных потерь только сигналов с высокой степенью стационарности, т.е. пригоден для сжатия ограниченного набора естественных изображений.

В патентах США №7239743 [2] и №7082217 [3] также делается попытка решить проблему сжатия с фиксированным коэффициентом сжатия на основе кодирования изображения блоками размером 4×4 пикселя. В обоих патентах предусмотрено формирование цветовой палитры с построением и кодированием битовой карты. Основной недостаток этих решений заключается в том, что они ориентированы на работу с относительно крупным блоком (4×4) и неспособны эффективно обрабатывать участки нестандартного характера, например резкие непредсказуемые контуры (переходы) внутри изображения. Несколько лучше работает способ, описанный в публикации "Graphics for the Masses - A Hardware Rasterization Architechture for Moible Phones" Tomas Akenine-Moller and Jacob Strom ACM Transactions on Graphics, vol.22, no.3, Proceedings of the ACM SIGGRAPH 2003, p.801-808, July [4]. В этом способе используется алгоритм сжатия текстуры, основанный на обработке изображения блоками фиксированного размера, например 4×4, 2×4, 8×8, с последующим вычислением средних значений этих блоков и вычислением в каждом пикселе разности между индивидуальным значением его яркости и средним значением и кодированием этих разностей с помощью набора фиксированных квантователей. Этот способ также оказался неэффективным для обработки резких по цвету и яркости контуров.

Наиболее близким к заявляемому изобретению является решение, описанное в выложенной заявке на патент США №2007/0253483 [5]. В этом решении тоже используют блоки размером 4×4 и применяют пространственное прогнозирование значений блока на основе различных пространственных направлений (вертикаль, горизонталь, диагонали) и помимо этого вводят так называемую пространственную фильтрацию обрабатываемого пикселя (имеется в виду устранение корреляции в одном из пространственных направлений), определяют режим прогнозирования и кодирования. Кроме того, отфильтрованные значения пикселей подвергаются различным блочным преобразованиям и кодированию. Этот подход использует несколько режимов кодирования, однако он не гарантирует фиксированную скорость передачи битов, а блок обработки имеет сравнительно большой размер (4×4). Помимо этого в данном подходе используется буферная строка для хранения ранее закодированных данных, что не позволяет осуществлять независимое кодирование блоков изображения, т.е. степень устойчивости алгоритма к помехам невысока.

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

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

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

Целесообразно также рассматривать верхние восемь битов изображения в виде блоков размером 2×4 пикселя, при этом каждый такой блок обрабатывают как единый блок размером 2×4 (далее будут рассмотрены способы такой обработки, это, в частности, способы, идентифицируемые как F-, O-, D-, L-, U-, H- и M-способы) или как два блока размером 2×2 пикселя (здесь применяют методы N, Р, S, C и E).

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

- сжатие цветного цифрового изображения и видеопоследовательности без визуально различимых искажений при фиксированной скорости передачи данных (fixed bitrate);

- кодирование и декодирование с фиксированной степенью сжатия в 2,4 раза для цветных изображений с 10-битной глубиной по каждой компоненте цвета при малых вычислительных ресурсах с сохранением высокого качества;

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

Заявляемый способ ориентирован на работу с небольшими блоками размером 2×4 пикселей и обеспечивает их независимое кодирование. Он обеспечивает устойчивость сжатого битового потока к помехам и произвольный доступ к любой части обрабатываемого изображения без декодирования пикселей из ранее закодированных блоков.

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

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

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

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

- Заголовок, указывающий на то, какой способ сжатия используется.

В результате экспериментов установлено, что оптимальным вариантом будет использование заголовка переменной длины (Variable Length Encoding Header - VLEH), Размер заголовка зависит от применяемого способа и может варьироваться от 1 бита до 10 битов.

- Данные о компактном представлении младших разрядов блока (Least Significant Bits Data - LSBD). В сжатом блоке размером 2×4 эти данные, как правило, зависят от выбранного способа кодирования и занимают от трех до шести битов на блок.

- Сжатый битовый поток. Он представляет в компактном виде верхние восемь наиболее существенных битов для всех пикселей в пределах блока размером 2×4.

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

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

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

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

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

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

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

O-Способ. Используют тогда, когда один цветовой канал по своим энергетическим характеристикам в целом существенно превосходит другие каналы внутри обрабатываемого блока 2×4. При этом рассматриваются четыре возможные ситуации, когда доминирует канал яркости, каналы R, G или B.

L-Способ. Применяют к блоку размером 2×4 во всех трех каналах одновременно. Для обеспечения эффективного представления внутренней структуры изображения для каждого подблока размером 2×2 формируют собственную палитру. Затем используется один из трёх режимов: режим межблочного дифференциального кодирования палитр для двух соседних подблоков 2×2, режим дифференциального кодирования цветов внутри каждого подблока и режим прямого квантования цветов палитры.

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

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

Для подблоков размером 2×2 были разработаны пять других способов (для отличия от ранее описанных способов далее будем называть их «методами»), входящих во вторую группу. Эти методы независимо применяются к обоим подблокам 2×2, а затем для каждого исходного блока выбирается сочетание методов, обеспечивающее минимальную погрешность. К методам второй группы относятся следующие:

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

P-метод. Метод является модификацией N метода и обеспечивает кодирование подблока 2×2 с использованием вертикальных/горизонтальных/диагональных преимущественных направлений, а также кодирования на основе среднего значения.

C-метод. Метод основан на NSW-преобразовании и заключается в его применении ко всем цветовым каналам одновременно с последующим групповым кодированием разностных величин из трех цветовых каналов совместно. За счет этого, в случае если разностные величины NSW-преобразования по трем цветовым каналам в достаточной мере сходны, достигается повышение точности кодирования (квантования) путем увеличения динамического диапазона квантователя и устранения независимости выбора квантователя от цветового канала.

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

S-метод. Этот метод весьма схож с N методом и отличается модифицированной процедурой кодирования, которая адаптирована для передачи участков изображений, на которых разностные величины принимают сравнительно малые значения по всем трём цветовым каналам в пределах подблока 2×2.

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

Выбор метода осуществляется поэтапно.

Этап 1. Левые и правые подблоки 2×2, входящие в обрабатываемый блок 2×4, подвергают сжатию пятью методами: N, Р, C, S и E. B результате этого формируют набор погрешностей (ошибок) и промежуточных битовых потоков.

Этап 2. Для каждого подблока выбирают наилучший метод. Выбор основан на поиске наименьшей величины погрешности среди всех рассчитанных.

Этап 3. Определяют наилучшую комбинацию методов для блока 2×4 на основе методов N, Р, C, S и E, примененных к левому и правому подблокам, а также вычисляют комбинационную погрешность.

Этап 4. Блок 2×4 обрабатывают семью способами: D, O, M, F, L, U, H. При этом рассчитывают погрешности кодирования текущего блока каждым из указанных семи способов.

Этап 5. Определяют минимальную погрешность, сравнивая комбинационную погрешность и погрешности, вызванные применением способов D, O, M, F, L, U, H. В результате выбирают наилучший способ.

Этап 6. В выходной буфер заносят VLEH, соответствующий выбранному способу сжатия.

Этап 7. В выходной буфер заносят также сжатый битовый поток.

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

Этап 9. В случае необходимости добавляют дополняющие биты для обеспечения фиксированной скорости передачи обрабатываемого блока 2×4.

Фиг.1 - основные этапы способа кодирования.

Фиг.2 - вид 2.1 - исходный подблок 2×2; вид 2.2 - направления разностей NSW-преобразования; вид 2.3 - блок-схема N-метода.

Фиг.3 - виды 3.1-3.4 - преимущественные способы кодирования P-метода; вид 3.5 - блок-схема P-метода.

Фиг.4 - вид 4.1 - схема оценки дополнительных свободных битов для P-метода; вид 4.2 - последовательность битового потока с дополнительными свободными битами.

Фиг.5 - вид 5.1 - упрощенная последовательность действий E-метода; вид 5.2 - графическое представление структуры блока 2×4 и ее интерпретация в E-методе.

Фиг.6 - детальная схема способа кодирования отдельного цветового перехода.

Фиг.7 - вид 7.1 - иллюстрация разделения блока 2×4 на левый и правый подблоки 2×2; вид 7.2 - блок-схема D-способа.

Фиг.8 - вид 8.1 - иллюстрация положения опорных точек и отдельных производных в F-способе; вид 8.2 - блок-схема F-способа.

Фиг.9 - блок-схема O-способа.

Фиг.10 - блок-схема L-способа.

Фиг.11 - блок-схема способа определения цветов палитры блока 2×2.

Фиг.12 - общая блок-схема U-способа.

Фиг.13 - вид 13.1 - блок-схема первого способа кодирования, входящего в U-способ; вид 13.2 - логическая схема кодирования среднего значения «гладкого» цвета в первом способе кодирования, входящего в U-способ.

Фиг.14 - общая блок-схема второго способа кодирования, входящего в U-способ.

Фиг.15 - детальная блок-схема кодирования одного цвета в пределах блока 2×4 в соответствии со вторым способом кодирования, входящего в U-способ.

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

Фиг.17 - вид 17.1 - способ разделения битов в пределах пространственного блока 2×4 на существенную и несущественную части; - вид 17.2 - способ частичной группировки младших битов при кодировании младших разрядов.

Основные этапы разработанной методики кодирования показаны на Фиг.1. Каждый кадр видеопоследовательности рассматривается в виде независимого цветного изображения. Каждое изображение представляется в виде множества неперекрывающихся блоков размером 2×4. Этап 100 заключается во вводе изображения, представлении его в виде блоков и их кодировании возможными способами. При этом изначально 10-битные данные разделяются на существенную и несущественную части. Далее, существенная часть, образующая блок 2×4 из 8-битных значений обрабатывается на этапах 101…121, в то время как младшая часть, образующая блок 2×4 из 2-битных значений, обрабатывается на этапе 123. Каждый непересекающийся блок 2×4 исходного изображения разделяется на левый подблок размером 2×2 (три канала), правый подблок размером 2×2 (три канала), а также рассматривается как целый блок размером 2×4 (три канала). Левый подблок обрабатывают на этапах 101, 103, 105, 107, 109. Правый подблок обрабатывают на этапах 102, 104, 106, 108, 110. Целый блок обрабатывают на этапах 111-117.

После того как каждый блок подвергнется кодированию всеми доступными в конкретном случае способами, определяют погрешности кодирования и выбирают способ, дающий наименьшую погрешность для каждого блока (этапы 118-120). На этапе 121 определяют погрешность кодирования, вызванную раздельным кодированием левого и правого подблоков на этапах 101, 103, 105, 107, 109 и 102, 104, 106, 108, 110 соответственно. На этапе 122 выбирают оптимальный способ (среди способов, выбранных на этапах 118-120).

На этапе 123 кодируют данные младших разрядов (LSBD Least Significant Bits Data). Число битов при кодировании LSBD зависит от выбранного способа кодирования.

На этапе 124 формируют выходной битовый поток, который состоит из заголовка, указывающего на то, какой способ использован. Размер заголовка зависит от конкретного способа и может занимать от одного до десяти битов. Затем в поток вносят данные о младших разрядах (LSBD) блока 2×4 в сжатом виде. В зависимости от выбранного способа эти данные могут занимать от трех до шести битов на блок 2×4. В случае необходимости поток пополняется дополняющими битами, которые предназначены для обеспечения фиксированной скорости битового потока. Подблок размером 2×2 кодируется набором методов. Первый из таких методов основан на NSW-преобразовании и называется N-метод. Этот метод применяют на этапах 101, 102. Преобразование NSW является новым двумерным преобразованием, разработанным на основе комбинации предикативного кодирования, одномерного вейвлет-преобразования Хаара, лифтинг-схемы.

Будем рассматривать блок размером 2×2 в любом цветовом канале как набор из четырех значений A, B, C, D (Фиг.2.1). Набор из четырех исходных значений A, B, C, D преобразуют в четыре значения: {A, B, C, D}→{s, h, v, d} согласно следующим формулам:

h=A-B
ν=A-C	B=A-h
d=A-D	C=A-ν
	D=A-d

где s - означает среднее значение четырех пикселей, h, v, d - простейшие градиенты в направлениях: горизонталь, вертикаль, диагональ (Фиг.2.2). Блок-схему N-метода иллюстрирует Фиг.2.3. На этапе 200 выполняют преобразование NSW, получая значения s, h, v, d. Первоначально для хранения s требуется восемь битов, h, v, d занимают по девять битов на каждое значение: 1-разряд для хранения знака+8-разрядная величина. Для компактного представления этих данных используются определенные процедуры. N-метод применяют к подблоку 2×2, который входит в состав блока размером 2×4 для трех цветовых каналов. Очевидно, что каждый подблок 2×2 должен кодироваться в среднем не более чем 90:6=15 битами. Эти пятнадцать битов должны представлять s, h, v, d с достаточной точностью. В целях обеспечения надежности и простоты кодирования кодирование величины s осуществляется с использованием простого равномерного квантования. Точность в шесть битов является достаточной для представления среднего значения для естественных частей изображений - этап 201. Квантование набора разностных величин {h, v, d} основано на построении набора фиксированных квантователей, подобного оптимальному фиксированному квантованию Ллойда-Макса - этапы 202…208 (см. "Quantizers for symmetric gamma distributions" in Proc. IEEE Globecom Conf, p.214-118, 1983; "The enhanced LBG algorithm" // Giuseppe Patane, Marco Russo) - [6]. При этом каждый квантователь относится к изображению с определенной структурой и состоит из более чем одного значения, являющегося уровнем восстановления квантованного значения. Процесс квантования заключается в выявлении подходящего квантователя среди набора квантователей для {h, v, d} (этап 209 после этапов 202…208) для одного цвета, а затем нахождении для каждой разности соответствующего уровня восстановления (этап 210). Из-за ограниченного битового бюджета налагаются следующие ограничения: набор квантователей состоит из восьми отдельных квантователей, каждый из которых имеет четыре значения: два положительных и симметрично два отрицательных (эти значения здесь и далее называются уровнями восстановления). Обычно значения уровней восстановления заключены в диапазоне [-255…255]. При этом модули значений уровней восстановления одного квантователя представляют собой монотонно возрастающую дискретную функцию. Таблица с предпочтительными уровнями восстановления приведена ниже:

Таблица 1
Таблица квантования
Номер квантователя	Id×0	Id×1	Id×2	Id×3
0	-220	-80	80	220
1	-23	-4	4	23
2	-200	-10	10	200
3	-80	-40	40	80
4	-138	-50	50	138
5	-63	-18	18	63
6	-42	-12	12	42
7	-104	-28	28	104

Процесс кодирования разностных величин {h, v, d} включает в себя следующее:

- определение номера квантователя N из набора квантователей, три величины которого являются наилучшим приближением для {h, v, d};

- определение индексов уровней восстановления для {h, v, d} в квантователе с номером N.

Описанный процесс кодирования разностных величин здесь и далее обозначается процессом фиксированного квантования по таблице (FQvT). Для большего обобщения имеет смысл сформулировать FQvT в общих математических терминах. Набор квантователей может быть описан в виде двумерной матрицы Q (таблицы квантования), включающей QS строк (квантователей) и IX столбцов (уровней восстановления или квантования). Допустим, что требуется выполнить квантование набора разностных величин {d₁…d_K}. Определим общее выражение для вычисления погрешности Е приближения, которая вызвана квантованием исходного набора разностных величин {d₁…d_K}. Не ограничивая общности, положим, что она может зависеть от набора разностей {d₁…d_K}, выбранных уровней восстановления {Id₁…Id_K}, а также выбранного квантователя QI. Е=Е({d₁…d_K}, (Id₁…Id_K}, QI). Нахождение оптимального квантователя из набора квантователей заключается в определении аргумента выражения:

Это выражение математически описывает этапы 202…208 и условный переход на Фиг.2.3. С технической точки зрения оно означает, что для каждого квантователя (QI) набор разностных величин {d₁…d_K} должен быть аппроксимирован наилучшими уровнями восстановления, которые однозначно идентифицируются индексами {Id^Q1 ₁…Id^QI _K). Затем среди всех квантователей из набора квантователей должен быть выбран только один, и это должно обеспечить минимальную погрешность аппроксимации. Для данного квантователя QI и данной разностной величины d_j наилучший уровень восстановления в общем случае определяется выражением:

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

Функция E({d₁…d_K}, {Id₁…Id_K), QI) может также включать дополнительные веса, которые позволят вычислять взвешенную погрешность (если, например, используются разностные величины из цветовых каналов с различной видимостью). Очевидно, что представленная таблица квантования не может идеально передать произвольную комбинацию {h, v, d}. Однако результаты проведенных экспериментов указывают на то, что для естественных изображений множество значений (h, v, d) локализовано в определенных подобластях. Исходя из этого таблица квантования оптимизирована именно для этих случаев.

Выбор оптимального квантователя (или строки в таблице 1) основан на вычислении погрешности аппроксимации подблока определенным набором {h', v', d'}. Рассмотрим процесс квантования разностных величин h, v, d как добавление аддитивного шума к исходным значениям:

Тогда погрешность интенсивностей пикселей A, B, C, D может быть оценена следующим образом:

Если среднее значение s подвергается квантованию, то соответствующая Δs должна прибавляться к ΔА для того, чтобы корректно оценить оставшиеся пиксельные погрешности.

На основе проведенных исследований приемлемые результаты могут быть достигнуты, если в качестве меры погрешности Е использовать сумму квадратов значений ΔA, ΔB, ΔC, ΔD (этап 207). Для каждой строки вычисляют эту величину и затем выбирают минимум. Следует отметить, что эта величина, по существу, является среднеквадратичным отклонением ошибки кодирования подблока (погрешность квантования, вызванная квантованием значения s, не рассматривается, но также может быть учтена).

В тех или иных целях для оценки меры погрешности могут быть использованы и более простые функциональные зависимости. Например, значение максимального отклонения MAX(|Δh|, |Δv|, |Δd|) также рекомендовано к применению. Результаты экспериментов также подтверждают ее эффективность.

Второй метод обработки подблока размером 2×2 - это P-метод, который реализуется на этапах 103 и 104. Преобразование NSW эффективно используется при кодировании естественных частей изображений. Но некоторые из них могут состоять из одного вертикального/горизонтального элемента. В этом случае одна из разностей будет близка нулю и таблица квантования N-метода не будет столь эффективной. Для преодоления этой проблемы таблица квантования оптимизирована под указанные случаи. Кроме того, добавлены дополнительные подрежимы кодирования, обеспечивающие эффективную передачу подблоков с вертикальными/горизонтальными или диагональными преимущественными направлениями, а также однородными участками в пределах подблока размером 2×2. Способ кодирования определяется субпрефиксом переменной длины (VL), который указывает, какой тип кодирования используется. В P-методе используют семь подрежимов. Они представлены в Таблице 2. Обобщенная блок-схема Р-метода показана на Фиг.3.5.

Таблица 2
Субпрефиксы VL для метода NSWPZ
Субпрефикс (двоичное представление)	Название подрежима
00	Горизонтальное преимущественное направление (H структура)
01	Вертикальное преимущественное направление (V структура)
100	h величина близка к 0
101	v величина близка к 0
110	d величина близка к 0
1110	Диагональное преимущественное направление (D структура)
1111	Среднее значение

H структура означает, что для кодирования подблока 2×2 используются две "опорные точки" A, C (Фиг.3.1). Каждая из них кодируется семью битами (простое усечение младшего разряда). Усеченный младший разряд восстанавливается нулевым значением.

V структура означает, что для кодирования подблока 2×2 используют две "опорные точки" A, B (Фиг.3.2). Каждая из них кодируется семью битами (простое усечение младшего разряда). Усеченный младший разряд восстанавливается нулевым значением.

D структура означает, что для кодирования подблока 2×2 используют две "опорные точки" A, B (Фиг.3.3). Каждая из них кодируется шестью битами (простое усечение двух младших разрядов). Усеченные младшие разряды восстанавливаются бинарным значением 10b. По сравнению с режимом H/V-структур в этом случае опорные точки A, В используются для восстановления точек C, D следующим способом: D=A, C=B.

Режим среднего значения используется для того, чтобы кодировать все пиксели A, B, C, D через среднее значение (однородный блок), а среднее значение занимает восемь битов.

Один из режимов "h/v/d величина близка к нулю" используется, если после NSW-преобразования одна из величин (h, v, d) близка к нулю. Префиксы выбраны на основе следующих соответствий:

100: |А-В |~0

101: |А-С |~0

110: |A-D |~0

В каждом случае только две разностные величины подвергаются квантованию:

h≡0; {v, d}→{Квантователь N, Iv, Id},

v≡0; {h, d}→{Квантователь N, Ih, Id},

d≡0; {h, v}→{Квантователь N, Ih, Iv}.

Предпочтительная таблица квантования, описывающая набор квантователей для метода NS WPZ, представлена ниже:

Таблица 3
Таблица квантования. Р-метод
Номер квантователя	Id×0	Id×1	Id×2	Id×3
0	-250	-240	240	250
1	0	0	-7	7
2	-224	-9	9	224
3	-118	-66	66	118
4	-94	-19	19	94
5	-220	-125	125	220
6	-185	-52	52	185
7	-39	-12	12	39

Величина s первоначально кодируется шестью битами простым усечением двух младших разрядов, однако в ряде случаев точность представления может быть повышена за счет более эффективного кодирования разностных величин. Процесс кодирования включает в себя следующие этапы: на этапе 300 подблок размером 2×2 кодируют с помощью структуры H; на этапе 301 подблок размером 2×2 кодируют с помощью структуры V; на этапах 302 и 303 подблок размером 2×2 кодируют соответственно с помощью структуры D и среднего значения. После этого на этапе 304 вычисляют погрешности, вызванные соответствующими способами кодирования подблока. Затем выполняют NSW-преобразование (этап 305). Среди модулей разностных величин (h, v, d) определяют наименьшее значение - этап 306. Затем две ненулевые разностные величины кодируют методом FQvT с помощью Таблицы 3 и процесса квантования, описанного выше (этап 307). На этапе 308 определяют дополнительные свободные биты и исходя из этого величину s кодируют с точностью шесть, семь или восемь битов. Оценивают погрешность, вызванную кодированием блока 2×2 с помощью метода FQvT - этап 309. Среди полученных на этапе 310 пяти погрешностей выбирают наименьшую. Соответствующий субпрефикс из Таблицы 2 вводят в битовый поток перед сжатыми данными - этап 311.

В результате экспериментов установлено, что 6-битовая точность представления среднего значения в ряде случаев оказывается недостаточной для обеспечения визуальной идентичности некоторых участков изображения. В связи с этим предложено один из квантователей (Номер 1) использовать как индикатор. Он содержит как нулевые значения, так и ненулевые значения, которые кодируются префиксными кодами специального вида: Id×0→0b; Id×1→ запрещенное значение; Id×2→10b; Id×3→11b. Таблица с уровнями восстановления для этого квантователя приведена ниже:

Номер квантователя	Id×0	Id×1	Id×2	Id×3
1	0	0 запрещенное значение	-7	7

Алгоритм для выявления числа "Свободных Битов" показан на Фиг.4.1. Декодер может определить наличие свободных битов аналогичным образом, в силу чего когерентность кодера/декодера не нарушается. Соответствие числа свободных битов и точности представления среднего значения указано в Таблице 4:

Таблица 4
Интерпретация свободных битов
Количество свободных битов	Точность представления "s" величины
0	6
1	7
9	8

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

Третий метод этой группы называется S-метод. Этот метод применяют на этапах 105, 106. Он разработан специально для воспроизведения участков со сравнительно малой интенсивностью (и, следовательно, с малыми разностными величинами) во всех трех цветовых каналах в пределах подблока 2×2 и является модификацией N-метода за счет применения иной таблицы квантования и иной процедуры кодирования среднего.

Величина s кодируется с использованием пять битов следующим образом:

- берут младшие шесть битов восьмибитового представления величины s;

- из них старшие пять битов рассматриваются как кодовое представление величины s. При декодировании младший разряд декодированной величины s восстанавливают нулевым значением.

Таблица квантования обеспечивает передачу незначительных изменений интенсивностей:

Таблица 5
Таблица квантования. Кодирование малых значений
Номер квантователя	Id×0	Id×1	Id×2	Id×3
0	-1	-2	1	2
1	-2	-6	2	6
2	-1	-4	1	4
3