立体匹配中的NCC，SAD，SSD算法

Normalized Cross correlation (NCC)

NCC(u,v) =  [(wl - w)/(|wl - w|)]*[(wr - w)/(|wr - w|)] 选择最大值

 

Sum of Squared Defferences (SSD)

SSD(u,v) =  Sum{[Left(u,v) - Right(u,v)] * [Left(u,v) - Right(u,v)]} 选择最大值

Sum of Absolute Defferences (SAD) 

SAD(u,v) = Sum{|Left(u,v) - Right(u,v)|}  选择最小值

 

先说说SAD算法的基本流程：

1.构造一个小窗口，类似与卷积核。

2.用窗口覆盖左边的图像，选择出窗口覆盖区域内的所有像素点。 

3.同样用窗口覆盖右边的图像并选择出覆盖区域的像素点。

4.左边覆盖区域减去右边覆盖区域，并求出所有像素点差的绝对值的和。

5.移动右边图像的窗口，重复3，4的动作。（这里有个搜索范围，超过这个范围跳出） 

6.找到这个范围内SAD值最小的窗口，即找到了左边图像的最佳匹配的像素块。

 

OpenCV代码示范SAD:

 1 IplImage* generateDisparityImage(IplImage* greyLeftImg32,
 2                          IplImage* greyRightImg32, 
 3                          int windowSize,int DSR){
 4 
 5     int offset=floor((double)windowSize/2); 
 6    int height=greyLeftImg32->height;
 7    int width=greyLeftImg32->width;
 8     double* localSAD=new double[DSR];//DSR即搜索范围
 9 
10    int x=0, y=0,d=0,m=0;
11    int N=windowSize;             
12 
13    IplImage* winImg=cvCreateImage(cvSize(N,N),32,1);//mySubImage(greyLeftImg32,cvRect(0,0,N,N));
14    
15    IplImage* disparity=cvCreateImage(cvSize(width,height),8,1);//or IPL_DEPTH_8U
16    BwImage imgA(disparity);
17    
18    for (y=0;y<height;y++){ 
19       for (x=0;x<width;x++){
20          imgA[y][x]=0;
21       }
22    }
23    
24      CvScalar sum;
25    //CvScalar s2;
26    for (y=0;y<height-N;y++){ //height-N
27       for (x=0;x<width-N;x++){//width-N 
28          cvSetImageROI(greyLeftImg32, cvRect(x,y,N,N));
29          d=0;         
30           //initialise localSAD
31           for (m=0;m<DSR;m++){localSAD[m]=0;} 
32           
33           //start matching
34           do{ 
35             if (x-d>=0){ 
36                cvSetImageROI(greyRightImg32, cvRect(x-d,y,N,N)); 
37             }else{
38                break;
39             } 
40 
41             cvAbsDiff(greyLeftImg32,greyRightImg32,winImg);//absolute difference
42             sum=cvSum(winImg);//sum
43             localSAD[d]=sum.val[0];//0 means single channel
44 
45             cvResetImageROI(greyRightImg32); 
46             d++;
47          }while(d<=DSR);
48          
49          //to find the best d and store
50           imgA[y+offset][x+offset]=getMaxMin(localSAD,DSR,0)*16; //0 means return minimum index
51          cvResetImageROI(greyLeftImg32);
52       }//x 
53       if (y%10==0)cout<<"row="<<y<<" of "<<height<<endl;  
54    }//y
55    
56    cvReleaseImage(&winImg); 
57    //cvReleaseImage(&rightWinImg); 
58         
59    return disparity;
60 
61 }