计算机视觉教程CCV13

1、第13章广义匹配13.1 目标匹配13.2 动态模式匹配13.3 关系匹配13.4 图同构匹配13.1 目标匹配13.1.1 匹配的度量13.1.2字符串匹配13.1.3惯量等效椭圆匹配13.1.1 匹配的度量1.Hausdorff距离描述点集之间的匹配程度或相似性几何意义：如果点集A和B之间的Hausdorff距离为d，那么在每个点集中都可以找到一个点，使另一个点集的各点都落在以该点为中心、以d为半径的圆中13.1.1 匹配的度量1.Hausdorff距离对噪声点或点集的外野点（outline）很敏感采用统计平均的概念，用平均值代替最大值，称为改进的Hausdorff距离（MHD）13.1.

2、1 匹配的度量1.Hausdorff距离 MHD具有对噪声和点集的外野点不敏感的优点，但对点在点集中的分布还不敏感13.1.1 匹配的度量 13.1.1 匹配的度量2.结构匹配量度“模板和弹簧”参考结构和待匹配结构之间的匹配一个按照其优度定量了的对应 13.1.2 字符串匹配1.字符串(1)S aA（起始符号可用元素a和变量A来替换）(2)A bS（变量A可用元素b和起始符号S来替换）(3)A b（变量A可以用单个元素b来替换）13.1.2 字符串匹配2.字符串匹配借助字符串匹配来匹配两个目标区域的轮廓用M表示两字符串间已匹配的总次数，则未匹配字符的个数为A和B之间一个简单的匹配量度为13.1

3、.2 字符串匹配3.字符串匹配应用匹配两个视频片段序列V1和V2两个序列的长度相同，即L1 = L2两个序列的长度不同，考虑如何选取匹配时间起点，移动时间起点t13.1.3 惯量等效椭圆匹配3.字符串匹配应用目标 惯量椭圆 等效椭圆平移变换13.1.3 惯量等效椭圆匹配3.字符串匹配应用旋转变换尺度变换13.1.3 惯量等效椭圆匹配3.字符串匹配应用匹配两个连续切片上对应同一细胞的两个相邻剖面图13.1.3 惯量等效椭圆匹配3.字符串匹配应用对横跨10个连续切片的细胞剖面配准的结果13.2 动态模式匹配1.匹配流程13.2 动态模式匹配2.绝对模式和相对模式绝对模式包含绝对坐标，具有旋转不变性

4、13.2 动态模式匹配2.绝对模式和相对模式相对模式不仅具有旋转不变性，而且也具有平移不变性13.2 动态模式匹配2.绝对模式和相对模式动态模式匹配实例13.3 关系匹配13.3.1 关系表达和距离13.3.2 关系匹配模型13.3.1 关系表达和距离两个关系集Xl和Xr，其中Xl属于待匹配对象，Xr属于模型Qr = 1，2，3，4。各元件间的关系集可表示为Xr = (R1，R2，R3)，其中R1代表连接关系，R1 = (1，2) (1，3) (1，4) (2，4) (3，4)；R2代表上下关系，R2 = (1，2) (1，3) (1，4)；R3代表左右关系，R3 = (2，3) (2，4)

5、(4，3)13.3.1 关系表达和距离Xl和Xr之间的距离记为dis(Xl, Xr)13.3.1 关系表达和距离Xl和Xr之间的距离记为dis(Xl, Xr)13.3.2 关系匹配模型(1)(2)13.3.2 关系匹配模型(3)(4)13.4 图同构匹配13.4.1 图论基础13.4.2 图同构和匹配13.4.1 图论基础1.基本定义图G：由有限非空顶点/结点集合V(G)及有限边/边线集合E(G)组成有色图G：C为顶点色性集S为边线色性集13.4.1 图论基础2.图的几何表达将图的顶点用圆点表示，将边线用连接顶点的直线或曲线表示V(G) = A, B, C，E(G) = a, b, c, d，其中a AB，b AB，c BC，d CC13.4.1 图论基础3.子图和母图13.4.1 图论基础13.4.2 图同构和匹配1.图的恒等和同构同构：具有相同的几何表达但不恒等13.4.2 图同构和匹配2.同构的判定(1)全图同构：B1和B2之间一对一的映射(2)子图同构：B1子图和B2的全图之间的同构(3)双子图同构：B1的各子图和B2的各子图教程作者（章毓晋）联系信息 通信地址：北京清华大学电子工程系 邮政编码：100084 办