【文章內(nèi)容簡介】 lafman 等 [34]用 基于 k–means 聚類 的 體類型網(wǎng)格分割方法 對網(wǎng)格曲面進行變形操作。他們提出的 k–means 聚類 分割過程如下： (a)計算每個 網(wǎng)格對之間的距離 ； (b)計算出網(wǎng)格單元 的 初始聚類中心 ； (c)對 所有網(wǎng)格單元 ， 計算它們與最近聚類中心之間的距離 ； (d)通過 使 網(wǎng)格單元與 其 聚類中心之間的距離 為 最小 來更新聚類中心 ； (e) 重復(fù)步驟 (a)至 (d)， 直 到 聚類中心不再發(fā)生變化為止。 類似 于Shlafman 等 [34]提出的 基于 k–means 聚類網(wǎng)格分割方法 ， Katz 等 [35]提出 了一種基于分層 模糊 k–means 算法 的 網(wǎng)格模型 分割方法。該方法的距離函數(shù)是 重心的測地距離 權(quán)和以及網(wǎng)格之間 角度 。在 二叉樹 分割時，網(wǎng)格被分割為兩個細(xì)分區(qū)域和一個模糊區(qū)域。由 最小割 算法將模糊區(qū)域切割歸類到兩個細(xì)分區(qū)域，兩個細(xì)分區(qū)域被較深的凹面分離。分層 模糊 k–means 算法 的優(yōu)點是模型被分割為有意義的組成部分，并且深度凹面符合極小值規(guī)則；缺點是分割邊界沒有被凹面包圍，最小切割不是總能找到最優(yōu)分割邊界。 三維 實體 模型 分割 工程應(yīng)用中的三維模型大多是參數(shù)化的 CAD實體模型 ，主要有 CSG和 Brep兩 種 表達(dá)方式。前者通過 原始體素的布爾運算 生成 實體模型，表達(dá)方式 比較 直觀，容易理解 ， 但 存在著 CSG 描述 的 不唯一 性問題。 Brep 表達(dá) 包含有模型的幾何和拓?fù)湫畔?，實體與模型之間是一一 對應(yīng) 關(guān)系 。但是幾何和拓?fù)湫畔?以私有的數(shù)據(jù)格式存儲，在不同的 CAD 系統(tǒng)之間轉(zhuǎn)換時 ， 存在著數(shù)據(jù)丟失的情況。 實體模型分割 是將形狀復(fù)雜的物體分解為簡單的體元素?，F(xiàn)有的體分割相關(guān)研究主要集中在加工特征識別領(lǐng)域 ，常用的體分解方法有凸分解 [36,37]和基于殼的分解 [38,39]。 凸分解方法遞歸 地將初始體模型 分解 為 凸殼 、以及 凸殼 與原來形體之間的毛 坯去除體 。體方法通常用二叉樹描述初始體模型，由布爾運算的并集和差集運算來實現(xiàn)模型體的分解 。然而 ，由于很難定義曲面的凸殼， 凸分解方法不能應(yīng)用于 具有 曲面形狀 的形體分割。 此外 ，一些在初始形體中不存在的 虛構(gòu) 面，在形體分解過程中被產(chǎn)生，這些 虛構(gòu) 的面可能使初始形體的特征失真?；跉さ姆纸夥椒▽⒊跏俭w模型分解為不包含凹邊的最大體元素。首先，初始體模型被分解為具有簡單形狀的殼元素；接著，一些殼元素被合并，以便能夠找到最大體元素。該方法中， 初始體模型分解僅由布爾并運算來完成，并且能夠分割具有二次曲面的體模型。然而，由于體分解過程中僅僅應(yīng)用了布爾并運算，很難得到理想的分解結(jié)果。另外，合并殼元素的過程中尋找最大體元素所需要的時間，與殼元素的數(shù)量存在著指數(shù)級的關(guān)系。 Shah 等 [40]使用半空劃分將實體模型分割成最大凸體，由模型表面的半空間交叉實現(xiàn)模型的半空間劃分。然而，使用彎曲表面分割實體模型時不是總能找到半空間劃分操作。 Sakurai 等 [41]將實體模型分解為一組單元體，然后將相關(guān)的單元體優(yōu)化組合形成最大體單元，從而實現(xiàn)實體模型分割。當(dāng)面殼的數(shù) 量較多時，該方法在合并單元體時計算效率較低。 Woo 等 [42]通過遞歸二等分實體模型和組合二分體單元的最大體單元來改善最大體分解的擴展性。 該方法在分割過程中，有時產(chǎn)生大量的不合理的細(xì)小特征，并且計算時間是指數(shù)級的。 馬等 [43]使用切割環(huán)收縮的方法分解實體模型，通過選擇特殊的切割環(huán)決定面殼的表面劃分，將實體模型分割為體單元。上述各種方法存在的問題是在模型分解過程中，往往會強行切割模型中原本不需要分割的部分而得到不合理的分割體，同時也使分割體失去了原本的設(shè)計意圖。 Dong 等 [44]通過 面延伸重構(gòu)體特征 的方法來 實現(xiàn) 多面體模型分割。 首先，通過 特征面與其鄰接面延伸求交 ， 生成新的頂點和邊 ；接著，依據(jù) 新生成的頂點和邊 、以及 模型中原有的頂點和邊 ， 構(gòu)造一個線框模型 ；最后，依據(jù) 面信息將線框模型轉(zhuǎn)化為實體模型。 這里的 特征面是指模型中具有加工特征痕跡的平面。 Sandiford 等 [45]和 Sashikumar 等 [46]在 Dong 方法的 基礎(chǔ)上 ，提出 了一種 基于面延伸和邊延伸的體重構(gòu)方法 。該方法能夠分割 具有二次曲面的模型。Li 等 [47]提出 的基于 面延伸和邊延伸的體重構(gòu) 分割 方法 ，對延伸面和 延伸邊進行了 更 為細(xì)致 的分析， 進一步 推廣了該 類 方法的 應(yīng)用 范 圍?；谘由烀婊蜓由爝叿椒ǖ?局限性在于， 延伸面和延伸邊的選擇 對模型 分割結(jié)果 有 直接影響 。 不合理 的延伸面或延伸邊選擇 ，會導(dǎo)致 模型無法封閉 。 三維模型 整體檢索 國內(nèi)外研究 現(xiàn)狀 CAD模型檢索是信息檢索的一個重要應(yīng)用。傳統(tǒng)的 CAD模型手工檢索分類，主要依賴于人的認(rèn)知對機械零件進行分類。成組技術(shù)是最為經(jīng)典的機械零件手工分類方法。眾所周知，手工分類方法是費時和易于出現(xiàn)錯誤的，并且手工分類的方法難以在企業(yè)級對數(shù)以萬計的機械零件模型進行分類。近年來，基于內(nèi)容的CAD 模型自動檢索已經(jīng)出現(xiàn) [48]。形狀描述是實現(xiàn) CAD 模 型自動檢索時最為重要的任務(wù)。形狀描述符是用簡潔的數(shù)學(xué)方法對三維模型的形狀進行抽象描述，以實現(xiàn)模型的形狀檢索。一般地，每一種整體形狀檢索方法，都有自己獨特的形狀描述符，用于表達(dá) CAD 模型的整體形狀相似性。大多數(shù)模型的整體形狀描述符可以分類為以下三種類型：數(shù)學(xué)描述符、基于視圖的描述符和基于知識的描述符。 整體形狀 數(shù)學(xué)描述符 (1) 整體特征形狀描述符 基于整體特征的形狀描述符是用整體幾何屬性的特征向量表征三維模型的整體形狀。 Paquet 等 [49]首次提出用邊界盒表征二維視圖形狀，并且使用基于弦的向量 集、基于小波變換的體積占有率等整體特征比較三維形狀。 Paquet 等 [50]和Zhang 等 [51]提出的三維形狀匹配方法使用矩作為三維實體的特征描述符。 Lou 等[52]提出的方法采用不變的主慣量評估三維形狀的相似性。 Zhang 等 [53]通過引入表面積比率、不變矩和傅里葉變換系數(shù)，對基于整體特征的三維形狀描述符進行了進一步的擴展。 Sun 等 [54]使用離散小波變換描述曲面區(qū)域的曲率和曲面邊界的徑向距離。 Kazhdan 等 [55]提出了一種基于反射對稱性的三維模型形狀描述符，它具有良好的 噪音魯棒性 和采樣分辨率。 基于 整體特征的形狀描述符的一個普遍缺陷是一類特征向量僅僅表征幾何屬性的一個方面（如不變矩、表面積比率等）。因此，基于單一特征向量的描述符并不能全面地反映模型的形狀內(nèi)容。 基于數(shù)學(xué) 變換 的 形狀 描述 符將三維模型的空域信息通過數(shù)學(xué)變換方法變換為 頻域信息 ，用變換系數(shù)表征模型的形狀特征。球面調(diào)和函數(shù)是典型的 數(shù)學(xué) 變換 的 形狀 描述 符，它用出色的調(diào)和系數(shù)近似地表征三維形狀，因而能夠更為全面地表征模型的形狀內(nèi)容?，F(xiàn)有的大部分相關(guān)工作是用基于球面調(diào)和的方法評估三維模型之間的幾何屬性的相似性 [56,57]。 Vranic 等 [56]提出了一種 基于球面調(diào)和函數(shù)的三維形狀描述符。球面調(diào)和函數(shù)主要描述模型的整體特征向量。首先使用球面傅里葉系數(shù)從已經(jīng)正交化預(yù)處理的模型中取出特征向量，接著通過比較球面調(diào)和特征向量得到相比較模型的形狀相似度。類似地，Saupe 等 [57]同時采用矩和球面調(diào)和函數(shù)評估三維模型的幾何屬性相似性。 Morris等 [58]將球面調(diào)和推廣到生物高分子領(lǐng)域，用于判定蛋白質(zhì)結(jié)構(gòu)是否具有可以利用的生化特性。他們用球面調(diào)和系數(shù)表征蛋白質(zhì)的 結(jié)合口袋 形狀，并且用系數(shù)空間的幾何距離評估結(jié)合口袋之間的相似度。 Papadakis 等 [59] 提出的 三維形狀 描述符用球面調(diào)和函數(shù)表征分析模型的 縮放和軸翻轉(zhuǎn)不變性 ，并且用連續(xù)的主元分析法表征分析模型的旋轉(zhuǎn)不變性。 基于數(shù)學(xué)變換的形狀描述 符能夠?qū)θS模型進行從粗到精 的 多分辨率 形狀表征， 與其它形狀描述 符 有著良好的互補效果 。 但 該方法要求在 數(shù)學(xué)變換前 ，需要 對 三維 模型進行規(guī)范化 的預(yù)處理 ，計算 過程比較 復(fù)雜。 (2) 基于統(tǒng)計的形狀描述 符 基于統(tǒng)計的形狀描述 符 是利用統(tǒng)計學(xué)的思想， 通過對三維形體進行采樣測量， 統(tǒng)計 具有一定形狀辨識 能 力、并能 反映模型本質(zhì)內(nèi)容的 形狀 特征出現(xiàn)頻率，以 統(tǒng)計分布曲線 或 統(tǒng)計直方圖來表征 三維 模型的形狀 。 Osada 等 [60]較早用整體形狀的 概率分布 表征三維模型的形狀。 概率分布 是使用幾何函數(shù) A3 和 D2 等在模型表面進行隨機采樣，統(tǒng)計幾何函數(shù)數(shù)值出現(xiàn)的次數(shù)。這里 A3 是測量模型表面 3 個隨機點之間形成的角度， D2 是測量模型表面任意 2 個隨機點之間的距離。通過評估兩個相比較模型的 概率分布 ，得到相比較模型的相似度。 Ip 等 [61]通過將 D2 函數(shù)細(xì)分為 IN、 OUT 和 MIXED 三種類型，將 初始的 形狀分布 統(tǒng)計 方法 推廣 到 CAD 模型 形狀檢索 。 IN 是指 連接 模型上 2 個點的線段完全在實體模型 內(nèi) ； OUT 是指 連接 模型上 2 個點的線段完全在模型外；MIXED 是指 連接 模型上 2 個點的線段 穿過 模型。由 D IN、 OUT 和 MIXED的 加權(quán) 和 來度量 相比較 CAD 模型 的 相似度。該方法 在檢索 CAD 實體模型時，具有一定的精度。其缺點是 需要 將每條 線段與三維模型求交 ，以判定其類型。 概率分布 方法的 優(yōu) 點是 幾何 函數(shù)簡單， 描述符生成過程中不需要 姿態(tài)調(diào)整 和 模型配準(zhǔn)等 預(yù)處理步驟 。 另一類 基于統(tǒng)計的形狀描述 符 是形狀直方圖。它 最早來源于檢索二維多邊形的截面編碼技術(shù)，其基本思想是將模型進行三維分割，并用編碼的方式對分割形成的部分進行描述。最基本的分割技術(shù)是 Ankerst 等 [62]提出的 同心球分割 、 扇 形分割以及同心球 與 扇形相結(jié)合的空間分割方法 。模型中每個分割形成的部分，在空間 占據(jù)的比例 被 編碼成一個向量 ，作為模型形狀比較的對象。 同心球分割 得到的 形狀直方圖具有旋轉(zhuǎn)不變性；扇形分割 得到 的形狀直方圖具有比例不變性；同心球與扇形相結(jié)合的分割方法 得到的形狀直方圖的形狀辨識能力較強，但不具備旋轉(zhuǎn)不變性和比例不變性 。 Kriegel 等 [63]提出了一種基于體素化模型的形狀直方圖描述符。由于該方法需要考慮 的體素駐留 哪 在一個分區(qū) 比較明確，導(dǎo)致 計算 的復(fù)雜度比較低 。 其它類型的基于統(tǒng)計的描述符有基于弦的測量 [64]、標(biāo)量函數(shù)分布 [65]、球映射信號 [66]和基于密度的描述符 [67]等。總的來說， 形狀直方圖 表征 三維模型的形狀 比較 直觀 ， 但 這類方法 需要 在分割前對模型進行 姿勢規(guī)范化 的 預(yù)處理 ，并且 對于 某些 形狀復(fù)雜的 三維 模型，由于 它們的 形狀直方圖 近似于 鐘形曲線，導(dǎo)致形狀直方圖 比較 相似的 兩 個復(fù)雜模型 ，它們的實際 形狀 可能 很不相似 ， 圖 給出這樣一個實例。在 圖 中，三維模型 heat_exchanger1 的 D2 形狀分布直方圖 與 grip 的 D2 形狀分布 直方圖 更為相似，而實際的模型是 heat_exchanger1與 heat_exchanger2 更為相似。 圖 形狀直方圖 對某些 復(fù)雜模型 形狀辨識能力不足的實例 [68] 基于視 圖 的 整體形狀 描述符 與 中的整體形狀數(shù)學(xué)描述符不同， 基于視 圖 的整體形狀描述符 是人類使用不同的感知來評估三維模型的相似性?；谌说母兄绻麅蓚€物體從每個視角看起來都相似，或者從三維視角觀察到兩個物體具有很強的相似性，我們認(rèn)為這兩個三維物體是相似的。 （ 1）二維視圖形狀描述符 近二十多年來，基于內(nèi)容的圖像檢索技術(shù)已經(jīng)成為了一個活躍的研究主題。這些圖像檢索方法大多將從圖像中取出的顏色、紋理或 二維 輪廓等作 為形狀描述符來評估二維圖像之間的相似度，其中的大部分方法能夠推廣應(yīng)用到三維模型的形狀檢索?；诙S視圖的三維模型檢索的理論依據(jù)是：兩 個三維模型 如果是 相似的， 那么 從任意視角看它們都應(yīng)該是相似的。 一些不同的二維視圖描述符被用于表征模型的形狀，并且被作為模型形狀比較的間接比較對象。 Funkhouser 等 [69]和 Garc237。a 等 [70]使用 模型的二維輪廓 （ silhouettes） 視 圖作為圖像形狀描述符。與人們常用三個二維視圖表征模型的形狀不同， Funkhouser 等 [69]用 從 十三 個視 角 方向 投影 獲得 的 二維視圖 表征模 型形狀，這十三個視角方向分別對應(yīng)于模型所在立方體的三個側(cè)面、四個頂點和六條邊。 Chen 等 [71]提出的擴展二維輪廓視圖描述符使用光場 投影 得到的十個二維 輪廓 視圖表征模型的形狀。具體方法是選擇十個均勻分布的光場進行投影，每個光場由一個半球里的十二面體的二十個頂點發(fā)光，投影得到十張二維輪廓 視圖 。光場描述符能夠有效地過濾高頻率的噪聲，具有 旋轉(zhuǎn)不變性 。 Vranic 等 [56]用視平面與物體之間的距離 作為模型的形狀描述符。他們認(rèn)為，在 正交三維模型的圖像中，較暗的像素顯示視平面與物體之間的距離較大 。 Barton 等 [72]提 出的機械零件模型檢索方法用正交投影輪廓表征三維模型的形狀。為了準(zhǔn)確地表征 CAD 模型 的形狀， Pu等 [73] 提出的 基于圖樣 （ drawing）的 二維視圖 形狀描述符，同時考慮了 二維視圖