V(G) = {A, B, C }， E(G) = {a, b, c, d }， 其中 a AB，b AB， c BC，d CC
26
子图和母图
27
28
图的恒等和同构
恒等
同构
同构：具有相同的 几何表达但不恒等
29
同构的判定 (1) 全图同构：B1和B2之间一对一的映射 (2) 子图同构：B1子图和B2的全图之间的同构 (3) 双子图同构：B1的各子图和B2的各子图
14
例13.1.2 细胞图像配准实例 对横跨10个连续切片的细胞剖面配准的结果
15
匹配流程
16
绝对模式和相对模式 绝对模式包含绝对坐标，具有旋转不变性
17
绝对模式和相对模式 相对模式不仅具有旋转不变性，而且也具有平移不变性
18
绝对模式和相对模式 例13.2.1 动态模式匹配实例
19
两个关系集Xl 和Xr，其中Xl 属于待匹配对像，Xr 属于模型
30
R2代表上下关系 R2 = [(1, 2) (1, 3) (1, 4)]
R3代表左右关系 R3 = [(2, 3) (2, 4) (4, 3)]
20
X l 和X r 之间的距离记为dis(X l , X r ) 关系表达 对应变换
4 种误差
21
X l 和X r 之间的距离记为dis(X l , X r ) 误差加权和
惯量等效椭圆匹配 目标匹配 目标 惯量椭圆 等效椭圆 由于图像中的每个目标都可用它的等效椭圆来表示，
所以对目标的配准问题就可转化为对其等效椭圆的匹配
12
惯量等效椭圆匹配 目标匹配
平移变换
旋转变换 尺度变换
13
例13.1.2 细胞图像配准实例 匹配两个连续切片上对应同一细胞的两个相邻剖面图
2
目 录 contents
13.1 目标匹配 13.2 动态模式匹配 13.3 关系匹配 13.4 图同构匹配
3
豪斯道夫距离 描述点集之间的匹配程度或相似性
几何意义：如果点集A和B之间的豪斯道夫距离为d，则 对两点集中的任意一个点，都可在以该点为中心、以d 为半径的圆中找到另一个点集里的至少一个点
9
字符串匹配 借助字符串匹配来匹配两个目标区域的轮廓 用M 表示两字符串间已匹配的总次数，则未匹配
字符的个数为
A和B之间一个简单的匹配量度为
10
字符串匹配应用 匹配两个视频片段序列V1和V2 两个序列的长度相同，即L1 = L2
两个序列的长度不同，考虑如何选取匹配时间起点， 移动时间起点 t
11
以项计误差
对应误差 最小的映射
对应误差最小 的一组映射
22
(1) 相同关系
所属模型
24
基本定义 图G：由有限非空顶点/结点集合V(G)及有限边/边线集
合E(G)组成
有色图G：
C为顶点色性集 S为边线色性集
25
图的几何表达
将图的顶点用圆点表示，将边线用连接顶点的直线或 曲线表示。边数大于等于1的图可以有无穷多个几何表达
CT 表 示 模 板 和 待 匹 配 结 构 之间的不相似性 CS表示待匹配结构和目标 部件之间的不相似性 CM表示对遗漏部件的惩罚
8
字符串 (1) S aA（起始符号可用元素a和变量A来替换） (2) A bS（变量A可用元素b和起始符号S来替换） (3) A b （变量A可以用单个元素b来替换）
计算机视觉教程
●
1
第13章 广义匹配
从视觉的角度看，“视”应该是有目的的 “视”，即要根据一定的知识（包括对目标的描述） 借助图像去场景中寻找符合要求的目标；“觉”应 该是带识别的“觉”，即要从输入图像中抽取目标 的特性，再与已有的目标模型进行匹配，从而达到 识别景物、理解场景含义的目的
匹配可在不同（抽象）层次上进行 广义匹配比较抽象，主要与图像目标或目标 的性质有关
4
豪斯道夫距离 对噪声点或点集的外野点（outline）很敏感 采用统计平均的概念，用平均值代替最大值，称为
改进的豪斯道夫距离（MHD）
5
豪斯道夫距离 MHD具有对噪声和点集的外野点不敏感的优点，
但对点在点集中的分布还不敏感
6
豪斯道夫距离
用标 准方 差改 进的 豪斯 道夫 距离
7
结构匹配量度 “模板和弹簧”
R1代表连接关系 R1 = [(A，B) (A，C)]
R2代表上下关系 R2 = [(A，B)(A，C)]
R3代表左右关系 R3 = [(B，C)]
Ql = (A，B，C) Xl = {R1，R2，R3}
Q r = {1, 2, 3, 4} X r = (R1, R2, R3)
R1代表连接关系 R1 = [(1,2)(1,3)(1,4)(2,4)(3,4)]