二維形狀特征描述及分類識別研究進展綜述

劉 磊，鄒媛媛，陳泊璇

1.沈陽建筑大學 機械工程學院，沈陽110168

2.高檔石材數控加工裝備與技術國家地方聯(lián)合工程實驗室，沈陽110168

物體的形狀特征由于其不會隨著光照、顏色和紋理等的變化而發(fā)生改變，被認為是一個穩(wěn)定的特征，因此，形狀特征被廣泛應用于物體識別、目標跟蹤等領域。其中，魯棒的二維形狀表示可以提高形狀識別的精度和準確率，因此，形狀表示在形狀識別、形狀檢索等相關應用中起著重要作用。通常，二維形狀的表示可分為三類：基于輪廓的表示方法、基于區(qū)域的表示方法以及基于骨架的表示方法。近年來，研究學者針對二維形狀的高效表示，在傳統(tǒng)特征表示的基礎上，不斷提出了新的形狀特征表示方法，例如通過融合不同類別的特征來表示二維形狀，以提高形狀描述的準確性。

高性能高精度的分類識別方法也會影響二維形狀分類識別的準確度?，F有研究中常用機器學習分類器進行二維形狀分類識別，主要有支持向量機[1]（Support Vector Machine，SVM）和隨機森林[2]（Random Forest，RF）等傳統(tǒng)的分類器以及集成分類器，其中，集成分類器相較于單分類器，識別性能得到了一定的提升?；跈C器學習的二維形狀識別分類過程如圖1 所示。隨著深度學習的發(fā)展，運用卷積神經網絡[3-4]（Convolutional Neural Network，CNN）進行二維形狀分類識別也受到了研究學者的關注，成為了一個新的方向。

圖1 基于機器學習的二維形狀識別分類流程圖

本文首先對二維形狀特征表示和識別中的關鍵問題研究現狀進行了總結，接著，綜述了近年來二維形狀表示方法和識別分類方法，對各方法進行了綜合分析，其中，形狀特征表示方法分別包括基于輪廓的、基于區(qū)域的、基于骨架的以及基于多特征融合的二維形狀特征表示方法，識別分類方法主要包括傳統(tǒng)的機器學習分類器、集成分類器、深度學習方法等，然后，匯總了二維形狀識別中常用的標準數據庫，最后，展望了二維形狀特征表示和分類識別方法的研究發(fā)展趨勢，并對本文工作做了總結。

1 形狀特征表示方法研究進展

魯棒的二維形狀表示應該對平移、旋轉、尺度變換等變化不敏感，并對邊界噪聲有一定的魯棒性。本章主要綜述近年來二維形狀特征表示方法的研究進展。

1.1 基于輪廓的形狀表示

基于輪廓的二維形狀表示方法基于形狀邊界，通過提取輪廓邊界特征來表示二維形狀。根據是否將輪廓進行分段，該方法又可分為使用總體輪廓的輪廓全局表示方法以及使用輪廓段的輪廓局部表示方法。

輪廓全局表示方法主要有Wang 等人[5]提出的名為高度函數（Height Function，HF）的形狀描述符。首先將輪廓以固定的采樣點進行表示，對于每個采樣點，高度函數定義為其他采樣點到此采樣點切線的距離。然后通過平滑高度函數得到緊湊和魯棒的形狀描述符。Shu等人[6]提出的名為輪廓點分布直方圖（Contour Point Distribution Histogram，CPDH）的形狀描述符。這是一種通過極坐標下物體輪廓點的分布位置來表示形狀特征的方法。CPDH是尺度不變和平移不變的，對于旋轉不變問題，需要添加額外的條件加以保證。Shi等人[7]提出的基于輪廓重構和特征點弦長函數的圖像檢索算法，以輪廓為基礎，這種方法通過分析輪廓的能量保持率并對輪廓進行降維重構，減少了噪聲對輪廓的影響。通過篩選有效的輪廓特征點，得到輪廓點和相應特征點的弦長關系作為輪廓特征的表示，這種方法滿足不變性要求。

輪廓局部表示方法主要有Laich 等人[8]提出的用有序的輪廓片段序列來表示輪廓形狀的方法，然后使用最小二乘模型，將每個片段與一個三次多項式曲線相關聯(lián)，再將得到的曲線進行歸一化，得到最終的形狀描述符，這種方法是縮放、旋轉、平移不變的。Yang 等人[9]提出的一種名為三角形質心距離（Triangular Centroid Distances，TCDs）的形狀描述符。首先通過離散曲線演化[10]（Discrete Contour Evolution，DCE）算法將輪廓分割成輪廓片段，然后計算輪廓質心點，輪廓片段上的兩個采樣點和輪廓質心點形成一個三角形，計算此三角形的質心，得到三角形質心和輪廓質心之間的距離，作為最終的形狀描述符。

近年來，有研究學者基于單詞包[11-12]（Bag of Words，BoW）模型，融合全局輪廓信息和局部輪廓信息，研究了一種形狀特征包[13]（Bag of Shape Features，BoSF）形狀分類識別框架。該框架主要可分為以下幾個部分：第一步提取輸入形狀的輪廓，并應用離散輪廓演化算法將輪廓分解為不同長度的輪廓段；第二步對每一個輪廓段進行特征描述；第三步進行形狀編碼，常用的編碼方式為局部線性約束編碼[14]（Locality-constrained Linear Coding，LLC）；第四步特征池化，并得到直方圖作為最終的形狀表示；第五步運用SVM 進行訓練和實驗。該框架最終得到的形狀表示既包含局部信息，又包含全局信息。BoSF框架的算法流程圖如圖2所示，其中，特征池化方法可以采用空間金字塔匹配[15]（Spatial Pyramid Matching，SPM），也可以采用最大池化及平均池化等。

圖2 BoSF框架算法流程圖

許多基于該框架提出的方法在常用的形狀分析數據庫上均取得了不錯的識別率和分類準確率。Wang等人[16]提出了名為輪廓碎片包（Bag of Contour Fragments，BCF）的形狀表示。這種方法使用形狀上下文[17]描述每個輪廓片段，并使用LLC算法將其編碼成形狀代碼，最終通過SPM算法匯集形狀代碼，得到緊湊的形狀表示。Pedrosa 等人[18]提出了名為顯著點袋（Bag of Salience Points，BoSP）的形狀描述子，這種描述子為尋找兩組顯著點的對應關系提供了快速解決方案，有助于加速形狀匹配任務。Shen等人基于該框架，在特征池化過程中采用最大池化和平均池化加權，并通過學習確定權重，這種改進提高了識別準確率。Zeng 等人[19]針對二維形狀識別中的非剛性變換和局部變形問題，提出采用曲率對每個輪廓段進行表示，得到曲率詞袋Curvature Bag of Words（CBoW）模型。實驗結果表明該算法識別率高，魯棒性好，適用于非剛性變換和局部變形的目標形狀識別領域。表1對上文所提到的一些描述符做了匯總。

表1 幾種基于輪廓的表示方法

基于輪廓的二維形狀表示方法提取的特征包含豐富的邊界信息，其中，輪廓全局表示方法抗噪性較好，但無法捕捉局部特征，導致區(qū)分不同形狀的能力較差，輪廓局部表示方法能夠更好地捕捉局部形狀，但是對邊界噪聲較敏感，且不易實現，融合局部輪廓信息和全局輪廓信息的特征能夠更準確地表示形狀，識別效果更好。

1.2 基于區(qū)域的形狀表示

基于區(qū)域的二維形狀表示方法通過利用形狀的內部區(qū)域來表示二維形狀，有學者選擇通過提取整個形狀區(qū)域的特征進行表示，也有選擇對區(qū)域進行分割，提取分割后的子區(qū)域特征進行形狀表示。

柯善武等人[20]提出了一種融合圖像顯著區(qū)域二維形狀特征的圖像檢索算法。這種方法很好地解決了當目標存在變形以及大小存在巨大差異時難以提取圖像形狀特征的問題。Wahyono 等人[21]提出了一種基于質心的樹結構（CENTREES）。該方法是一種典型的基于區(qū)域的形狀分類識別方法，其將形狀質心作為根節(jié)點，根據點和相對于質心的主軸之間的角度將形狀分成幾個子區(qū)域，對每個子區(qū)域，用幾種幾何參數作為描述符。最終，所有參數的向量作為形狀描述符，該方法是平移旋轉縮放不變的。該算法的流程圖如圖3 所示。Wang等人[22]提出了一種將形狀分解與形狀分類相結合的框架，構造一個被稱為“分解圖”的數據結構，最后通過在分解圖上搜索最優(yōu)路徑得到分解和分類的結果，實驗證明該方法有很好的分類性能。Priyanka等人[23]提出了名為三角二階形狀導數的形狀描述符，將幾何概念和圖像導數算子融合來實現特征描述和提取，取得了很好的檢索率。表2對上文提到的方法做了匯總。

表2 幾種基于區(qū)域的表示方法

圖3 基于質心的區(qū)域形狀分解流程圖

基于區(qū)域的二維形狀表示利用了形狀內部信息，多數學者采用對區(qū)域進行分割的方法，通過分割得到的子區(qū)域對形狀進行描述，這種方法區(qū)分不同形狀的能力更強。然而，區(qū)域分割方法不易實現，且當數據集較大且形狀種類多時，存在細節(jié)信息丟失的情況。

1.3 基于骨架的形狀表示

基于骨架的二維形狀表示方法通過提取形狀骨架來表示二維形狀。在提取骨架時，用到了最大內切圓模型，最大內切圓指的是圓心在形狀內部且至少內切形狀輪廓上兩個點的圓形。形狀骨架點由這些內切圓的圓心集合而成。

陳展展等人[24]提出了一種骨架樹匹配算法。這種算法不考慮骨架樹的拓撲結構，只匹配骨架樹的葉子節(jié)點，實驗證明這種方法提高了匹配精度。Bai 等人[25]提出了一種稱為路徑相似骨架圖的匹配算法。其主要思想是通過比較骨架端點之間的測地路徑（骨架末端節(jié)點之間的最短骨架路徑）來匹配骨架圖，該方法不考慮拓撲圖的結構，即使形狀存在一些變形，該方法也能得到正確的結果。Aslan等人[26]提出了一種運用不連續(xù)骨架進行形狀匹配的算法，這種表示沒有傳統(tǒng)連續(xù)骨架常見的不穩(wěn)定性問題，實驗結果證明該種表示方法魯棒性較好。Shen等人[27]提出了一種聚類結構，它基于一個名為公共結構骨架圖（Common Structure Skeleton Graph，CSSG）的骨架表示，這種骨架表示表達了集群的各個骨架的節(jié)點之間可能存在的對應關系，實驗結果證明該方法是有效的。Xie等人[28]提出了一種形狀匹配和建模方法，該方法基于代表性的骨架特征，在匹配過程中使用骨架分支與沿著形狀曲線的連續(xù)片段進行自然對應，避免了不同片段之間的錯誤對應。實驗結果顯示了其具有很好的性能。

骨架是形狀數據的一種簡單的一維表示，不僅能表示形狀的拓撲信息并且包含一些豐富的細節(jié)信息。然而，當形狀受到較大噪聲影響時，骨架可能會存在冗余的骨架枝，導致結構混亂，影響對真實形狀的判斷。

1.4 基于特征融合的形狀表示

在二維形狀特征表示中，為了提高形狀描述的準確性，有研究學者在傳統(tǒng)特征表示的基礎上，通過融合多種特征來表示二維形狀，并取得了很好的識別效果。

盧勇強等人[29]采用輪廓與骨架相結合的方法來描述二維形狀特征，該方法引入生物信息序列分析方法到二維形狀分析中，提出了一種輪廓骨架協(xié)同編碼方案。實驗結果表明，與原有方法相比，該方法提高了識別效率和準確性。Yang 等人[30]提出了一種用于形狀匹配和檢索的不變多尺度描述符，該方法對DCE 算法加以改進，改善了原算法的過度演化問題，并采用這種改進之后的稱為自適應離散輪廓演化（ADCE）的算法提取輪廓顯著特征點，并將歸一化面積、弧長和中心距離三種描述符進行融合，作為最終的二維形狀表示，實驗結果表明該表示方法具有較好的魯棒性。Lin等人[31]針對非線性失真導致形狀輪廓分類性能差的問題，提出了一種基于輪廓的多特征融合算法，實驗結果顯示該方法優(yōu)于原有的其他方法，解決了幾何變換和非線性失真導致的分類性能差的問題。Shen 等人[32]提出了一種稱為骨架相關形狀上下文（Skeleton-associated Shape Context，SSC）的形狀描述符，該描述符獲取與骨架信息相關的輪廓片段，在此基礎上，運用BoSF 框架進行特征提取，形成了一種對整體形狀有意義的特征向量。實驗結果表明，該方法在幾個標準形狀數據集上取得了很好的識別性能。Lin 等人[33]提出了一種運用區(qū)域特征進行形狀分類的方法，該方法將名為區(qū)域骨架描述符（Region Skeleton Descriptor，RSD）、區(qū)域面積描述符（Region Area Descriptor，RAD）和簡化形狀簽名（Simplified Shape Signature，SSS）三種描述符進行融合，作為最終的形狀表示，在核極限學習機[34-35]（Kernel Extreme Learning Machine，K-ELM）上進行實驗。實驗結果表明該方法的效率和準確率都很高。表3 對上文提到的特征融合方法做了簡單匯總。

表3 幾種特征融合的表示方法

上文提到的基于輪廓、區(qū)域、骨架以及特征融合的二維形狀表示方法各有優(yōu)缺點，表4對其做了一個匯總。

表4 各類表示方法對比分析

2 形狀分類方法

二維形狀分類識別中，通常選用機器學習分類器進行形狀分類，在提取出形狀特征后，通過選取訓練樣本，訓練分類器，最終可以得到有效的模型完成形狀分類識別。本章主要討論了在二維形狀分類中常用的傳統(tǒng)機器學習分類器、集成分類器以及深度學習方法。

2.1 傳統(tǒng)機器學習分類器

傳統(tǒng)的分類技術又可分為有監(jiān)督學習和無監(jiān)督學習兩類，在二維形狀分類中，常用的分類器多為有監(jiān)督分類器，包括樸素貝葉斯分類器、隨機森林、支持向量機等等。

樸素貝葉斯分類器是一種概率分類方法，其原理是利用貝葉斯公式，根據某種特征的先驗概率計算出它的后驗概率，選擇具有最大后驗概率的類別作為特征所屬的類別。樸素貝葉斯分類器的優(yōu)點在于數據集易于訓練，并且完成計算所花費的時間較少。

Sun 等人[36]利用類段集對輪廓形狀進行分類，實驗采用了貝葉斯分類器，得到了很高的分類精度。

隨機森林（RF）是一種有監(jiān)督學習的分類器，它包含多個決策樹。決策樹是一種樹形結構，它通過將數據劃分成具有相似性的子集來完成樹的構建，這種劃分過程會一直持續(xù)到不能繼續(xù)劃分下去為止。樹中包含兩種節(jié)點，其中，有兩個及以上分支的節(jié)點稱為決策節(jié)點，沒有分支的節(jié)點是葉子節(jié)點。隨機森林是許多決策樹的一個集成，并且輸出的類別由個別樹輸出類別的眾數決定。隨機森林的效率很高，即使是大型的數據集，依舊可以高效運轉，且在數據不一致的情況，它也能提供準確性。

Lepetit 等人[37]將隨機森林分類器用于三維物體檢測和姿態(tài)估計。Bosch等人[38]比較了隨機森林分類器與支持向量機（SVM）用于圖像分類的性能，結果表明，當使用感興趣區(qū)域（Region Of Interest，ROI）時，隨機森林分類器較支持向量機有約5%的性能提升，且當在分類器訓練期間生成額外的數據時，隨機森林分類器的性能也會得到提升，文章方法的隨機森林分類器與支持向量機相比，最終得到一個約10%的性能提升。Huang等人[39]提出了一種管狀結構分類的方法，該方法提取了三個形狀描述符：三角形面積、距離閾值以及最小慣性軸，將其組合作為最終的形狀表示，并使用隨機森林分類器進行訓練和實驗，取得了很好的分類結果。Keskin 等人[40]運用隨機森林分類器進行手勢形狀分類，同樣得到了很好的分類效果。

支持向量機（SVM）是一種有監(jiān)督學習的分類器，是當前最常用的分類算法。SVM的決策邊界是對學習樣本求解的最大邊距超平面。SVM的目標是以最小的錯誤率對物體進行分類。SVM的優(yōu)勢在于給出的結果比其他方法更準確，但是它的訓練過程需要一定的時間且需要額外內存來存儲訓練圖像[41]。

文獻[16]使用線性支持向量機分類器進行形狀分類，同時提出使用徑向基函數核和交集核等能夠提高性能，但較為耗時。文獻[13]同樣使用了線性支持向量機進行形狀分類。文獻[32]使用線性支持向量機進行形狀分類，并指出該方法使用非線性核分類器反而會導致性能下降。Daliri 等人[42]提出了一種形狀識別的核方法，該方法使用支持向量機進行形狀分類，在常用的形狀分析數據集上均取得了較好的結果。

2.2 集成分類器

對于有監(jiān)督機器學習任務，集成學習是一種有效的方法，其思路是通過多機器學習算法的集成來提升預測的結果。理論上，集成學習在訓練集上比單一模型的擬合能力更強，且某些集成學習方法也能更好地處理過擬合的問題。對于分類性能好的分類器，集成學習往往能夠給予更高的權重。

常用的集成方法包括bagging[43]、boosting[44]等，除此之外，投票法、簡單加權以及隨機森林方法也常用于分類器的集成。

采用相同的分類算法，在不同的訓練集子集上進行訓練，且采樣時將樣本放回，這種方法稱為bagging，也稱為自舉匯聚法。使用該方法進行集成得到的分類器與單一分類器相比，降低了在訓練集上訓練的偏差和方差。該方法流行的原因不僅在于其可以并行進行，還因為此方法易于拓展。

提升法是指將多個弱學習器結合成為一個強學習器的集成方法，代表方法包括AdaBoost 和梯度提升兩種。兩種方法類似，差別僅在于AdaBoost 方法不再是調整單個預測器的參數使得成本函數最小化，而是不斷在集成中加入預測器，使模型越來越好。該方法的缺點是無法并行，所以在拓展方面的表現不如bagging方法。

投票法是指將多個分類器的結果進行聚合，然后將得票最多的結果作為最終的結果的一種方法，這種大多數投票分類器也被稱為硬投票分類器，其工作原理如圖4所示。

圖4 多數投票法集成分類器

簡單加權是指使用不同的分類器在同一訓練集上進行訓練，得到的結果通過權重進行組合的一種集成方法。通常，組合權重α可通過學習過程獲得。加權組合得到的集成分類器性能往往高于單一的分類器。

Mohandes 等人[45]提出了一個基于準則的多分類器組合技術框架及其應用領域，將分類器的組合類型大致分為四類：組合級別、閾值類型、組合的適應性和基于集成的方法。Wang等人[46]提出了一種融合特征以及分類器的方法來進行形狀識別，該方法通過訓練7種不同的單分類器，并通過平均規(guī)則進行融合得到分類結果，在標準形狀分析數據庫上顯示出很好的性能。Rida等人[47]提出的掌紋識別，Zhao 等人[48]提出的手寫字體識別，均采用了集成學習的技術，顯示出分類器集成相較于單分類器，性能得到了提升。

2.3 深度學習方法

卷積神經網絡（CNN）是一類包含卷積計算且具有深度結構的前饋神經網絡，它是多層感知器（MLP）的一個變種形式。其基本結構由三層組成：輸入層、隱藏層、輸出層。其隱藏層又包含卷積層、池化層、全連接層等結構。CNN 對于大數據集的處理效果很好，當數據集樣本偏小時，性能受到很大影響。采用CNN 進行形狀分類識別流程如圖5所示。

圖5 卷積神經網絡進行形狀識別分類流程圖

Atabay 等人[49]提出了一種適用于二值圖像的CNN結構，該方法在小尺度的二值圖像上性能較高且時間復雜度較低。在另一篇文章中，Atabay 等人[50]將CNN 用于葉片圖像分類，引入指數線性單元（ELU）代替校正線性單元（ReLU）得到新的CNN 結構。實驗結果表明在兩個葉片數據集上，新的CNN網絡結構性能優(yōu)異。Tixier等人[51]利用傳統(tǒng)的2D CNN網絡進行圖形分類，該方法將圖形進行處理之后輸入進網絡來進行后續(xù)操作，該方法在時間復雜度方面優(yōu)于圖核方法，并且適用于更大圖形的更大規(guī)格的數據集。表5 對上文提到的幾種分類器做了簡單匯總。

表5 幾種不同分類器的識別率比較

3 二維形狀標準數據庫

為了便于開展二維形狀分析研究，目前，研究學者建立了多個二維形狀標準數據庫，本文將常用的二維形狀標準數據庫進行了匯總。

MPEG-7數據庫[52]是形狀分析研究領域中最常用的數據庫，其包含70個類別，在每個類別中，有20個形狀，因此數據集中的形狀總數為1 400個。

Animal數據庫[53]包含20個類別，每個類別中有100個形狀，總共由2 000 個形狀組成。由于動物是非剛性物體，該數據集中的形狀具有很高的類內可變性，因此，這個數據庫的分類識別任務相當具有挑戰(zhàn)性。

Swedish leaf 數據庫[54]由15 個類別組成，每個類別有75個樣本，共有1 125個形狀。由于有較大的類內差異，這個數據庫的識別也相當具有挑戰(zhàn)性。

ETH-80數據庫[55]包含八類對象。每個類別中有10個物體是從不同的視角拍攝的，每個物體有41 幅彩色圖像，如圖6所示，共有80個樣本。

圖6 ETH-80數據庫

Tools數據庫[56]包含8類對象，其中包括6類不同的剪刀和2 類訂書機，一共40 個形狀，如圖7 所示。在每一類中，這五種形狀相互之間有較大的關節(jié)變形差異。

圖7 工具數據庫

針對二維形狀識別分類問題，分類識別準確率[16]往往是執(zhí)行分類任務的算法的評估標準?；跈C器學習的方法中，半訓練和留一法是兩種常用的評估方案。半訓練是指將一半樣本用于算法的訓練，另一半樣本用于實驗測試。留一法是指將90%的樣本用于算法訓練，剩下的10%樣本用于實驗測試。

表6 匯總了上文提到的表示方法和識別分類方法在標準數據庫上的識別率。并將現有在上述五個數據庫上表現較突出的方法的識別率匯總在表7之中。

表6 各方法識別率匯總

表7 不同數據庫上表現較突出的方法的識別率

4 研究發(fā)展趨勢

隨著二維形狀特征描述及分類識別技術研究的不斷深入，學者們提出了眾多的形狀描述符以及識別分類方法。由于實際中的形狀往往存在噪聲、變形、遮擋等情況，使得這些方法的準確實現受到挑戰(zhàn)。因此，對該領域的研究還有很多值得深入的地方。

在表示方法方面，單一的人工特征描述符方法接近穩(wěn)定，基于此，新提出的特征描述符往往嘗試將傳統(tǒng)特征進行融合，將融合后的特征作為最終的形狀描述符，以提高形狀表示的準確性。在分類識別方法方面，傳統(tǒng)的動態(tài)規(guī)劃方法以及相似性度量方法存在算法復雜度高以及精確度不夠的問題，使得機器學習方法逐漸被學者們應用到二維形狀識別分類的研究當中。不滿足于單一分類器得到的結果，已有學者運用集成學習方法將多種分類器進行集成，以提高分類識別的精確度。同時，深度學習方法也在該領域得到了應用，并展示出良好的性能。

5 結束語

本文綜述了用于二維形狀特征描述及分類識別領域的新的技術。主要從形狀特征提取、形狀分類識別、形狀數據庫三個方面展開討論。形狀特征提取方法主要基于輪廓、區(qū)域、骨架三種特征，特征融合方法的提出，一定程度上彌補了單一特征進行形狀分類識別所表現出的不足。分類識別方法主要基于機器學習，現有方法大多使用單一分類器完成分類識別任務，集成學習方法也在形狀分類識別領域得到應用，并取得了令人滿意的結果。文中列舉的形狀分析數據庫是進行二維形狀分類識別實驗常用的數據庫，不同方法在不同數據集上的表現略有差別。