對一種快速邊緣跟蹤算法的討論

1、第 21 卷 第 6 期2000 年 6 月小 型 微 型 計 算 機(jī) 系 統(tǒng)m in i- m icro syst emv o l121 n o 16j uen 2000文 章 編 號: 100021220 (2000) 0620641205對一種快速邊緣跟蹤算法的討論史冊( 浙江大學(xué)信息與電子工程學(xué)系 杭州 310027)摘 要: 本文首先介紹了一種快速邊緣跟蹤算法的原理, 然后針對如何提高該算法的處理速度所涉及的問題進(jìn)行了深入的討論.關(guān) 鍵 詞:分 類 號:計算機(jī)視覺; 實時圖象處理; 鏈碼; 邊緣跟蹤文獻(xiàn)標(biāo)識碼: at p 391物體的邊緣信息在計算機(jī)視覺中占有重要地位, 它在圖象分割

2、、景物識別、圖象理解等領(lǐng)域中起著關(guān)鍵作用. 因此, 邊 緣提取在視覺信息處理中是一個必不可少的環(huán)節(jié). 對數(shù)字圖 象而言, 邊緣由滿足一定條件的像素 (稱為邊界點) 構(gòu)成, 獲得邊界點的方法有多種, 如直方圖2閾值法, 過零點檢測等, 但僅 僅獲得邊界點是不夠的, 必須通過邊緣跟蹤將它們從圖象信 息轉(zhuǎn)換為符號信息, 才有利于后續(xù)處理的使用. 邊緣跟蹤的結(jié)果通常是鏈碼表示, 在此的基礎(chǔ)上, 可以方便、快速地提取出角點1、直線2等多種重要信息.本文主要討論如何在已獲得邊界點的二值圖基礎(chǔ)上, 以 盡可能快的速度獲得邊緣的鏈碼表示. 作者先向讀者介紹一 種比較好的邊緣跟蹤算法的思想, 然后對涉及到該算法

3、執(zhí)行 速度的若干問題進(jìn)行深入的討論.沿 元 的 值 非 零. 根 據(jù) 考 察 點 是 目 標(biāo) 點 還 是 背 景 點 分 別 取 正( po sit iv ity, 記為 p ) 或負(fù) (n ega t iv ity, 記為 n ). 參見圖 1 和圖2 中的 (c)、(d).跟蹤方向規(guī)定如下: 目標(biāo)點始終在前進(jìn)方向的左邊. 如各 圖中箭頭所示. 對于一個連通區(qū)域的外邊界, 跟蹤方向為逆時 針方向; 而內(nèi)邊界 (內(nèi)部孔洞所形成的邊界) 則為順時針方向. 當(dāng)在封閉鏈碼基礎(chǔ)上求面積時, 外邊界鏈碼所圍成的區(qū)域面 積為正, 而內(nèi)邊界鏈碼所圍成區(qū)域面積為負(fù), 從而在計算機(jī)視 覺的高層推理中很容易把內(nèi)、

4、外邊界區(qū)分開.顯然, 邊沿元的取值同時也表明了相應(yīng)的跟蹤方向, 因此以下用邊沿元的方向來表明相應(yīng)的跟蹤方向. 如說某個邊沿 元方向為正, 對水平邊沿元而言, 跟蹤方向向右; 對垂直邊沿 元而言, 跟蹤方向向上.跟蹤過程中的標(biāo)記打在當(dāng)前邊沿元的目標(biāo)點上 (參見圖1、2 中帶 陰 影 的 目 標(biāo) 點) , 以 區(qū) 分 該 邊 界 點 是 否 已 經(jīng) 被 跟 蹤 過.1. 2 邊沿元的記法:用 h 或 v 表示邊沿元的類型 (水平還是垂直) , 后跟當(dāng)前 考察點的坐標(biāo), 等號右邊表明對邊沿元的值. 如:“v ij=n ”即表示: 在考察點為ij和參考點為ij+ 1之間的邊 沿元類型為 v 、值為 n

5、 (即跟蹤方向向下的垂直邊沿元). 為方便讀者, 各邊沿元的記法同時標(biāo)在圖 1、2 中.1算法的思想邊緣跟蹤算法主要包括掃描過程和跟蹤過程, 不同算法的差異主要體現(xiàn)在跟蹤過程中, 尤其是如何根據(jù)當(dāng)前的情況 判斷下一步的跟蹤方向, 這是算法的核心. 這一部分就主要討 論這個核心問題.本文采用 t. p av lid is 3對鏈碼及方向的定義, 并以2 表示二值圖中的背景點, 以+ 表示二值圖中的目標(biāo)點.1. 1 邊沿元的定義本文假設(shè)邊界存在于像素之間, 由邊沿元構(gòu)成, 分為水平(h o r izo n ta l, 記為 h ) 和垂直 (v e r t ica l, 記為 v ) 兩種. 參見

6、圖2、3 中的 (a)、(b ).設(shè)當(dāng)前考察點坐標(biāo)為ij, 判斷是否存在水平邊沿元以i+ 1j為參考點, 判斷是否存在垂直邊沿元以ij+ 1為 參考點.當(dāng)考察點與參考點的值相同時, 這兩個點之間沒有邊界 通過, 邊沿元的值為零. 根據(jù)它們都是目標(biāo)點還是背景點分為正 零 ( po sit ive ze ro , 記 為 p z ) 和 負(fù) 零 (n ega t ive ze ro , 記 為n z) 兩種.當(dāng)考察點與參考點的值相異時, 兩點之間有邊界通過, 邊圖 1 水平邊沿元 h圖 2 垂直邊沿元 v1. 3 后繼邊沿元的確定收稿日期: 1999204221 作者簡介: 史冊, 博士. 主要研

7、究方向為圖像處理、計算機(jī)視覺、人工智能.前面說過, 邊緣跟蹤算法的核心在于如何判定下一步的跟蹤方向. 這個判定方法非常重要, 它在很大程度上決定了算 法效率的高低. 下面首先討論另外兩種算法中判定方法的優(yōu) 缺點, 并與本文的判定方法做對比, 然后再詳細(xì)闡述本文的判定方法.文獻(xiàn)4中的判定方法采用了查找表的方法. 取 22 大 小的觀察窗口, 窗口中不同的位置賦予不同的權(quán)值. 跟蹤時,以該窗口模板對圖象中相應(yīng)象素的加權(quán)和作為索引, 查找事先造好的查找表 ( 相當(dāng)于本文的圖 3 6) 就可得到下一步的 跟蹤方向.這樣做的好處是比較快 ( 對同一幅圖, 4中的算法僅比 本文的算法慢 10% 左右) ;

8、 缺點是:( 1) 查找表中有重復(fù). 例如, 圖 3 (d ) 與圖 4 (d ) 將具有相 同的索引值, 必須再參照當(dāng)前的跟蹤方向 (4中稱為“上一步跟蹤方向”) 才能區(qū)別.(2) 窗口中 各 點 的 取 值 已 足 以 判 斷 出 下 一 步 的 跟 蹤 方 向, 因此沒有必要計算加權(quán)和.作者采用了4中的窗口思想, 但與4的不同之處在于:4以窗口的類型為出發(fā)點, 在必要時才判斷當(dāng)前的跟蹤方 向; 而作者則以當(dāng)前邊沿元的類型及方向為基礎(chǔ), 輔以窗口其 它的點的取值情況.與4相比, 文獻(xiàn)5中的方法與本文更加接近. 它類似地 定義了水平邊界、垂直邊界及其方向. 但它首先要計算出所有像素的水平邊界

9、值和垂直邊界值 ( 分為 0, 1 和- 1 三種) , 在 此基礎(chǔ)上再根據(jù)每個像素的這兩個邊界值確定下一步的跟蹤方向.5中利用像素的邊界值來確定下一步跟蹤方向的思想 非常巧妙, 但有以下兩個不足之處:(1) 沒有進(jìn)一步區(qū)分兩種不存在邊界的情況. 這樣, 對于 邊界值為 0 的像素, 在跟蹤時還要判定是同為目標(biāo)點還是同 為背景點;( 2) 實驗表明 ( 參見討論四) , 對各像素的邊界值的計算 是完全可以省略的.本文的判定方法與4、5相比, 有其長而無其短. 簡略 來說, 其主要思想就是: 當(dāng)當(dāng)前考察點與參考點之間存在非零邊 沿元時 (圖 1 2 中的 (c)、(d) ) , 根據(jù)這兩點所構(gòu)成

10、的 22窗口中其余兩點的情況, 來決定下一步的跟蹤方向 (以下稱為 后繼邊沿元).圖 3 6 給出了所有以ij為當(dāng)前考察點并在已知當(dāng)前 邊沿元的類型及方向的情況下, 所有可能的后繼邊沿元的類型及方向. 其中, 帶陰影的目標(biāo)點是當(dāng)前邊沿元的標(biāo)記點.的兩個像素ij+ 1和i+ 1j+ 1的取值有四種組合 ( 圖 4( a ) (d ) ) , 每一種組合都確定了唯一的后繼邊沿元 ( 在各圖 中標(biāo)明). 容易證明: 對于圖 3 6 中的任何一種情況, 其后繼邊沿元都是唯一的.圖 4h ij= n 時的后繼邊沿元圖 5v ij= p 時的后繼邊沿元圖 6v ij= n 時的后繼邊沿元1. 4 邊緣跟蹤

11、算法如果用 succ 表示后繼邊沿元的類型及方向, 跟蹤過程主 要處理如下:w h ile ( 沒有返回到起點, 即跟蹤過程沒有結(jié)束) if (h ij= = p )if (h ij+ 1= = p z)if (h ij+ 1= = n z)if (h ij+ 1= = p )if (h ij+ 1= = n )if (h ij= = n )if (h ij21= = p z)if (h ij21= = n z)if (h ij21= = p )if (h ij21= = n )if (v ij= = p )if (v i21j= = p z)if (v i21j= = n z)if (v i

12、21j= = p )if (h i21j= = n )if (v ij= = n )if (v i+ 1j= = p z)if (v i+ 1j= = n z)if (v i+ 1j= = p )if (v i+ 1j= = n )succ: v i+ 1j= nsucc: v ij= psucc: h ij+ 1= psucc: v i+ 1j= nsucc: v ij21= psucc: v i+ 1j21= n succ: v ij21= psucc: h ij21= nsucc: h i21j+ 1= psucc: h i21j= nsucc: v i21j= psucc: h i21

13、j+ 1= psucc: h ij= nsucc: h ij+ 1= psucc: h ij= nsucc: v i+ 1j= n2算法的實現(xiàn)圖 3 h ij= p 時的后繼邊沿元例如, 對于圖 3, 當(dāng)前邊沿元為“h ij= p ”, 窗口右邊作者主要研究計算機(jī)視覺中的實時 ( 指 25 幀秒的電視頻率) 問題, 因此對一個算法的處理時間特別在意. 在考察上6 期史 冊 等: 對一種快速邊緣跟蹤算法的討論643述算法的處理速度時, 作者發(fā)現(xiàn)了一些有趣的結(jié)論. 下面以討論的形式給出, 供有興趣的讀者參考.點掃描, 無孤立邊界點) 的結(jié)果參見圖 10- 12.討論一: 4 方向還是 8 方向?根

14、據(jù)文獻(xiàn)3的定義, 鏈碼又可細(xì)分為 8 方向鏈碼和 4 方 向 鏈碼兩種, 對于圖 3 6 中 (a) (c) 的情況, 無論采用哪種 表 示, 后繼邊沿元都是相同的. 但對于圖 3 6 中的 (d) , 采用 不 同的表示, 就有不同的后續(xù)邊沿元. 如圖 3 (d) , 如果采用 4 方 向鏈碼, 后繼邊沿元就改為“v ij= p ”. 但無論采用哪 種鏈碼, 圖 3 6 中任何一種情況的后繼邊沿元都是唯一的.圖 7bl o c k 原圖圖 10 bl o c k 邊界跟蹤結(jié)果圖圖 8 g irl 原圖圖 11 g irl 邊界跟蹤結(jié)果圖圖 9 br id ge 原圖作者挑選了三副具有代表性的

15、圖象 ( 2562568b it, 參 見圖 7- 9) 作為實驗對象. 第一副原始圖象為自然光下的簡 單人造物體圖象 ( 記為 b lo ck , 多用于景物分析) , 分割后圖中 有內(nèi)外兩條邊緣; 第二副原始圖象為自然光下的較復(fù)雜的人 物肖像 (記為 g ir l, 多用于圖象編碼) ; 第三副原始圖象為多光 譜下較復(fù)雜的自然景物圖象 (記為 b r idge, 多用于目標(biāo)識別). 限于篇幅, 略去了這三幅圖象的二值化圖象, 其邊緣跟蹤 (逐圖 12 br id ge 邊界跟蹤結(jié)果圖一般認(rèn)為 8 方向鏈碼的結(jié)果比較精確, 而 4 方向鏈碼的速度比較快. 但實際上這兩者是差不多的. 這是因為

16、為了保證對于只有一個像素寬的斜線的正確跟蹤, 必須修改 4 方向鏈 碼的跟蹤方式, 否則, 跟蹤結(jié)果將是一個個孤立的邊界點 (多數(shù) 情況下被丟棄) 而不是一個線段. 修改后, 4 方向鏈碼與 8方向鏈碼相差不多. 因此, 本文中提到的鏈碼, 除明確說明外,均指 8 方向鏈碼.討論二: 圖象的表示對于圖象的表示, 有一維數(shù)組和二維數(shù)組兩種表示. 從表 面上看, 一維數(shù)組會比二維數(shù)組要快一些. 因為在移動指針 時, 前者只需做加減法, 而后者必須做乘法. 但實踐表明, 因采 用不同的表示而造成的速度差別并不象人們所想象的那么進(jìn)一步的實驗表明, 做一次判斷所花費的時間很少: 106次判定的時間開銷為

17、 25 拍. 就拿最壞情況下每一步都要重復(fù)4 次判斷來說, 對 于 邊 界 點 數(shù) 目 最 多 的 圖 象 b r idge, 將 多 出98283 4 次判斷, 算下來處理時間將相差 1 拍, 與表 4 正好相 符. 而且, 處理器速越高, 這種差別就更小. 這表明, 在本算法中使用 go to 語句所帶來的好處并不大.另外, 在本算法中, 使用 go to 語句對程序結(jié)構(gòu)、可讀性及 維護(hù)等方面帶來的影響也很小, 因此, 是否使用 go to 語句來避免重復(fù)判斷, 要根據(jù)具體應(yīng)用的環(huán)境來決定. 在實時系統(tǒng)中, 相差的這一拍也許就是任務(wù)分配的關(guān)鍵數(shù)據(jù).討論四: 各像素邊界值的計算可以省略前文說

18、過, 文獻(xiàn)5要對各像素計算水平邊界值和垂直邊 界值. 這一步實際上是可以省略的. 因為這兩個值一次性的, 僅供跟蹤時使用, 而且在跟蹤過程中完全可以根據(jù)其原理邊 判斷, 邊跟蹤, 沒必要單獨掃描整個圖象做計算. 為此, 作者做 了對比實驗, 結(jié)果如表 3 所示.表 3 是否計算各像素邊界值的速度差異多. 因為開發(fā)系統(tǒng) (如 bc 3. 1, bc + +5. 0 等) 一般都對二維數(shù)組的引用做了優(yōu)化處理, 因此, 二維數(shù)組與一維數(shù)組在引用上的速度差別大約是: 107 次相差 4 拍1. 對于一副 256256大小的圖象而言, 相差不到 1 拍.受操作系統(tǒng) do s 的限制, 超過 64k (

19、16 b y te 大小的數(shù)據(jù) 塊必須使用 h uge 指針, 才能保證數(shù)據(jù)的正確引用. 而 h uge 指 針受尋址方式的影響, 處理速度會急劇降低 (參見表 1).表 1 h uge 指針與非 h uge 指針的速度差異從表 3 可以得到下面兩個結(jié)論:結(jié)論 1: 無論二值圖的復(fù)雜程度 (邊界點數(shù)目) 如何, 計算各像 素的邊界值所花費的時間基本上是固定的, 即計算時間與圖 象的復(fù)雜度無關(guān).結(jié)論 2: 對同一幅圖象, 在其它條件相同時, 省略該步驟可以 極大地加快處理速度.討論五: 掃描方式一般的邊緣跟蹤算法采用逐點掃描的方式尋找新的尚未 跟蹤過的邊界點, 與處理圖象的最終目的無關(guān). 但在計

20、算機(jī)視 覺中, 因為信息量非常大, 而且具有很強(qiáng)的不確定性, 因此必 須結(jié)合最終目的盡早對處理加以引導(dǎo), 防止信息量的過度增 長. 通常情況下, 只在一個特定的范圍內(nèi) (大小與感興趣對象 的大小有關(guān)) 而不是整個圖象進(jìn)行處理.為此, 作者采用網(wǎng)格掃描的掃描方式, 對選定的三副圖象 做對比實驗, 結(jié)果如表 4 所示, 網(wǎng)格的大小根據(jù)感興趣的目標(biāo)大小而定.表 4 逐行掃描與網(wǎng)格掃描的速度差異當(dāng)在 32 位操作系統(tǒng) (如w in dow s 95) 或?qū)Ｓ锰幚硇酒h(huán)境下, 就不存在此問題, 圖象可以是任意大小. 考慮到程序的可 讀性, 應(yīng)盡量采用二維數(shù)組. 為避免 h uge 指針帶來的影響, 可采

21、用宏定義, 使圖象的表示具有二維的形式, 一維的實質(zhì). 作者正是如此處理的.討論三: 是否使用 go to 語句避免重復(fù)判斷.仔細(xì)研究前一部分給出的程序段就會發(fā)現(xiàn)其中存在著大 量的重復(fù)判斷.假設(shè)當(dāng)前第 k 步及下一步第 k + 1 步的邊沿元類型及方 向如圖 3 (a) 所示, 如果利用 go to 語句就可直接轉(zhuǎn)到圖 6 對其 余兩個像素 (i+ 1j與i+ 1j+ 1) 進(jìn)行判斷, 得到第 k +2 步的跟蹤方向; 否則, 就必須再判斷圖 3 (a ) 中的i+ 1j與i+ 1j+ 1兩個像素的類型 (第 k + 1 步的邊沿元的方向及 類型) 后, 才能到達(dá)圖 6. 而這兩個判斷其實在第

22、 k 步時已經(jīng)作過了, 即重復(fù)判斷.這樣的重復(fù)判斷在跟蹤過程中的每一步至少有 2 次, 最 多時有 4 次. 仔細(xì)觀察圖 3 6 就可知道, 圖中 h 邊沿元與 v 邊沿元之間的轉(zhuǎn)換占 34, 因此這種重復(fù)判斷的數(shù)量是很高 的. 但出人意料的是, 實驗表明, 這種重復(fù)并沒有占多少時間(參見表 2).表 2 使用與不使用 go to 語句的速度差異對圖象做網(wǎng)格掃描, 只有與網(wǎng)格線相交的區(qū)域才有可能被跟蹤, 那些完全落在網(wǎng)格內(nèi)的區(qū)域則被忽略. 因此, 本次實 驗中邊界點的數(shù)目有所減少. 表 4 表明, 采用網(wǎng)格掃描也可以極大地提高處理速度.1t ick , 1 s= 18. 2 t ick , 下

23、同. 實驗環(huán)境為 ibm 386 (do s). 之所以選擇這樣的實驗環(huán)境是為了便于向并行處理平臺移植.圖象跟蹤時間 (w itho u t go to )跟蹤時間 (w ith go to )邊界點數(shù)目b lo ck44986g ir l665121b r idge989828圖象跟蹤時間 (逐行掃描)跟蹤時間 (1616 網(wǎng)格掃描)邊界點數(shù)目b lo ck40. 6964g ir l61. 64251b r idge92. 87228圖象跟蹤時間跟蹤時間 (h uge)邊界點數(shù)目b lo ck420986g ir l6215121b r idge9329828圖象計算各像素的邊界值不計算各

24、像素的邊界值邊界點數(shù)目計算時間跟蹤時間總計跟蹤時間b lo ck64104986g ir l661265121b r idge6915998286 期史 冊 等: 對一種快速邊緣跟蹤算法的討論645另外, 還可以根據(jù)感興趣的目標(biāo)大小預(yù)先確定一個長度閾值, 對獲得的鏈碼進(jìn)行選擇: 只有長度大于該閾值的鏈碼才 予以保留. 雖然此步對邊緣跟蹤算法本身的處理速度沒有多大影響, 但它可以減少后續(xù)處理的數(shù)據(jù)量, 從而達(dá)到提高整個系統(tǒng)處理速度的目的.度來說, 處理速度的提升空間已經(jīng)很有限. 欲滿足實時處理系統(tǒng) 的要求, 最好的方法就是采用并行處理的環(huán)境和方法 ( 例 如: 將圖象分塊, 分布到多個處理器上同時進(jìn)行跟蹤, 然后再合并跨分塊的邊界). 關(guān)于并行處理環(huán)境下, 邊緣跟蹤的快速算法問題, 另有專文進(jìn)行論述, 本文就不再討論.3結(jié)論參 考 文 獻(xiàn)本文介紹了一種較好的快速邊緣跟蹤算法的思想, 并對實現(xiàn)過程中遇到的幾個問題做了深入的探討.本文給出的算法處理速度已經(jīng)很快, 足以滿足一般情況 下的實際應(yīng)用. 但對于 25 幀秒的電視頻率而言, 一幀圖象的 處理時間只有 40m s, 這樣的處理速度還是太慢. 但在目前單 處理器的實驗環(huán)境下, 要想進(jìn)一步大幅度提高處理