《第10章-广义匹配-图像工程(第2版)下册图像理解教学课件.ppt》由会员分享，可在线阅读，更多相关《第10章-广义匹配-图像工程(第2版)下册图像理解教学课件.ppt（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、章毓晋清华大学电子工程系 100084 北京图象工程（下）第2页第9讲第第1010章章广义匹配广义匹配10.1匹配基础10.2目标匹配10.3动态模式匹配10.4关系匹配10.5图同构10.6线条图标记章毓晋(TH-EE-IE)第3页第9讲10.1匹配基础匹配基础匹配的作用：匹配用储存在计算机中的模型去识别输入的未知视觉模式，并最终建立对输入的解释“视”应该是有目的的“视”，即要根据一定的知识（包括对目标的描述）借助图象去场景中寻找符合要求的目标“觉”应该是带识别的“觉”，即要从输入图象中抽取目标的特性，再与已有的目标模型进行匹配，从而达到理解场景含义的目的 章毓晋(TH-EE-IE)第4页第
2、9讲10.1匹配基础匹配基础 10.1.1匹配策略和类别10.1.2匹配和配准章毓晋(TH-EE-IE)第5页第9讲第6页第9讲10.1.1匹配策略和类别根据所用图象模型来分类(1)基于光栅的匹配基于光栅的匹配直接比较灰度或灰度函数来找到映射函数(2)基于特征的匹配基于特征的匹配提取图象的显著特征并进行几何映射(3)基于关系的匹配基于关系的匹配基于特征间拓扑关系的相似性 章毓晋(TH-EE-IE)第7页第9讲10.1.2匹配和配准匹配和配准配准：含义常较窄，主要指在图象空间，或者说比较低层表达的匹配配准技术常由以下四个元素所决定配准技术常由以下四个元素所决定 (1)确定用来进行配准所用特征的特
3、征空间(2)限制搜索范围，确定使搜索过程有可能有解的搜索空间(3)对搜索空间进行扫描的搜索策略(4)用来确定匹配是否成立的相似测度 章毓晋(TH-EE-IE)第8页第9讲10.2目标匹配目标匹配 10.2.1匹配的度量10.2.2字符串匹配 10.2.3形状数匹配 10.2.4惯量等效椭圆匹配 章毓晋(TH-EE-IE)第9页第9讲第10页第9讲10.2.1匹配的度量1.Hausdorff距离：如上定义的Hausdorff距离对噪声点或点集的外野点（outline）很敏感 改进的改进的Hausdorff距离距离用平均值代替最大值 章毓晋(TH-EE-IE)第11页第9讲10.2.1匹配的度量2
4、.结构匹配量度：“模板和弹簧”的物理类比模型“模板”用“弹簧”连接，“弹簧”函数描述了各“模板”间的关系匹配质量是“模板”局部拟合的优度和待匹配结构拟合参考结构而拉长“弹簧”所需能量的函数 章毓晋(TH-EE-IE)第12页第9讲第13页第9讲10.2.2字符串匹配 将两个区域边界A和B分别编码为字符串a1a2an和b1b2bm 从a1和b1开始，如果在第k个位置有ak=bk，则称两边界有一次匹配未匹配符号的个数为：相似性量度 章毓晋(TH-EE-IE)第14页第9讲第15页第9讲10.2.3形状数匹配 比较形状数，确定相似度 6个不同的形状 相似树 相似矩阵章毓晋(TH-EE-IE)第16页
5、第9讲10.2.4惯量等效椭圆匹配 基于目标区域进行 目标都可用它的等效椭圆来表示平移、旋转和尺度变换所需的参数平移、旋转和尺度变换所需的参数 平移参数可根据两个等效椭圆的中心坐标差算得 章毓晋(TH-EE-IE)第17页第9讲第18页第9讲10.3动态模式匹配动态模式匹配需匹配的表达是在匹配过程中动态建立 以由切片图象重建3-D细胞为例 章毓晋(TH-EE-IE)第19页第9讲10.3动态模式匹配动态模式匹配绝对模式章毓晋(TH-EE-IE)第20页第9讲10.3动态模式匹配动态模式匹配相对模式章毓晋(TH-EE-IE)第21页第9讲10.4关系匹配关系匹配场景可以分解为多个物体或各个组成元
6、件，它们之间存在着不同类型的关系设有两个关系集：X l和X rXl=R1，R2，R3 连接关系，R1=(A，B)(A，C)上下关系，R2=(A，B)(A，C)左右关系，R3=(B，C)章毓晋(TH-EE-IE)第22页第9讲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=(2，3)(2，4)(4，3)章毓晋(TH-EE-IE)第23页第9讲第24页第9讲dis(Xl,Xr)：Xl和Xr之间的距离 由各对相应关系表达对应项的差异组成
7、 dis(Rl,Rr)：关系表达的对应项之间的距离Rl和Rr之间的距离就是各项误差的加权和 10.4关系匹配关系匹配章毓晋(TH-EE-IE)第25页第9讲用C(E)表示E中以项计的误差 需要寻求的对应变换p应满足要匹配两个关系集Xl和Xr，则应找到一系列对应变换pj使得下式得到满足 10.4关系匹配关系匹配P241例 章毓晋(TH-EE-IE)第26页第9讲(1)确定相同关系（元件间关系）(2)确定匹配关系的对应映射（关系表达对应）10.4关系匹配关系匹配章毓晋(TH-EE-IE)第27页第9讲第28页第9讲10.5图同构图同构10.5.1图论简介10.5.2图同构和匹配章毓晋(TH-EE-
8、IE)第29页第9讲10.5.1图论简介1.基本定义图G定义为由有限非空顶点集合V(G)及有限边集合E(G)组成，记为G=V(G),E(G)顶点u和v，边e：e=uv或e=vu 如果两条边有相同的两端点，就称它们为重边或平行边 如果一条边的两端点相同，就称它为环，否则称为棱章毓晋(TH-EE-IE)第30页第9讲第31页第9讲10.5.1图论简介2.图的几何表达 顶点：圆点；边线：连接顶点的直线或曲线边数大于等于1的图可有无穷多个几何表达 V(G)=A,B,C E(G)=a,b,c,d 边a，b，c均为棱 边d为环边a和b为重边章毓晋(TH-EE-IE)第32页第9讲10.5.1图论简介2.图
9、的几何表达 有色图表达示例顶点色性用顶点形状区别连线色性用连线线型区别 章毓晋(TH-EE-IE)第33页第9讲10.5.1图论简介3.子图 子图H G：V(H)V(G)，E(H)E(G)生成子图：H G 且V(H)=V(G)去掉所有重边和环而得到的简单生成子图称为基础简单图（仅(d)）章毓晋(TH-EE-IE)第34页第9讲10.5.2图同构和匹配1.图的恒等和同构 图G和H恒等：V(G)=V(H)，E(G)=E(H)恒等的图可用相同的几何表达来表示 用相同几何表达来表示的并不一定恒等章毓晋(TH-EE-IE)第35页第9讲10.5.2图同构和匹配1.图的恒等和同构 图G和H同构：记为G H
10、 在V(G)和V(H)，E(G)和E(H)之间有如下映射 P和Q相关联 Q(e)=P(u)P(v)，e=uv E(G)章毓晋(TH-EE-IE)第36页第9讲10.5.2图同构和匹配2.同构的判定 (1)全图同构：(a)(b)(2)子图同构：(a)(c)(3)双子图同构：(a)(d)章毓晋(TH-EE-IE)第37页第9讲10.6线条图标记线条图标记1.轮廓标记 (1)刃边（blade）(2)翼边（limb）(3)折痕（crease）(4)痕迹（mark）(5)阴影（shade）章毓晋(TH-EE-IE)第38页第9讲10.6线条图标记线条图标记2.结构推理 借助2-D图象中的轮廓结构来对3-
11、D目标的结构进行推理分析 章毓晋(TH-EE-IE)第39页第9讲10.6线条图标记线条图标记2.结构推理 四类16种边线连接的（拓扑）组合类型 章毓晋(TH-EE-IE)第40页第9讲10.6线条图标记线条图标记3.回溯标记 自动标记线条图的一种算法给2-D线条图中的每条边赋一个标记将边排成序列，以深度优先的方式生成通路依次对每条边进行所有可能的标记检验新标记与其他边标记的一致性得到一种标记结果（得到一条到达树叶的完全通路）例10.6.2 章毓晋(TH-EE-IE)第41页第9讲F 通信地址：北京清华大学电子工程系F 邮政编码：100084F 办公地址：清华大学东主楼，9区307室F 办公电话：F 传真号码：F 电子邮件：F 个人主页：/F 实验室网：联联 系系 信信 息息章毓晋(TH-EE-IE)