基于最小點對成本的二維輪廓精確匹配與分析方法

李向軍,周 勇,劉 韜,劉伯成,羅 銘

(南昌大學 a.信息工程學院; b.軟件學院,南昌 330031)

0 概述

人類通過視覺、觸覺和聽覺等多模態來識別物體,視覺是其中極為重要的一種模態。經過億萬年的進化,生物通過三維視覺進行對象識別時獲得了極高的效率與較好的魯棒性,且與視點和對象取向無關,即使是在復雜環境中也能輕松識別出目標對象。在對物體進行識別的過程中,人類使用了多種特征,如輪廓、紋理等,且輪廓相對紋理而言更加穩定,原因是其不易受到光照變化和顏色變化的影響。文獻[1]對比了人類視覺和由深度神經網絡驅動的機器視覺系統,發現兩者處理對象信息的方式存在顯著差異,人類在識別物體時傾向于輪廓,而由深度神經網絡驅動的機器視覺系統更傾向于紋理。雖然人類在識別圖像中的物體時是基于大量的先驗知識,如輪廓、紋理、顏色和上下文等[2],但是即使只給定輪廓,人類也能迅速識別出其類別,這說明輪廓在物體識別中起重要作用。物體的形狀識別作為物體識別的主要內容,一直是計算機視覺領域的研究熱點之一,這類方法[3-4]一般通過輪廓匹配來實現,可以將其統稱為基于輪廓的識別方法。二維輪廓匹配方法應當具有人類視覺所具備的平移不變性、旋轉不變性、尺度不變性以及鏡像不變性4個基本特性。

自然界中的生物受到物理規律的約束,不同部位的尺寸大小與其整體重量存在一定的關系。在觀察物體時,人類的眼睛會將三維世界投影為二維圖像,但大腦會根據環境而構建出相應的三維模型[5]。將三維世界物體轉換為二維輪廓圖像時,不同部位的尺寸大小與其整體重量的關系就轉變為距離關系和面積關系。本文通過交互式分割法學習上述關系,分割出符合人類視覺特性的輪廓段,對輪廓進行點對匹配以度量輪廓間的相似性,從而提取盡量多的輪廓全局特征和局部特征,減少信息丟失。

1 相關工作

文獻[6]總結了近年來相繼出現的二維形狀表示及匹配方法。早期的形狀描述符[7-9]主要是獲取輪廓的全局特征,如傅里葉描述符[7]、矩描述符[8-9],其通過計算特征向量之間的距離進行物體識別,但是,類內輪廓差異大的物體識別率不高且輪廓細節匹配能力弱。形狀上下文[10]是一種經典的描述符,其實現了輪廓點的局部分布編碼,對識別率有較大的改善。形狀上下文以采樣點為極點構建極坐標系,將極角劃分為m份,極徑劃分為n份,得到m×n個區域,統計每個區域內采樣點的出現次數,構建對應的直方圖,該直方圖表示了其他采樣點相對于當前點的局部分布。形狀上下文統計的是采樣點的分布,對噪聲數據不敏感,但是其也丟失了全局信息。文獻[4]將輪廓點順序作為全局形狀特征并與形狀上下文相結合,提高了描述符的全局特征編碼能力。文獻[3]分析部位及其結構在計算機視覺和人類視覺中的重要性,采用內距離來代替形狀上下文中的歐氏距離,提出內距離形狀上下文IDSC(Inner-Distance Shape Context),其中,內距離定義為輪廓上標記點與其他采樣點在輪廓內的最短路徑長度。對于具有關節部位的輪廓,內距離比歐氏距離能更有效地捕獲部位結構從而建立更準確的描述符。文獻[11]為了降低匹配的復雜度并提高檢索速度,提出輪廓點分布直方圖(Contours Points Distribution Histogram,CPDH)描述符,其基于極坐標系下對象輪廓采樣點的分布而忽略了輪廓的局部特征。文獻[12]提出封閉曲線和開放曲線的相似性度量方法,其將輪廓作為一條封閉曲線,利用曲線采樣點的有序集合來表示輪廓,然后將該集合視為有限維矩陣李群的元素,通過李代數的L2-范數在輪廓之間進行相似性度量,該方法計算出的點對關系優于形狀上下文。

曲率尺度空間描述符[13]通過曲率變化來表示形狀,即尋找輪廓上的曲率過零點來構建輪廓的曲率空間直方圖,其實質是對關鍵局部信息進行編碼,但是不同的輪廓可能會產生類似的曲率空間直方圖。文獻[14]利用離散曲率演化算法提取輪廓段作為局部信息,將其與從骨架中提取的全局信息相結合以表示形狀。BCF(Bag of Contour Fragments)[15]是受BoW(Bag of Words)模型啟發而被提出的新的形狀表示,其首先將形狀分解為輪廓片段,然后采用形狀上下文描述符對每個輪廓片段進行處理并將其編碼為形狀代碼,最后利用輪廓片段的形狀代碼的統計直方圖來表示形狀。文獻[16]改進BCF方法,將骨架信息也作為形狀特征,在BoF(Bag of Features)框架下引入適用于輸入形狀特征的可學習的池化函數,該池化函數是最大池化和平均池化的加權和,權重可以使用形狀分類器通過梯度下降學習獲得,該方法在輪廓識別方面獲得了較高的識別率。文獻[17]提出一種基于三角形質心距離(Triangular Centroid Distances,TCD)的形狀描述符TCDs,使用TCDs形狀描述符來解決部位之間的部分形狀匹配問題,該方法在整體匹配和部位匹配中均獲得了較好的效果。上述方法均能在一定程度上提高匹配效果,但是普遍存在的問題是提取到的輪廓段與人類視覺分割的輪廓段不一致。

2 輪廓精確匹配與分析方法

人類在利用輪廓識別物體時,通常先識別出大致輪廓的類別,然后通過判斷其部位與該類別的部位是否相似來確定最終的輪廓類別。受此啟發,本文提出一種基于最小點對成本的輪廓精確匹配與分析方法,該方法主要分3步實現:首先通過交互式學習類別的輪廓原型、部位原型及其輪廓分析參數;然后刪除輪廓中大于點對比率閾值的輪廓段以獲得該輪廓的主體輪廓,通過粗匹配獲得輪廓的候選類別;最后分割出輪廓的部位,將其與候選類別的部位輪廓進行匹配找到相似度最高的候選類別,該類別即為最終的匹配類別。

2.1 交互式學習

本文通過交互式分割法學習不同類別的原型及輪廓分析參數,該階段不僅學習類別整體輪廓原型,而且通過人工分割學習類別不同部位的輪廓原型,前者可用于類別輪廓的匹配,后者可用于類別部位的輪廓匹配。本文通過人工來選擇需要學習的原型,在交互式學習中采用的是閉合輪廓,交互式學習的其中一個目標是學習類別及其部位在不同的主視角下的輪廓。考慮到基于最小點對成本的精確匹配方法需要使用輪廓圖像,形狀描述符就必須具有可恢復性,本文采用鏈碼[18]作為形狀描述符,其編碼方式如圖1所示,其中,P表示當前像素點,0～7用于編碼不同的方向。

圖1 鏈碼的編碼規則Fig.1 Coding rule of chain codes

交互式學習的另一個目標是學習類別的輪廓分析參數,主要包括點對曲率、點對面積距離比、部位端點最大距離、部位端點最小距離、部位最小面積比、部位最大面積比和部位類別名稱等,其中,點對曲率和點對面積距離比的定義分別如下:

定義1(點對曲率) 令lp為輪廓上任意可連通2點之間的像素點數量,dp為2點之間的距離,則由這2點組成的點對曲率Cp可表示為:

(1)

定義2(點對面積距離比) 令p為輪廓上任意可連通2點之間的最短長度線段的邊界點集,Ap為邊界點集所圍成的面積,dp為2點之間的距離,則由這2點組成的點對面積距離比Rp可表示為:

(2)

點對曲率、點對面積距離比、部位最小面積比和部位最大面積比本身就具有尺度不變性,而部位端點最大距離和部位端點最小距離與輪廓的尺寸相關,本文針對輪廓中最長的點對距離進行歸一化處理,以獲得參數的尺度不變性。交互式學習過程主要分為3步:

1)讀入選定的類別圖像,將其調整為固定尺寸的輪廓圖像。

2)人工分割出輪廓中的不同部位。

3)根據分割出的輪廓圖像學習類別的輪廓分析參數,并將類別輪廓和部位輪廓存儲到知識庫中。

圖2所示為通過人工分割獲得的類別部位分割效果。

圖2 交互式工具獲得的類別組件分割效果Fig.2 Segmentation effect of category componentsobtained by interactive tool

2.2 基于最小點對成本的精確匹配方法

IDSC、BCF、CPDH和基于形狀上下文的匹配方法各有優點,但它們都不能實現精確匹配。本文提出一種基于最小點對成本的精確匹配方法,其通過計算2個邊界圖之間的最小成本對應關系[19]來實現精確匹配。基于最小點對成本的精確匹配方法將輪廓匹配轉換為點分配,輪廓邊界點集S1中任意一點與輪廓邊界點集S2中的點都有一條邊相連,邊的權重即為點與點之間的匹配成本,其距離度量公式可表示為:

(3)

其中,pi和qj分別表示輪廓邊界點集S1和S2中的像素點,C(pi,qj)表示2個輪廓之間的點對成本,本文將點對之間的歐氏距離作為點對的匹配成本。

為了滿足人類視覺所具有的基本特性,還需對基于最小點對成本的精確匹配方法進行優化。首先對匹配輪廓進行歸一化和鏡像(無鏡像、X鏡像、Y鏡像)處理,然后以輪廓的質心為旋轉中心,將360°劃分為n份,最后將每一次旋轉后的圖像與原型進行匹配,找到與待匹配輪廓具有最小匹配成本的原型。通過以歸一化后的輪廓質心為基準進行旋轉和鏡像處理,使得優化后的最小點對成本匹配方法具備平移不變性、旋轉不變性、鏡像不變性和尺度不變性。

雖然基于最小點對成本的精確匹配方法可實現像素級的匹配,但是其無編碼能力并且丟失了像素間的空間關系。人類在判斷2個輪廓之間的相似性時不僅依賴輪廓之間的點對距離,還與輪廓中點與點之間的空間關系有關。基于形狀上下文的匹配方法能有效捕獲輪廓中點與點之間的空間關系,將形狀上下文匹配方法融合到最小點對成本匹配方法中,使其具有局部分布編碼能力。此時,輪廓之間的相似性由2個輪廓之間的點對距離和形狀上下文成本表示,其距離度量公式可改寫為:

Df=dmin+αdSC

(4)

其中,α表示形狀上下文的匹配成本權重。式(4)的距離度量公式體現出需要找到與待匹配輪廓具有最小點對距離、邊界點集分布最相似的輪廓原型。

雖然基于最小點對成本的精確匹配方法在引入形狀上下文距離后獲得了局部分布編碼能力,但同時也導致異常點多時匹配效果差、對輪廓細節的變化較敏感等問題。為了解決異常點多時匹配效果差的問題,本文在進行形狀上下文匹配時只選取在最小點對成本匹配中已配對的點集,這樣可以避免異常點對形狀上下文匹配的影響。與特征匹配方法相比,基于最小點對成本的精確匹配方法能以可視化的方式呈現出符合觀察習慣的匹配結果。

2.3 輪廓精確匹配與分析

人類在進行輪廓匹配時通常不考慮相似度低的輪廓而主要關注大致相似的輪廓。受此啟發,在實際的輪廓匹配處理中,往往采用預處理的方式找出大致相似的輪廓,然后再進行輪廓精確匹配,這樣可以有效提升匹配速度。限于篇幅,本文主要討論輪廓精確匹配階段,預處理階段不做贅述。

雖然基于最小點對成本的精確匹配方法已經避免了異常點的影響,但對輪廓細節變化比較敏感的問題并未解決,如果直接對輪廓進行匹配將達不到預期效果。受到人類識別物體的啟發,本文在該方法中引入粗到精的二級匹配策略,該策略與文獻[14-15,20]中的匹配策略有相似之處,都是將輪廓分割為輪廓段,從而降低對輪廓細節變化的敏感性,但文獻[14-15,20]中的匹配策略提取的輪廓段往往與人類在進行輪廓識別時分割出的輪廓段不一致。

粗到精的二級匹配策略的第一級為粗匹配,第二級為精匹配。粗匹配主要實現類別主體輪廓的匹配,具體過程為:首先對輪廓進行處理,刪除點對曲率大于閾值的輪廓段,獲得穩定的主體輪廓;然后通過基于最小點對成本的精確匹配方法尋找相似的原型,將滿足閾值要求的輪廓原型的類別作為待匹配輪廓的候選類別。精匹配可以認為是對粗匹配分析結果的進一步優化,其仍然采用基于最小點對成本的精確匹配方法,具體過程為:首先對每一種候選類別進行輪廓分析獲得輪廓的部位;然后對其部位進行匹配;最后將候選類別的部位匹配成本和粗匹配成本平均值作為該候選類別的匹配成本,將相似度最高的候選類別作為最終的匹配結果。無論是粗匹配階段的主體輪廓還是精匹配階段的部位輪廓,相比于整體輪廓而言已經極大降低了輪廓復雜性,從而利于形狀上下文捕獲邊界點之間的空間關系。

圖3所示為輪廓分析的處理過程,其中,第1行是待匹配的輪廓圖像,從左到右為原始輪廓、主體輪廓、輪廓分割圖像和輪廓分析結果,第2行是知識庫中的一些輪廓原型(鴨子、鳥類、牛、蝴蝶)的主體輪廓,最后一行是待匹配的主體輪廓和第2行中原型主體輪廓的點對匹配圖像,所有圖片來源于Animal數據集(http://cloud.eic.hust.edu.cn:8071/～xbai/softwares.html)。輪廓分析是指分割出輪廓中的部位并識別出輪廓類別及其部位類別。本文將原型知識庫和二級匹配策略的最小點對成本匹配方法應用于輪廓分析,提出一種基于最小點對成本的輪廓精確匹配與分析算法,其偽代碼如算法1所示。首先通過粗匹配找到相似的原型,并將滿足閾值要求的輪廓原型的類別作為待匹配輪廓的候選類別;然后處理每一個候選類別,假定該候選類別即為輪廓類別,從原型知識庫中讀取該類別的輪廓分析參數,隨后利用分析參數對輪廓進行分割,找出符合要求的部位,如圖3第1行第3幅圖所示;最后將部位與原型庫中的該候選類別的部位輪廓原型進行匹配,并將該候選類別的主體輪廓匹配成本和部位輪廓匹配成本的平均值作為候選類別的匹配成本。將候選類別中匹配成本最低的類別及其部位分割和識別結果作為最終的輪廓分析結果,如圖3第1行第4幅圖所示。

圖3 基于最小點對成本的輪廓匹配與分析算法效果Fig.3 Contour matching and analysis algorithm effect based on minimum point-pair cost

算法1基于最小點對成本的輪廓精確匹配與分析算法

輸入圖像Iin,原型知識庫PK,點對曲率閾值h

輸出輪廓類別Cc,組件類別Cp

步驟1獲得輪廓圖像。

步驟2從知識庫中讀取輪廓原型信息。

步驟3刪除輪廓中點對曲率大于閾值h的輪廓線段,并將其余輪廓段作為輪廓主體。

步驟4將主體輪廓與原型的主體輪廓進行匹配,并使用符合要求的原型類別作為候選類別。

步驟5處理每個候選類別并使用候選類別的分析參數分析輪廓。

步驟6將分割出的組件與候選類別的組件原型進行匹配以獲得匹配成本。

步驟7將候選類別的主體匹配成本和組件匹配成本的平均成本作為候選類別的匹配成本。

步驟8輪廓類別Cc為候選類別中匹配成本最低的類別,該候選類別對應的組件匹配結果即為輪廓的組件類別Cp。

3 實驗結果與分析

為了驗證匹配方法的有效性,選取MPEG-7[21]數據集和Animal[14]數據集作為實驗數據集。首先,在MPEG-7數據集上比較不同匹配方法對剛性物體的識別率;然后,在Animal數據集上比較不同匹配方法對非剛性物體的識別率。考慮到人類可能有額外的機制來處理遮擋和扭曲的情況,在對非剛性物體的識別任務中僅選用通過輪廓即可識別出其類別的圖像作為數據集,圖像全部選自Animal數據集。實驗在微軟Windows 10(64位)操作系統、酷睿i7-6500U CPU 2.5 GHz頻率、內存8 GB的計算機上完成,采用分類準確率作為評價指標。

表1所示為MPEG-7數據集中的實驗結果,從表1可以看出,對于剛性物體,本文匹配方法、SC[10]、BCF[15]、CSM[12]、TCDs[17]和BoSCP-LP[16]方法均有較高的識別率,這是由于剛性物體的類內差異較小。

表1 MPEG-7數據集上不同匹配方法的識別率對比Table 1 Comparison of recognition rates of differentmatching methods on MPEG-7 dataset

圖4顯示了部分類別的部位識別結果,表2所示為Animal數據集中部分類別的粗匹配、精匹配、組件分割和組件識別的識別率。

圖4 Animal數據集上部分類別的組件識別結果Fig.4 Component recognition results of some categories on Animal dataset

表2 Animal數據集上部分類別的實驗結果Table 2 Experimental results of some categories on Animal dataset

從圖4和表2可以看出,精匹配的識別率相比粗匹配有一定提升,說明部位識別在一定程度上有利于整體輪廓的識別,鴨、蝴蝶、牛的類內輪廓變化不大,而鳥、鱷魚有著較大的類內輪廓差異,類內差異小的類別有較高的識別率,其中,鳥的精匹配準確率較高是由于其增加了部位的原型數量,而鱷魚在未增加部位原型數量的情況下識別率顯著降低。圖4中第1行最后一幅鳥類部位分割圖由于腳與尾巴相似而識別錯誤,第4行最后一幅蝴蝶部位分割圖中尾巴曲率不滿足要求而沒有被分割出來,第5行鱷魚的嘴、尾、腳有時很相似導致識別時出錯。上述實驗結果表明各方法均有較高的部位分割與識別準確率。

表3所示為Animal數據集上本文粗匹配、精匹配、SC方法[10]、BCF方法[15]、CSM方法[12]、TCDs方法[17]和BoSCP-LP方法[16]的實驗結果對比。從表3可以看出,對于類內差異較大的鱷魚,所有匹配方法的識別率均較低,這表明輪廓細節的變化對匹配結果有較大影響。粗匹配的識別率與其他匹配方法相近,而精匹配具有較高的識別率,這說明粗到精的策略有利于輪廓識別。基于形狀上下文的匹配方法雖然可以對輪廓邊界點之間的關系進行編碼以提高對輪廓的識別效果,但是鴨子脖子和鱷魚尾巴在整個輪廓中所占比例較大且相對于輪廓主體位置不固定,因此該方法對鴨子和鱷魚的識別率較低。TCDs形狀描述符本質上仍然是傅里葉描述子,不能有效區分類間的差異,不同類別輪廓的傅里葉描述子可能極為相似,TCDs對于類內形變較大的鱷魚識別率較低,該形狀描述符適用于開放輪廓段間的匹配。BCF、CSM和BoSCP-LP在不同類中均有較高的識別率,但是BCF、BoSCP-LP獲得的輪廓段并非人類視覺分割結果[15],BCF和CSM也未識別出類別的部位。總體而言,輪廓中部位的位置變化不利于輪廓識別,本文提出的兩級匹配策略可有效降低部位的位置變化對輪廓識別結果的影響,并且能夠識別出其部位的類別。

表3 Animal數據集上不同匹配方法的識別率對比Table 3 Comparison of recognition rates of different matching methods on Animal dataset

4 結束語

針對物體識別中輪廓精確匹配與部位識別問題,本文通過交互式分割法學習不同類別的輪廓原型數據和輪廓分析參數,構建類別輪廓原型知識庫,提出一種可以實現精確匹配的最小點對成本匹配方法,其能有效地從輪廓原型知識庫中找到與待匹配輪廓具有最小點對距離、邊界點集分布最相似的輪廓原型。多數已有匹配方法對類內輪廓的差異比較敏感,本文匹配方法引入粗到精的二級匹配策略,從而降低匹配方法對輪廓細節變化的敏感性。在此基礎上,結合類別輪廓原型知識庫和最小點對成本匹配方法,提出一種基于最小點對成本的輪廓精確匹配與分析方法,該方法可以識別出輪廓類別及其部位類別,具有平移不變性、旋轉不變性、尺度不變性和鏡像不變性等特點。實驗結果表明,基于原型匹配的物體識別策略具有可行性,本文所提方法能實現精確匹配并在部位分割、輪廓識別和部位識別方面具有較高的準確率。

在二維空間采用基于原型匹配的物體識別方法時仍然存在一定不足,例如,由于視點的不同,三維物體的輪廓經過投影變換后有無數種二維形狀,這不僅增加了二維輪廓的原型數量而且也提高了二維輪廓匹配的難度。此外,從二維輪廓中獲得的部位和整體關系與三維輪廓中的部位和整體關系存在差異,更好的基于原型匹配的物體識別策略是模擬人腦構建出不同類別的三維原型知識庫,然后通過三維輪廓匹配與分析方法來進行物體識別。下一步將通過上述策略提高物體識別的效率和準確率。