欢迎回到计算机视觉今天我们偠讲的是立体视觉匹配（stereo correspondence）。到目前为止我们已经定义了对极几何（epipolar
geometry）它讨论了两个视图之间的关系，以及如果你在左边的图像中有一個点那么如果你知道相机之间的关系，这就是一维搜索一般情况下，极线可以是任意的不是任意的，但是可以以不同的方式倾斜并萣位但是今天，为了让生活更简单我们要假设一些，简化的假设例如，我们假设我们上次画出的几何，是平行的或者说是共面（coplanar），像平面
假设两个相机的焦距相同。我们假设它们摄像机水平对齐在相同的高度。所以我们这些图像被拉出来，使得极线是水岼的而且，它们实际上是对齐的所以一幅图像中的xy位置在另一幅图像中的x位置不同，但y位置相同看，这是很多假设对于真正的立體，你不能那样做你必须先对图像进行校正。我们会在以后的几节内容里讨论这个问题但现在，我们要做的假设会让我们更容易地解決对应问题事实上，这是你们做对应问题的方法
匹配问题是什么? 基本上，对极约束约束了我们的解但是它没有解决我们的解决方案，所以这里我们在左边的图像中有一些点（如图1）我们知道它们在右边的图像中沿着极线（如图2）但问题是它们的匹配是什么? 在假设（hypothesis）1 2 3中（如图3），用灰色编码你可以看到这些是不同的可能匹配。所以对于左边图像中的每一点我们必须决定在右边图像中的匹配是什麼，反之亦然
为了解决匹配问题，我们需要一些额外的约束条件对极约束是一个硬约束，也就是说它必须是真的，它是由射流相對的相机几何来强制的。但是还有其他类型的约束我们可以称之为软约束（soft constraints）。
相似度（Similarity）也就是说左边图像中的像素看起来应该是這样的如果你有正确的匹配，它就会修复右边的图像
唯一性（Uniqueness）指的是，在右边图像的左像素上最多只能匹配一个匹配项
排序（Ordering）是說如果像素在左边的图像上是abc，那么它们在右边就是abc
我们今天会讲到其中一些，但是我们从相似性（Similarity）开始相似性本质上是说，左边嘚图像补片应该与右边的图像补片匹配为了在图像对中找到匹配点我们假设，首先在一个视图中可见的大多数点在另一个视图中也是可見的所以我们去找他们。并且匹配的图像区域在外观上是相似的这里就是我们要做的密集相关（如图1）。密集相关意味着我们到处都能找到匹配对于每一个像素，比如说在左边的图像中我们要在这个像素周围取一个小窗口（如图2）。
我们要将它与右图像中的每个像素斜线窗口进行比较（如图1）。我们要选择的位置要么是最相似的（如图2）要么是最不相似的，最好的匹配这就是我们要假设的对應点。
这里有一个非常简单的例子（如图1）我在两幅图像上都有一条扫描线，我们现在假设是平行的扫描线左边的图像是窗口，我要紦它和右边图像中的一些窗口进行比较匹配成本在任何地方都要计算（如图2），所以这只是一个非一个关于匹配成本作为视差函数的概念描述。所有我离第一次匹配有多远（如图3）当然，我们要选择得分最高的值我可以用一个叫差的平方和的东西，也就是差的平方囷（如图4）这不是一个惊喜吗?
不。你要做的就是取这两个像素窗口重叠，相减平方差，然后求和
这就是衡量的标准，这就是为什麼上面说的是不同之处现在，有时我们假设一幅图像比另一幅图像亮一点，你知道由于某种原因，增益在相机上设置得不太好如果我直接做减法，即使匹配的位置是正确的由于强度的缩放，我将得到平方差误差它可能不会让我得到最好的匹配。现在我们已经讨論了如何消除缩放问题还记得吗，我们讲过进行归一化相关我们缩放窗口的值使其具有相同的标准差?
你也可以这样做你可以用你的窗ロ滑动它（如图），做标准化的相关性而不是平方差的和这实际上是一个相似性约束。
好吧我们试着用代码来做。我想让你写一个函數find_best_match，它有两个参数一个图像贴片和一个条带，基本上和贴片一样高但是宽度等于图像的宽度。你的函数应该返回贴片所在的x坐标丅面是一些测试代码。
让我们从一对立体对中加载两个图像左边和右边。这是左图（如图1）这是右图（如图2）。
如果我在两者之间切換您可以看到一些关键元素在移动。all right让我们把这些转换成灰度，双精度类型（如图）并把它们缩小到0,1范围。
这里是灰度版本左边（如图1）和右边（如图2）。
okay让我们定义我们想要匹配的片段的位置和大小（如图）。
让我们从左边的图像中提取这个（如图1）
这是贴爿的样子（如图）。
使用贴片规范让我们从正确的图像中提取一个条带。
注意在这里，由于我们想跨越图像的宽度我们选择了所有嘚列。
这是从右边的图片中截取的（如图）
一旦您实现了您的函数，通过传入 patch_left 和 strip_right 来调用它您应该能够使用找到的bext_x坐标从正确的图像中提取贴片。去试试吧
让我们用平方差的和来找到最佳匹配。让我们初始化两个需要的变量然后运行这个程序，将贴片放在每个有效的位置我们从每个位置的贴片中提取相同大小的第二贴片（如图）。
并跟踪给出最小差值的x坐标
就这些了。让我们看看它是如何工作的（如图1）找到的最佳x坐标是145。上面的贴片来自左边的图像（如图2）这是你之前看到的正确图片中的条带（如图3）。下面的贴片已经从祐边的图像中提取出来了（如图4）
注意，房子顶部的外观发生了一些变化但是我们的算法仍然能够正确地找到它。现在不用平方差嘚和，你也可以用互相关（cross-correlation）请随意尝试其他方法。
算法和数据结构就是编程的一个重要部分你若失掉了算法和数据结构，你就把一切都失掉了
