Как рисовали Зеленоград

Посмотрев видеоролик Russia: Edits to OpenStreetMap 2007-2012 ^[1] от ITO World, я захотел сделать свой — только по Зеленограду. Чтобы хорошо было видно детали и даже мелкие правки.

На реализацию ушло больше 2 недель.
В этой статье я расскажу, как это было сделано.
Само видео сразу под катом.

Смотреть лучше на полный экран в 1080p и со звуком

Создание такого видео делится на 2 основных части:

1. Получить нужные данные
2. Собрать из этих данных видеоролик

Получить нужные данные

Получение исторических данных несколько затруднено архитектурой OpenStreetMap, которая рассчитана на быструю выдачу текущей карты и редактирование, но не на выгрузку истории. Дополнительно задача усложнена сменой лицензии ^[2] с СС-BY-SA на ODbL, которая привела к удалению из базы части объектов и истории изменений некоторых других. Зеленоград пострадал при смене лицензии весьма сильно, на 7:18 это хорошо видно в ролике.
В целом пока нет сервиса, который позволял бы удобно скачивать всю историю всех объектов в некоторой области.

Что нужно

Для начала, конечно, нужно определиться что скачивать.
Зеленоград по административной границе ^[3] довольно неплохо вписывается в почти квадратную рамку. Однако зацепить ближайшие окрестности (Менделеево, Чашниково, Голубое, Фирсановку, Пятницкое шоссе и т.п.) без поворота, перекоса или существенного искажения масштаба не получается. Было решено обязательно добавить лишь Фирсановское шоссе ^[4].
Full HD 1920x1080 получался несколько диспропорциональным — Зеленоград по центру, неполные Фирсановка и Сходня в нижнем правом углу и пустые остальные углы. При сохранении вертикального разрешения в 1080 строк, минимальный кадр получался 1220х1080. После некоторой медитации над схемой видеоразрешений ^[5] было решено расшириться до 1440х1080.
Для скачивания данных был взят bbox 55.92-56.05,37.08-37.31 — с запасом под линии, уходящие за край кадра.

Источники данных

Из основных источников есть (на момент написания статьи):

1. Основная база, выдающая только ODbL данные — либо текущие по региону, либо историю по-объектно, либо по changeset.
2. Последний полный исторический дамп (full history planet file) ^[6] от 19 октября, весящий 37 GB в bz2-архиве, только ODbL данные. Т.е. 300-500 GB в распакованном виде, полуторамесячной давности и не вся история.
3. Последний полный исторический дамп под СС-BY-SA ^[7] от 1 июня, весящий 35 GB в bz2-архиве. Это за 1.5 месяца до «выпиливания» ботом данных несовместимых с ODbL и за 4.5 месяца до смены лицензии.
4. Посуточные ^[8], почасовые и поминутные диффы — как текущей базы под ODbL, так и эпохи CC-BY-SA ^[9], так и переходного периода ^[10].
5. Различные выгрузки полной истории ^[11].
6. Суточные диффы России на gis-lab ^[12] к сожалению содержат пропуски, планетарные ^[13] — нет, но все они содержат лишь окончательные версии изменённых объектов, т.е. не совсем подходят для видео детальнее чем 1 кадр в сутки.

Эксперименты показали, что вырубка нужных данных из полного исторического дампа требует существенных ресурсов. Например, скрипт history-excerpt.pl ^[14] жаловался на нехватку оперативной памяти, даже когда её было 6 GB.

В итоге был выбран смешанный вариант:

1. История до 2012.04.01 взята из выгрузки России от Simon Poole ^[15] (russia.osh.bz2 — 1 GB), всего 17 GB в распакованном виде.
2. История с 2012.04.01 по 2012.08.31 взята из посуточных диффов переходного периода ^[10]. Диффы состыкованы с эпохой CC-BY-SA не полностью (часть правок 1-4 апреля есть только в почасовых и поминутных диффах), но правки по Зеленограду находятся все в посуточных. Тем не менее, 65 GB в распакованном виде.
3. История с 2012.09.01 взята из основной базы путём выкачивания всех changeset по Зеленограду. Перечень changeset получен через скачивание сотни страниц истории изменения прямоугольной области ^[16] с сайта openstreetmap.org. Данный источник выдаёт множество лишних данных (например, попался импорт Аляски ^[17], не стал скачивать), однако за небольшой период объём данных небольшой — всего 90 MB.

Вырезать нужный фрагмент

По текущей архитектуре, в OSM 3 типа сущностей — node, way и relation. Но если node (точка) имеет координаты, то way (линия) является лишь перечнем node и собственных координат не имеет. Для выгрузки данных по определённой области это означает, что нужные node выбрать просто, а вот для выбора нужных way нужно проверять все используемые им node. Т.е. необходимо строить разреженный перечень node (идентификаторы уже почти достигли 2 миллиардов), позволяющий быстро проверять way по нему.
Relation служат для группировки объектов и рисования сложных конструкций, могут состоять из node, way и других relation в том числе могут образовывать любой уровень вложенности и зацикливания. Для данного видео было решено их не загружать и не отображать — поскольку они не дают дополнительно геометрии (повлиять могут на порядок закрашивания областей, которое в видео не используется).

После нескольких экспериментов было выбран следующий порядок:

1. Перечень node составлялся с помощью утилиты egrep, которая регулярным выражением
   весьма быстро протягивала через себя все данные (в том числе упакованные данные направлялись в неё из архива без сохранения в файл).
   Далее из списка выдёргивались только node id (двумя egrep, sort и uniq) и сохранялись в файл. Заняло около 30 минут суммарно.
2. Специально написанная программка построчно (без парсинга XML) сканировала файл и выдёргивала полную информацию о всех версиях найденных node и о всех way, использующих хоть один из выбранных node. Для посуточных диффов, в которых не указывается атрибут visible для объектов, этот атрибут добавлялся на основании внешнего тэга (<delete> и т.п.). Поиск по перечню node (около 170 тысяч в итоге) был ускорен 16-битным индексом (старшие 16 бит от 32-битного представления node id). Для перечня way, пополняемого на лету, индекс не использовался, т.к. way набралось всего 26 тысяч и проверка требуется существенно реже. Заняло около 7 часов, из них 5 часов — на 150 посуточных диффов.

Результат был проверен на корректность:

1. Проверка последовательного возрастания версий показала, что пропусков нет. Вручную были удалены последние версии way 8038408 ^[18], который в 2008 году шёл от Торжка до Зеленограда, а теперь есть только за Торжком и случайно затесался ^[19] в список изменений, полученных с openstreetmap.org
2. Срезы выгрузки на нужные дни совпали с сохранёнными у меня выгрузками города 2009-2012 годов, а также вырезками из выборочных выгрузок Московской области от gis-lab ^[20] за 2012 год.

Однако при отрисовке кадров было обнаружено, что way 23273948 ^[21], задававший границу спутникового снимка Yahoo в 2008-2010 годах, до апреля 2009 попадал в мой bbox только 1 точкой ^[22] и соответственно рисовался некорректно. Дополнительные node данного way были добавлены в выгрузку вручную.

Итоговую выгрузку можно скачать (6.3 MB в rar) ^[23].
Не забывайте только, что на это сборка данных под двумя лицензиями — CC-BY-SA 2.0 на всё до 2012-09-12T10:00:00Z и ODbL 1.0 после.

Собрать видеоролик

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

1. 2005-11-10T17:35
2. 2007-04-02T12:30
3. 2007-09-29T11:29

Т.е. при общем интервале в 7 лет, за первые почти 2 года — только 2 правки (далее идёт плотно). Пустоты между этими правками было решено «промотать» ускоренно.
Общая скорость 1 кадр в сутки показалась мне слишком высокой. 5 лет более-менее активых правок — 1830 кадров, чуть больше минуты.
1 кадр в час даст 30 минут видео, это слишком много.
Остановился на варианте 1 кадр в 4 часа (т.е. x360000 относительно реальности).
С учётом промотки в начале получилось 11800 кадров, 7:52.

Хронокадры

Для отрисовки кадров нужно либо держать в быстром доступе все версии всех объектов, либо «накладывать» изменения последовательно по течению времени и рисовать кадры в нужные моменты. Остановился на втором варианте.
Поскольку выгрузка от Simon Poole организована «все node — все way — все relation», её нужно было как-то упорядочить по течению времени. Простой программкой (опять построчно без парсинга XML) выгрузка была разбита на хронокадры — изменения за каждый 4-х часовой интервал были записаны в отдельный файл, названый по времени кадра. Заняло около 10 минут.
Теперь достаточно загружать хронокадры последовательно и после каждого рисовать изображение.

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

Отрисовка в SVG

Чтобы не изобретать собственный растровый рендерер было решено формировать векторые SVG ^[24], которые потом конвертировать в растр готовыми программами. SVG удобен тем что он xml-но текстовый и поддерживает всякие удобные штуки типа полупрозрачности.
Для формирования SVG снова пришлось писать программку, теперь уже с парсингом XML. Однако объём данных стал уже вполне приемлемый.
Рендеринг занял 1 час 15 минут. Общий объём SVG — 15 GB.

20120720080000.svg — последний кадр до прихода бота
^[25]

20120721000000.svg — апогей выпиливания неODbL-ных данных
^[26]

Хочу отметить, что разные программы иногда по разному интерпретируют SVG и к этому надо быть готовым. Chromium, которым я смотрел формируемые файлы, иногда показывал мне не такую картину, как потом делал ImageMagick. Формирование SVG пришлось несколько раз корректировать.

Конвертация в растр

Первоначально планировалась конвертация SVG в PNG ^[27], как наиболее подходящего формата для растровых схем. Однако мне не удалось подружить avidemux с PNG формируемыми ImageMagick, avidemux упорно заливал мне весь кадр зелёным цветом.
В итоге была сделана конвертация в BMP.
Работала утилита convert из ImageMagick ^[28] с единственным ключом -type truecolor
Процесс занял 6 часов. Общий объём BMP — 53 GB.

Сборка видео

Видеоролик собирался из пачки BMP-файлов программой avidemux ^[29].
Был выбран кодек Xvid, как GNU-шный и неплохо зарекомендовавший себя. Относительно стандартных настроек только quantizer был переставлен на 2.
Сборка заняла примерно 25 минут.

Видео без музыки выложено в виде файла (137 MB) ^[30] под лицензией CC-BY-SA 3.0
Два кадра SVG выше — также под этой лицензией.

Наложение музыки

Музыка из моей коллекции не совместима с лицензиями CC, поэтому вариант с музыкой был сделан для youtube.
Чтобы заполнить почти 8 минут были взяты наиболее эпичные фрагменты из композиций

1. Vangelis — Voices (примерно с 1:00 по 6:50)
2. Bond — Elysium (примерно с 0:30 по 2:30)

Музыка смикширована в Adobe Audition, наклеена на видео в VirtualDub ^[31]
Привязка каких-то событий к музыке не делалась, все совпадения случайны.

Результат

Что отображается на видео:

• Timestamp и лицензия на соответствующий момент
• Все выгруженные way — линиями
• Все выгруженные node, не входящие ни в один way — точками
• Новые объекты вспыхивают белым и медленно гаснут до зелёного и тёмно-зелёного
• Модифицированные объекты вспыхивают жёлтым и медленно гаснут до зелёного и тёмно-зелёного
• Удалённые объекты вспыхивают красным и плавно пропадают (т.е. видны после фактического удаления)
• Если модифицируются node, входящие в way, но не меняется сам way, node вспыхивают жёлтыми точками и плавно гаснут
• Отображаются никнеймы всех, кто выполнил правку в видимой области — вспыхивают белым в момент правки, плавно гаснут до зелёного и пропадают
• Никнеймы двух административных аккаунтов, выпиливавших неODbL-ные данные, — вспыхивают красным

Благодарности:

• Simon Poole — за full history выгрузку России на 1 апреля 2012 года.
• Larry0ua ^[32] — за идею использовать посуточные диффы.
• giner ^[33] — за идею показывать никнеймы, помощь по использованию линуксовых утилит и бета-тестинг.
• авторам ImageMagick, avidemux, VirtualDub, Xvid, osmconvert и Ubuntu

Принимаются предложения:

• Как собрать «видео» в виде 1 SVG с анимацией
• Какой видеокодек использовать для лучшей передачи такой wireframe графики

Автор: OverQuantum

Источник ^[34]