鞋印花紋裂縫特征自動檢測方法

陳偉卿，于 躍，蘭 胤，黃日輝，張 翼，靳躍群，馮 海，劉威恒，姜福鑫

（1.大連恒銳科技股份有限公司，遼寧 大連 116085；2.廣州市公安局刑事技術所，廣州 510440）

鞋外底損傷特征是指大底在堅硬銳利的客體上踩踏、蹬踢、磕碰形成的硬傷，這些特征出現的位置、形狀、大小和深淺具有隨機性，特定性好[1]，是鞋印鑒定的主要依據?；y裂縫特征，是鞋在穿用過程中由于受到外力的影響，導致鞋底局部材料缺失形成的一類損傷特征，在鞋印上呈現為連續花紋的中斷。該特征常發生在較細的花紋上。引起花紋材料缺失的原因和物質特性不同，裂縫特征的大小和位置也因此具有較高的隨機性，在直線型、波折型鞋印的鑒定中，這類特征的識別和特征之間相符程度的比較起到非常關鍵的作用。

實際鞋印鑒定和相關的科研工作中，特征的辨識主要由人工進行。國內外學者對隨機特征（即細節特征）的檢測和描述進行了一系列嘗試。Yekutieli等[2]開發了專門的特征繪制工具，采用人工交互方式實現特征邊界的描繪：首先圍繞隨機特征使用多邊形標畫出特征范圍，對多邊形內圖像使用交互的二值化操作，得到初始邊界，以此為基礎，對邊界進行人工的增、刪、改操作，得到特征的最終邊界，建立特征數據庫，進行鞋印隨機特征稀有性的量化研究；隨后同機構的Shor等[3]利用該數據庫驗證了在實際案例中，使用他們提出的統計方法得到的量化結果，與傳統的專家鑒定結論之間具有相關性。美國西弗吉尼亞大學Speir的團隊[4-5]做了大量的工作，對1 300只鞋進行了隨機特征檢驗，用于對不同鞋在相同位置上出現相似形狀的隨機特征的可能性分析。實驗數據準備中，使用Photoshop軟件中的鉛筆工具，純手工對鞋印圖像中反映出來的隨機特征進行描繪。上述兩種方法均較為繁瑣和耗時，特征位置的標識和特征邊界的繪制不可避免受到操作人員經驗的制約和其他人為因素影響。王新年等[6]將隨機特征分為角型和斑點型兩類，分別使用Harris角點檢測器和Hessian檢測器實現特征的位置（中心點坐標）檢測，但未能標識出特征范圍。劉珞晰[7]對84只鞋大底跟部的人造缺損特征進行了跟蹤研究，使用Photoshop的磁性套索工具對鞋印上的缺損進行標劃，用筆刷工具涂紅標劃的缺損，進而使用FIJI1.0軟件對缺損特征進行測量描述，使用支持向量機對缺損進行訓練和分類測試，實驗結果表明缺損特征有較好的特定性。

可見，目前國內外研究機構已經開始了對隨機穿用特征的特定性、穩定性的定量化基礎性研究。特征檢測是這些研究的基礎。當前研究通常僅進行隨機特征的位置檢測，或借助工具使用人工交互方式進行手動特征標注，不能滿足自動、快速、準確地檢測特征的要求。因此本文提出一種基于嫌疑人鞋印圖像花紋裂縫特征的自動檢測算法，針對局部鞋印圖像，利用圖像處理技術，根據花紋的走向，自動檢測出花紋裂縫特征所在區域，用于后續鞋印鑒定工作，或用于基于特征的量化研究中。

1 花紋裂縫特征自動檢測算法

算法由圖像預處理、連通域分析、花紋切分、花紋段配對、裂縫特征區域檢測與標識等主要步驟組成，算法流程圖如圖1所示。

圖1 算法流程圖Fig.1 Flowchart of the algorithm

圖像預處理包括圖像二值化和中值濾波等，以分割出鞋印圖像的花紋，并去除噪聲影響；連通域分析即將圖像分為互不相連的花紋集合，每個花紋為一個連通區域；花紋切分是將交叉花紋或走向改變的花紋，切分為方向單一的花紋段；花紋段配對，即對花紋段進行兩兩分組，根據各花紋段的走向和相對位置關系，判斷其是否由同一花紋斷裂所產生，即兩者之間的空隙是否為一個裂縫特征；對于配對成功的一組花紋段，進行裂縫特征區域的檢測，并用圓形在原圖中標識出其所在區域，即完成裂縫特征的檢測與標識。算法的輸入為一局部圖像，整幅足跡圖像可首先進行分塊，對每塊圖像調用該算法進行特征檢測。

花紋裂縫特征示例如圖2。圖中顯示一波浪型花紋鞋印的前掌部分，在從上到下第4條花紋的中間位置，及第6條花紋的左側位置，分別有一處連續花紋的斷裂，即裂縫特征（如圖中紅色圓所示）。

圖2 花紋裂縫特征示例Fig.2 Exampled rift characteristics of a shoeprint pattern

1.1 連通域分析

連通域是指圖像中具有相同像素值且位置相鄰的前景像素點組成的圖像區域，連通域分析（connected component analysis）[8]是指將圖像中的各個連通域找出并進行標記的過程。對于二值圖，選取一個前景像素點作為種子，在其八鄰域內，將與種子相鄰的前景像素合并到同一個像素集合中，最后得到的像素集合即為一個連通區域。

對給定的鞋印二值圖像進行連通域分析，可將其中的花紋分為不同的花紋集合，便于進行后續的裂縫特征所在區域的檢測。圖3給出了一花紋圖像的連通域分析示例，其中，圖3a為鞋印圖像的某一局部；圖3b為使用最大類間方差法[9]對圖3a進行閾值化后得到的二值圖像，其中前景像素為白色；圖3c為圖3b經過連通域分析后得到的4個花紋集合，分別由紅色、黃色、淺藍色和藍色表示。

1.2 花紋切分

鞋底花紋類型中，除了常見的平行直線類花紋，還常存在各種波折型、網格型花紋。本文提出的裂縫特征檢測方法，主要依據花紋的走向進行，因此需要首先對交叉型或波折型等復雜花紋進行切分，形成一系列走向單一的花紋段。

對圖像中每個花紋，計算其復雜度。給定閾值T，若復雜度小于T，則視為簡單花紋；若復雜度大于或等于T，則視為復雜花紋，需進行切分，轉化為系列簡單花紋，也稱花紋段。

1.2.1 復雜花紋判定

花紋復雜度定義如下：

其中密實度為平面幾何形狀描述中常用的參數，定義為：

一個花紋的凸包是指包含其所有前景像素的最小的凸多邊形[10]?；y的面積為前景像素個數之和，凸包面積為凸包內包含的像素總個數。

圖4為圖3c所示各花紋的復雜度分析，根據經驗，復雜度閾值T取經驗值0.35?？梢?，圖4a、4c為簡單花紋，圖4b、4d為復雜花紋，需進行花紋切分。注意，對于圖4c這類與區域邊界相連的簡單花紋，由于其區域較小且與其它花紋距離較遠，不再進行后續的計算。

圖3 連通域分析（a：鞋印局部圖像；b：二值圖；c：連通域）Fig.3 The connected component analysis (a: local shoeprint image; b: binary-formatted image; c: the connected components)

圖4 花紋復雜度分析（a：0.1342；b：0.3703；c：0.1645；d：0.5104）Fig.4 Analysis into the complexity of shoeprint patterns (a: 0.1342; b: 0.3703; c: 0.1645; d: 0.5104)

1.2.2 基于邊界到邊界方向距離的復雜花紋切分

簡單花紋無需進行切分處理，直接進行配對即可。對于復雜的花紋，則需要進行切分，即根據其中包含的多個單方向花紋的走勢，將其切分成多個不同方向、互相獨立的花紋段。本文采用邊界到邊界方向距離（boundary-to-boundary orientation distance，BBOD）算法，實現復雜花紋的切分。

BBOD算法[11]常用于漢字字符的筆畫分析中。其基本原理如下：

1）首先將0°~180°均勻量化成K個方向（本文K＝60）；

2）對花紋區域中的每個像素，分別計算經過該點的K個方向的直線與該像素所屬花紋區域邊界相交的兩個邊界點之間的距離，得到一個1×K維的方向距離矢量；

3）以角度為橫軸，方向距離為縱軸，可得該像素點的BBOD曲線；

4）計算BBOD曲線的所有波峰，并將波峰對應的量化方向作為通過該點的切線方向。

圖5a為一鞋印局部圖像二值圖，圖5b為圖5a右側交叉花紋某點（左圖紅色星號所示）處的BBOD曲線。從圖中可見，該點的切線方向為150°（水平向右為x軸正方向，逆時針方向角度為正）。

圖5 BBOD曲線（a：鞋印局部二值圖像；b：BBOD曲線）Fig. 5 BBOD plotting (a: binary-formatted image of local shoeprint pattern; b: BBOD curve about the indicated red star in this Fig.’s a)

基于上述方法求得復雜花紋上各點的切線方向，具有相同切線方向的點組成的連通區域即為該復雜花紋拆分出的花紋段。BBOD曲線具有2個以上波峰的像素，對應于2個或以上花紋的交叉位置，將同時被放在對應量化方向的花紋段中。圖6為一花紋切分示例，其中圖6a為鞋印局部二值圖像，對其中的復雜花紋使用上述切分方法，得到箭頭右側兩組不同方向的花紋段。

圖6 復雜花紋切分（a：二值圖；b：子圖1；c：子圖2）Fig.6 Splitting the complex pattern (a: binary-formatted image; b/c: the sub-image 1/2 from splitting)

1.3 花紋段配對

經過上述復雜花紋判定和對復雜花紋的切分之后，得到了所有的簡單花紋段。接下來將根據這些花紋段的位置及形態，進行疑似裂縫的判定，即對所有簡單花紋段，分別進行兩兩組合，根據其走勢、寬度和空間關系判定它們是否為同一花紋斷裂而形成。如果是，則配對成功，這兩個花紋段將作為一組保留，以進行后續的裂縫特征檢測。

本文提出了基于投影的花紋段配對方法。對于直線型花紋，裂縫后所形成的兩個花紋段走向一致，即二者在同一條直線（共線）；波折型的花紋，在折角處斷裂時，所形成的兩個花紋段呈一定角度（相交）。根據這一規律，對一組花紋段的組合，可通過如下方法判斷其是否由一個完整花紋中斷形成，完成配對：

1）分別計算兩花紋骨架[12]，判斷骨架線是否共線或相交。如果滿足條件，則繼續。

2）生成以候選的兩個花紋段為前景的二值圖像BW1。

3）分別計算兩個花紋段的寬度w1和w2，如果兩寬度差絕對值大于較小寬度的0.5倍，則視為原鞋底設計中的兩個不同花紋，非由同一花紋中斷形成，不能配對，否則，繼續。

4）計算兩個花紋段的質心，及兩質心連線與圖像水平方向的夾角θ，將二值圖旋轉角度θ，得到二值圖BW2。

5）統計BW2在水平方向的投影直方圖，該直方圖若存在兩個波峰，且波峰距離小于一定閾值，則認為當前候選花紋段為同一個花紋中斷而成，即兩花紋段之間空隙為一裂縫特征?？紤]到鞋底花紋設計中，相鄰花紋之間的溝槽寬度通常不大于花紋陽紋本身的寬度，為避免將溝槽視為裂縫特征引起誤檢，此處閾值最大可設為1.5倍花紋寬度。

仍以前面的局部圖像為例說明簡單花紋的配對過程，具體如圖7所示。圖7a為鞋印局部二值圖，對其中復雜花紋切分后形成如圖6所示的2組不同方向的子圖，以子圖1為考察對象，可見共有3個直線型花紋段（圖7b），任取兩組，可有3種組合：（1，2）、（1，3）、（2，3）。其中前2個組合均不滿足共線或相交要求，故僅需對（2，3）的組合進行配對判斷。二者形成的二值圖BW1如圖7c所示；分別求得兩段花紋的質心（圖7d），計算質心連線與圖像水平方向的夾角；并按照該角度旋轉生成圖像BW2，如圖7e所示；對BW2進行垂直投影，并按最大值歸一化，投影結果如圖7f的藍色曲線所示，為了避免噪聲影響，對垂直投影進行二值化，小于一定閾值（圖中閾值為0.35，對應紅色虛線）的視為0，否則為1，得到圖中的紅色階躍曲線，及曲線的兩個峰點P1和P2；兩點的距離小于花紋寬度，故圖7c中這組花紋段配對成功。

圖7 花紋段配對（a：區域圖像；b：切分子圖；c：待配對；d：質心連線；e：旋轉圖像；f：垂直投影）Fig.7 Having the correlating segments matched in pairs (a: original local image; b: sub-image after splitting; c: pairs to be matched; d:joining segments with centroids; e: the image after rotation; f: vertical projection)

花紋寬度的計算方法：使用形態學方法計算花紋的骨架，對骨架上的每個點，計算過該點的骨架法線與花紋邊界的兩個交點，兩交點的歐氏距離即為該骨架點處的花紋寬度，取所有骨架點花紋寬度的均值，作為整個花紋的寬度。

1.4 裂縫特征檢測

裂縫特征檢測是指對配對花紋段進行處理，確定它們之間的缺失部分（即裂縫特征）的位置和范圍，并以適當大小的圓形將該部分標識出來的過程。包括如下步驟：1）裂縫特征中心的確定；2）裂縫特征范圍的確定；3）裂縫特征的標識。

對于組成一個裂縫特征的兩個花紋段，其花紋方向上最近的兩端之間的空隙即為裂縫特征，因此，可分別計算兩個花紋段的骨架，取兩條線距離最近的兩個端點的連線的中點，作為裂縫特征的中心。裂縫特征的范圍用以裂縫中心為圓心、以花紋寬度為半徑的圓進行標識。圖8中，a為待檢測裂縫特征的花紋圖像；b中紅線為配對花紋段的骨架，藍線為兩骨架最近點的連線，紅色圓圈為檢測到的裂縫中心點；c為某骨架點處花紋寬度的計算示意，圖中的藍線和紅線分別為該花紋段的邊界和骨架，綠色為骨架某點處骨架線的法線，兩個紅色小圓為法線與邊界交點；d為檢測結果，裂縫特征用紅色圓標識。

圖8 特征區域檢測與標識（a：原圖；b：特征中心；c：花紋寬度；d：特征標識）Fig.8 Detection and labelling of characteristic site (a: original image; b: characteristic center; c: pattern width; d: labelled characteristic site)

2 實驗

前文介紹了對于給定的圖像區域，自動進行裂縫特征檢測的算法。為了驗證算法的有效性，首先進行實驗圖像的采集，然后使用本文提出的方法，進行裂縫特征檢測實驗。

2.1 實驗圖像采集

首先，使用大連恒銳科技股份有限公司研制的足跡采集系統3.1進行鞋印圖像的采集。共收集經一定時間穿用的平底鞋180雙，由原穿用者親自穿著，按照采集方法，采用正常行走的姿勢踏過采集面板，采集得到動態的數字化鞋印，每只鞋共采集5枚，分辨率為300 DPI。其次，由具有一定檢驗經驗的人員對這些鞋印進行初篩，選擇有個別特征反映的鞋印作為備選鞋印，若每只鞋有多枚鞋印入選，則只選其中1枚，最后得備選鞋印33枚；對備選鞋印進行裂縫特征人工檢驗，截取裂縫特征所在的局部圖像，作為實驗圖像，共計70張。

為了與算法結果對比，人工對這些實驗圖像進行特征標記（共標記特征80個），作為算法性能的評價基礎。

2.2 實驗結果與分析

為了測試算法的性能，在實驗圖像上應用上述算法進行自動裂縫特征檢測，并使用客觀指標進行評價。

部分有代表性花紋的實驗結果如圖9所示。圖9a為復雜的網格型花紋上的裂縫特征檢測示例，從左至右分別為鞋印局部圖像原圖、經預處理和對其中復雜花紋切分后形成的子圖1和子圖2、配對成功的一組配對花紋、檢測結果；圖9b為包含多個裂縫特征的直線型花紋檢測示例，從左至右分別為原圖、3組配對成功的花紋、檢測結果，可見3個裂縫特征均得到了正確檢測；圖9c為波折型花紋的裂縫特征，從左至右分別為原圖、配對花紋、檢測結果。該特征發生在轉折處，也被正確檢測。

圖9 多種類型花紋的裂縫特征檢測實例（a：網格型花紋；b：直線型花紋；c：波折型花紋）Fig.9 Detection of rift characteristics with several shoeprint patterns (a: grid pattern; b: multiple-characteristic line pattern; c: wave pattern)

采用特征檢出率進行算法性能的客觀評價。檢出率是指實驗數據中的裂縫特征被算法正確檢出的比例，即：

檢出率＝正確檢出的特征數目／特征總數目 （3）

對于檢測出的特征，根據交并比是否大于設定閾值來判斷其是否正確。記檢測出的特征標識圓為Cd，對應的人工標記圓為Cg，二者的交并比（intersection over union，IOU）為：

其中等號右邊式子的分子表示兩個圓交集的面積，分母表示兩個圓并集的面積。若IOU>0.5，則認為檢測正確。

實驗圖像中人工標記裂縫特征80個，算法正確檢出特征70個，檢出率為87.5%，各特征對應的IOU值如表1，小于閾值的如黑體部分所示。

表1 檢測結果IOU值Table 1 IOU (intersection over union) values from detection into characteristics

圖10給出了部分漏檢的結果示例，其中紅色圓標記的是檢測結果，藍色圓是漏檢的特征。算法漏檢的主要是位于圖像邊緣的裂縫特征，由于組成這些特征的花紋段較小且位于圖像邊緣，在預處理階段被過濾掉，導致后續無法參與配對。

圖10 漏檢示例Fig.10 Characteristics (indicated with blue circle) missed of detection (for exampling)

當前算法主要是在給定的鞋印區域圖像上進行，完整鞋印需先進行分塊，再對每一塊圖像調用檢測算法完成檢測。實驗結果表明，算法能夠幫助檢驗人員對裂縫特征進行定位。

后續研究中，需研究鞋印自動分塊的方法，以及嘗試使用重疊分塊的方式降低由于特征位于塊邊緣而漏檢的概率。

3 結論

本文對鞋印圖像隨機特征的識別進行了研究，提出了一種基于復雜花紋切分的裂縫特征的自動檢測方法。實驗結果表明，算法能夠正確檢出常見直線型、波折型、網格型等類型花紋上的裂縫特征。對于相對復雜的整幅鞋印圖像，可對其進行分塊，對每塊圖像使用本文方法進行塊內裂縫特征的自動檢測，后續研究將致力于鞋印中相似花紋的分塊處理。本文方法可有效降低鑒定中這類特征檢測對人員經驗的依賴，消除人為因素的影響，為下一步特征的客觀比較奠定基礎。