СПОСОБ СЖАТИЯ ИЗОБРАЖЕНИЙ И ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЕЙ
METHOD TO COMPRESS IMAGES AND VIDEO SEQUENCES

Заявляемое изобретение касается способов обработки видеоданных и, в частности, способа сжатия видеопоследовательностей.
Как известно, эффективность обмена информацией повышается, если удается снизить избыточность передаваемого сообщения, например, удалив несущественные части, а точнее, такие элементы, которые достаточно легко поддаются восстановлению на принимающей стороне. Если при передаче письменных сообщений целые фразы можно заменить условными символами, например математическими, или аббревиатурами, то при передаче изображений, а тем более видеозаписей, приходится применять более сложные методы, удаляя из передаваемых изображений несущественную информацию о точках (пикселях) по специально разработанной методике и затем восстанавливая эти точки при воспроизведении изображений. При этом степень сжатия и корректность восстановления изображения зависят от применяемого алгоритма, а сложные, детально проработанные алгоритмы требуют наличия значительных вычислительных ресурсов.
Из уровня техники известны разные подходы и алгоритмы, используемые для сжатия изображений и видеопоследовательностей, в частности, следует упомянуть решение, описанное в выложенной заявке на патент США №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
<img file="00000001.tif" he="10" wi="41" img-content="undefined" img-format="tif" />
ν=A-C
B=A-h
d=A-D
C=A-ν
<img file="00000002.tif" he="10" wi="39" img-content="undefined" img-format="tif" />
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.
1
K
1
K
1
K
1
K
1
K
1
K
Описанный процесс кодирования разностных величин здесь и далее обозначается процессом фиксированного квантования по таблице (FQvT). Для большего обобщения имеет смысл сформулировать FQvT в общих математических терминах. Набор квантователей может быть описан в виде двумерной матрицы Q (таблицы квантования), включающей QS строк (квантователей) и IX столбцов (уровней восстановления или квантования). Допустим, что требуется выполнить квантование набора разностных величин {d…d}. Определим общее выражение для вычисления погрешности Е приближения, которая вызвана квантованием исходного набора разностных величин {d…d}. Не ограничивая общности, положим, что она может зависеть от набора разностей {d…d}, выбранных уровней восстановления {Id…Id}, а также выбранного квантователя QI. Е=Е({d…d}, (Id…Id}, QI). Нахождение оптимального квантователя из набора квантователей заключается в определении аргумента выражения:
1
K
1
K
j
Q1
QI
Это выражение математически описывает этапы 202…208 и условный переход на Фиг.2.3. С технической точки зрения оно означает, что для каждого квантователя (QI) набор разностных величин {d…d} должен быть аппроксимирован наилучшими уровнями восстановления, которые однозначно идентифицируются индексами {Id …Id ). Затем среди всех квантователей из набора квантователей должен быть выбран только один, и это должно обеспечить минимальную погрешность аппроксимации. Для данного квантователя QI и данной разностной величины d наилучший уровень восстановления в общем случае определяется выражением:
j
Следует отметить, что другой способ определить наилучший уровень восстановления состоит в том, чтобы сравнить d со средними точками между смежными уровнями восстановления. В этом случае требуется лишь выполнить операции "сравнения". Кроме того, легко заметить, что если таблица является симметричной (каждый квантователь включает в себя положительные и отрицательные величины), то во время квантования нужно рассмотреть лишь амплитуды разностных величин.
1
K
1
K
Функция E({d…d}, {Id…Id), 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
-4
-10
4
10
4
-3
-8
3
8
5
-4
-20
4
20
6
-8
-40
8
40
7
-3
-15
3
15
Процедура квантования разностных величин аналогична соответствующей процедуре N-метода.
Четвертый метод называется C-метод. Его применяют на этапах 107 и 108. Метод основан на применении NSW-преобразования и заключается в его применении ко всем цветовым каналам одновременно с последующим групповым кодированием разностных величин из трех цветовых каналов совместно. Эффективность данного метода для определенного класса изображений обуславливается высокой схожестью амплитуд разностных величин после NSW-преобразования всех трех каналов и их совокупным широким динамическим диапазоном, что является отличительной особенностью отдельных областей указанного класса изображений. За счет группового кодирования, увеличения динамического диапазона квантователя (до восьми уровней восстановления), а также устранения независимости выбора квантователя от цветового канала достигается повышение точности кодирования (квантования), в случае если разностные величины NSW-преобразования по трем цветовым каналам в достаточной мере сходны. Эти особенности могут быть рассмотрены как отличительные признаки заявляемого изобретения. Таблица 6 представляет рекомендованный оптимизированный набор квантователей.
Таблица 6
Таблица квантования. C-метод
Номер квантователя
Id×0
Id×1
Id×2
Id×3
Id×4
Id×5
Id×6
Id×7
0
-128
-180
-213
-245
128
180
213
245
1
-3
-15
-30
-50
3
15
30
50
2
-20
-86
-160
-215
20
86
160
215
3
-50
-82
-104
-130
50
82
104
130
4
-90
-145
-194
-240
90
145
194
240
5
-9
-40
-73
-106
9
40
73
106
6
-163
-122
-66
-15
15
66
122
163
7
-180
-139
-63
-25
25
63
139
180
Процесс квантования весьма схож с процессом квантования, примененным в N-методе. Основное отличие состоит в том, что для всего набора разностных величин из подблока 2×2: {hR, hG, hB, vR, vG, vB, dR, dG, dB} выбирают один общий квантователь. Каждая из разностных величин кодируется посредством 3-битового значения. В целом девять разностей занимают: 9×3=27 битов. Индекс квантователя кодируется тремя битами, что в итоге дает (27+3)=30 битов. Каждая величина {sR, sG, sB} кодируется пятью битами путем усечения трех младших разрядов. Восстановление засеченных разрядов осуществляется через бинарное значение 100b. В целом, подблок 2×2 в трёх цветовых каналах кодируется использованием сорока пяти битов. Для определения оптимального квантователя применяется процедура, аналогичная процедуре, используемой в N-методе. Для обеспечения оптимального визуального качества суммарная погрешность приближения набора разностных величин во всех трех цветовых каналах должна учитывать различную цветовую чувствительность зрительной системы человека. В частности, в данном изобретении предложено использовать специально определенные веса, отражающие различное восприятие наблюдателем красного, зеленого и синего цветов. В этом случае погрешность Е, порожденную процедурой FQvT для {hR, hG, hB, vR, vG, vB, dR, dG, dB}, можно выразить следующим образом:
c
Здесь ΔhC, ΔvC, ΔdC обозначают ошибку приближения h/v/d разностных величин после FQvT процедуры в цветовом канале C. W - весовые коэффициенты, отражающие относительную видимость каждого из цветовых каналов C для человека. Более простой способ оценки погрешности E заключается в расчете суммы взвешенных максимальных ошибок кодирования h/v/d разностных величин:
Этот способ оценки погрешности обеспечивает адекватные результаты с точки зрения визуального качества закодированного изображения и рекомендован к применению в случае, если сложность реализации является критической.
Пятый метод обозначается как E-метод. Он выполняется на шагах 109 и 110. Известно, что на границах между двумя чистыми цветами стандартные методы кодирования могут вызывать видимые искажения. Ввиду этого предложено расщепить исходный блок 2×4 на четыре микроблока меньшего размера с размерами 1×2 пикселей - шаг 500 на Фиг.5.1. При этом каждый микроблок 1×2 состоит из двух пространственных пикселей, обозначенных A, B - Фиг.5.2. Каждый пространственный пиксель состоит из трех цветовых компонент R, G, B. Для каждого микроблока определяется доминирующий канал и затем осуществляется передача значений пикселей в доминирующем канале путем кодирования соответствующих значений в шесть битов; минорные (неосновные) каналы кодируются посредством передачи средних значений между двумя значениями для каждой пространственной позиции, при этом используется процедура квантования и ограничения - шаг 501. Блок-схема кодирования микроблока 1×2 показана на Фиг.6. На шаге 602 рассчитывается сумма интенсивностей пикселей по каждому цветовому каналу. Затем осуществляется последовательное сравнение рассчитанных сумм для того, чтобы определить основной (доминирующий) канал. Если сумма интенсивностей в пределах красного канала больше, чем соответствующие суммы в пределах зеленого и синего - шаг 603, то делается заключение о доминировании красного канала. Иначе, если сумма интенсивностей в пределах зеленого канала больше, чем сумма интенсивностей красного и синего - шаг 604, делается заключение о доминировании зеленого канала. Иначе, если сумма интенсивностей в пределах синего канала больше, чем сумма интенсивностей красного и зеленого - шаг 605, делается заключение о доминировании синего канала. В противном случае предполагается, что доминирующим каналом является яростный канал, а цветоразностные каналы являются минорными - шаг 606. Интенсивности пикселей доминирующего канала сохраняются во временных переменных D1/D2. В зависимости от того какие каналы признаны минорными, вычисляются определенные средние значения - шаги 608, или 609, или 610. Ключевой особенностью является способ расчета среднего: усреднение производится не в пределах каждого минорного канала, а между двумя минорными каналами в каждой пространственной позиции. Для примера рассмотрим шаг 608. Первое среднее значение рассчитывается в пространственной позиции A между красным и синим каналами. Второе среднее значение рассчитывается путем усреднения интенсивностей в пространственной позиции B в красном и синем каналах. После этого временные переменные, которые хранят значения доминантного канала, кодируются 6-битными значениями путем усечения двух младших разрядов - шаг 607. Восстановление усеченных разрядов осуществляется двоичным значением 10b. Усредненные значения минорных каналов вначале ограниваются по верхнему порогу, равному шестидесяти трем (если значение больше 63, оно устанавливается равным 63) - шаг 611. Затем ограниченные значения квантуются усечением трех младших разрядов - шаг 612. Восстановление усеченных разрядов осуществляется двоичным значением 100b. С каждым микроблоком 1×2 передается дополнительная информация, указывающая номер доминирующего канала (два бита).
В дополнение к описанным выше методам авторами разработаны семь способов кодирования, которые предназначены для кодирования блока 2×4. Данные способы дополняют комплект методов, описанных выше, и в определенных случаях обеспечивают более эффективную передачу внутренней структуры изображения.
Первый способ этой группы будем далее называть D-способом. Способ применяется на шаге 113. Он предназначен для тех участков изображения, в которых присутствует совокупность небольших областей с четко выраженной структурой (кроссдиагональные границы) и небольших натуральных областей. D-способ метод заключается в определении подблоков 2×2 в пределах блока 2×4, которые обладают регулярной (кроссдиагональной) и натуральной структурой. Подблок с регулярной структурой кодируется с использованием заранее заданного шаблона и шаблонных значений. Шаблон определяет пространственные позиции для каждого из шаблонных значений. Подблок с натуральной структурой кодируется посредством квантования значений пикселей, которое выражается в усечении младших двух битов.
Процесс кодирования блока 2×4 D-способом раскрывается на Фиг.7.1, 7.2. На шаге 700 определяется подблок с регулярной (шаблонной) структурой. Для этого определяются шаблонные значения левого и правого подблоков 2×2, затем определяются ошибки приближения левого и правого подблоков 2×2 шаблонным кодированием. Исходя из сравнения вычисленных ошибок определяется подблок с наиболее выраженной регулярной структурой. Описанные действия выполняются на шагах 701, 702.
Шаблонные значения определяются в соответствии со следующими формулами:
0
1
Здесь: C, C - шаблонные значения, k - индекс подблока. k=0 - левый подблок, k=1 - правый подблок.
Ошибка B1E(k) приближения подблока шаблонным кодированием вычисляется по формуле:
После этого номер подблока, который будет закодирован с использованием шаблонного кодирования, помещают в исходящий сжатый поток.
Второй способ далее будем называть F-способом. Он реализуется на шаге 111. Способ предназначен для эффективного представления блоков, состоящих их 2×4 пикселей с градиентной структурой. Способ может быть применен к каждому цветовому каналу индивидуально. Для обеспечения заданной скорости потока, а также поддержки высокой точности представления градиентных переходов в качестве элементов кодирования используются средние опорные точки, среднее значение модулей горизонтальных межпиксельных разностей, а также знаки каждой из разностей. Опорные точки, а также направления отдельных межпиксельных разностей показаны на Фиг.8.1. Блок-схема способа показана на Фиг.8.2. На шаге 800 вычисляются 6 разностных величин: D1, D2, D3, D4, D5, D6. На шаге 801 вычисляется среднее значение модулей величин D1…D6. На шаге 802 вычисляются знаки каждой из разностных величин. В качестве кодовой информации передается среднее значение модулей разностей, знаки разностей, а также две опорные точки - A2, B2 - шаг 803. Опорные точки передаются без потерь. Таким образом, F-способ может быть сформулирован следующим образом: кодирование блоков, содержащих градиентные участки, выполняют одновременно или отдельно по трем каналам, осуществляя следующие операции:
- вычисляют шесть разностных величин D1, D2, D3, D4, D5, D6 по формулам: D1=A1-A2; D2=A2-A3; D3=A3-A4; D4=B1-B2; D5=B2-B3; D6=B3-B4;
- вычисляют среднее значение модулей разностных величин D1…D6;
- вычисляют знаки каждой из разностных величин D1…D6;
- в качестве кодовой информации передают среднее значение модулей разностей, знаки разностей, а также две опорные точки - A2, B2.
Третий способ предназначен для эффективного кодирования высокочастотных тестовых изображений и далее будет обозначаться как M-способ. Он применяется на шаге 117. Способ включает в себя три подспособа кодирования.
Первый подспособ кодирования заключается в применении несимметричного равномерного квантования пикселей исходного блока. При этом каждый пиксель блока, а точнее, интенсивность по каждому цветовому каналу для каждого пикселя блока кодируется тремя или четырьмя битами. 3/4-битные коды, описывающие закодированные значения пикселей, вычисляются по следующим формулам (здесь индекс i обозначает ось ординат, j обозначает ось абсцисс):
где I - значение пикселя исходного блока; C - битовый код, который кодирует соответствующий пиксель. Процедура декодирования пикселей, закодированных таким образом, описывается следующими формулами (здесь D - декодированный пиксель):
Второй подспособ кодирования основан на усреднении с частичным огрублением двух подблоков 2×2 в пределах блока 2×4. При этом кодовые величины вычисляются согласно следующим формулам:
Для этого подспособа процедура декодирования выполняется в соответствии со следующими формулами:
Третий подспособ кодирования основан на частичной реконструкции одного из цветовых каналов по двум другим, пиксели которых кодируются путем усечения нескольких младших разрядов. В частности, красный и зеленый канал кодируются согласно формулам:
в то время как два крайних пикселя синего канала, которые не могут быть реконструированы из красного и зеленого каналов, кодируются согласно следующим формулам:
,
Процедура декодирования в этом случае реализуется в соответствии с выражениями:
После применения к обрабатываемому блоку 2×4 описанных выше трех подспособов определяется подспособ, обеспечивающий минимальную ошибку. Его номер (один из трех) передается в первых двух битах сжатого потока.
Четвертый способ, используемый при кодировании блока 2×4, будем определять как способ кодирования доминирующего цвета или O-способ. Он применяется на шаге 112. Способ является эффективным, если один цветовой канал по своим энергетическим характеристикам существенно превосходит другие цветовые каналы в пределах блока. В данном способе анализируется четыре ситуации: доминирующим является яростный канал, красный, зеленый или синий. Для указания номера доминирующего цвета используется 2-битный индекс. Значения пикселей доминирующего цвета передаются без искажений 8-битными значениями. Значения двух оставшихся каналов кодируются посредством усреднения в пределах каждого из каналов и передачи каждого такого среднего значения 8-битной величиной. Подробная блок-схема данного способа представлена на Фиг.9. На шаге 900 рассчитываются суммы интенсивностей пикселей по каждому из каналов красного, зеленого или синего. Затем на шагах 901, 902, 903 выполняется последовательное сравнение значений трех рассчитанных сумм с заданным наперед пороговым значением. Принятие решения о номере доминирующего канала осуществляется на шагах 904, 905, 906 в зависимости от результатов сравнения на шагах 901, 902, 903. Если ни одно сравнение не было успешным, предполагается, что доминирующим является яростный канал, а цветоразностные каналы являются минорными - шаг 907. Затем на шаге 908 вычисляются средние значения минорных каналов. Затем интенсивности пикселей доминирующего канала, а также средние значения минорных каналов кодируются без потерь - шаги 909, 910. Таким образом, сжатый поток состоит из 2-битного индекса доминирующего канала, восьми 8-битных значений пикселей доминирующего канала, а также двух 8-битных значений средних величин минорных каналов.
Пятый способ мы назвали L-способом. Способ применяется на шаге 114 к блоку 2×4 для всех трех цветовых каналов одновременно. При этом цветовые каналы обрабатываются независимо. В пределах блока 2×4 для каждого подблока 2×2 формируется своя двухцветная палитра. Затем используется один из трех режимов кодирования двух палитр: режим дифференциального кодирования палитр, режим дифференциального кодирования цветов в пределах палитры или явное квантование цветов. Использование дифференциального кодирования палитр или дифференциального кодирования цветов палитр обеспечивает в ряде случаев повышенную точность передачи. Кроме того, зачастую одна из палитр оказывается состоящей из равных цветов.
Ввиду этого предложена дополнительная обработка цветов, которая может повысить вероятность использования режима дифференциального кодирования. Блок-схема способа представлена на Фиг.10. На шагах 1000 и 1001 выполняется определение двухцветных палитр для левого и правого подблоков 2×2. На шаге 1003 для оценки возможности использования режима дифференциального кодирования палитр выполняется проверка логического условия:
InterCondition≡(-2≤C00-C10<2)∧(-1≤C01-C11≤2),
Здесь: (C00, C01) цвета первой палитры (левый подблок 2×2), (C10, C11) цвета второй палитры (правый подблок 2×2). Если указанное условие верно, то цвета первой палитры передаются без потерь, в то время как цвета второй палитры кодируются как поправки к цветам из первой - шаг 1011. При этом выполняются следующие действия:
- вычисляются два индекса, значения которых преобразуются в числа больше либо равные нулю согласно выражениям:
TIdx_y=C00-C10+2. Диапазон индекса: [0…3];
TIdx_x=C01-C11+1. Диапазон индекса: [0…3];
- рассчитанные индексы преобразуются в 4-битную величину CDVal (Cumulative Difference Value - обобщенная разностная величина) с использованием таблицы, описывающей совместное распределение индексов TIdx_x/TIdx_y:
TIdx_x=0
TIdx_x=1
TIdx_x=2
TIdx_x=3
TIdx_y=0
0
1
2
3
TIdx_y=1
4
5
6
7
TIdx_y=2
8
9
10
11
TIdx_y=3
12
13
14
15
Использование таблицы распределения индексов является дополнительным отличительным способом кодирования, поскольку совокупность величин индексов TIdx_x/TIdx_y уже сама по себе обеспечивает возможность кодирования разностной информации. Однако использование таблицы позволяет расширить диапазон возможных взаимных значений цветов палитр за счет потенциальной локализации и удаления редко встречающихся комбинаций, а также кодирования иных. Для декодирования индексов TIdx_x/TIdx_y используются две дополнительные таблицы:
CDVal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TIdx_y
-2
-2
-2
-2
-1
-1
-1
-1
0
0
0
0
1
1
1
1
CDVal
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
TIdx_x
-1
0
1
2
-1
0
1
2
-1
0
1
2
-1
0
1
2
Они позволяют вычислить соответствующие индексы на основе четырехбитного значения CDVal. Восстановление значений разностей выполняется на основе формул:
C00-C10=TIdx_y-2. Новый диапазон: [-2…2]
C01-C11=TIdx_x-1. Новый диапазон: [-1…2]
Дополнительная обработка цветов палитр, увеличивающая вероятность использования дифференциального кодирования палитр, заключается в следующем.
- Детектирование факта равенства цветов в каждой палитре и установление флага равенства (FP) в 1 в случае равенства:
if(C00=C01)→FP1=1
else→FP1=0
if(C10=C11)→FP2=1
else→FP2=0
- Проверка того, что только одна палитра имеет равные цвета:
FP1+FP2=1
- Предположим, что цвета первой палитры равны (C00=C01). Тогда в первую палитру должен быть «вставлен» цвет из второй палитры, который является наиболее удаленным от изначальных цветов первой палитры. Для этого осуществляется проверка условия |C00-C11|<|C00-C10| и выполняется вставка фиктивного цвета:
If|С00-С11|<|С00-С10|→С00=С10
Else С01=С11
- В случае если вставка фиктивного цвета была осуществлена, информация об этом должна быть сохранена в логической временной переменной для того, чтобы в случае, если режим дифференциального кодирования палитр, тем не менее, невозможно задействовать, восстановить измененный цвет.
Конечным шагом дифференциального режима кодирования палитр является генерация карты цветов, состоящей из четырех записей - шаг 1010. В случае если на шаге 1003 условие оказалось ложным, каждая палитра кодируется независимо в одном из двух возможных режимов: режиме дифференциального кодирования цветов палитры или режиме явного квантования. На шаге 1004 InterDifbit устанавливается в нулевое значение, чтобы обеспечить декодер информацией о невозможности использования режима дифференциального кодирования палитр. Затем цвета в каждой палитре переупорядочиваются таким образом, что первый по порядку следования цвет в каждой из палитр соответствует первому (левому - верхнему) пикселю в пределах соответствующего подблока 2×2. Затем на шаге 1005 осуществляется проверка условия для дифференциального кодирования цветов в пределах каждой из палитр. В целях упрощения на блок-схеме отражены шаги кодирования только для палитры, соответствующей левому блоку. Если условие верно, IntraDifBit устанавливается в единичное значение, первый цвет кодируется без потерь, второй цвет кодируется как 2-битная поправка к первому цвету - шаг 1007. Если на шаге 1006 условие оказалось ложным, каждый цвет кодируется путем усечения младших трех разрядов - шаг 1008. Восстановление усеченных битов осуществляется бинарным значением 100b. Аналогичные действия выполняются для второй (правой) палитры. В заключение на шаге 1009 формируется карта цветов, состоящая из трех записей. L-способ использует два вида карты цветов: карту цветов, состоящую из трех записей, и карту цветов, состоящую из четырех цветов. Карта цветов, состоящая из трех записей, означает, что первый пиксель в блоке всегда кодируется первым по порядку следования цветом палитры. Каждая запись в карте цветов является битовым кодом цвета, используемого для кодирования данного пикселя. Определение цвета, которым будет закодирован текущий пиксель, основано на переборе всех цветов палитры и выборе того, абсолютная разница между интенсивностью которого и исходным значением пикселя минимальна. Определение цветов палитры может быть реализовано с использованием различных математических и алгоритмических подходов, например на основе метода наименьших квадратов. Блок-схема способа определения двух цветов, предложенного в данном изобретении, представлена на Фиг.11. Этот способ представляет собой компромисс между сложностью и эффективностью и заключается в разделении исходных значений четырех пикселей на две группы и расчете средних значений в пределах каждой группы, которые затем рассматриваются как цвета палитры.
Шестой способ называется U-способ и применяется на шаге 115. Способ предназначен для областей цветного изображения, в которых присутствует комбинация комплексных и относительно равномерных участков в пределах одного цветового канала или в пределах одного обрабатываемого подблока. Способ состоит из двух подспособов: U1 и U2, которые используются для компактного представления исходного блока 2×4 и оптимизированы под возможные комбинации комплексных и относительно равномерных участков изображения. На основе расчета ошибок приближения исходного блока обоими подспособами выбирается оптимальный, то есть обеспечивающий меньшую ошибку. Общая блока схема U-способа представлена на Фиг.12. Рассмотрим подспособ U1. Он применяется для подблока 2×2, входящего в состав исходного блока 2×4, и эффективен в случае, если один из трех цветовых каналов подблока 2×2 может быть закодирован средним значением, в то время как оставшиеся два канала (так называемые «активные цвета») кодируются с использованием NSW-преобразования и процедуры FQvT. Блок-схема подспособа представлена на Фиг.13.1 (в целях упрощения на блок-схеме показаны шаги только для одного подблока). На шаге 1300 рассчитываются средние значения mR, mG, mB по каждому цветовому каналу в пределах обрабатываемого подблока. Затем для каждого цветового канала рассчитывается сумма абсолютных разностей (SAD) - шаг 1301. В качестве примера ниже приведена формула расчета SAD для канала красного:
R
R
R
R
R
SAD=|A-mR|+|B-mR|+|C-mR|+|D-mR|
Затем определяется цветовой канал, который может быть оптимально передан средним значением: SAD значения цветовых каналов сравниваются с установленным наперед пороговым значением (SMOOTH_THRESHOLD) в фиксированном порядке: зеленый канал, затем красный канал, затем синий. Если все SAD больше порогового значения, выбирается тот цветовой канал, который обладает минимальным SAD - шаги 1302, 1303. Определяется, является ли среднее значение «равномерного» цветового канала малым или нет, путем сравнения с другим заданным наперед порогом, равным тридцати двум. Если среднее значение «равномерного» цветового канала мало, вместо явного указания номера этого цветового цвета 2-битным префиксом (номер цветового канала может принимать значение 0, 1 или 2) этот 2-битный префикс устанавливается равным трем и далее передается дополнительно 2-битное значение, явно указывающее номер «равномерного» цветового канала. Затем среднее значение «равномерного» цветового канала кодируют 3-битным значением путем усечения младших двух битов. В противном случае среднее значение кодируется 6-битным значением путем усечения младших двух разрядов - шаги 1304, 1305, 1306. Оставшиеся два цвета («активные цвета») в пределах подблока 2×2, обозначенные далее как первый и второй цвета, кодируются с использованием NSW-преобразования и FQvT следующим образом (шаги 1307, 1308):
- для пикселей в пределах первого и второго цвета в пределах данного подблока выполняется NSW-преобразование. В результате рассчитываются два набора значений: {s1, h1, v1, d1}, {s2, h2, v2, d2};
- {h1, v1, d1}, {h2, v2, d2} кодируются с использованием таблицы квантователей - Таблица 8. При этом каждый набор разностных величин {h1, v1, d1}, {h2, v2, d2} кодируется с использованием своего квантователя. Процедура квантования подобна FQvT квантованию, описанному выше. Оптимальный квантователь вычисляется исходя из определения квантователя среди восьми возможных так, что обеспечивается минимальная ошибка приближения каждого из наборов разностных величин {h1, v1, d1}, {h2, v2, d2};
- Величины s1, s2 кодируются в одном из двух режимов:
- 6/6 битов: режим используется, если среднее значение «равномерного» цветового канала мало и битовый бюджет позволяет кодировать s1, s2 путем усечения младших двух разрядов;
- дифференциальный режим используется, если режим «6/6 битов» не может быть применен, при этом выполняются следующие шаги:
- Оценивается ошибка, вызванная кодированием s1, s2 в 5/5 битов (усечение младших трех разрядов):
ErrQuant=|s1-(s1&0×F8)|0×04|+|s2-(s2&0×F8)|0×04|
Оценивается ошибка, вызванная квантованием s1, s2 в 6/6 битов с последующим дифференциальным представлением s2 как 3-битной знаковой поправки к s1:
- temp_s1=s1&0×FC; temp_s2=s21&0×FC;
- temp_s2=temp_s2-temp_s0;
- clamp(temp_s2, -31, 31) - «ограничение по двум порогам»
- temp_s2=temp_s2&0×FC
- temp_s2=temp_s2+temp_sl
ErrDifQuant=|s1-temp_s1+s2-temp_s2;
- Если (ErrQuant<ErrDifQuant), s1, s2 кодируются в режиме 5/5 битов путем усечения младших трех разрядов; иначе s1, s2 кодируются как: 6 битов (s1)+3 бита + знак (s2-s1).
Формат сжатого потока является важным аспектом U1 подспособа:
- Девятнадцать битов → сжатая информация о средних значениях (пояснено на Фиг.13.2);
- Три бита → номер квантователя: для первого активного цветового канала;
- (3+3+3) бит → индексы уровней восстановления разностных значений {h, v, d} первого активного цветового канала;
- Три бита → номер квантователя для второго активного цветового канала;
- (3+3+3) бит → индексы уровней восстановления разностных значений {h, v, d} второго активного цветового канала.
Таким образом, для кодирования одного подблока 2×2 требуется сорок три бита. Описанные выше шаги выполняются для обоих подблоков 2×2, входящих в состав обрабатываемого блока 2×4.
Таблица 8
Таблица квантования. U1 подспособ
Quantize - Set N
Id×0
Id×1
Id×2
Id×3
Id×4
Id×5
Id×6
Id×7
0
0
-18
-34
-45
0
18
34
45
1
-14
-60
-115
-160
14
60
115
160
2
-6
-38
-62
-95
6
38
62
95
3
-56
-77
-100
-112
56
77
100
112
4
-70
-107
-142
-160
70
107
142
160
5
0
-17
-32
-130
0
17
32
130
6
-53
-125
-196
-232
53
125
196
232
7
-16
-65
-100
-120
16
65
100
120
В случае если в одном цветовом канале в пределах блока 2×4 пиксели одного подблока 2×2 образуют равномерную структуру, в то время как пиксели второго подблока 2×2 образуют неравномерную область, эффективным способом кодирования является U2 подспособ, блок-схема которого показана на Фиг.14; подробная блок-схема процесса кодирования отдельно взятого цветового канала в пределах блока 2×4 показана на Фиг.15. Каждый цветной блок 2×4 рассматривается как три независимых блока по трем цветовым каналам: красный блок 2×4, зеленый блок 2×4 и синий блок 2×4. Каждый из них расщепляется на два смежных подблока 2×2 - шаг 1500. Для каждого из них рассчитывается ошибка приближения средним значением - шаги 1501, 1502. В качестве ошибки, не снижая общности, выбрана SAD, описанная выше. Затем на шаге 1503 определяется равномерный подблок с последующим его кодированием - шаг 1504 или 1506. Второй подблок кодируется с использованием NSW-преобразования и процедуры FQvT - шаги 1505, 1507. Соответствующая таблица квантования представлена в таблице 9. Каждая разностная величина из {h, v, d} кодируется посредством 3-битного индекса, указывающего лучший уровень восстановления в пределах квантователя, номер которого также передается 3-битным значением, s-значение кодируется 7-битовым значением путем усечения младшего разряда, который восстанавливается нулевым значением. Для указания подблока, который является равномерным, используется 1-битный индекс. Таким образом, каждый цветовой канал в пределах блока 2×4 кодируется с использованием 7+(3+3+3+3)+1+8=28 битов, что составляет восемьдесят четыре бита на весь блок 2×4.
Таблица 9
Таблица квантования. U2 подспособ
Номер квантователя
Id×0
Id×1
Id×2
Id×3
Id×4
Id×5
Id×6
Id×7
0
-60
-141
-178
-233
60
141
178
233
1
-2
-16
-28
-50
2
16
28
50
2
-10
-76
-150
-190
10
76
150
190
3
-44
-80
-108
-129
44
80
108
129
4
-100
-150
-201
-227
100
150
201
227
5
-1
-2
-3
-5
1
2
3
5
6
-8
-38
-65
-88
8
38
65
88
7
-60
-110
-160
-170
60
110
160
170
Последний способ этой группы называется способом кодирования на основе преобразования Адамара (H-способ). Способ применяется на шаге 116. В H-способе исходный блок 2×4 рассматривается как совокупность двух подблоков 2×2, и применяется известное преобразование Адамара (иначе называемое целочисленное Дискретное Косинусное Преобразование 2×2 - см. "Multiresolution progressive image transmission using a 2×2 DCT", Seock Hoon Woo, Chee Sun Won // IEEE 07803-5123-1/99) [7] к каждому из них с последующей специально разработанной процедурой кодирования FQvT. Преобразование описывается следующими формулами:
Прямое преобразование:
Обратное преобразование:
Известно, что данное преобразование осуществляет разделение исходного сигнала на компоненты с различной визуальной значимостью для наблюдателя. Исходя из этого диагональная компонента преобразования - dD может быть установлена в нулевое значение без существенного ухудшения качества. Оставшиеся компоненты S, dH, dV кодируются следующим образом:
- S компонента кодируется 6-битным значением путем усечения двух младших разрядов. Восстановление осуществляется двоичным значением 10b;
- {dH, dV} компоненты квантуются путем поиска наилучшего квантователя и наилучшего уровня восстановления в пределах квантователя.
Для каждого квантователя, входящего во множество из восьми квантователей, определяется наилучший уровень восстановления компонент {dH, dV} исходя из минимизации модуля разности между уровнем восстановления и значением соответствующей компоненты. Ошибка кодирования {dH, dV} компонент каким-либо квантователем рассчитывается путем суммирования модуля разницы соответствующего уровня восстановления и значения каждой из компонент, которая является минимальной среди всех возможных в пределах данного квантователя. Затем определяется квантователь, который обеспечивает минимальную ошибку кодирования. Таблица квантования, оптимизированная для квантования {dH, dV} компонент, представлена в Таблице 10.
Таблица 10
Таблица квантования {dH, dV} компонент
Номер квантователя
Id×0
Id×1
Id×2
Id×3
Id×4
Id×5
Id×6
Id×7
0
-6
-47
-86
-106
6
47
86
106
1
-20
-30
-41
-47
20
30
41
47
2
-1
-20
-38
-48
1
20
38
48
3
-3
-10
-16
-20
3
10
16
20
4
-18
-40
-64
-75
18
40
64
75
5
-6
-16
-26
-32
6
16
26
32
6
-8
-40
-73
-89
8
40
73
89
7
-9
-30
-52
-63
9
30
52
63
Каждый подблок 2×2 в пределах одного цветового канала кодируется с использованием шести битов для кодирования среднего, 3-битного номера квантователя и двух 3-битных индексов для кодирования оптимальных уровней восстановления dH, dV компонент.
Выбор способа кодирования для текущего обрабатываемого блока 2×4 основан на определении способа кодирования среди всей совокупности способов, используемых в данном изобретении, обеспечивающего минимизацию ошибки кодирования. Исходя из общих рассуждений следует, что эффективность и адекватность меры оценки искажения (ошибки кодирования) может оказывать существенное влияние на визуальное качество сжатого изображения. На основе проведенного анализа различных способов оценки искажений, не ограничивая общности, в данном изобретении использованы два способа оценки искажений, подробное описание которых дано ниже.
Необходимо подчеркнуть, что описанные два способа не ограничивают применение иных способов оценки визуального качества, а лишь являются вариантами реализации. Рассмотрим блок пикселей 2×4 по всем трем цветовым каналам - Фиг.16. Первым способом оценки искажений является расчет Взвешенной Среднеквадратичной Ошибки (B-СКО, WMSE)
Здесь символы A, B, C, D обозначают пиксели, расположенные в исходном блоке, как это показано на Фиг.16. Символы A, B, C, D с верхним подчеркиванием обозначают пиксели, расположенные в искаженном (закодированном) блоке. Wc являются весовыми коэффициентами, отражающими относительную значимость цветового канала. Экспериментально установлено, что приемлемые результаты с точки зрения визуального восприятия сжатого изображения могут быть получены со следующими значениями весовых коэффициентов:
Красный канал
Зеленый канал
Синий канал
W<sub>C</sub> value
6
16
4
Второй способ оценки искажений, предложенный в данном изобретении, назван Взвешенный Квадратичный Макс-Макс Критерий (ВКММК, WSMMC). Рассмотрим подблок 2×2, входящий в блок 2×4 - Фиг.16. Для определенности рассмотрим первый подблок (A1, B1, C1, D1 пиксели). Расчет WSMMC состоит из следующих шагов:
- Рассчитывают взвешенный квадрат максимума попиксельного отклонения между исходным и закодированным блоком по всем трем цветовым каналам:
- Рассчитывают сумму величин, определенных на первом шаге:
- Рассчитывают максимум среди величин, определенных на первом шаге:
R
G
B
MMax=MAX[MaxSq, MaxSq, MaxSq]
- Рассчитывают сумму величин, полученных на втором и третьем шагах:
WSMMC=SMax+Mmax
Чтобы рассчитать WSMMC для всего блока 2×4, необходимо сложить WSMMC-значения, рассчитанные для обоих подблоков 2×2.
Выбор способа компрессии состоит из следующих пунктов:
- Левый и правый подблоки, входящие в состав одного блока 2×4, кодируются раздельно пятью известными методами: N, P, C, S, E-методами. После сжатия каждого подблока одним из пяти известных методов N, P, C, S, E выполняется расчет ошибки согласно одному из способов, описанных выше, а также осуществляется формирование промежуточных битовых потоков;
- Для каждого из двух подблоков определяется метод, дающий минимальную ошибку - шаги 118, 119;
- На основе результатов пункта 2 для блока 2×4, состоящего из двух подблоков 2×2, определяется наилучшая комбинация методов N, P, C, S, E, обеспечивающая минимальную комбинационную погрешность (ошибку) кодирования блока 2×4 в виде двух подблоков 2×2 - шаг 121;
- Весь исходный блок 2×4 обрабатывается каждым из семи способов D, O, M, F, L, U, H, которые оптимизированы для сжатия блока 2×4. При этом после кодирования блока любым из указанных способов рассчитывается ошибка кодирования согласно одному из способов, описанных выше;
- Вычисляется минимальная ошибка среди ошибок, вызванных применением семи известных способов D, O, M, F, L, U, H к исходному блоку 2×4 - шаг 120;
- Вычисляется минимальная ошибка. В результате определяется оптимальный способ кодирования, обеспечивающий минимальную ошибку - шаг 122.
Каждый обрабатываемый блок 2×4 состоит из пикселей, каждый из которых представлен тремя цветовыми компонентами, каждая из которых изначально представлена 10-битным значением, в результате компрессии кодируется ровно 100 битами. Они представляют собой так называемый элементарный сжатый пакет, который состоит в свою очередь из VLEH, сжатых битов, битов, представляющих информацию о младших разрядах в компактном виде, и дополняющих битов (опционально).
Совокупность информации о возможных методах кодирования (исходя из всех возможных в рамках данного изобретения комбинаций), количестве сжатых битов, количестве битов, требуемых для кодирования младших разрядов, длине VLEH и значений битов, входящих в него, а также количестве дополняющих битов, представлена в таблице 11. Значения и длины VLEH и соответственно, количество битов, необходимых для кодирования младших разрядов, а также количество дополняющих битов зависят от реализации, однако общий принцип формирования выходного сжатого потока является одним из ключевых принципов, отличающих данное изобретение. В таблице имя метода включает одну-две буквы. В последнем случае расшифровка имени осуществляется следующим образом: первая буква соответствует методу, кодирующему левый подблок 2×2, вторая буква соответствует методу, кодирующему правый подблок 2×2.
Каждый заголовок может занимать от 1 до 10 битов; номер бита, указанный в таблице, означает порядок, в котором соответствующий бит помещается / извлекается из битового потока.
Кодирование младших разрядов (LSB-кодирование) относится к эффективному методу представления двух младших разрядов исходных 10-битных значений пикселей в пределах обрабатываемого блока 2×4 по одному или нескольким цветовым каналам. В данном изобретении предложены четыре различные процедуры LSB кодирования.
3-битное кодирование
Для каждого цвета выполняется расчет огрубленного среднего значения младших разрядов в пределах блока 2×4:
Здесь: Ic (x, y) - исходное 10-битное значение пикселя в цветовом канале C в позиции (x, y). mLSBc состоит из одного бита, описывающего огрубленное среднее младших разрядов. Огрубленные средние по всем трем цветовым каналам в совокупности образуют 3-битное число, являющееся закодированной информацией о младших разрядах в пределах блока 2×4.
4-битное кодирование
Этот способ кодирования младших разрядов аналогичен 3-битному LSB-кодированию для красного и синего цветовых каналов. Для зеленого канала используется более точное представление младших разрядов за счет раздельного кодирования младших битов левого и правого подблоков:
Огрубленные средние по красному и синему каналу в совокупности с двумя битами, описывающими огрубленные средние значения младших разрядов двух подблоков в зеленом канале, в совокупности составляют 4-битное значение, являющееся закодированной информацией о младших разрядах в пределах блока 2×4.
5-битное кодирование
Этот способ кодирования младших разрядов аналогичен 3-битному LSB-кодированию для синего цветового канала. Для красного и зеленого канала используется более точное представление младших разрядов за счет раздельного кодирования младших битов левого и правого подблоков:
Огрубленное 1-битовое среднее по синему каналу в совокупности с двумя битами, описывающими огрубленные средние значения младших разрядов двух подблоков в красном канале и двух битов, описывающих огрубленные средние значения младших разрядов двух подблоков в зеленом канале, в совокупности составляют 5-битное значение, являющееся закодированной информацией о младших разрядах в пределах блока 2×4.
6-битное кодирование
Для каждого цветового канала используется два бита для представления огрубленной информации о средних значениях младших разрядов подблоков в пределах исходного блока 2×4:
В этом методе 6-битное значение, являющееся закодированной информацией о младших разрядах в пределах блока 2×4, формируется путем объединения трех 2-битных значений, соответствующих огрубленной информации о среднем значении младших разрядов.
Восстановление соответствующих частей двух младших битовых плоскостей основано на получении одного или двух битов по каждому цветовому каналу и формировании среднего значения для двух битовых плоскостей по всему блоку 2×4 или формировании двух средних значений для двух битовых плоскостей в пределах левого и правого подблоков 2×2. Среднее значение (Middle Value) рассчитывается согласно формуле:
В иллюстративных целях на чертежах 17.1 и 17.2 показано расщепление исходных 10-битных значений в пределах блока 2×4 на две части: 8-битную и 2-битную, а также расщепление двух младших битовых плоскостей на две части: левую и правую.
Заявляемое изобретение может быть использовано в различных промышленных изделиях, которые применяются для обработки высококачественных цветных изображений высокого разрешения. Основная область применения - ТВ-вещание и ТВ-воспроизведение высококачественного видеопотока. Применение данного изобретения в изделиях потребительской электроники может привести к существенному снижению требований к внутренним аппаратным ресурсам, таким как память, шины данных, без снижения качественных характеристик изделий, что в свою очередь позволит снизить сопутствующие издержки. Помимо этого в область применения может быть включено телевидение сверхвысокой четкости, а также дисплеи для мобильных устройств. Кроме того, заявляемое изобретение может быть использовано как часть сложной системы видеокодирования для промежуточного хранения обрабатываемых изображений без визуальных потерь с целью снижения объемов требуемой памяти.