Квантовый Ёжик (overquantum) wrote,
Квантовый Ёжик
overquantum

Categories:
  • Music:

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


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

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



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

Создание такого видео делится на 2 основных части:
  1. Получить нужные данные

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

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

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

Что нужно

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

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

Из основных источников есть (на момент написания статьи):
  1. Основная база, выдающая только ODbL данные - либо текущие по региону, либо историю по-объектно, либо по changeset.

  2. Последний полный исторический дамп (full history planet file) от 19 октября, весящий 37 GB в bz2-архиве, только ODbL данные. Т.е. 300-500 GB в распакованном виде, полуторамесячной давности и не вся история.

  3. Последний полный исторический дамп под СС-BY-SA от 1 июня, весящий 35 GB в bz2-архиве. Это за 1.5 месяца до "выпиливания" ботом данных несовместимых с ODbL и за 4.5 месяца до смены лицензии.

  4. Посуточные, почасовые и поминутные диффы - как текущей базы под ODbL, так и эпохи CC-BY-SA, так и переходного периода.

  5. Различные выгрузки полной истории.

  6. Суточные диффы России на gis-lab к сожалению содержат пропуски, планетарные - нет, но все они содержат лишь окончательные версии изменённых объектов, т.е. не совсем подходят для видео детальнее чем 1 кадр в сутки.
Эксперименты показали, что вырубка нужных данных из полного исторического дампа требует существенных ресурсов. Например, скрипт history-excerpt.pl жаловался на нехватку оперативной памяти, даже когда её было 6 GB.

В итоге был выбран смешанный вариант:
  1. История до 2012.04.01 взята из выгрузки России от Simon Poole (russia.osh.bz2 - 1 GB), всего 17 GB в распакованном виде.

  2. История с 2012.04.01 по 2012.08.31 взята из посуточных диффов переходного периода. Диффы состыкованы с эпохой CC-BY-SA не полностью (часть правок 1-4 апреля есть только в почасовых и поминутных диффах), но правки по Зеленограду находятся все в посуточных. Тем не менее, 65 GB в распакованном виде.

  3. История с 2012.09.01 взята из основной базы путём выкачивания всех changeset по Зеленограду. Перечень changeset получен через скачивание сотни страниц истории изменения прямоугольной области с сайта openstreetmap.org. Данный источник выдаёт множество лишних данных (например, попался импорт Аляски, не стал скачивать), однако за небольшой период объём данных небольшой - всего 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, который в 2008 году шёл от Торжка до Зеленограда, а теперь есть только за Торжком и случайно затесался в список изменений, полученных с openstreetmap.org

  2. Срезы выгрузки на нужные дни совпали с сохранёнными у меня выгрузками города 2009-2012 годов, а также вырезками из выборочных выгрузок Московской области от gis-lab за 2012 год.
Однако при отрисовке кадров было обнаружено, что way 23273948, задававший границу спутникового снимка Yahoo в 2008-2010 годах, до апреля 2009 попадал в мой bbox только 1 точкой и соответственно рисовался некорректно. Дополнительные node данного way были добавлены в выгрузку вручную.

Итоговую выгрузку можно скачать (6.3 MB в rar).
Не забывайте только, что это сборка данных под двумя лицензиями - 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, которые потом конвертировать в растр готовыми программами. SVG удобен тем что он xml-но текстовый и поддерживает всякие удобные штуки типа полупрозрачности.
Для формирования SVG снова пришлось писать программку, теперь уже с парсингом XML. Однако объём данных стал уже вполне приемлемый.
Рендеринг занял 1 час 15 минут. Общий объём SVG - 15 GB.

20120720080000.svg - последний кадр до прихода бота


20120721000000.svg - апогей выпиливания неODbL-ных данных


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

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

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

Сборка видео

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

Видео без музыки выложено в виде файла (137 MB) под лицензией 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
Привязка каких-то событий к музыке не делалась, все совпадения случайны.

Результат

Что отображается на видео:
  • Timestamp и лицензия на соответствующий момент

  • Все выгруженные way - линиями

  • Все выгруженные node, не входящие ни в один way - точками

  • Новые объекты вспыхивают белым и медленно гаснут до зелёного и тёмно-зелёного

  • Модифицированные объекты вспыхивают жёлтым и медленно гаснут до зелёного и тёмно-зелёного

  • Удалённые объекты вспыхивают красным и плавно пропадают (т.е. видны после фактического удаления)

  • Если модифицируются node, входящие в way, но не меняется сам way, node вспыхивают жёлтыми точками и плавно гаснут

  • Отображаются никнеймы всех, кто выполнил правку в видимой области - вспыхивают белым в момент правки, плавно гаснут до зелёного и пропадают

  • Никнеймы двух административных аккаунтов, выпиливавших неODbL-ные данные, - вспыхивают красным
Благодарности:
  • Simon Poole - за full history выгрузку России на 1 апреля 2012 года.

  • Larry0ua - за идею использовать посуточные диффы.

  • giner - за идею показывать никнеймы, помощь по использованию линуксовых утилит и бета-тестинг.

  • авторам ImageMagick, avidemux, VirtualDub, Xvid, osmconvert и Ubuntu
Принимаются предложения:
  • Как собрать "видео" в виде 1 SVG с анимацией

  • Какой видеокодек использовать для лучшей передачи такой wireframe графики


Это моя статья, опубликованная 9-го декабря на Хабре

UPD 2020-07-05: ссылки заменены на яндекс.диск
Tags: habrahabr, howto, maps, openstreetmap, video, zelenograd
Subscribe

  • Беспонтовые печенюшки

    Как вы возможно слышали, Google открыл доступ к новому инструменту Guetzli для сжатия изображений формата JPEG. Что пока удалось выяснить: 1)…

  • SokobanCompact v0.7 - open source

    Опубликовал исходники SokobanCompact v0.7 под GPL v3 на github. SokobanCompact - бесплатная логическая игра типа Sokoban для Windows Mobile 6 и…

  • JPEGfix - чиним файлы JPEG самостоятельно

    JPEGfix - набор инструментов для ремонта повреждённых изображений в формате JPEG. Насколько я знаю, подобных программ в интернете нет, ни в…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments