基于輪廓分段特征描述的遮擋目標識別算法

摘 要： "針對傳統(tǒng)目標識別算法對于遮擋目標識別準確率低的問題，提出了一種基于輪廓分段特征描述的遮擋目標識別算法。該算法首先采用離散曲線演化算法初步劃分目標輪廓，根據分段起伏度進行分段優(yōu)化，得到完整描述目標輪廓特征的有效分段；然后通過動態(tài)規(guī)劃算法分析輪廓分段之間高度函數特征的相似度，利用特征顯著度評價分段特征相對于目標整體特征的重要性；最后將分段之間的相似度和其特征顯著度相結合，得到衡量識別準確率的聯(lián)合相似度，獲得最終的識別結果。通過對MPEG-7測試集進行實驗分析，證明所提算法能夠有效地對遮擋目標進行匹配識別，識別率優(yōu)于常見的遮擋目標識別算法。

關鍵詞： "遮擋目標； 輪廓分段； 分段優(yōu)化； 特征顯著度； 聯(lián)合相似度

中圖分類號： "TP317.4 """文獻標志碼： A

文章編號： "1001-3695（2022）02-055-0633-04

doi：10.19734/j.issn.1001-3695.2021.06.0237

Occluded object recognition algorithm based on "contour segmented feature description

Zhao Yawei， Zheng Wei， Yu Yang， Song Jianhui

（School of Automation amp; Electrical Engineering， Shenyang University of Science amp; Technology， Shenyang 110159， China）

Abstract： ""Aiming at the problem of low recognition accuracy of traditional target recognition algorithms for occluded targets，this paper proposed an occluded target recognition algorithm based on contour segmented feature description.The algorithm firstly used the discrete curve evolution algorithm to preliminarily divide the target contour，and optimized the segment accor-ding to the undulation degree of the segment，and obtained effective segments that completely described the characteristics of the target contour.Then，the algorithm analyzed the similarity of the height function features between the contour segments through the dynamic programming algorithm，and used feature saliency to evaluate the importance of segment features relative to the overall feature of the target.Further，the algorithm combined the similarity between the segments with their feature saliency to obtain the joint similarity that measured the recognition accuracy.Experiments on the MPEG-7 test set prove that the algorithm can effectively match and recognize occluded targets，and the recognition rate is better than common occluded target recognition algorithms.

Key words： "occlusion target； contour segments； segment optimization； feature saliency； joint similarity

局部遮擋下的目標識別一直是圖像識別領域的熱點與難點問題［1，2］。由于輪廓具有非常重要和穩(wěn)定的視覺特征，能夠反映重要的特征信息，所以被廣泛應用于遮擋目標識別領域［3，4］。為獲得準確的匹配識別效果，國內外學者提出了許多基于輪廓分段特征的遮擋目標識別算法。文獻［5～7］通過任意連接輪廓曲率極值點將輪廓劃分為若干輪廓分段，通過計算輪廓間的相似度識別遮擋目標，該方法受噪聲影響較大，而且分段較多，增加了識別算法的復雜性；文獻［8］將輪廓曲率關鍵點作為特征點對輪廓進行分段，通過比較分段的價值性進行合并處理，在此基礎上得到相似度匹配結果，該方法同樣受噪聲影響嚴重，易把噪聲當成關鍵點，造成誤分段，而且對于存在局部變形的目標輪廓識別困難；文獻［9］根據輪廓的骨架關鍵點對輪廓劃分，通過比較分段的局部特征性進行分段合并處理，提出加權相似度衡量特征分段之間的匹配程度，該方法能克服遮擋帶來的識別困難，但通過形狀上下文這一特征對復雜輪廓識別仍存在一定的不足；文獻［10］通過多邊形近似的方法對目標輪廓分段，采用動態(tài)規(guī)劃算法計算各分段不變矩特征的相似度，從而識別遮擋目標，該方法簡單，對于噪聲干擾具有良好的魯棒性，但未考慮輪廓分段的局部特征，識別效果較差；文獻［11］通過比較遮擋目標輪廓片段與其他輪廓的空間位置關系，在高比例遮擋下取得了較好的識別效果，但該方法只適用于目標存在離散輪廓片段的情況，不具有普適性。

本文針對遮擋目標識別算法中輪廓劃分不合理和特征描述不完整的問題，提出了基于輪廓分段特征描述的目標識別算法，通過離散曲線演化算法（discrete curve evolution，DCE）剔除邊界噪聲點，提取特征點對輪廓進行初步劃分，根據起伏度這一價值尺度對分段進行合并優(yōu)化，獲得合理有效的輪廓分段。在輪廓匹配階段，選用高度函數作為輪廓分段的特征描述子，該描述子計算簡單，描述了豐富的輪廓信息，在此基礎上利用動態(tài)規(guī)劃（dynamic programming，DP）算法得到輪廓分段高度函數特征之間的相似度。同時為了評價輪廓分段特征相對于目標整體特征的突出程度，引入輪廓分段特征顯著度分析。最后聯(lián)合分段之間的相似度和其特征顯著度共同實現(xiàn)對目標的識別，從而獲得準確、穩(wěn)定的識別結果。

1 基于DCE和起伏度的輪廓分段優(yōu)化算法

為獲得準確描述輪廓特征的輪廓分段，本文提出一種新的輪廓分段優(yōu)化算法。首先通過DCE算法對目標邊緣輪廓進行簡化，篩選出對輪廓特征貢獻程度大的邊界點，通過這些邊界點對輪廓進行初步劃分，最后根據各個分段的起伏度將初始分段合并成特征性更明顯的分段。

1.1 基于DCE的輪廓分段算法

DCE算法是一個遞歸刪除對物體形狀信息貢獻最小的多邊形頂點（最有可能是物體邊界的噪聲點）的過程［12］，基本思想如下：給定目標輪廓 C={S t}（t=1，2，…，M） ， S t 為構成輪廓的第 t 條線段， p i（i=1，2，…，N） 為線段上的輪廓點，在每個階段的演化中，找出貢獻度最小的點 p i ，刪除該點兩端的線段，連接兩條線段不相鄰的端點 p i-1 和 p i+1 作為新的線段。邊界點識別貢獻度定義為

K（S t，S t+1）= δ（S t，S t+1）l（S t）l（S t+1） l（S t）+l（S t+1） """（1）

其中： δ（S t，S t+1） 是 S t 和 S t+1 兩線段的夾角； l（S t） 是線段 S t 相對于輪廓周長歸一化后的長度； K（S t，S t+1） 越小， S t 和 S t+1 兩條線段在目標識別中的貢獻越小，因此在每次演化中，刪除貢獻度最小的兩條相鄰線段的公共端點，將兩條線段合并。為避免輪廓出現(xiàn)過演化現(xiàn)象，使用面積差值作為終止函數控制演化程度，當演化結果與原輪廓的面積差值小于設定的閾值 τ 時，終止演化算法。

將DCE算法保留下來的輪廓點記為特征點，通過特征點對輪廓進行劃分，得到輪廓的初步分段結果。圖1給出了輪廓分段過程，（a）是目標圖像；（b）是目標輪廓；（c）是根據離散曲線演化算法得到的輪廓特征點；（d）是通過特征點劃分輪廓得到的初步分段。

1.2 基于起伏度的輪廓分段優(yōu)化算法

通過DCE算法獲取的輪廓分段數量較多，其中一些片段對于目標識別的貢獻不大，為獲得完整描述特征的輪廓分段，提出基于起伏度的分段優(yōu)化算法。將輪廓分段的起伏程度作為價值尺度來衡量分段對于目標識別的重要性，通過合并算法將價值小的片段與相鄰價值高的分段進行合并，獲得完整高效且體現(xiàn)輪廓特征的輪廓分段。輪廓分段的起伏度定義為輪廓片段上所有點到起點與終點連線距離的標準差。下面給出起伏度的推導公式：給定輪廓分段 S t={p i}（i=1，2，…，N） ，設起始輪廓點為 p 1（x 1，y 1） ，終點為 p N（x N，y N） ，將每個輪廓點到直線 p 1p N 的距離記為 d i（i=1，2，…，N） ，并給出了 d i 的符號。當輪廓點位于直線 p 1p N 的上方時， d i 為正；當輪廓點位于直線 p 1p N 的下方時， "d i 為負。由此得到起伏度的定義為

Vol （S t） =std（ d 1，d 2，…，d N） ""（2）

其中：Vol （S t） 表示輪廓分段 S t 的起伏度；std（ d 1，d 2，…，d N） 表示所有采樣點到直線 p 1p N 距離的標準差。起伏度描述了分段的復雜程度，分段的起伏度越大，其描述輪廓特征的能力就越強。基于起伏度的輪廓合并算法如下：

a）設置最小分段數 F ，給定所有分段 C={S t}（t=1，2，…） ，計算各個分段的起伏度Vol （S t） 。

b）當輪廓分段數大于 F 時，開始合并輪廓分段；否則將當前分段作為最終特征分段。

c）選取輪廓分段中起伏度最小的片段 S t 進行合并， S t-1 和 S t+1 表示與 S t 左右相鄰的兩個片段。若Vol （S t-1） ≥Vol （S t+1），則S t與左邊相鄰片段S t-1合并；否則與右邊相鄰片段S t+1 合并。

d）將合并后的輪廓片段添加到分段集合 C 中，并從輪廓集合中將原片段 S t 剔除，重新計算合并后分段的起伏度。若當前輪廓分段數大于 F ，轉向步驟c），否則結束輪廓分段過程。

圖2為基于起伏度的輪廓分段合并算法流程。

通過分段合并算法得到最能體現(xiàn)局部特征的幾段輪廓分段。圖3給出了輪廓分段優(yōu)化效果圖。其中（a）給出了輪廓初步分段結果，通過DCE算法得到27段分段；（b）～（d）給出了分段優(yōu)化過程，在每一次合并操作中，選取價值最低的輪廓分段與相鄰價值最高的輪廓分段進行合并，獲得三段有效分段。通過優(yōu)化算法不僅使得特征分段數量減少，而且獲得的分段起伏度較大，能夠較好地描述輪廓的局部特征，有助于取得準確穩(wěn)定的識別結果。

2 形狀相似度匹配

在獲得遮擋目標輪廓的有效分段后，將其與數據庫中的輪廓分段進行相似度匹配。文獻［8，9］采用分段之間的形狀上下文距離來衡量其相似度，取得了較好的識別效果，但形狀上下文描述子不具有旋轉不變性，對于復雜輪廓以及存在非剛性形變的輪廓魯棒性較差，而且破壞了輪廓順序這一原本存在的特征，使得算法無法滿足高精度識別的要求。為精確描述輪廓分段特征信息，本章將高度函數作為輪廓分段的描述子，該描述子準確地描述了輪廓信息，引入輪廓順序這一特征，對于目標形狀的局部變形具有良好的魯棒性。在特征匹配階段，采用動態(tài)規(guī)劃算法求取特征序列之間的相似性，結合分段顯著性度量對目標進行匹配，可以有效提高遮擋目標識別準確率。

2.1 基于高度函數和動態(tài)規(guī)劃的相似性度量

高度函數是基于輪廓信息的形狀描述子，對于平移、旋轉、相似性變換具有不變性［13］。其基本原理如下：給定輪廓分段 P={p i}（i=1，2，…，N） ，其中 p i 為輪廓上第 i 個采樣點， N 為采樣點的個數，對于任意采樣點 p i ，定義高度函數 H i 為其他采樣點到該點切線距離的有序序列。

H i=（h1 i，h2 i，…，hN i） T= （h i，i，h i，i+1，…，h i，N，h i，1，…，h i，i-1） ""（3）

其中： h i，j 表示輪廓分段第 j 個采樣點到采樣點 p i 切線的垂直距離，即相對于點 p i 的高度函數值。該描述符具有旋轉、平移不變性，為使該描述子具有縮放不變性，對矩陣的每一行進行歸一化處理：

gj i= h i，j "max "t=1，2，…，N{‖hj t‖} """（4）

在得到遮擋目標輪廓分段和數據庫中所有輪廓分段的高度函數特征序列后，將輪廓分段之間高度函數特征的距離作為分段匹配的相似性度量。假設采樣點 p i 和 q j 分別屬于分段 P 和 Q ， gt p 和 gt q 分別為 p i 和 q j 兩點上第 t 個高度函數值，則兩點之間的特征距離為

cv （p i，q j）=∑ N t=1 μ t|gt p-gt q| ""（5）

其中： """μ t= 1 "min {t，M-t} "t=1，2，…，N ""（6）

在獲得兩個輪廓分段任意采樣點之間的特征距離后，利用動態(tài)規(guī)劃算法尋找輪廓分段 P 和 Q 的最優(yōu)匹配關系 β* ，使得每對輪廓點匹配距離的總和最小，最終得到輪廓分段 P 和 Q 之間的距離差異為

S（P，Q）=∑ N i=1 "cv （p i，β（p i）） ""（7）

2.2 輪廓分段顯著性度量

在進行輪廓分段匹配時，為獲得更精準的匹配結果，利用分段顯著度的分析對輪廓片段的重要性作出合理評價，本節(jié)選用輪廓分段的起伏度占比、長度占比分別評價輪廓分段特征的突出程度，最后將兩個參數聯(lián)合起來定義輪廓分段的顯著度。對于輪廓分段 S t ，起伏度占比 λu（S t） 和長度占比 λl（S t） 可表示為

λu（S t）= Vol （S t）/ max（Vol （S j）） ""（8）

λl（S t）=l（S t）/ max （l（S j）） j=1，2，… ""（9）

其中：Vol （S t） 表示分段 S t 的起伏度； l（S t） 表示分段 S t 的長度； λu（S t） 反映了輪廓分段 S t 的復雜程度， λu（S t） 越大，表明分段的復雜度越大，包含的特征信息越明顯； λl（S t） 反映了輪廓分段 S t 占整體輪廓的長度比例， λl（S t） 越大，則該分段描述的特征越豐富，其識別結果越具有可信度。在此基礎上得到分段的顯著度為

λ（S t）=θλu（S t）+（1-θ）λl（S t） ""（10）

其中： λ（S t） 表示分段 S t 的顯著度； θ 為調整 λu（S t） 和 λl（S t） 對分段顯著度 λ（S t） 貢獻程度的參數。

2.3 聯(lián)合相似度匹配

通過分段優(yōu)化算法獲得遮擋目標輪廓分段后，將其與模板輪廓分段庫進行逐對匹配，假設輪廓分段 SP i（i=1，2，…，N）和SQ j（j=1，2，…，M） 分別屬于目標輪廓 P 和模板輪廓 Q ，通過動態(tài)規(guī)劃算法計算兩個輪廓所有分段之間的高度函數特征相似度 S（SP i，SQ j） ，最后結合分段特征顯著度分析，得到最終衡量輪廓分段匹配準確率的聯(lián)合相似性度量。

D（SP i，SQ j）= S（SP i，SQ j） λ（SP i）+λ（SQ j） """（11）

其中： λ（SP i） 和 λ（SQ j） 分別表示輪廓分段 SP i 和 SQ j 的顯著度，輪廓分段的顯著度越高，其特征對于整體目標識別結果的貢獻越大，匹配結果越具有可信性。最后得到目標輪廓 P 和模板輪廓 Q 之間的相似度距離為

D P（P，Q）=D min（SP i，ρ（SQ j）） i=1，2，…，N ""（12）

其中： ρ（SQ j） 表示模板輪廓 Q 中與遮擋輪廓分段 SP i 相匹配的輪廓分段。根據式（12）選取 D P（P，Q） 最小值所對應的目標作為遮擋目標 P 的最終識別結果。本文算法的結構框架如圖4所示。

3 實驗結果與分析

為驗證本文遮擋目標識別算法的有效性，在MPEG-7圖片數據庫上進行遮擋目標匹配實驗，MPEG-7數據庫共有1 400張圖像，包含了70類形狀，每類20張圖片，選取每個類別中前15個形狀（共1 050個形狀）建立輪廓分段數據庫，在剩余圖像中選取15張不同形狀的圖像作為測試目標，目標測試集如圖5所示。

本文通過刪除連續(xù)的輪廓點對測試目標輪廓模擬不同比例的遮擋情況（遮擋率為10%～50%），在此基礎上建立遮擋目標數據庫。圖6給出了不同程度遮擋下的rat測試目標。在仿真實驗中，控制離散曲線演化程度的閾值 τ =0.4，輪廓分段數 F =3，輪廓分段特征提取時均勻采樣點數 N =60，在計算分段顯著度時，由于輪廓分段的起伏度越大，所描述的輪廓特征越明顯，對于整體目標識別的貢獻越大，選取 θ =0.8。

將遮擋目標數據庫中的每個形狀作為待檢索目標，分別與數據庫中所有形狀進行相似度匹配，表1給出了部分目標在遮擋率為20%時的匹配結果。其中第1列為測試目標，通過輪廓分段優(yōu)化算法獲得三段有效分段，第2～4列給出了與待測目標相似程度最高的前三個形狀以及對應的距離值，其中加粗實線表示匹配結果中與測試目標分段最相似的輪廓特征分段。可以看出，對于遮擋目標，在保留輪廓主要特征的基礎上，通過本文算法能夠獲得準確的識別結果。

實驗中為保證目標識別的準確性，在每一種遮擋情況下對測試目標進行100次隨機遮擋處理，將識別結果的平均值作為測試目標在該遮擋比例下的識別率，表2給出了測試目標在不同遮擋比例下的識別率。從中可以看出，本文算法對于目標輪廓遮擋的魯棒性較強，隨著遮擋率的提高，測試目標的識別率有所下降，但仍能保持較高的識別精度。deer、butterfly、beetle等復雜目標的識別率相對較高，這是由于此類目標輪廓的局部特征相對多于tree、chicken等簡單目標，所以雖然輪廓的缺失使得部分特征丟失，但仍能通過其他的局部特征對目標進行識別。

表3給出了本文算法與其他部分遮擋目標識別算法的識別效果比較，可以看出本文算法取得了最佳的識別效果，在不同比例的遮擋下，本文算法的識別率均優(yōu)于其他常見算法。這得益于以下原因：a）本文通過離散曲線演化算法平滑簡化輪廓，提取特征點對輪廓初步劃分，相較于文獻［5，8，14］中通過曲率關鍵點對輪廓劃分的方法，本文算法對于輪廓噪聲具有更好的魯棒性，同時根據起伏度這一價值尺度將輪廓分段合并成有限個完整描述輪廓信息的特征分段，提高了識別的準確率；b）本文選取高度函數作為輪廓分段的特征描述子，相較于文獻［9，15］中采用的形狀上下文描述子，高度函數描述子包含輪廓采樣點順序這一特征，更加準確地描述了輪廓分段信息，有效地提升了目標識別的效果；c）本文引入輪廓分段顯著度分析，突出重要分段對于整體目標識別的貢獻程度，使得輪廓分段的匹配結果更具有可信度。

4 結束語

本文提出了一種基于輪廓特征描述的遮擋目標識別算法，在獲取輪廓有效分段方面保持輪廓特征的基礎并通過離散曲線演化算法簡化目標輪廓，提取特征點對輪廓初步劃分，根據起伏度這一價值尺度對分段進行合并優(yōu)化，得到完整描述輪廓信息的有效分段。在特征匹配方面，提取輪廓分段的高度函數描述子，通過動態(tài)規(guī)劃算法分析輪廓分段之間高度函數特征的相似度，最后聯(lián)合輪廓分段特征顯著度分析，獲得最終的識別結果。實驗結果表明，本文算法對于遮擋下的目標能夠取得準確、合理的識別效果，有效提高了遮擋目標識別率。在后續(xù)研究中，將探索如何有效地將本文的輪廓分段優(yōu)化算法和相似度匹配算法應用到基于輪廓特征的自然圖像識別中。

參考文獻：

［1］ ""Li Baiping，Jing Xiaomei.A recognition scheme based on K-means feature clustering for obscured apple object［J］. IOP Conference Series：Materials Science and Engineering， 2020， 740 （1）：12086-12091.

［2］ "Jia Qi，F(xiàn)an Xin，Liu Yu， et al .Hierarchical projective invariant contexts for shape recognition［J］. Pattern Recognition ，2016， 52 ：358-374.

［3］ Gao Feng，Wang Mingqian，Cai Yichao， et al .Extracting closed object contour in the image：remove，connect and fit［J］. Pattern Analysis amp; Applications ，2019， 22 （3）：1123-1136.

［4］ 代沅興，于天彪，楊建宇，等.一種新的基于輪廓特征的指尖及手指指向檢測方法［J］.東北大學學報：自然科學版，2018， 39 （7）：937-941. （Dai Ruanxing，Yu Tianbiao，Yang Jianyu， et al. An innovative method for fingertip and finger pointing detection based on contour features［J］. Journal of Northeastern University：Natural Science ，2018， 39 （7）：937-941.）

［5］ Krolupper F，F(xiàn)lusser J.Polygonal shape description for recognition of partially occluded objects［J］. Pattern Recognition Letters ，2007， 28 （9）：1002-1011.

［6］ Saber E，Yao Wuxu，Tekalp A M.Partial shape recognition by submatrix matching for partial matching guided image labeling［J］. Pattern Recognition， 2005， 38 （10）：1560-1573.

［7］ Bai Xiang，Yang Xingwei，Latecki L J.Detection and recognition of contour parts based on shape similarity［J］. Pattern Recognition ，2008， 41 （7）：2189-2199.

［8］ 史思琦，石光明，齊飛，等.基于特征完整描述的部分遮擋目標識別算法［J］.系統(tǒng)工程與電子技術，2011， 33 （4）：60-65. （Shi Siqi，Shi Guangming，Qi Fei， et al. Partially occluded object recognition algorithm based on feature description integrity［J］. Systems Engineering and Electronics ，2011， 33 （4）：60-65.）

［9］ 史思琦，石光明，李甫.基于輪廓特征多層描述和評價的部分遮擋目標匹配［J］.光學精密工程，2012， 20 （12）：2804-2811. （Shi Siqi，Shi Guangming，Li Fu.Partially occluded object matching via multi-level description and evaluation of contour features［J］. Optics and Precision Engineering ，2012， 20 （12）：2804-2811.）

［10］ 張桂林，李強，陳益新，等.局部遮擋目標的識別［J］.華中理工大學學報，1994， 22 （5）：15-19. （Zhang Guilin，Li Qiang，Chen Yixin， et al. A method for recognizing partially-occluded objects［J］. Journal of Huazhong University of Science and Technology， 1994， 22 （5）：15-19.）

［11］ 宋建輝，宋鑫，于洋，等.采用輪廓片段空間關系實現(xiàn)遮擋目標識別［J］.華中科技大學學報：自然科學版，2019， 47 （7）：79-83. （Song Jianhui，Song Xin，Yu Yang， et al. Occlusion targets recognition using contour fragments spatial relationship［J］. Journal of Huazhong University of Science and Technology：Natural Science ，2019， 47 （7）：79-83.）

［12］ 胡大盟，黃偉國，楊劍宇，等.改進離散曲線演化的形狀匹配算法［J］.計算機輔助設計與圖形學學報，2015， 27 （10）：1865-1873. （Hu Dameng，Huang Weiguo，Yang Jianyu， et al. Improved shape matching algorithm based on discrete curve evolution［J］. Journal of Computer-Aided Design amp; Computer Graphics ，2015， 27 （10）：1865-1873.）

［13］ Wang Junwei，Bai Xiang，You Xinge， et al. Shape matching and classification using height functions［J］. Pattern Recognition Letters ，2012， 33 （2）：134-143.

［14］ Sun K B，Super B J.Classification of contour shapes using class segment sets［C］//Proc of IEEE Conference on Computer Vision and Pattern Recognition.2005：727-733.

［15］ 黃偉國，顧超，尚麗，等.基于輪廓分層描述的目標識別算法研究［J］.電子學報，2015， 43 （5）：854-861. （Huang Weiguo，Gu Chao，Shang Li， et al. Hierarchical representation method for object recognition［J］. Acta Electronica Sinica ，2015， 43 （5）：854-861.）