Сжатие двумерного точечного набора - идеи?

У меня есть набор двумерных точек, хранящихся в массиве. Мне нужно сжимать его, насколько я могу. Предпочтительно быстрый, но не прерыватель транзакций, цель сжатия. Правила:

  • точка = 32-битная структура, хранящаяся как (x, y), 2 байта для каждой координаты
  • координата = a "float" с 8-битной целой частью, дробная часть 8 бит

Специальные свойства:

  • Я могу изменить порядок точек, как я считаю подходящим
  • Мне даны точки в порядке целочисленных частей их x и y, возможно, я могу использовать это, но дробные части в значительной степени случайны из того, что я видел.
  • массив, который я получаю, является смежным (с точки зрения памяти).

То, что я исследовал до сих пор:

Мне удалось реализовать Huffman и BWT, но ни один из них не дает мне хорошего коэффициента сжатия (или использует основное свойство моего набора данных). Сегодня я собираюсь попробовать первый вариант.

Я уверен, что есть лучшие идеи. У вас есть? Вы столкнулись с чем-то похожим и реализовали что-то действительно хорошее?

Пример набора данных в шестнадцатеричном формате:

00 0A 00 77 00 55 00 80 00 2B 00 B9 00 7A 00 5B 
00 F6 00 76 00 B4 00 25 00 47 00 D3 00 F6 00 7D
...
01 05 00 A9 01 B8 00 10 01 4F 00 6A 01 ** 00 DF
01 1F 00 F0 01 BE 00 C3 01 6C 00 87 01 CE 00 44
...
...
15 06 03 F4 15 1E 03 29 15 35 03 10 15 B9 03 22
15 67 03 73 15 EF 03 5C 15 29 03 B8 15 4C 03 2F
...

где, например, частица 15 67 03 73 (последняя строка) означает частицу при x = 15 и 67/256, y = 3 и 73/256. Как видите, данные несколько упорядочены, но дробные части находятся в полном беспорядке.

2 ответа

Первый вариант из OP более уместен. Но это может быть улучшено далее.

  • Переинтерпретировать координаты как 16-битные целые числа.
  • Преобразовать позиции точек на расстояния по кривой Гильберта (или любую другую кривую заполнения пробела).
  • Сортировать расстояния, затем применить дельта-кодирование (вычислить различия соседних расстояний).
  • В зависимости от предпочтений сжатия/скорости (a) используйте что-то вроде кодов Elias или Golomb (самое быстрое), (b) используйте кодировку Хаффмана или (c) используйте что-то вроде арифметического кодирования (наилучшая степень сжатия).

Если в распределении точек есть некоторый шаблон, вы можете попробовать более продвинутые компрессоры для шага 4: LZ *, BWT или PPM.

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

method compressed size
------ ---------------
Uncompressed: 1000000
Elias4: 522989
Elias3: 495371
Elias2: 505376
Golomb12: 479802
Golomb13: 472238
Golomb14: 479431
Golomb15: 501422
FSE1: 455367
FSE2: 454120
FSE3: 453862

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

Все результаты были получены этим источником: http://ideone.com/ulmPzO


Перемещайте биты, представляющие координаты X и Y каждой точки, сортируйте и сжимайте.

Например, если у вас есть точка (X, Y), представленная двумя 16-разрядными номерами

(Х <суб> 15суб > X <суб> 14суб > X <суб> 13суб > X <суб> 12суб > X <суб> 11суб > Х <суб> 10суб > X <суб> 9суб > X <суб> 8суб > X <суб> 7суб > X <суб> 6суб > X <суб> 5 X 4 X 3 X 2 X 1 X 0, Y <суб> 15суб > Y <суб> 14суб > Y <суб> 13суб > Y <суб> 12суб > Y <суб> 11суб > Y <суб> 10суб > Y <суб> 9суб > Y <суб> 8суб > Y <суб> 7суб > Y <суб> 6суб > Y <суб> 5суб > Y < суб> 4суб > Y <суб> 3суб > Y <суб> 2суб > Y <суб> 1суб > Y <суб> 0суб > )

Преобразуйте его в следующий 32-разрядный номер:

X <суб> 15суб > Y <суб> 15суб > X <суб> 14суб > Y <суб> 14суб > X <суб> 13суб > Y < суб> 13суб > X <суб> 12суб > Y <суб> 12суб > X <суб> 11суб > Y <суб> 11суб > X <суб> 10суб > Y <суб> 10суб > X <суб> 9суб > Y <суб> 9суб > X <суб> 8суб > Y <суб> 8суб > X <суб> 7суб > Y <суб> 7суб > X <суб> 6суб > Y <суб> 6суб > X <суб> 5суб > Y <суб> 5суб > X <суб> 4суб > Y <суб> 4суб > X <суб> 3суб > Y <суб> 3суб > X <суб> 2суб > Y <суб> 2суб > X <суб> 1суб > Y <суб> 1суб > X <суб> 0суб > Y <суб> 0суб >

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

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

Дело в том, что тогда вы можете рассматривать его как дерево k-d, каждый бит разбивает пространство (влево/вправо или вверх/вниз). Для первых уровней вы можете сжать, а затем просто указать, сколько элементов есть на одной стороне, пока вы не дойдете до полюсов всего несколькими элементами, которые могут быть представлены, указав оставшиеся несколько бит явно. Для лучшего сжатия вам придется использовать арифметическое кодирование.

licensed under cc by-sa 3.0 with attribution.