|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitry Kalinin 2:5009/5.43 15 Aug 2001 15:48:10
To : Alexey Kozlov
Subject : Re: вэйвлет и косинус преобразования
--------------------------------------------------------------------------------
14 Авг 01 14:08, Alexey Kozlov -> All:
AK> хайль, all!
AK> подкинте сабжевые алгоритмы, желательно словами, а не в сорцах!
AK> Покедова ! 14 августа 2001 года
Кроме этой статьи есть пара статей html-ках, если нужну могу отправить.
Алгоритм JPEG можно разделить на несколько этапов
0. Подготовка
1. ДКП (Дискретно Косинусоидальное Преобразование)
2. Квантование
3. Вторичное сжатие
-----------------------------------------------------------------------------
Этап 0. Подготовка
-----------------------------------------------------------------------------
Hужно преобразовать изображение в вид яркость/цветность, можно использовать
цветовую схему YCbCr (YUV), вот формулы перевода:
Y = 0.299*R + 0.578*G + 0.114*B
Cb = 0.1678*R - 0.3313*G + 0.5*B
Cr = 0.5*R - 0.4187*G + 0.0813*B
Y нужно сохранить без изменений, его можно сжать любым алгоритмом без потери
данных.
Теперь я попятаюсь объяснить как сжать Cb и Cr
-----------------------------------------------------------------------------
Этап 1. ДКП
-----------------------------------------------------------------------------
Следует создать ДКП матрицу, используя эту формулу
DCT = 1/sqr(N), если i=0
ij
DCT = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i > 0
ij
N = 8, 0 < i < 7 , 0 < j < 7
в результате имеем:
|.353553 .353553 .353553 .353553 .353553 .353553 .353553 .353553|
|.490393 .415818 .277992 .097887 -.097106 -.277329 -.415375 -.490246|
|.461978 .191618 -.190882 -.461673 -.462282 -.192353 .190145 .461366|
DCT = |.414818 -.097106 -.490246 -.278653 .276667 .490710 .099448 -.414486|
|.353694 -.353131 -.354256 .352567 .354819 -.352001 -.355378 .351435|
|.277992 -.490246 .096324 .416700 -.414486 -.100228 .491013 -.274673|
|.191618 -.462282 .461366 -.189409 -.193822 .463187 -.460440 .187195|
|.097887 -.278653 .416700 -.490862 .489771 -.413593 .274008 -.092414|
например, нам нужно сжать следующий фрагмент изображения:
| 95 88 88 87 95 88 95 95|
|143 144 151 151 153 170 183 181|
|153 151 162 166 162 151 126 117|
IMG = |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|
|-33 -40 -40 -41 -33 -40 -33 -33|
| 15 16 23 23 25 42 55 53|
| 25 23 34 38 34 23 -2 -11|
IMG = | 15 16 5 2 15 25 31 47|
| -5 -16 -12 2 15 19 34 61|
| 5 23 34 38 42 60 38 0|
| 32 40 38 31 7 -27 -35 -30|
| 26 27 25 16 -2 -22 -10 5|
T
вот формула, по которой производится ДКП: RES*IMG*DCT
T
для начала нужно посчитать промежуточную матрицу: TMP = IMG*DCT
|-103 -3 1 2 4 0 -1 5|
| 89 -40 12 -2 -7 5 1 0|
| 57 31 -30 6 2 0 5 0|
TMP = | 55 -28 24 1 0 -8 0 0|
| 32 -60 18 -1 14 0 -8 1|
| 84 -11 -37 17 -24 4 0 -4|
| 19 81 -16 -20 8 -3 4 0|
| 22 40 11 -22 8 0 -3 2|
затем умножаем ее на ДКП матрицу: RES = TMP*DCT
| 91 3 -5 -6 2 0 1|
|-38 -57 9 17 -2 2 2|
|-80 58 0 -18 4 3 4|
RES = |-52 -36 -11 13 -9 3 0|
|-86 -40 44 -7 17 -6 4|
|-62 64 -13 -1 3 -8 0|
|-16 14 -35 17 -11 2 -1|
|-53 32 -9 -8 22 0 2|
______________________________________________________________________________
Этап 2. Квантование
------------------------------------------------------------------------------
Hа этом этапе мы посчитаем матрицу квантования, используя этот псевдо код:
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
Q[i][j] = 1+((1+i+j)*q);
}
где q - это коэффициент качества, от него зависит степень потери качества
сжатого изображения
для q = 2 имеем матрицу квантования:
| 3 5 7 9 11 13 15 17|
| 5 7 9 11 13 15 17 19|
| 7 9 11 13 15 17 19 21|
Q = | 9 11 13 15 17 19 21 23|
|11 13 15 17 19 21 23 25|
|13 15 17 19 21 23 25 27|
|15 17 19 21 23 25 27 29|
|17 19 21 23 25 27 29 31|
теперь нужно каждое число в матрице квантования разделить на число в
соответствущей позиции в матрице RES, в результате получим:
| 30 0 0 0 0 0 0 0|
| -7 8 1 1 0 0 0 0|
|-11 6 0 1 0 0 0 0|
A = | -5 -3 0 0 0 0 0 0|
| -7 -3 2 0 0 0 0 0|
| -4 4 0 0 0 0 0 0|
| -1 0 1 0 0 0 0 0|
| -3 1 0 0 0 0 0 0|
как вы видите здесь имеется довольно много нулей, мы получим наиболее
длинную последовательность нулей, если будем использовать следущий алгоритм:
+----+----+----+----+----+----+----+----+
| 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 |
+----+----+----+----+----+----+----+----+
итак у нас получилась последовательность:
30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0
0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
для большего сжатия можно перед первым этапом JPEG можно провести
субдискретизацию, или другими словами уменьшить частоту изображения,
идея очень проста:
к примеру у нас есть следующая последовательность (Cb или Cr)
11 42 200 123 56 32 125 234 12 24 34 78 145 134 245 101
если будем использовать субдискретизацию 4:1:1 результирующая
последовательность будет:
11 123 125 24 145 101
а если использовать 4:2:2
11 234 245
а для восстановления последовательности нужно интерполироать
------------------------------------------------------------------------------
Этап 3. Вторичное сжатин
______________________________________________________________________________
Любым доступным алгоритмом пакуются данные
Dmitry
... "Ты знаешь все, что надо знать ..." (с) 1999 Ария. Искушение
--- 0f 0f 0e 0e 0e 0e 0c 0c 0a 09 09 06 03 00 00 00 ДВБВДБДДВДДДДДБДДДДД
* Origin: bESt reGUARdS (2:5009/5.43)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: вэйвлет и косинус преобразования 