盧勇強(qiáng)，栗志揚(yáng)，陳祎楠，劉朝斌，黃一鳴

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

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

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

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

不過(guò)在形狀發(fā)生一些等距變換（如關(guān)節(jié)變換）時(shí)，基于輪廓的表示方法往往穩(wěn)定性不好，而此時(shí)形狀骨架的拓?fù)浣Y(jié)構(gòu)會(huì)保持不變?？梢越柚羌芴岢鲂螤罡?jiǎn)潔且穩(wěn)定的描述方法。一般來(lái)說(shuō)，骨架是形狀內(nèi)所有最大內(nèi)切圓圓心的集合，提供了形狀的厚度沿骨架的變化信息，對(duì)非脊變形和關(guān)節(jié)具有不變性，且對(duì)于輪廓上的噪聲比較魯棒。這些優(yōu)點(diǎn)使得基于骨架的形狀表示獨(dú)具優(yōu)勢(shì)。

然而現(xiàn)實(shí)中的形狀往往存在較多變形，如放縮、遮擋、大尺度噪聲、同一形狀的多樣性等，給形狀的準(zhǔn)確表示和識(shí)別帶來(lái)很大挑戰(zhàn)。近期，二維形狀方面的研究進(jì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é)模型解決二維形狀的識(shí)別問(wèn)題，其基本思想是把形狀輪廓按照其空間分布編碼為生物信息序列，即DNA分子序列，然后借助標(biāo)準(zhǔn)的生物信息序列分析工具來(lái)進(jìn)行序列之間的相似性分析，以及在此基礎(chǔ)上的形狀識(shí)別或分類。

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

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

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

1 形狀描述及匹配

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

1.1 基于輪廓的形狀描述

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

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

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

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

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

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

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

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

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

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

1.2 基于骨架的形狀描述

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

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

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

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

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

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

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

這類方法存在以下兩個(gè)方面的不足：

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

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

1.3 生物信息序列分析工具

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

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

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

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

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

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

這類方法存在以下兩個(gè)方面的不足：

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

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

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

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

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

2.1 形狀歸一化

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

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

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

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

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

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

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

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

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

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

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

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

2.3 形狀信息編碼方法

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

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

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

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

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

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

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

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

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

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

加入懲罰項(xiàng)之后，通過(guò)計(jì)算式（2），最終得到2個(gè)形狀之間的相似度評(píng)分：

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

3 實(shí)驗(yàn)及分析

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

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

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

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

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

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

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

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

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

MPEG-7數(shù)據(jù)集利用牛眼比較法，和現(xiàn)有的方法的對(duì)比結(jié)果如表1所示?？梢钥闯?，在牛眼比較的準(zhǔn)確率上，本文方法并不是最好的。離性能表現(xiàn)最好的方法尚有一定的差距，但是對(duì)于文獻(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%以上。不過(guò)，這2種方法性能的提升均建立在對(duì)于形狀相似度矩陣的距離學(xué)習(xí)上，屬于形狀識(shí)別領(lǐng)域中的后處理方法。該類方法必須提前得到一個(gè)質(zhì)量較好的形狀相似度矩陣，且并不能提供形狀的表示。這與本文方法及形狀上下文（SC和IDSC）等方法有本質(zhì)上的區(qū)別。

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

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

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

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

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

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

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

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

本文方法和現(xiàn)有方法的識(shí)別準(zhǔn)確率如表3所示?？梢钥闯?，本文方法取得了較高的準(zhǔn)確率，相對(duì)于傳統(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ù)集的識(shí)別結(jié)果

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

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

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

表3 ETH-80數(shù)據(jù)集上的分類準(zhǔn)確率對(duì)比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)確率對(duì)比Table 4 Comparison of classification accuracy rate on Swedish leaf dataset

3.5 深入分析

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

在主體輪廓上中，選取不同間隔的輪廓點(diǎn)：相鄰點(diǎn)、間隔一個(gè)點(diǎn)、間隔兩個(gè)點(diǎn)和間隔三個(gè)點(diǎn)，產(chǎn)生了不同的生物信息序列；并結(jié)合不同的序列對(duì)齊工具：局部對(duì)齊（SW）、全局對(duì)齊（NW）、MUSCLE對(duì)齊以及MUSCLE對(duì)齊加懲罰項(xiàng)，進(jìn)行不同組合之間的比較。實(shí)驗(yàn)中，選取MPEG-7數(shù)據(jù)集和ETH-80數(shù)據(jù)集，使用上述的留一法進(jìn)行比較，實(shí)驗(yàn)結(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

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

4 結(jié) 論

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

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

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