компактное представление и выдача точечных данных

Question

У меня есть массив данных точек, значения точек представлены как координата x и координата y.

Эти точки могут находиться в диапазоне от 500 до 2000 и более.

Данные представляют собой траекторию движения, которая может варьироваться от простой до очень сложной, а также может содержать в себе острие.

Могу ли я представить эти данные одним сплайном, набором сплайнов или другим форматом с очень жестким сжатием.

Я пытался представить их как коллекцию Безье, но в лучшем случае я получаю экономию в 40%. Например, если у меня есть массив из 500 точек, это дает мне значения 500 x и 500 y, поэтому у меня есть 1000 частей данных. Я около 100 квадратичных Безье из этого. Каждый Безье представлен как controlx, controly, anchorx, anchory. что дает мне 100 х 4 = 400 шт данных. Таким образом, вход = 1000 шт., Выход = 400 шт.

Я хотел бы еще больше, какие-нибудь предложения?

Answer 1

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

Вы также можете добиться сжатия без потерь, используя какую-то схему кодирования. Я просто придумываю это, набирая текст, используя пример диапазона в предыдущем ответе (1000 для x и 400 для y),

1. Каждой точке нужно только 19 бит (10 для x, 9 для y). Вы можете использовать 3 байта для представления координаты.
2. Используйте 2 байта для представления смещения до +/- 63.
3. Используйте 1 байт для представления короткого смещения до +/- 7 для x, +/- 3 для y.

Чтобы правильно декодировать последовательность, вам понадобится некоторый префикс для определения типа кодирования. Допустим, мы используем 110 для полной точки, 10 для смещения и 0 для короткого смещения.

Битовая разметка будет выглядеть так:

Coordinates:        110xxxxxxxxxxxyyyyyyyyyy
Dislacement:        10xxxxxxxyyyyyyy
Short Displacement: 0xxxxyyy

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

Давайте посмотрим, как это работает, на коротком примере.

3 балла: A (500, 400), B (550, 380), C (545, 381)

Допустим, вы использовали 2 байта для каждой координаты. Кодирование без сжатия займет 16 байт.

Для кодирования последовательности с использованием схемы сжатия,

A - первая точка, поэтому будет использоваться полная координата. 3 байта. Смещение B от A равно (50, -20) и может быть закодировано как смещение. 2 байта. Смещение C от B равно (-5, 1) и соответствует диапазону короткого смещения 1 байт.

Таким образом, вы экономите 10 байтов из 16 байтов. Реальная степень сжатия полностью зависит от структуры данных. Лучше всего работает на точках, образующих движущийся путь. Если очки случайные, экономия может достигать только 25%.

Answer 2

Во-первых, , сохраняйте только те десятичные точки в ваших данных, которые вам действительно нужны. Удаление их уменьшит вашу точность, но это расчетная потеря. Чтобы сделать это, попробуйте преобразовать свой номер в строку, определить местоположение точки и вырезать эти многочисленные символы с конца. Это может обработать быстрее, чем математика, ИМО. Наконец, вы можете преобразовать его обратно в число.

 150.234636746  ->  "150.234636746"  ->  "150.23"  ->  150.23

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

 A    A    A             A    R   R
 150, 200, 250     ->    150, 50, 50

Answer 3

Вы можете провести частотный анализ чисел, которые вы пытаетесь кодировать, и использовать различные битовые длины для их представления, конечно, здесь я смутно описываю кодирование Хаффмана

Answer 4

Если, например, вы используете 32-разрядные целые числа для координат точек и существует предел диапазона,
, например, x: 0..1000, y: 0..400, вы можете упаковать (x, y) в один 32-битная переменная.

Таким образом, вы получаете еще 50% сжатия.