基于特征的识别

24.5.2 基于特征的识别

除了采用原始像素亮度作为特征，我们还可以检测和标注一些空间的局部化特征，比如区域和边缘（参见第24.3节）。使用边缘的动机有两个。一个是减少数据量——边缘要比图像像素点少得多。另一个是亮度不变性——在适当的对比度范围内，检测到的边缘位置大致相同，而与精确的照明环境无关。边缘是一维特征；二维特征（区域）和零维特征（点）也已被采用。注意在基于亮度和基于特征的方法中对空间位置的处理是不同的。在基于亮度的方法中，特征向量分量的下标暗含了空间位置。在基于特征的方法中，位置(x, y)就是特征。

边缘的排列方式是一个物体的特点——这是我们能够很容易地理解线条图（见图24.13）的原因之一，即使这些图像在自然界中并不存在！利用这个知识的最简单的方式是使用最近邻分类器。我们可以预先计算并存储与已知物体的视图相对应的边缘结构。只要给出与查询图像中的未知物体相对应的边缘结构，我们就可以确定它到存储视图的库中每个成员的“距离”。最近邻分类器可以选出最接近的匹配。

关于图像之间的距离，已经提出了许多不同的定义。一个比较有趣的方法是基于可变形匹配（deformable matching）的思想。D’Arcy Thompson（1917）在他的经典著作《成长与形成》（On Growth and Form）中论述了相关而不相同的形状经常可以通过简单坐标变换发生形变，从而能够校准。在这个范例中，我们可以用一个三阶段过程实施形状相似性的概念：(1)求解两个形状之间的对应性问题， (2)利用对应性对校准变换进行估计，并且(3)计算两个形状之间的距离，即对应点之间的匹配误差总和，连同测量校准变换的量级的一个项。

我们用一个形状的内轮廓或外轮廓上的离散采样点集表示这个形状。这些可以和利用边缘检测算子检测到的边缘像素点位置一起得到，为我们提供了一个N点集合{p1,...,pN}。图24.20的（a）和（b）显示了两个形状的采样点。

图24.20 形状上下文的计算与匹配。（a），（b）两个形状的边缘采样点。（c）为计算形状上下文所使用的对数-极坐标直方图方柱的图。我们用5个方柱表示log r，12个方柱表示θ。（d）～（f）在（a,b）中用点〇，◇， 标出的参考采样点的形状上下文例子。每个形状上下文都是以参考点为原点的点集合中所有其余点坐标的对数-极坐标直方图。（深色的方块表示方柱中有较多的点数。）注意〇和¸的形状上下文看上去很相似，它们是对两个形状上相对比较相似的点计算得到的。相比之下， 的形状上下文就相当不同了。（g）用双向匹配找到的（a）和（b）之间的对应点，其中代价定义为直方图之间的χ2距离

现在考虑一个特定的采样点pi，以及从该点出发到形状中其余所有采样点的向量集合。这些向量表示了整个形状相对于参考点的布局。这引出了以下思想：每个采样点都对应着一个描述记录，即形状上下文（shape context），它描述了对于该点而言，形状的其余部分的粗略排列情况。更准确地说， pi的形状上下文是其余N − 1个点pk的相对坐标pk− pi的粗略空间直方图。一个对数-极坐标系被用来定义该直方图的方柱，确保描述记录对附近像素的差异更敏感。一个例子如图24.20（c）所示。

注意到平移不变性是形状上下文的定义所固有的，因为所有的度量都是针对物体上的点进行的。为了得到尺度变换不变性，所有的径向距离都用点对之间的平均距离进行归一化。

形状上下文使人们能够解决两个相似但不相同形状之间的对应问题，比如图 24.20（a）和24.20（b）。单一形状S上不同点的形状上下文是不同的，而相似形状S和S '上的对应（相应）点倾向于有相似的形状上下文。于是我们可以把寻找两个形状之间对应点的问题转化为寻找具有相似形状上下文的点对。

更加精确地，考虑第一个形状上的一点pi与第二个形状上的一点qj。令Ci j= C( pi, qj)表示对这两点进行匹配的代价。由于形状上下文是用直方图表示的分布，因此很自然地采用χ2距离：

其中hi(k)和hj(k)表示在pi和qj处规格化直方图的第k个方柱。给定由第一个形状上的各点i和第二个形状上的各点 j组成的所有点对的代价Ci j的集合，我们希望在一对一匹配的约束下使对象匹配的总代价最小化。这是加权双向匹配（weighted bipartite matching）问题的一个实例，可以用匈牙利算法（Hungarian algorithm）在O(N3)时间内求解。

如果已知采样点处的对应关系，就可以通过对把一个形状映射到另一个的校准变换进行估计，将对应关系扩展到整个形状。正则化的薄板样条算法是特别有效的。一旦形状被校准，就可以相对直接地计算相似性评分。两个形状的距离可以定义为对应点之间的形状上下文距离以及与薄板样条相关的弯曲能量的加权和。利用这种距离测量方法，可以用一个简单的最近邻分类器解决识别问题。在第二十章中描述了这种方法在手写体数字分类中的优异性能。