СПОСОБ СЖАТИЯ ИЗОБРАЖЕНИЙ Российский патент 2016 года по МПК G06T9/00 H03M7/30 H04N19/25 

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

Из существующего уровня техники известен способ сжатия изображений JPEG2000 на базе пирамидального вейвлет-преобразования с последующим квантованием коэффициентов. Обработка вейвлет-коэффициентов осуществляется методом контекстно-зависимого бит-ориентированного арифметического кодирования. На этапе квантования возникают основные информационные потери, и именно за счет квантования возможно существенное уменьшение объема представления изображения. JPEG2000 позволяет обрабатывать цветные, полутоновые и двоичные изображения глубиной до 38 бит на точку с высоким качеством восстановления. Позволяет сжимать области интереса с более высоким качеством. JPEG2000 предусматривает возможность обработки без распаковки всего изображения. (Гонсалес Р., Вудс Р. Цифровая обработка сигналов: Москва, 2005, с. 727). Основным недостатком JPEG2000 является значительная ресурсоемкость, так как требуется хранение всех волновых пакетов, число которых при большом размере изображения достигает 10 для каждой цветовой компоненты. При сильном сжатии появляется блочность и большие волны в вертикальном и горизонтальном направлениях.

Известен способ сжатия с потерями (патент РФ №2500067, дата приоритета 01.03.2012, МПК H03M 7/30, G06T 9/00, опубликовано 27.11.2013), основанный на исключении некоторой части информации из пространственной области путем численного решения дифференциальных уравнений Пуассона или Лапласа с последующей оценкой различий между полученным решением и фактическими значениями в дискретных точках изображения; формировании массива граничных условий, содержащего значительное число равных элементов, который сжимают. При этом для восстановления изображения решают дифференциальные уравнения в частных производных Пуассона или Лапласа, используя массив граничных условий. Далее применяется стандартный способ компрессии.

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

Известен способ сжатия с потерями JPEG на базе дискретно-косинусного преобразования, который является наиболее близким по совокупности существенных признаков к заявляемому способу и принят в качестве прототипа (Гонсалес Р., Вудс Р. Цифровая обработка сигналов: Москва, 2005, с. 718). В этом способе распространенный формат JPEG использует для сжатия дискретно-косинусное преобразование с последующим модифицированным преобразованием Хаффмана. Основой JPEG-сжатия является получение пространственного спектра изображения с последующим исключением некоторой части спектральных компонентов, позволяющее впоследствии восстановить изображение в достаточном качестве. Недостатком JPEG-сжатия является потеря целостности изображения, возникающая в результате специфических артефактов «блочности» (контрастное выделение областей 8×8 или 16×16) в восстановленном изображении. К следующему недостатку можно отнести эффект Гиббса - ореолы по границам резких переходов цветов, что проявляется в «размытии» границ между различными объектами изображения и является следствием фильтрации (удаления при сжатии) высокочастотных составляющих. Артефакт «размытия» допустим в фотографических изображениях, но в некоторых видах изображения, например космических снимках, изображениях для печати, где необходимо сохранить контраст, «размытие» недопустимо. При сжатии без потерь в формате JPEG возможно сохранение контрастности границ объектов, при этом размер сжатого изображения остается достаточно большим, что тоже является недостатком. JPEG формат не обеспечивает эффективное сжатие изображений, содержащих большие пространства одного цвета или плавного градиента.

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

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

Указанная задача решается за счет разделения на цветовые компоненты, каждая из которых является цифровым полутоновым изображением, представленным g-разрядными двоичными числами, разделении цифрового полутонового изображения на РДИ; выделении окрестности для каждого элемента изображения; предсказании состояния элементов разрядных двоичных изображений на основе матрицы вероятностей перехода (МВП), связывающей состояния элементов окрестности предсказываемого элемента и его возможные состояния.

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

Предлагаемый способ отличается от способа JPEG тем, что изображение разделяется на РДИ, процедура предсказания для каждого из них выполняется поэлементно, что позволяет сохранить структуру изображения при восстановлении. Предлагаемый способ позволяет при сохранении малого числа элементов восстановить детали изображения за счет процедуры предсказания. Степень сжатия и точность восстановления изображения зависит от выбора процедуры для каждого РДИ и от точности выделения областей в процедуре 2. Таким образом, в отличие от JPEG-преобразования для сжатия и восстановления изображения не требуется переход в спектральную область, сочетание процедур 1 и 2 дает возможность реализовать статистическую избыточность изображения, что позволяет в некоторых случаях производить более эффективное сжатие по сравнению с JPEG.

Цифровое полутоновое изображение рассматривается как двумерный марковский процесс с несколькими состояниями N с вектором вероятностей начальных состояний P=║p₁, p₂, …, p_N║^T и МВП ¹П и ²П из состояния M_i в соседнее состояние M_j (i,j∈N) по горизонтали и вертикали соответственно

Представим g-разрядное ЦПИ набором g разрядных двоичных изображений (РДИ) (фиг. 1). Каждое РДИ представляет собой двумерный марковский процесс с двумя (N=2) равновероятными состояниями (р₁=р₂) и МВП ¹П и ²П из M_i в соседнее состояние M_j (i,j∈N) по горизонтали и вертикали соответственно

РДИ представляет марковское случайное поле размером тхп на несимметричной полуплоскости, полученной классической разверткой с левого верхнего угла слева направо вниз (фиг. 2). Состояние элемента M_i,j (i,j∈n) зависит только от известных элементов некоторого подмножества ∧_i,j, называемого окрестностью элемента M_i,j. Лучшим образом удовлетворяющее условию каузальности является конфигурация окрестности (фиг. 3), где приняты обозначения v ₁=M_i,j-1; v ₂=M_{i-1, j}; v ₃=M_{i-1, j-1}; v ₄=M_i,j

Вероятности перехода от состояний элементов окрестности ∧_i,j к состоянию M_i,j образуют МВП вида

Элементы матрицы П (4) связаны с элементами МВП (2) следующими соотношениями

где $${}^3{\pi }_{ii}$$ - элементы дополнительной МВП ³П=¹ПײП′.

МВП (4) позволяет определить вероятности перехода к N=2 состояниям элемента v ₃ исходя из состояний элементов окрестности ∧_i,j. Это позволяет прогнозировать состояние каждого элемента области F₄ изображения (фиг. 2). Для элементов областей F₂ и F₃ окрестность составляет один предыдущий элемент, поэтому для их прогнозирования достаточно МВП (2) соответственно. Первый элемент изображения (область F₁) не имеет окрестности и предсказать его состояние невозможно, поэтому он является первым непредсказанным элементом.

Сущность метода сжатия заключается в предсказании элементов изображения на основе МВП (3). В «сжатом» изображении хранятся только неправильно предсказанные элементы, а при восстановлении они служат опорными для предсказания верно предсказанных при сжатии.

Способ осуществляется следующим образом.

Для цветных изображений преобразование можно производить в любом заранее выбранном цветовом пространстве, например RGB или YCrCb. Преобразование производится отдельно для каждого канала цветовой палитры. В цветовой палитре YCrCb для большинства изображений можно добиться более высокой степени сжатия, чем в палитре RGB.

Элементы каждой цветовой компоненты, представленные в двоичном коде, преобразуются в код Грея, далее компонента разбивается на РДИ. Для каждого РДИ вычисляются статистические характеристики - элементы матрицы вероятностей перехода по горизонтали и вертикали. Для этого предлагается использовать следующий алгоритм:

- определяется средняя длина последовательностей одного значения элементов по горизонтали χ_гор и вертикали χ_верт РДИ;

- определяется значение вероятности перехода $${}^3{\pi }_{ii}=1-1/{\chi }_{гор}$$ по горизонтали и $${}^2{\pi }_{ii}=1-1/{\chi }_{верт}$$ .

Выставляется порог Н-0,6, значение порога получено эмпирически может изменяться, что позволяет увеличить/уменьшить коэффициент сжатия.

Если для РДИ значения $${}^1{\pi }_{ii}>H$$ и $${}^2{\pi }_{ii}>H$$ , к нему применяется процедура 1. Если для РДИ значения $${}^1{\pi }_{ii}\le H$$ и $${}^2{\pi }_{ii}\le H$$ , к нему применяется процедура 2.

Процедура 1 в формальном виде.

1) Исходя из МВП ¹П и ²П вычисляется МВП (4).

2) Определяются значения элементов окрестности ∧_i,j двумя битами - значение предыдущего элемента по горизонтали и вертикали соответственно. Если ∧_i,j - 00 для прогнозирования элемента $${\hat{M}}_{ij}$$ используются элементы π₁₁₁ и π₁₁₂ МВП (4); 01 - π₁₂₁ и π₁₂₂; 10 - π₂₁₁ и π₂₁₂; 11 - π₂₂₁ и π₂₂₂.

3) Если истинный элемент РДИ совпадает с предсказанным $$M_{ij}={\hat{M}}_{ij}$$ , то элемент отбрасывается.

4) Если $$M_{ij}\ne {\hat{M}}_{ij}$$ , блок M_ij полежит хранению и становится опорным для предсказания следующего.

5) Последовательность опорных элементов кодируется.

Процедура 2 в формальном виде.

1)Для РДИ создается двоичная маска с областями, содержащими элементы изображения и фон, для этого накладывается «окно» размером k×k.

Если все биты «окна» имеют одно значение, т.е. M_i,j=M_i,j+1=M_i+1,j=M_i+1,j+1=…=M_i,j+k-1=M_i+k-1,j=M_i+k-1,j+k-1,

соответствующим элементам маски присваивается значение 1 (единичная область), в противном случае 0 (нулевая область). Окно поэлементно сдвигается по всему РДИ.

2) Для маски РДИ применяется процедура 1.

3) Последовательность маски РДИ подвергается кодированию.

4) Для областей РДИ, соответствующих единичным областям маски, вычисляется МВП (4).

5) Для единичных областей применяется процедура 1.

6) Последовательность опорных элементов кодируется.

Процедура восстановления заключается в выполнении следующих действий:

1) декодирование битового потока;

2) предсказания элементов (п. 2 Процедура 1);

3)для процедуры 2 заполнение нулевых областей выборками белого гауссовского шума:

- для каждого элемента нулевой области генерируется случайное число ξ с помощью генератора случайных чисел с нормальным распределением с нулевым средним и дисперсией 1;

- если ξ<=0, элемент принимает значение M_ij=0;

- если ξ>0, элемент принимает значение M_ij=1.

Для кодирования можно эффективно применять алгоритмы на основе стандартных преобразований Хаффмана, LZ78, арифметического кодирования.

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

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

Изобретение относится к области обработки цифровых изображений. Технический результат - обеспечение увеличения быстродействия и эффективности сжатия изображений, устранение потери целостности изображения и сохранение контрастности границ между различными объектами изображения. Способ сжатия цифрового цветного изображения заключается в: разделении на цветовые компоненты, каждая из которых является цифровым полутоновым изображением, представленным g-разрядными двоичными числами; разделении цифрового полутонового изображения на разрядные двоичные изображения; выделении окрестности для каждого элемента изображения; применении для старших разрядных двоичных изображений, содержащих крупные элементы изображения, процедуры 1 предсказания элементов на основе коэффициентов корреляции по горизонтали и вертикали и теории условных марковских процессов и удалении правильно предсказанных; применении для младших разрядных двоичных изображений, содержащих мелкие детали изображения и фон, схожий по своей структуре с белым гауссовским шумом процедуры 2, предусматривающей выделение областей, содержащих детали изображения, и применении к ним процедуры 1; удалении областей, содержащих фон; кодировании битового потока. 1 з.п. ф-лы, 5 ил.

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

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