基于輪廓特征的平面鞋印自動識別算法的研究和實現

摘 要：提出了一種基于輪廓特征的平面鞋印自動識別算法，根據鞋印長度比任何一個部位的長度和寬度都長這一特點，找到距離最長的兩輪廓點，算出由這兩點確定的直線與水平方向軸所成夾角，根據此夾角將鞋印圖像進行傾斜校正，然后自動提取鞋印輪廓九個特征，利用歐氏距離進行鞋印的相似性度量。實驗結果表明運用該算法進行鞋印識別是很有效的。

關鍵詞：輪廓特征； 輪廓提取； 傾斜校正； 鞋印識別

中圖分類號：TP311 文獻標志碼：A 文章編號：1001-3695(2008)08-2413-03

Research and realization of recognition for shoe soles based on outline feature

GUAN Yan1， 2， LI Cun-hua1， ZHONG Zhao-man2

(1.School of Information Engineering， Yangzhou University， Yangzhou Jiangsu 225009， China; 2. Dept. of Computer， Lianyungang Normal College， Lianyungang Jiangsu 222006， China)

Abstract:This paper proposed a method of recognition for shoe soles based on outline feature， which found that the two outline points at the longest distance according to the feature that the length of shoe sole was longer than any other parts in a shoe sole， and then calculated the angle shaped by the two points and horizontal axes. It proofreaded the shoe soles in terms of angle calculated， extracted 9 features of shoe sole automatically， and measured the similarities of shoe soles by Euclidean distance. The experimental results show the method used to recognize shoe soles is effective.

Key words：outline feature; extracting outline; slant correction; recognition of shoe soles

0 引言

鞋印是作案者在作案過程中遺留在承受客體上的痕跡。平面鞋印的分析檢驗一直是偵察和司法實踐中的難題。從目前國內鞋印檢驗工作的總體情況來看，鞋印的諸多特征還需根據經驗去目估判斷，對特征的很多認識都是定性的。盡管幾十年來許多痕跡專家為此進行了大量卓有成效的研究和實踐，總結了許多辦案經驗，也提出了多種檢驗方案。但歸結起來，這些方案大多是手工辦案經驗，標定和測量的標準不一。目前國內外出現利用計算機、數字圖像處理技術進行鞋印識別^[1~9]， 如H. Su等人^[5]提出一種基于鞋印直方圖特征和紋理特征識別鞋印的方法，該方法利用灰度共生矩陣和灰度直方圖提取鞋印的紋理和直方圖特征。由于承受客體不同、光線等因素的影響，會出現同樣的人穿同樣的鞋踩出的兩只鞋印的紋理和直方圖特征不同。國內大連海事大學^[6~9]在鞋印識別研究中做了很多工作，他們主要從鞋底的花紋著手，對于花紋的識別，分別采用人工和機器兩種方法識別。人工識別的方法需要鞋底花紋的錄入者必須是經過專門訓練的，但即使經過訓練，也不能保證鞋印花紋的錄入的正確率達到100%，這樣就影響了鞋印的識別率。由于鞋底花紋的種類繁多，目前他們只提出了一些對常規花紋（圓形、方形、點等）的識別算法，讓機器自動識別出所有鞋底的花紋還是個難點。鞋印的輪廓不同于其他物體的輪廓，它可以用幾何參數（鞋長、掌寬、弓寬、跟寬等）精確描述出來，輪廓特征是鞋印的一個比較穩定的、重要的特征。本文提出了一種基于輪廓的平面鞋印自動識別算法，該算法根據鞋印的輪廓特征進行匹配，按相似度從高到低，列出相似的前20幅鞋印圖像由人工進一步識別。實驗結果表明該方法具有快速、較好的識別率。

1 鞋印幾何形狀特征參數

鞋印的輪廓特征用幾何形狀特征參數進行描述，鞋印分為鞋尖、鞋掌、鞋弓、鞋跟四個區，所用幾何形狀特征參數主要有：a)鞋長（最長軸），鞋印輪廓上距離最大的兩像素點的連線;b)掌寬，鞋印輪廓最寬處的寬度;c)弓寬，弓部最窄的距離;d)跟寬，跟部最寬的距離;e)方位角，鞋印最長軸與水平方向軸的夾角。

2 鞋印圖像預處理

將目標從復雜的背景中分割出來是圖像處理的關鍵技術之一。到目前為止，沒有任何一種算法能將目標從復雜背景中準確無誤地分割出來。本文主要研究的是提取鞋印的有效輪廓特征，進行鞋印識別。為了避免復雜背景的影響，本文實驗用的所有圖像都是在淺色背景下拍攝的，該背景和鞋印的顏色差別很大。因為鞋底的輪廓等同于鞋印的輪廓，為了方便實驗，本文拍攝的都是鞋底圖像。對所有的鞋底圖像進行預處理，主要包括圖像增強、噪聲消除、灰度化、二值化、輪廓提取等。圖像增強是按特定的需要突出一幅圖像中的某些信息，同時削減或去除某些無須處理的信息，提高圖像的可識別率。本文采用Retinex圖像增強算法進行鞋底圖像增強，該算法具有銳化、顏色恒常性、動態范圍壓縮大、色彩保真度高等特點。彩色圖像包含著大量顏色信息，存儲上開銷大，處理上也會降低系統的執行速度，因為本文要提取的是鞋印的輪廓特征，輪廓特征用幾何參數進行描述，無須顏色信息。首先采用經驗公式：grey=0.30×R+0.59×G+0.11×B （grey為灰度值，R、G、B分別為紅色、綠色和藍色分量）將彩色圖像轉換為灰度圖像，再利用最大熵原理來選擇閾值對圖像進行分割，分割后整幅圖像轉換成二值圖像，即背景變為白色，鞋印變為黑色^[10]。

3 輪廓提取、傾斜校正和特征提取算法

通過幾何形狀特征參數描述鞋印的輪廓特征，其核心算法是鞋印輪廓的提取、傾斜校正、輪廓特征提取。為了便于算法的實現，以上鞋印經過預處理之后都進行轉動，使腳尖朝上進行存儲。

3.1 輪廓提取

對于二值化后的圖像，即鞋底圖像是黑色，背景是白色。本文采用逐行掃描的算法，將每行的左起第一個黑像素點和右起第一個黑像素點的坐標記錄下來。具體實現的代碼如下：

void lunkuotiqu()

{ h=0; k=0;flag1=1; flag2=1;

for(int i=0;ibiHeight;i++)

{flag3=1;

for(int j=0;jbiWidth;j++)

//逐行從左掃描，找到左起第一個黑像素點

{ p=pw+(SrcBufSize-LineBytes-i*LineBytes)+j;

if(*p==0)

{flag3=0;

if(flag1==1){h=i; flag1=0;}

a[i][0]=j; break;

}

}

if(flag3==0)

for(int k=m_pBIH->biWidth-1;k>=0;k--)

//逐行從右掃描，找到右起第一個黑像素點

{ p=pw+(SrcBufSize-LineBytes-i*LineBytes)+k;

if(*p==0) {a[i][1]=k; break;}

}

if (flag3==0)(h>0){ k=i; flag2=0;}

if(flag2==0)break;

}

}

該段代碼中主要變量的作用是：a[i][0]存放第i行左起第一個黑像素點的縱坐標；a[i][1]存放第i行右起第一個黑像素點的縱坐標；h用來標志逐行掃描出現的第一個黑像素點所在的行標；k用來標志逐行掃描出現的最后一個黑像素點所在的行標；flag1、flag2分別用來標志逐行掃描到的黑像素點是否第一個黑像素點和最后一個黑像素點；flag3用來標志從左掃描有無黑像素點出現，如果無就沒有必要再從右掃描。

通過該算法使鞋印的輪廓存儲在一個二維矩陣中A=ah，0，ah，1

ah+1，0，ah+1，1

…

ak，0，ak，1。其中:ax，0存放第x行左起第一個黑像素點的縱坐標；ax，1存放右起第一個黑像素點的縱坐標；h≤x≤k，h用來標志逐行掃描出現的第一個黑像素點所在的行標；k用來標志逐行掃描出現的最后一個黑像素點所在的行標。

3.2 傾斜校正

鞋印實地拍攝過程中考慮光線的問題，技術人員為了獲取比較清晰的鞋印紋理，需要調整拍攝的角度。這樣拍攝下來的照片中鞋印會出現各種角度。在鞋印預處理時已將圖像轉動，使鞋尖朝上，但不能保證所有的鞋印圖像的傾斜程度一致，這就直接影響了后面的自動識別和瀏覽效果，所以需要檢測傾斜角度，并轉正圖像。在鞋印的傾斜校正上，本文根據鞋印長度比任何一個部位的長、寬度都長這一特點將方位角作為實際角度偏差加以調整。具體算法描述如下：

a)求出鞋長（最長軸），思路：將鞋印輪廓上最長兩點的距離作為鞋長。本文采用如下的計算公式:l={max(distance((i，ai0)，(j，aj，1))|h≤i≤k，i≤j≤k}。其中:distance((i，ai0)，(j，aj.1))為坐標(i，ai0)的輪廓點與坐標(j，aj，1)的輪廓點的距離；h為輪廓中最上面黑像素點所在的行標；k為輪廓中最下面黑像素點所在的行標；ai0為行標i的左輪廓點的列標；aj，1為行標j的右輪廓點的列標。為了提高執行效率，避免重復求過的兩輪廓點距離，最長軸左邊的輪廓點分別和最長軸右邊所有行標大于等于左輪廓點行標的所有右輪廓點求距離。具體代碼如下：

void qingxiejiaozheng（）

//求出鞋長，同時記下鞋印最長兩點的坐標

{l=0; i1=0，j1=0，i2=0，j2=0;

for(int m=h;mk;m++)

{ if(abs(a[m][1]-a[m][0])>l)

{ l=abs(a[m][1]-a[m][0]);

i1=i2=m;j1=a[m][0];j2=a[m][1];

for(int y=0;y<2;y++)

{ for( int n=m+1;nbiHeight;n++)

for(int z=0;z<2;z++)

if(sqrt((a[m][y]-a[n][Z])*(a[m][y]-a[n][z])+(m-n)*(m-n))>l)

{

l=sqrt((a[m][y]-a[n][Z])*(a[m][y]-a[n][z])+(m-n)*(m-n);

i1=m;j1=a[m][y];i2=n;j2=a[n][z];

}

}

}

}

b)算出方位角α，即最長軸與水平方向X軸的夾角；

c)如果α≤90°，則圖像逆時針轉動的角度為90°-α，如果α>90°，則圖像順時針轉動α-90°。

3.3 鞋印輪廓特征的提取

目前在實際辦案中技術人員采用手工方式測量鞋長、掌寬、弓寬、跟寬，這樣會出現人為的偏差。為了避免特征參數測量不準，給識別帶來影響，本文提出了自動提取鞋印的輪廓特征。鞋印一般分為鞋尖、鞋掌、鞋弓、鞋跟四個區，每個區占整個鞋印一定的比例^[11]，如圖1所示。為了比較準確地描述出各分區的寬度，在圖1描述的各分區的范圍基礎上，上下各擴大5%求其寬度。分別采用式(1)~(3)計算掌寬、弓寬、跟寬。

max{distance((x，ax，0)，(x，ax，1))}

其中:（k-h+1）×13%」≤x≤(k-h+1)×51%」}(1)

min{distance((x，ax，0)，(x，ax，1))}

其中:（k-h+1）×41%」≤x≤(k-h+1)×80%」(2)

max{distance((x，ax，0)，(x，ax，1))}

其中:(k-h+1)×70%」≤x≤k(3)

如果僅用鞋長、掌寬、弓寬、跟寬這四個參數來描述鞋印的輪廓特征是不夠的，會出現這四個參數完全一致的兩只鞋印輪廓完全不同，如圖2所示。出現這種情況的主要原因是沒有考慮掌寬處、弓寬處、跟寬處相對整個鞋的偏移位置，即各特征點的距離或夾角。本文中不僅考慮各部位的長寬度，還考慮各特征點的距離，距離就是反映掌寬處、弓寬處、跟寬處相對整個鞋的偏移位置。鞋印的形狀特征向量描述為S=(CD/AB，EF/AB，GH/AB，AI/AB，AJ/AB，AK/AB，CI/CD，EJ/EF/GK/GH)。

4 鞋印識別流程

鞋印識別的整個過程主要包括六大步驟，如圖3所示。在流程圖中出現兩次輪廓提取，因本文輪廓提取是提取每行左起第一個黑像素點和右起第一個黑像素點，在鞋印傾斜校正前有可能同行上會出現兩個以上的輪廓點，這樣提取就會出現輪廓點遺漏的情況發生，但第一次輪廓提取是為了計算出鞋長（最長軸），并記下最長兩點的坐標，便于下一步的傾斜校正，所以無影響。為了鞋印特征提取的準確性，傾斜校正后必須重新進行輪廓提取。

5 實驗結果及分析

筆者對包含有 500 幅鞋底圖像的數據庫做實驗。其中，鞋底庫主要分為五類：皮鞋、運動鞋、休閑鞋、涼鞋、拖鞋。兩幅鞋印圖像是否相似是指鞋印圖像的特征向量是否相似，將圖像特征看做是向量空間中點，通過計算兩個點之間的接近程度來衡量圖像特征之間的相似度。在圖像相似性度量中，可以采用各種距離函數或者距離度量、統計學方法和非幾何相似性測度方法。本文采用歐幾里得距離公式進行度量，在本系統中采用例子查詢方式，計算其與鞋底庫中的所有圖像的相似度，然后將相似度從高到低的20幅圖像排序后提交給用戶，由用戶進一步識別。為了驗證該方法的實用性，從鞋底庫中抽取30幅圖像進行識別，從實驗結果看，這30幅圖像都可以在返回結果的20幅圖像中找到相同的。圖4為其中一幅示例，利用本文提供的基于輪廓特征鞋印識別方法進行識別，表1列出了與圖4相似性從高到低的前十幅鞋印圖像的特征向量，圖5是表1相應的圖像。從結果看，基于輪廓特征的鞋印識別方法符合人眼的識別模式，具有很好的效果。

表1 與圖4相似性從高到低的前十幅鞋印圖像的特征向量特征值圖像編號02310100123000800712102108905410.3200000.2903230.2833330.2741940.3333330.2816330.3548390.320000.2857140.30864220.2000000.2016130.2083330.2096770.2291670.2326530.2419350.2320000.2040820.24691430.2400000.2217740.2416670.2459680.2500000.2448980.2822580.2440000.2367350.27983540.2400000.3064520.2916670.3024190.3125000.3469390.3145160.3200000.3183670.24691450.6000000.6129030.5791670.5645160.6666670.575510.6048390.6800000.5959180.55555660.7600000.8064520.8250000.8185480.8541670.848980.7983870.8200000.8163270.77777870.5625000.5555560.4852940.5588240.5125000.5507250.4772730.4000000.3183670.24691480.6000000.5600000.5600000.5000000.5454550.5263160.4833330.5000000.5959180.55555690.5500000.5454550.5172410.5245900.6000000.5833330.4571430.5409840.8163270.777778歐氏距離0.0000000.09810440.13182950.14810580.16634820.17086370.20323620.23222310.37560730.39963576 結束語

本文提出了基于輪廓特征的平面鞋印自動識別，創新之處主要有以下兩點：

a)根據鞋印長度比任何一個部位的長、寬度都長這一特點，用智能化算法找到距離最長的兩輪廓點，記錄這兩點的坐標，并將這兩點的距離作為鞋長，根據這兩點算出方位角α，將鞋印圖像進行傾斜校正，便于后面幾何形狀特征的自動提取。

b)提出一種鞋印輪廓特征的提取算法，該算法不僅考慮鞋印鞋長、掌寬、弓寬、跟寬，還考慮掌寬處、弓寬處、跟寬處相對整個鞋的偏移位置。

參考文獻：

[1]ALEXANDRE G. Computer classification of the shoeprint of burglar soles [J]. Forensic Science International， 1996， 82: 59-65.

[2]SAWYER N. SHOE-FIT: a computerized shoe print database[C]//Proc of European Convention on Security and Detection. London: [s.n.]，1995.

[3]ASHLEY W. The use of computerized image database to assist in identification[J].Forensic Science International， 1996， 82: 67-79.

[4]GERADTS Z， KEIJZER J. The image data REBEZO for shoeprint with developments for automatic classification of shoe outsole designs [J]. Forensic Science International， 1996， 82:21-31.

[5]SU H，BOURIDANE A， CROOKES D. Image quality measures for hie-rarchical decomposition of a shoeprint image [J].Forensic Science International， 2006， 163 :125-131.

[6]吳志軍.鞋底花紋比對與分析系統的設計與實現[D]. 大連:大連海事大學，2004.

[7]王福生.基于紋理與形狀特性的鞋底花紋自動識別算法的研究[D]. 大連:大連海事大學，2006.

[8]柯少卿.鞋印分塊分類的研究[D]. 大連:大連海事大學，2006.

[9]劉健康.足跡圖像處理方法研究[D]. 大連:大連海事大學，2006.

[10]吳謹，李娟，劉成云，等.基于最大熵的灰度閾值選取方法[J]. 武漢科技大學學報：自然科學版，2004，27（1）:58-60.

[11]高樹輝，王新淮.現場鞋印檔案管理及計算機輔助檢索系統研究[J].公安大學學報：自然科學版，2003（2）:69-74.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文