An explicit growth model of the stereo region growing algorithm for parallel processing

GOTCHA is a well-tried and tested stereo region growing algorithm, which iteratively applies Adaptive Least Square Correlation (ALSC) matching to the adjacent neighbours of a seed point in order to achieve a dense reconstruction with sub-pixel precision. It is, however, a computationally expensive algorithm as every seed point collected by the ALSC matching produces quadrants or octants of new matching candidates. Accordingly, the computational complexity increases exponentially as the stereo matching region grows. To expedite the matching process of a traditional GOTCHA, this paper proposes a parallelised stereo region growing algorithm called a MT-GOTCHA. To achieve data parallelism, the proposed method initially divides a stereo image from arbitrary
distributed seed points, which are able to employ multiple GOTCHA’s. In addition, since it estimates a cluster of neighbours using a non-linear diffusion equation and performs multiple ALSC processes in parallel to verify local matching candidates, more tiepoints are obtained within less processing time. Experimental results demonstrate the proposed method can reduce the processing time of a dense reconstruction at a reasonable cost of memory consumption.