What is your algorithm exactly? Are you following a particular paper? This processor supports OpenCL so to get maximum performance, you should choose algorithms that have a good way to parallelize on GPU (which deque cannot because of the dependancy on the processing order).

STL deque may involve new/delete operations which may be costy. If the deque is fixed-size, use an array and variables pointing to the first/last element. Inc/dec the first/last index when popping/pushing elements, and handle the wrap-around.

• @Bruno Martin,I am using a simple correlation SAD algorithm with a maximum correlation window of size 7x7, I got the idea of my implementation from this paper

  Conference Paper FPGA based memory efficient high resolution stereo vision sy...

  So I am trying to eliminate redundant computation in one row using 1D Box filtering algorithm. I used the deque because of its efficiency in insertion and deletion from both ends (push_back and pop_front).
• For the openCL, I don't know anything about that language, so it's not an option for me

Dirk Frommholz your idea is intersting, but If I use it I need a very large array to process on row of the image. Besides that I am using a vector of deques to constrcut a matrix so I should have 20 arrays of large size which is unaffordable. The other way is to use a small fixed size and keep shifting the array to the left with each new value inserted however the time complexity here is huge (n2) . and the deque will be more preferable in this scenario, I will perform other tests on different data structures and find the best one.

Seems you're trying to implement SAD matching using the "moving average" technique. Are you sure you need the deque at all ?

I would store the stereo bitmaps as a contiguous array, then compute the initial SAD value using the 7x7 window. When you shift the window horizontally, subtract the SAD values of the last window column and add the SAD values of the new column. When you shift the window vertically, same procedure but with the SAD values of the respective top and bottom rows. No need for a deque, all can be done with pointer arithmetics, and if you want to optimize the SAD calculation, try the ARM NEON intrinsics.

However, you'll have to keep at least the SADs per pixel per disparity per epipolar line/image row and find the minimum disparity later. This will consume some memory. Computational complexity for SAD-MA matching for the entire image should be O(w*h*d) with d being the maximum disparity range.

Dirk Frommholz , Thank you very much, you have been very helpful. I tired the method you are referring to for the horizontal displacement, the problem with this approach and used vector to store the SAD results for the first column over the whole disparity range and the results were not good. Actually, I am trying to implement my algorithm so that I can make calculation of several rows in parallel. Also I am using the opencv "at" method to access pixels and have read that this method is the slowest but since I am using a sliding window I can't find a better alternative

You must take care at the borders of course, for instance by periodizing the image or simply starting inside the image. Also, SAD correlation is not really high-quality but quite fast. I once implemented SAD-MA myself, and it worked with identical results to the classic SAD matcher.

The "moving average" approach can be easily multithreaded, i.e. perform the horizontal shift with k threads on k rows, but you'll have to initialize the k SAD values at the start of each row from a full 7x7 SAD calculation. Also, you'll need a disparity buffer of k*w*d pixels for subsequently finding the minimum disparity.

The opencv at() function probably does range checks and hence will be slow. Also, accessing pixels of a contiguous image array relative to the current position using pointer increments/decrements/adds/subtracts will greatly improve the speed compared to the full computation of the pixel address (i.e. y*width+x). Accessing a 2D STL construct (vector of vectors, or vector of deques) for the image will always be slower than pointer arithmetics, probably by a magnitude (10x).

Dirk Frommholz , on which you implemented the SAD-Ma before ? and what was was the performance ? In the last part of your answer, if I treat the whole image a contiguous storage who can I construct the moving window ?

I implemented the moving average-style SAD on some AMD K10 CPU (x64) as a proof of concept, so performance was some seconds for a 2MPix image as far as I can remember for 64 disparities or so. I didn't do pointer arithmetics nor multithreading though.

Nowadays at DLR we do semi-global matching with disparity gating at ~1MPix/s on an i7 w/ 8 cores which provides a much better quality :-) I also own an 1.8 Ghz Odroid-U3 privately, but can't remember the performance on this quadcore board anymore. It was far below the i7 values since I didn't use SSE4/AVX/AVX2 intrinsics but pure C++ (~50 kilopixel disparities per second?).

If you have a contiguous image array you can do SAD-MA with pointer arithmetics instead of getPixel()-like functions. You don't have to construct the window explicitly since you just need to compute and update the SAD value for each x;y;disparity using the moving average scheme.

Dirk Frommholz I assume that you're refering to the first method in this tutorial https://docs.opencv.org/2.4/doc/tutorials/core/how_to_scan_images/how_to_scan_images.html. If I treat the image as a contiguous storage than iI can assume that the image is a long vector of size w*h so to access different pixels in one window I need to index them like this p[i*w+j] will this scheme produce a better results then using at(i,j). Or you suggesting another way, because I'm not really following here

Probably not. I just had a brief look into the opencv docs which state that at() will use range checks only for debugging and probably is implemented as p[i*w+j], that is, you'll do a full address calculation every time you access a pixel. This is not necessary for neighboring pixels where you can do a simple ++p or p+=width to access the next horizontal or next vertical pixel when reading the elements under the filter mask for grayscale images saving you the multiplication.

ARM architecture also has some nice SAD intrinsics which require pointers as the input, so for maximum performance you will probably have to work on the raw data anyway. See https://stackoverflow.com/questions/39569591/arm-neon-8x8-sad-operation for the 8x8 SAD calculation with pointer arithmetics/NEON for an example.

Dirk Frommholz still confusing, lets assume that we have 7x7 window and and our pointer p is at the center of the window. How can you for example scan the pixels of the window starting from the pixel at the upper left corner of the correlation window ?

You place p at the top left pixel of the mask and do the SAD calculation using pointer arithmetics or NEON. Then you write the result to the pixel under the mask center, for which you can use another pointer q initially set to the that position (q=p+4+4*width=p+4+(width

Okay I get the idea now, it means when I scan the image and reach to the pixel pointed by p I start the SAD computation, however when I jump from one line in the mask I need to find *(p+j+w*i). i and j, range from 0 to mask_widht-1. and for the central pixel in my example it should be q = p+3+3*width = p+3+(width

The other solution I can think of is to add the SAD of 49 elements in one operation this is to be done at least for the first processed pixel in each row of the image, this will make the code very long an inflexible, and It's the only way I can see to avoid multiplication when using pointer arithmetic.

You can entirely avoid multiplications. Only additions are needed to switch to the next pixel/row in a grayscale image relatively to the current position using pointer arithmetics. This is because the next pixel is p+1 and the next row is p+width. You can put this in your 7x7 loop, and no multiplications will occur.

I think I get it now, in each iteration, I either add 1 or width image depending on the level of the loop. I will try it, though I still have one issue to deal with, I'm excluding the pixels at the border of the image from processing so I think I need two other pointers one to point to the last pixel to be processed in each row to be updated when I jump to process one row, and another pointer to point to the last pixel that will be processed, like this I won't have to use any loop except for the one to traverse the image as a 1D vector, I will try it and see the improvement. Another question, will using the pointer arithmetic here make it easier to use neon intrinsic because honestly I don't know anything about them

The NEON intrinsics (as well as the SSE2/3/4/AVX intrinsics) take pointers as arguments for the respective load/store functions, so you can directly load a set of consecutive pixels into the vector registers and run the SIMD operation.

Concerning the border problem with pointer arithmetics, you can consider mirroring (recommended) or a wrap-around at the first/last pixel horizontally and vertically. This will cost you some additional arithmetics, but allows to process the entire image. Alternatively, you can extend the image accordingly when you load it or grab it from the camera, i.e. embed the pixels into a larger bitmap and repeat the border pixels.

You may wanna do this anyway since, to my knowledge, the NEON instructions will require aligned pointers, i.e. the address stored by the pointer probably must be a multiple of 8 or you'll receive an alignment exception.

Okay I have finished my algorithm, after accelerating it I got a processing speed of around 15 fps for SAD matching. (images of size 320x240 with disparity range of 20), I am not sure wether this is a good performance or not, I really found few works only in the literature that uses CPU as implementation platform to achieve real time. The parallelization is done using four CPUS.