第13章广义匹配(计算机视觉)课件.ppt
计计 算算 机机 视视 觉觉 教教 程程章毓晋章毓晋13-2第13章第第13章章 广义匹配广义匹配13.1 目标匹配13.2 动态模式匹配13.3 关系匹配13.4 图同构匹配13-3第13章13.1 目标匹配13.1.1 匹配的度量13.1.2字符串匹配13.1.3惯量等效椭圆匹配13-4第13章13.1.1 匹配的度量1.Hausdorff距离距离描述点集之间的匹配程度或相似性几几何何意意义义：如果点集A和B之间的Hausdorff距离为d，那么在每个点集中都可以找到一个点，使另一个点集的各点都落在以该点为中心、以d为半径的圆中13-5第13章13-6第13章13.1.1 匹配的度量1.Hausdorff距离距离 MHD具有对噪声和点集的外野点不敏感的优点，但对点在点集中的分布还不敏感13-7第13章13.1.1 匹配的度量 13-8第13章13.1.1 匹配的度量2.结构匹配量度结构匹配量度“模板和弹簧”参考结构和待匹配结构之间的匹配一个按照其优度定量了的对应 13-9第13章13-10第13章13.1.2 字符串匹配2.字符串匹配字符串匹配借助字符串匹配字符串匹配来匹配两个目标区域的轮廓用M表示两字符串间已匹配的总次数，则未匹配字符的个数为A和B之间一个简单的匹配量度为13-11第13章13.1.2 字符串匹配3.字符串匹配应用字符串匹配应用匹配两个视频片段序列V1和V2两个序列的长度相同，即L1=L2两个序列的长度不同，考虑如何选取匹配时间起点，移动时间起点t13-12第13章13-13第13章13.1.3 惯量等效椭圆匹配3.字符串匹配应用字符串匹配应用旋转变换尺度变换 13-14第13章13-15第13章13.1.3 惯量等效椭圆匹配3.字符串匹配应用字符串匹配应用对横跨10个连续切片的细胞剖面配准的结果 13-16第13章13.2 动态模式匹配1.匹配流程匹配流程13-17第13章13-18第13章13.2 动态模式匹配2.绝对模式和相对模式绝对模式和相对模式相对模式不仅具有旋转不变性，而且也具有平移不变性13-19第13章13.2 动态模式匹配2.绝对模式和相对模式绝对模式和相对模式动态模式匹配实例13-20第13章13.3 关系匹配13.3.1 关系表达和距离13.3.2 关系匹配模型13-21第13章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)(4，3)13-22第13章13.3.1 关系表达和距离Xl和Xr之间的距离记为dis(Xl,Xr)13-23第13章13-24第13章13.3.2 关系匹配模型(1)(2)13-25第13章13.3.2 关系匹配模型(3)(4)13-26第13章13.4 图同构匹配13.4.1 图论基础13.4.2 图同构和匹配13-27第13章13-28第13章13.4.1 图论基础2.图的几何表达图的几何表达将图的顶点用圆点表示，将边线用连接顶点的直线或曲线表示V(G)=A,B,C，E(G)=a,b,c,d，其中a AB，b AB，c BC，d CC13-29第13章13.4.1 图论基础3.子图和母图子图和母图13-30第13章13-31第13章13.4.2 图同构和匹配1.图的恒等和同构图的恒等和同构同构：同构：具有相同的几何表达但不恒等13-32第13章13.4.2 图同构和匹配2.同构的判定同构的判定(1)全图同构：B1和B2之间一对一的映射(2)子图同构：B1子图和B2的全图之间的同构(3)双子图同构：B1的各子图和B2的各子图13-33第13章教程作者（章毓晋）联系信息教程作者（章毓晋）联系信息F 通信地址：北京清华大学电子工程系F 邮政编码：100084F 办公地址：清华大学东主楼，9区307室F 办公电话：F 传真号码：F 电子邮件：zhang-F 个人主页：
