Лекция #35. Компрессия векторных данных [Лектор - Rageous]

Автор: Rageous

18:02:06  Rageous: лекция, которую я сегодня читаю, посвящена моим исследованиям в области компрессии векторных данных
18:02:30  Rageous: в связи с тем, что мне уже задавали вопросы, что есть векторные данные, я проясню этот вопрос отдельно
18:02:52  Rageous: здесь и далее под векторными данными я буду подразумевать функции f(t), где t - время, а f(t) - функция, возвращающая некоторое рациональное значение
18:03:16  Rageous: с подобными данными мы работаем каждый день: в играх это анимации персонажей, пути перемещения объектов, траектории движения физических тел
18:03:35  Rageous: в софте это информация по трекингу машин автопарка, к примеру
18:03:58  Rageous: здесь, к примеру, можно увидеть сохраненный путь автомобиля. сохраненные данные используются для анализа скорости, времени и количества остановок:

18:04:21  Rageous: здесь зеленоградский автопарк предоставил свои данные для анализа дорожной обстановки на одной из самых нагруженных московских трасс, чем облегчил жизнь множеству автомобилистов:

18:04:47  Rageous: итак, векторные данные полезны. часто бывает полезно их сохранять. к сожалению их объем нередко далек от "незначительного"
18:05:17  Rageous: в связи с этим возникает вопрос об их компрессии
18:05:54  Rageous: к примеру, если вы хотите сохранить реплей заезда в автосимуляторе, чтобы поделиться им с друзьями, вам придется думать о том, как переслать по интернету до десятка мегабайт данных
18:06:56  Rageous: если же вы занимаетесь ПО и хотите хранить годами информацию по имеющимся в вашем распоражении автомобилям или морским судам или самолетам или еще чему - вы можете легко столкнуться с проблемой огромного объема этих сведений
18:07:19  Rageous: к счастью существуют архиваторы :)
18:07:48  Rageous: и к сожалению сжатие векторных данных - одно из самых низких для большинства современных алгоритмов
18:08:00  Rageous: так, например, zip сжимает такие данные в 2-3 раза
18:08:17  Rageous: rar и 7zip обеспечивают сжатие до 25 раз, но делают это весьма медленно
18:09:07  Rageous: слабым местом архиваторов является то, что они предоставляют lossless (без потерь) компрессию, а так же не располагают сведениями о структуре предоставленных им данных
18:10:17  Rageous: целью, которую я ставил перед собой, когда начинал заниматься компрессией векторных данных, было сжатие в 100-1000 раз при скорости достаточной, чтобы осуществлять это сжатие в реальном времени без серьезного удара по производительности основного приложения
18:10:34  Rageous: итак, что я делал
18:11:17  Rageous: первое - все данные были разбиты на отдельные потоки вида v(t), где v - это функция времени, возвращающая одно или несколько рациональных чисел
18:12:07  Rageous: имеющиеся данные были слегка изменены, чтобы избавиться от избыточности: вместо полных матриц 4*4 трансормации я писал вектора и нормализованные (3 компоненты) кватернионы
18:12:48  Rageous: потоки, объединяющие в себе несколько флоатов для одного момента времени пригодились для записи нормализованных кватернионов - уменьшив погрешность
18:13:27  Rageous: второе - так как данные нужно было сжимать и сохранять в реальном времени, все данные были разбиты на пакеты фиксированной длины (обычно порядка 30-90 секунд)
18:14:09  Rageous: в памяти одновременно находятся два пакета: текущий и прошлый. прошлый сжимается вместе с наполнением текущего, что позволяет избежать пиковых нагрузок при сохранении пакета в файл или иное хранилище
18:14:33  Rageous: после сохранения сжатого пакета его место, соот-но, занимает текущий, а текущий начинает наполняться новыми данными
18:16:08  Rageous: третье - данные в библиотеку приходят очень часто. в играх - раз в кадр. в софте - при каждом замере. в большинстве ситуаций это означает избыточность данных, т.к. объект, который движется почти прямолинейно, создает такой же объем сведений, как и объект, который бешенно меняет свою позицию и ориентацию
18:16:19  Rageous: чтобы избавиться от этой избыточности нужно провести аппроксимацию
18:16:54  Rageous: наиболее частым и простым подходом в данной ситуации является аппроксимация кусочно-линейным сплайном
18:17:01  Rageous: или, проще говоря, ломаной
18:17:31  Rageous: фиттинг (вычисление минимального набора необходимых ключей) для такого сплайна осуществляется очень просто и быстро
18:18:03  Rageous: но результат оставляет желать лучшего как с т.з. компрессии, так и с т.з. внешнего вида полученных после обработки данных
18:18:15  Rageous: машина начинает двигаться "угловато"
18:18:49  Rageous: вторым подходом является фиттинг сплайнов более высокого порядка - квадратичных и кубических сплайнов
18:19:25  Rageous: сразу скажу, несмотря на интуитивно-большую гибкость кубических, я остановился на квадратичных
18:19:46  Rageous: это связано с тем, что фиттинг кубических сплайнов - весьма сложный процесс, который требует тонкой настройки
18:20:02  Rageous: в противном случае на сплайне появляются выбросы, которые сводят на нет все преимущества
18:20:10  Rageous: либо же компрессия становится чрезвычайно низкой
18:20:41  Rageous: неплохая статья с исходниками по кубическим сплайнам находится здесь: http://alglib.sources.ru/interpolation/spline3.php
18:21:00  Rageous: про фиттинг можно почитать здесь: http://www.stanford.edu/~boyd/cvx/examples/cvxbook/Ch06_approx_fi… /fig6_20.html и здесь: http://ask.metafilter.com/50554/Generating-Bezier-curves-from-dis… te-point-sets
18:21:22  Rageous: что же квадратичный сплайн. я взял сплайн безье: http://ru.wikipedia.org/wiki/Кривая_Безье
18:21:54  Rageous: он имеет очень простую формулу, которая легко обращается, дабы вычислить опорную точку по имеющимся точкам начала и конца, а так же некоторой промежуточной
18:22:05  Rageous: потому его фиттинг легко объяснить на пальцах:
18:22:24  Rageous: мы берем весь пакет данных, вычисляем для него усредненную опорную точку
18:22:55  Rageous: с ней прогоняем функцию оценки ошибки. если ошибка слишком велика, делим данные пополам - и проводим ту же процедуру с первой половиной
18:23:37  Rageous: так - до тех пор, пока не найдем кусок данных максимальной длины, который можно представить в виде начальной, конечной точек и опорного значения (P1 в формулах на вики)
18:24:09  Rageous: с оставшимися данными процесс повторяется до тех пор, пока весь пакет не будет представлен в виде наборов квадратичных сплайнов

#аппроксимация, #битстрим, #векторные данные, #сжатие, #сплайны

20 апреля 2008 (Обновление: 21 фев 2012)