Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11695
Последний выпуск: 19.06.2015

JPG


Алгоритм JPEG

В алгоритме JPEG исходное изображение представляется двумерной матрицей размера N*N, элементами которой являются цвет или яркость пиксела. Упаковка значений матрицы выполняется за три этапа.

Высокая эффективность сжатия, которую дает этот алгоритм, основана на том факте, что в матрице частотных коэффициентов, образующейся из исходной матрицы после дискретного косинусного преобразования, низкочастотные компоненты расположены ближе к левому верхнему углу, а высокочастотные - внизу справа. Это важно потому, что большинство графических образов на экране компьютера состоит из низкочастотной информации, так что высокочастотные компоненты матрицы можно безболезненно выбросить.“Выбрасывание” выполняется путем округления частотных коэффициентов. После округления отличные от нуля значения низкочастотных компонент остаются, главным образом, в левом верхнем углу матрицы. Округленная матрица значений кодируется с учетом повторов нулей. В результате графический образ сжимается более чем на 90% , теряя очень немного в качестве изображения только на этапе округления.


Дискретное косинус преобразование

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

        DCT   = 1/sqr(N), если i=0
           ij
        DCT   = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i > 0
           ij
        N = 8,  0 

в результате имеем:

      |.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|

Этап Квантования

На этом этапе мы посчитаем матрицу квантования, используя этот псевдо код:

	for i:=0 to 8 do
	 for j:=0 to 8 do
	  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

Этап Вторичного Сжатия.

Самым распространенным методом вторичного сжатия является метод Хаффмана и его разновидности.

Метод Хаффмана.

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

  1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;
  2. Последовательно объединяем два символа с наименьшими вероятностями появления в новый составной символ, вероятность появления которого полагается равной сумме вероятностей составляющих его символов. В конце концов, мы построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него;
  3. Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (например, направо - 1, налево - 0).

Поясним создание дерева с использованием иллюстраций :

A	B	C	D	E
10	5	8	13	10

B	C	A	E	D
5	8	10	10	13

A	E	BC	D
10	10	13	13

BC	D	AE
13	13	20

AE	BCD
20	26

AEBCD
46

Таким образом, построено дерево

Бинарное дерево

Теперь, если в тексте встречается, например, символ "d", то вместо того, чтобы выделять этому символу байт, после сжатия символ займет всего 2 бита (01).

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
34K
04 ноября 2007 года
Voltt
0 / / 04.11.2007
Мне нравитсяМне не нравится
22 сентября 2013, 14:51:24
Ссылка на скачивание, кому это нужно (люди до сих пор пишут письма, это приятно), ссылка должна работать столь же вечно, сколь вечен Яндекс.Диск: http://yadi.sk/d/b_QGT7W79gJLe
2.
34K
04 ноября 2007 года
Voltt
0 / / 04.11.2007
Мне нравитсяМне не нравится
11 мая 2011, 10:58:31
Т.к. моя поделка вызывает интерес, выкладываю в общий доступ.
В ней есть приведённый алгоритм, кроме сжатия. Т.к. в 2006 году он почил вместе с первой реализацией алгоритма. В 2008 я переписал программу, планируя вместо 7 bit RLE что-нибудь поинтереснее. Но ничего так и не реализовал.

исходники (Delphi 7)
narod.ru@disk/12530062001/JPEG%20algorithm.rar.html
(вместо @ поставьте /)
3.
34K
04 ноября 2007 года
Voltt
0 / / 04.11.2007
Мне нравитсяМне не нравится
7 октября 2008, 22:03:42
Прошу прощения у всех, кому не прислал своевременно реализацию алгоритма, он был утерян. Сейчас рабочая программа существует и может быть выслана (пишите на Volontyor@mail.ru, исходники Delphi)
Хочу особо подчеркнуть, что это не JPEG в каноническом виде, а только алгоритм - как это работает.
4.
Аноним
Мне нравитсяМне не нравится
13 мая 2006, 17:59:40
Только согласно некому Д.Мастрюкову (к главе чьей книги прилагается Сишный сорец) формула расчёта DCT записывается НЕ:

sqr(2/N)*cos[(2j+1)*i*3.14/2N]

, а:

sqr(2/N)*cos[(2j+1)*i*3.14/(2N)]

(2.0*N - действие ВЫШЕ)

вот теперь поясните кто-нибудь пожалуйста - чему верить!?


Кстати, как раз по формуле sqr(2/N)*cos[(2j+1)*i*3.14/(2N)] ДКП матрица получается точь в точь как в статье (ну там местами отклонения в сотых-тысячных на единицу-две), если же использовать формулу со статьи, то выходит ну совсем ИНАЧЕ!

Остальные расчёты в статье комментировать не стану, ХОТЯ МНОГО ПОРАЗИЛО и самое ужасно - пол руНета откопировало данную статью (кстати,естьв ерсии и пополнее), с ТАКИМИ ГРУБЫМИ ОШИБКАМИ (благодарю Voltt, что указал на них)...
5.
Аноним
Мне нравитсяМне не нравится
30 марта 2006, 19:00:08
Вообще, текст содержит довольно много ошибок:

1) IMG = ...
IMG = ...
Не сказано, что нижняя матрица IMG та же, что и верхнаяя, из каждого элемента которой вычли 128, вообще это важно.

2) Неверно записаны формулы ДКП, вот истинная
RES = DCT * IMG * DCT_транспонированная.
Можно разбить на 2 этапа:
TMP = IMG * DCT_траспонированная
RES = DCT * TMP

3) Грубые вычисления. Если считать все данные в типе double, и на конечном этапе преобразовать их в int, во многих местах получится сильное несоответствие с приведёнными данными

4) "теперь нужно каждое число в матрице квантования разделить на число в соответствущей позиции в матрице RES" - нужно сделать наоборот, каждое число в матрице RES разделить на соответствующее число в матрице Q. В приведённой матрице A для некоторых чисел не написан знак "-", т.е. они не положительные а отрицательные на самом деле.

5) "итак у нас получилась последовательность:
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"
Не сказано, как она появилась. Вот как: числа из матрица A выписывались в соответсвии с числами матрицы Q по их возрастанию. Т.е. число 30 соответствует числу 3 в матрице Q, 0 (строка 1, столбец 2) соответствует числу 5, -7 (строка 2, столбец 1) соответсвтует также числу 5, 8 (сртрока 2, столбец 2) соответсвует числу 7, и т.д. Такая выписка позволяет группировать большее число подряд идущих нулей, а значит обеспечить лучшее сжатие.

6) Метод a) 7bit RLE не совсем понятно описан.
Постараюсь объяснить более доступным языком:
есть последлвательность:
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

Имеем подряд идущие разные числа: 30 0 -7 -11 8
им будет соответствовать RLE последовательность
133 30 0 -7 -11 8
133 - значимый байт = 128 + 5
128 - (старший бит = 1) указывает на то, что записывается последлватльность РАЗНЫХ чисел, 5 указывает их колчичество. Т.о. последовательно может быть записано не более 127 разных чисел, мы имеем матрицу 8x8, а значит даже в случае отсутствия в матрице 0, кодировка RLE прибавит всего 1 байт к данным
Итог: 6 байт
0 0
запишетв в RLE последовательность 2 0
2 - значимый байт = 0 + 2
0 - (старший бит = 0) указывает на то, что записывается последовательность ОДИНАКОВЫХ чисел, второй байт говорит, какое это число, в нашем случае 0.
И т.д.

Если нужен исходник приведённого алгоритма (на Delphi), можете написать на мыло Volontyor@mail.ru
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог