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

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

引言

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

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

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

1 特定邊界跟蹤

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

1.1 邊界點(diǎn)預(yù)估計(jì)

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

(1)

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

(2)

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

(3)

(4)

邊界點(diǎn)預(yù)估計(jì)原理如圖1所示。

圖1 邊界點(diǎn)預(yù)估計(jì)原理Fig.1 Principle of boundary points estimation

1.2 邊界點(diǎn)搜索

(5)

2個(gè)搜索方向?yàn)?/p>

(6)

圖2 邊界點(diǎn)雙向搜索原理Fig.2 Principle of boundary points bidirectional searching

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

(7)

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

yi>K(yi-1+yi)

(8)

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

yi

(9)

成立，則邊界在該區(qū)間是上凹的，定義vi+1可能存在的方向?yàn)檫吔缭谠撎幇枷莸囊粋?cè)。

2 角點(diǎn)存在判別

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

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

(10)

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

(11)

當(dāng)vi和vi+1之間存在角點(diǎn)時(shí)，角點(diǎn)兩側(cè)的一階導(dǎo)數(shù)出現(xiàn)跳變。實(shí)際搜索情況如圖3所示。對(duì)兩種人工圖像進(jìn)行實(shí)驗(yàn)，結(jié)果如圖4所示。

圖3 角點(diǎn)附近邊界跟蹤情況Fig.3 Boundary tracking near corner point

圖變化情況實(shí)驗(yàn)Fig.4 Examination for trends

(12)

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

3 角點(diǎn)檢測

設(shè)vi為角點(diǎn)，邊界y=C(x)在y處左右導(dǎo)數(shù)為

(13)

(14)

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

(15)

(16)

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

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

(17)

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

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

(18)

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

設(shè)vi-2、vi-1、vi、vi+1和vi+2均為待檢測邊界上的點(diǎn)，且角點(diǎn)兩側(cè)至少有2個(gè)邊界點(diǎn)，定義：

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

(19)

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

4 實(shí)驗(yàn)及分析

對(duì)本文所提出的角點(diǎn)檢測方法，用不同的圖像進(jìn)行檢測，圖5是對(duì)測試圖像1進(jìn)行跟蹤的結(jié)果，圖6是對(duì)人臉側(cè)面圖像嘴巴附近圖像進(jìn)行處理的結(jié)果。

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

圖5 測試圖像1實(shí)驗(yàn)結(jié)果比較Fig.5 Experiment comparison of test image 1

圖6 人臉嘴巴附近圖像實(shí)驗(yàn)結(jié)果比較Fig.6 Experiment comparison of side face image

5 結(jié)論

實(shí)驗(yàn)結(jié)果表明：

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

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

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

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

[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]. 儀器儀表學(xué)報(bào),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.