Кейт Ма был научным сотрудником летом 2018 года. В настоящее время он работает инженером по обработке данных в лабораториях Tellus, где занимается изучением и моделированием глобального предложения сельскохозяйственных культур. Кейт воодушевлен пересечением геопространственных данных и машинного обучения, а также проблемами, уникальными для этой области. До Insight он защитил докторскую диссертацию. получил степень доктора геологии и геофизики в Йельском университете.

Солнце и тень сильно влияют на то, сколько из нас выбирает маршрут к тем местам, которые мы хотим посетить. Лично для меня прямое солнце - это сам дьявол. Цель зонтика - использовать знания об окружающей среде, чтобы помочь людям принимать эти решения. Это аналогично тому, как мы используем популярные навигационные приложения, такие как Google Maps или Waze, для навигации по загруженным дорогам: мы хотим избежать перегруженных маршрутов, и приложения используют дополнительную информацию о текущих условиях, чтобы помочь нам в этом. Навигационное приложение Зонтик знает больше о солнечном и тенистом месте, чем вы, и может помочь вам придерживаться того, что вам больше всего нравится.

Я построил Parasol в течение четырех недель в качестве независимого проекта с Insight Data Science. Я не могу рекомендовать это товарищество достаточно высоко. Если вы доктор философии и хотите сделать карьеру в области науки о данных, обращайтесь в Insight. Если вы - компания, которая ищет новых специалистов по данным, станьте партнером.

Для заинтересованных, весь код этого проекта размещен на Github по адресу: github.com/keithfma/parasol.

TL;DR

Parasol использует данные о высоте с высоким разрешением для имитации солнечного света и построения маршрутов, которые удерживают пользователей на солнце или в тени, в зависимости от того, что они предпочитают. Вы можете попробовать приложение на сайте parasol.allnans.com. Еще проще посмотрите демонстрационное видео ниже:

Подход, лежащий в основе Parasol, на удивление прост. Сначала я построил модель рельефа с высоким разрешением. Затем я смоделировал солнце / тень, используя положение солнца для заданной даты и времени, чтобы осветить сетку высот. Затем я вычислил функцию стоимости, которая включает солнце / тень, а также расстояние для каждого сегмента транспортной сети. Наконец, я применил алгоритм Дейкстры для вычисления кратчайшего пути с заданной стоимостью. Все это упаковано в удобное веб-приложение.

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

Исходные данные, которые я использовал:

Основные инструменты, которые я использовал:

Отметка с привязкой к координатной сетке из LiDAR

Чтобы создать достойную модель оттенка, мне нужна была достойная модель рельефа. Моей целью было построить две сетки высот: одну для «верхней поверхности», включая здания, деревья и т. Д., И одну для «нижней поверхности», которая исключает эти вещи. Для моих целей солнце светит на верхней поверхности, а люди ходят по нижней.

Данные сканирования LiDAR (Light Detection and Ranging) - почти идеальный источник данных для моего приложения. Необработанные данные состоят из «облака точек», то есть длинного списка точек (x, y, z,…) с интервалом ‹1 метр. Более того, каждый лазерный выстрел может иметь несколько отражений, так что можно разрешить как верхушку деревьев, так и возвышенность голой земли.

Первой задачей было разделить облако точек на верхнюю и нижнюю части (то есть верхушки деревьев и голую землю). Есть несколько хорошо зарекомендовавших себя методов для этого, но оказалось, что данные LiDAR, которые я использовал, были предварительно классифицированы NOAA. Поскольку эти классификации были довольно хороши, я просто использовал их прямо из коробки.

Теперь у меня было два облака точек, но все еще не было сетки. Данные LiDAR находятся не на хорошей регулярной сетке, а, скорее, разбросаны с неравномерным интервалом. Поскольку в измеренной высоте есть некоторый шум, мне нужно было сгладить (не интерполировать) необработанные данные, а затем выполнить повторную выборку на регулярной сетке. Это сложнее, чем можно было бы ожидать, особенно потому, что объекты с острыми краями (например, здания) важны для моделирования солнца / тени. Я использовал медианный фильтр ближайшего соседа, который возвращает медианное значение k -ближайших соседей для каждой точки выходной сетки. Это дает хороший эффект как сглаживания шума в данных, так и сохранения резких краев. Медианные фильтры распространены для уменьшения шума изображения, но мне пришлось реализовать свои собственные для работы с разрозненными входными данными. Если интересно, можете найти здесь код моего медианного фильтра ближайшего соседа - это довольно просто!

Имитация солнечного света

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

Я также провел быструю качественную проверку, в которой я сравнил смоделированные тени с наблюдаемыми тенями в аэрофотосъемке высокого разрешения (из программы NAIP).

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

Стоимость Солнца и Тени

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

  1. Учитывайте как инсоляцию, так и расстояние
  2. Учитывайте маршруты, которые предпочитают солнце, а также маршруты, которые предпочитают тень
  3. Иметь минимальное количество бесплатных параметров (в идеале - один), чтобы пользователям было легко указать свои предпочтения
  4. Быть неотрицательным

Оказывается, я смог записать стоимость как простое средневзвешенное значение «стоимости солнца» и «стоимости тени»:

cost = β⋅sun_cost + (1 − β) shade_cost

Параметр веса (β) отражает предпочтения пользователя в отношении солнца или тени. Он варьируется от 0 (общее предпочтение тени) до 1 (общее предпочтение солнцу).

Термин «солнечная стоимость» - это интеграл по пути от инсоляции вдоль каждого сегмента транспортной сети OpenStreetMaps. Это связано с количеством солнечного света, которое вы поглотите, пройдя определенный отрезок пути. Прекрасная особенность интегрирования по длине каждого сегмента заключается в том, что стоимость неявно включает длину сегмента - это среднее значение инсоляции, умноженное на длину сегмента.

Оказывается, в этом сверхпростом подходе есть проблема: инсоляция составляет порядка 1000 Вт / м², тогда как длина маршрута составляет порядка 10 м, что означает, что солнце намного важнее, чем расстояние в общей стоимости. По опыту могу сказать, что это ведет к очень сумасшедшим маршрутам. Чтобы решить эту проблему, я изменил масштаб инсоляции до диапазона от 0 до 1 перед вычислением стоимости. Это равносильно присвоению расстоянию и инсоляции равных весов в функции стоимости. На практике это генерирует разумные маршруты, поэтому я остановился на этом, но было бы очень интересно изучить, какое масштабирование приведет к «оптимальной» функции стоимости. Если принять значение I как нормализованную инсоляцию, стоимость солнца составит:

sun_cost = ∫ₛ I ds

В дальнейшем термин «стоимость тени» немного страннее, чем «стоимость солнца». Это интеграл по пути от снижения инсоляции из-за тени вдоль каждого сегмента транспортной сети. Это связано с количеством солнечного света, которого избегает тень на каждом сегменте. Я рассчитал стоимость тени как разницу между максимальной инсоляцией и наблюдаемой инсоляцией. Поскольку инсоляция нормализована (имеет максимальное значение 1), это составляет:

shade_cost = ∫ₛ 1 - I ds

Вот что самое интересное: если пользователь устанавливает β = 0,5, мы восстанавливаем путь кратчайшей длины! Работа над этим показывает, что стоимость в этом случае - это просто интеграл по путям от константы, которая пропорциональна длине.

cost = 0,5 ∫ₛ I ds + 0,5 1 - I ds

cost = 0,5 ∫ₛ I + (1 - I) ds

cost = ∫ₛ 0,5 дс

Вуаля! Функция стоимости с одним параметром, которая позволяет пользователям выбирать солнечные или тенистые маршруты и при этом заботиться о расстоянии.

Маршрутизация с затратами на солнце / тень

Тяжелую работу по вычислению маршрута выполняет замечательное расширение PostgreSQL, pgRouting. Это расширение вычисляет маршруты с наименьшей стоимостью с использованием различных алгоритмов (я использовал Dijkstra) и позволяет пользователю указывать стоимость как функцию столбцов в базе данных OpenStreetMap. Все, что мне нужно было сделать, это сохранить вычисленную стоимость солнца и тени для каждого сегмента транспортной сети в моей базе данных, выбрать правильный столбец для использования в зависимости от времени суток и применить мое простое уравнение стоимости.

Веб-приложение

Я не буду вдаваться в подробности, но я настроил веб-приложение с помощью Python и Flask для размещения API с конечными точками для генерации маршрутов и т. Д., Использовал Leaflet с несколькими замечательными расширениями для создания интерактивной карты и разместил солнце / затенять имитацию изображений с помощью Geoserver.

Следующие шаги

Моя самая большая надежда на Parasol заключается в том, что эта идея привлечет внимание и будет реализована и интегрирована в одно (или несколько!) из множества замечательных навигационных приложений, существующих в дикой природе . Вот несколько вещей, которыми я надеялся заняться, но на которые не хватило времени:

  1. Для прокладки маршрута используйте тротуары, а не дороги. Хотя OpenStreetMaps включает в себя специальные теги для тротуаров, покрытие крайне неполное. Это проблематично, потому что Зонтик не может посоветовать пользователям пользоваться улицами, где один тротуар тенистый. Есть несколько способов сделать это: (1) попытаться синтезировать график тротуаров или (2) отрегулировать затраты на солнце и тень, чтобы следовать по лучшей стороне каждой улицы.
  2. Отрегулируйте тень, чтобы учесть сезонный покров деревьев. Определенно возможно идентифицировать деревья по данным LiDAR, и тень, отбрасываемую этими деревьями, может быть скорректирована в зависимости от сезона. Более того, вероятно, можно использовать спутниковые снимки, чтобы определить время изменения.
  3. Лучше литье лучей! Я использовал GRASS GIS, который работал нормально, но, вероятно, было бы лучше воспользоваться преимуществами замечательного механизма, который управляет современной компьютерной графикой. Дополнительным преимуществом было бы то, что LiDAR можно было бы преобразовать в правильную 3D-модель, а не в сетку высот, а литье лучей могло бы лучше обрабатывать края препятствующих объектов.

Хотите перейти к карьере в области науки о данных? Узнайте больше о программе Insight Data Science Fellows Program в Кремниевой долине, Нью-Йорке, Бостоне, Сиэтле и Торонто. Подайте заявку сегодня или подпишитесь на обновления программы.

Первоначально опубликовано на сайте http://www.allnans.com/jekyll/update/2018/08/07/introduction-parasol.html 7 августа 2018 г.