Introduction Guide to stereo vision (7): stereo matching

About stereo matching , I have written many blogs before , There is no need to write repeatedly , For learning friends, please read the following link .

In this paper, we talk about the methodology of stereo matching and weak texture restoration .

Stereo matching series

0

Detailed explanation of binocular stereo matching steps

1 SGM series

Theory constant Talk Series

【 Constant theory 】【 Stereo matching series 】 classic SGM：（1） Mutual information of matching cost calculation （MI）
【 Constant theory 】【 Stereo matching series 】 classic SGM：（2） Calculation of matching cost Census Transformation
【 Constant theory 】【 Stereo matching series 】 classic SGM：（3） Cost aggregation （Cost Aggregation）
【 Constant theory 】【 Stereo matching series 】 classic SGM：（4） Parallax calculation 、 Parallax optimization

Code combat series

【 Code on the actual battle 】【 Stereo matching series 】 classic SGM：（1） Framework and class design
【 Code on the actual battle 】【 Stereo matching series 】 classic SGM：（2） Cost calculation
【 Code on the actual battle 】【 Stereo matching series 】 classic SGM：（3） Cost aggregation
【 Code on the actual battle 】【 Stereo matching series 】 classic SGM：（4） Cost aggregation 2
【 Code on the actual battle 】【 Stereo matching series 】 classic SGM：（5） Parallax optimization
【 Code on the actual battle 】【 Stereo matching series 】 classic SGM：（6） Parallax filling
【 Code on the actual battle 】【 Stereo matching series 】 classic SGM：（7） Weak texture Optimization

2 PatchMatch series

Theory constant Talk Series

【 Constant theory 】【 Stereo matching series 】 classic PatchMatch: （1）Slanted support windows Inclined support window model
【 Constant theory 】【 Stereo matching series 】 classic PatchMatch: （2） be based on PatchMatch Parallax estimation
【 Constant theory 】【 Stereo matching series 】 classic PatchMatch: （3） post-processing （ Consistency check and parallax filling ）

Code combat series

【 Code on the actual battle 】【 Stereo matching series 】 classic PatchMatch: （1） frame
【 Code on the actual battle 】【 Stereo matching series 】 classic PatchMatch: （2） The main class
【 Code on the actual battle 】【 Stereo matching series 】 classic PatchMatch: （3） Random initialization
【 Code on the actual battle 】【 Stereo matching series 】 classic PatchMatch: （4） Cost calculation
【 Code on the actual battle 】【 Stereo matching series 】 classic PatchMatch: （5） Iterative propagation
【 Code on the actual battle 】【 Stereo matching series 】 classic PatchMatch: （6） post-processing

3 AD-Census series

Theory constant Talk Series

【 Constant theory 】【 Stereo matching series 】 classic AD-Census: （1） Cost calculation
【 Constant theory 】【 Stereo matching series 】 classic AD-Census: （2） Cross domain cost aggregation （Cross-based Cost Aggregation）
【 Constant theory 】【 Stereo matching series 】 classic AD-Census: （3） Scan line optimization （Scanline Optimization）
【 Constant theory 】【 Stereo matching series 】 classic AD-Census: （4） Multistep parallax optimization

Code combat series

【 Code on the actual battle 】【 Stereo matching series 】 classic AD-Census: （1） frame
【 Code on the actual battle 】【 Stereo matching series 】 classic AD-Census: （2） The main class
【 Code on the actual battle 】【 Stereo matching series 】 classic AD-Census: （3） Cost calculation
【 Code on the actual battle 】【 Stereo matching series 】 classic AD-Census: （4） Cross domain cost aggregation
【 Code on the actual battle 】【 Stereo matching series 】 classic AD-Census: （5） Scan line optimization
【 Code on the actual battle 】【 Stereo matching series 】 classic AD-Census: （6） Multistep parallax optimization

If you can learn to SGM and PatchMatch, Then you will be completely introduced to stereo matching .

About methodology

What we really need to learn is the methodology of stereo matching , from SGM Algorithm , You can learn how Markov random fields are applied to stereo matching , Then you can go deep into the classic theory of Markov random field , It is widely used in 3D reconstruction , You will see it in different places , In short , Most label assignment problems can be modeled by Markov random fields , And solve the energy optimization problem of Markov random field , They all use efficient approximation methods , such as SGM Scan line optimization (Scanline Optimize)、 Dynamic programming (Dynamic Programming)、 belief propagation （Belief Propagation）、 Cooperative optimization （Cooperative Optimization） etc. .

We will find that , Whether in scientific research or engineering practice , Modeling is important and critical , When you find that stereo matching problem can be transformed into label assignment problem, you quickly think of Markov random field modeling , Then try to solve the problem with one of many mature optimization algorithms . Most papers are produced in this way , The breakthrough of research progress is at the moment when you transform the problem , Of course, the premise is that you have to master a certain number of algorithm models , This is one of the basic knowledge you should master .

And from PatchMatch Algorithm , and SGM In contrast, we can clearly perceive , The label allocation method based on discrete space does not seem to be the optimal solution of stereo matching problem , The parallax plane method based on continuous space , It has obvious advantages in accuracy and effect . Especially in the restoration of boundaries and fine structures , The inaccuracy of discrete space and SGM The cost aggregation model of does not deal with the boundary clearly （ Or not exactly ）, bring SGM and PatchMatch The gap is clear , Here is an example ：

Original picture

SGM

PatchMatch

Boundary restoration problem , It can't be said to be the problem of discrete space , Now the deep neural network , In essence, it is also a label allocation method in discrete space , But it raises the effect to another level , The boundary recovery is also better than the traditional label allocation method , But in terms of the accuracy of the final point cloud , contrast PatchMatch Did not show an advantage , If the depth neural network can beat the traditional geometric algorithm in accuracy , That can be regarded as an all-round subversion , But this is not impossible , Because the traditional algorithm known at present is not in the best state , Even if the geometric accuracy is the best at present PatchMatch There is also precision resolution , Finally, when the parallax is refined, it still falls into the discrete space , So it is possible that it will be surpassed by the deep learning network in the future .

I think the theoretical view is , If deep learning and traditional geometry receive the same attention and research , Then the accuracy of the results of traditional geometric algorithms will continue to show advantages , The integrity and accuracy of the results of deep learning also make it difficult for traditional geometric algorithms to match . But the reality is , Deep learning has far more attention and research than traditional geometric algorithms , To some extent, this leads to a gap between in-depth learning and some precision oriented industrial practices , So you can see , In the field of precise measurement where accuracy is extremely important , For example, industrial measurement 、 Mapping 、 Positioning grab, etc , Deep learning is rarely used , Instead, structured light reconstruction technology with simple principle and high accuracy is popular .

In some applications that do not excessively pursue high precision , For example, depth acquisition in autonomous driving , It is not necessary that the accuracy of each point is very high , Integrity is more important , After all, is there anything in front of the car , And whether the distance from the car is accurate enough , Obviously, the former is more important ; Another example is the current popular depth camera , Although most of them are traditional algorithms , But in fact, in many cases, it does not need very high accuracy , The reason why most traditional algorithms are used is the low computational power of traditional algorithms , If the requirement of deep learning computing power decreases , Or the computing power of the chip is enhanced , Then deep learning will become mainstream .

On the problem of weak texture restoration

Weak texture restoration is a chronic problem in stereo matching , Radiation difference is crucial for all stereo matching , This is the most critical information to distinguish whether the two points are the same . But the radiation difference of weak texture is very small and the radiation value is highly similar , This brings great difficulties to the stereo matching method based on local window .

The weak texture restoration method I know so far , Generally speaking, there are two kinds , One is clustering segmentation 、 One is multiscale estimation .

The assumption of clustering segmentation method is that a local weak texture region with similar color is likely to belong to the same continuous surface , Usually this surface is assumed to be a plane , Under this assumption, there are two specific ideas to complete optimization ：
1、 Complete disparity estimation for all pixels first , Clustering and segmentation of pixels , For pixels that failed to recover , Use other effective parallax in the same block for plane fitting , The fitting equation can be used to fill in the missing pixel .
2、 First, cluster and segment the pixels , Then stereo matching is carried out based on the scale after clustering , Then map the matching results to the fine-grained pixel scale .
This kind of method is rarely used in practice , Because its assumption seems obviously flawed , Clustering segmentation itself has the problems of over segmentation and under segmentation, which are difficult to solve , And it is not uncommon for the foreground and background colors to be similar , This makes the problem more difficult .

I want to talk more about another kind of method ： Multiscale estimation method . Scale is a very important factor in our human perception , If you put a pure white wall in front of you very close , You must be confused , I don't know what this is , And your sense of distance will be very weak , I can't feel how far this thing is from your eyes . And when the distance slowly widens , You gradually see the information around the wall and infer that it is a wall , And the sense of distance will become clearer . The size of the scale determines the range of information we can receive in a limited field of vision , Obviously, the larger the scope of information is, the better our identification and positioning , But we should also realize that the larger the information range, the weaker the information clarity under the unit element size , The two must be contradictory .

Back to stereo matching , Obviously, we can't rely on one pixel information alone to complete the pairing of left and right pixels , Local information around pixels is necessary , But the premise is that the local window has enough information entropy , In the last example , In the process of getting farther , Before you see the outline of the white wall , You still can't recognize it , So for weak textures , The need to expand the scope of local information is particularly prominent , We recognize that the range of surrounding information is very important for the ability to identify and locate , So we want a larger window to receive a wider range of information , Therefore, increasing the window size is often helpful for the optimization of weak texture .

But increasing the size of the window often leads to an increase of several times the amount of calculation , So actually, it is more practical to reduce the image resolution , Generate multi-scale images with multiple resolutions , Get better results for weak textures on low resolution scales and project them on high resolution scales .

I have done a group of comparative experiments here to verify the multi-scale SGM Effect of algorithm ：

Original picture

Original image matching

1/2 Graph matching

1/4 Graph matching

As the image resolution scale becomes smaller , The parallax on the wall is becoming more and more complete . This is an evidence that multi-scale matching is helpful to restore weak textures .

OK, that's all for this article , Update after half a year , I hope I can help you , bye ！