Способ эффективного кодирования и декодирования цифрового изображения
METHOD FOR EFFICIENT ENCODING AND DECODING OF A DIGITAL IMAGE

Изобретение относится к области обработки изображений, в частности к способам кодирования и декодирования цифровых изображений, и предназначено для использования в съемочной аппаратуре космических аппаратов (КА) дистанционного зондирования Земли, а также в системах передачи и записи потока изображений высокого разрешения в режиме реального времени.
Современные КА дистанционного зондирования Земли, такие как Worldwiev-2, RapidEye, SPOT-6, Pleiades-HR имеют на борту съемочную аппаратуру, формирующую изображения высокого разрешения со скоростью, значительно превосходящей пропускную способность радиолинии передачи данных в наземный пункт приема. В связи с этим КА используют бортовое кодирование изображений по стандарту JPEG2000 [1], который является способом сжатия цифровых изображений [2]. Существенным недостатком данного способа является высокая вычислительная сложность, что приводит к высокой ресурсоемкости и низкой пропускной способности при его бортовой реализации на программируемой логической интегральной схеме (ПЛИС).
Также известен способ сжатия (кодирования) цифрового изображения Subband-Block Hierarchical Partitioning (далее способ SBHP) [3], который из источников информации позиционируется как альтернатива стандарту JPEG2000 [1] с низкой вычислительной сложностью и входит в верификационную модель стандарта JPEG2000 (VM 4.2). Способ SBHP по сущности наиболее близок к предлагаемому изобретению и выбран за прототип.
Способ SBHP поддерживает все характеристики стандарта JPEG2000 и отличается только способом эффективного кодирования, где вместо вычислительно-сложного алгоритма бит-ориентированного арифметического кодирования используется сортировка вейвлет-коэффициентов по способу set-partitioning embedded block (SPECK) [4, 5] и дополнительное кодирование Хаффмана [6].
i,j
C
C
n
n
n
n
n
n
Способ SBHP (фиг. 1) заключается в выполнении следующих операций: считывают из внешней памяти цифровое изображение, представленное в виде двумерного блока C пикселов или вейвлет-коэфициентов размером N x N, определяют номер старшей битовой плоскости MSB двумерного блока пикселов с помощью выражения  и передают полученные данные на формирователь выходного потока, а считанный двумерный блок пикселов сохраняют в регистровой памяти для дальнейшей работы. Регистровая память позволяет иметь доступ к каждому биту пиксела, соответственно, к каждой битовой плоскости ВР двумерного блока пикселов. Далее кодирование идет последовательно от старшей битовой плоскости MSB до младшей битовой плоскости 0. Текущую битовую плоскость BP одновременно подают на блок рекурсивного кодирования значимых бит и блок кодирования уточняющих бит. Рекурсивное кодирование значимых бит заключается в обновлении содержимого вспомогательных массивов памяти LSS (список значимости множеств - содержит их координаты, размер и информацию о значимости), LIS (список незначимых множеств - содержит их координаты и размер), LSP (список значимых пикселов - содержит их координаты). А также в процессе рекурсивного кодирования битовой плоскости производят: сортировку на значимые и незначимые множества с учетом вспомогательных массивов памяти LSS и LIS и выражения  (т.е. S(B)=1, если в битовом множестве В есть хотя бы один ненулевой бит); по результатам анализа битовых множеств на значимость (0 или 1) заполняют карту значимости SM; выделение знаков значимых бит S с учетом содержимого вспомогательного массива памяти LSP. Карта значимости SM подвергается кодированию Хаффмана с получением сжатой карты значимости  Далее знаки значимых бит, сжатую карту значимости подают на формирователь выходного потока.
n
MSB
MSB
MSB
MSB-1
MSB-1
MSB-1
0
0
0
Кодирование уточняющих бит осуществляют с учетом обновленного массива памяти LSP с получением уточняющих бит RB, которые тоже подают на формирователь выходного потока. После обработки всех битовых плоскостей двумерного массива формирователь выходного потока объединяет все полученные данные и выдает выходной поток в следующем виде: MSB, SM, S, RB, SM, S, RB, … SM, S, RB. Декодирование цифрового изображения производится в обратном порядке.
Способ декодирования по сути выполняет все те же действия, что и в способе SBHP кодирования (приведенный выше), но в обратном порядке.
Способ SBHP [3] позволяет производить кодирование потока цифровой информации со скоростью 100 мегапикселей в секунду (что превышает примерно в 4 раза быстродействие JPEG2000) и сжимать изображения разрядности 11-12 бит с коэффициентами сжатия 2-20 раз с потерями и примеров 2 раза - без потерь с удовлетворительным качеством декодирования изображения.
Недостатком известного способа SBHP является высокая вычислительная сложность рекурсивной сортировки битовых множеств, которая при аппаратной реализации приводит к использованию большого количества памяти и низкой скорости кодирования и декодирования.
Задачей данного изобретения является снижение вычислительной сложности, увеличение быстродействия обработки данных и уменьшение объема используемой памяти, при сохранении хорошего качества кодирования и декодирования цифрового изображения.
Для решения поставленной задачи предложены способ эффективного кодирования цифрового изображения и способ эффективного декодирования цифрового изображения.
i,j
CB
C
C
C
i,j
k
n
HQT
4
CB
n
Сущность способа эффективного кодирования цифрового изображения заключается в следующем: из массива внешней памяти считывают по Z-развертке цифровое изображение, представленное в виде двумерного блока C размером N=N × N, где N - число пикселов в строке/столбце, с получением одномерного блока, который сохраняют в регистровой памяти кодера, одновременно с этим в кодере рассчитывают номер старшей битовой плоскости MSB двумерного блока C, анализируют знаки его значимых пикселов S, из одномерного блока выделяют битовые плоскости BP где n от 0 до MSB, которые далее последовательно и независимо друг от друга обрабатывают, для каждой битовой плоскости формируют L-уровневое иерархическое бинарное квадродерево m, где L=logN, при этом нулевой уровень формируют путем копирования в него всех битов битовой плоскости BP, а последующие уровни заполняют на основе предыдущих путем оценки значимости их бит согласно формуле
где
L
1
min
L
1
CB
n
n
min
CB
n
2
n
min
1
n
2
n
min
L
n
2
n
n
0..n..MSB
k
далее оценивают компактность карты значимости C для полученного L-уровневого иерархического бинарного квадродерева согласно формуле:  и компактность карты значимости С для 1 -уровневого иерархического бинарного квадродерева согласно формуле: затем выбирают минимальную компактность C=min(C, C, N) и по ее значению посредством реверсивного кодирования формируют 2-битный флаг F и карту значимости SM исходя из следующих условий: если минимальная компактность C равна размеру двумерного блока N, то 2-битному флагу Fприсваивается значение 11 и в карту значимости SM переносятся биты нулевого уровня иерархического бинарного квадродерева; если минимальная компактность C равна компактности карты значимости C для 1-уровневого иерархического бинарного квадродерева, то 2-битному флагу F присваивается значение 10 и в карту значимости SM переносятся биты первого уровня и все значимые биты нулевого уровня иерархического бинарного квадродерева; если минимальная компактность C равна компактности карты значимости C для L-уровневого иерархического бинарного квадродерева, то 2-битному флагу F присваивается значение 01 и в карту значимости SM переносятся все значимые биты уровней от L-1 до 0 иерархического бинарного квадродерева; карту значимости SM подвергают энтропийному кодированию с получением сжатой карты значимости  после обработки всех битовых плоскостей одномерного блока объединяют все полученные данные и формируют на выходе кодера поток кодированного цифрового изображения в следующем виде: номер старшей битовой плоскости MSB, сжатые карты значимости всех битовых плоскостей  разделенные 2-битными флагами F, и знаки всех значимых пикселов S.
CB
CB
C
C
C
0..n..MSB
k
n
n
n
n
2
n
2
n
2
4
CB
n
HQT
n
*
Сущность способа эффективного декодирования цифрового изображения заключается в следующем: на вход декодера подают размер N двухмерного блока, где N=N × N, N - число пикселов в строке/столбце, и поток кодированного цифрового изображения, представленный в виде: номер старшей битовой плоскости MSB, сжатые карты значимости всех битовых плоскостей  разделенные 2-битными флагами F, и знаки всех значимых пикселов S, в декодере сжатые карты значимости SM, где n от 0 до MSB-1, последовательно и независимо друг от друга подвергают энтропийному декодированию с получением карты значимости SM, одновременно с этим выделяют 2-битный флаг F, соответствующий сжатой карте значимости  и находят количество уровней L иерархического бинарного квадродерева исходя из условий: если F=11, то L=1; если F=10, то L=2; если F=01, то L=logN; далее посредствам реверсивного декодирования карты значимости SM и с учетом количества уровней L иерархического бинарного квадродерева формируют само L-уровневое иерархическое бинарное квадродерево m, начиная с уровня L-1 путем переноса бит из карты значимости SM на этот уровень в соответствии с условием:
где  х - текущий бит карты значимости,
HQT
n
n
k
i,j
нулевой уровень иерархического бинарного квадродерева m является битовой плоскостью BP одномерного блока, которую записывают в регистровую память, после обработки всех сжатых карт значимости  где n от 0 до MSB-1, с получением всех битовых плоскостей BP одномерного блока, а также учитывая знаки значимых пикселов S формируют одномерный блок, который затем преобразуют по Z-развертке в двухмерный блок C, который представляет собой декодированное цифровое изображение и подают его на выход декодера.
Считывание по Z-развертке цифрового изображения с получением одномерного блока при кодировании позволило упростить кодирование и снизить вычислительную сложность.
n
Возможность анализа знаков значимых пикселов, выделение из одномерного массива битовых плоскостей BP, где n от 0 до MSB, которые далее последовательно и независимо друг от друга обрабатывают способствует снижению вычислительной сложности, увеличению быстродействия обработки данных и уменьшению объема используемой памяти.
L
1
Формирование для каждой битовой плоскости L-уровневого иерархического бинарного квадродерева, оценивание компактности карты значимости C и С, выбор минимальной компактности, формирование 2-битного флага и карты значимости позволило сохранить хорошее качество цифрового изображения при кодировании и декодировании.
Формирование на выходе кодера потока кодированного цифрового изображения в определенном виде и последовательности обеспечивает корректную передачу закодированного цифрового изображения и обратного его качественного декодирования, что позволяет сохранить хорошее качество цифрового изображения.
Изобретение поясняется чертежами. На фиг. 1 приведена блок-схема способа SBHP (прототип). На фиг. 2 приведена блок-схема эффективного кодирования цифрового изображения. На фиг. 3 представлена блок-схема эффективного декодирования цифрового изображения.
i,j
CB
C
C
C
Предложенный способ эффективного кодирования цифрового изображения может быть реализован следующим образом (фиг. 2): из массива внешней памяти 1 цифровое изображение, представленное в виде двумерного блока C размером N=N × N, где N - число пикселов в строке/столбце кратное 4, подают на вход кодера 2 и там считывают при помощи преобразователя 3 по Z-развертке с получением одномерного блока. Процедура считывания по Z-развертке является классическим действием [7].
Полученный одномерный блок сохраняют в регистровой памяти 4 кодера 2 (фиг. 2). Одновременно с этим в преобразователе 3 рассчитывают номер старшей битовой плоскости MSB двумерного блока по формуле  и анализируют знаки его значимых пикселов согласно формуле  и полученные данные передают в формирователь 5 потока кодированного цифрового изображения.
n
Регистровая память 4 кодера 2 позволяет из одномерного блока выделить битовые плоскости BP, где n от 0 до MSB, так как регистровая память 4 представляет собой массив n-битных регистров, каждый из которых содержит n элементарных ячеек памяти триггеров (каждый триггер может хранить один бит информации). Следовательно, каждый пиксел одномерного блока записывается в свой регистр и у реверсивного кодера 6 в последующем в любой момент времени есть доступ к любому биту (битовой плоскости) пикселов.
HQT
4
CB
n
Далее из регистровой памяти 4 кодера 2 выделенные битовые плоскости последовательно и независимо друг от друга подают в реверсивный кодер 5, в котором для каждой битовой плоскости формируют L-уровневое иерархическое бинарное квадродерево m, где L=logN, при этом нулевой уровень формируют путем копирования в него всех битов битовой плоскости BP, а последующие уровни заполняют на основе предыдущих путем оценки значимости их бит согласно формуле
где
L
1
Реверсивный кодер 6 оценивает компактность карты значимости C для полученного L-уровневого иерархического бинарного квадродерева согласно формуле:  и компактность карты значимости С для 1 -уровневого иерархического бинарного квадродерева согласно формуле:
min
L
1
CB
n
n
min
CB
n
2
n
min
1
n
2
n
min
L
n
2
n
n
Затем реверсивный кодер 6 выбирает минимальную компактность C=min(C, C, N) и по ее значению посредством реверсивного кодирования формирует 2-битный флаг F и карту значимости SM исходя из следующих условий: если минимальная компактность C равна размеру двумерного блока N, то 2-битному флагу F присваивается значение 11 и в карту значимости SM переносятся биты нулевого уровня иерархического бинарного квадродерева; если минимальная компактность C равна компактности карты значимости С для 1-уровневого иерархического бинарного квадродерева, то 2-битному флагу F присваивается значение 10 и в карту значимости SM переносятся биты первого уровня и все значимые биты нулевого уровня иерархического бинарного квадродерева; если минимальная компактность C равна компактности карты значимости C для L-уровневого иерархического бинарного квадродерева, то 2-битному флагу F присваивается значение 01 и в карту значимости SM переносятся все значимые биты уровней от L-1 до 0 иерархического бинарного квадродерева. Полученные биты 2-битного флага F передают в формирователь 5 потока кодированного цифрового изображения.
n
n
Полученные карты значимости SM на выходе реверсивного кодера 6 содержат небольшую избыточность (порядка 1-3%), которую устраняют с помощью энтропийного кодирования для получения максимального коэффициента сжатия, поэтому биты карты значимости SM подвергают энтропийному кодированию с получением сжатой карты значимости  Энтропийное кодирование можно производить как в реверсивном кодере 6, так и в отдельном энтропийном кодере 7. Наиболее подходящим вариантом с точки зрения производительности является энтропийное кодирование с помощью детерминированных таблиц Хаффмана [6], которое и используется в данном способе. Однако для этих целей возможно использовать другой тип энтропийного кодирования, например адаптивное арифметическое кодирование.
Сжатую карту значимости  передают в формирователь 5 потока кодированного цифрового изображения.
n
Выше перечисленными действиями производят обработку всех битовых плоскостей BP, где n от 0 до MSB.
0..n..MSB
k
Формирователь 5 объединяет все полученные данные и формирует на выходе кодера 2 поток кодированного цифрового изображения в следующем виде: номер старшей битовой плоскости MSB, карты значимости всех битовых плоскостей  разделенные 2-битными флагами F, и знаки всех значимых пикселов S.
Из массива внешней памяти 1 на вход кодера 2 можно подавать любое цифровое изображение, которое может представлять собой пикселы исходного (ни чем не обработанного) цифрового изображения или пикселы цифрового изображения предварительно обработанного, например, с помощью двухмерного декоррелирующего преобразования (вейвлет, Фурье, Баттерворт), которое перераспределяет энергию в пикселах цифрового изображения. Однако для получения максимальной эффективности кодирования цифрового изображения необходимо использовать предварительно обработанное изображение.
В способе эффективного декодирования цифрового изображения по сути выполняют все те же действия, что и в способе эффективного кодирования (приведенном выше), но в обратном порядке.
CB
CB
C
C
C
0..n..MSB
k
n
Предложенный способ эффективного декодирования цифрового изображения может быть реализован следующим образом (фиг. 3): на вход декодера 1 подают размер N двухмерного блока, где N=N × N, N - число пикселов в строке/столбце, и поток кодированного цифрового изображения, представленный в виде: номер старшей битовой плоскости MSB, сжатые карты значимости всех битовых плоскостей разделенные 2-битными флагами F, и знаки всех значимых пикселов S. В декодере 1 посредством анализатора 2 выделяют сжатые карты значимости  где n от 0 до MSB-1, и которые далее последовательно и независимо друг от друга подвергают энтропийному декодированию с получением карты значимости SM. Энтропийное декодирование можно производить как в отдельном энтропийном декодере 3, так и в реверсивном декодере 4. Метод энтропийного декодирования должен быть идентичным тому методу энтропийного кодирования (таблицы Хаффмана или арифметическое кодирование), который был применен в кодере.
k
n
n
n
2
n
2
n
2
4
CB
*
Одновременно с этим анализатор 2 выделяет знаки значимых бит S, а также 2-битный флаг F, соответствующий сжатой карте значимости SM, и находит количество уровней L иерархического бинарного квадродерева исходя из условий: если F=11, то L=1; если F=10, то L=2; если F=01, то L=logN.
n
HQT
n
HQT
n
В реверсивном декодере 4 посредствам реверсивного декодирования карты значимости SM и с учетом количества уровней L иерархического бинарного квадродерева формируют само L-уровневое иерархическое бинарное квадродерево m, начиная с уровня L-1 путем переноса бит из карты значимости SM на этот уровень. L-уровневое иерархическое бинарное квадродерево m формируется при декодировании сверху вниз по уровням на основании предыдущего уровня и бит карты значимости SM в соответствии с условием:
где  х - текущий бит карты значимости.
HQT
n
Нулевой уровень иерархического бинарного квадродерева m является битовой плоскостью BP одномерного блока, которую записывают в регистровую память 5 декодера 1.
k
k
Декодер знаков 6 после декодирования MSB битовых плоскостей получает знаки значимых пикселов S одномерного блока от анализатора 2 и восстанавливает знаки всех пикселов одномерного блока в массиве регистровой памяти 5 на основании значений их амплитуд (если амплитуда больше нуля, то знак переносится из S в соответствующий пиксел, иначе пиксел пропускается).
n
n
k
i,j
*
После обработки всех сжатых карт значимости SM, где n от 0 до MSB-1, с получением всех битовых плоскостей BP одномерного блока, а также учитывая знаки значимых пикселов S формируют одномерный блок, который затем с помощью преобразователя 7 преобразуют по координатам Z-развертки в двухмерный блок C, который представляет собой декодированное цифровое изображение, и подают его на выход декодера 1.
Предложенный способ эффективного кодирования и декодирования цифрового изображения, основанный на построении иерархического квадродерева для битовой плоскости, характеризуется упрощенной схемой формирования карты значимости, что позволяет сократить количество ресурсов памяти ~ в 1,5 раза и повысить быстродействие ~ в 2 раза (200 мегапикселей в секунду) по сравнению с прототипом, а также сжимать изображения разрядности 11-12 с коэффициентами сжатия от 2 до 20-ти с потерями и ~ 2 без потерь с хорошим качеством декодированного цифрового изображения.
Источники информации
1. Bormin Huang, Satellite Data Compression, Springer New York DordrechtHeidelberg, London, 2011, p. 33-45.
2. Taubman D.S. and Marcellin M.W., JPEG2000: Fundamentals, Standards and Practice. Kluwer Academic Publishers, Boston, 2002.
3. C. Chrysafis, A. Said, A. Drukarev, A. Islamand W.A. Pearlman. SBHP - A low complexity wavelet coder. IEEE Int. Conf. Acoust, Speech Signal Processing (ICASSP), Vol. 4, pp. 2035-2038, June 2000.
4. US 6965700 B2 (WILLIAM A. PEARLMAN), Nov. 15, 2005, весь документ.
5. W.A. Pearlman, A. Islam, N. Nagaraj and A. Said. Efficient, low-complexity image coding with a set-partitioning embedded block coder. IEEE transactions on circuits and systems for video technology, Vol. 14, No. 11, November 2004.
6. Huffman D.A. - A method for the construction of minimum redundancy codes. Proc. Inst. Electr. Radio Eng., Vol. 40, No. 9, pp. 1098-1101, September 1952.
7. G.M. Morton. A computer oriented geodetic data base and a new technique in file sequencing. Technical report, IBM Ltd., Ottawa, Ontario, Canada, 1966.