【教学课件】第10章广义匹配.ppt

《【教学课件】第10章广义匹配.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第10章广义匹配.ppt（41页珍藏版）》请在三一办公上搜索。

1、第10章广义匹配,10.1匹配基础10.2目标匹配10.3动态模式匹配10.4关系匹配10.5图同构10.6线条图标记,10.1匹配基础,匹配的作用：匹配用储存在计算机中的模型去识别输入的未知视觉模式，并最终建立对输入的解释“视”应该是有目的的“视”，即要根据一定的知识（包括对目标的描述）借助图象去场景中寻找符合要求的目标“觉”应该是带识别的“觉”，即要从输入图象中抽取目标的特性，再与已有的目标模型进行匹配，从而达到理解场景含义的目的,10.1匹配基础,10.1.1匹配策略和类别10.1.2匹配和配准,匹配策略和类别,匹配通过映射来进行（取决于映射函数）(1)目标空间的匹配目标O直接通过对透视

2、变换TO1和TO2的求逆来重建(2)图象空间的匹配直接将图象I1和I2用映射函数T12联系起来目标模型是隐含地包含在T12的建立过程中,匹配策略和类别,根据所用图象模型来分类(1)基于光栅的匹配直接比较灰度或灰度函数来找到映射函数(2)基于特征的匹配提取图象的显著特征并进行几何映射(3)基于关系的匹配基于特征间拓扑关系的相似性,匹配和配准,配准：含义常较窄，主要指在图象空间，或者说比较低层表达的匹配配准技术常由以下四个元素所决定(1)确定用来进行配准所用特征的特征空间(2)限制搜索范围，确定使搜索过程有可能有解的搜索空间(3)对搜索空间进行扫描的搜索策略(4)用来确定匹配是否成立的相似测度,1

3、0.2目标匹配,10.2.1匹配的度量10.2.2字符串匹配 10.2.3形状数匹配 10.2.4惯量等效椭圆匹配,1.Hausdorff 距离：目标的匹配在一定意义上是点集的匹配 Hausdorff距离的几何意义如果点集A和B之间的Hausdorff距离为d，那么一个点集中的所有点将都落在另外一个点集中以任意一点为中心，以d为半径的圆中,匹配的度量,匹配的度量,1.Hausdorff距离：如上定义的Hausdorff距离对噪声点或点集的外野点（outline）很敏感 改进的Hausdorff距离用平均值代替最大值,匹配的度量,2.结构匹配量度：“模板和弹簧”的物理类比模型“模板”用“弹簧”连

4、接，“弹簧”函数描述了各“模板”间的关系匹配质量是“模板”局部拟合的优度和待匹配结构拟合参考结构而拉长“弹簧”所需能量的函数,匹配的度量,2.结构匹配量度：“模板和弹簧”的匹配量度 CT：结构模板和待匹配结构之间的不相似性 CS：待匹配结构和目标部件之间的不相似性 CM：对遗漏部件的惩罚 F(.)：将参考模板变换为待匹配结构部件的映射,字符串匹配,将两个区域边界A和B分别编码为字符串a1a2an和b1b2bm 从a1和b1开始，如果在第k个位置有ak=bk，则称两边界有一次匹配未匹配符号的个数为：相似性量度,形状数匹配,形状数是数值最小的边界链码的差分码 两个形状 A 和 B 之间的相似度 k

5、 是这两个形状数之间的最大公共形状数如果 S4(A)=S4(B)，S6(A)=S6(B)，Sk(A)=Sk(B)，Sk+2(A)Sk+2(B)，则 A 和 B 的相似度就是 k 两个形状间的距离：它们相似度的倒数：,形状数匹配,比较形状数，确定相似度 6个不同的形状 相似树 相似矩阵,惯量等效椭圆匹配,基于目标区域进行 目标都可用它的等效椭圆来表示平移、旋转和尺度变换所需的参数 平移参数可根据两个等效椭圆的中心坐标差算得,惯量等效椭圆匹配,旋转参数可根据两个椭圆朝向角度差算得 朝向角f 借助惯量椭圆两主轴的斜率k和l求得 尺度变换参数可根据两个椭圆长轴长度比例算得 等效椭圆半长主轴的长度a,1

6、0.3动态模式匹配,需匹配的表达是在匹配过程中动态建立 以由切片图象重建3-D细胞为例,10.3动态模式匹配,绝对模式,10.3动态模式匹配,相对模式,10.4关系匹配,场景可以分解为多个物体或各个组成元件，它们之间存在着不同类型的关系设有两个关系集：X l和X rXl=R1，R2，R3 连接关系，R1=(A，B)(A，C)上下关系，R2=(A，B)(A，C)左右关系，R3=(B，C),10.4关系匹配,考虑另一个物体Qr=1，2，3，4 Xr=(R1，R2，R3)连接关系：R1=(1，2)(1，3)(1，4)(2，4)(3，4)上下关系：R2=(1，2)(1，3)(1，4)左右关系：R3=(

7、2，3)(2，4)(4，3),Xl和Xr的匹配是两集合各对相应关系的匹配 用Rl和Rr分别代表相应的关系表达p为S对T的对应变换，p1为T对S的对应变换定义运算符号代表复合（composite）运算,10.4关系匹配,dis(Xl,Xr)：Xl和Xr之间的距离 由各对相应关系表达对应项的差异组成 dis(Rl,Rr)：关系表达的对应项之间的距离Rl和Rr之间的距离就是各项误差的加权和,10.4关系匹配,用C(E)表示E中以项计的误差 需要寻求的对应变换p应满足要匹配两个关系集Xl和Xr，则应找到一系列对应变换pj使得下式得到满足,10.4关系匹配,P241例,(1)确定相同关系（元件间关系）(

8、2)确定匹配关系的对应映射（关系表达对应）,10.4关系匹配,(3)确定匹配关系集的对应映射系列(4)确定所属模型,10.4关系匹配,10.5图同构,图论简介图同构和匹配,图论简介,1.基本定义图G定义为由有限非空顶点集合V(G)及有限边集合E(G)组成，记为G=V(G),E(G)顶点u和v，边e：e=uv或e=vu 如果两条边有相同的两端点，就称它们为重边或平行边 如果一条边的两端点相同，就称它为环，否则称为棱,图论简介,1.基本定义顶点的色性（指顶点用不同的颜色标注）边的色性（指边用不同的颜色标注）有色图G：顶点集顶点色性集 边线集边线色性集,图论简介,2.图的几何表达 顶点：圆点；边线：

9、连接顶点的直线或曲线边数大于等于1的图可有无穷多个几何表达,V(G)=A,B,C,E(G)=a,b,c,d,边a，b，c均为棱,边d为环,边a和b为重边,图论简介,2.图的几何表达 有色图表达示例顶点色性用顶点形状区别连线色性用连线线型区别,图论简介,3.子图 子图H G：V(H)V(G)，E(H)E(G)生成子图：H G 且V(H)=V(G)去掉所有重边和环而得到的简单生成子图称为基础简单图（仅(d)）,图同构和匹配,1.图的恒等和同构 图G和H恒等：V(G)=V(H)，E(G)=E(H)恒等的图可用相同的几何表达来表示 用相同几何表达来表示的并不一定恒等,图同构和匹配,1.图的恒等和同构

10、图G和H同构：记为G H 在V(G)和V(H)，E(G)和E(H)之间有如下映射 P和Q相关联 Q(e)=P(u)P(v)，e=uv E(G),图同构和匹配,2.同构的判定(1)全图同构：(a)(b)(2)子图同构：(a)(c)(3)双子图同构：(a)(d),10.6线条图标记,1.轮廓标记(1)刃边（blade）(2)翼边（limb）(3)折痕（crease）(4)痕迹（mark）(5)阴影（shade）,10.6线条图标记,2.结构推理 借助2-D图象中的轮廓结构来对3-D目标的结构进行推理分析,10.6线条图标记,2.结构推理 四类16种边线连接的（拓扑）组合类型,10.6线条图标记,3.回溯标记 自动标记线条图的一种算法给2-D线条图中的每条边赋一个标记将边排成序列，以深度优先的方式生成通路依次对每条边进行所有可能的标记检验新标记与其他边标记的一致性得到一种标记结果（得到一条到达树叶的完全通路）例10.6.2,通信地址：北京清华大学电子工程系 邮政编码：100084 办公地址：清华大学东主楼，9区307室 办公电话：传真号码：电子邮件：个人主页：实验室网：,联 系 信 息,