田軍委，王 沁，趙 鵬,王崗罡

(1.西安工業(yè)大學 機電工程學院，陜西 西安 710032；2.中國人民解放軍駐211廠軍事代表室，北京100076)

引言

在特定邊界檢測中，邊界跟蹤是常用的一種方法，而邊界跟蹤中較多采用“爬蟲”跟蹤算法[1-3]。由于這類算法要跟蹤完所有的輪廓邊界點，而且，邊界跟蹤僅利用圖像局部信息，沒有利用全局信息作為先驗知識，造成信息浪費和跟蹤效率較低。目前又出現(xiàn)了一種抽取邊界點的邊界跟蹤算法，這種算法從反映邊界信息的角度出發(fā)，檢測部分邊界點，實現(xiàn)特定輪廓跟蹤。這種方法檢測效率高、穩(wěn)定性好，但由于采用等步長采樣，往往檢測不到角點，并且在角點附近存在大量信息丟失現(xiàn)象，因此必須采用角點檢測算法檢測出角點，保證邊界跟蹤的正確性和準確性。

角點是圖像輪廓發(fā)生突變的點，反映了物體輪廓特征，有時又稱為特征點，是模式識別和圖像處理中要處理的最小化數(shù)據(jù)。由于角點在數(shù)字圖像處理中的重要作用，研究人員提出了各種角點檢測算法，如Cooper等人利用鏈碼處像素坐標估計最大曲率值來尋找角點[4]。Ponce和Brady利用圖像I(x,y)對x、y的偏導數(shù)來尋找角點[5]。Hsin-Teng和Hu則使用多邊形近似邊界鏈，然后把兩邊的交點作為角點[6]。Kitchen和Rosenfeld[7]采用目標邊緣梯度方向的曲率變化率來檢測角點。Zuniga和Haralick[8]采用最小二乘法用三次多項式曲面擬合數(shù)字圖像，先檢測出邊界點，然后計算該點的梯度方向角在梯度方向的變化率，大于某閥值時，則認為該邊界點是角點。Wang和Brady[9]先利用高斯濾波器卷積原始圖像，然后計算圖像的表面曲率，最后通過閾值技術來檢測角點。Medioni和Yasumoto[10]利用B-樣條擬合邊界的方法來檢測角點，把計算得到的曲率最大值的點檢測為角點。Beaudet[11]通過對圖像函數(shù)二階導數(shù)的泰勒展開，得到Hessian矩陣H(x,y)，該矩陣具有旋轉不變性，可以直接對灰度圖像進行操作提取角點。Smith等人[12]提出了一種低層次圖像處理小核值相似區(qū)的方法(簡稱SUSAN算法)。Trajkovic等人[13]在角點響應函數(shù)(CRF)的基礎上提出一種新的角點檢測算法。Noble[14]提出了一種數(shù)學形態(tài)學的角點檢測方法，利用形態(tài)運算A-AoB來檢測凸型角點，利用AgB-A來檢測凹型角點。Robert[15]提出了使用非對稱閉運算來檢測角點。

這些算法都能夠成功檢測到角點，但是，對于固定步長邊界跟蹤算法，這些角點檢測算法或者不適定，或者計算效率低。為了在固定步長邊界跟蹤中快速、正確地檢測到角點，本文提出了尋區(qū)間角點檢測算法。

1 特定邊界跟蹤

特定邊界跟蹤[16]思想是：根據(jù)待檢測邊界的連續(xù)性和對該邊界的先驗知識，以歐氏距離為度量，搜索過程分為邊界點預估計和邊界點搜索兩步。

1.1 邊界點預估計

Δki-2=ki-1-ki-2∈[Δkmin,Δkmax]

(1)

Δki-1=ki-ki-1∈[Δkmin,Δkmax]

(2)

式中：ki為vi和vi+1連線的斜率。

(3)

(4)

邊界點預估計原理如圖1所示。

圖1 邊界點預估計原理Fig.1 Principle of boundary points estimation

1.2 邊界點搜索

(5)

2個搜索方向為

(6)

圖2 邊界點雙向搜索原理Fig.2 Principle of boundary points bidirectional searching

雙向鄰域擴展中，其中一個搜索方向是冗余的，為了進一步提高搜索效率，可采用準雙向鄰域擴展搜索算法，優(yōu)先搜索方向可以利用邊界在該范圍的凹凸性來判別。

(7)

根據(jù)函數(shù)凹凸性判別準則，如果

yi>K(yi-1+yi)

(8)

成立，則該區(qū)間內待檢測邊界是上凸的，如果

yi

(9)

成立，則邊界在該區(qū)間是上凹的，定義vi+1可能存在的方向為邊界在該處凹陷的一側。

2 角點存在判別

由于待檢測邊界上往往存在角點，要完成跟蹤并得到正確的檢測結果，必須正確檢測出角點并給出合理的種子點以完成后續(xù)邊界跟蹤。

設vi是邊界y=C(x)上的一個角點，則在vi處y=C(x)的左右導數(shù)不相等。

(10)

在實際邊界跟蹤中一般無法確知y=C(x)的解析式，需要用判別算法識別輪廓角點。

(11)

當vi和vi+1之間存在角點時，角點兩側的一階導數(shù)出現(xiàn)跳變。實際搜索情況如圖3所示。對兩種人工圖像進行實驗，結果如圖4所示。

圖3 角點附近邊界跟蹤情況Fig.3 Boundary tracking near corner point

圖變化情況實驗Fig.4 Examination for trends

(12)

如果角點存在，角點va所處的區(qū)間為va∈[vi,vi+1]。

3 角點檢測

設vi為角點，邊界y=C(x)在y處左右導數(shù)為

(13)

(14)

式中，δ>0。設vi-1和vi+1分別為角點vi兩側的邊界點，用直線vi-1vi和vivi+1的斜率近似y=C(x)在vi處的左右一階導數(shù)，則有：

(15)

(16)

如果vi不是角點，根據(jù)(1)式和(2)式的結論，有Δki-1=ki-ki-1∈[Δkmin,Δkmax]；如果vi是角點，由于y=C(x)的一階導數(shù)在vi處發(fā)生跳變，有如下關系：

Δki-1<Δkmin或Δki-1>Δkmax

(17)

對Δkmin和Δkmax進行歸一化處理，(17)式就可以寫成：

|Δki-1|>ΔkthΔkth=max{|Δkmin|,|Δkmax|}

(18)

這樣，利用三點之間連線斜率關系可以檢測出角點。這種方法稱為尋點法，但在搜索過程中，如果采用逐點搜索，Δk是一個漸變量(由邊界的連續(xù)性可知)，滿足(18)式的點往往有許多，其中|Δk|最大者才是真正的角點，用這種方法搜索角點時，必須進行二次判斷。為了快速準確地找到角點，我們提出了一種尋區(qū)間法。

設vi-2、vi-1、vi、vi+1和vi+2均為待檢測邊界上的點，且角點兩側至少有2個邊界點，定義：

Δkp=|Δki+1-Δki-2|

(19)

容易證明，如果Δkp>Δkth，那么角點必在vi的某一鄰域內，當區(qū)間vi足夠小，且搜索步長選擇合理(大于像素本身產生的微觀角點)，第一次滿足(18)式的點vi就是角點。這種方法用尋找區(qū)間來代替尋找某個點，從而易于判別，且效率大大提高。

4 實驗及分析

對本文所提出的角點檢測方法，用不同的圖像進行檢測，圖5是對測試圖像1進行跟蹤的結果，圖6是對人臉側面圖像嘴巴附近圖像進行處理的結果。

由實驗結果可以看出，當沒有對所檢測輪廓角點進行判斷和檢測時，邊界跟蹤所得到的邊界點就會在角點附近出現(xiàn)大段缺失，因而丟失了許多有用的邊界信息。由圖5(a)和圖6(a)的跟蹤結果還可以看出，邊界跟蹤丟失的信息和角點附近輪廓邊界變化情況有關，當角點附近輪廓邊界變化劇烈，兩邊邊界夾角小，邊界點缺失距離就大，丟失的邊界信息也多，圖6(a)所丟失的邊界信息就明顯地多于圖5(a)。當在邊界跟蹤過程中加入邊界點判別和檢測處理，邊界跟蹤中就能夠越過邊界點，正確進行后續(xù)邊界跟蹤，不丟失后續(xù)輪廓的信息。圖5(b)和圖6(b)的結果表明，兩種方法得到邊界點數(shù)量分別為19、37和13、21，在邊界跟蹤過程中本文所提出的算法均能夠正確判斷出角點位置檢測到該角點，然后植入有效的種子邊界點，使后續(xù)跟蹤能夠完整跟蹤完后續(xù)邊界。由于所檢測的邊界點反映了待檢測輪廓的所有信息，因此在后續(xù)建模中才有可能建立正確的輪廓模型。

圖5 測試圖像1實驗結果比較Fig.5 Experiment comparison of test image 1

圖6 人臉嘴巴附近圖像實驗結果比較Fig.6 Experiment comparison of side face image

5 結論

實驗結果表明：

1) 本文所提出的特定輪廓邊界角點判別準則在不增加計算量的情況下能夠準確判斷出角點所在的區(qū)間；

2) 在判斷出的角點所在的區(qū)間內，采用尋區(qū)間檢測算法能夠快速準確檢測出角點，并從角點開始給出正確的種子，為后續(xù)邊界跟蹤提供正確的初始條件；

3) 采用角點判別和檢測方法的邊界跟蹤算法能夠檢測到正確的輪廓邊界，且不丟失輪廓變化的重要信息；

4) 由實驗結果可以看出，角點附近所檢測到的邊界點比較密集，和邊界的變化情況關系不密切，存在冗余邊界點，有待提出有效的約束，去除冗余邊界點。

[1] Sobel L. Neighborhood coding of binary images for fast contour following and general binary array processing[J]. Computer Graphics Image Process, 1978, 8(1):127-135.

[2] Liow Y T. A contour tracking algorithm that preserves common boundaries between regions[J]. CVGIP-Image Understanding, 1991,53(3): 313-321.

[3] Wang Yu, Lu Yanpin, Zhang Zehong, et al. A reptile method with memory and alterable window for image boundary tracing[J]. Chinese Journal of Scientific Instrument, 2004, 25(4):383-491.

王玨, 盧艷平, 張澤宏,等. 一種有記憶的變窗“爬蟲”圖像邊界跟蹤方法[J]. 儀器儀表學報,2004 ,25(4):483-491.

[4] Cooper J, Sveth A, Kitechen L. Early jump-out corner detectors[J]. IEEE Transactions on PAMI, 1993(15):823-828.

[5] Ponce J, Brady M. Towards a surface primal sketch[C]. St.Louis, MOUSA： In: IEEE International Conference on Robotics and Automation, 1985:420-425.

[6] Hsin Teng, Hu W C. A rotationally invariant two-phase scheme for corner detection[J]. Pattern Recognition, 1996,28(5):819-829.

[7] Kitchen L, Rosenfeld A K. Gray-level corner detection[J]. Pattern Recognition Letters, 1982,3(1):95-102.

[8] Zuniga O A, Haralick R. Corner detection using the facet model[C]. Washington D.C.： IEEE VCPR, 1983:30-37.

[9] Wang H, Brady M. Real-time corner detection algorithm for motion estimation[J]. Image and Vision Computing,1995,13(9):695-703.

[10] Medioni G, Yasumoto Y. Corner detection and curve representation using cubic B-spline[J]. Compute Vision, Graphics, Image Process, 1987,39(3):267-278.

[11] Beaudet P R. Ratationally invariant image operators [C]. Kyoto, Japan：Internat. Joint Conf. on Pattern Recognition, 1978:579-583.

[12] Smith S M, Brady J M. SUSAN-a new approach to low level image processing[J]. Journal of Computer Vision, 1997,23(1):45-78.

[13] Trajkovic M, Hedley M. Fast corner detection[J]. Image and Vision Computing, 1998,16(1):75-87.

[14] Noble J A. Image as functions and sets[J]. Image and Vision Computing, 1992,10(1):19-29.

[15] Robert L. A morphological operator for corner detection[J]. Pattern Recognition, 1998,31(11):1643-1652.

[16] Tian Junwei, Huang Yongxuan, Pan Wanying. Adaptive step-size fast interested boundary tracking[J]. IEEE, 2007(5-8):2395-2398.

[17] Yoon J S, Park J C, Jang S W, et al. A shakable snake for estimation for image contours[J]. ICCSA, LNCS,2004, 3043: 9-16.