Результат интеллектуальной деятельности: Способ эффективного кодирования и декодирования цифрового изображения

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

Современные КА дистанционного зондирования Земли, такие как 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].

Способ SBHP (фиг. 1) заключается в выполнении следующих операций: считывают из внешней памяти цифровое изображение, представленное в виде двумерного блока C_i,j пикселов или вейвлет-коэфициентов размером N_C x N_C, определяют номер старшей битовой плоскости MSB двумерного блока пикселов с помощью выражения и передают полученные данные на формирователь выходного потока, а считанный двумерный блок пикселов сохраняют в регистровой памяти для дальнейшей работы. Регистровая память позволяет иметь доступ к каждому биту пиксела, соответственно, к каждой битовой плоскости ВР_n двумерного блока пикселов. Далее кодирование идет последовательно от старшей битовой плоскости MSB до младшей битовой плоскости 0. Текущую битовую плоскость BP_n одновременно подают на блок рекурсивного кодирования значимых бит и блок кодирования уточняющих бит. Рекурсивное кодирование значимых бит заключается в обновлении содержимого вспомогательных массивов памяти LSS (список значимости множеств - содержит их координаты, размер и информацию о значимости), LIS (список незначимых множеств - содержит их координаты и размер), LSP (список значимых пикселов - содержит их координаты). А также в процессе рекурсивного кодирования битовой плоскости производят: сортировку на значимые и незначимые множества с учетом вспомогательных массивов памяти LSS и LIS и выражения (т.е. S_n(B)=1, если в битовом множестве В есть хотя бы один ненулевой бит); по результатам анализа битовых множеств на значимость (0 или 1) заполняют карту значимости SM_n; выделение знаков значимых бит S_n с учетом содержимого вспомогательного массива памяти LSP. Карта значимости SM_n подвергается кодированию Хаффмана с получением сжатой карты значимости Далее знаки значимых бит, сжатую карту значимости подают на формирователь выходного потока.

Кодирование уточняющих бит осуществляют с учетом обновленного массива памяти LSP с получением уточняющих бит RB_n, которые тоже подают на формирователь выходного потока. После обработки всех битовых плоскостей двумерного массива формирователь выходного потока объединяет все полученные данные и выдает выходной поток в следующем виде: MSB, SM_MSB, S_MSB, RB_MSB, SM_MSB-1, S_MSB-1, RB_MSB-1, … SM₀, S₀, RB₀. Декодирование цифрового изображения производится в обратном порядке.

Способ декодирования по сути выполняет все те же действия, что и в способе SBHP кодирования (приведенный выше), но в обратном порядке.

Способ SBHP [3] позволяет производить кодирование потока цифровой информации со скоростью 100 мегапикселей в секунду (что превышает примерно в 4 раза быстродействие JPEG2000) и сжимать изображения разрядности 11-12 бит с коэффициентами сжатия 2-20 раз с потерями и примеров 2 раза - без потерь с удовлетворительным качеством декодирования изображения.

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

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

Для решения поставленной задачи предложены способ эффективного кодирования цифрового изображения и способ эффективного декодирования цифрового изображения.

Сущность способа эффективного кодирования цифрового изображения заключается в следующем: из массива внешней памяти считывают по Z-развертке цифровое изображение, представленное в виде двумерного блока C_i,j размером N_CB=N_C × N_C, где N_C - число пикселов в строке/столбце, с получением одномерного блока, который сохраняют в регистровой памяти кодера, одновременно с этим в кодере рассчитывают номер старшей битовой плоскости MSB двумерного блока C_i,j, анализируют знаки его значимых пикселов S_k, из одномерного блока выделяют битовые плоскости BP_n где n от 0 до MSB, которые далее последовательно и независимо друг от друга обрабатывают, для каждой битовой плоскости формируют L-уровневое иерархическое бинарное квадродерево m_HQT, где L=log₄N_CB, при этом нулевой уровень формируют путем копирования в него всех битов битовой плоскости BP_n, а последующие уровни заполняют на основе предыдущих путем оценки значимости их бит согласно формуле

где

далее оценивают компактность карты значимости C_L для полученного L-уровневого иерархического бинарного квадродерева согласно формуле: и компактность карты значимости С₁ для 1 -уровневого иерархического бинарного квадродерева согласно формуле: затем выбирают минимальную компактность C_min=min(C_L, C₁, N_CB) и по ее значению посредством реверсивного кодирования формируют 2-битный флаг F_n и карту значимости SM_n исходя из следующих условий: если минимальная компактность C_min равна размеру двумерного блока N_CB, то 2-битному флагу F_n присваивается значение 11₂ и в карту значимости SM_n переносятся биты нулевого уровня иерархического бинарного квадродерева; если минимальная компактность C_min равна компактности карты значимости C₁ для 1-уровневого иерархического бинарного квадродерева, то 2-битному флагу F_n присваивается значение 10₂ и в карту значимости SM_n переносятся биты первого уровня и все значимые биты нулевого уровня иерархического бинарного квадродерева; если минимальная компактность C_min равна компактности карты значимости C_L для L-уровневого иерархического бинарного квадродерева, то 2-битному флагу F_n присваивается значение 01₂ и в карту значимости SM_n переносятся все значимые биты уровней от L-1 до 0 иерархического бинарного квадродерева; карту значимости SM_n подвергают энтропийному кодированию с получением сжатой карты значимости после обработки всех битовых плоскостей одномерного блока объединяют все полученные данные и формируют на выходе кодера поток кодированного цифрового изображения в следующем виде: номер старшей битовой плоскости MSB, сжатые карты значимости всех битовых плоскостей разделенные 2-битными флагами F_0..n..MSB, и знаки всех значимых пикселов S_k.

Сущность способа эффективного декодирования цифрового изображения заключается в следующем: на вход декодера подают размер N_CB двухмерного блока, где N_CB=N_C × N_C, N_C - число пикселов в строке/столбце, и поток кодированного цифрового изображения, представленный в виде: номер старшей битовой плоскости MSB, сжатые карты значимости всех битовых плоскостей разделенные 2-битными флагами F_0..n..MSB, и знаки всех значимых пикселов S_k, в декодере сжатые карты значимости SM_n^*, где n от 0 до MSB-1, последовательно и независимо друг от друга подвергают энтропийному декодированию с получением карты значимости SM_n, одновременно с этим выделяют 2-битный флаг F_n, соответствующий сжатой карте значимости и находят количество уровней L иерархического бинарного квадродерева исходя из условий: если F_n=11₂, то L=1; если F_n=10₂, то L=2; если F_n=01₂, то L=log₄N_CB; далее посредствам реверсивного декодирования карты значимости SM_n и с учетом количества уровней L иерархического бинарного квадродерева формируют само L-уровневое иерархическое бинарное квадродерево m_HQT, начиная с уровня L-1 путем переноса бит из карты значимости SM_n на этот уровень в соответствии с условием:

где х - текущий бит карты значимости,

нулевой уровень иерархического бинарного квадродерева m_HQT является битовой плоскостью BP_n одномерного блока, которую записывают в регистровую память, после обработки всех сжатых карт значимости где n от 0 до MSB-1, с получением всех битовых плоскостей BP_n одномерного блока, а также учитывая знаки значимых пикселов S_k формируют одномерный блок, который затем преобразуют по Z-развертке в двухмерный блок C_i,j, который представляет собой декодированное цифровое изображение и подают его на выход декодера.

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

Возможность анализа знаков значимых пикселов, выделение из одномерного массива битовых плоскостей BP_n, где n от 0 до MSB, которые далее последовательно и независимо друг от друга обрабатывают способствует снижению вычислительной сложности, увеличению быстродействия обработки данных и уменьшению объема используемой памяти.

Формирование для каждой битовой плоскости L-уровневого иерархического бинарного квадродерева, оценивание компактности карты значимости C_L и С₁, выбор минимальной компактности, формирование 2-битного флага и карты значимости позволило сохранить хорошее качество цифрового изображения при кодировании и декодировании.

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

Изобретение поясняется чертежами. На фиг. 1 приведена блок-схема способа SBHP (прототип). На фиг. 2 приведена блок-схема эффективного кодирования цифрового изображения. На фиг. 3 представлена блок-схема эффективного декодирования цифрового изображения.

Предложенный способ эффективного кодирования цифрового изображения может быть реализован следующим образом (фиг. 2): из массива внешней памяти 1 цифровое изображение, представленное в виде двумерного блока C_i,j размером N_CB=N_C × N_C, где N_C - число пикселов в строке/столбце кратное 4, подают на вход кодера 2 и там считывают при помощи преобразователя 3 по Z-развертке с получением одномерного блока. Процедура считывания по Z-развертке является классическим действием [7].

Полученный одномерный блок сохраняют в регистровой памяти 4 кодера 2 (фиг. 2). Одновременно с этим в преобразователе 3 рассчитывают номер старшей битовой плоскости MSB двумерного блока по формуле и анализируют знаки его значимых пикселов согласно формуле и полученные данные передают в формирователь 5 потока кодированного цифрового изображения.

Регистровая память 4 кодера 2 позволяет из одномерного блока выделить битовые плоскости BP_n, где n от 0 до MSB, так как регистровая память 4 представляет собой массив n-битных регистров, каждый из которых содержит n элементарных ячеек памяти триггеров (каждый триггер может хранить один бит информации). Следовательно, каждый пиксел одномерного блока записывается в свой регистр и у реверсивного кодера 6 в последующем в любой момент времени есть доступ к любому биту (битовой плоскости) пикселов.

Далее из регистровой памяти 4 кодера 2 выделенные битовые плоскости последовательно и независимо друг от друга подают в реверсивный кодер 5, в котором для каждой битовой плоскости формируют L-уровневое иерархическое бинарное квадродерево m_HQT, где L=log₄N_CB, при этом нулевой уровень формируют путем копирования в него всех битов битовой плоскости BP_n, а последующие уровни заполняют на основе предыдущих путем оценки значимости их бит согласно формуле

где

Реверсивный кодер 6 оценивает компактность карты значимости C_L для полученного L-уровневого иерархического бинарного квадродерева согласно формуле: и компактность карты значимости С₁ для 1 -уровневого иерархического бинарного квадродерева согласно формуле:

Затем реверсивный кодер 6 выбирает минимальную компактность C_min=min(C_L, C₁, N_CB) и по ее значению посредством реверсивного кодирования формирует 2-битный флаг F_n и карту значимости SM_n исходя из следующих условий: если минимальная компактность C_min равна размеру двумерного блока N_CB, то 2-битному флагу F_n присваивается значение 11₂ и в карту значимости SM_n переносятся биты нулевого уровня иерархического бинарного квадродерева; если минимальная компактность C_min равна компактности карты значимости С₁ для 1-уровневого иерархического бинарного квадродерева, то 2-битному флагу F_n присваивается значение 10₂ и в карту значимости SM_n переносятся биты первого уровня и все значимые биты нулевого уровня иерархического бинарного квадродерева; если минимальная компактность C_min равна компактности карты значимости C_L для L-уровневого иерархического бинарного квадродерева, то 2-битному флагу F_n присваивается значение 01₂ и в карту значимости SM_n переносятся все значимые биты уровней от L-1 до 0 иерархического бинарного квадродерева. Полученные биты 2-битного флага F_n передают в формирователь 5 потока кодированного цифрового изображения.

Полученные карты значимости SM_n на выходе реверсивного кодера 6 содержат небольшую избыточность (порядка 1-3%), которую устраняют с помощью энтропийного кодирования для получения максимального коэффициента сжатия, поэтому биты карты значимости SM_n подвергают энтропийному кодированию с получением сжатой карты значимости Энтропийное кодирование можно производить как в реверсивном кодере 6, так и в отдельном энтропийном кодере 7. Наиболее подходящим вариантом с точки зрения производительности является энтропийное кодирование с помощью детерминированных таблиц Хаффмана [6], которое и используется в данном способе. Однако для этих целей возможно использовать другой тип энтропийного кодирования, например адаптивное арифметическое кодирование.

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

Выше перечисленными действиями производят обработку всех битовых плоскостей BP_n, где n от 0 до MSB.

Формирователь 5 объединяет все полученные данные и формирует на выходе кодера 2 поток кодированного цифрового изображения в следующем виде: номер старшей битовой плоскости MSB, карты значимости всех битовых плоскостей разделенные 2-битными флагами F_0..n..MSB, и знаки всех значимых пикселов S_k.

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

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

Предложенный способ эффективного декодирования цифрового изображения может быть реализован следующим образом (фиг. 3): на вход декодера 1 подают размер N_CB двухмерного блока, где N_CB=N_C × N_C, N_C - число пикселов в строке/столбце, и поток кодированного цифрового изображения, представленный в виде: номер старшей битовой плоскости MSB, сжатые карты значимости всех битовых плоскостей разделенные 2-битными флагами F_0..n..MSB, и знаки всех значимых пикселов S_k. В декодере 1 посредством анализатора 2 выделяют сжатые карты значимости где n от 0 до MSB-1, и которые далее последовательно и независимо друг от друга подвергают энтропийному декодированию с получением карты значимости SM_n. Энтропийное декодирование можно производить как в отдельном энтропийном декодере 3, так и в реверсивном декодере 4. Метод энтропийного декодирования должен быть идентичным тому методу энтропийного кодирования (таблицы Хаффмана или арифметическое кодирование), который был применен в кодере.

Одновременно с этим анализатор 2 выделяет знаки значимых бит S_k, а также 2-битный флаг F_n, соответствующий сжатой карте значимости SM_n^*, и находит количество уровней L иерархического бинарного квадродерева исходя из условий: если F_n=11₂, то L=1; если F_n=10₂, то L=2; если F_n=01₂, то L=log₄N_CB.

В реверсивном декодере 4 посредствам реверсивного декодирования карты значимости SM_n и с учетом количества уровней L иерархического бинарного квадродерева формируют само L-уровневое иерархическое бинарное квадродерево m_HQT, начиная с уровня L-1 путем переноса бит из карты значимости SM_n на этот уровень. L-уровневое иерархическое бинарное квадродерево m_HQT формируется при декодировании сверху вниз по уровням на основании предыдущего уровня и бит карты значимости SM_n в соответствии с условием:

где х - текущий бит карты значимости.

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

Декодер знаков 6 после декодирования MSB битовых плоскостей получает знаки значимых пикселов S_k одномерного блока от анализатора 2 и восстанавливает знаки всех пикселов одномерного блока в массиве регистровой памяти 5 на основании значений их амплитуд (если амплитуда больше нуля, то знак переносится из S_k в соответствующий пиксел, иначе пиксел пропускается).

После обработки всех сжатых карт значимости SM_n^*, где n от 0 до MSB-1, с получением всех битовых плоскостей BP_n одномерного блока, а также учитывая знаки значимых пикселов S_k формируют одномерный блок, который затем с помощью преобразователя 7 преобразуют по координатам Z-развертки в двухмерный блок C_i,j, который представляет собой декодированное цифровое изображение, и подают его на выход декодера 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.