计算机视觉教程（第3版）第13章

计算机视觉教程（第3版）●章毓晋

从视觉的角度看，“视”应该是有目的的“视”，即要根据一定的知识（包括对目标的描述）借助图像去场景中寻找符合要求的目标；“觉”应该是带识别的“觉”，即要从输入图像中抽取目标的特性，再与已有的目标模型进行匹配，从而达到识别景物、理解场景含义的目的

匹配可在不同（抽象）层次上进行

广义匹配比较抽象，主要与图像目标或目标的性质有关第13章

广义匹配目录contents13.1

目标匹配13.2

动态模式匹配13.3 关系匹配13.4

图同构匹配13.1目标匹配 描述点集之间的匹配程度或相似性几何意义：如果点集A和B之间的豪斯道夫距离为d，则对两点集中的任意一个点，都可在以该点为中心、以d为半径的圆中找到另一个点集里的至少一个点豪斯道夫距离13.1目标匹配 对噪声点或点集的外野点（outline）很敏感

采用统计平均的概念，用平均值代替最大值，称为改进的豪斯道夫距离（MHD）豪斯道夫距离13.1目标匹配

MHD具有对噪声和点集的外野点不敏感的优点，但对点在点集中的分布还不敏感豪斯道夫距离13.1目标匹配豪斯道夫距离用标准方差改进的豪斯道夫距离13.1目标匹配结构匹配量度

“模板和弹簧”CT表示模板和待匹配结构

之间的不相似性CS表示待匹配结构和目标部件之间的不相似性CM表示对遗漏部件的惩罚13.1目标匹配字符串(1)

S

aA（起始符号可用元素a和变量A来替换）(2)

A

bS（变量A可用元素b和起始符号S来替换）(3)

A

b（变量A可以用单个元素b来替换）13.1目标匹配字符串匹配

借助字符串匹配来匹配两个目标区域的轮廓

用M表示两字符串间已匹配的总次数，则未匹配字符的个数为

A和B之间一个简单的匹配量度为13.1目标匹配字符串匹配应用

匹配两个视频片段序列V1和V2

两个序列的长度相同，即L1=L2

两个序列的长度不同，考虑如何选取匹配时间起点，移动时间起点t13.1目标匹配惯量等效椭圆匹配目标匹配

目标

惯量椭圆

等效椭圆

由于图像中的每个目标都可用它的等效椭圆来表示，所以对目标的配准问题就可转化为对其等效椭圆的匹配13.1目标匹配惯量等效椭圆匹配目标匹配尺度变换旋转变换平移变换13.1目标匹配例13.1.2细胞图像配准实例

匹配两个连续切片上对应同一细胞的两个相邻剖面图13.1目标匹配例13.1.2细胞图像配准实例

对横跨10个连续切片的细胞剖面配准的结果13.2动态模式匹配匹配流程13.2动态模式匹配绝对模式和相对模式

绝对模式包含绝对坐标，具有旋转不变性13.2动态模式匹配绝对模式和相对模式

相对模式不仅具有旋转不变性，而且也具有平移不变性13.2动态模式匹配绝对模式和相对模式

例13.2.1动态模式匹配实例13.3关系匹配两个关系集Xl和Xr，其中Xl属于待匹配对像，Xr属于模型R1代表连接关系R1

=[(A，B)(A，C)]R2代表上下关系R2

=[(A，B)(A，C)]R3代表左右关系R3

=[(B，C)]Qr

={1,2,3,4}Xr=(R1,R2,R3)Ql

=(A，B，C)Xl

={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)(4,3)]13.3关系匹配Xl和Xr之间的距离记为dis(Xl,Xr)4种误差对应变换关系表达13.3关系匹配

Xl和Xr之间的距离记为dis(Xl,Xr)误差加权和以项计误差对应误差最小的映射对应误差最小的一组映射13.3关系匹配

(1)相同关系 (2)对应映射13.3关系匹配

(3)映射系列

(4)所属模型13.4图同构匹配基本定义

图G：由有限非空顶点/结点集合V(G)及有限边/边线集合E(G)组成

有色图G：

C为顶点色性集

S为边线色性集13.4图同构匹配图的几何表达

将图的顶点用圆点表示，将边线用连接顶点的直线或曲线表示。边数大于等于1的图可以有无穷多个几何表达

V(G)={A,B,C}， E(G)={a,b,c,d}，其中a

AB，b

AB， c

BC，d

CC13.4图同构匹配子图和母图13.4图同构匹配13.4图同构匹配图的恒等和同构

同构：具有相同的几何表达但不恒等恒等同构13.4图同构匹配同构的判定

(1)全图同构：B1和B2之间一对一的映射

(2)子图同构：B1子图和B2的全图之间的同构

(3)双子图同构：B1的各子图和B2的各子图教程作者（章毓晋）联系信息通信地址：北京清华大学电子工程系邮政编码：100084

办公地址：清华大学