基于双目图像分割的区域匹配技术的研究.doc

基于双目图像分割的区域匹配技术的研究计算机科学与技术学院2009级 01班 中文摘要：计算机视觉系统的诞生，是计算机发展史上的一次伟大革命，无论是发展到后来的模式识别，图像追踪，还是三维还原，多目测距等技术，都为生产和生活带来了极大的便利。 而立体匹配技术是计算机视觉中至关重要的一部分，通过立体匹配可以得到几个二维图像中物体的3D信息，立体匹配算法的选择和使用，也直接影响了后续对图形的进一步处理的结果。所以说立体匹配技术也是整个立体视觉系统之中的核心的所在。对2幅二维图像的特征点进行较为准确的匹配，从而达到立体匹配效果，这就需要我们对2幅图像进行一些处理，使图中的特征点所占的比例尽可能的大一些，这样，在后续匹配算法的执行过程中，特征点的匹配数量越多，所达到的匹配效果就更好，转化的深度图也将更为精确。为了尽可能多的保留处理图像中的特征点，忽略掉一些非特征点，我们将对图像进行分割处理，这就引入了图像分割技术。图像分割技术同样是图像处理中的一项关键技术，使用图像分割技术可以将图像当中有意义的特征点的集合提取出来（如物体的边缘，特征区域等），忽略掉一些不具有特征的点（或者说人们分析问题时不感兴趣的点）。由此可见，良好的图像分割技术可以为后续的区域匹配和立体匹配打下坚实的基础。本文将着重对图像分割问题进行较为细致的讨论，在后文当中将例举出2种图像分割算法并对其进行比较，其中包括分水岭算法和mean shift分割算法，并给出分割的实验现象。实验过程中由OPENCV在VS2008平台上实现。关键词： 图像分割区域匹配mean shift算法 分水岭算法SAD算法 ABSTRACT:Stereo matching technology has been more and more important to solve the problems in the domain of computer vision .Using this technology ,we can match two or more images to get the objects information,which are in the situation we took up. Stereo matching is also the core of the computer vision system because of the great influence . In order to match feature points accurately between two images,so as to achieve the effect of stereo matching ,we need to make some processing which remain the feature points and ignore the non-feature points as much as possible.After that ,the proportion of the feature points will be major in the point collection .Accordingly ,using the technology of image segmentation is necessary.Image segmentation is the key technology in image processing .We will select the points which we are interested in in image because these points can help us analyze the problems about the stereo matching.As for the points which are not useful ,we had better eliminate them by image segmentation algorithm. Therefore,a suitable image segmentation technology lays a solid foundation for area matching .This paper will focus on the two discussions in detail which are the image segmentation and area matching ,writing program by OPENCV on VS2008 platform.目录：第一章 绪论.11.1研究背景及其意义.11.2 国内外研究进展.21.3 本文研究的内容及方向.2第二章2.1图像分割的概念.32.2图像分割算法.42.3分水岭算法.82.3.1 分水岭算法介绍.82.3.2分水岭算法实验现象.102.4Mean shift 算法.112.4.1mean shift 算法介绍.112.4.2图像分割的实验现象.152.6基于图像分割的区域匹配.162.7区域匹配的SAD算法.182.7.1 区域匹配的实验现象.19第三章 3.1总结与展望.203.1.1工作总结.203.1.2结论.203.1.3对未来的展望.223.2致谢.223.3附录.23第一章 绪论1.1 研究背景及意义双目视觉技术是近年来计算机领域的热门话题。人类利用所获取的视觉信息来观察世界，改造世界，是因为人眼可以很好的将周围景物所成的像转化为三维的立体感知。那么如果将计算机也赋予这种可以从数个图像中获取三维信息的能力，那么计算机的应用领域将更加广泛，计算机的功能也将更加强大。众所周知，计算机拥有计算能力强，工作时间长，失误率低，精确度高等很多人所不具有的工作能力，所以让计算机实现图像处理的功能，无疑是生产力上的一次革命性的飞跃。那么如何才能赋予计算机这种从二维图像获取三维信息的能力呢，伴随着这个应用性问题的提出，计算机视觉技术便诞生了出来。双目立体视觉技术是计算机视觉技术的一个分支，它所强调的是让计算机通过输入的2幅不同点所拍摄的图像，从而得到场景中物体的三维几何描述及深度信息的能力。经过了人们几十年不断的探索与研究，双目立体视觉的理论正在不断的完善与发展。1.2 海内外研究进展20世纪80年代，美国麻省理工的Marr首次提出通过具有像素差的几个二维图像获得物体的深度的方法，从而正式提出立体匹配算法。而微软公司与华盛顿大学合作为卫星“探测者”号设计了宽基线立体视觉系统，日本东京大学集成双目视觉理论体系与人工智能开发构建了机器人的动态行走导航系统，可以实时进行双目测距实现障碍物检测，从而确定机器人的行走方向。在我国，计算机的双目图像匹配和深度求取虽然没有直接应用于实际的生产生活中，但是已经建立了比较成熟和全面的理论体系。清华大学曾开发的机器人TBIPR1，采用的关键技术便是最为典型的平行双目立体视觉系统。图像的匹配是多视点系统应用中的关键技术，通过模拟双目来达到获取3D信息的目的。在计算机视觉领域之中，图像匹配技术不可或缺，也是世界学者一直在着力研究的对象。立体匹配的算法到现在为止，已经出现多种，具有代表性的有基于区域的立体匹配，和基于特征的立体匹配算法等。计算机工程第14期基于多目立体匹配深度的获取方法中，设计了一种基于颜色分割的立体匹配算法，较好的改进了以上两种算法的缺陷，可以得到较高质量的稠密视差图。1.3本文研究的内容及方向本文通过对不同位置所拍摄的同一场景的二维图像进行图像分割与区域匹配，对二维图像所拍摄的3D场景进行合成，具体方式是先对2个二维图像进行分割操作，再将分割后的二维图像通过基于窗口的区域匹配算法使二维图像中的特征点一一对应起来，得到初步的视差图。之后通过接口，把对应起来的分割后的图像进行立体匹配，根据特征点对应位置不同与摄像机标定的几何关系，求出二维图像中物体的深度，即表示二维图中各个物体到摄像机的距离。在实际应用当中，这种求取深度的测距技术可以解决传统意义上测距（如激光测距，超声波测距等）容易受到环境误差(如光照强度，温度，湿度等)的问题，并且具有实时性，运算速度快，对硬件要求低等优点，对未来科技，如医学研究，机器人智能开发，军事领域等的发展有着重要意义。第二章 2.1图像分割的概念图像分割的描述性定义：把图象按照一定要求分成一些“有意义”区域的处理技术。我们所说的“有意义”是指希望这些区域能够分别和图象景物中各目标物或者背景相对应。图像分割的准确定义： 令集合 R 代表整个图象区域，对R的分割可看作将R分成若干个满足如下五个条件的非空的子集（子区域）：（1）（2）对所有的i 和j ,有Ri Rj = ø (ij)（3）对i=1，2，3，N，有P（Ri）=TRUE（4）对ij，有P(Ri Rj)=FALSE（5）对i=1，2，N，Ri是连通区域我们分别对以上5个条件进行解释:(1) 将分割后的子区域全部集中起来，可以得到整体的图像。同样，我们可以理解为图像中的每个像素都能够被划分到同一个子区域当中。(2) 不同的子区域之间不能有重叠的像素部分。(3) 对于每个被划分的子区域，其中应该具有某些特点或者特征。(4) 不同的子区域之间不会有相同的特征，或者说应该具有不同特征。(5) 每个子区域之间像素必须是连通的。对于上面给出的精确定义，不仅明确的规定了分割准则，同时也为之后的分割算法提供了一条思路。最后需要指出的是，在实际的图像处理过程中，应用图象分割不仅是要把一幅图象分成满足以上五个条件的各具特性的区域，更重要的是要把其中人们讨论问题时感兴趣的目标区域提取出来,只有这样才算是真正完成了图象分割的任务。2.2图像分割算法概述图像分割可以将图像划分出包含真实世界中物体具有明显特征的各个区间，所以图像分割即是图像初步处理和分析中的重要问题,同时也是计算机视觉研究中的一个经典难题。尽管它一直备受国际学者们的关注,但是图像分割算法的道路依然很曲折,被认为是计算机视觉的一个瓶颈。迄今为止,人们仍然没有找到一种可以适用于所有图像的统一，全面的图像分割方法,也没有归纳出某一类图像适合于所有的图像分割方式。近几年来,研究人员不断改进原有方法，结合经典图像分割算法提出了不少新的分割方法。本章节对传统的图像分割方法进行分析。传统的图像分割方法包括阈值法，边缘检测法，以及区域法等。通过分析这些图像分割方法我们可以发现，图像分割理论的基本依据和条件主要有以下几个方面:(l)分割后的图像子区域具有同质性，特别是灰度级别的相近、区域内部纹理相似等。(2)被分割的子区域内部应该平整，不能存在漏洞（很小的空缺）。(3)相邻子区域之间由于没有被约束在同一区域内，所以应存在显著差异性(4)对于每个分割子区域，其边界应该具有齐整性（不能出现边界模糊的情况），同时也要具有明确的空间位置。随着图像分割理论的日渐成熟，体现出的分割算法也日渐精确和快速，然而现有的大多数图像的分割方法也很难实现以上的所有条件。只能满足上述条件中的几个。如果过于强调分割区域的同性质约束，也就是对区域的特征要求过高，那么分割后形成的子区域就很容易产生大量的小空洞，违反了子区域内部的平整性和完整性。但如果增大了对不同区域间性质差异的显著性研究，那么原本在分割当中的很多相邻子区域如果差异性并没有我们所要求那么高时，就会造成这些区域的合并和边界丢失。在我们讨论问题时往往发现对于一些区域的分割是必要的，显然如果这些区域因为我们设计的算法过于强调差异性而没有被分割出来，这种情况是我们不愿看到的。所以说，图像分割方法必须要在各种约束条件下寻找一个平衡点，而这个平衡点的决定，取决于我们对图像处理过程的要求。下面我们以阈值法为例对这种图像分割做简单的说明。阈值法是图像分割当中最基本，同时也是最简单的方式之一。当图像中满足灰度差别很大的条件时，人们通常选用阈值法来处理图像。但是阈值法同时也存在很大的缺点，如果处理的图像中不存在明显的灰度差异时，阈值法就不能够很有效的将图像的前景及背景区分开来，所以得到的分割效果不理想。并且由于阈值法对待问题的局限性，也就是仅仅以图像的灰度信息作为处理问题的参考，而忽视了图像的空间信息，这使得阈值法对噪声区域和灰度不均匀的区域非常敏感。所以阈值法参与到实际应用当中时，通常会有其他的辅助分割算法与之配合使用。阈值法是通过灰度信息来进行分割的算法，首先将一幅图像转化为灰度图像，将像素的灰度值用直方图的形式表现出来，当灰度直方图呈现出来后，我们就可以简单的设置一个或者几个值将直方图分成几类, 所分的类当中对应的各个像素就构成了所分划的区域，而我们为了将直方图分类而设定的这几个表示灰度的值，就被称作“阈值”。根据阈值的确定方式又可以将阈值法分为全局阈值分割和局部阈值分割。全局阈值分割，顾名思义是指通过对整幅图像的灰度信息进行处理从而得到阈值，并根据该阈值实现对图像子区域的分割操作。而局部阈值分割法（又称作自适应的阈值分割法）则是根据图像当中的不同区域获得对应的阈值的一种方法, 之后再利用这些阈值对各自的区域进行分割, 每一个阈值对应其相应的一个子区域，需要注意的是一个子区域仍然可以有多个阈值参与分割。由于阈值法实现起来简单且能够很好的区分具有很大对比性的物体这种特点,所以这种分割算法深受人们的关注与好评，一般来说，阈值法可以作为处理图像过程当中的第一个步骤。如何确定合适的阈值从而进行图像分割成为了阈值法分割法的关键所在，也是算法的难点所在。如果在图像处理后得到的灰度直方图上可以观察到明显的波峰或者波谷，那么我们就可以选择处于谷底的灰度值作为阈值。基本形式的阈值法只能产生通过一个阈值所限定出的前景和背景。并且由于阈值法只是简单的考虑象素本身的灰度值, 从而使其忽视了图像的空间特性, 这样对噪声以及纹理的处理有时并不尽如人意。下面来介绍几种阈值法全局阈值法（1）双峰法对于前景与背景的灰度级有明显差异的图像,其灰度直方图的分布会呈现双峰状,两个波峰分别与图像当中前景和背景相对应,波谷处与图像的边缘对应。通常选择谷底的灰度值作为阈值来进行图像分割可以取得最好的效果。使用双峰法可以很容易的构造出阈值，从而实现对全局的分割,但是如果灰度直方图中并没有出现比较明显或剧烈的起伏（如波峰不突出或者波谷比较平坦的状况），就不能使用这种方法来处理图像。当我们所要处理的图像中只有一个前景和背景需要分割，同时前景和背景的色差（灰度差）偏大时，其转化的灰度图直方图可以直观的呈现出双峰效果。图2.2.1 双峰法灰度直方图通过对阈值T的设定，我们可以实现出理想的分割效果寻找阈值的算法主要是通过使用数组来记录直方图中各个像素的个数，数组ax中，x表示灰度（0-255）ax中记录的数据则表示图中该灰度下像素的个数，之后选择谷底的像素灰度值作为阈值。（2）灰度直方图变换法正如上面所说，基本形式的阈值法具有比较大的局限性，当我们所要处理的图像对应的灰度直方图不具有明显的波峰以及谷底相对平坦时，直接使用基本形式的阈值法可能会出现边界模糊或者将背景划分到前景的情况。所以这时当我们仍然需要对图像进行阈值法处理时，就需要对图像进行简单的处理，使得处理后的图像对应直方图具有较强的波峰波谷特征,灰度直方图变换法即是通过变换图像的灰度直方图，这样变换之后直方图就满足了适合阈值法的条件，之后就可以使用双峰法做后续处理了。这种方法的实现是基于像素的局部特征，将比较分散的像素集中处理，因为灰度是影响阈值法的唯一因素，所以我们只要将比较平均或者分散的灰度直方图做集中化处理即可，由于对灰度直方图做了类似聚类的处理，呈现的直方图会表现出很明显的波峰和波谷。虽然灰度直方图法的使用范围比基本的阈值法有更广泛的适用领域，但是这种算法仍然延续了阈值法的思想，只是把图像近似成灰度差异较大的前景和背景，所以图像不能近似看做简单的阈值法模型时，灰度直方图处理后也并不能给出太大的帮助。局部阈值法（1）自适应阈值阈值法强调的是前景和背景的分割，其中背景由单一灰度像素或者灰度相近像素构成，然而多数情况下，我们所处理的图像并不具有这样的特性，如果背景的灰度值也呈现变化趋势或者可以分成几个类别，那么传统的阈值法就不能起到很好的分割效果。简言之，前景和背景如果发生灰度的变化，阈值分割法就会受到条件的约束，这一局限性也大大制约了阈值法的发展，如果此时设定一个阈值，那么这个阈值可能会适合整幅图像的某个部分，但是对于对于分割其他的区域会变得很糟糕。如果考虑到更多的因素，比如阴影，光照不均匀等情况发生时，只使用一个固定的阈值来实现图像分割，同样会影响分割的效果，针对这种问题人们采用自适应的阈值分割法来实现图像的阈值化处理，也就是将原始图像分块，针对各自的区域选取合适的阈值，这样，阈值就和图像的位置区域形成了映射关系，所以我们也称此时的阈值为阈值函数，随着图像区域的变化所产生不断变化的阈值。自适应的阈值分割法主要是将所要分割的图像分成多个模块，在每一块内使用阈值法进行分割，这样在各自的区域内所形成的分割效果要比整体分割的效果要好上许多。虽然自适应的阈值分割算法需要消耗较多的演算时间和内存空间，但是从分割效果上看要强于整体的阈值分割，抗噪能力也较强。2.3分水岭算法2.3.1 分水岭算法介绍分水岭算法是一种建立在数学模型结构基础上的分割算法，以数学形态学为思想的算法逐渐成为了图像处理中的热门话题，建立以数学模型为基准的算法也是人们研究的热门方向。分水岭算法就是其中的代表之一。传统的图像分割算法通常以图像的灰度作为标准，分水岭算法也是如此，通过图像的灰度来进行分割处理，但是与以往的分割算法有所不同，以往的分割算法虽然对图像做了灰度转换处理，但其目的往往是为了找出灰度图像中的不同之处加以区分，从而实现对应其像素的分割运算。分水岭算法则有所不同，我们首先可以想象一个三维空间坐标系（如右手坐标系），我们将灰度图平放与XOY平面重合的位置，则图中每个像素点a都具有自己的空间位置a（x，y，0），那么我们引入第三个维数Z，对于任意一个像素点a（x，y，0），都有唯一一个点b（x，y，z）与之对应，其中z表示像素点a的灰度，这样b点集就构成了一个类似地貌的拓扑结构。分水岭算法模仿的是一个模型浸水的过程，在水位从0开始向上蔓延的过程中，需要人为地设置局部极小值点，实际上，在图上做了适当标记之后，这些点在“水”位上涨的时候，首先从这些点开始浸水，如果这些浸水点周围的灰度值较小，那么水位上涨的过程中，水就会很快速的没过这些像素，形成一个集水盆，反之，如果局部极小值点周围的像素灰度值较高，那么水位上涨的很长时间内，都不能浸没该点附近的区域。之前提到了集水盆的概念，集水盆是由于水通过局部极小值点扩散到周围而形成的，在集水盆扩散的过程中，我们发现，属于同一个集水盆的像素他们之间的灰度差异较小，这种微小的差异至少应该比他们与其他集水盆的元素灰度差异值小（否则该点的元素会归并至其他的集水盆当中）。由于每个集水盆都具有灰度相似的特点，同时还与其他集水盆的元素形成灰度上的差异，这样，各个集水盆就很好为我们创造了分割的条件，由于水位的不断上涨，各个集水盆的面积会不断变大，最后将整个地貌结构全部覆盖，此时我们只需将各个最大化的集水盆区别并保存下来，就能够得到我们所要的分割图像。于是，我们为了保存这些集水盆，使之不至于在扩充之中相互融合，引入了分水岭的概念，分水岭即集水盆的边界，当几个集水盆在扩大的过程中相交，则会在交界处产生分水岭，集水盆在分水岭形成的位置不再生长，直到整个集水盆被分水岭或者图像边缘包围，该集水盆不在扩大，当所有的集水盆都确定下来时，算法结束。分水岭算法的重点在于为像素灰度的排序和淹没过程。2.3.2 分水岭算法实验现象：分水岭算法的实验现象如下： 图2.3.1 实验原图图2.3.2分割图 图2.3.3 实验原图 图2.3.4 分割图为了使分割后我们能够观察到的图像区域性明显，分割图各区域内采用随机上色模式。2.4mean shift 算法2.4.1mean shift算法介绍Mean Shift 这个概念的首次提出是在1975年，当时mean shift出现在Fukunaga等人的一篇关于概率密度梯度函数的估计中，其最初含义正如其名,就是偏移的均值向量，在文章中Mean Shift只是一个指代向量的名词，直到1995年，Yizong Chen 对基本的均值漂移算法做了改进并提出了该算法可能应用的领域，人们才认识到这种思想的巨大应用价值，后来，Comaniciu等人成功的把这一算法应用在了特征空间分析，进一步拓展了该算法在图像分割领域的具体应用，并取得了较好结果。Mean shift 算法实质上是核密度估计的算法，算法核心是对特征空间上的样本点进行聚类，并得到所谓的模式点，即密度梯度为0的点，理论如下：Mean shift基本形式：在d维的欧几里得空间中取n个样本点，i=1，n,在点的均值漂移向量的基本形式定义为：(1)其中是一个样本点的集合，这些样本点满足这样的条件，即与初始点所形成的向量其模要小于h。 (2)我们注意到其中（1）中除了样本点的个数外，还存在一个参数k，这里k的作用是将各个向量平均加权，k即集合中样本点的总数。从以上2个定义式我们能够直观的发现，对于特征空间中的每一个点x，与任意的中的 （i=0,1，k），都构成了一个向量，而所有这些向量加和再求平均就得到了x点处的均值漂移向量。如果样本点从一个概率密度函数中采样得到,由于概率密度函数的梯度指向概率密度增加最大的方向,因此从概率的角度上来看，在概率密度增加最快的方向上（也就是沿着梯度方向）落在高维球区域上的点将越来越多，所以由定义可以发现，均值漂移向量的方向也应该指向概率密度梯度的方向。图2.4.1 mean shift 图示由上面图我们可以看到mean shift 的几何意义，大球的半径是指我们所选取的h，大球内部的空心点指的是落在求区域当中的点的集合，实心点表示我们所选取的点x，即mean shift 所选取的基本点，很明显我们可以看到最终向量会指向点分布最密集的方向。为了通过mean shift 实现图像分割算法，我们还需要引入以下几个概念：核函数的概念：定义：X代表d维欧式空间，x表示该空间中的一个点，用列向量来表示， ，R表示实数域，如果一个函数K：X R 存在一个剖面函数K：0, R 即 ，并且满足:(1) k是非负的(2) k是非增的,即如果那么(3) k是分段连续的,并且 这样的函数K(x)就被称为核函数。在核函数中有2个比较常用的核函数：单位均匀核函数：(4)单位高斯核函数：(5)这两类核函数的图像表示：(a) 单位均匀核函数(b)单位高斯核函数Mean shift 算法的拓展形式： 由基本形式(1)我们可以发现，对于落入高维球区域的任何一点，对最后向量计算的贡献是一样的，但是在我们做图像分析的时候发现，针对我们研究的某个点，距离该点较近的样本点可以更好的帮助我们分析该点附近区域的信息，如灰度变化，样本的聚集程度等，因此我们利用核函数将每个向量加权，这样在计算时可以将距离也视为一个影响向量的因素。基于这个理论，我们将mean shift 以数学公式的形式拓展出来： (6)其中:是一个单位核函数是一个正定的对称矩阵,我们一般称之为带宽矩阵是一个赋给采样点的权重在实际应用的过程中,带宽矩阵一般被限定为一个对角矩阵,甚至更简单的被取为正比于单位矩阵,即.由于后一形式只需要确定一个系数,在Mean Shift中常常被采用,在本文的后面部分我们也采用这种形式,因此(6)式又可以被写为: (7)在上式中如果对所有的采样点使其满足：(1)(2) 则(7)式完全退化为(1)式，也就是说我们所给出的扩展的Mean Shift形式在某些情况下会退化为最基本的Mean Shift形式。现在讨论mean shift 算法在图片分割上的步骤：我们在前面已经指出,我们在提及Mean Shift向量和Mean Shift算法的时候指代不同的概念,Mean Shift向量是名词,指的是一个向量；而Mean Shift算法是动词，指的是一个迭代的步骤.我们把(7)式的提到求和号的外面来,可以得到下式：(8)我们把上式右边的第一项记为,即(9)给定一个初始点,核函数, 容许误差,Mean Shift算法循环的执行下面三步,直至结束条件。(1)计算(2)把赋给(3)如果,结束循环;若不然,继续执行(1)由(8)式我们知道，因此上面的步骤也就是不断的沿着概率密度的梯度方向移动，同时步长不仅与梯度的大小有关，也与该点的概率密度有关，在密度大的地方，更接近我们要找的概率密度的峰值，Mean Shift算法使得移动的步长小一些,相反,在密度小的地方,移动的步长就大一些.由于mean shift 算法的收敛性已经被证明，所以在满足一定条件下,Mean Shift算法一定会收敛到该点附近的峰值。2.4.2mean shift 分割算法实验现象：采用mean shift 分割算法得到实验现象： 图2.4.2 原图 图2.4.3 分割图 图2.4.4 原图 图2.4.5 分割图2.6 区域匹配前面章节中我们介绍了几种图像分割方法，主要目的是为了使用较好的分割方式从而使后续的双目图像进行的区域匹配更加精确。回顾几种分割方式，我们发现阈值分割法的适用范围并不广泛，而分水岭算法虽然可以得到较好的分割图像，但是由于我们接下来要处理具有强相关性的左右2幅双目图，分水岭算法在这里存在2个问题：（1）分水岭算法中需要人为的设置局部极小值点，对于2幅双目图像，同时人为的设置相同像素的局部极小值点会产生比较大的误差，从而导致了不同的分割方式，进而影响之后的区域匹配操作。（2）分水岭算法并不能特别明显地识别两侧像素灰度差别不大的边界区域，容易造成边界缺失，这也为后续区域匹配的实现带来困扰。综合来看，我们认为mean shift 算法作为双目图像的分割算法最为合适。通过mean shift 算法我们可以将左右两幅图做相同的处理，这样我们就得到了两幅双目分割图像，接下来为了最终能够实现立体匹配，我们应该要得到一个初步的深度图，而初步的深度图就是依据区域匹配产生的，所以我们接下来研究的问题是，如何将左右两幅分割图像通过域匹配将图像中的特征区域对应起来。区域匹配的概念就是将2幅或者多幅图中的特征区域（或特征点的集合）对应起来。由于我们所研究的双目图像是平行架设的摄像机所拍摄的，所以图像中的像素之间会满足一些约束条件，这些条件可以帮助我们减少搜索匹配区域的工作量。现在将这些约束一一列举出来，然后我们将会对这些约束做一些解释说明。（1） 外极线约束（2） 相似性约束（3） 唯一性约束（4） 连续性约束（5） 形状连续性约束（6） 顺序约束外极线约束告诉我们平行架设的摄像机所拍摄的左右2幅双目图像，其中一幅图上所有的点与另一幅所对应的点在同一外极线上，也就是图像的同一水平面上，如果存在一点p（x，y），则p点在另一幅图上的对应点应为q（x，y）。这样我们在搜索匹配点的过程中将会省去很多不必要的匹配工作，所以外极线约束也是匹配当中最重要的约束条件。唯一性约束和顺序约束强调的是点与点之间的对应，对于左图当中的一点p，只能有唯一的一点q与之对应，反之对于点q，也不能有其他异于点p的点与之对应，通常唯一性约束用来检验匹配点是否准确。顺序约束进一步强调了点对之间的空间限制，左图中p点与右图q点对应，则q点的横坐标一定大于p点的横坐标，所以当我们以p（x，y）为参考点，在右图中搜索p的对应点时，我们只需从x点开始依次向右搜索就可以了，这个约束条件再一次为我们减少了搜索工作，同时也减少了区域匹配中的误匹配。相似性约束主要体现在匹配算法的实现上，也就是说，匹配算法本身很大程度上是基于相似性约束条件给出的，如果说之前的三条约束说明了特征匹配点对之间的位置关系，那么相似性约束则说明了对应点之间应该具有相同的内在属性，比如匹配点之间的灰度关系，匹配点周围像素的分布性质等。连续性约束和形状连续性约束主要说明的是三维场景中物体以及物体所成像上像素之间的关系，同一个物体上的像素应该在灰度上保持连续性，而双目图像上的物体也应该保有这个特性。2.7 SAD算法上一节我们了解到关于双目图像匹配算法的几个约束条件，现在我们将提出基于以上约束条件的SAD（sum of absolute differences）算法。基于外极线约束，我们知道双目图像中左图像素对应在右图中的像素一定在同一极线上（即两点的纵坐标相同），这将大大减轻我们的匹配搜索工作量，但是由于每个像素的灰度值只能从0到255，即使从对应图中的一条直线中搜索匹配像素，也可能有完全相同的象素从而造成误匹配，也就是说以点为搜索单位是不可取的方法，有此我们引入窗口的思想，如果我们以n为边长的窗口为搜索单位，如果双目图像中左图中的一个窗口的像素和右图上同一极线上的窗口完全相同，那么匹配正确的可能性将大大提高。在双目对应窗口的匹配过程中（默认在外极线约束条件下），匹配过程先以中心像素开始，再逐步扩充到中心像素的外层，从而n变为3，再扩充至外层，n变为5，以此类推。这样n的值一般选择5到21的奇数。在这里值得一提的是，固定左图中一个窗口，右边窗口以像素为单位进行滑动匹配，此时也应该满足连续性约束进一步加强算法