Stereo Coplanar Area Matching Principal Component Analysis Parallel (SCAMPCAP)

The following reflects improvements to the previously published work on 3D Depth reconstruction from stereo camera images for machine vision. The core of the new algorithm relies on Principal Component Analysis (PCA) to match key epipolar coplanar regions in the 2 stereo images. Selection of these corresponding coplanar regions seems to mimic the manner in which biological systems extract key features for visual cortex processing. Several improvements to the previously published algorithm were made to increase accuracy. Efficiency gains were realized through more accurate region matching, constraining search areas, and finally, paralleling of the process. The Java threading model with cyclic barrier synchronization is the mechanism by which the parallel processing is achieved. Performance remains suitable for realtime applications and is immune to calibration errors and color balance. the code is operational and in place on a number of robotic test platforms in both indoor and outdoor environments.

 Improved algorithm for stereo matching:

(The terms region, node, and octree node and octree cell are synonymous)

 The steps in the pipeline are:

 1.) Edge detect both images using Canny edge detection. A single thread performs these operations.

 2.) Generate 2 octrees of edge detected images at the minimal octree node level, now 7. The number of threads in the octree build process is proportional to the image scan height. A pool of threads that is 1/10 the scan height of the images is used to process each scan line of the images in parallel.

 3.) Use Principal Component Analysis (PCA) on the 2 images to find the minimal coplanar regions in both octrees and generate the eigenvectors and eigenvalues of the principal axis of the minimal coplanar regions.

// A typical barrier synchronized parallel execution block
// this one manages the building of octrees from the stereo image data
for(int syStart = 0; syStart < execLimit; syStart++) {
    SynchronizedFixedThreadPoolManager.getInstance(numThreads, execLimit).spin(new Runnable() {
        @Override
        public void run() {
            imagesToOctrees(dataL, dataR, imageLx, imageRx, yStart.getAndIncrement(), camWidth, camHeight, nodel, noder);
        }
});  
SynchronizedFixedThreadPoolManager.getInstance().waitForGroupToFinish();
                      } // for syStart

4.) Sort the resulting collections of minimal coplanar regions by their centroid Y values.

5.) Process the left image coplanar regions against the right coplanar regions by comparing vector cross products of the two secondary eigenvector axis. Limit processing regions to those whose centroids are within a preset tolerance of the difference in Y value of the 2 centroids. Currently, 25 pixels is used as a tolerance. If more than one candidate is found, select the one with minimal difference in eigenvector cross product. Parallel work is assigned using the sorted centroid Y values to partition the processing into blocks of regions with centroids of common Y value.

6.) Assign a disparity to the minimal octree region based on differences in linear distance of the 2 octree centroids of the points in the coplanar minimal regions from step 4. The regions are small enough that centroid value is accurate enough to give a reasonable disparity value. Work is now assigned to parallel threads based on the size of the collection of minimal regions from the left image, as it is the left image that drives the process of depth assignment. The thread pool is set to a subset of the collection size and the maximum number of threads is set at the number of elements in the collection.

7.) Calculate the mean, variance, and standard deviation of the depth of all the minimal regions, once assigned by step 6. 

8.) Reset the left image octree and regenerate the coplanar regions via PCA at a higher octree level, using octree level 5.

9.) Find the minimal regions (that were assigned a depth) enclosed by the newly generated larger coplanar regions.

10.) Find the mean of all the depths in the subsample of minimal regions enclosed in the larger coplanar region.

11.) Remove from consideration any of the minimal regions whose depth is 2 sigma above the mean of all the minimal regions calculated in step 7.

12.) For all points in the larger regions, determine which enclosed minimal region they fall into. If within the smaller region, assign the point the depth we found and assigned to that minimal region earlier in step 6.

 13.) For points in the larger region that do not fall into a smaller enclosed region, assign it the mean of the depth of the subsampled regions from step 10.

14.) After processing a larger region, remove the smaller regions it encloses from consideration.

 15.) If any minimal regions remain, place them in a 'no-confidence' collection along with unmatched minimal regions from step 5. The collection of 'no-confidence' minimal regions can be used to indicate the possible presence of occlusions that prevent the images from being matched. These occlusions occur when an object appears in one camera but not the other. Conditions where occlusion occurs can include objects closer than the image baseline, or objects positioned in such a way that an object blocks the view of one camera.

16.) Place in 2 separate collections those maximal regions that enclose zero minimal regions, and the maximal regions that were assigned a depth from the mean of the enclosed minimal regions in step 10. A larger region may enclose zero minimal regions when an overlapping region has processed and 'used up' all the minimal regions it encloses.

17.) Process the collection of maximal regions that enclose zero minimal regions in parallel threads based on the size of the collection. For each 'zero region', determine the 'depth regions' it encloses, or the 'depth regions' that enclose it, and create a collection of that subsample for each 'zero region' in each thread.

18.) For every point in the 'zero region', determine the enclosing/enclosed 'depth region' it falls into. If it falls into one of these regions, assign the point the depth associated with the corresponding 'depth region'. If the point falls into none of the 'depth regions', assign the point the mean of all the 'depth regions' enclosed by the 'zero region' of the point, much as we did at a smaller level in steps 9, 10, 11, 12 and 13.

So the pipeline determines the matching epipolar minimal coplanar regions, uses those to apply that disparity to a larger common coplanar region as depth, then uses the larger coplanar regions to assign larger, but still common, coplanar regions a depth. The algorithm seems to consistently result in a 97% depth assignment rate.

Testing is still underway using 2 different robots in indoor and outdoor conditions but sub-1-second response time using 640 by 480 pixel images from standard webcams at a 205mm baseline and a 4.5mm focal length is achieved. The code implementing SCAMPCAP, documentation, and video of test platform robots in the field using code from my various projects, appear in the repositories at github.com/neocoretechs

Final 3D SCAMPCAP point cloud rendered from depth assigned edge detected image, rendered slightly off axis, with minimal coplanar regions (small tricolor areas), unmatched minimal regions (small blue squares), and maximal octree nodes (large blue squares).