关于算法速度问题解答

[ethan-li-coding]

PatchMatch速度是比较慢的。确保你的运行环境是Release模式，若为Debug模式则会非常慢，对代码里带的示例数据，Release模式可以在几分钟至十几分钟跑出结果。
此外，如果你设置为前端平行窗口模式，则速度会加快很多，这样设置：
pms_option.is_fource_fpw = true

[Diksha-Moolchandani]

Why is patch match slower than others? Is it inherently supposed to be slow or it is due to some data structures?

[ethan-li-coding]

Why is patch match slower than others? Is it inherently supposed to be slow or it is due to some data structures?

Inherently. The main bottleneck of algorithm speed is plane optimization step, which can be ignored when frontal parallel windows mode is selected.

[Diksha-Moolchandani]

But if that step is ignored, can it be called patchmatch algorithm? It would be modified version of patchmatch then.

[ethan-li-coding]

But if that step is ignored, can it be called patchmatch algorithm? It would be modified version of patchmatch then.

yep, you are right.

[Diksha-Moolchandani]

Thanks

[ethan-li-coding]

Thanks

Happy to help

[Diksha-Moolchandani]

How should I check if the operating environment is in Release mode?
I have already done this step: pms_option.is_fource_fpw = true

I am running it in linux from command line as a cpp code. I am not using visual studio.

[ethan-li-coding]

add -O2 when compiling

[Diksha-Moolchandani]

Thanks. I was using -O3 while compiling.

[ethan-li-coding]

-O3 is already in release mode Diksha Moolchandani <[email protected]> 于2020年12月11日周五 下午1:47写道：

…

I had used -O3 while compiling. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#3 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AO55OWCJGCBJSVBU2YSTDVLSUGW75ANCNFSM4PJ7FRFQ> .

[lingkang]

不知道作者还看不看这个issue了，我觉得好像是代码中实现plane refinement的过程有点小问题，在论文中2.2节作者提到

The idea is to allow large changes in the first iterations, which makes sense if the current plane is completely wrong. In later iterations, we sample planes that are very close to our current one, which allows capturing disparity details, e.g., at rounded surfaces.

也就是说，在后面的迭代中，视图优化部分使用的步长可以更小一些，隐含的意思应该是指每次迭代只做一次视图优化（步长随着迭代次数指数下降）。
但是在现在的实现中，每一次迭代都从最大步长走到了最小步长走了一遍，这应该是算法比较慢的主要原因，实际上迭代后期，每次还随机一个很大的步长都是无用的，基本不可能得到一个更好的cost，实际上也就disp_update、norm_update最后的几次可能有作用。
也就是说在PlaneRefine函数中，while (disp_update > stop_thres) 这个while循环本质上应该是和外层iteration是一个层级的，这样相当于整体提高了一个数量级的时间复杂度。
同时因为在外层设置了 fronto-parallel 模式不进行plane refinement 所以 fronto-parallel 要快很多。

[ethan-li-coding]

代码里的disp_update每次循环完是更新为上一次的1/2的，是指数减小的。

[lingkang]

代码里的disp_update每次循环完是更新为上一次的1/2的，是指数减小的。

指数减小是对的，我的意思是 DoPropagation()中的 PlaneRefine() 函数应该放到这边的for循环里，和其他Propagation应该是同级的
`
// 迭代传播
for (int k = 0; k < option_.num_iters; k++) {

propa_left.DoPropagation();
propa_left.planerefine();
propa_right.DoPropagation();
propa_right.planerefine();
}
`
这样对于planeRefine()来说，运行次数就会少很多，当然这也会要求iteration次数变多

按照作者的意思应该是这样的，现在的实现可以保证有很好的结果，但是感觉速度上牺牲比较多

[Diksha-Moolchandani]

Hi @lingkang ,

Did you calculate the accuracy of this algorithm? I am getting a 14-15% error rate on the KITTI dataset. Can you confirm?

[ethan-li-coding]

代码里的disp_update每次循环完是更新为上一次的1/2的，是指数减小的。

指数减小是对的，我的意思是 DoPropagation()中的 PlaneRefine() 函数应该放到这边的for循环里，和其他Propagation应该是同级的
`
// 迭代传播
for (int k = 0; k < option_.num_iters; k++) {

propa_left.DoPropagation();
propa_left.planerefine();
propa_right.DoPropagation();
propa_right.planerefine();
}
`
这样对于planeRefine()来说，运行次数就会少很多，当然这也会要求iteration次数变多

按照作者的意思应该是这样的，现在的实现可以保证有很好的结果，但是感觉速度上牺牲比较多

我觉得不是这样，
（1）“iteration次数变多”，原文中明确提及到迭代次数是3次：“In our experiment, we run three iterations.“ 这个次数是无法满足你设定的这个迭代逻辑的。 即便原文是想让Plane Refine单独设置迭代次数，那么他也应该在论文中提及这个迭代次数的设置。
（2）你贴的原文中有一句话：“The idea is to allow large changes in the first iterations, which makes sense if the current plane is completely wrong”，这个是说为什么一开始要设置一个较大的调整范围，即maxdisp/2，是为了校正那些完全错误的平面，这是合理的，而即使经过了多次迭代也不能避免有些像素存在完全错误的平面，所以每次迭代最大调整范围都是使用的maxdisp/2也合理。