Как хранятся матрицы в памяти?

Question

Примечание. Возможно, это связано с компьютерной организацией, а не с программным обеспечением.

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

http://en.wikipedia.org/wiki/JPEG

Сравнивая оригинальный 8x8 пример субблок изображения на матрице «B», которая преобразуется иметь общее более низкие значения величины и гораздо больше нулей во всем. Как матрица B хранится так, что она сохраняет намного больше памяти по исходной матрице?

Оригинальная матрица явно нуждается в 8x8 (количество записей) x 8 бит/запись, так как значения могут варьироваться в случайном порядке от 0 до 255. ОК, поэтому я думаю, что довольно ясно, что для этого нам нужно 64 байта памяти. С другой стороны, матрица B, хм. Лучший случайный сценарий, о котором я могу думать, заключается в том, что значения варьируются от -26 до +5, поэтому в большинстве случаев запись (например, -26) требует 6 бит (5 бит для формирования 26, 1 бит для знака, который я предполагаю). Итак, вы можете хранить 8x8x6 бит = 48 байт.

Другая возможность, которую я вижу, заключается в том, что матрица хранится в порядке «зигзаг» слева вверху. Затем мы можем указать начальный и конечный адрес и просто хранить по диагонали до тех пор, пока мы не останемся с нулями. Скажем, это 32-битная машина; то 2 адреса (начало + конец) составят 8 байтов; для других ненулевых записей по 6 бит каждый, скажем, нам нужно пройти почти по всем верхним диагоналям, чтобы сохранить сумму из 28 элементов. Всего эта схема займет 29 байт.

Подводя итог моему вопросу: если JPEG и другие кодировщики изображений требуют экономии места, используя алгоритмы, чтобы сделать матрицу изображения менее плотной, как это дополнительное пространство реализуется на моем жестком диске?

Приветствие

Answer 1

Как говорится в «Энтропийном кодировании», используется шаблон зигзага, а также RLE, который уже уменьшит размер для многих случаев. Однако, насколько я знаю, DCT не дает разреженной матрицы как таковой. Но он обычно усиливает энтропию матрицы. Это точка, в которой сжатие становится убыточным: матрица ввода передается с DCT, затем значения квантуются, а затем используется кодировка huffman.

Answer 2

нуждается в ДКПЕ должен сопровождаться другими схемами сжатия, которые используют нули/частую частоту. Простым примером является кодирование длины пробега.

JPEG использует вариант кодирования Хаффмана.

Answer 3

Самое простое сжатие будет использовать повторяющиеся последовательности символов (нули). Матрица памяти может выглядеть следующим образом (предположим, в системе разл)

0000000000000100000000000210000000000004301000300000000004 

После сжатия может выглядеть следующим образом

(0,13)1(0,11)21(0,12)43010003(0,11)4 
(Symbol,Count)... 

Answer 4

, как мой под стендом, JPEG только на сжатие, но и падение данных. После передачи блока 8x8 в частый домен он отбрасывает значимые (высокочастотные) данные, что означает, что он должен сохранять только важные данные размером 6x6 или даже 4x4. То, что он может иметь более высокую скорость сжатия, а затем не потерянный метод (например, gif)