寧小娟，王映輝，郝雯

(西安理工大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710048)

近年來，隨著計算機(jī)視覺、人工智能技術(shù)以及機(jī)器人技術(shù)的發(fā)展，關(guān)于各種空間物體的理解和識別的研究已經(jīng)引起了越來越多的關(guān)注。特別是三維激光掃描技術(shù)的普及，基于離散點表示的空間物體成為學(xué)者們的重點研究對象。然而離散點表示的空間物體外形信息和拓?fù)浣Y(jié)構(gòu)的復(fù)雜性、物體獲取方式和外形表示方法的多樣性以及環(huán)境影響因素的多變性等，都毫無疑問地增加了計算機(jī)對空間物體的自動感知和理解的難度[1]。因此針對空間物體理解與識別的研究仍是一項富有挑戰(zhàn)性的課題。

空間物體是現(xiàn)實世界中的主要組成部分，也是人類感知世界的基本對象。所謂空間物體理解與識別是在環(huán)境感知數(shù)據(jù)獲取空間物體外形信息的基礎(chǔ)上，通過物體的特征分析與表示，利用設(shè)計的自動智能體根據(jù)視覺輸入對空間物體進(jìn)行推理，達(dá)到對視覺物體的感知和理解[2]。這項研究在很多領(lǐng)域都得到了廣泛的應(yīng)用，諸如：機(jī)器人感知導(dǎo)航[3]、人身安全和環(huán)境監(jiān)控[4-6]、醫(yī)學(xué)影像輔助診斷和計算機(jī)輔助外科手術(shù)[7]等，這些領(lǐng)域都需要輸入人類或機(jī)器可感知的視覺物體，并對真實世界中物體間的相互關(guān)系進(jìn)行推理。

人類對空間物體的感知和表達(dá)主要有兩種理論：一種是基于空間物體模型的組件(Recognition by Components)或者說對模型的結(jié)構(gòu)化描述[8-10]；另一種是基于多視點的描述[11-13]。大量的研究表明[14]，這兩種方法結(jié)合起來可以更好地表示人類對空間物體的感知和認(rèn)知。

因此，從空間物體的形狀復(fù)雜度出發(fā)，將研究對象分為：①簡單場景(只包含單目標(biāo)物體，以下簡稱為“單目標(biāo)物體”)的理解與識別；②復(fù)雜場景(包含多個目標(biāo)物體，以下簡稱為“多目標(biāo)場景”)的理解與識別。這兩者具有緊密的相關(guān)性，但應(yīng)用的側(cè)重點不同，前者多應(yīng)用在模型檢索、模型分析、曲面重建等方面，后者主要用在智能機(jī)器人控制、城市規(guī)劃、文化遺產(chǎn)保護(hù)、虛擬漫游等方面。據(jù)此，本文分別總結(jié)、闡述和分析現(xiàn)有的針對兩種不同的目標(biāo)復(fù)雜度場景的理解與識別方法，重點總結(jié)和分析現(xiàn)有方法的優(yōu)缺點，并對在此過程中所涉及的相關(guān)技術(shù)難題提出相應(yīng)的構(gòu)想和思路，進(jìn)一步指出未來的研究方向。

1 空間物體的數(shù)據(jù)獲取

對空間物體最傳統(tǒng)、最直觀的獲取方法是基于CCD相機(jī)的二維圖像拍攝。近年來隨著傳感器技術(shù)的進(jìn)步，激光掃描儀、醫(yī)學(xué)斷層成像設(shè)備、大地測量衛(wèi)星、雷達(dá)或地震勘探儀器等現(xiàn)代數(shù)據(jù)采集設(shè)備的相繼出現(xiàn)，使得物體外形信息的采集技術(shù)得到空前的進(jìn)步；尤其是各類中低檔的數(shù)字激光掃描儀價格已為許多研究單位所承受，曾經(jīng)難以實現(xiàn)或無法實現(xiàn)的測量以及復(fù)雜形狀的表達(dá)成為可能，測量精度也越來越高。這些技術(shù)為快速記錄空間物體結(jié)構(gòu)和物理信息的獲取提供了方便。

現(xiàn)有的空間物體的數(shù)據(jù)表示形式也較多，按照獲取方式的不同可以分為以下幾種數(shù)據(jù)表示方法。

1) 二維圖像(2D Image)

圖像是將三維場景中的物體經(jīng)過成像系統(tǒng)投影到二維平面而獲得的，是記錄和獲取空間物體數(shù)據(jù)表示的最為直接的方式。大多數(shù)的研究者在基于圖像的空間物體理解與識別方面展開了大量的探索研究工作。

2) 深度圖像(Range Image)

當(dāng)傳感器如掃描儀光學(xué)三角測量儀器在規(guī)則的2D采樣格上生成深度值時，深度圖像就形成了。因此，深度圖像在概念上等同于一般的灰度圖像(Intensity Image)，不同的是其中的灰度值替換為從傳感器到物理位置的距離。鑒于此，深度圖像通?？梢詫⒍S圖像信號處理中的相關(guān)操作和方法運用到三維數(shù)據(jù)處理過程中。許多的研究者致力于采用深度圖像進(jìn)行可視化的研究。

3) 點云數(shù)據(jù)(Point Cloud Data)

與傳統(tǒng)的測繪技術(shù)相比，激光掃描技術(shù)獲取空間信息數(shù)據(jù)具有快速、精度高和便于處理等優(yōu)點，利用該技術(shù)可以深入到復(fù)雜的現(xiàn)場環(huán)境及空間中進(jìn)行掃描操作，直接得到各種大型的、復(fù)雜的、不規(guī)則、標(biāo)準(zhǔn)或非標(biāo)準(zhǔn)的實體或?qū)嵕暗娜S數(shù)字幾何信息。這些幾何信息通常以原始無序的、密度分布不勻的三維空間點集的形式存在，數(shù)量從幾千到上千萬個不等，我們稱之為三維離散點集，或稱為點云數(shù)據(jù)(Point Cloud Data，簡稱為PCD)。圖1(a)給出了利用激光掃描儀獲取點云的示意圖，圖1(b)是利用拓普康GLS-1500采集的西安理工大學(xué)計算機(jī)學(xué)院的全景點云模型，數(shù)據(jù)的顏色是由其物體表面的反射強(qiáng)度來決定的。

圖1 三維點云數(shù)據(jù)的獲取

2 單目標(biāo)物體的理解與識別

單目標(biāo)物體的理解與識別主要包括兩方面的內(nèi)容：其一是形狀的分解；其二是基于形狀分解的物體理解。形狀分解是對物體形狀進(jìn)行拓?fù)湫畔⒎治龅幕A(chǔ)上進(jìn)行組成部分的拆分；而形狀理解則是在形狀分解的基礎(chǔ)上，利用組成部分之間的拓?fù)潢P(guān)系對物體形狀進(jìn)行描述，進(jìn)而探索基于語義的物體理解，形狀分解可以更好地得到物體各個組成部分的信息，是進(jìn)行物體理解與識別的關(guān)鍵一步，可為理解與識別工作提供更為直觀的感知信息。

2.1 形狀分解

形狀理解是把復(fù)雜拓?fù)浣Y(jié)構(gòu)的空間物體分解為若干個具有一定視覺意義的組成部分或者具有各自不同功能的組成部分。在圖像處理領(lǐng)域中，此過程也稱為分割，它是一個古老話題，也是一個核心問題。

形狀的分解有利于對物體整體結(jié)構(gòu)和外形進(jìn)行分析、理解和識別，除此之外還在物體的形狀簡化、匹配、變形、檢索、紋理映射、骨架提取以及模型重建等方面有著廣泛的應(yīng)用[15-18]。盡管針對圖像處理已經(jīng)有相當(dāng)?shù)难芯砍晒珜τ邳c云仍是一項具有挑戰(zhàn)性的研究課題?，F(xiàn)有的關(guān)于點云三維形狀分解的研究主要集中于網(wǎng)格模型[19-22]，這些研究依賴于網(wǎng)格模型提供的邊、面等拓?fù)湫畔?，Shamir[23]給出了一些網(wǎng)格分割方法的比較。此外有很多研究者為了利用成熟的網(wǎng)格模型分割技術(shù)，將點云直接轉(zhuǎn)化為網(wǎng)格進(jìn)行分析與理解。

2.1.1 面向多特征集的形狀分解

從三維點云表示的空間物體出發(fā)，基于輸出結(jié)果的類型不同可以將分割方法分為基于塊(Part-type Segmentation)和基于分片(Patch-type Segmentation)兩種分割算法[24]。

1) 基于塊的分割方法

基于塊的分割方法是根據(jù)人眼可感知的特征對物體進(jìn)行有意義的分解，可以得到語義方面的特征，直接用于三維幾何模型檢索、骨架提取與簡化。利用邊界信息是基于塊的分割方法中一個常用的感知特征，Katz和Tal[16]基于測地距離和角度距離生成表面元素的模糊聚類，經(jīng)過聚類之后將模糊的切割部分進(jìn)行更新。文獻(xiàn)[25] 首先提取與姿態(tài)無關(guān)的特征點，每個分割部分必須至少對應(yīng)一個特征點。Lee 等人[26]采用極小值規(guī)則找到局部特征輪廓，并將其封閉成環(huán)狀，通過選擇最典型的環(huán)，并利用基于蛇形的方法將環(huán)移動到更適合的位置，形成塊切割。

此外，還有一類方法主要利用模型的內(nèi)部特征，Mortara等人[27]將形狀分解為一般的部分和管狀部分，該方法主要利用球沿著模型的內(nèi)部做掃描運動。Attene 等[28]提出基于擬合基本圖元(例如圓柱和球體)的分割方法。另外一種考慮模型內(nèi)部特征的方法是根據(jù)骨骼結(jié)構(gòu)，如曲線骨架。Reniers和Telea[29]檢測曲線骨架的連接處，然后利用與每個曲線骨架點相關(guān)的Jordan曲線自然地將邊界分為連通的部分。Li等人[30]提出一種沿著骨架和信號平面空間掃描方法。Lien等人[31]觀察到分割和骨架化擁有相似的特征，并提出一種分割和骨架化并行的方法。

2) 基于分片的分割方法

基于分片的分割方法通常輸出一些滿足給定幾何約束特性的分割結(jié)果[24]，該方法是將網(wǎng)格曲面分解成若干拓?fù)渫哂趫A盤的多個分片，這種分割方法依賴于不同的幾何準(zhǔn)則，比如平面性、常曲率或凸性。這些分片結(jié)果通常在幾何屬性上具有一致性，因而多數(shù)應(yīng)用于曲面參數(shù)化、曲面重建等方面。

Garland等人[20]對網(wǎng)格面片進(jìn)行層次聚類，生成由平面部分組成的分片類型分割結(jié)果。Clarenz等人[32]提出一種基于面曲率的三維形狀模糊尺度分割，然而這種方法往往會在低曲率區(qū)域產(chǎn)生噪聲邊界。Borgefors等人[33]結(jié)合多分辨率結(jié)構(gòu)來計算局部厚度，進(jìn)而生成3D體素形狀的層次分割。Hisada等[34]使用骨架、去噪和濾波技術(shù)來檢測多邊形的顯著形狀特征。Mangan和Whitaker[17]利用分水嶺算法將網(wǎng)格面片分解成具有相似曲率的部分，該方法使用曲率作為高度函數(shù)。Zuckerberger等[22]提出了一種改進(jìn)的分水嶺算法，并給出了多種分割應(yīng)用。Provot等[35]通過檢測可變寬度的離散平面對體素模型進(jìn)行分割。Wang等人[36]提出了一種基于投影分析的有監(jiān)督的三維模型語義分割算法，利用一種新穎的兩類Hausdorff距離來對三維模型所投影的二值圖像進(jìn)行匹配。此算法可有效解決三維模型分析中數(shù)據(jù)源問題。

2.1.2 面向目標(biāo)函數(shù)和優(yōu)化策略的形狀分解

按照目標(biāo)函數(shù)的特點和優(yōu)化策略可以將三維模型形狀分割方法分類為三種，基于親和力的方法(Affinity-based Approaches)，基于模型擬合的方法(Model-fitting Approaches)以及基于特征的方法(Property-based Approaches)。

1) 基于親和力的方法

親和力用來定義屬于同一類的每對面片元素之間的相似性，分割算法正是基于這種相似性提出的，如：分水嶺算法(Watershed Segmentation)[17]，基于模型凸分割(Convex Decomposition)[37]，層次聚類方法(Hierarchical Clustering)[20]，k-means聚類分析[21]，模糊聚類與最小割方法(Fuzzy Clustering and Cuts)[16]，核心抽取方法(Core Extraction)[25]，Reeb圖方法(Reeb Graph)[38]，關(guān)鍵點分析方法(Visual Salience)[39]，隨機(jī)走動方法(Random Walk)[40]，區(qū)域生長(Region Growing)[41]，模型簡化(Decomposing polygon meshes)[30]，隨機(jī)切割方法[42]，圖割的方法[43-45]等。這類方法需要估計兩個面片之間的目標(biāo)函數(shù)，為了對目標(biāo)函數(shù)進(jìn)行合理的評估，通常需要大量的形狀上下文語義。

2) 基于模型擬合的方法

該方法假設(shè)分割的每一部分都可以由不同的參數(shù)化模型獨立產(chǎn)生。在這種情況下對模型進(jìn)行分割，通?？梢源_定模型的類型和相應(yīng)的最佳擬合的模型參數(shù)。相反，如果給定一個已知的模型也可以相應(yīng)地分類網(wǎng)格面片，從而達(dá)到分割的目的。在該類型的分割方法中，典型的優(yōu)化整個分割的方法主要包括：區(qū)域生長[46]，基于變化的[47-48]和基于層次的方法[28]。這類方法通常無法滿足諸如對稱性或凸性，因為這些一般難以用一個模型來生成。

3) 基于特征的方法

基于特征的方法主要是根據(jù)分割的特征進(jìn)行分類，主要有對稱性(symmetry)[49-51]、凸性(Convexity)[37,52-54]，管狀特征(Tubularity)[27]，紋理特征(Texture)[55-56]，表面擴(kuò)散(Diffusion)[57]和物理模型中的振動模式(Vibration of Modes)[58]。通常這些屬性難以通過表面元素之間親和力或模型生成的方法來獲取。此外，Agathos[20-21,59]和Shamir[60]分別對現(xiàn)有的方法做了總結(jié)和討論，盡管如此仍沒有一個全面的、自動的分割標(biāo)準(zhǔn)框架。于是2009年Chen等人[61]建立了一個模型分割的Benchmark，通過分析大量的模型分割數(shù)據(jù)以及人工分割和計算機(jī)分割各自的特點，提供了7種分割方法的量化分析和比較，同時提出了評價模型分割算法結(jié)果的Benchmark。Evangelos Kalogerakis等[62]在Chen等2009年的工作的基礎(chǔ)上，提出了一種數(shù)據(jù)驅(qū)動的方法來對三維模型進(jìn)行同步分割和標(biāo)記，通過對已有的模型庫進(jìn)行學(xué)習(xí)、訓(xùn)練，實現(xiàn)對測試模型的正確分割。這類方法為了產(chǎn)生一致的分割結(jié)果往往需要大量的樣本進(jìn)行訓(xùn)練和學(xué)習(xí)。Wu等[63]提供了一種交互式的形狀聯(lián)合分割方法。為了避免交互、學(xué)習(xí)等問題，大量的無監(jiān)督學(xué)習(xí)的方法涌現(xiàn)[64-69]。Golovinskiy等人[64]首次將單個形狀分割的思想推廣到多形狀的分割上，通過對輸入形狀進(jìn)行剛性對齊，并利用層次聚類進(jìn)行形狀分割。該方法僅對具有高度相似性的形狀有效。Sidi等[65]提出了一種非監(jiān)督的形狀集分割方法，可以有效表示形狀語義并建立形狀集之間的對應(yīng)關(guān)系。Lei等[66]提出了一種基于譜圖方法的三維模型無監(jiān)督聯(lián)合分割算法，該方法可以分割各種不同類型的三維模型，而且在處理具有顯著拓?fù)浣Y(jié)構(gòu)變化的三維模型時更為有效。

2.2 形狀理解

形狀分解涉及到了對視覺物體對象幾何屬性的認(rèn)知、學(xué)習(xí)，是一項非常復(fù)雜而且極富挑戰(zhàn)性的問題，在機(jī)器視覺和不同領(lǐng)域有很多復(fù)雜的應(yīng)用，如醫(yī)學(xué)圖像、動畫和產(chǎn)品建模等。迄今為止所獲得的成果推動了極具創(chuàng)新性的研究領(lǐng)域的大量有意義的工作，例如在處理多維媒體的基于語義的知識系統(tǒng)領(lǐng)域等。

為了處理形狀理解的復(fù)雜性，Les等給出了一些平面物體形狀理解的方法[70-72]。Oliver等[73]提出了非監(jiān)督式的形狀層次分析方法，不僅可以揭示形狀的層次結(jié)構(gòu)還可以獲得結(jié)構(gòu)之間的關(guān)系。在三維形狀的理解研究方面，Attene[74]從計算方法的角度對形狀理解進(jìn)行分類，主要可以分為基于幾何和結(jié)構(gòu)的方法(Geometry and Structure)、基于形狀拓?fù)涞姆椒?Topology-based Method)。

1) 基于幾何和結(jié)構(gòu)的方法

該方法是通過對物體對象的空間范圍(即幾何)、物體的特征以及物體的組成部分分解(結(jié)構(gòu)表示)等實現(xiàn)的。通常需要定義一些理想的形狀描述符以捕捉和計算給定表面的主要特點，并提取旋轉(zhuǎn)、平移和縮放不變的幾何形狀，然后區(qū)分全局和局部特征，并將其聯(lián)合起來抽象成一個緊湊的表示形式，進(jìn)而用于一些復(fù)雜的任務(wù)諸如：形狀匹配、形狀檢索和形狀比較。典型的研究機(jī)構(gòu)IMATI-GE/CNR(Genova of the Institute of Applied Mathematics and Information Technologies)開發(fā)了AIM@SHAPE國際項目，其主要目的是發(fā)展基于語義的形狀表示，并利用相關(guān)的知識開發(fā)面向語義的工具來獲取、構(gòu)造、傳遞和處理形狀。

這里涉及的形狀描述符主要有局部表面描述符和全局表面描述符兩種。局部表面描述符用來表示曲面上的點以及鄰接點的幾何特征，并通過匹配場景數(shù)據(jù)和目標(biāo)模型以實現(xiàn)物體識別、模型匹配、形狀配準(zhǔn)等目標(biāo)工作?，F(xiàn)今有許多的研究工作集中于采用局部表面描述符來表示物體的形狀。

de Figueiredo和Kehtarnavaz[75]假設(shè)物體是由一些光滑的分片集組成的，然后他們利用屬性圖來表示物體，圖中每個節(jié)點的屬性都由對應(yīng)分片的高斯曲率來表示，最后主要采用基于圖匹配的方法進(jìn)行物體的識別。Stein和Medioni[76]主要研究密集型數(shù)據(jù)，他們主要利用兩種主要特征，一種是基于三維曲線，另一種稱為splash，它基于小的曲面分片，是一種可以描述面法向量的局部高斯映射。這兩種特征經(jīng)過編碼后可以用來快速地進(jìn)行檢索和匹配。Chua和Jarvis[77]提出一種特征描述符point signature，然后通過特征的計算和投票機(jī)制對物體進(jìn)行識別。Johnson和Hebert[78]提出使用旋轉(zhuǎn)圖像來表示由許多密集樣本點描述的曲面形狀，每一點的旋轉(zhuǎn)圖像都是經(jīng)過對物體表面點的坐標(biāo)進(jìn)行編碼而成的，然后通過比較和匹配這些旋轉(zhuǎn)圖像達(dá)到識別的目的。Sidi等[65]也提出采用多特征描述符來度量各分割區(qū)域之間的相似性，并將聯(lián)合分割問題看作是一種聚類問題。除此之外還有許多其它一些類似工作，這些工作的主要區(qū)別在于如何定義局部表面特征符以及如何進(jìn)行曲面的匹配。

全局表面描述符主要描述了3D物體整體形狀中的全部或者最顯著的幾何特征，這種描述方法在3D物體的表示、匹配和分類中也得到大量的研究。

早在幾十年前，傅里葉描述符就可以用來表示封閉的2D輪廓，并已經(jīng)應(yīng)用到基于2D物體輪廓線對物體進(jìn)行識別[79-80]。近年來，也有很多研究者致力于將傅里葉描述方法推廣到3D曲面中[81-84]。這些方法的基本思想是：首先將物體的原點映射到一個單位球體上以形成一個定義在單位球曲面上的函數(shù)。該函數(shù)可擴(kuò)展成一系列的球諧波函數(shù)，傅里葉的系數(shù)可用作面描述符，通過比較系數(shù)空間中的傅里葉描述符實現(xiàn)物體的比較和識別。

2) 基于形狀拓?fù)涞姆椒?/p>

實際上基于形狀拓?fù)涞姆椒ㄊ抢脭?shù)學(xué)工具來判斷物體之間是否匹配，是否有區(qū)別，進(jìn)而捕獲和理解空間的形狀。除了組合拓?fù)浣Y(jié)構(gòu)之外，傳統(tǒng)的工具諸如Morse理論、同倫和同源性都是可以用來處理與形狀理解相關(guān)的問題。Morse理論主要研究空間中不同形狀之間的關(guān)系以及在空間上定義的光滑函數(shù)的臨界點的關(guān)系。近幾年來，Morse理論也被成功地應(yīng)用到標(biāo)量場數(shù)據(jù)的可視化中。

Hilaga[85], Biasotti[86], Dey[87]和Xiao[88]分別根據(jù)Morse理論，采用Reeb圖的方法對模型的拓?fù)浣Y(jié)構(gòu)進(jìn)行分析，獲得模型的拓?fù)浣Y(jié)構(gòu)表示，得到實體的語義描述，然后進(jìn)行形狀的理解與識別研究。其中Hilaga[85]使用表面測地線距離作為Morse函數(shù)，并提出一種多尺度Reeb圖算法。Biasotti在Morse理論和Reeb圖的基礎(chǔ)上給出了擴(kuò)展Reeb圖[86](extended Reebgraph，ERG)，用以表示臨界點之間的拓?fù)潢P(guān)系，該方法為模型的分類、簡化和存儲提供了有效的形狀表示。Dey等人利用Morse 理論的思想定義離散域上的光滑函數(shù)進(jìn)行網(wǎng)格分割[87]。Xiao等人[88]采用了一種離散Reeb圖(DRG)的方法來對人體模型的拓?fù)浣Y(jié)構(gòu)進(jìn)行分析。另外，Bespalov等[89]提出了一種頂點的距離矩陣，通過距離矩陣對三維模型進(jìn)行分解來得到三維模型的Reeb圖。Tung[38]提出了一種增量Reeb圖算法，這個算法采用的Morse函數(shù)也是高度函數(shù)。Hui等[90]通過兩層拓?fù)浞纸?，利用圖表示實體各部分的分解關(guān)系，實現(xiàn)對形狀的初步理解。波恩大學(xué)的Schnabel[91]通過把語義實體描述為具有原始形狀結(jié)構(gòu)的帶約束的圖，然后進(jìn)行形狀的理解研究，其中包括三維點云數(shù)據(jù)的形狀表示問題。Zheng等[92]首先將輸入的三維模型進(jìn)行預(yù)分割為一組關(guān)系圖，并在此基礎(chǔ)上提出一種對稱的功能排列(簡稱為SFARR-s)方法，可以組合得到不同形狀的物體。

綜上，基于幾何和結(jié)構(gòu)的方法主要利用特征描述符，經(jīng)過特征匹配達(dá)到物體的理解與識別，而基于形狀拓?fù)涞姆椒ㄖ饕ㄟ^獲取物體的形狀信息利用數(shù)學(xué)工具進(jìn)行模型的匹配與識別。這些方法都僅考慮物體的幾何或者形狀，僅局限于物體的一種特征描述。如果結(jié)合物體的形狀分解結(jié)果，綜合利用物體的結(jié)構(gòu)和形狀拓?fù)?，從物體整體的組成和語義關(guān)系出發(fā)，建立物體的語義描述，這樣才能抓住單個物體理解與識別的關(guān)鍵問題。

3 多目標(biāo)場景的理解與識別

3.1 多目標(biāo)場景的分割

多目標(biāo)場景的分割是感知和理解場景中多目標(biāo)物體的最基本步驟，即如何有效、快速地選擇能夠完整表示場景中各目標(biāo)的點云子集。場景目標(biāo)分割中典型的方法有Hough變化、區(qū)域增長和基于隨機(jī)采樣一致算法RANSAC(RANdom Sample Consensus)等。在機(jī)器視覺和計算機(jī)圖形學(xué)領(lǐng)域中經(jīng)常使用第1和第3種方法，而區(qū)域生長的方法多用于逆向工程領(lǐng)域。

1) 基于Hough變換的方法

Hough變換是基于一種投票機(jī)制，旨在從原始離散參數(shù)化空間中提取參數(shù)化形狀。為此，Hough變換將輸入的數(shù)據(jù)中每一個點映射到參數(shù)域中的一個流形上。生成的流形由所輸入點相交的所有可能的變體組成。在離散參數(shù)化空間的所有cell如果與流形相交則得到一個投票。當(dāng)輸入的每個點都經(jīng)過處理之后，通過選擇投票較多的參數(shù)向量進(jìn)行形狀的提取。然而對于形狀復(fù)雜的基元，其參數(shù)通常非常多(如：圓環(huán)面)，那么對于高維離散參數(shù)域來說，該方法的復(fù)雜度則成為其的最大缺點[93]，盡管仍有一些方法[94-95]用來針對此問題，然而其主要的應(yīng)用領(lǐng)域仍是在參數(shù)較少的二維空間中。其中一個特例是vosselman等[96]利用Hough變換進(jìn)行3D數(shù)據(jù)集中的平面檢測和柱面的檢測。

2) 基于區(qū)域增長的方法

區(qū)域增長的方式首先從數(shù)據(jù)中選擇一個種子區(qū)域，然后通過判斷與周圍區(qū)域的相似性進(jìn)而確定能否進(jìn)行增長。區(qū)域增長方法的主要問題是初始的種子區(qū)域與初始區(qū)域的擬合質(zhì)量都將會影響到最終分割的結(jié)果，因此如果一個區(qū)域的噪聲較大時很難確定是否進(jìn)行增長。文獻(xiàn)[97]提出了一種擴(kuò)展的區(qū)域增長方法，該方法中多個種子區(qū)域同時獨立進(jìn)行增長，從而得到多個重疊的聚類，然后選擇可以逼近整個數(shù)據(jù)的聚類的子集，同時代價函數(shù)又最小，該方法可以得到較好的分割結(jié)果，但是受噪聲影響比較大。在逆向工程中多數(shù)的曲面重建技術(shù)都是基于區(qū)域生長的方法[98-100]。然而選擇合適的種子點、合適的增長設(shè)定閾值以及合適的增長準(zhǔn)則非常不易，這使得要實現(xiàn)真正意義上的點云場景分割，甚至得到語義分割仍存在很大的困難。

3) 基于隨機(jī)采樣一致算法

隨機(jī)采樣一致算法最早是1981年由Fischler 和 Bolle[101]提出的，主要用來從一堆數(shù)據(jù)點中估計出一個預(yù)先定義好的模型及其參數(shù)，是一個非常魯棒的模型估計算法。由于該算法對噪聲和外點都有很好的魯棒性，所以對于真實空間場景掃描數(shù)據(jù)的形狀檢測是一個非常好的方法。很多研究者在此方面展開了研究，典型的工作主要有Bolles和 Fischler[102]利用RANSAC從深度圖像中提取圓柱信息，Chaperon和Goulette[103]使用RANSAC和高斯圖像來檢測3D點云中的圓柱。這兩種方法都沒有考慮多種類型的形狀基元。相比而言，Roth和Levine[104]利用RANSAC檢測不同類型的簡單形狀基元，然而這些方法對處理大規(guī)模的離散點云數(shù)據(jù)，顯得很棘手。Schnabel等[91]利用RANSAC快速檢測語義實體描述的形狀，并將其表示為具有原始形狀結(jié)構(gòu)的帶約束的圖，最后將其應(yīng)用到掃描的場景中，然而其中用的查詢圖和其中的約束條件必須經(jīng)過手工定義。Zheng等人[105]利用RANSAC算法從掃描點云場景中提取出平面信息。盡管RANSAC算法是一種比較有效的模型估計方法，可用來提取空間物體中圓柱、平面等不同形狀，然而這些形狀如何組成物體，不同形狀之間的空間分布都無從獲得。

3.2 場景的理解與識別

利用場景目標(biāo)分割方法將場景分成一個個獨立的、相互聯(lián)系的小區(qū)域，這些區(qū)域表示或者代表的是哪一種物體，場景主要是由哪些目標(biāo)物體組成的，目標(biāo)物體之間有著什么樣的關(guān)系，都成為場景理解和識別的關(guān)鍵內(nèi)容。

1) 基于圖模型的方法

Chen[106]在基于CSG(Constructive Solid Geometry)的三維物體識別方法中，提出用PG圖(Precedence Graph)來表示三維物體，并成功地應(yīng)用神經(jīng)網(wǎng)絡(luò)實現(xiàn)了模型與深度圖像中景物的匹配，進(jìn)而實現(xiàn)三維物體的識別。但在該方法中基元的主要參量為曲面類型及大小，因而對三維曲面物體的識別具有一定的局限性。Zheng等[107]提出基于幾何推理和物理推理的場景理解方法，利用一種新的DG圖表示能量圖，進(jìn)而完成對場景中對象的分割和理解。Somani[108]將感知模型和推理引擎相結(jié)合完成機(jī)器人對場景的理解，該方法首先探測出場景的基本形狀，然后將對象利用基本形狀圖表示(primitive shape Graph, PSG)，根據(jù)圖的匹配完成機(jī)器人對場景物體的識別。Xu等[109]提出了一種基于聚焦點分析的方法。將三維場景模型表示成圖結(jié)構(gòu)，聚焦點則是一種在大量彼此相關(guān)的場景圖結(jié)構(gòu)中頻繁出現(xiàn)的子圖結(jié)構(gòu)，通過自動提取這種上下文相關(guān)的子圖結(jié)構(gòu)，可以實現(xiàn)對大規(guī)模場景數(shù)據(jù)集的結(jié)構(gòu)分析和結(jié)構(gòu)化組織。

2) 基于局部特征的方法

由于場景的復(fù)雜性以及目標(biāo)物體的多樣性使得全局表面描述符不能夠準(zhǔn)確地描述物體的真實幾何信息，因此基于全局描述符的識別工作很難適用。而局部表面描述符側(cè)重于表示局部3D幾何信息，不會對局部特征計算的準(zhǔn)確性造成太多影響，也不會對識別產(chǎn)生影響，因此許多學(xué)者在基于局部表面描述符進(jìn)行場景理解和識別方面展開研究。

Antonio Adan[110]提出利用靈活的相似性度量策略對三維物體進(jìn)行識別。Mian等[111]提出一種基于3D模型的、與視點無關(guān)的場景物體分割和識別方法。Salvador等[112]提出利用球旋轉(zhuǎn)圖像來表示物體的形狀特征，通過剛體變換查找最佳匹配實現(xiàn)物體的識別和定位。Frome[113]提出兩種區(qū)域點描述符對場景中的物體進(jìn)行識別。Rabbani[114]和Unnikrishnan[115]主要對場景中的幾何圖元進(jìn)行提取和分類。魏[116]提出了一種基于局部描述符的三維點云物體識別算法。算法的總體過程是通過把三維物體進(jìn)行分割、投影，建立二維描述并形成模型庫, 從而把三維物體識別轉(zhuǎn)化為二維識別。

3) 基于機(jī)器學(xué)習(xí)的方法

Himmelsbach[117]等利用柵格的思想分割物體，然后在原始激光數(shù)據(jù)上提取特征，并使用支持向量機(jī)對物體進(jìn)行分類。Anguelov[118]等完整地描述了一種基于Markov隨機(jī)場的物體分類方法。相比較，Agrawal[119]雖然也采用Markov隨機(jī)場模型來對物體進(jìn)行認(rèn)知，但是該方法首先利用激光點的鄰域關(guān)系從激光數(shù)據(jù)中提取多邊形集，然后以此作為結(jié)點對物體進(jìn)行分類處理。Lalonde[120]通過計算三維空間特征，并利用貝葉斯分類器實現(xiàn)三維物體的分類識別。Lai[121]提出一種HMP3D算法，自動從RGBD圖像以及點云數(shù)據(jù)中提取特征，無需手動設(shè)計，通過學(xué)習(xí)實現(xiàn)對小型桌面類場景中對象的標(biāo)識。

4) 基于特定目標(biāo)的方法

按照場景中物體類型的不同，研究者分別針對場景中具體的物體設(shè)計具體的方案，從現(xiàn)有的文獻(xiàn)資料來看，大多數(shù)場景理解和識別方面的研究主要集中于場景中建筑物的識別、樹木的識別、車輛的識別、地形識別等。

Golovinskiy[122]詳細(xì)描述了識別空間場景中小物體的方法，主要通過定位、分割、描述和分類等步驟實現(xiàn)。關(guān)于場景中建筑物的理解和識別方面，Kada和Dorninger做了相關(guān)研究，Kada[123]提出利用Cell分解的方法從場景中提取出建筑，并結(jié)合圖像識別窗戶部分。Dorninger[124]利用層次聚類的算法提取場景的平面信息，旨在對提取的建筑物部分進(jìn)行重建工作。Pu等[125]提出利用知識的表示方法對場景中的物體進(jìn)行分類。在場景中樹木識別方面，Wang等[126]從森林的LIDAR點云數(shù)據(jù)中檢測并估計出樹木的三維模型，Xu等[127]對樹木的樹枝和樹冠進(jìn)行分析和提取。Dai等[128]利用主方向分析的方法對掃描的樹木的樹枝和樹葉進(jìn)行分類提取。此外，Alexander等[129]提出結(jié)合自底向上和自頂向下的過程來檢測空間場景中的物體，并將研究重點集中于場景中汽車的檢測和識別。

上述方法中關(guān)于空間場景理解和識別方面的研究還是有很大的局限性，大多數(shù)的工作都僅僅是對復(fù)雜場景中的單個目標(biāo)進(jìn)行檢測、提取和識別，而對空間場景的整體組成結(jié)構(gòu)的情況、組成結(jié)構(gòu)之間的關(guān)系以及場景的理解、場景中不同目標(biāo)的理解和識別都還缺乏詳細(xì)的研究，需要進(jìn)一步深入探討。

4 難點問題與發(fā)展方向

雖然現(xiàn)有的研究成果已經(jīng)能夠在很多場合幫助人們更好的感知和理解空間物體模型。但是，僅有這些方法還遠(yuǎn)遠(yuǎn)不夠，要高效地幫助計算機(jī)感知和理解空間物體(包括簡單場景和復(fù)雜場景)，還需要研究和探索以下一些難點問題。

1) 姿態(tài)問題

對于空間點云物體而言，由于不同的姿態(tài)下物體本身的形體會發(fā)生一定程度的變化，因此姿態(tài)是影響進(jìn)一步理解與識別物體的關(guān)鍵因素之一，那么如何實現(xiàn)符合人類感知和認(rèn)知的空間點云物體一致性形狀分解與表達(dá)？如果輸入同類物體不同姿態(tài)下的多個數(shù)據(jù)集，那么在對物體進(jìn)行形狀分解時希望獲得一致性的形狀分解結(jié)果。針對此問題，一方面可利用有監(jiān)督的方法，通過訓(xùn)練樣本獲得先驗知識。另一方面利用無監(jiān)督的方法，關(guān)鍵問題是建立不同數(shù)據(jù)集之間的特征關(guān)系，以及如何傳遞形狀分解結(jié)果以避免物體姿態(tài)變化的影響。

2) 拓?fù)潢P(guān)聯(lián)問題

拓?fù)浣Y(jié)構(gòu)是空間目標(biāo)之間最基本的也是最重要的結(jié)構(gòu)關(guān)系。有了形狀組成，如果缺少他們之間的拓?fù)潢P(guān)系，則根本無法構(gòu)造場景中的對象，也更無法談及理解與識別問題。因此，如何構(gòu)造場景物體的拓?fù)潢P(guān)系以及組成結(jié)構(gòu)之間的關(guān)聯(lián)性則是物體理解與識別的關(guān)鍵點和突破點。為了解決此問題，可考慮結(jié)合圖論或者引入視覺感知信息來獲得物體(場景)本身的拓?fù)浣Y(jié)構(gòu)表示，為進(jìn)一步實現(xiàn)語義表達(dá)奠定基礎(chǔ)。

3) 語義問題

關(guān)于物體的語義信息獲取以及將形狀語義應(yīng)用于物體的形狀理解仍然是研究者們“回避”的一個方向。由于不同的物體其形狀各異，而且語義的描述比較抽象、難以理解，為了更加直觀地建立物體的高層語義需要結(jié)合多方面的內(nèi)容，既要有物體的結(jié)構(gòu)，又要有物體的形狀、拓?fù)浼捌湎嚓P(guān)聯(lián)性，所以只有多層次的結(jié)合才可以建立魯棒的形狀高層語義描述統(tǒng)一模型。

以上問題的解決可為點云物體的理解和識別方法研究提供新的思路和理論依據(jù)。綜合上述難點問題，可考慮以同類物體的不同姿態(tài)下的多數(shù)據(jù)集作為輸入，研究無監(jiān)督數(shù)據(jù)驅(qū)動下的點云物體(場景)形狀分割方法，建立物體形狀語義的統(tǒng)一描述模型。由此可見，綜合譜聚類、圖論等理論知識，研究無監(jiān)督的物體(場景)的分割(分類)方法，探討空間數(shù)據(jù)結(jié)構(gòu)以及基本形狀表示模型，探索物體(場景)分割、理解與識別的普適性方法將是進(jìn)一步研究與發(fā)展的新方向。

5 結(jié) 論

本文以單目標(biāo)物體、多目標(biāo)場景為主要研究對象，分別重點分析總結(jié)了現(xiàn)有的基于點云的空間物體理解與識別方法，討論了不同類方法的不足，并指出姿態(tài)問題、拓?fù)潢P(guān)聯(lián)問題以及語義問題是當(dāng)前研究迫切需要解決的難點問題，并分別提出無監(jiān)督的分類法、視覺感知信息引導(dǎo)以及高層語義模型建立等相應(yīng)的解決思路。同時強(qiáng)調(diào)提出一套系統(tǒng)的、普適性的空間點云物體理解和識別方法將是進(jìn)一步的研究方向。

參考文獻(xiàn):

[1] Stuart R, Peter N. Artificial intelligence: a modern approach [M].Prentice Hall. New Jersey, USA, 2002.

[2] Newman P, Cole D, Ho K. Outdoor SLAM using visual appearance and laser ranging[C]//Proceedings of the International Conference on Robotics and Automation (ICRA), Orlando, FL, 2006: 1180-1187.

[3] Ellen K, Blake C, Olga R, et al. Autonomous operation of novel elevators for robot navigation[C]//Proceedings of the International Conference on Robotics and Automation (ICRA), 2010: 751-758.

[4] Quigley M, Batra S, Gould S, et al. High accuracy 3D sensing for mobile manipulation: improving object detection and door opening[C]//Proceedings of the International Conference on Robotics and Automation (ICRA), Kobe, 2009: 2816-2822.

[5] Saxena A, Wong L, Quigley M, et al. A vision-based system for grasping novel objects in cluttered environments[C]//In International Symposium on Robotics Research (ISRR), Hiroshima, Japan, 2007: 337-348.

[6] Thirde D, Borg M, Ferryman J, et al. A real-time scene understanding system for airport apron monitoring[C]// Proceedings of the International Conference on Computer Vision Systems (ICCVS), NY, USA, 2006: 26-26.

[7] Mirota D, Taylor R H, Ishii M, et al. Direct endoscopic video registration for sinus surgery[C]//In Medical Imaging: Visualization, Image-guided Procedures and Modeling. Proceedings of the SPIE, Lake Buena Vista, FL, 2009, 7261:1-8.

[8] Marr D. Vision: a computational investigation into the human representation and processing of visual information [M].New York：Henry Holt and Co Inc.,1982.

[9] Biederman I. Recognition by components: a theory of human image understanding[J].Psychological Review, 1987, 94(2): 115-147.

[10] Biederman I, Gerhardstein P C. Viewpoint-dependent mechanisms in visual object recognition: reply to tarr and bulthoff[J].Journal of Experimental Psychology: Human Perception and Performance, 1995, 21(6): 1506-1514.

[11] Koenderink J, Doorn A. The internal representation of solid shape with respect to vision[J].Biological Cybernetics, 1979, 32(4): 211-216.

[12] Bultho H H, Edelman S Y, Tarr M J. How are three-dimensional objects represented in the brain?[J].Cerebral Cortex, 1995, 5(3): 247-260.

[13] Tarr M J, Williams P, Hayward W G, et al. Three-dimensional object recognition is viewpoint dependent[J].Nature Neuroscience,1998,1(4): 275-277.

[14] Tarr M J, Bulthoff H H. Image-based object recognition in man. Monkey and machine[J].Cognition, 1998, 67(1-2): 1-20.

[15] Heckel B, Uva A E, Hamann B. Cluster-based generation of hierarchical surface models[C]//Proceedings of Scientific Visualization. Washington, DC, USA, 1997: 105-114.

[16] Katz S, Tal A. Hierarchical mesh decomposition using fuzzy clustering and cuts[J].ACM Transaction on Graphics, 2003,22(3): 954-961.

[17] Mangan A P, Whitaker R. T. Partitioning 3d surface meshes using watershed segmentation[J].IEEE Transactions on Visualization and Computer Graphics, 1999: 308-321.

[18] Shalfman S, Tal A, Katz S. Metamorphosis of polyhedral surfaces using decomposition[J].Computer Graphics Forum, 2002, 21(3): 219-228.

[19] Attene M, Katz S, Mortara M, et al. Mesh segmentation-a comparative study[C]//In SMI '06: Proceedings of the IEEE International Conference on Shape Modeling and Applications, Matsushima, 2006: 1-7.

[20] Garland M, Willmott A, Heckbert P S. Hierarchical face clustering on polygonal surfaces[C]//Proceedings Symposium on Interactive 3D graphics, New York, NY, USA, 2001: 49-58.

[21] Agathos A, Pratikakis I, Perantonis S, et al. 3D mesh segmentation methodologies for CAD applications[J].Computer-Aided Design &Applications, 2007,4(6): 827-841.

[22] Zuckerberger E, Tal A, Shlafman S. Polyhedral surface decomposition with applications[J].Computers and Graphics, 2002,26(5): 733-743.

[23] Shamir A. Segmentation and shape extraction of 3d boundary meshes (state-of-the-art report)[C]//In Eurographics, Vienna, Austria, 2006: 137-149.

[24] Shamir A. A formulation of boundary mesh segmentation[C]//Proceedings of the 3D Data Processing, Visualization, and Transmission. 2nd International Symposium, IEEE Computer Society, Washington, DC, USA, 2004: 82-89.

[25] Katz S, Leifman G, Tal A. Mesh segmentation using feature point and core extraction[J].The Visual Computer, 2005, 21(8):649-658.

[26] Lee Y, Lee S, Shamir A, et al. Mesh scissoring with minima rule and part salience[J].Computer Aided Geometric Design, 2005, 22(5): 444-465.

[27] Mortara M, Patanè G, Spagnuolo M, et al. Plumber: a multi-scale decomposition of 3d shapes into tubular primitives and bodies[C]//Proceedings of Solid Modeling and Applications, Genoa, Italy, 2004: 339-344.

[28] Attene M, Falcidieno B, Spagnuolo M. Hierarchical mesh segmentation based on fitting primitives[J].Visual Computer, 2006, 22(3): 181-193.

[29] Reniers D, Telea A. Skeleton-based hierarchical shape segmentation[C]//In SMI '07: Proceedings of the IEEE International Conference on Shape Modeling and Applications, IEEE Computer Society, Washington, DC, USA, 2007: 179-188.

[30] Li X, Woon T W, Tan T S, et al. Decomposing polygon meshes for interactive applications[C]//Proceedings of the 2001 Symposium on Interactive 3D Graphics, New York, USA: ACM, 2001: 35-42.

[31] Lien J M, Keyser J, Amato N M. Simultaneous shape decomposition and skeletonization[C]//Proceedings of ACM Solid and Physical Modeling Symposium (SPM), New York, USA, 2005: 219-228.

[32] Clarenz U, Griebel M, Schweitzer M A, et al. Feature sensitive multi-scale editing on surfaces[J].The Visual Computer, 2004, 20(5): 329-343.

[33] Borgefors G, di Baja G S, Svensson S. Decomposing digital 3d shapes using a multi resolution structure[C]// Proceedings of Discrete Geometry for Computer Imagery, Marne-la-Vallee, France, 1999: 19-30.

[34] Hisada M, Belyaev A G, Kunii T L. A skeleton-based approach for detection of perceptually salient features on polygonal surfaces[J].Computer Graphics Forum,2001, 21(4): 689-700.

[35] Provot L, Debled-rennesson I. Segmentation of noisy discrete surfaces[C]//12th International workshop on combinatorial Image Analysis,Buffalo,NY,United States, 2008, 4958:160-171.

[36] Wang Y, Gong M, Wang T, et al. Projective analysis for 3D shape segmentation[J].ACM Transaction on Graphics,2013, 32(6):article No.192:1-12.

[37] Lien J.M, Amato N M. Approximate convex decomposition of polyhedral[C]//ACM Symposium on Solid and Physical Modeling. Beijing, China, 2005: 121-131.

[38] Tung T, Schmitt F. Augmented reeb graphs for content-based retrieval of 3D mesh models[C]// International Conf. on Shape Modeling and Applications, Genova, Italy, 2004: 157-166.

[39] Lin H, Liao H Y M, Lin J. Visual salience-guided mesh decomposition[J].Multimedia IEEE Transaction on, 2007, 9(1): 46-57.

[40] Lai Y K, Hu S M, Martin R R, et al. Fast mesh segmentation using random walks[C]//Proceedings of the 2008 ACM symposium on Solid and Physical Modeling, Stony Brook, New York, 2008: 183-191.

[41] Gelfand N, Guibas L J. Shape segmentation using local slippage analysis[C]//Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing, Nice, France, 2004: 214-223.

[42] Golovinskiy A, Funkhouser T. Randomized cuts for 3D mesh analysis[J].ACM Transactions on Graphics. 2008, 27(5):article No.145:1-12.

[43] Podolak J, Shilane P, Golovinskiy A, et al. A planar-re?ective symmetry transform for 3d shapes[J].ACM Transaction on Graphics, 2006, 25(3): 549-559.

[44] Liu R, Zhang H. Mesh segmentation via spectral embedding and contour analysis[J].Computer Graphics Forum, 2007, 26(3): 385-394.

[45] Liu R F, Zhang H, Shamir A, et al. A part-aware surface metric for shape analysis[J].Computer Graphics Forum,2009, 28(2): 397-406.

[46] Lukács G, Martin R, Marshall D. Faithful least-squares fitting of spheres, cylinders, cones and tori for reliable segmentation[C]//Proceedings of the 5th European Conference on Computer Vision-Volume I - Volume I (ECCV'98), London, UK, 1998: 671-686.

[47] Simari P, Singh K. Extraction and remeshing of ellipsoidal representations from mesh data[C]//Proceedings of Graphics Interface, Victoria, British Columbia, 2005: 161-168.

[48] Julius D, Kraevoy V, Sheffer A. D-charts: Quasi-developable mesh segmentation[J].Computer Graphics Forum, 2005, 24(3): 581-590.

[49] Thrun S, Wegbreit B. Shape from symmetry[C]//Proceedings of the Tenth IEEE International Conference on Computer Vision- Volume 2 (ICCV '05). Washington, DC, USA, 2005, 2: 1824-1831.

[50] Mitra N J, Guibas L J, Pauly M. Partial and approximate symmetry detection for 3d geometry[J].ACM Transaction on Graphics, 2006, 5(3): 560-568.

[51] Simari P, Kalogerakis V, Singh K. Folding meshes: Hierarchical mesh segmentation based on planar symmetry[C]//The Fourth Eurographics Symposium on Geometry Processing, Cagliari, Sardinia, Italy, 2006: 111-119.

[52] Chazelle B, Dobkin D P, Shouraboura N, et al. Strategies for polyhedral surface decomposition: an experimental study[J].Computational Geometry: Theory and Applications, 1997, 7(5-6): 327-342.

[53] Kraevoy V, Sheffer A. Variational meaningful shape decomposition[C]//ACM SIGGRAPH Sketches, Boston, Massachusetts, 2006,article No.50:1-2.

[54] Kreavoy V, Julius D, Sheffer A. Model composition from interchangeable components[C]//Proceedings of the 15th Pacific Conference on Computer Graphics and Applications, Washington, DC, USA, 2007: 129-138.

[55] Liu S, Martin R R, Langbein F C, et al. Segmenting reliefs on triangle meshes[C]//ACM Symposium on Solid and Physical Modeling, Cardiff, Wales, United Kingdom, 2006: 7-16.

[56] Liu S, Martin R R, Langbein F C, et al. Segmenting geometric reliefs from textured background surfaces[J].Computer-Aided Design and Applications, 2007, 4(5): 565-583.

[57] De Goes F, Goldenstein S, Velho L. A hierarchical segmentation of articulated bodies[C]//Eurographics Symposium on Geometry Processing, Copenhagen, Denmark, 2008: 1349-1356.

[58] Huang Q, Wicke M, Adams B, et al. Shape decomposition using modal analysis [J].Computer Graphics Forum, 2009, 28(2): 407-416.

[59] Agathos A, Pratikakis I, Perantonis S, et al. 3D mesh segmentation methodologies for CAD applications[J].Computer-Aided Design and Applications, 2007, 4(6): 827-841.

[60] Shamir A. A survey on mesh segmentation techniques [J].Computer Graphics Forum, 2008, 27(6):1539-1556.

[61] Chen X, Golovinskiy A, Funkhouser T. A benchmark for 3D mesh segmentation[J].ACM Transactions on Graphics, 2009, 28(3):article No.73:1-12.

[62] Kalogerakis E, Hertzmann A, Singh K. Learning 3D mesh segmentation and labeling[J].ACM Transactions on Graphics, 2010, 29(4):article No.102:1-12.

[63] Wu Z, Wang Y, Shoua R, et al. Unsupervised co-segmentation of 3D shapes via affinity aggregation spectral clustering[J].Computers & Graphics, 2013, 37(6):628-637.

[64] Golovinskiy A, Funkhouser T. Consistent segmentation of 3D models[J].Computers & Graphics (Proc. of SMI), 2009, 33(3): 262-269.

[65] Sidi O, Oliver V K, Yanir K, et al. Unsupervised co-segmentation of a set of shapes via descriptor-space spectral clustering[J].ACM Transactions on Graphics, 2011, 30(6):article No.126:1-10.

[66] Lei H P, Luo X N, Lin S J, et al. Automatic 3D shape co-segmentation using spectral graph method[J].Journal of Computer Science and Technology, 2013, 28(5): 919-929.

[67] Hu R, Fan L, Liu L. Co-segmentation of 3D shapes via subspace clustering[J].Computer Graphics Forum, 2012, 31(5): 1703-1713.

[68] Huang Q, Koltun V, Guibas L. Joint shape segmentation with linear programming[J].ACM Transactions on Graphics, 2011, 30(6):article No.125:1-12.

[69] Xu K, Li H, Zhang H, et al. Style-content separation by anisotropic part scales[J].ACM Transactions on Graphics, 2010, 29(5):article No.184:1-10.

[70] Les Z. Shape Understanding: possible classes of shapes[J]. International Journal of Shape Modeling, 2001, 7(1): 75-109.

[71] Les Z. Shape understanding system: understanding the thin object[J].International Journal of Computers and Graphics, 2002, 26(6): 951-970.

[72] Les Z, Les M. Shape understanding system: the visual reasoning process [J].International Journal of Pattern Recognition and Artificial Intelligence, 2003, 17(4): 663-683.

[73] Oliver V K, Xu K, Zhang H, et al. Co-hierarchical analysis of shape structures[J].ACM Transactions on Graphics, 2013, 32(4):article No.69:1-10.

[74] Attene M, Biasotti S, Mortara M, et al. Computational methods for understanding 3D shapes[J].Computers & Graphics, 2006, 30(3): 323-333.

[75] De Figueiredo R J P, Kehtarnavaz N. Model-based orientation-independent 3-D machine vision techniques[J].Aerospace and Electronic Systems IEEE Transactions on, 1988, 24(5): 597-607.

[76] Stein F, Medioni G. Structural indexing:efficient 3D object recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992, 14(2): 125-145.

[77] Chin S C, Ray J. Point signatures:a new representation for 3D object recognition[J].International Journal of Computer Vision,1997, 25(1):63-85.

[78] Johnson A E, Hebert M. Using spin images for efficient object recognition in cluttered 3D scenes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999, 21(5):433-449.

[79] Kuhl F, Giardina C. Elliptic Fourier features of a closed contour[J].Computer Graphics and Image Processing, 1982, 18(3):236-258.

[80] Persoon E, Fu K S. Shape discrimination using Fourier descriptors[J].IEEE Transaction on Pattern Analysis, Machine Intelligence, 1986, 8(3):388-397.

[81] Brechbühler C. Parametrization of closed surfaces for 3-D shape description[J].Computer vision and Image understanding,1995, 61(2):154-170.

[82] Li H D, Hartley R. New 3D Fourier descriptors for genus-zero mesh objects[C]//Proceedings of 7th Asian Conference on Computer Vision, Hyderabad, India, 2006, I: 734-743.

[83] Morris R J, Najmanovich R J, Kahraman A, et al. Real spherical harmonic expansion coefficients as 3D shape descriptors for protein binding pocket and ligand comparisons[J].Bioinformatics, 2005, 21(10): 2347-2355.

[84] Sijbers J, Ceulemans T, Van Dyck D. Algorithm for the computation of 3D Fourier descriptors[C]//16th international conference on pattern recognition, Los Alamitos, California, 2002, 2:790-793.

[85] Hilaga M, Shinagawa Y, Kohmura T, et al. Topology matching for fully automatic similarity estimation of 3D shapes[C]//Proceedings of SIGGRAPH, Los Angeles, USA, 2001: 203-212.

[86] Biasotti S. Topological techniques for shape understanding[C]//In: 5th Central European Seminar on Computer Graphics, Bratislava, Slovakia, 2001: 163-172.

[87] Tamal K D, Giesen J, Goswami S. Shape segmentation and matching with flow discretization[C]//Proceedings Workshop on Algorithms and Data Structure, Ottawa, Ontario, Canada, 2003, 2748: 25-36.

[88] Xiao Y J, Werghi N, Siebert P. A topological approach for segmenting human body shape[C]//12th International Conference on Image Analysis and Processing, Mantova, Italy, 2003: 82-87.

[89] Bespalov D, Ali S, William C R, et al. Scale-space representation of 3D models and topological matching[C]//8th ACM/SIGGRAPH Symposium on Solid Modeling and Applications, Seattle, Washington, 2003: 208-215.

[90] Hui A, De Floriani L. A two-level topological decomposition for non-manifold simplicial shapes[C]// Proceedings of the 2007 ACM symposium on Solid and physical modeling, ACM, New York, USA, 2007: 355-360.

[91] Schnabel R, Wahl R, Wessel R, et al. Shape recognition in 3D point clouds[C]//Computer Graphics Technical Reports CG-2007/1, Bonn, Germany, 2007:1-8.

[92] Zheng Y, Cohen-Or D, Mitra N J. Smart variations: functional substructures for part compatibility [J]. Eurographics. 2013, 32(2):195-204.

[93] Illingworth J, Kittler J. A survey of the hough transform[J]. Computer Vision, Graphics and Image Processing, 1988, 44(1): 87-116.

[94] Illingworth J, Kittler J. The adaptive hough transform [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1987, 9(5): 690-698.

[95] Xu L, Oja E. Randomized hough transform (RHT): basic mechanisms, algorithms, and computational complexities [J].CVGIP: Image Underst, 1993, 57(2): 131-154.

[96] Vosselman G, Gorte B G H, Sithole G, et al. Recognising structure in laser scanner point clouds[J].International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2004, 46(8/W2): 33-38.

[97] Leonardis A, Gupta A, Bajcsy R. Segmentation of range images as the search for geometric parametric models[J].International Journal of Computer Vision, 1995, 14(3): 253-277.

[98] Várady T, Martin R R, Cox J. Reverse engineering of geometric models - an introduction[J].Computer-Aided Design, 1997, 29(4): 255-268.

[99] Nickolas S S, Besl P J. Direct construction of polynomial surfaces from dense range images through region growing [J].ACM Transactions on Graphics,1995, 14(2): 171-200.

[100] Benk P, Kos G, Várady T, et al. Constrained fitting in reverse engineering[J].Computer Aided Geometric Design, 2002, 19(3):173-205.

[101] Fischler M A, Bolles R C. Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography[J].Comm. of the ACM, 1981, 24(6): 381-395.

[102] Bolles R C, Fischler M A. A ransac-based approach to model fitting and its application to finding cylinders in range data[C]//Proceedings of the 7th International Joint Conference on Artificial Intelligence, Vancouver, BC, Canada, 1981: 637-643.

[103] Chaperon T, Goulette F. Extracting cylinders in full 3d data using a random sampling method and the Gaussian image[C]//Proceedings of the Vision Modeling and Visualization Conference, 2001:35-42.

[104] Roth G, Levine M D. Extracting geometric primitives[J]. CVGIP: Image Underst, 1993, 58(1):1-22.

[105] Zheng Q, Sharf A, Wan G, et al. Non-local scan consolidation for 3d urban scenes[J].ACM Transactions on Graphics, 2010, 29(4):article No.94:1-9.

[106] Chen T W, Lin W C. A neural network approach to CSG-based 3D object recognition[J].Pattern Analysis and Machine Intelligence, 1994, 16(7): 719-726.

[107] Zheng B, Zhao Y, Yu J, et al. Beyond point clouds: scene understanding by reasoning geometry and physics[C]//IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Portland/USA,2013: 3127-3174.

[108] Somani N, Dean E, Cai C, et al, Perception and reasoning for scene understanding in human-robot interaction scenarios[C]//The 15th International Conference of Computer Analysis of Images and Patterns, York, UK. 2013: 1-15.

[109] Xu K, Ma R, Zhang H, et al. Organizing heterogeneous scene collection through contextual focal points[J].ACM Transactions on Graphics (Proceedings of SIGGRAPH 2014),2014,33(4):1-12.

[110] Adan A, Adan M. A flexible similarity measure for 3D shapes recognition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(11): 1507- 1520.

[111] Mian A S, Bennamoun M, Owens R. Three-dimensional model-based object recognition and segmentation in cluttered scenes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006, 28(10): 1584-1601.

[112] Ruiz-Correa S, Shapiro L G, Melia M. A new signature-based method for efficient 3D objects recognition[C]//Computer Vision and Pattern Recognition,Kauai, HI, USA, 2001, 1: I-769- I-776.

[113] Frome A, Huber D, Kolluri R, et al. Recognizing objects in range data using regional point descriptors[C]//In ECCV, Prague, Czech Republic, 2004, 3023:224-237.

[114] Rabbani T, van den Heuvel F, Vosselmann G. Segmentation of point clouds using smoothness constraint[C]//In IEVM06, Dresden,2006, XXXVI(5):248-253.

[115] Unnikrishnan R, Hebert M. Robust extraction of multiple structures from non-uniformly sampled data[C]//In IROS, Las Vegas, 2003, 2: 1322-1329.

[116] 魏永超,劉長華,杜冬.基于曲面分割的三維點云物體識別[J].光子學(xué)報,2010, 39(12):2268-2273.

Wei Yongchao, Liu Changhua, Du Dong. 3D Points Cloud object recognition based on surface segmentation[J].Acta Photonica Sinica,2010, 39(12):2268-2273.

[117] Himmelsbach M, Luettel T, Wuensche H J. Real-time object classification in 3D point clouds using point feature histograms[C]//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, St. Louis, MO, 2009: 994-1000.

[118] Anguelov D, Taskarf B, Chatalbashev V, et al. Discriminative learning of markov random fields for segmentation of 3D scan data[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Diego, CA, USA, 2005, 2: 169-176.

[119] Agrawal A, Nakazawa A, Takemura H. MMM-classification of 3D range data[C]//Proceedings of the IEEE International Conference on Robotics and Automation. Kobe, Japan, 2009: 2269-2274.

[120] Lalonde J F, Unnikrishnan R, Vandapel N, et al. Scale selection for classification of point-sampled 3d surfaces [C]//In Fifth International Conference on 3-D Digital Imaging and Modeling, Ottawa, Ontario, Canada, 2005: 285-292.

[121] Lai K, Bo L, Fox D. Unsupervised feature learning for 3D scene labeling[C]//In IEEE International Conference on Robotics and Automation (ICRA), Hongkong, China, 2014: 1-8.

[122] Golovinskiy A, Kim V G, Funkhouser T. Shape-based recognition of 3D point clouds in urban environments[C]//ICCV 2009, Kyoto, 2009: 1-10.

[123] Kada M, Haala N, Becker S. Improving the realism of existing 3d city Models [J]. Innovations in 3D Geo Information Systems, 2006: 405-415.

[124] Dorninger P, Pfeifer N. A comprehensive automated 3d approach for building extraction, reconstruction, and regularization from airborne laser scanning point clouds[J]. Sensors, 2008, 8(11): 7323-7343.

[125] Pu S, Vosselman G. Knowledge based reconstruction of building models from terrestrial laser scanning data[J].ISPRS Journal of Photogrammetry and Remote Sensing, 2009, 64 (6): 575-584.

[126] Wang Y, Weinacker H, Koch B. A lidar point cloud based procedure for vertical canopy structure analysis and 3d single tree modeling in forest[J].Sensors,2008,8(6):3938-3951.

[127] Xu H, Gossett N, Chen B. Knowledge and heuristic-based modeling of laser scanned trees[J].ACM Transaction on Graphics, 2007, 26(4):article No.19:1-9.

[128] Dai M, Zhang X, Zhang Y, et al. Segmentation of point cloud scanned from trees[C]//Proceedings of Workshop on 3D content and applications with ACCV, Xi'an, China, 2009:1-12.

[129] Patterson A, Mordohai P, Daniilidis K. Object detection from large-scale 3D datasets using bottom-up and top-down descriptors[C]//ECCV, Marseille France, 2008: 553-566.