OpenCV Q&A Forum - RSS feedhttp://answers.opencv.org/questions/OpenCV answersenCopyright <a href="http://www.opencv.org">OpenCV foundation</a>, 2012-2018.Thu, 19 Jul 2018 17:32:29 -0500Understanding OpenCV Stereobm implementationhttp://answers.opencv.org/question/195443/understanding-opencv-stereobm-implementation/ Hello all,
I'm trying to understand the StereoBM implementation in CPU and GPU.
I started with the CPU on https://github.com/opencv/opencv/blob/master/modules/calib3d/src/stereobm.cpp.
I have some **basic knowledge on how a Stereo Block Matching works**.
I was **able to get into the flow** but **had some hiccups** when hit the *line 1204* which initialized an integer *bufSize0* which then added with further values in the upcoming lines.
int bufSize0 = (int)((ndisp + 2)*sizeof(int));
bufSize0 += (int)((height+wsz+2)*ndisp*sizeof(int));
bufSize0 += (int)((height + wsz + 2)*sizeof(int));
bufSize0 += (int)((height+wsz+2)*ndisp*(wsz+2)*sizeof(uchar) + 256);
It would be great if someone can help me out in understanding in **what basis these buffer size calculations are done and what it is used for**.Tue, 10 Jul 2018 14:05:26 -0500http://answers.opencv.org/question/195443/understanding-opencv-stereobm-implementation/Answer by opalmirror for <p>Hello all,</p>
<p>I'm trying to understand the StereoBM implementation in CPU and GPU. <br>I started with the CPU on <a href="https://github.com/opencv/opencv/blob/master/modules/calib3d/src/stereobm.cpp">https://github.com/opencv/opencv/blob...</a>.</p>
<p>I have some <strong>basic knowledge on how a Stereo Block Matching works</strong>.</p>
<p>I was <strong>able to get into the flow</strong> but <strong>had some hiccups</strong> when hit the <em>line 1204</em> which initialized an integer <em>bufSize0</em> which then added with further values in the upcoming lines.</p>
<pre><code> int bufSize0 = (int)((ndisp + 2)*sizeof(int));
bufSize0 += (int)((height+wsz+2)*ndisp*sizeof(int));
bufSize0 += (int)((height + wsz + 2)*sizeof(int));
bufSize0 += (int)((height+wsz+2)*ndisp*(wsz+2)*sizeof(uchar) + 256);
</code></pre>
<p>It would be great if someone can help me out in understanding in <strong>what basis these buffer size calculations are done and what it is used for</strong>.</p>
http://answers.opencv.org/question/195443/understanding-opencv-stereobm-implementation/?answer=195923#post-id-195923I've struggled through this StereoBM code too, and while I did not come to complete enlightenment, I came to an understanding. The data structure dynamically allocated and here indexed by bufSize0, is a cache of intermediate results that allows optimizing the algorithm for a much faster calculation.
The basic StereoBM algorithm is relatively easy to comprehend, but the algorithm scales as a product of dimensions, roughly O(cols * rows * disparity_range * windowsize * windowsize). You could write a simple, straightforward algorithm to do this, and it would be correct, but it would be slow.
But, if you can use a memory buffer (appropriately sized and dimensioned based on above parameters) to cache already calculated results, then you can save a lot of time by not recalculating block match scores exhaustively.
The first optimization is to realize that many of the addressed block matches at a given column, row, disparity offset, window offset (dx, dy), are exactly the same as a previously calculated block match score result . So, cache those intermediate results and reuse them without recalculating them.
The second optimization is to realize that if you've simply moved one row or column beyond a previously calculated block, since the block match score is a sum of absolute differences, you can start with the prior similar block match result, subtract the score result of the the row or column you are leaving behind, and add the score result from the row or column you are moving toward.
The details of the indexed data structure are complicated, and its addressing is complicated, but it is performing the above sorts of optimizations to store and reuse intermediate results, to vastly reduce the amount of time to exhaustively recalculate every block match score pixel by pixel.Wed, 18 Jul 2018 14:32:20 -0500http://answers.opencv.org/question/195443/understanding-opencv-stereobm-implementation/?answer=195923#post-id-195923Comment by opalmirror for <p>I've struggled through this StereoBM code too, and while I did not come to complete enlightenment, I came to an understanding. The data structure dynamically allocated and here indexed by bufSize0, is a cache of intermediate results that allows optimizing the algorithm for a much faster calculation.</p>
<p>The basic StereoBM algorithm is relatively easy to comprehend, but the algorithm scales as a product of dimensions, roughly O(cols * rows * disparity_range * windowsize * windowsize). You could write a simple, straightforward algorithm to do this, and it would be correct, but it would be slow.</p>
<p>But, if you can use a memory buffer (appropriately sized and dimensioned based on above parameters) to cache already calculated results, then you can save a lot of time by not recalculating block match scores exhaustively.</p>
<p>The first optimization is to realize that many of the addressed block matches at a given column, row, disparity offset, window offset (dx, dy), are exactly the same as a previously calculated block match score result . So, cache those intermediate results and reuse them without recalculating them.</p>
<p>The second optimization is to realize that if you've simply moved one row or column beyond a previously calculated block, since the block match score is a sum of absolute differences, you can start with the prior similar block match result, subtract the score result of the the row or column you are leaving behind, and add the score result from the row or column you are moving toward.</p>
<p>The details of the indexed data structure are complicated, and its addressing is complicated, but it is performing the above sorts of optimizations to store and reuse intermediate results, to vastly reduce the amount of time to exhaustively recalculate every block match score pixel by pixel.</p>
http://answers.opencv.org/question/195443/understanding-opencv-stereobm-implementation/?comment=195986#post-id-195986As I understand it:
- mind is the minimum disparity. It is also the index into sad[] with the least difference value.
- the 1st two assignments ensure that sad[-1] and sad[ndisp] have actual values in them not smaller than sad[mind].
- The p, n, d trick seems to determine whether mind is at the left or right edge of a block of minimum disparity and needs to be smoothed.
- d is zero if sad[mind-1] and sad[mind+1] are the same as sad[mind], positive otherwise.
- dptr[] is always an array of int16_t (definition of stereoBM disparity array). Units of disparity are scaled by a factor of 16.
- dptr[y*dstep] assigns the disparity value for this cell. it is max possible disparity less mind, smoothed if d shows mind at an edge, rounded up, scaled by 16.
- costptr optimizes next passThu, 19 Jul 2018 17:32:29 -0500http://answers.opencv.org/question/195443/understanding-opencv-stereobm-implementation/?comment=195986#post-id-195986Comment by mohanen for <p>I've struggled through this StereoBM code too, and while I did not come to complete enlightenment, I came to an understanding. The data structure dynamically allocated and here indexed by bufSize0, is a cache of intermediate results that allows optimizing the algorithm for a much faster calculation.</p>
<p>The basic StereoBM algorithm is relatively easy to comprehend, but the algorithm scales as a product of dimensions, roughly O(cols * rows * disparity_range * windowsize * windowsize). You could write a simple, straightforward algorithm to do this, and it would be correct, but it would be slow.</p>
<p>But, if you can use a memory buffer (appropriately sized and dimensioned based on above parameters) to cache already calculated results, then you can save a lot of time by not recalculating block match scores exhaustively.</p>
<p>The first optimization is to realize that many of the addressed block matches at a given column, row, disparity offset, window offset (dx, dy), are exactly the same as a previously calculated block match score result . So, cache those intermediate results and reuse them without recalculating them.</p>
<p>The second optimization is to realize that if you've simply moved one row or column beyond a previously calculated block, since the block match score is a sum of absolute differences, you can start with the prior similar block match result, subtract the score result of the the row or column you are leaving behind, and add the score result from the row or column you are moving toward.</p>
<p>The details of the indexed data structure are complicated, and its addressing is complicated, but it is performing the above sorts of optimizations to store and reuse intermediate results, to vastly reduce the amount of time to exhaustively recalculate every block match score pixel by pixel.</p>
http://answers.opencv.org/question/195443/understanding-opencv-stereobm-implementation/?comment=195930#post-id-195930Hey @opalmirror, Thanks for your answer, I Gone through the code completely now how an idea of how its implemented here, but am stuck at the last disparity calculation
sad[-1] = sad[1];
sad[ndisp] = sad[ndisp-2];
int p = sad[mind+1], n = sad[mind-1];
d = p + n - 2*sad[mind] + std::abs(p - n);
dptr[y*dstep] = (short)(((ndisp - mind - 1 + mindisp)*256 + (d != 0 ? (p-n)*256/d : 0) + 15) >> 4);
costptr[y*coststep] = sad[mind];
As far as I can understand is that the mind is the actual disparity value for the pixel, then what is this calculation is about and why it has to be a 16bit fixed point valueThu, 19 Jul 2018 00:16:43 -0500http://answers.opencv.org/question/195443/understanding-opencv-stereobm-implementation/?comment=195930#post-id-195930