Пусть мы взяли две картинки:

Пусть мы поняли насколько отличаются их цвета в одном и том же пикселе:

Давайте проложим кратчайший путь по этой карте различий из нижнего левого угла всего пространства панорамы в верхний левый угол:

Что нам для этого надо учесть? Как свести задачу к Дейкстре из прошлого задания?

• Давайте максимально приблизим к решению из задания про “найти выход в лабиринте-картинке”

• Достаточно создать картинку-лабиринт (см. функцию buildTheMaze(...)) из нашей картинки насколько отличаются их цвета в одном и том же пикселе

• А в пикселях лабиринта где хотя бы одна из наложенных картинок отсутствует (т.е. isPixelEmpty(...), т.е. черный пиксель) - скажем что цена прохождения очень высокая - например const int BIG_PENALTY = 100000;

• После чего (см. функцию findBestSeam(...)) из каждого пикселя давайте проведем ребро вверх и ребро вправо с длинной равной значению содержащемуся в пикселе лабиринта

• И наконец найдем Дейкстрой кратчайший путь из вершины start соответствующей нижнему левому углу всего пространства панорамы, в вершину finish соответствующую верхнему правому углу всей панорамы

Теперь надо как-то построить красивую панораму так чтобы все что слева от этого шва - было взято из первой картинки, а все что справа от этого шва - было взято из правой картинки.

Давайте визуализируем и построим для начала такую картинку - в каждом пикселе черный цвет (PIXEL_NO_DATA = 0) если этого пикселя нет ни на одной картинке, темно-серый (PIXEL_FROM_PANO0 = 100) если этот пиксель должен быть взят с первой картинки, светло-серый (PIXEL_FROM_PANO1 = 200) если со второй:

Как построить такую картинку? Давайте начнем с того чтобы заполнить всю картинку PIXEL_NO_DATA, затем запретим пересекать шов - заполним все пиксели принадлежащие шву значением PIXEL_IS_ON_SEAM = 1, затем с помощью поиска в ширину заполним пиксели относящиеся к первой картинке (т.е. PIXEL_FROM_PANO0):

1) Изначально отметим все пиксели как PIXEL_NO_DATA

2) Теперь запретим пересекать шов - заполним все пиксели принадлежащие шву значением PIXEL_IS_ON_SEAM = 1

3) Дальше давайте воспользуемся поиском в ширину (BFS) чтобы распространить влияние первой картинки начиная с верхнего левого угла вплоть до шва-границы

4) Отметим верхний левый пиксель как PIXEL_FROM_PANO0 и добавим его в текущую волну распространения (curWave)

5) Выполняем в цикле while до тех пока в текущей волне распространения (curWave) есть хотя бы один пиксель:

5.1) Смотрим на каждый пиксель из текущей волны распространения и смотрим в цикле на каждый из четырех соседей (слева, сверху, справа, снизу)

5.2) Если сосед (neighbor - сосед, поэтому пусть nx, ny) за пределами картинки - ничего с ним не делаем

5.3) Если сосед пуст в первой картинке - в него тоже не надо распространять влияние первой картинки - ничего с ним не делаем

5.4) Если это пиксель лежащий на шве (PIXEL_IS_ON_SEAM) - в него тоже не надо распространять влияние первой картинки - ничего с ним не делаем

5.5) Если это пиксель который уже принадлежащий первой картинке (PIXEL_FROM_PANO0) - ничего с ним не делаем

5.6) Иначе - отмечаем соседний пиксель nx, ny как принадлежащий первой картинке (PIXEL_FROM_PANO0) и добавляем его в следующую волну обработки nextWave

5.7) Когда мы обработали все пиксели текущей волны - новая волна готова, берем ее вместо текущей: curWave = nextWave;

6) Все остальные пиксели будем заполнять со второй картинки - значит все кто не PIXEL_FROM_PANO0 и при этом не пусты на второй картинке - должны быть заполнены PIXEL_FROM_PANO1

Наконец давайте сделаем красивую панораму с учетом этой картинки указывающей откуда какую картинку брать:

Как это сделать? пройти по всем пикселям, посмотреть из какой картинки брать цвет - и взять соответственно :)

Сделайте свою панораму

Сделайте две фотографии при этом убрав два объекта на фоторой фотографии, примерно так:

Голубая вертикаль показывает где прошла граница другой фотографии.

Когда снимаете первую фотографию положите объект (зеленого Единорога) там где будет проходить граница второй фотографии.

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

Когда снимаете вторую фотографию уберите старый объект и положите новый объект (фиолетовое нечто, или можете просто переложить объект) там где проходит граница первой фотографии.

Подумайте где должен был бы пройти шов, проверьте где он на самом деле прошел. А что будет если оба эти объекта большие и наложатся?

Чтобы сохранить результат на github - разверните все подпапки в lesson17/resultsData -> выделите все картинки (кликнув по самой верхней, а затем зажав Shift и кликнув по самой нижней) -> правая кнопка мыши -> Git -> Add.

Как ускорить Дейкстру

1) Использовать компиляцию с оптимизациями, т.е. компилировать Release или RelWithDebInfo

2) В самом начале считанные картинки уменьшить в разрешении - см. сколько раз они уменьшаются - переменная int downscale = 2;

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

• Создайте эту приоритетную очередь (очередь по английски - queue): std::set<std::pair<int,int>> queue;

• Каждый элемент в этой очереди - пара, первое число в паре - приоритет (в нашем случае “расстояние от старта”), второе число - номер вершины

• Изначально в очередь нужно добавить стартовую вершину с приоритетом 0: queue.insert( std::pair<int,int>(0, start));

• Чтобы достать (и удалить из очереди) минимальный элемент (тоже пару): std::pair<int, int> min_pair = queue.extract(queue.begin()).value();

• Чтобы узнать из минимального элемента что за вершина в нем: the_closest_one = min_pair.second; (не забудьте проверить - а не обработана ли уже эта вершина, ведь мы одну и ту же вершину могли добавить в очередь несколько раз, подумайте об этом!)

• И наконец каждый раз когда у какой-то вершины меняется дистанция - ее нужно добавить в очередь с этой новой дистанцией как приоритет: queue.insert(std::pair<int, int>(vertex_new_distance, vertex));

• Удобнее всего обкатать ускоренную Дейкстру в прошлом задании про лабиринты, когда заработает - можно убрать уменьшение картинок в этом задании - int downscale = 0;