李洪武董 波

（1 遼寧警察學(xué)院 遼寧 大連 116036；2 大連恒銳科技股份有限公司 遼寧 大連 116023）

基于霍夫變換的工具痕跡特征提取方法研究

李洪武1董 波2

（1 遼寧警察學(xué)院 遼寧 大連 116036；2 大連恒銳科技股份有限公司 遼寧 大連 116023）

利用計(jì)算機(jī)對(duì)線(xiàn)條型工具痕跡進(jìn)行自動(dòng)比對(duì)的關(guān)鍵是提取特征，基于此，研究了一種基于霍夫變換的工具痕跡特征提取方法，該方法包括圖像預(yù)處理、邊緣檢測(cè)、霍夫變換、直線(xiàn)模型匹配與聚類(lèi)、主方向與成痕過(guò)程模擬幾個(gè)步驟，通過(guò)以上步驟可以從痕跡圖像中提取工具痕跡的直線(xiàn)方程與成痕方向，為后續(xù)特征比對(duì)提供數(shù)據(jù)基礎(chǔ)。

霍夫變換 工具痕跡 特征提取

線(xiàn)條型工具痕跡數(shù)字化比對(duì)方法的研究是基于提取痕跡的特征點(diǎn)，利用計(jì)算機(jī)采用線(xiàn)性圖像邊緣檢測(cè)算法和圖像匹配技術(shù)，利用圖像的邊緣紋理特征對(duì)圖像進(jìn)行比較，并根據(jù)這些特征的匹配度統(tǒng)計(jì)數(shù)據(jù)，對(duì)工具痕跡之間的相似度做出評(píng)價(jià)。它的開(kāi)發(fā)研制可以提高檢驗(yàn)鑒定的準(zhǔn)確度，進(jìn)而提高此類(lèi)痕跡的利用率，對(duì)于串并案件和提升刑事案件的偵破率具有較大的幫助。構(gòu)建該工具的技術(shù)關(guān)鍵有兩個(gè)：工具痕跡特征的提取與量化描述，工具特征痕跡特征相似性評(píng)價(jià)模型構(gòu)建。前者是后者的研究基礎(chǔ)。

1 算法內(nèi)容

1.1 霍夫變換

霍夫變換(Hough Transform)是圖像處理中從圖像中識(shí)別幾何形狀的基本方法之一，該方法最早是由霍夫于1959年提出的，直到1981年，Ballard提出利用該變換來(lái)檢測(cè)幾何形狀是可行的。隨著該理論的不斷擴(kuò)充，其應(yīng)用也變得越來(lái)越廣泛，也衍生出了很多改進(jìn)算法。但是，最常用的霍夫變換就是從黑白圖像中檢測(cè)直線(xiàn)，應(yīng)用場(chǎng)景主要是目標(biāo)識(shí)別與定位，比如衛(wèi)星圖像的橋梁識(shí)別、自動(dòng)駕駛中的路線(xiàn)檢測(cè)等。

對(duì)于霍夫變換的基本原理可以從基于霍夫變換的直線(xiàn)識(shí)別過(guò)程來(lái)理解：在平面直角坐標(biāo)系（x-y）中，一條直線(xiàn)可以用方程y=kx+b表示。對(duì)于直線(xiàn)上一個(gè)確定的點(diǎn)(x0，y0)有b=y0-kx0，則該直線(xiàn)也可以變成以-x0為斜率、y0為截距直線(xiàn)，原始的（x-y）坐標(biāo)系，變成了（k-b）坐標(biāo)系，那么原始直線(xiàn)上所有的點(diǎn)，在（k-b）坐標(biāo)系中變成了直線(xiàn)簇，從數(shù)據(jù)域到參數(shù)域的變換就是霍夫變換，這樣一來(lái)，直線(xiàn)簇公共交點(diǎn)在參數(shù)域的坐標(biāo)值，就是所要檢測(cè)的直線(xiàn)方程參數(shù)。有幾個(gè)交點(diǎn)，就代表待檢測(cè)圖像中有幾條直線(xiàn)。

1.2 基于霍夫變換的工具痕跡特征提取方法工作流程

首先，對(duì)采集到的工具痕跡圖像通過(guò)預(yù)處理進(jìn)行灰度化與去噪，然后利用邊緣檢測(cè)得到邊緣圖像，利用邊緣的坐標(biāo)集進(jìn)行霍夫變換，再對(duì)檢測(cè)到的直線(xiàn)進(jìn)行聚類(lèi)，并剔除干擾直線(xiàn)，最后利用直線(xiàn)線(xiàn)段擬合，得到成痕過(guò)程整體曲線(xiàn)描述，并給出成痕主方向（如圖1所示）。

1.3 圖像預(yù)處理

主要有灰度化處理和灰度歸一化兩個(gè)基本環(huán)節(jié)。灰度歸一化處理的目的是將從灰度上盡量消除由于成像系統(tǒng)不統(tǒng)一帶來(lái)的成痕灰度差異?；叶然瘏⒖寄Ｐ腿缦率剿尽?/p>

式中，I（x，y）代表的是原圖灰度；g（x，y）代表的是處理后圖灰度；k是灰度縮放系數(shù)；b是灰度平移系數(shù)。

圖1 算法流程圖

圖2為待檢測(cè)圖像，圖3是經(jīng)過(guò)灰度歸一化的圖像，從結(jié)果來(lái)看，該步驟同樣具有部分圖像增強(qiáng)的效果。

圖2 待檢測(cè)圖像

圖3 灰度歸一化圖像

1.4 邊緣檢測(cè)

由于工具成痕客體不同，而且客體表面的紋理與工具痕跡之間的關(guān)系模型并不固定，因此，此步驟建議采用人工標(biāo)畫(huà)成痕區(qū)域，消除其他紋理線(xiàn)條的影響。然后進(jìn)行差分，得到邊緣差分值，通過(guò)自動(dòng)閾值二值化得到邊緣，采用Sobel算子進(jìn)行一階差分，達(dá)到邊緣檢測(cè)的目的。由于單純的邊緣檢測(cè)不帶有整體去噪特性，因此，后續(xù)的差分去噪、形態(tài)學(xué)操作、邊緣細(xì)化等步驟是必不可少的。利用能量均值做二值化閾值，進(jìn)行圖像二值化處理，得到最后的邊緣圖。

1.5 基于霍夫變換的直線(xiàn)提取

該環(huán)節(jié)主要參考霍夫變換檢測(cè)直線(xiàn)的方法，該方法可以將邊緣坐標(biāo)點(diǎn)進(jìn)行霍夫變換，得到直線(xiàn)方程，同時(shí)得到了直線(xiàn)的方向描述，圖4是圖2經(jīng)過(guò)霍夫變換之后的參數(shù)域圖像，圖5是檢測(cè)出的圖像中直線(xiàn)軌跡所處位置。由圖可知，由于邊緣圖中的直線(xiàn)有很多，得到的結(jié)果中會(huì)有干擾項(xiàng)存在，所以需要其他方法來(lái)剔除邊界痕跡，并對(duì)其余直線(xiàn)劃分類(lèi)別討論。

圖4 參數(shù)域結(jié)果

圖5 霍夫變換直線(xiàn)檢測(cè)結(jié)果圖（檢測(cè)出直線(xiàn)已在圖中標(biāo)出）

1.6 直線(xiàn)聚類(lèi)與干擾剔除

聚類(lèi)方法，其基本理念就是通過(guò)對(duì)樣本劃分區(qū)域特征統(tǒng)計(jì)，得到樣本分布中心，從而達(dá)到分類(lèi)的目的，對(duì)于直線(xiàn)而言，對(duì)其斜率進(jìn)行二維聚類(lèi)分析，便可以將同方向的直線(xiàn)歸并到同一類(lèi)別，從而得到主要成痕方向以及各自直線(xiàn)之間的夾角。而邊界干擾線(xiàn)可以直接通過(guò)直線(xiàn)所在區(qū)域判定，直接剔除即可。圖6中標(biāo)記了經(jīng)過(guò)該步驟以后，圖2檢測(cè)到的痕跡直線(xiàn)。分類(lèi)結(jié)果如表1所示。通過(guò)計(jì)算，主要類(lèi)別間夾角為13.8度。

圖6 直線(xiàn)聚類(lèi)剔除后結(jié)果

表1 痕跡直線(xiàn)分類(lèi)結(jié)果

至此，工具痕跡的主要特征：線(xiàn)條數(shù)量、不同線(xiàn)條的方向聚類(lèi)特征點(diǎn)位置、線(xiàn)條的直線(xiàn)方程描述以及相鄰線(xiàn)條間的角度差都計(jì)算完畢，以上特征作為工具痕跡特征，用于后續(xù)的特征比對(duì)。

1.7 成痕過(guò)程仿真

這個(gè)步驟屬于數(shù)據(jù)可視化的范疇，在上一步中，計(jì)算機(jī)得到了主要類(lèi)別的信息與特征，但無(wú)法從主觀上觀察到成痕信息，因此，將上一步中分類(lèi)完畢的同類(lèi)直線(xiàn)進(jìn)行統(tǒng)計(jì)擬合，得到整體痕跡線(xiàn)，就可以將直線(xiàn)內(nèi)容從圖像上表現(xiàn)出來(lái)，易于觀察。通過(guò)分析直線(xiàn)間的角度變化差異，可以估計(jì)成痕時(shí)的工具使用方向，以動(dòng)畫(huà)的形式表現(xiàn)出成痕過(guò)程，仿真過(guò)程的部分圖像可參考圖7。

2 實(shí)驗(yàn)結(jié)果與分析

為了檢驗(yàn)算法的基本性能，采用了12組工具痕跡圖像進(jìn)行測(cè)試，12組圖像是通過(guò)3種工具留下的，通過(guò)各組實(shí)驗(yàn)圖像結(jié)果可知，不同工具之間的數(shù)據(jù)有較大的差異性，同種工具之間，在主痕跡線(xiàn)的方向、線(xiàn)與線(xiàn)之間的夾角、線(xiàn)條數(shù)量上都有較好的相似性，可以考慮利用這些參數(shù)構(gòu)建評(píng)分模型。限于篇幅內(nèi)容，本文給出3種工具的部分仿真結(jié)果圖，具體內(nèi)容參考圖8。對(duì)于相應(yīng)的圖像，其特征描述可參考表2（夾角項(xiàng)是該類(lèi)別與下一個(gè)類(lèi)別間的夾角，最后一類(lèi)的夾角值為空）。

圖7 不同時(shí)刻痕跡仿真過(guò)程圖像

3 結(jié)論

本文給出了基于霍夫變換的工具痕跡特征提取方法，痕跡特征包括痕跡數(shù)量、痕跡直線(xiàn)描述與痕跡間夾角三個(gè)特征值，對(duì)于不同工具所形成的痕跡圖像，都可以完成定量檢測(cè)，并且可以通過(guò)過(guò)程仿真，動(dòng)態(tài)顯示成痕過(guò)程，為了提高痕跡檢驗(yàn)的效率，利用該特征，需要進(jìn)一步利用量化評(píng)分模型來(lái)進(jìn)行特征比對(duì)研究。

圖8 三種工具痕跡仿真結(jié)果圖

表2 三種不同工具痕跡特征結(jié)果

[1]張書(shū)杰.工具痕跡學(xué)[M].北京：中國(guó)人民公安大學(xué)出版社，2002.

[2]D.H.Ballard.Generalizingthe Hough Transform to Detect Arbitrary Shapes[J].Pattern Recognition，1981，13(2).

[3]Hartigan,J.A.and Wong，M.A.A K-means clustering algorithm[J].Applied Statistics，1979，28.

（責(zé)任編輯：孟凡騫）

D918.3

A

2014-11-07

遼寧省教育廳科學(xué)研究一般項(xiàng)目（編號(hào)：L2012455）

李洪武（1969-），男，遼寧朝陽(yáng)人，遼寧警察學(xué)院刑事技術(shù)系教授，學(xué)士，主要從事刑事科學(xué)技術(shù)教學(xué)和科研工作。