More Related Content
More from MSU GML VideoGroup (20)
Построение карт глубины и сопоставление стерео
- 1. Построение карт глубины и сопоставление стерео Сергей Матюнин Video Group CS MSU Graphics & Media Lab
- 2. Only for Maxus Содержание Введение Connectivity-slant AdaptingBP Cooperative Optimization Сравнение 2 CS MSU Graphics & Media Lab (Video Group)
- 3. Only for Maxus Введение Вход: стерео-изображение Ищем функцию смещения d(x,y) (disparity) d(x,y)~1/D(x,y), где D(x,y) – глубина Очищенное (rectificated) стерео Scharstein and Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. IJCV 2002. 3 CS MSU Graphics & Media Lab (Video Group)
- 4. Only for Введение Maxus Схема алгоритма Вычисление функции стоимости Суммирование стоимости Вычисление/оптимизация карты смещения Уточнение Scharstein and Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. IJCV 2002. 4 CS MSU Graphics & Media Lab (Video Group)
- 5. Only for Maxus Содержание Введение Connectivity-slant AdaptingBP Cooperative Optimization Сравнение 5 CS MSU Graphics & Media Lab (Video Group)
- 6. Only for Connectivity-slant Maxus Плоский мир Модель глубины: кусочно-постоянная функция Правильное смещение максимизирует площадь сегмента сопоставления и наоборот Сегментация и сопоставление – только совместное решение Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 6 CS MSU Graphics & Media Lab (Video Group)
- 7. Only for Connectivity-slant Maxus Плоский мир Распространение связности через горизонтальные границы Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 7 CS MSU Graphics & Media Lab (Video Group)
- 8. Only for Connectivity-slant Maxus Однозначность и наложения Соответствие «один к одному» для пикселей Если нашли соответствие (Ileft, Iright) то пары (Ileft’, Iright) и (Ileft, Iright’) отбрасываем Пиксели, которые не попали в какую- либо пару, помечаем как наложение Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 8 CS MSU Graphics & Media Lab (Video Group)
- 9. Only for Connectivity-slant Maxus Алгоритм для плоского мира Построчная обработка Для всех возможных значений δx: Сдвигаем IL на δx. Полученное I'L сопоставляем с IR Если есть горизонтальная граница, разрываем связность с предыдущей строкой Строим связанные компоненты Находим веса Обновляем карту смещений, учитывая ограничения единственности Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 9 CS MSU Graphics & Media Lab (Video Group)
- 10. Only for Connectivity-slant Maxus Алгоритм для не плоского мира N пикселей одного изображения соответствуют M пикселям другого Нужно сопоставлять не точки, а интервалы Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 10 CS MSU Graphics & Media Lab (Video Group)
- 11. Only for Connectivity-slant Maxus Алгоритм для не плоского мира Сначала растянуть изображение, потом искать соответствие Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 11 CS MSU Graphics & Media Lab (Video Group)
- 12. Only for Connectivity-slant Maxus Горизонтальный наклон Рассматриваем линейную зависимость между точками левого и правого изображений и характеризуют горизонтальный наклон Максимизируем длину сегмента, содержащего точку Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 12 CS MSU Graphics & Media Lab (Video Group)
- 13. Only for Connectivity-slant Maxus Birchfield and Tomasi method 1 1 1 1 I L(xL ), I L(xL ), I R(xR ), I R(xR ) 2 2 2 2 1 1 I L min {I L(xL ),I L(xL ),I L(xL )} min 2 2 1 1 I L max {I L(xL ),I L(xL ),I L(xL )} max 2 2 I R , I R – аналогично min max d L max { 0 ,I L(xL ) I R ,I R I L(xL )} max min d R max { 0 ,I R(xR ) I L ,I R I R(xR )} max min d min {d L ,d R } разность между xL и xR Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 13 CS MSU Graphics & Media Lab (Video Group)
- 14. Only for Connectivity-slant Maxus Однозначность Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 14 CS MSU Graphics & Media Lab (Video Group)
- 15. Only for Connectivity-slant Maxus Горизонтальный наклон Построчное сопоставление Максимизация связности по строке Сопоставление интервалов Ограничения единственности и наложений Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 15 CS MSU Graphics & Media Lab (Video Group)
- 16. Only for Connectivity-slant Maxus Алгоритм Для всех возможных коэффициентов растяжения mL и смещений ΔL: Растянуть IL на mL. Получить I'L Найти dL по ΔL из уравнения ΔL=( mL – 1 ) xL + dL Сопоставить I'L с IR, используя dL Найти связанные сегменты и их веса Обновить карту смещений, учитывая ограничения единственности Аналогично для коэффициентов mL и ΔL Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 16 CS MSU Graphics & Media Lab (Video Group)
- 17. Only for Connectivity-slant Maxus Вертикальный наклон Изменения по горизонтали Есть наложение Нет горизонтального наклона Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 17 CS MSU Graphics & Media Lab (Video Group)
- 18. Only for Connectivity-slant Maxus Вертикальный наклон Изменения по горизонтали Нет наложения Есть горизонтальный наклон Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 18 CS MSU Graphics & Media Lab (Video Group)
- 19. Only for Connectivity-slant Maxus Вертикальный наклон Изменения по вертикали Есть вертикальный наклон или разрыв Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 19 CS MSU Graphics & Media Lab (Video Group)
- 20. Only for Connectivity-slant Maxus Вертикальный наклон Для надежности можно считать, что горизонтальная граница всегда признак разрыва Если нет границы, то разрыв тоже может быть Нужно использовать восстановление формы по текстуре, освещению и т. д. Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 20 CS MSU Graphics & Media Lab (Video Group)
- 21. Only for Connectivity-slant Maxus Реализация Скрипт для MATLAB CPU Celeron 1.8 GHz Cones – ~5 c Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 21 CS MSU Graphics & Media Lab (Video Group)
- 22. Only for Connectivity-slant Maxus Оригинал Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 22 CS MSU Graphics & Media Lab (Video Group)
- 23. Only for Connectivity-slant Maxus Ground truth Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 23 CS MSU Graphics & Media Lab (Video Group)
- 24. Only for Connectivity-slant Maxus Результат Ogale, Aloimonos. Shape and the stereo correspondence problem. IJCV 2005. 24 CS MSU Graphics & Media Lab (Video Group)
- 25. Only for Maxus Содержание Введение Connectivity-slant AdaptingBP Cooperative Optimization Сравнение 25 CS MSU Graphics & Media Lab (Video Group)
- 26. Only for AdaptingBP Maxus Схема метода 26 CS MSU Graphics & Media Lab (Video Group)
- 27. Only for AdaptingBP Maxus Color segmentation Mean shift color segmentation Излишняя сегментация предпочтительна C.Yang et al. Mean-shift analysis using quasi-newton methods. ICIP 2003. 27 CS MSU Graphics & Media Lab (Video Group)
- 28. Only for AdaptingBP Maxus Mean Shift C.Yang et al. Mean-shift analysis using quasi-newton methods. ICIP 2003. 28 CS MSU Graphics & Media Lab (Video Group)
- 29. Only for AdaptingBP Maxus Self-adapting dissimilarity measure N(x, y) – окно 3 × 3 Nx(x, y) – окно без правого столбца Ny(x, y) – окно без нижней строки A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. 29 CS MSU Graphics & Media Lab (Video Group)
- 30. Only for AdaptingBP Maxus Self-adapting dissimilarity measure Итоговая метрика определяется максимизацией количества надежных соответствий (проверка left-to-right и right-to-left) По надежным соответствиям можно определить уровень шума A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. 30 CS MSU Graphics & Media Lab (Video Group)
- 31. Only for AdaptingBP Maxus Аппроксимация плоскостями Используем только надежные соответствия Нужна устойчивость к выбросам Оценка проводится последовательно по горизонтальным линиям по вертикальным линиям для всего сегмента A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. 31 CS MSU Graphics & Media Lab (Video Group)
- 32. Only for AdaptingBP Maxus Аппроксимация плоскостями Оценка горизонтального наклона: Надежные соответствия внутри одного сегмента на одной горизонтальной линии Гистограмма δd/δx Сглаживание гистограммы Выбор максимума («голосование») Оценка вертикального наклона Аналогично Используем наклон плоскости для устойчивой оценки смещения сегмента A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. 32 CS MSU Graphics & Media Lab (Video Group)
- 33. Only for AdaptingBP Maxus Уточнение Для каждого сегмента и плоскости вычисляем стоимость: d – смещение для плоскости P Для каждого сегмента выбираем плоскость с наименьшей стоимостью Группируем сегменты по плоскостям Повторяем оценку плоскостей для полученных групп A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. 33 CS MSU Graphics & Media Lab (Video Group)
- 34. Only for AdaptingBP Maxus Устойчивая оценка плоскостей Ищем разметку сегментов – множество соседних сегментов – штраф (длина общей границы и похожесть цветов) Loopy Belief Propagation A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. 34 CS MSU Graphics & Media Lab (Video Group)
- 35. Only for AdaptingBP Maxus Реализация CPU Athlon64 2.21GHz 14 – 25 с Большая часть – сегментация A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. 35 CS MSU Graphics & Media Lab (Video Group)
- 36. Only for AdaptingBP Maxus Оригинал A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. 36 CS MSU Graphics & Media Lab (Video Group)
- 37. Only for AdaptingBP Maxus Ground truth A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. 37 CS MSU Graphics & Media Lab (Video Group)
- 38. Only for AdaptingBP Maxus Результат A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. 38 CS MSU Graphics & Media Lab (Video Group)
- 39. Only for Maxus Содержание Введение Connectivity-slant AdaptingBP Cooperative Optimization Сравнение 39 CS MSU Graphics & Media Lab (Video Group)
- 40. Only for Cooperative Optimization Maxus Схема алгоритма Сегментация Стерео Mean Shift Начальная оценка смещения (Adaptive correlation window matching) Оценка плоскостей смещения Кооперативная оптимизация Карта (Cooperative Optimization) смещений Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 40 CS MSU Graphics & Media Lab (Video Group)
- 41. Only for Cooperative Optimization Maxus Начальное приближение Суммирование функции стоимости в окрестности с весами Вес зависит от принадлежности к текущему сегменту Для соседних сегментов вес ненулевой Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 41 CS MSU Graphics & Media Lab (Video Group)
- 42. Only for Cooperative Optimization Maxus RANSAC Повторяем заданное количество раз: Выбираем k случайных элементов из n исходных Строим по ним модель Считаем количество элементов, удовлетворяющих модели (inlier) Модель с наибольшим количеством inlier будет результатом Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 42 CS MSU Graphics & Media Lab (Video Group)
- 43. Only for Cooperative Optimization Maxus Устойчивость к выбросам Количество ошибок Сравнение RANSAC и алгоритма голосования Голосование более устойчиво Эксперимент Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 43 CS MSU Graphics & Media Lab (Video Group)
- 44. Only for Cooperative Optimization Maxus Идея Разбиваем задачу на подзадачи Оптимизируем отдельно Поддерживаем постоянными общие параметры Повторяем до сходимости Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 44 CS MSU Graphics & Media Lab (Video Group)
- 45. Only for Cooperative Optimization Maxus Представляем энергию в виде суммы по сегментам: E ( x) E1 ( x) E2 ( x) ... En ( x) Оптимизация ддл каждого сегмента Ei( x) min ((1 i ) Ei ( x) i wij E j ( x)) x j i Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 45 CS MSU Graphics & Media Lab (Video Group)
- 46. Only for Cooperative Optimization Maxus Функционал энергии и – множества видимых пикселей q и p – сопоставленные пиксели Если смещение не целочисленное, интерполируем Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 46 CS MSU Graphics & Media Lab (Video Group)
- 47. Only for Cooperative Optimization Maxus Наложения – штраф за наложение – количество пикселей с наложением Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 47 CS MSU Graphics & Media Lab (Video Group)
- 48. Only for Cooperative Optimization Maxus Гладкость – множество пикселей границы – соседний пиксель с d(p) и d(q) – смещение p и q – константа-штраф Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 48 CS MSU Graphics & Media Lab (Video Group)
- 49. Only for Cooperative Optimization Maxus Функционал энергии На каждой итерации находим локальный минимум Метод Пауэлла Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 49 CS MSU Graphics & Media Lab (Video Group)
- 50. Only for Cooperative Optimization Maxus Оригинал 50 CS MSU Graphics & Media Lab (Video Group)
- 51. Only for Cooperative Optimization Maxus 1-я итерация: e=516622.0 51 CS MSU Graphics & Media Lab (Video Group)
- 52. Only for Cooperative Optimization Maxus 4-я итерация: e=467576.0 52 CS MSU Graphics & Media Lab (Video Group)
- 53. Only for Cooperative Optimization Maxus Ground Truth 53 CS MSU Graphics & Media Lab (Video Group)
- 54. Only for Cooperative Optimization Maxus Реализация VC8.0 CPU PM1.6G Tsukuba – ~20 с 4 итерации Сегментация – 8 с Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. 54 CS MSU Graphics & Media Lab (Video Group)
- 55. Only for Maxus Содержание Введение Connectivity-slant AdaptingBP Cooperative Optimization Сравнение 55 CS MSU Graphics & Media Lab (Video Group)
- 56. Only for Сравнение Maxus Оригинал 56 CS MSU Graphics & Media Lab (Video Group)
- 57. Only for Сравнение Maxus Ground truth 57 CS MSU Graphics & Media Lab (Video Group)
- 58. Only for Сравнение Maxus Connectivity-slant 58 CS MSU Graphics & Media Lab (Video Group)
- 59. Only for Сравнение Maxus AdaptingBP 59 CS MSU Graphics & Media Lab (Video Group)
- 60. Only for Сравнение Maxus CoopRegion 60 CS MSU Graphics & Media Lab (Video Group)
- 61. Only for Сравнение Maxus Ground truth 61 CS MSU Graphics & Media Lab (Video Group)
- 62. Only for Сравнение Maxus Ошибка Алгоритм Время работы Tsukuba Venus Teddy Cones Среднее 14–25 с (осн. – AdaptingBP 1.11 0.10 4.22 2.48 4.23 сегментация) 20 с (8 с – CoopRegion 0.87 0.11 5.16 2.79 4.41 сегментация) DoubleBP 0.88 0.13 3.53 2.90 4.19 GC+occ 1.19 1.64 11.2 5.36 8.26 Connectivity- 1.77 3.00 - - - 5с slant http://vision.middlebury.edu/stereo/eval/ 62 CS MSU Graphics & Media Lab (Video Group)
- 63. Only for Maxus Список литературы Z. Wang, Z. Zheng. A Region Based Stereo Matching Algorithm Using Cooperative Optimization. CVPR 2008. A. S. Ogale, Y. Aloimonos. Shape and the stereo correspondence problem. International Journal of Computer Vision, vol. 65, no. 3, 147-162, 2005. D. Scharstein and R. Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision, 2002. A. Klaus, M. Sormann and K. Karner. Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure. ICPR 2006. C.Yang et al. Mean-shift analysis using quasi-newton methods. ICIP 2003. Scharstein and Szeliski. Middlebury Stereo Evaluation. http://vision.middlebury.edu/stereo/eval/ 63 CS MSU Graphics & Media Lab (Video Group)
- 64. Only for Maxus Вопросы ? 64 CS MSU Graphics & Media Lab (Video Group)