基于关系的匹配 - Read.PPT

第10章　广义匹配 10.1　匹配基础 10.1　匹配基础 10.1.1　匹配策略和类别 10.1.1　匹配策略和类别 10.1.2　匹配和配准 10.2　目标匹配 10.2.1　匹配的度量 10.2.1　匹配的度量 10.2.1　匹配的度量 10.2.1　匹配的度量 10.2.2　字符串匹配 10.2.3　形状数匹配 10.2.3　形状数匹配 10.2.4　惯量等效椭圆匹配 10.2.4　惯量等效椭圆匹配 10.3　动态模式匹配 10.3　动态模式匹配 10.3　动态模式匹配 10.4　关系匹配 10.4　关系匹配 10.4　关系匹配 10.4　关系匹配 10.4　关系匹配 10.4　关系匹配 10.4　关系匹配 10.5　图同构 10.5.1　图论简介 10.5.1　图论简介 10.5.1　图论简介 10.5.1　图论简介 10.5.1　图论简介 10.5.2　图同构和匹配 10.5.2　图同构和匹配 10.5.2　图同构和匹配 10.6　线条图标记 10.6　线条图标记 10.6　线条图标记 10.6　线条图标记 联 系 信 息 2.　图的几何表达 顶点：圆点；边线：连接顶点的直线或曲线 边数大于等于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.　图的恒等和同构 图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) 1.　轮廓标记 (1) 刃边（blade） (2) 翼边（limb） (3) 折痕（crease） (4) 痕迹（mark） (5) 阴影（shade） 2.　结构推理 借助2-D图象中的轮廓结构来对3-D目标的结构进行推理分析 2.　结构推理 四类16种边线连接的（拓扑）组合类型 *章毓晋 (TH-EE-IE) 第*页 第9讲 章毓晋 清华大学电子工程系 100084 北京 图象工程（下） 10.1 匹配基础 10.2 目标匹配 10.3 动态模式匹配 10.4 关系匹配 10.5 图同构 10.6 线条图标记 匹配的作用： 匹配用储存在计算机中的模型去识别输入的未知视觉模式，并最终建立对输入的解释 “视”应该是有目的的“视”，即要根据一定的知识（包括对目标的描述）借助图象去场景中寻找符合要求的目标 “觉”应该是带识别的“觉”，即要从输入图象中抽取目标的特性，再与已有的目标模型进行匹配，从而达到理解场景含义的目的 10.1.1 匹配策略和类别 10.1.2 匹配和配准 匹配通过映射来进行（取决于映射函数） (1)　目标空间的匹配 目标O直接通过对透视变 换TO1和TO2的求逆来重建 (2)　图象空间的匹配 直接将图象I1和I2用映射函数T12联系起来 目标模型是隐含地包含在T12的建立过程中 根据所用图象模型来分类 (1)　基于光栅的匹配 直接比较灰度或灰度函数来找到映射函数 (2)　基于特征的匹配 提取图象的显著特征并进行几何映射 (3)　基于关系的匹配 基于特征间拓扑关系的相似性 配准：含义常较窄，主要指在图象空间，或 者说比较低层表达的匹配 配准技术常由以下四个元素所决定 (1) 确定用来进行配准所用特征的特征空间 (2) 限制有哪些信誉好的足球投注网站范围，确定使有哪些信誉好的足球投注网站过程有可能有解 的有哪些信誉好的足球投注网站空间 (3) 对有哪些信誉好的足球投注网站空间进行扫描的有哪些信誉好的足球投注网站策略 (4) 用来确定匹配是否成立的相似测度 10.2.1 匹配的度量 10.2.2 字符串匹配 10.2.3 形状数匹配 10.2.4 惯量等效椭圆匹配 1.　Hausdorff 距离： 目标的匹配在一定意义上是点集的匹配 Hausdorff距离的几何意义 如果点集A和B之间的Ha