基于FPGA的SAD立体匹配算法实现(3)
根据SAD算法的定义，设 为视差，即在一个方向上左摄像机拍摄的图像中窗口移动的距离， 为基准图中的待匹配点像素的灰度值， 为配准图中的匹配点像素的灰度值，则SAD算法可以表示为：
其中， 表示匹配窗口的半径， 和 分别表示窗口的高度和宽度。在不同视差值 的情况下，计算SAD值并选取其中的最小值，则此时 所代表的配准图中的点即使 所代表的待匹配点在配准图中的最佳匹配点。
相比较而言，SSD算法和NCC算法则较为复杂：
其中， 表示图像 中像素 的 邻域的像素平均灰度的大小， 表示图像 中像素 的 邻域的像素灰度的标准差。从上面两个式子不难看出，SSD算法和NCC算法相比于SAD算法运算量还是相当大的，因此，在利用FPGA硬件实现时，SAD算法效率更高，运算速度更快。
SAD算法的基本流程为：先构造一个长宽为 的小窗口，相当于卷积核；用该窗口覆盖待匹配图像区域内的所有像素点；同样的，用该窗口覆盖配准图像，并通过式2.1设置 的值计算出所有像素点差的绝对值和；在配准图像中移动该窗口，再次设置 的值为移动距离，通过式2.1得出所有像素点差的绝对值和；找到 最大值范围内所求得的SAD值最小的窗口，即找到了最佳匹配像素块。[14]
2.2 FPGA的基本原理和结构
FPGA（Field Programmable Gate Array）即现场可编程门阵列，是一种半定制电路。FPGA的结构是由阵列式的逻辑功能块排列组成，并利用可编程的互连资源来连接这些逻辑功能块和相应的输入输出单元来实现各种设计，并且可以反复擦写。其中，逻辑结构配置数据决定了FPGA的功能。