第10章廣義匹配-資料下載頁
2025-07-20 06:42本頁面
【正文】 ：連接頂點的直線或曲線 ? 邊數(shù)大于等于 1的圖可有無窮多個幾何表達 V(G) = {A, B, C} E(G) = {a, b, c, d} 邊 a， b， c均為棱 邊 d為環(huán) 邊 a和 b為重邊 第 32頁 第 9講 章毓晉 (THEEIE) 圖論簡介 2. 圖的幾何表達 ? 有色圖表達示例 頂點色性用 頂 點形狀區(qū)別 連線色性用連線線型區(qū)別 B C連接關系A上下關系左右關系14元件類型1元件類型2元件類型3 2 3第 33頁 第 9講 章毓晉 (THEEIE) 圖論簡介 3. 子圖 ? 子圖 H ? G ： V(H) ? V(G)， E(H) ? E(G) ? 生成子圖： H ? G 且 V(H) = V(G) ? 去掉所有重邊和環(huán)而得到的簡單生成子圖稱 為基礎簡單圖（僅 (d)） 第 34頁 第 9講 章毓晉 (THEEIE) 圖同構和匹配 1. 圖的恒等和同構 ? 圖 G和 H恒等： V(G) = V(H)， E(G) = E(H) ? 恒等的圖可用相同的幾何表達來表示 ? 用相同幾何表達來表示的并不一定恒等 第 35頁 第 9講 章毓晉 (THEEIE) 圖同構和匹配 1. 圖的恒等和同構 ? 圖 G和 H同構：記為 G ? H ? 在 V(G)和 V(H)， E(G)和 E(H)之間有如下映射 P和 Q相關聯(lián) Q(e) = P(u)P(v)， ?e = uv ? E(G) )()(: HVGVP ?)()(: HEGEQ ?第 36頁 第 9講 章毓晉 (THEEIE) 圖同構和匹配 2. 同構的判定 (1) 全圖同構： (a) ? (b) (2) 子圖同構： (a) ? (c) (3) 雙子圖同構： (a) ? (d) 第 37頁 第 9講 章毓晉 (THEEIE) 線條圖標記 1. 輪廓標記 (1) 刃邊（ blade） (2) 翼邊（ limb） (3) 折痕（ crease） (4) 痕跡（ mark） (5) 陰影（ shade） 第 38頁 第 9講 章毓晉 (THEEIE) 線條圖標記 2. 結(jié)構推理 借助 2D圖象中的輪廓結(jié)構來對 3D目標的結(jié)構進行推理分析 第 39頁 第 9講 章毓晉 (THEEIE) 線條圖標記 2. 結(jié)構推理 四類 16種邊線連接的（拓撲）組合類型 第 40頁 第 9講 章毓晉 (THEEIE) 線條圖標記 3. 回溯標記 ? 自動標記線條圖的一種算法 ? 給 2D線條圖中的每條邊賦一個標記 ? 將邊排成序列，以深度優(yōu)先的方式生成通路 ? 依次對每條邊進行所有可能的標記 ? 檢驗新標記與其他邊標記的一致性 ? 得到一種標記結(jié)果（得到一條到達樹葉的完 全通路） {例 } 第 41頁 第 9講 章毓晉 (THEEIE) ? 通信地址： 北京清華大學電子工程系 ? 郵政編碼： 100084 ? 辦公地址： 清華大學東主樓， 9區(qū) 307室 ? 辦公電話 ： (010)62781430 ? 傳真號碼 ： (010)62770317 ? 電子郵件： ? 個人主頁： ~zhangyujin/ ? 實驗室網(wǎng)： 聯(lián) 系 信 息
電大資料相關推薦
鄂ICP備17016276號-1