03.11.2017 admin

4.2 Формат JPEG


Эта аббревиатура расшифровывается как Join Photographic Experts Group (объединенная группа экспертов-фотографов) – организация, которая создала этот формат. Степень сжатия задается условным числом q, которое изменяется от 1 до 100 (или от 1 до 10). Основным этапом работы алгоритма является нахождение матрицы дискретного косинусного преобразования Фурье (ДКП)

Dij=(1/n)1/2, если j=0, Dij=(2/n)1/2cos((2i+1)jπ/(2n)), если j>0


В итоге на не цветной картинке, изображающей портрет ортогональной матрицы ДКП мы видим волну, это вполне привычный нам косинус, взятый вниз и вправо. Цветной портрет матрицы тоже информативен, он показывает одинаковые элементы, их учет в алгоритмах вычисления спектра ведет к так называемому быстрому преобразованию Фурье (БПФ).



Рисунок 1. Матрица дискретного косинусного преобразования


Первый столбец этой матрицы имеет, как видно, самую низкую "частоту" (нулевую), следующие столбцы содержат чаще осциллирующие последовательности, управляемые множителем jπ/(2n).

Например, нужно сжать следующий фрагмент изображения со значениями элементов от 0 до 255

P=
 95 
  88 
  88 
  87 
  95 
  88 
  95 
  95 
 143 
 144 
 151 
 151 
 153 
 170 
 183 
 181 
 153 
 151 
 162 
 166 
 162 
 151 
 126 
 117 
 143 
 144 
 133 
 130 
 143 
 153 
 159 
 175 
 123 
 112 
 116 
 130 
 143 
 147 
 162 
 189 
 133 
 151 
 162 
 166 
 170 
 188 
 166 
 128 
 160 
 168 
 166 
 159 
 135 
 101 
  93 
  98 
 154 
 155 
 153 
 144 
 126 
 106 
 118 
 133 


Рисунок 2. Матрица изображения до центрирования


Для начала эти элементы центруются, вычитанием 128. Затем происходит переход к спектральной матрице S=D'(P–128*O)D, O – матрица единичных элементов, см. рис. 3



Рисунок 3. Изображение P и двухмерный спектр изображения S=D'(P–128*O)D

S=
 92.25 
  2.3946 
  –7.8856 
  –7.4139 
  3.7504 
  –1.2731 
  0.5609 
  1.4337 
  –38.7254 
  –57.2544 
  11.4181 
  17.4934 
  –2.4737 
  2.1859 
  4.0216 
  2.31 
  –85.2144 
  63.5258 
  –0.3419 
  –16.9772 
  2.5046 
  4.6248 
  –5.5371 
  4.9267 
  –51.8996 
  –36.9947 
  –9.6905 
  13.089 
  –9.2524 
  3.0976 
  –1.7001 
  0.2885 
  –85.7501 
  –41.2717 
  50.1194 
  –8.2787 
  18.2506 
  –6.6955 
  –1.8177 
  4.5015 
  –63.2377 
  66.1383 
  –13.0008 
  –0.5269 
  2.3776 
  –7.536 
  –2.3394 
  0.6346 
  –16.9282 
  14.6428 
  –36.536 
  17.6617 
  –11.5911 
  3.2022 
  2.8403 
  –1.0386 
  –52.8234 
  30.6848 
  –7.2563 
  –9.8128 
  23.3477 
  –0.9328 
  1.4353 
  2.7026 


Элементы, отвечающие за сохраняемые низкочастотные составляющие, сосредотачиваются в верхнем левом углу этой матрицы.


Теперь пора применить фильтр низкой частоты (ФНЧ), использовав в качестве матрицы пропусных коэффициентов гиперболическую зависимость

Fij=1/(1+(1+i+j)*q),


где q – коэффициент подавления, рассматриваемый в диапазоне от 0 до 100. Числитель этой зависимости называется матрицей квантования Q.



Рисунок 4. Матрица фильтра F матрицы квантования Q




Рисунок 5. Частотная характеристика фильтра нижних частот (ФНЧ)




В результате фильтрации спектра S=F.*S=S./Q (поточечные умножение и деление) получим много нулевых элементов на канве (после округления).



Рисунок 5. Спектр изображения до и после фильтрации



Для подсчета последовательностей нулей развернем отфильтрованную матрицу спектра в последовательности змейкой: номерами показана последовательность Z перебора элементов.

Z=
1
2
6
7
 15 
 16 
 28 
 29 
3
5
8
 14 
 17 
 27 
 30 
 43 
4
9
 13 
 18 
 26 
 31 
 42 
 44 
 10 
 12 
 19 
 25 
 32 
 41 
 45 
 54 
 11 
 20 
 24 
 33 
 40 
 46 
 53 
 55 
 21 
 23 
 34 
 39 
 47 
 52 
 56 
 61 
 22 
 35 
 38 
 48 
 51 
 57 
 60 
 62 
 36 
 37 
 49 
 50 
 58 
 59 
 63 
 64 


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


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

Восстановим изображение обратными операциями P=D*S.*Q*D'+128*O и отметим, что при коэффициенте фильтрации (регулятора степени сжатия) q=2 амплитуда искажения восстановленного изображения достигает 10, при q=2 это значение удваивается, но в дальнейшем растет не столь быстро. .

ВИКИУЧЕБНИК | ДЕМО | ПРИМЕР | АЛГОРИТМ ХАФФМАНА НА JAVASCRIPT

Hide

Rambler's Top100