Методы матричного сжатия

Question

В приложении, над которым я работал, я должен отправить матрицу 256 x 256 через сокет. Я разрабатываю клиент визуализации для симулятора оффшорной системы, работающего в кластере, и эта матрица представляет собой карту высот, отображающую текущее состояние поверхности океана.

Это приложение в реальном времени, поэтому скорость необходима. И, используя матрицу с плавающей запятой 256 x 256, я должен отправлять 256 кбайт данных каждую секунду для требования полосы пропускания 256 кбайт / с.

Это много, по крайней мере, для моего приложения.

Итак, мой вопрос: есть ли какой-нибудь хороший способ сжатия этой матрицы перед ее отправкой через сокет? И, если есть такой метод, сколько я могу ожидать уменьшения ОС?

Поскольку моя матрица представляет собой непрерывную поверхность, методы сжатия с потерями для меня не проблема. В основном меня интересует степень сжатия, время, необходимое для сжатия, и, наконец, если уже есть реализация этого метода для C ++.

Answer 1

Если вы находитесь достаточно далеко от берега и / или в спокойных морских штатах, то, как правило, ломающиеся волны вряд ли станут большой проблемой. Если это так, то поверхность будет очень непрерывной и, вероятно, будет очень похожа на суперпозицию множества синусоидальных / косинусных волн в X и Y.

2-D БПФ поверхности могут дать вам некоторое представление. Возможно, вы сможете представить поверхность в виде двумерного БПФ с ограниченной полосой пропускания и отбросить данные для более высоких пространственных частот.

Answer 2

Сначала: Числовое представление

Поскольку я предполагаю, что физический диапазон максимума океана ограничен (скажем, от -50,0 до 50 метров волн), если я правильно понимаю ваше описание, типичное IEEE 754-2008 32-разрядная с плавающей запятой (т. Е. float в C / C ++) использует 8-разрядную для своей степени (диапазон от -126 до 127) и 23-разрядную для дробной и однойнемного за знак.Обратите внимание, что это основание 2.

Если ваша минимальная измеренная (или вычисленная) дисперсия составляет 1 мм, 0,001 метра, то вы можете уменьшить размер плавающей запятой до как минимум 16 бит.IEEE 754 определяет 16-битное значение с плавающей запятой для использования в качестве формата обмена.Который составляет 5 битов для показателя степени, 10 битов для дроби и 1 бит для знака.Я считаю, что это подойдет, и сразу же уменьшите ваши требования до 128 КБ / с (1024 Кбит / с).

После того, как я изначально написал это, я понял, что если вам нужно единообразное представление, с очень небольшим количеством ошибок впредставление (<= 2 мм), затем преобразуется в 16-разрядное целое число со знаком, что <code>unit представляет 2 мм физической высоты.Так что у вас будет единообразное представление с разрешением 2 мм, от значений в диапазоне от -32768 (== -65536 мм или приблизительно -65 метров до -200 футов) до 32767 (== 65534 мм или приблизительно 65,5 метров).

Это очень простое альтернативное представление, основанное на простом предположении, что a) допустимый диапазон значений составляет +/- 65,5 метра, и что разрешение 2 мм приемлемо для передачи.

Секунда: Изменение (фильтрация) данных

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

Третий: Традиционное сжатие без потерь

В противном случае достаточно быстрые методы сжатия без потерь, такие как методы на основе Лемпеля-Зива (LZ, LZH, LZW и т. Д.) И, возможно, быстрый метод LZO .

Answer 3

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

Answer 4

Сначала посмотрите на свои данные.Сколько битов информации в этих поплавках вам действительно нужно отправить?Поиграйте с обрезкой наименее значимых битов и посмотрите, достаточно ли это точно.Далее начнем с основных алгоритмов без потерь.Сжатие с помощью LZ, без потерь (LZ78, LZW, ...). Получите базовый коэффициент без потерь с быстрой скоростью распаковки.Затем попробуйте BZip и т.п. для возможно лучшего метода сжатия и более медленной распаковки.Теперь у вас есть предел без потерь.Теперь попробуйте некоторые алгоритмы с потерями.JPEG и им подобные имеют настраиваемые коэффициенты потерь и по-прежнему быстро распаковываются.Наконец, добавьте несколько фильтров.Ваши данные, вероятно, будут очень хорошо сжаты с помощью простого дифференциального прохода по оси X или Y (или попробуйте оба и сохраните результат как 1 бит). Это должно сделать ваши данные еще более сжимаемыми.Я думаю, вы могли бы получить по крайней мере х3 вашей текущей пропускной способности без потерь и х10 с небольшой потерей.

Answer 5

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

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

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

Как только вы это сделаете, вы можете рассмотреть возможность использования сжатия Хаффмана или даже арифметического сжатия, но любое из них замедлит ваше сжатие на значительное количество.

Answer 6

Ну, матрица - это просто 2D-сигнал.Так что есть много разных методов сжатия.Сначала я бы попробовал простое решение: пойти на раздувание / раздувание без контейнера (в основном Zip, без Zip).http://en.wikipedia.org/wiki/DEFLATE Уровень сжатия будет зависеть от данных, поэтому я не могу сказать, вы должны попробовать это сами.

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

Answer 7

Ну, во-первых, сколько уровней роста вам нужно?Какая максимальная разница в высоте от пика волны до впадины?Могу поспорить, что вы можете представить его только с 256 или 65536 возможными значениями высоты, которые сразу же сокращают ваши данные до 1/2 или 1/4 без необходимости изменять структуру данных.Вы также можете отправлять минимальные / максимальные значения как поплавки и каждое обновление, поэтому 256 уровней всегда используются полностью, чтобы получить максимально возможную точность ... по мере того как море становится более грубым, вы теряете точность.сохранить изображение 256x256, используя стандартные алгоритмы изображения.У вас не совсем есть растровое изображение стандартного формата, которое можно рассматривать как градации серого. Если каждая вершина V масштабируется до значения 0-255, вы можете создать цвет (V, V, V) и бесплатно использовать библиотеку JPGэто уже существует.Или вы, вероятно, можете найти формат файла DDS, который также имеет один канал 8/16/32-битных данных.

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

Answer 8

Я бы попробовал следующее:

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

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