Построение карты высот численными методами

Цель проекта — построить карты высот по набору зашумлённых и/или неполных карт на графическом процессоре GPU. Такой подход удобно использовать в картографировании, потому что в некоторых случаях хороший результат легче получить через большое количество не самых лучших данных, чем через маленькое количество идеальных. 

Карта высот — это двумерный массив, значения которого и есть высота в точке (x,y). На первых этапах она представлялась в виде png изображения, но со временем мы перешли на формат PFM, потому что ошибки целочисленного округления ухудшали результаты.

Выбор языков программирования и фреймворка

Математику для решения этой задачи уже написали и доказали, поэтому хочется её постепенно и аккуратно воплотить в код: от прототипирования на Python до полноценного приложения, которое работает на GPU. Решения подобных задач уже есть в открытом доступе. В основном это код на python и matlab.

Однако решение, которое мы предложили в течение практики, базируется на OpenCL. Для этого есть несколько причин: 

— Это открытое ПО, которое работает почти на любом железе. 

— Это стандарт для GPU и среда исполнения для процессоров. Она позволяет выжать из процессора почти всё, что можно, включая SSE команды. 

Выбор С++ в этой задаче достаточно очевиден: нам хочется достичь максимальной производительности. OpenCL 1.2 работает с модификацией C99, а значит перенос на него будет легче с C++.

Реализация

Мы реализовали все, что описали, покрыли тестами и собрали на Travis CI, чтобы избежать ситуаций «на моей машине работает, проблемы у вас».

Производительность выросла, как и ожидалось. Это подтверждается бенчмарками, которые мы провели на коленке.

Затем мы применили алгоритм на настоящих данных. Под прицел попал набор карт высот города Дортмунд. Набор данных представлен большим количеством отснятых участков, которые выглядят так:

Их прямое совмещение даёт такой результат:

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