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

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

, (22)

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

В общем случае указанный подход повышения скорости МКР применим не только для восстановления исходного сигнала по паттерну, но и для других задач, решение которых возможно с помощью МКР. Дополнительно способ тестировался на различных задачах электротехники, описываемых уравнением Лапласа и Пуассона, в пространствах с числом измерений пространства и .

Во всех случаях полученное промежуточное решение позволяло существенно сократить число итераций МКР для получения решения с заданной точностью. Особый выигрыш в сокращении числа итераций наблюдается при гладких краевых условиях, вплоть до того, что при некоторой достаточной гладкости может быть получено решение только с применением указанного способа без итерационного процесса МКР. Такие краевые условия вполне актуальны для некоторых типов изображений.

Рис. 6. Значения логарифмов суммарных невязок по всем узлам сетки в зависимости от номера итерации в двумерном пространстве . a.) - без поиска предварительного решения; b.) - с поиском предварительного решения.

Существенное ускорение сходимости, в результате оптимизации рассмотренным способом, на примере невязок в решении двумерной (плоско-параллельной) задачи электростатики, приведено на изображении (рис. 6). Для разбиения области выбиралась прямоугольная сетка, образованная линиями, параллельными координатным осям, с равным во всех направлениях шагом . В качестве многочлена (21) было использовано уравнение прямой , коэффициенты которой () рассчитывались по двум элементам краевых условий из .

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

Ещё одним дополнительным способом повышения скорости вычислений МКР является распараллеливание итерационного процесса, например, по элементам сетки. Достаточно просто такое решение реализуется на базе современных графических процессоров, например, при помощи технологии CUDA, что позволяет многократно (в сотни раз) повысить скорость вычислений [16].

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

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

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

- число исключённых элементов из паттерна;

- коэффициент сжатия:

, (23)

где: - объём сжатых (выходных) данных (бит); - объём исходных (входных) данных (бит);

- среднеквадратичную ошибку (MSE - mean square error):

, (24)

где: - значения исходного и - восстановленного сигналов;

- пиковое отношение сигнал/шум (PSNR - peak signal to noise ratio):

; (25)

- отношение сигнал/шум (SNR - signal to noise ratio):

, (26)

где: RMSE - корень среднеквадратической ошибки т.е.: .

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

Рис. 7. Стандартное тестовое изображение «4.1.05.bmp». Размер исходного файла изображения 196662 байт, размеры пикселей, глубина цвета 24 бита, размер цифрового сигнала изображения байт.

В таблице (таблица 2) приведены численные результаты экспериментов. Для всех цветовых каналов величина -критерия была выбрана одинаковая, формирование паттерна производилось в цветовом пространстве RGB. После формирования паттерна производилось сжатие длин серий, а затем кодирование Хафманна. Для результирующих данных был разработан специальный формат позволяющий сохранить в файл не только сами данные но и некоторую служебную информацию: дату, размеры изображения, используемое цветовое пространство, некоторые другие данные записанные пользователем. Служебная информация несколько увеличивает размер готового файла по сравнению размером сжатого сигнала. Длина служебных данных в файлах, создаваемых сжатием с помощью анализа дифференциальной структуры, составила 52 байта, а в исходном файле «4.1.05.bmp» 54 байта. При общем размере исходного файла «4.1.05.bmp» 196662 байт.

Для восстановления изображения применялся МКР (1000 итераций) с предварительным отысканием промежуточного решения. Время формирования паттерна в одном вычислительном потоке (ОС Windows, C++) на процессоре Core2Duo E8500 (с эффективной тактовой частотой процессора 3,16 ГГц, частота процессорной шины 1.333 ГГц, кэш-память второго уровня размером 6МБ), составило 31250 мкс, время восстановления 1343750 мкс. Расспаралеливание вычислительного потока не применялось. Расчёт коэффициента сжатия и фактора сжатия производился путём соотношения размеров конечных файлов исходного изображения «4.1.05.bmp» (196662) и файла полученного в результате сжатия с помощью анализа дифференциальной структуры.

Таблица 2. Некоторые оценки сжатия изображения «4.1.05.bmp».

84129

42,79022

0,582

1,719

2,204839

44,70

40,08303

20

107364

54,60815

0,481

2,080

5,200922

40,97

36,356

25

127779

64,99176

0,388

2,578

11,78631

37,42

32,80302

30

144492

73,49243

0,304

3,290

22,84199

34,54

29,92946

35

157290

80,00183

0,234

4,275

36,16757

32,55

27,93361

40

166086

84,47571

0,184

5,436

56,36549

30,62

26,00667

45

171954

87,46033

0,148

6,759

85,77358

28,80

24,18327

50

176058

89,54773

0,123

8,132

127,981

27,06

22,44535

55

179193

91,14227

0,104

9,618

192,4735

25,29

20,67309

60

181608

92,37061

0,089

11,239

268,6562

23,84

19,22483

65

183483

93,32428

0,077

12,991

384,8277

22,28

17,66414

70

184998

94,09485

0,068

14,710

503,2751

21,11

16,49875

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

Рис. 8. Исходное изображение (a.), далее восстановленные (b., d., e., g., h., j., k.) 1000 итераций МКР с использованием промежуточного решения. Колонка справа (c., f., i., l.) соответствует паттернам. Значения -критерия следующие: b., c. - 0; d. - 10; e., f. - 20; g. - 30; h., i. - 40; j. - 50; k., l. - 60.

Обычное значение коэффициента для изображений приемлемого качества составляет величину порядка единиц [8]. Сопоставляя результаты (таблица 2) и (рис. 8) можно заметить, что в области значений -критерия порядка наблюдается существенное, для визуального восприятия, ухудшение качества изображения, возникают области размытия вблизи границ объектов, при этом значения (для ) и (для ), что соответствует ожидаемой области ограничения приемлемого качества. Коэффициент сжатия (для ) и (для ). При дальнейшем росте величины -критерия наблюдается дальнейшее ухудшение качества, особенно проявляемое на границах графических объектов, изучение структуры паттерна показывает, что снижается и качество отображения текстуро-подобной однотонной области кирпичных стен, при сравнении паттерна (рис. 8, h.) с (рис. 8, j.) заметно, что пропадают граничные элементы, разделяющие отдельные малоконтрастные элементы изображения. При дальнейшем увеличение величины -критерия до единиц содержимое изображения, несмотря на значительные искажения, оставалось узнаваемым. Далее рассмотрим сопоставление полученных результатов с некоторыми другими, наиболее распространёнными графическими форматами (таблицы 3, 4, 5).

Таблица 3. Некоторые оценки JPEG-сжатия изображения «4.1.05.bmp».

Таблица 4. Некоторые оценки PNG-сжатия изображения «4.1.05.bmp».

Таблица 5. Некоторые оценки GIF-сжатия изображения «4.1.05.bmp».

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

Рис. 9. Изображения, полученные различными способами сжатия (таблица 6):

a.) - сжатие на основе анализа дифференциальной структуры ( таблица 2);