基于交叉投影熵的車輛目標匹配算法

周軍妮，王燕妮，魏 蕊

(西安建筑科技大學信息與控制工程學院，陜西 西安 710055)

責任編輯:任健男

隨著社會經濟的迅猛發展，交通在人類經濟、社會活動中的地位日益凸顯，交通管理的層次、質量更是與人們生活緊密相關。然而，由于機動車數量的快速增加，道路擁擠、事故頻發、違章逃逸等問題也越發嚴重，交通運輸環境急劇惡化。提高交通管理水平的重要措施就是采用智能交通系統(Intelligent Traffic System，ITS)［1］。在復雜交通場景下，基于數字圖像的車輛目標匹配為交通信息的采集與分析提供了一條良好途徑，這些技術可廣泛地應用于違章、肇事車輛的線索搜尋，這是基于計算機視覺的智能交通系統中的關鍵技術，也是目前智能交通系統研究的熱點。

在復雜的交通環境下，往往需要借助大量的線索圖片查找目標(諸如肇事逃逸車輛)，為了減輕人工查找的工作量，提高工作效率，需要借助一定的匹配算法來實現自動化匹配。目前車輛目標匹配傳統算法是應用灰度相關(Gray Correlation Algorithm，GCA)的模板匹配方法進行目標匹配，該算法具有原理簡單、易于硬件實現等優點，但由于該法直接以圖像灰度為輸入進行相關計算，因此對噪聲、光線變化極為敏感，在實際應用中經常出現錯配、誤配等現象。目前圖像匹配主要利用圖像特征(如輪廓特征、邊緣特征、分形特征、紋理特征、統計特征等)進行目標匹配，相對于灰度相關匹配，基于圖像特征的匹配方法在抗噪性、光線的敏感性方面具有一定的優勢，但圖像特征的描述算法通常復雜度高，從而導致計算量大，因而又影響了其在實時匹配系統上的應用。自Li C H［2］、Brink A D［3］和 Pal N R［4］等人相繼提出最小交叉熵準則，并將其引入到圖像分割領域以來，眾多學者都對交叉熵在圖像處理上的應用進行了探索和研究。如薛景浩提出的基于最大類間后驗交叉熵準則的閾值分割算法［5－6］，而江和平將最小交叉熵準則應用到圖像跟蹤匹配領域［7］，其提出的交叉熵匹配跟蹤算法(Cross－Entropy Algorithm，CEA)具有一定的抗輻射失真和抗幾何失真能力，但其存在抗噪性差、對光線敏感，尤其拍攝時有鏡頭光暈時更是誤檢率很高，并且算法復雜度高等缺點。桂志國提出的基于投影相關法的圖像匹配算法(Projection Correlation Algorithm，PCA)［8］運算速度高，但僅僅依據投影變換進行圖像匹配僅適用于圖像背景單一、目標特征明顯的圖像匹配，此后文獻［9－12］又提出諸多結合投影變換規則的圖像匹配算法，但這些算法大都存在適用場合有限等不足。本文在分析了前人工作的基礎之上，提出了將圖像交叉熵和投影變換相結合的復雜背景車輛目標匹配算法。為了說明方便，以下簡稱為交叉投影熵算法(Cross Projection Entropy Algorithm，CPEA)。CPEA算法結合了CEA算法在圖像匹配上的優勢，同時又利用投影變換改進了CEA算法的算法復雜度，大大提高了圖像的匹配速度。

1 圖像交叉熵和投影變換相結合的車輛目標匹配算法

1.1 圖像交叉熵

熵的概念最早是由克勞修斯(Clausius)于1854年發表的論文《力學的熱理論的第二定律的另一種形式》中首次提出，之后，玻爾茲曼(Boltzmann)定義了玻爾茲曼熵(統計熵)，1948年香農(Shannon)發表了《通信的數學理論》，引入了信息熵的概念，奠定了現代信息論的基礎。交叉熵是在香農信息熵的基礎上定義的，它是一種用來度量兩個概率分布 P={p1，p2，…，pN}，Q={q1，q2，…，qN}之間信息量差異的概念，P和Q通常代表先驗概率和后驗概率［2－4］，其定義為

這里，N代表概率分布中不同概率的信息量，從式(1)可以看出，DCE(P，Q)≠ DCE(Q，P)，即交叉熵不是對稱的。然而，可以通過DCE(P，Q)和DCE(Q，P)相加，得到一個對稱形式的距離度量，稱為對稱交叉熵［2－4］。其定義如下

交叉熵反映的是兩個概率分布的信息量差異，如果P為模板圖像的概率分布矩陣，Q為實時圖像中與模板圖像同尺寸的局部圖像的概率分布矩陣，則根據圖像交叉熵的定義，可以用最小交叉熵準則來進行圖像匹配。一維對稱交叉熵表征了圖像灰度分布的類聚特征，卻沒有反映圖像特征分布的空間屬性，為了表征這種空間位置信息，需要定義二維對稱交叉熵，定義如下

在利用圖像交叉熵來進行圖像匹配時，P和Q分別表示同樣大小的模板圖像及實時圖像的概率分布，通過計算它們之間的最小圖像交叉熵值來確定最佳配準匹配位置。因為這里只是對圖像的某一局部計算交叉熵，因此稱為圖像局部交叉熵。當P和Q的絕對差越小，交叉熵的取值也越小，表示此時模板圖像與實時局部圖像之間的相似性越大。因此，可以通過最小交叉熵的求取來獲得最優圖像匹配坐標。

1.2 圖像投影變換

設f(i，j)(f(i，j)≥0)表示分辨力為M×N的數字圖像，圖像的行、列投影變換分別定義為 U［i］，V［j］，其中

根據上述投影變換的定義，若把大小為M×N的數字圖像看作是M×N個特征向量集，則通過行投影變換和列投影變換，此向量集變換到大小為M+N的向量集。可以看出，投影變換不僅改變了特征點的屬性，并且減小了特征空間的向量數，如果直接將投影變換用于圖像匹配，在某些情況下，可能會降低匹配的精度;另外，在實時圖具有一定程度的幾何形變時，會增強圖像匹配中對光線變化的穩健性，提高匹配性能;更重要的是，由于特征空間維數由二維降到一維，圖像匹配的速度提高了。

1.3 結合圖像交叉熵和投影向量的車輛目標匹配算法

利用式(3)進行基于圖像交叉熵的圖像匹配雖然具有匹配精度較高、抗失真形變性較強的優點，然而，光線變化對于圖像交叉熵的影響較大，其穩健性有待提高;并且由于運算量很大，限制了其在實時跟蹤系統上的應用。

基于此，本文提出將圖像的投影特征和圖像的交叉熵計算方法相結合，用于圖像匹配計算，旨在保持抗幾何失真性較好的同時，一定程度上提高匹配算法的抗光線變化能力和匹配速度。根據投影變換公式(4)和公式(5)及圖像交叉熵的公式(3)，本算法建模的過程中，首先考慮減少交叉熵的計算量，因此以模板圖和實時圖的投影變換作為先驗概率和后驗概率，這樣將圖像交叉熵的二維累加和減少到一維累加和的運算量。基于此，可定義圖像的交叉投影熵為

式中:HU為該圖像的行交叉投影熵，HV為該圖像的列交叉投影熵。由于運算中涉及的是圖像的某一局部定義，因此，式(6)、式(7)定義的交叉投影熵實為局部交叉投影熵。公式中的 PUI［i］，PUJ［i］，PVI［j］，PVJ［j］分別是實時圖的行投影變換、模板的行投影變換、實時圖的列投影變換、模板的列投影變換，定義分別如下

利用式(6)、式(7)，構造復雜交通場景下的車輛目標匹配算法，其實現步驟為:

1)對模板向量計算基于投影變換的交叉熵，分別計算行交叉熵向量和列交叉熵向量;

2)對實時圖按照模板圖的大小進行單元向量劃分，對每個單元計算基于投影向量的交叉熵，得到行交叉熵向量和列交叉熵向量;

3)根據局部交叉投影熵搜索規則，得到每個單元的模板圖與實時圖的行、列交叉熵矩陣;

4)根據步驟3)的結果計算最優解，得到匹配位置坐標，即為匹配結果。

考慮到對數計算運算量很大，實際工程應用中，通常將對數運算用泰勒公式展開，以簡化式(6)和式(7)的運算量。

2 實驗結果與分析

為了驗證本文算法的有效性，用實際圖像做了大量的測試實驗，一方面比較了傳統的灰度相關算法(GCA)、投影相關算法(PCA)以及文獻［7］提出的局部交叉熵算法(LCEA)與本文提出的局部交叉投影熵算法(CPEA)的圖像匹配效率;另一方面進行了基于交叉投影熵算法(CPEA)的誤差分析。本實驗的測試環境為DELL XPS M1330筆記本計算機，操作系統是Windows Vista Home Basic(32 bit/SP2)，其處理器是 Intel Core 2 Duo CPU 2.00 GHz，內存2.00 Gbyte，用 MATLAB 7.01 編程實現。

2.1 結合算法匹配矩陣進行算法有效性分析

圖1所示為測試中用到的實時圖與基準圖，特別要說明的是，為了更清晰地辨識基準圖，顯示的基準圖是按原比例放大3倍的基準圖。首先結合圖2從算法的有效性進行分析。圖2所示的4組圖分別為GCA、PCA、LCEA和本文提出CPEA的算法匹配矩陣三維示意圖。圖2a所示的5幅圖分別為GCA在原圖、光線不足、光線過強、局部遮擋及和云層遮擋情況下算法匹配矩陣的三維示意圖，圖2b、圖2c和圖2d分別為PCA、LCEA和CPEA的算法匹配矩陣三維示意圖。GCA是直接以圖像的灰度為輸入對象，因此當圖像受到光線變化及局部遮擋時，在灰度值本身發生了較大變化時，該算法很難正確地匹配到目標物。從圖2a也能再次驗證這個結論，圖2a第一幅圖為原實時圖像和模板圖的GCA算法匹配矩陣的三維示意圖，可以看出圖2a的第二、三、四、五幅圖與第一幅圖差異非常大，這是由于灰度相關法在灰度發生變化時穩健性很差。PCA首先將灰度向量集轉化為行投影向量和列投影向量，然后進行實時圖與模板圖的相關計算，信息量損失很大，從圖2b可以看出，5幅圖變化很大，當實時圖拍攝環境發生變化時，該算法很不穩定。文獻［7］提出的LCEA是以實時圖和模板圖的灰度概率為輸入對象，因此對光線變化不是很敏感，圖2c的5幅圖為LCEA的算法匹配矩陣三維示意圖，從圖示可以看出，相比圖2a，LCEA的算法匹配矩陣變化相對較小，在圖像灰度有較大變化的情況下也能較好地反映圖像的本質屬性。本文所提出的CPEA是以實時圖和模板圖的投影變換為輸入對象，除了較好地保留了局部交叉熵法對光線變化時的穩健性，還改善了局部交叉熵法運算量大的不足。圖2d所示為本文所提出的CPEA的算法匹配矩陣三維示意圖，與圖2a、2b、2c相比較，圖2d的5幅圖相對變化最小，在光線變化或局部遮擋情況下，前兩種方法沒有明顯的多峰效果，但在本文算法中，這種情況得到了很大改善，不但顯示了較明顯的峰谷特性，而且能很好地反映圖像的本質屬性，更符合人的視覺特征，因此基于局部交叉投影熵的匹配算法不但匹配精度高，而且匹配性能也優于文獻［7］提出的LCEA。

圖1 實時圖和基準圖

2.2 4種算法的匹配時間和匹配性能比較實驗

為了說明CPEA在匹配精度及匹配速度上的優劣，通過上述仿真實驗，對匹配坐標及誤差和匹配時間進行了統計。表1所示為4種匹配算法方法在不同情況下的匹配時間比較。從時間代價來看，GCA和PCA的匹配效率最高，LCEA的匹配速度最慢，而本文所提出的CPEA匹配性能介于兩者之間，比LCEA提高了近1/3 ms。

表2所示為4種匹配算法在不同情況下的匹配性能比較。這里的匹配誤差是指匹配坐標相距實際坐標點(以左上角坐標(377，317)為基準進行比較)的歐氏距離。可以看出本文所提出的CPEA在匹配精度上具有明顯的優勢。

圖2 4種算法的三維示意圖

表1 4種算法在不同情況下的匹配時間比較 mm

2.3 算法仿真結果比較實驗

本次實驗選取的實時圖為一幅大小為560×443、內容極為豐富的城市生活場景圖，基準圖是原圖中左上角坐標為(377，317)截取的大小為44×44的一輛小汽車，詳見圖1。從圖像內容來看，要匹配的目標是馬路上的一輛汽車，可以看到，這幅圖片上有很多和目標很相似的部分，比如其他的汽車、高樓上的窗格以及高聳的汽車廣告牌等，并且在幾何尺寸和灰度變化規律上都和目標汽車非常接近，所以選擇這幅圖片來驗證本文算法的匹配效果。應用4種算法分別對實時圖像進行變暗、變亮、光暈效果及遮擋處理后的情況進行目標匹配比較。圖3所示的4幅圖分別為光線不足、光線過強、光圈光暈及局部遮擋情況下的實時圖。圖4所示4組圖分別是為光線不足、光線過強、光圈光暈及局部遮擋情況下的目標匹配結果，其中圖4a為GCA的匹配結果，圖4b，4c，4d分別為PCA、LCEA和CPEA的匹配結果。可以看出，本文提出的CPEA在光線變化、鏡頭光暈及存在局部遮擋情況影響時，相比GCA、PCA和LCEA都有很好的匹配結果。

表2 4種算法在4種情況下的匹配坐標及誤差(像素)

3 結束語

復雜交通場景下的車輛匹配通常受到光線、遮擋等因素的影響而出現錯配、誤配及漏配的現象。因此匹配算法一定要抗光線變化及在局部遮擋情況下也具有較好的穩健性。圖像交叉熵具有抗局部遮擋性能，而投影向量又降低了算法對光線的敏感度。仿真結果顯示，本文提出的匹配算法CPEA結合交叉熵及投影變換，使其同時具有對光線變化不敏感，并且在一定的局部遮擋情況下也能正確匹配目標物。從匹配時間和匹配精度來看，本文所提出的CPEA匹配速度優于LCEA。從匹配精度看來，比GCA、PCA和LCEA具有明顯優勢。后續的工作是研究CPEA的快速匹配算法，旨在進一步提高該算法的運算速度，使其更加適用于實時匹配系統中。

［1］史忠科，曹力.交通圖像匹配與分析［M］.北京:科學出版社，2007:20－50.

［2LI C H，LEE C K.Minimum cross entropy thresholding［J］.Pattern Recognition，1993，26(4):617－625.

［3］BRINK A D，PENDOCK N E.Minimum cross－entropy threshold selection［J］.Pattern Recognition，1996，29(1):179－188.

［4］PAL N R.On minimum cross－entropy thresholding［J］.Pattern Recognition，1996，29(4):575－580.

［5］薛景浩，章毓晉，林行剛.基于最大類間后驗交叉熵的閾值化分割算法［J］.中國圖形圖象學報，1999，4(2):110－114.

［6］薛景浩，章毓晉，林行剛.圖像分割中的交叉熵和模糊散度算法［J］.電子學報，1999，27(10):131－134.

［7］江和平，沈振康.基于局部交叉熵的圖像匹配跟蹤算法［J］.紅外與激光工程，2005，34(6):729－732.

［8］桂志國，薄瑞峰，韓焱.基于投影特征的圖像匹配的快速算法［J］.華北工學院測試技術學報，2000，14(1):18－20.

［9］鈕峰，俞能海，吳皓.航空圖片中車輛的匹配方法研究［J］.電路與系統學報，2002，7(4):80－83.

［10］曹丹華，劉斌昺，吳裕斌.投影特征匹配的快速鈔幣面值識別算法［J］.光電工程，2004，31(1):59－62.

［11］羅鐘鉉，劉成明.灰度圖像匹配的快速算法［J］.計算機輔助設計與圖形學學報，2005，17(5):966－970.

［12］黃文杰，王海濤，姬建崗.基于公路收費系統的車牌定位與字符分割算法［J］. 電視技術，2006，30(2):85－87.