結(jié)合輪廓及骨架序列編碼的二維形狀識別

盧勇強，栗志揚，陳祎楠，劉朝斌，黃一鳴

（大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，大連116026）

形狀是人類認(rèn)知物體的一個重要線索。某些情況下，物體可能并不具備亮度、紋理或顏色等信息，只能通過其形狀來表達。僅通過形狀信息，人類仍然可以輕松識別不同的物體及其類別。而且，形狀對于物體的顏色、光照和紋理的變化是具有穩(wěn)定性的［1］，也可以作為其他物體表示的一種輔助，以提高物體表示及識別的準(zhǔn)確性。由于形狀信息具備上述優(yōu)點，基于形狀的物體高效表示及識別一直是研究的熱點。

計算機視覺中研究的形狀一般分為二維（平面）形狀和三維形狀兩種數(shù)據(jù)類型，兩類形狀有多種應(yīng)用領(lǐng)域。其中，二維形狀被廣泛地應(yīng)用于諸如商標(biāo)檢索、指紋表示及識別、物體定位、圖像檢索等領(lǐng)域中［2］。這些應(yīng)用的一個基本問題是如何形成一種豐富、簡潔和高效的形狀特征表示［3］。典型的二維形狀表示方法可以大體上分為三類：基于輪廓的形狀表示、基于區(qū)域的形狀表示和基于骨架的形狀表示。本文主要關(guān)注的是基于輪廓和基于骨架的二維形狀表示及識別方法。

形狀的輪廓提供了形狀大部分的整體及細(xì)節(jié)信息，是形狀表示中最為頻繁采用的對象。基于輪廓的形狀表示［1-2］多數(shù)把輪廓進行離散化采樣，通過統(tǒng)計輪廓序列上采樣點的空間位置分布關(guān)系，來提取形狀輪廓上一些穩(wěn)定的特征量，一般稱為形狀特征描述符。這些特征量可以是全局的［3］或者是局部的［1］，其中最為典型的特征子應(yīng)該是形狀上下文（Shape Context，SC）［1］。形狀上下文在每個采樣點上，利用二維直方圖統(tǒng)計其余采樣點相對于該點的距離和角度變化信息。兩個形狀之間的相似性通過各自采樣點集的最優(yōu)匹配計算，采樣點之間的匹配誤差由其形狀上下文描述向量衡量。實驗表明，基于輪廓的形狀表示方法，在形狀簡單變化時具備較好的穩(wěn)定性，可以有效應(yīng)對形狀中的噪聲和輕度的變形。

不過在形狀發(fā)生一些等距變換（如關(guān)節(jié)變換）時，基于輪廓的表示方法往往穩(wěn)定性不好，而此時形狀骨架的拓?fù)浣Y(jié)構(gòu)會保持不變。可以借助骨架提出形狀更簡潔且穩(wěn)定的描述方法。一般來說，骨架是形狀內(nèi)所有最大內(nèi)切圓圓心的集合，提供了形狀的厚度沿骨架的變化信息，對非脊變形和關(guān)節(jié)具有不變性，且對于輪廓上的噪聲比較魯棒。這些優(yōu)點使得基于骨架的形狀表示獨具優(yōu)勢。

然而現(xiàn)實中的形狀往往存在較多變形，如放縮、遮擋、大尺度噪聲、同一形狀的多樣性等，給形狀的準(zhǔn)確表示和識別帶來很大挑戰(zhàn)。近期，二維形狀方面的研究進展包括基于深度神經(jīng)網(wǎng)絡(luò)的方法［4］和基于生物信息學(xué)的方法［5］等。其中，深度神經(jīng)網(wǎng)絡(luò)一般需要大規(guī)模的標(biāo)記樣本，而二維形狀公開數(shù)據(jù)集的樣本規(guī)模往往較小，制約了深度神經(jīng)網(wǎng)絡(luò)在二維形狀研究領(lǐng)域中的推廣。與傳統(tǒng)研究方法不同，Bicego和Lovato［5］提出了利用生物信息學(xué)模型解決二維形狀的識別問題，其基本思想是把形狀輪廓按照其空間分布編碼為生物信息序列，即DNA分子序列，然后借助標(biāo)準(zhǔn)的生物信息序列分析工具來進行序列之間的相似性分析，以及在此基礎(chǔ)上的形狀識別或分類。

而目前兩個形狀之間的相似性分析，通用的方法還是借助于其特征描述點集之間的最優(yōu)匹配。匹配過程由傳統(tǒng)的動態(tài)規(guī)劃算法實現(xiàn)，存在算法復(fù)雜度較高且匹配精確度不夠等問題。利用生物信息序列分析工具替代傳統(tǒng)基于動態(tài)規(guī)劃的匹配方法，無疑將有助于豐富輪廓之間相似性的計算方法，同時，生物序列相似性匹配具有幾十年的研究歷史，涌現(xiàn)出了多種針對不同場景的匹配算法。所以，利用生物信息序列分析方法，進行二維形狀分析顯然頗具新意，是一個有不錯前景且值得進一步深入研究的方向。

基于上述思路，引入生物信息序列分析方法到二維形狀分析及識別中。研究中發(fā)現(xiàn)，輪廓中的細(xì)長分支會使得生物信息編碼序列中出現(xiàn)大量方向相反且長度相近的編碼，這些編碼對于形狀相似性匹配貢獻較少，且有時會制約匹配的精度。區(qū)別于Bicego和Lovato［5］的工作，提出了結(jié)合形狀輪廓和骨架的協(xié)同編碼方案。

本文的主要貢獻：①提出了一種新型的二維形狀表示及識別方法，該方法基于生物信息學(xué)，把二維形狀轉(zhuǎn)化為生物信息序列，可以借助生物信息學(xué)領(lǐng)域的序列匹配方法提高二維形狀的識別精度。②提出了一種二維形狀的輪廓及骨架協(xié)同編碼的方案。該方案利用骨架表示形狀中的細(xì)長分支，并分別對輪廓和骨架進行不同類型的編碼，具備編碼簡潔、后續(xù)匹配準(zhǔn)確性高等優(yōu)點。同時在基于草圖圖像檢索（SBIR）也有一定的應(yīng)用前景［6］。③在三個公開形狀數(shù)據(jù)集上做了大量的形狀識別實驗，并采用不同的準(zhǔn)確性評價指標(biāo)，與多種通用形狀識別方法進行了詳細(xì)的比較，證明了本文方法的優(yōu)勢和有效性。

1 形狀描述及匹配

首先簡單介紹一些典型的基于輪廓和基于骨架的二維形狀表示及識別方法，然后給出在形狀匹配中所采用的生物信息序列分析工具的相關(guān)概述。

1.1 基于輪廓的形狀描述

基于輪廓的形狀表示方法是二維形狀描述中最為通用的一類方法，在二維形狀識別中有著廣泛的應(yīng)用。其描述方法的共同特點是通過統(tǒng)計輪廓序列上點的空間位置分布關(guān)系來提取形狀輪廓某種不變特征量。

Belongie等［1］根據(jù)輪廓點空間位置關(guān)系提出了一種形狀上下文的描述方法。該描述方法對輪廓序列上的每個點采用一個向量來表示，通過構(gòu)造一組特征向量對形狀目標(biāo)進行描述。該方法著重考察輪廓序列上的一個點與該輪廓序列上的其他所有采樣點的空間位置分布關(guān)系，具有包含信息量大、描述能力強和魯棒性良好等特點。

Ling和Jacobs［2］基于形狀上下文的思想，提出了利用輪廓點間的內(nèi)部距離（Inner-Distance Shape Context，IDSC）來代替Belongie等［1］計算形狀上下文中采用的歐氏距離，把輪廓序列上兩個采樣點經(jīng)形狀內(nèi)部的最短路徑長度定義為內(nèi)部距離。該方法適用于產(chǎn)生柔性變化目標(biāo)的識別，實驗中取得了較好效果。

Biswas等［7］基于內(nèi)部距離的形狀上下文描述方法，提出了一個新的形狀索引和檢索框架。通過索引，高效計算待檢索形狀與數(shù)據(jù)庫中形狀的相似度，改進了傳統(tǒng)基于動態(tài)規(guī)劃的形狀匹配算法的效率。總體上說，基于輪廓形狀描述方法的優(yōu)點主要表現(xiàn)在以下三個方面：

1）可以把二維形狀整體信息與局部信息有機地結(jié)合在一起，較準(zhǔn)確地描述形狀結(jié)構(gòu)特征。

2）可以與多種形狀匹配算法組合，靈活地采用基于動態(tài)規(guī)劃的形狀匹配或基于詞典的形狀索引及匹配。

3）可以通過圖像分割及物體邊界提取，方便地應(yīng)用于自然圖像的形狀識別，具有較好的實用性。

這類方法主要存在以下兩個方面的不足：

1）僅考慮了目標(biāo)形狀的輪廓邊界信息，而輪廓容易受到形狀變形的影響，導(dǎo)致提取的特征量有時無法準(zhǔn)確反映物體信息。

2）對于復(fù)雜場景中的多個物體，基于輪廓的表示方法往往存在輪廓線參數(shù)化困難等問題，大多只能處理簡單場景下的物體圖像。

1.2 基于骨架的形狀描述

骨架是形狀數(shù)據(jù)一種重要的幾何特征描述符，由Blum在1967年首次提出［8］，并將其應(yīng)用到形狀識別中。使用一種基于最大內(nèi)切圓模型的骨架表示方法，具體指圓心在形狀內(nèi)部、且至少內(nèi)切形狀輪廓上兩個點的圓形。形狀的骨架點就是這些內(nèi)切圓圓心的集合。

陳展展等［9］提出利用樹形結(jié)構(gòu)表示形狀骨架，首先根據(jù)歐氏距離變換定義一個骨架點的中心點，然后構(gòu)造以骨架中心點為根節(jié)點的骨架樹，使用骨架中心點到骨架端點路徑上經(jīng)過的骨架點構(gòu)造特征向量，并利用改進的最優(yōu)子序列雙射算法來進行骨架點之間的匹配，以用于二維形狀的分類和識別。

Bai和Latecki［10］提 出 了 一 種 基 于 骨 架 路 徑相似性的形狀識別，屬于整體對局部的形狀描述方法。通過提取當(dāng)前骨架端點到其他所有骨架端點間骨架路徑上的特征量，對骨架端點進行描述，結(jié)合最優(yōu)匹配算法對形狀目標(biāo)進行識別。

基于骨架形狀描述方法的優(yōu)點主要表現(xiàn)在以下三個方面：

1）骨架表示了目標(biāo)形狀的整體結(jié)構(gòu)，也能反映目標(biāo)形狀的邊界。

2）骨架簡化了目標(biāo)形狀的描述難度，也能方便目標(biāo)形狀的匹配。

3）骨架保持了形狀的重要拓?fù)浣Y(jié)構(gòu)和幾何特征，也能降低因噪聲而引起的輪廓失真。

這類方法存在以下兩個方面的不足：

1）骨架不能有效抵抗大尺度噪聲的影響，會產(chǎn)生較多的冗余骨架枝，易出現(xiàn)主次不分、結(jié)構(gòu)混亂的現(xiàn)象，從而影響對物體真實形狀和連接關(guān)系的判斷。

2）輪廓邊緣的突起或遮擋會引起形狀骨架的變化，有時會較大改變骨架的拓?fù)溥B接，造成目標(biāo)形狀骨架的信息多余，從而影響骨架的度量和匹配。

1.3 生物信息序列分析工具

生物信息學(xué)中，基因序列在區(qū)分生物種類上有決定性的作用。經(jīng)過過去40年生物信息學(xué)的研究，在基因序列分析方面已經(jīng)有了大量的工具和解決方案。在基因序列分析工具中，主要分為雙序列比較工具和多序列比較工具。

雙序列比較工具分為全局比較和局部比較：全局比較嘗試將兩個完整的基因序列進行對準(zhǔn)，而局部比較則是將兩個基因序列的高相似性短區(qū)域進行對準(zhǔn)。最有名的雙序列比對算法是Needleman-Wunsch（全局比較）［11］和Smith-Waterman（局部比較）［12］。近些年，比較通用的基因序列比較方法是BLAST工具（基本局部對比較工具）［13］，在比對的準(zhǔn)確性和效率上都有著較好的表現(xiàn)。

多序列比較工具是對三個以上基因序列比較，首先對所有序列對準(zhǔn)，然后進行多序列的比較。其最廣泛使用的方法是漸進技術(shù)，該技術(shù)通過從最相似的一對基因序列進行對齊到最不相似的基因序列，近些年主要使用多序列比較工具包括Clustal［14］、MUSCLE等。

基于生物信息序列進行形狀分析的優(yōu)點主要表現(xiàn)在以下兩個方面：

1）把二維形狀編碼為生物信息序列，是一種新型的描述二維形狀幾何分布的方法，拓展了傳統(tǒng)的二維形狀表示技術(shù)。

2）可以利用多種生物信息序列比對工具，進行形狀編碼的相似性匹配，從而改進了傳統(tǒng)基于動態(tài)規(guī)劃的匹配算法，提高了算法效率。

這類方法存在以下兩個方面的不足：

1）本質(zhì)上，生物信息序列表示屬于一種形狀簽名技術(shù)，相比于形狀上下文，其表示準(zhǔn)確性需要進一步提高。

2）目前二維形狀的生物信息編碼技術(shù)，尚存在編碼冗余問題，同時也未充分考慮如何使形狀編碼序列具有更多基因?qū)用娴男畔ⅰ?/p>

2 基于輪廓及骨架序列的編碼方法

形狀編碼及匹配流程如圖1所示。本節(jié)具體給出形狀輪廓和骨架的協(xié)同表示及編碼方案。首先，假定二維形狀數(shù)據(jù)F 的輪廓已經(jīng)得到，C（F）=｛c1，c2，…，cn｝為輪廓上的n個等距采樣點，并按順時針排列，其中ci=（xi，yi）。其次，利用二維形狀骨架提取方法［15］得到形狀F的骨架S（F）。

圖1 二維形狀匹配流程圖Fig.1 Flowchart of 2D shape matching

2.1 形狀歸一化

在形狀編碼過程中，形狀的方向?qū)幋a有著很大的影響。兩個相同的形狀，如果編碼方向不同，得到的形狀編碼也會不同，從而影響編碼之間的距離。為了解決這個問題，需要對形狀進行歸一化。首先，旋轉(zhuǎn)形狀使其長軸與x軸平行，消除不同旋轉(zhuǎn)角度對形狀分類結(jié)果的影響。

形狀的長軸可以由形狀數(shù)據(jù)的主成分分析得到，也可以通過形狀中距離最長的兩個點簡單確定。實驗中，發(fā)現(xiàn)兩種選擇的形狀識別結(jié)果相近。簡單起見，本文選擇了后者。旋轉(zhuǎn)對齊后，還可能會存在形狀與目標(biāo)匹配形狀180°翻轉(zhuǎn)的情況。本文采用的解決方案是：以形狀長軸作為分隔線，把形狀分為兩個部分，使得面積較大的那一部分處于長軸的上方。

此時，形狀與目標(biāo)匹配形狀可能還存在大小比例不一致的問題，本文編碼方法本質(zhì)上可以有效應(yīng)對形狀之間的比例尺度不一致的問題，不過，為了與其他形狀匹配方法進行比較，實驗中，還是通過標(biāo)準(zhǔn)的尺度歸一公式（式（1））對形狀進行尺度歸一化。其中，D為目標(biāo)長軸大小，D0為當(dāng)前形狀長軸大小。

2.2 形狀的輪廓與骨架聯(lián)合表示

給定形狀F，利用上述標(biāo)準(zhǔn)化方法得到其輪廓C（F），同時提取骨架S（F），如圖2所示。圖中左邊是獲取了輪廓點與骨架點之后的形狀，右邊藍色代表骨架點，綠色代表輪廓點。假定在每個輪廓點或骨架點周圍至多有兩個輪廓點或骨架點位于其8個連通方向上。這里的骨架點不包括骨架的關(guān)節(jié)點。

Bicego和Lovato［5］提出可以把形狀輪廓轉(zhuǎn)化為生物信息序列即DNA分子序列，本質(zhì)上是對每個輪廓點的8個方向上的輪廓點，利用字母A～H依次編碼。不過發(fā)現(xiàn)，這種編碼方案在形狀細(xì)支處兩邊的編碼會產(chǎn)生過多的冗余，使大量重復(fù)的編碼被考慮進形狀分類，如圖3所示。圖3中細(xì)支上，a到b點的相對位置關(guān)系可以近似另一邊c到b點相對位置關(guān)系。也即輪廓點從a到b的編碼和從b到c的編碼雖然不一樣，但是存在一個變換，在該變換下，兩個編碼是相似的。所以，a到b的編碼和b到c的編碼存在冗余。而發(fā)現(xiàn)，如果利用藍色的骨架表示這個細(xì)支，也即通過e到d的編碼代替a到c的編碼可以有效減少編碼的冗余。同時，這種編碼方案也可以繼承骨架表示的優(yōu)點。

圖2 形狀的輪廓與骨架Fig.2 Contour and skeleton of a shape

圖3 形狀細(xì)支處的輪廓與骨架Fig.3 Contour and skeleton of branch of a shape

另外，如果使用整個輪廓點進行編碼，如編碼圖3所示的昆蟲。昆蟲在細(xì)支處發(fā)生變形，細(xì)支處兩邊輪廓上一般會產(chǎn)生大體相似的變形，從而形狀的一處變形會產(chǎn)生編碼兩處較大的改變。而在非細(xì)支處，輪廓的一側(cè)變形，很難使這段輪廓在骨架上對應(yīng)的另一端輪廓發(fā)生變形。所以，僅依靠輪廓信息進行編碼無法表示形狀的這種特性，從而降低了編碼的準(zhǔn)確性。顯然，如果在細(xì)支處采用骨架點編碼，在主體輪廓處采用輪廓點編碼，可以兼顧編碼的簡潔性和準(zhǔn)確性，有效解決上述問題。

同時，形狀中往往會存在形變的情況，如動物形狀和日常物體形狀等。常見的形變包括輕度變形、遮擋和關(guān)節(jié)變換等。而骨架處理這些變形問題獨具優(yōu)勢［10］，由于本文引入了針對骨架的編碼，所以也具備了對于形變物體一定的魯棒性。

當(dāng)然，在形狀中準(zhǔn)確定位其細(xì)支位置，本身也是一個比較有挑戰(zhàn)性的問題。不過，由于本文編碼方案可以單獨在輪廓上編碼，所以并不要求對于形狀中分支的準(zhǔn)確定位。實驗中，認(rèn)為骨架特征尺寸（內(nèi)切圓半徑）低于一個給定閾值的骨架點對應(yīng)的輪廓點處于一個細(xì)支中，這些輪廓點不參與編碼過程，由其骨架點的編碼代替。圖3的形狀經(jīng)上述方法可以確定形狀中所有的細(xì)支和主體，從而得到一個聯(lián)合部分骨架和部分輪廓所形成的形狀表示，如圖4黑色點所示。

圖4 輪廓與骨架的聯(lián)合表示及默認(rèn)的編碼方向Fig 4 A combined representation of contour and skeleton and default encoding direction

2.3 形狀信息編碼方法

在得到形狀的輪廓和骨架的聯(lián)合表示之后，可以對形狀進行編碼。區(qū)別于Bicego和Lovato［5］單一編碼形式，對形狀輪廓和骨架分別采用不同的編碼形式，即把二維形狀轉(zhuǎn)化為字母和數(shù)字聯(lián)合表示的字符編碼。

同時，Bicego和Lovato［5］形成編碼序列的方法是對每個輪廓點的8個方向上的輪廓點依次使用字母A～H進行編碼。如果輪廓存在一些局部變形，這種編碼方式的結(jié)果是不太穩(wěn)定的。為了改善這一方案，提出以下編碼方法。

在輪廓上，每隔兩個輪廓點取一個輪廓點，這樣可以在一定程度上解決輪廓發(fā)生局部變形時穩(wěn)定性不足的問題，也可以精簡輪廓部分編碼的長度，最大限度地保留輪廓上的大部分細(xì)節(jié)信息。在實驗部分，給出了輪廓點的選取方式對準(zhǔn)確率影響的比較，在實驗結(jié)果看來，目前的方案是最優(yōu)的。由于骨架部分往往僅占全部形狀編碼的一小部分，所以取所有骨架點進行編碼，這樣可以使骨架部分的編碼長度最長，所占全部編碼的比重也最大，使骨架編碼的貢獻度最高。為了能在字符編碼中分別區(qū)分輪廓信息給予的貢獻和骨架信息給予的貢獻，分別用字母和數(shù)字來編碼輪廓和骨架。

按照上述編碼方式，在每個輪廓點周圍會存在24個方向可能出現(xiàn)下一個輪廓點，對每個可能出現(xiàn)的下一個輪廓點的位置賦予從A～X的字母表示。起始點設(shè)為圖像最左上方的輪廓點，即通過下一個輪廓點與此輪廓點的相對位置關(guān)系，來表示此輪廓點的編碼。每個骨架點周圍會有8個方向出現(xiàn)下一個骨架點，對每個可能出現(xiàn)的下一個骨架點的位置賦予從1～8的數(shù)字表示。起始點為離輪廓點最近的骨架點，結(jié)尾的骨架點用0表示，即通過下一個骨架點與此骨架點的相對位置關(guān)系，來表示此骨架點的編碼。通過把骨架和輪廓進行編碼，會得到圖像的編碼，如圖5所示。

關(guān)于編碼的方向如圖4紅色箭頭所示。編碼開始的起點為輪廓部分最靠近左上方的點，沿逆時針方向?qū)π螤钌纤悬c按照上述規(guī)則進行編碼，最后回到起點。

圖5 編碼構(gòu)造規(guī)則Fig.5 Encoding construction rule

2.4 使用生物學(xué)工具形狀分類

在通過2.3節(jié)轉(zhuǎn)換后，可以得到不同形狀唯一的字符編碼表示。通過生物信息學(xué)的映射規(guī)則，把字符編碼映射為基因序列，在分類時，就可以使用大量生物信息學(xué)領(lǐng)域的對齊工具。區(qū)別于Bicego和Lovato［5］使用的NW （全局比較）和SW（局部比較）對齊工具，使用更為高效和準(zhǔn)確的MUSCLE對齊工具。因為NW 和SW 對齊工具只能比較2個基因序列，效率不高且對齊效果太過依賴生物基因信息的氨基酸占比。在此使用的是支持多序列同時比較、對生物多樣性更為適合的MUSCLE對齊工具。之后實驗會給出使用不同對齊工具對結(jié)果的影響。

通過對齊工具的比較，可以得到形狀之間的相似度的評分，由于該評分是通過生物學(xué)的基因?qū)R工具獲得，為了使該評分能表現(xiàn)形狀上的基本信息，引入懲罰項，使評分更為合理。

在懲罰項的選擇中，使用簡單形狀描述符。文獻［16］已證實簡單形狀描述符能達到這一目的。這里選用最小邊界矩形面積及離心率作為懲罰項。懲罰項如式（2）。最小邊界矩形是通過在原形狀上利用周長最小原則做外界矩形，計算此矩形的面積為最小邊界矩形面積，離心率是最小外界矩形的寬度與長度之比。

加入懲罰項之后，通過計算式（2），最終得到2個形狀之間的相似度評分：

式中：SF、SF′表示2個形狀最小邊界矩形面積；EF、EF′表示2個形狀所形成的最小邊界離心率。

3 實驗及分析

使用不同的數(shù)據(jù)集對本文方法進行性能評價。思路來源于文獻［5］。首先把二維形狀通過輪廓信息轉(zhuǎn)換為生物信息編碼，然后使用現(xiàn)有的編碼分析工具：全局對齊工具（NW）和局部對齊工具（SW）計算形狀之間的相似性。提出了一種結(jié)合輪廓和骨架的混合編碼方案，并采用MUSCLE對齊工具，以進一步提高形狀相似性度量的準(zhǔn)確性。在形狀的識別實驗中，論文采用文獻［5］中方法，利用K近鄰分類器進行形狀的分類和識別。

3.1 數(shù)據(jù)集和分類方法

3.1.1 MPEG-7數(shù)據(jù)集MPEG-7數(shù)據(jù)集是形狀分析研究領(lǐng)域中最流行的數(shù)據(jù)集之一。有70個不同的類別組成，每個類別中有20個形狀，因此數(shù)據(jù)集中總計有1 400個形狀。比較方法使用牛眼比較法（bullseye），即對每個查詢形狀，計算按相似度排序的前40個結(jié)果中，屬于同一類的形狀的百分比。同時，本文也采用留一法（leave one out）和留半法（half training）進行識別準(zhǔn)確性的評價。留一法，即每次在同一類形狀中抽取一個作為測試樣本，其余作為訓(xùn)練集，檢測樣本集被準(zhǔn)確分類的百分比。留半法，即每次在一類中選取一半作為測試集，其余全部作為訓(xùn)練集，檢測樣本集被成功分類的百分比。

3.1.2 ETH-80數(shù)據(jù)集

ETH-80數(shù)據(jù)集包含8類形狀，每個類別中有10個對象，每個對象具有41幅不同角度拍攝的彩色圖片。由于本文主要是對形狀進行分類，不考慮圖片中的顏色問題。在識別準(zhǔn)確率評價中，采用基于K最近鄰的留一法。即對每個形狀找與其相似度最高的K個形狀（不包括本身），記該形狀的類別為K個形狀中類別出現(xiàn)頻次最高的那一類。最后統(tǒng)計所有形狀識別（分類）成功的個數(shù)，從而得到總體的識別準(zhǔn)確率。

3.1.3 Swedish leaf數(shù)據(jù)集

Swedish leaf數(shù)據(jù)集是全部由樹葉圖片組成的數(shù)據(jù)集，由15個類別組成，每個類別包含75個樣本。Swedish leaf數(shù)據(jù)集由高分辨率的彩色圖像組成，雖然提供了豐富的信息，但是與形狀分類無關(guān)。所以，在原分辨率不變的情況下，本文對圖像取二值處理，即只保留圖像中葉子的形狀信息，這樣既可以保留葉子的細(xì)節(jié)，也可以去除圖像中的多余信息。識別準(zhǔn)確率的評價采用基于K最近鄰的留一法進行。

3.2 MPEG-7數(shù)據(jù)集的識別結(jié)果

MPEG-7數(shù)據(jù)集每一類形狀的代表如圖6所示。

MPEG-7數(shù)據(jù)集利用牛眼比較法，和現(xiàn)有的方法的對比結(jié)果如表1所示。可以看出，在牛眼比較的準(zhǔn)確率上，本文方法并不是最好的。離性能表現(xiàn)最好的方法尚有一定的差距，但是對于文獻［5］得到的77.24%的準(zhǔn)確率，本文提出的編碼方案還是有較大提升。主要得益于形狀中細(xì)支處使用骨架和主體上使用輪廓的協(xié)同編碼方式。

圖6 MPEG-7數(shù)據(jù)集Fig.6 MPEG-7 dataset

性能表現(xiàn)最好的2種方法是IDSC+LP和IDSC+SSP，準(zhǔn)確率均在90%以上。不過，這2種方法性能的提升均建立在對于形狀相似度矩陣的距離學(xué)習(xí)上，屬于形狀識別領(lǐng)域中的后處理方法。該類方法必須提前得到一個質(zhì)量較好的形狀相似度矩陣，且并不能提供形狀的表示。這與本文方法及形狀上下文（SC和IDSC）等方法有本質(zhì)上的區(qū)別。

進一步，在MPEG-7數(shù)據(jù)集上，本文分別使用了留一法和留半法的評價原則和現(xiàn)有的方法進行了比較，結(jié)果如表2所示。

由表2可見，本文編碼方法在使用留一法和留半法時都取得了一個較高的準(zhǔn)確率，和文獻［5］的方法結(jié)果相當(dāng)，不過本文的編碼較為簡短，冗余較小。由于一些形狀存在比較明顯的細(xì)支，另一些形狀不存在。下面分別給出含有細(xì)支處形狀和沒有含有細(xì)支處形狀對于形狀編碼的可視化查詢，如圖7所示。

表1 MPEG-7數(shù)據(jù)集上牛眼比較法分類準(zhǔn)確率對比Table 1 Comparison of classification accuracy rate of bullseye method on MPEG-7 dataset

表2 MPEG-7數(shù)據(jù)集上的分類準(zhǔn)確率對比Table 2 Comparison of classification accuracy rate on MPEG-7 dataset

圖7中，形狀上點的顏色表示點與點匹配相似度的高低。通過可視化查詢的片段中可以看出，在未含有細(xì)支的形狀中，如上半部分所示，主體輪廓所形成的編碼可以準(zhǔn)確地描述形狀。在含有細(xì)支的形狀中，如下半部分所示，本文的方法由于在細(xì)支處使用骨架來進行編碼，可以更有效地表示出細(xì)支處的形狀信息，對該類形狀的貢獻度比較大。所以，在細(xì)支處使用骨架、在主體處使用輪廓的編碼方案可以有效地表示形狀信息。

圖7 MPGE-7數(shù)據(jù)集可視化查詢Fig.7 Visual query of MPEG-7 dataset

3.3 ETH-80數(shù)據(jù)集的識別結(jié)果

在ETH-80數(shù)據(jù)集，每組中隨機選取一個作為測試形狀，然后對所有形狀進行編碼，計算測試形狀和訓(xùn)練形狀之間的相似度，然后通過相似度排序選取前79個形狀，統(tǒng)計它們的類別，得到測試形狀的分類，并最終計算識別準(zhǔn)確率。ETH-80數(shù)據(jù)集中8類物體的代表性形狀如圖8所示。

本文方法和現(xiàn)有方法的識別準(zhǔn)確率如表3所示。可以看出，本文方法取得了較高的準(zhǔn)確率，相對于傳統(tǒng)的描述子如基于內(nèi)部距離的形狀上下文（IDSC +DP），準(zhǔn)確率提高了將近5%。

圖8 ETH-80數(shù)據(jù)集Fig.8 ETH-80 dataset

3.4 Swedish leaf數(shù)據(jù)集的識別結(jié)果

由于不同葉子類之間的高度相似性以及葉子類中往往存在較大變形，Swedish leaf數(shù)據(jù)集具有較大挑戰(zhàn)性。識別準(zhǔn)確率的計算方式和ETH-80數(shù)據(jù)集方式相同，在Swedish leaf數(shù)據(jù)集每類中選取一個作為測試形狀，然后對所有形狀進行編碼，通過相似度降序排序選取前14個形狀的相似度，判定該形狀的類別為14個形狀中比重最大的類別，最終得到識別準(zhǔn)確率。Swedish leaf數(shù)據(jù)集15類葉子的代表性形狀如圖9所示。

本文方法和現(xiàn)有方法的識別準(zhǔn)確率如表4所示。可以看出本文在Swedish leaf數(shù)據(jù)集上取得了較高的準(zhǔn)確率。

當(dāng)然，本文方法的識別準(zhǔn)確率，與BCF和CNN方法的準(zhǔn)確率相比還有一些差距。BCF方法利用多個輪廓片段及其池化表示，借助支持向量機（SVM）進行分類及識別。而CNN方法把形狀表示和識別融合于卷積神經(jīng)網(wǎng)絡(luò)的訓(xùn)練和學(xué)習(xí)，其準(zhǔn)確性依靠于樣本的規(guī)模和有效標(biāo)記。和這2種方法不同，本文的方法基于生物信息序列分析的理論。把形狀數(shù)據(jù)表示為基因序列，可以直接用于形狀數(shù)據(jù)的表示與匹配，也是一個頗具前景的方向。

表3 ETH-80數(shù)據(jù)集上的分類準(zhǔn)確率對比Table 3 Comparison of classification accuracy rate on ETH-80 dataset

圖9 Swedish leaf數(shù)據(jù)集Fig.9 Swedish leaf dataset

表4 Swedish leaf數(shù)據(jù)集上的分類準(zhǔn)確率對比Table 4 Comparison of classification accuracy rate on Swedish leaf dataset

3.5 深入分析

在結(jié)合輪廓與骨架的編碼方案中，除了本文提出的策略外，還有其他多種選擇，不同的編碼策略會產(chǎn)生不同的編碼形式和編碼長度。本節(jié)通過實驗說明本文選擇策略的有效性。

在主體輪廓上中，選取不同間隔的輪廓點：相鄰點、間隔一個點、間隔兩個點和間隔三個點，產(chǎn)生了不同的生物信息序列；并結(jié)合不同的序列對齊工具：局部對齊（SW）、全局對齊（NW）、MUSCLE對齊以及MUSCLE對齊加懲罰項，進行不同組合之間的比較。實驗中，選取MPEG-7數(shù)據(jù)集和ETH-80數(shù)據(jù)集，使用上述的留一法進行比較，實驗結(jié)果如圖10和圖11所示。

圖10 MPEG-7數(shù)據(jù)集上不同編碼策略分類準(zhǔn)確率的比較Fig.10 Comparison of classification accuracy rate on MPEG-7 dataset by different encoding strategies

圖11 ETH-80數(shù)據(jù)集上不同編碼策略分類準(zhǔn)確率的比較Fig.11 Comparison of classification accuracy rate on ETH-80 dataset by different encoding strategies

可以看出，使用本文的編碼選擇策略，即在主體輪廓上間隔兩個點選取一個輪廓點進行編碼，同時采用MUSCLE對齊工具和懲罰項，得到了最高的識別準(zhǔn)確率。

4 結(jié) 論

本文提出了一種新型的二維形狀識別方法。該方法首先得到形狀主體輪廓和細(xì)支骨架的組合表示，其次通過一個輪廓及骨架的協(xié)同編碼方案，把形狀編碼為生物信息序列，最后由成熟的生物序列對齊工具進行形狀的分類及識別。在3個公開形狀數(shù)據(jù)集的實驗表明，本文方法相較于現(xiàn)有方法，有一定準(zhǔn)確度的提升。

本文方法的優(yōu)勢在于可以有效降低原始編碼方案的信息冗余。同時，骨架和輪廓的組合表示及編碼可以增強形狀編碼的魯棒性，提高后續(xù)編碼匹配的效率和準(zhǔn)確性。最后，把形狀識別轉(zhuǎn)化為生物信息序列匹配，可以采用廣泛的生物序列對齊工具。

在對形狀轉(zhuǎn)化為基因編碼的過程中，如何使形狀編碼序列具有更多基因?qū)用娴男畔ⅰ缀涡畔⑴c基因信息有更深層次的映射關(guān)系［29］仍是一個頗具前景的研究方向。