# PyrSGM sgm金字塔优化

**Repository Path**: WN90/pyrsgm-sgm-pyramid-optimization

## Basic Information

- **Project Name**: PyrSGM sgm金字塔优化
- **Description**: 优化版sgm，纯cpu单核单线程版本，支持全范围视差估计，通过金字塔缩放在小尺度估计深度，然后再在大尺度上微调，通过topn模型计算代价，极大的降低了内存的使用，提升了速度。可以在无GPU的低计算能力的嵌入式设备上使用。
- **Primary Language**: C++
- **License**: BSD-3-Clause
- **Default Branch**: master
- **Homepage**: https://blog.csdn.net/weixin_39266208/article/details/122021884
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 1
- **Created**: 2021-12-19
- **Last Updated**: 2023-03-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# pysgm sgm金字塔优化

#### 最终发现
x86_64视差范围小的时候没有opoencv的快，这个是个人玩具，练习和研究的产物。

#### 介绍
优化版sgm，纯cpu单核单线程版本，支持全范围视差估计，通过金字塔缩放在小尺度估计深度，然后再在大尺度上微调，通过topn模型计算代价，极大的降低了内存的使用，提升了速度。 **可以在无GPU的低计算能力的嵌入式设备上使用** 。

对于1836x954的测试图片，占用内存仅366M(代码中使用的是top8，top的个数越多占内存也越多，和视差范围无关)，而为采用topn优化的SGM，在0-170视差占用内存3.3G，0-1000视差占用内存19G+。计算速度稳定，根据视差范围，图片大小，参数和配置以及代价的计算方式等不同会有波动，两个1836x954的图片全范围视差估计最快可能1-2s左右(AMD Ryzen7 5700g)，而未优化版本代价聚合的时间和视差平方成正比，可能慢十几倍，甚至几百倍以上。

无论内存(精简掉不用的图像通道和代价计算方式，降低topn数量等)，还是计算速度(并行优化)，都可以进一步再提升，但是要和结果质量一起权衡考虑。

仅仅在linux中测试过，由于使用了gnu的扩展，只支持gcc或clang，其他编译器如果不支持gnu扩展可能要修改代码才能编译通过。
依赖 opencv(读取和保存图片和后处理)， gnu++14标准(gcc,clang支持)


#### 软件架构


这里使用的算法以SGM的聚合算法为基础，通过金字塔模型进行全范围视差提速，缩放采用了一种每个像素均等贡献的方式，缩放kernel如下

```
0 1 1 0
1 2 2 1
1 2 2 1
0 1 1 0
```

其中step为2，假设缩放前高度H，缩放后高度h，则h = (H-4)/2 + 1，如果H-4不能被2整除，上侧跳过一个，宽度类似。一共有12个点对缩放之后的一个点做贡献，不考虑边界，每一个点对三个缩放之后的点做贡献。

lower层计算完视差向上传播到邻近upper层，upper层视差搜索范围为lower层估计的视差附近，对于lower层估计无效的情况，使用如下方式估计

```
dr-(xr-x) <= d <= dl+(x-xl)
```
其中d为当前点视差，x为当前点横向坐标，xl,xr为当前点左右的 **正确匹配** 的点的横向坐标，dl,dr为正确匹配的点的视差，为了增加找到正确匹配的点的概率，采用了固定间隔多次搜索的方式。


代价计算保存最小的n个，使用大顶堆结构，通过堆顶排除代价大的结果。


代码中默认使用的是YCrCb颜色空间或只有grayscale的但通道图像，而不是BGR，但可以修改。



#### 编译和使用


```
mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release

#如果使用clangd等来看代码，可能需要生成compile_commands.json，添加-DCMAKE_EXPORT_COMPILE_COMMANDS=1
#cmake .. -DCMAKE_BUILD_TYPE=Release -DCMAKE_EXPORT_COMPILE_COMMANDS=1

make
# 测试，结果保存在/tmp/result.bmp
./pyrstereo ../data/*.png
#可选视差搜索范围，提高精度和速度
./pyrstereo ../data/*.png 0 170
```

#### 相关资料和引用


SGM算法
> H. Hirschmuller, "Stereo Processing by Semiglobal Matching and Mutual Information," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30, no. 2, pp. 328-341, Feb. 2008, doi: 10.1109/TPAMI.2007.1166.


一个使用金字塔优化改进的SGM
> Rothermel, Mathias & Wenzel, Konrad & Fritsch, Dieter & Haala, Norbert. (2012). SURE: Photogrammetric Surface Reconstruction From Imagery. 

Census扩展
> Stein, Fridtjof. (2004). Efficient Computation of Optical Flow Using the Census Transform. DAGM-Symposium. 3175. 79-86. 10.1007/978-3-540-28649-3_10. 

一个基于深度学习的，采用了金字塔思想的双目深度估计算法
> Y. Wang et al., "Anytime Stereo Image Depth Estimation on Mobile Devices," 2019 International Conference on Robotics and Automation (ICRA), 2019, pp. 5893-5900, doi: 10.1109/ICRA.2019.8794003.

Middleburry数据集
> D. Scharstein, H. Hirschmüller, Y. Kitajima, G. Krathwohl, N. Nesic, X. Wang, and P. Westling. High-resolution stereo datasets with subpixel-accurate ground truth.
> In German Conference on Pattern Recognition (GCPR 2014), Münster, Germany, September 2014. 

EthanLi的SGM教学及代码
> https://ethanli.blog.csdn.net/
> https://github.com/ethan-li-coding/SemiGlobalMatching



感谢SGM作者带来这么好的聚合方式，和EthanLi博客的详细讲解，感谢Middleburry数据集作者提供的高清的带有groundtruth的立体图片。