一個(gè)抽取邊界曲線特征點(diǎn)的新算法

1、一個(gè)抽取邊界曲線特征點(diǎn)的新算法 3劉勇奎 , 劉向東 , 王春霞(大連民族學(xué)院 , 遼寧 大連 116600 )摘 要 : 景物的特征點(diǎn)抽取是模式識(shí)別及計(jì)算機(jī)視覺(jué)中的一個(gè)重要問(wèn)題 ,已出現(xiàn)的多種檢測(cè)特征點(diǎn)的方法中主要有角檢測(cè)法和多邊形逼近法 。在這兩種方法基礎(chǔ)之上 ,人們又提出了結(jié)合兩種方法的綜合方法 。提出了一種 新的綜合方法 ,首先應(yīng)用一個(gè)簡(jiǎn)單的角檢測(cè)方法 ,然后利用前面計(jì)算曲率時(shí)的一些值在檢測(cè)到的角點(diǎn)之間加入一些特征點(diǎn) 。實(shí)驗(yàn)結(jié)果表明新方法比傳統(tǒng)方法執(zhí)行速度更快 ,并且克服了傳統(tǒng)方法的缺陷 。關(guān)鍵詞 : 模式識(shí)別 ; 曲率 ; 特征點(diǎn) ; 角檢測(cè) ; 多邊形逼近文章編號(hào) : 100123

2、695 ( 2006) 06 20148 205中圖法分類號(hào) : tp391文獻(xiàn)標(biāo)識(shí)碼 : ao n d e tec tion of dom inan t po in ts on cu rve s of o b jec t con tou rl iu yong2ku i, l iu x iang2dong, wan g chun2xia(d a lian n a tiona lities u n iversity, d a lian l iaon ing 116600, c h ina)a b stra c t: d e tec ting dom inan t po in ts is an i

3、mpo rtan t sub jec t in p a tte rn recogn ition and comp u te r vision. co rne r de tec tion andpo lygona l app roxim a tion a re two m a jo r app roache s fo r dom inan t po in t de tec tion. b a sed on the two app roache s, com b ined m e2 thod s have been p ropo sed. in th is p ap e r, a new com

4、b ined m e thod is p re sen ted to de tec t the dom inan t po in ts. the new m e thod first app lie s a simp le co rne r de tec tion p rocedu re, then add s som e po in ts be tween de tec ted co rne r po in ts w ith the va lue of cu rva2 tu re comp u ta tion. exp e rim en ta l re su lts show tha t t

5、he new com b ined m e thod is mo re effic ien t than the conven tiona l m e thod s.a nd it ove rcom e s som e defec ts in the conven tiona l m e thod s.key word s: pa tte rn r ecogn ition; cu rva tu re; dom inan t po in ts; co rne r d e tec tion; po lygona l app roxim a tion之上 ,人們又提出了結(jié)合兩種方法的綜合方法 6,

6、7 。這種方法的一般步驟是 :先通過(guò)應(yīng)用角檢測(cè)方法得到曲線的角點(diǎn) ,這些 點(diǎn)已是曲線的特征點(diǎn) ,但不夠完全 ; 再使用多邊形逼近法在兩 個(gè)連續(xù)角點(diǎn)之間分割曲線 ;最后把這些檢測(cè)到的角點(diǎn)和分割點(diǎn) 作為曲線上的特征點(diǎn) 。本文將上述幾種方法相結(jié)合 ,給出一種計(jì)算量小 、執(zhí)行速 度快的綜合方法 ,并且克服了前面提到的傳統(tǒng)方法的缺陷 。1 引言景物的特征點(diǎn)抽取是模式識(shí)別及計(jì)算機(jī)視覺(jué)中的一個(gè)重要問(wèn)題 。如果要描述一個(gè)物體的形狀 ,檢測(cè)出物體邊界上的特 征點(diǎn)是必不可少的 。所謂特征點(diǎn)就是能夠代表邊界曲線特征 的一些點(diǎn) (如拐點(diǎn)等 ) ,并且從人的視覺(jué)角度考慮 ,這些特征點(diǎn) 能夠表達(dá)曲線上足夠的信息來(lái)描繪物體

7、輪廓的特征 。特征點(diǎn)的概念已經(jīng)應(yīng)用到輪廓識(shí)別算法 ,基于點(diǎn)的運(yùn)動(dòng)估計(jì)方法以及編碼方法中 ,我們把一個(gè)物 體輪廓的特征點(diǎn)作為它的 一種標(biāo) 志 。在這些應(yīng)用 中 ,特征點(diǎn) 檢測(cè)是非常重要的預(yù)處理 步驟 之一 。a ttneave有一個(gè)非常著名的結(jié)論 : 描述一條曲線形狀的信 息集中在具有高曲率的特征點(diǎn)上 1 。許多算法就是基于這個(gè)結(jié)論 。到目前為止 ,已出現(xiàn)了多種檢測(cè)特征點(diǎn)的方法 。主要可分為兩大類 ,即角檢測(cè)法 2, 3, 9 和多邊形 逼近法 4, 5, 8, 10 。角檢 測(cè)法的一般步驟是 : 逐點(diǎn)計(jì)算曲線上每一點(diǎn)的曲率 ; 找出 曲率較大的那些點(diǎn)作為特征點(diǎn) 。而多邊形逼近法則是從最初點(diǎn)開(kāi)始

8、 ,不斷向兩個(gè)最初點(diǎn)之間的曲線段中加入分割點(diǎn) ,直到滿足一定的條件為止 。加入分割點(diǎn)的原則是在允許的誤差條 件下使各段曲線盡量地長(zhǎng) 。最后曲線上的點(diǎn)就被定為是特征點(diǎn) 。由于這兩種方法有各自的缺陷 ,因此 ,在這兩種方法基礎(chǔ)2 特征點(diǎn)檢測(cè)方法研究現(xiàn)狀在角檢測(cè)算法中 ,首先介紹兩種簡(jiǎn)單的曲率估計(jì)方法 ,它們分別是由 ro senfe ld與 john ston和 teh與 ch in提出的 。在多 邊形逼近方法中 ,首先介紹分割曲線的連續(xù)逼近方法和迭代逼 近方法 。前者是由 w a ll和 d an ie lsson提出 ,而后者由 r am e r提 出 。然后 ,介紹一種由 w u和 w an

9、g提出的綜合方法 。在介紹算法之前 ,我們先對(duì)數(shù)字曲線進(jìn)行一下描述 ,使用n個(gè)整數(shù)坐標(biāo)序列 , 即c = p = ( x ,y , i = 1, 2, , n i )i i其中 , 點(diǎn) pi + 1是點(diǎn) pi 的鄰接點(diǎn) (以 n 為 模 ) 。曲 線 c 的 f ree2m an編碼由 n個(gè)向量組成 : ci = pi - 1 pi而且 , 每個(gè)向量均可由一個(gè)從 0 7 的整數(shù)表示 , 如圖 1 所示 ,向量與 x軸的夾角為 f / 4。曲線鏈碼定義為 ci , i = 1, 2, , n 且 ci = ci ±n收稿日期 : 2003203215; 修返日期 : 200520620

10、7基金項(xiàng)目 : 國(guó)家自然科學(xué)基金資助項(xiàng)目 ( 60473108)去掉一些特殊情況 ,一個(gè)是 co si, h為 - 1 的點(diǎn) ; 另一個(gè)是如果對(duì)于點(diǎn) pi , 它的左或右相鄰點(diǎn) pi - 1或 pi + 1也保留下來(lái) ,而 且 co si, h co si - 1, h或 co si, h co si + 1, h , 則去掉點(diǎn) pi。( 4)把剩余的點(diǎn)作為曲線 c 的特征點(diǎn) 。212 多邊形逼近方法多邊形逼近就是用一個(gè)多邊形來(lái)表示邊界曲線 ,所以人們 就借助這種思想得到了曲線的特征點(diǎn)檢測(cè)算法 。把逼近的多 邊形的頂點(diǎn) (也稱為斷點(diǎn) )作為其特征點(diǎn) 。多邊形逼近方法一般分為兩類 ,即連續(xù)逼近方

11、法和迭代逼 近方法 。連續(xù)逼近方法的一般過(guò)程是從曲線上的某一點(diǎn)出發(fā) ,通過(guò)順序地合并相鄰點(diǎn)得到符合一定條件的一段曲線 ,它是原 來(lái)曲線的一個(gè)子集 ,然后把該段曲線的最后一點(diǎn)作為下一個(gè)起始點(diǎn) ,進(jìn)行合并下一段符合條件的曲線 。如此下去 ,直到整條曲線被遍歷到 。這些得到的一系列起始點(diǎn)就作為特征點(diǎn) 。但 這個(gè)方法有個(gè)缺點(diǎn) ,它會(huì)丟失一些特征點(diǎn) 。因此出現(xiàn)了迭代逼近方法 。此方法先選擇兩個(gè)起始點(diǎn)分割曲線 ,如果不滿足規(guī)定的測(cè)試條件 ,則繼續(xù)分割下去 。在兩個(gè)起始點(diǎn)之間找到一點(diǎn) ,把曲線分割為兩條更小的曲線 ,這個(gè)分割點(diǎn)作為被分割后形成 的小段曲線的起始點(diǎn)之一 。這個(gè)過(guò)程將繼續(xù)下去 ,直到?jīng)]有進(jìn)一步分

12、割的必要 。在這個(gè)算法中 ,終止曲線分割一般采取這樣 的測(cè) 試 條 件 , 那 就 是 對(duì) 一 段 待 分 割 的 曲 線 間 所 有 的 點(diǎn) , 滿 足211 角檢測(cè)方法角檢測(cè)方法的目的是要檢測(cè)那些能夠描述物體邊界上出 現(xiàn)方向突變的地方的點(diǎn) ,它首先要估算曲線上每一點(diǎn)的曲率 。 在實(shí)域平面上 ,曲率定義為斜率的變化和弧長(zhǎng)函數(shù)的比值 。對(duì) 于曲線 y = f ( x ) ,曲線上某點(diǎn)的曲率表達(dá)為導(dǎo)數(shù)的形式 ,即22 3 /2cur ( x) = d ydy1 +dx2dx而對(duì)于數(shù)字曲線 ,計(jì)算其離散曲率時(shí)如果只是簡(jiǎn)單地通過(guò)一個(gè)像素點(diǎn)的變化來(lái)替代上式中的導(dǎo)數(shù)值 ,那么斜率細(xì)微的變 化將無(wú)法在計(jì)算

13、中反映出來(lái) ,因?yàn)閿?shù)字曲線上連續(xù)的斜率角的變化是 45 °的倍數(shù) 。在角檢測(cè)算法中一般都是采用擴(kuò) 大范圍的方式解決這個(gè)問(wèn)題 ,即 k > 1 ( k 是該點(diǎn)左右像素點(diǎn)的個(gè)數(shù) ) ,稱這個(gè) k值為平滑因子 , 利用這個(gè) k值可以得到計(jì)算該點(diǎn)曲率 的支撐區(qū)域 。估算離散曲率的方法有很多 ,這些方法一般有這樣一個(gè)宗 旨 ,那就是必須準(zhǔn)確地反映曲線真正的曲率 ,在此基礎(chǔ)上要盡 量減少計(jì)算量 。這里 引 入 兩 種 方 法 : 由 ro senfied 和 john s2ton 2 提出的 ,如圖 2 ( a)所示 ,用 co s 來(lái)估計(jì)曲線上點(diǎn) p 的曲ii率 cur i ,基于這一點(diǎn)

14、 ,我們稱它為 co s方法 , pi 是曲線上第 i個(gè)點(diǎn) 。 由 teh和 ch in 3 提出的改進(jìn)方法 ,如圖 2 ( b)所示 ,使 用偏差與弦長(zhǎng)的比值作為點(diǎn)的曲率 ,其中這 個(gè)偏差值是點(diǎn) pi 到弦 pi - k pi + k的距離 di , 它決定了點(diǎn) pi 的支持區(qū)域 , 即它決定 了對(duì)應(yīng)于點(diǎn) pi 的弦中 k值的取法 , 即用 di /l i 表示曲線上第 i 點(diǎn)的曲率 。d t 則不再分割下去 , 其中 d 仍為偏差值 , t 是偏差限度 。i did根據(jù)上面的方法 ,產(chǎn)生了多種檢測(cè)算法 , 最常用的有 r a2m e r算法 4 和分割 合并算法 5 。其中 ,后者要比 r

15、 am e r算法復(fù)雜一些 , r em e r算法只是一個(gè)分割的過(guò)程 。下面是分割 合 并算法的概括性描述 :( 1)沿邊界分配幾個(gè)點(diǎn)作為初始斷點(diǎn) ,順序地連接這些點(diǎn) 形成初始的多邊形 。( 2)在每?jī)蓚€(gè)相鄰斷點(diǎn)之間 ,沿著這一曲線段找到距離兩斷點(diǎn)連線的垂直距離最大的點(diǎn) 。如果這個(gè)距離大于我們預(yù)先 設(shè)定的一個(gè)閾值 ,那么把這一點(diǎn)作為新的斷點(diǎn) 。這就是算法中 的“分割 ”過(guò)程 。一旦曲率估算出后 , 下一步就判斷曲率是否大于某一閾值 tg ,若大于 ,則該點(diǎn)被認(rèn)為是角點(diǎn) , 即特征點(diǎn) 。但一 般情況 下 ,并不是簡(jiǎn)單地這樣做 ,而是分兩步來(lái)做 : 給出一個(gè)曲率閾值 ,去掉那些因曲率太小而不可能

16、是特征點(diǎn)的點(diǎn) ; 這一步稱 為非最大值篩選 過(guò)程 , 它是 把第 步過(guò)濾剩余的點(diǎn)再 進(jìn)行處理 ,去掉那些在該點(diǎn)支撐區(qū)域內(nèi)曲率不是極大值的點(diǎn) ,這樣把 最終剩余的點(diǎn)作為此曲線的特征點(diǎn) 。下面是 ro senfe ld2john ston算法的簡(jiǎn)單描述 :( 1 )定義曲線上點(diǎn) pi 的兩個(gè) k 2向量和 co sik :( 3)在相鄰的兩個(gè)線段上比較連續(xù)的三 個(gè)斷點(diǎn) ,如 a、b、c,計(jì)算出曲線段 ac上點(diǎn)到線段 ac 的最大距離 ,如果這個(gè)距離在閾值范圍內(nèi) ,則去掉 b 點(diǎn) 。這就是算法中的“合并 ”過(guò)程 。( 4)重復(fù)步驟 ( 2 )和步驟 ( 3 ) ,直到達(dá)到一個(gè)平衡狀態(tài) ,沒(méi)有再進(jìn)行“

17、分割 ”和“合并 ”的必要 。213 綜合方法角檢測(cè)方法可以檢測(cè)出一些重要的角點(diǎn) ,但是有時(shí)檢測(cè)出 的這些角點(diǎn)并不能很好地表示原邊界曲線 ,例如對(duì)于具有一長(zhǎng) 段緩慢變化的曲線段的邊界線 , 這樣的曲 線上就檢測(cè)不出角 點(diǎn) ,而要進(jìn)行特殊處理 ,如圖 3 所示 。多邊形迭代逼近方法對(duì) 起始點(diǎn)的設(shè)置比較敏感 ,不同的起始點(diǎn)可能導(dǎo)致不同的逼近結(jié) 果 ,因此起始點(diǎn)的選擇對(duì)這種方法很重要 。如果把這兩種算法 結(jié)合起來(lái) ,就可以克服它們各自的缺點(diǎn) 。a ik = ( x i - x i + k , y i - y i + k )bik = ( x i - x i - k , y i - y i - k )

18、a ×bik ik, co sik =a ik× bik其中 , co sik是 k 2向量 aik和 bik夾角的余弦值 ,且 - 1 co sik 1 ,當(dāng)其為 - 1時(shí) ,說(shuō)明這是一直線段 。( 2 )選擇一平滑因子 m (根據(jù) 曲 線 c 的 具 體 情 況 或 者 為n / 15, 或者為 n / 10 ) , 對(duì) c 上 每 一 點(diǎn) pi 計(jì) 算 co sik , k = 1, 2, m 。( 3 )根據(jù)下式選出對(duì)于點(diǎn) pi 的支撐區(qū)域 h i, 并且得出的曲率值 co si, h i : 6 pi因此 , a n sa ri和 d e lp 首先提出了一種綜合

19、方法 ,它首先是在邊界曲線上找到一系列曲率的極大值 ,然后運(yùn)用上面提到 的“分割 合并 ”多邊形逼近算法來(lái)檢測(cè)特征點(diǎn) 。co sim < co si, m - 1 << co si, h i co si, h i - 1 7 對(duì)于 co si, h i co sj, h j中所有的 j, 若點(diǎn) pi;| i - j | h i / 2, 則保留w u和 w ang 提出了一種基于曲率的多邊形逼近的綜合方法 ,稱為 co s2maxd 方法 。它把角檢測(cè) 法得到的角點(diǎn)作為( y i -y i - 1 ) x i - 2 - ( x i - x i - 1 ) y i - 2 +

20、 x i y i - 1 - x i - 1 y i =多邊形迭代逼近方法的起始點(diǎn) ,先通過(guò)一種角檢測(cè)方法得到最重要的特征點(diǎn) ,然后在這些點(diǎn)分割的小曲線段上進(jìn)行多邊形逼 近 ,這樣會(huì)得到很好的效果 。然而 ,以上提到的算法也有一個(gè)缺點(diǎn) ,檢測(cè)特征點(diǎn)算法本 應(yīng)該不受物體的大小和方向的影響 ,也就是說(shuō) ,當(dāng)物體的大小和方向發(fā)生變化時(shí) ,我們檢測(cè)到的特征點(diǎn)的數(shù)量不應(yīng)該變化 ,而且特征點(diǎn)的位置也不應(yīng)該偏離太多 。但上面的算法做不到 這一點(diǎn) ,我們?cè)诒疚闹刑岢隽艘环N有效并且速度更快的綜合方法 ,并且對(duì)物體的大小和方向的變化不那么敏感 。y i x i - 2 - y i - 1 x i - 2 - x

21、i y i - 2 + x i - 1 y i - 2 + x i y i - 1 - x i - 1 y i =- ( y i - y i - 2 )x i - 1 - ( x i - x i - 2 ) y i - 1 + x i y i - 2 - x i - 2 y i 最后的表達(dá)式與 dsi - 1的表達(dá)式的分子式相同 , 只是符號(hào)相反 , 這正是我們要證明的 。 關(guān)于 dsi 的符號(hào) , 我們有( y i + 1 - y i - 1 ) x i - ( x i + 1 - x i - 1 ) y i + x i + 1 y i - 1 - x i - 1 y i + 1ds =i2

22、 +) 2( y i + 1 - y i - 1 ) i + 1 i - 1( x- x將 pi + 1點(diǎn)代入式 ( 1 )的左邊 , 我們得到相同的結(jié)論 :( y i - y i - 1 ) x i + 1 - ( x i - x i - 1 )y i + 1 + x i y i - 1 - x i - 1 y i =3 新綜合方法的基本原理y i x i + 1 - y i - 1 x i + 1 - x i y i + 1 + x i - 1 y i + 1 + x i y i - 1 - x i - 1 y i =- ( y i + 1 - y i - 1 )證畢 。x i - ( x

23、 i + 1 - x i - 1 ) y i + x i + 1 y i - 1 - x i - 1 y i + 1 綜合方法的原理是很直觀的 。像角檢測(cè)方法一樣 ,該方法也是先計(jì)算各初始點(diǎn)的曲率并找出一些明顯的角點(diǎn) ;同時(shí)它還 像多邊形逼近方法那樣 ,從這些角點(diǎn)開(kāi)始逐漸向邊界上加入一些特征點(diǎn) ,直到滿足一定的條件為止 。新方法的最主要的特征 是對(duì)各點(diǎn)到弦的距離 di (如果小于設(shè)定的閾值 ) 進(jìn)行累加 (相當(dāng)于曲率的累加 ) ,該累加值累加到一定的值時(shí)則增加一個(gè)特征點(diǎn) ,并重新開(kāi)始累加 。這樣對(duì)于緩慢變化的曲線也可找到一 些特征點(diǎn) ,對(duì)其進(jìn)行描述 。這個(gè)綜合方法克服了角檢測(cè)方法的上述缺陷 ,

24、同時(shí)又比多邊形逼近方法提高了速度 ,這一速度的提高是因?yàn)樗褂昧它c(diǎn)到弦距離 di 的累加來(lái)決定應(yīng)在何處加 點(diǎn) 。而 di 在計(jì)算各點(diǎn)的第一個(gè)弦的曲率 (即由其相鄰的兩點(diǎn) 連線計(jì)算出的曲率 )時(shí)已算出 ,這樣在決定是否加點(diǎn)時(shí)在每一 點(diǎn)只需計(jì)算一次弦的曲率而不必像多邊形逼近方法那樣算多次弦 (包括非相鄰兩點(diǎn)間連線 )得出的曲率以判斷是否滿足某 條件 。由圖 4可以看出 , di 的累加值可以很好地表示邊界曲線的彎曲及被逼近程度 ,尤其對(duì)于平滑曲線 。因此 ,綜合算法就判 斷這個(gè)累加值是否大于某個(gè)閾值 td 。若是 , 則應(yīng)加一特征點(diǎn) ;否則 , 繼續(xù)累加 。在累加 di 的過(guò)程中 ,如果在相鄰兩點(diǎn)

25、處曲線向不同側(cè)彎曲 , 則此時(shí)要用減法操作 ; 否則用加法 ,如 圖 5 所現(xiàn)在 , 我們有如下的結(jié)果 :如果曲線在相鄰的兩點(diǎn) pi - 1和pi 處向不同側(cè)彎曲 , 則將另兩點(diǎn) pi - 2和 pi + 1分別代入式 ( 1 ) 的 左邊將產(chǎn)生不同的符號(hào) 。這些符號(hào)又分別與 dsi - 1和 dsi的符號(hào) 相反 , 所以在這種情況下 , dsi - 1的符號(hào)與 dsi 的符號(hào)是相反的 。這樣 , 在下面的算法中我們總是將每 一點(diǎn)的 dsi 進(jìn)行累加 , 實(shí)際上是對(duì)曲線彎曲的累加 , 這時(shí)的累加是帶符號(hào)的 。實(shí)際上 , 當(dāng)曲線彎向一側(cè)時(shí) , 相當(dāng)于將 dsi 的絕對(duì)值加到累加值中 ; 而 曲線

26、彎向另一側(cè)時(shí) , 相當(dāng)于從累加值中減去 dsi 的絕對(duì)值 。當(dāng)累加值達(dá)到一定量時(shí) ,即使沒(méi)有角點(diǎn)出現(xiàn) ,也要增加一個(gè)特征點(diǎn) ,以適應(yīng)緩慢彎曲的曲線 。4 算法實(shí)現(xiàn)411 預(yù)處理我們?cè)诶眠吔绺櫵惴ǖ玫揭粋€(gè)物體的邊界鏈碼時(shí) ,要 對(duì)這一鏈碼進(jìn)行一些處理 。( 1)除去邊界中所有寬度為一個(gè)像素的突起 。這種很細(xì)微的細(xì)節(jié)問(wèn)題不能由圖像的分辨率所解決 ,而且它是由噪聲和 量化誤差引起的 。一個(gè)像素寬度的突起就是這樣引起的 ,我們 必須除去 。這樣的例子如圖 6所示 。( 2)由于在直線上的點(diǎn)不能作為特征點(diǎn) ,所以我們要排除曲線上的這些點(diǎn) ,這可以通過(guò)檢查鏈碼來(lái)完成 。設(shè)曲線的鏈碼示 。觀察圖 5我們

27、會(huì)發(fā)現(xiàn) ,如果曲線在某兩點(diǎn)pi - 1和pi 處向不同側(cè)彎曲 , 則其前后兩點(diǎn) pi - 2和 pi + 1一定在 pi - 1和 pi 連線的不同側(cè) 。該連線的方程式可以寫(xiě)為( y i - y i - 1 ) x - ( x i - x i - 1 ) y + x i y i - 1 - x i - 1 y i = 0( 1 )為序列 c1 , c2 , c3 , cn , 那么如果 ci - 1 = ci , 則點(diǎn) pi 不可能這樣 , 將 b i - 2點(diǎn)和 b i + 1點(diǎn)分別代入上式 ,左邊一定會(huì)產(chǎn)生不同符號(hào)的值 。是特征點(diǎn) 。例如在圖 7中 , 由于 c4 = c5 = c6 =

28、7, 所以 p5 和 p6點(diǎn)不可能是特征點(diǎn) ; 而 p4 和 p7 點(diǎn)則可能是特征點(diǎn) ,可能的特 征點(diǎn)我們稱為轉(zhuǎn)折點(diǎn) ,在圖 7中由 ®表示 。這樣我們只需在轉(zhuǎn)折點(diǎn)處計(jì)算曲線的曲率 ,因而減少了大量的計(jì)算 。為了減少算法的計(jì)算量 ,我們使用帶 符號(hào)的距離 dsi , 并且 di = | dsi | 。下面的定理是新方法的基礎(chǔ) 。定理dsi - 1的符號(hào)與將點(diǎn) pi - 2代入式 ( 1)左邊所得值的符號(hào) 相反 ; dsi 的符號(hào)與將點(diǎn) pi + 1代入式 (1)左邊所得值的符號(hào)相反 。412 確定支撐區(qū)域在上面提到的算法中 ,均要求輸入一些參數(shù) ,特別是在計(jì) 算曲線上每一點(diǎn)的曲率時(shí)

29、,要求必須有一個(gè)支撐區(qū)域 ,這個(gè)區(qū) 域的確定是基于兩個(gè)方面 : 該曲線的長(zhǎng)度 ,也就是該數(shù)字曲( y i - y i - 2 ) xi - 1 - ( x i - x i - 2 ) y i - 1 + x i yi - 2 - x i - 2 y i證明 : dsi - 1 =22( y i - y i - 2 ) + ( x i - xi - 2 )由于上式的分母一定是正的 , 所以 dsi - 1的符號(hào)只 由上式的分子決定 ?，F(xiàn)將點(diǎn) pi - 2代入式 ( 1)左邊得 :線所包括像素的個(gè)數(shù) ; 當(dāng)前計(jì)算的點(diǎn)附近的細(xì)節(jié)狀況 。一般情況下 ,對(duì)一個(gè)變化急劇頻繁的曲線而言確定一個(gè)合適的支撐 區(qū)

30、域是很困難的 ,太大了會(huì)平滑掉曲線上一些特征 ,使很明顯 的特征點(diǎn)被忽略掉 ;而太小的支撐區(qū)域會(huì)產(chǎn)生很多冗余的特征點(diǎn) 。在確定支撐區(qū)域時(shí) ,我們所用的方法是對(duì) ro senfe ld2john s2ton角檢測(cè)方法的一種改進(jìn) 。在 ro senfe ld2john ston 方法中 ,如 果輸入的平滑參數(shù)選擇不恰當(dāng) ,將會(huì)導(dǎo)致某些點(diǎn)的支撐區(qū)域和曲率的計(jì)算均出現(xiàn)錯(cuò)誤 。為了克服這一缺點(diǎn) ,我們采用了對(duì)曲 線上每一點(diǎn)分別計(jì)算其所需的支撐區(qū)域 ,這一方面使算法對(duì)不 同的被檢測(cè)邊界曲線以及曲線上不同的細(xì)節(jié)保證了其獨(dú)立性 ;另一方面 ,減少了算法的輸入?yún)?shù) 。這樣一旦支撐區(qū)域確定下來(lái) ,那么在檢測(cè)特征點(diǎn)

31、時(shí) ,才能保證每一點(diǎn)曲率計(jì)算的正確性 。 從而我們得到了這樣一個(gè)結(jié)論 :特征點(diǎn)的檢測(cè)不僅依靠特征值(一般為曲率 )計(jì)算的正確性 ,而且更主要的是依靠支撐區(qū)域的精確測(cè)量 。這與傳統(tǒng)檢測(cè)方法的說(shuō)法有所不同 ,在傳統(tǒng)方法 中 ,離散曲率的正確測(cè)量被認(rèn)為是檢測(cè)可靠的特征點(diǎn)的主要因素 。下面是確定支撐區(qū)域的過(guò)程 : d i 中除去 。若點(diǎn) pi - 1或 pi + 1也在集合 d i 中 ,也就是說(shuō) ,曲線上連續(xù) 的兩點(diǎn)都是轉(zhuǎn)折點(diǎn) ,而且經(jīng)計(jì)算后 ,均通過(guò)了篩選 。這時(shí)如果 cur ( pi ) cur ( pi - 1 )或者 cur ( pi ) cur ( pi + 1 ) 則也把 pi從集合 d

32、 i 中除去 。這一過(guò)程可以與步驟 ( 3)并行操作 。5 實(shí)驗(yàn)結(jié)果比較與算法分析511 分析結(jié)果的標(biāo)準(zhǔn)從模式識(shí)別角度講 ,在數(shù)字曲線上檢測(cè)特征點(diǎn)可看作是曲 線的一種壓縮 ,或者說(shuō)是曲線有效的表示 。連接相鄰的特征點(diǎn) 得到的多邊形用來(lái)逼近這個(gè)曲線 。我們?cè)诒疚闹卸x了一些 標(biāo)準(zhǔn)來(lái)反映它們之間的關(guān)系和分析算法實(shí)現(xiàn)結(jié)果 。如果用數(shù) 據(jù)壓縮的觀點(diǎn)來(lái)衡量 ,是期望得到盡量少的特征點(diǎn) ,然而特征 點(diǎn)太少又不能很好地反映原曲線 。因此應(yīng)該在權(quán)衡這兩方面 的基礎(chǔ)上 ,得到較好的綜合考慮的標(biāo)準(zhǔn) 。我們?cè)谶@里使用了三 個(gè)標(biāo)準(zhǔn)來(lái)衡量算法的實(shí)現(xiàn) 。( 1)壓縮比 ( cr ) , 即曲線上的點(diǎn)數(shù)與 所檢測(cè)到的特征點(diǎn)

33、 數(shù)的比值 。定義為 cr = n /m , 其中 , n 是被檢測(cè)曲線點(diǎn)的個(gè)數(shù) (如果為封閉曲線 , 則 n = n, n 是曲線鏈碼的個(gè)數(shù) ; 否 則 , n =n + 1) 。而 m 是通過(guò)檢測(cè)算法后檢測(cè)到的特征點(diǎn) 。這個(gè)壓縮 比越大 , 說(shuō)明這個(gè)算法在數(shù)據(jù)的壓縮上越有效 。( 2)均值誤差 ( e2 )用來(lái)估計(jì)原曲線和逼近多邊形的差別 ,它是所有逼近多邊形的邊與原曲線所夾面積的平均值 。定義( 1 )定義點(diǎn) pi - k和 pi + k的弦長(zhǎng) 。 lik =pi - k pi + k, 并且定義dik為點(diǎn) b i 到弦 pi - k pi + k的垂直距離 , 如圖 2 ( b)所示

34、。( 2 )從 k = 1開(kāi)始 , 計(jì)算 lik和 dik直到滿足條件 : lik li, k + 1或者dik di, k + 1dik di, k + 1當(dāng) dik > 0; 當(dāng) dik < 0。1 m likli, k + 1likli, k + 1為 e2 = a i , 其中 , m 是曲線被分割后的曲線段數(shù) (如果為m i = 1封閉曲線 , 則 m =m ; 否則 , m = m - 1 ) , 而 a i 為原曲線和弦這樣 , 我們把滿足條件 或者條件 的點(diǎn)作為點(diǎn) pi 的支撐區(qū)域 , 用 s ( pi ) 表示 : s ( pi )pi + k ) |條件 或者條

35、件 。413 新算法描述= ( pi - k , pi - 1 , pi , pi + 1 ,v iv i + 1 (v i 是第 i個(gè)特征點(diǎn) ) ,如圖 8所示 。面積的大小我們采用曲線段上所有點(diǎn)到弦的垂直距離來(lái)估算 。這個(gè)參數(shù)反映了 逼近多邊形在多大程度上逼近原有的曲線 。很明顯 ,這個(gè)值越小 ,這種算法越有效 。在前面討論的基礎(chǔ)上 ,我們對(duì)新算法進(jìn)行以下描述 :輸入 : td (對(duì)于 di的累加值設(shè)定的閾值 ) ; tg (對(duì)曲率估算 值 di /l i 設(shè)定的閾值 ) ; pi (原始取樣點(diǎn)集 ) 。輸出 : d i (求出的特征點(diǎn)集 ) 。 算法 :( 1 )得到被測(cè)物體的邊界曲線鏈

36、碼 pi 。( 2 )通過(guò)檢測(cè)由 pi 形成的鏈碼找出轉(zhuǎn)折點(diǎn) , 即從 pi 得 到轉(zhuǎn)折點(diǎn)集 b i 。( 3 )找出所有的特征點(diǎn) ,其過(guò)程如下 :ac0;fo r每一個(gè) b i do計(jì)算 d si和 l i ;if | d si /l i | > tg then將 b i 放到 d i 集合中 ;ac0e lse acac + d si ;if | ac | > td then 將 b i 放到 d i 集合中 ;a c0 ( 4 )一些必要的處理 ,去掉不必要的點(diǎn) 。對(duì)于第 ( 3 ) 步得 到的集合 d i , 若 集 合 中 點(diǎn) 支 撐 區(qū) 域 k = 1, 則 把 pi

37、從 集 合( 3)最大誤差 ( em ) :定義為 em ax = m ax a i1im 512 與傳統(tǒng)算法的比較對(duì)新算法與在第 2 節(jié)中介紹的三種算法分別在以下幾個(gè) 方面進(jìn)行比較 : 特征點(diǎn)的個(gè)數(shù) ; 逼近誤差 e2 和 em ax ; 算 法的 cpu 運(yùn)行時(shí)間 。在這里我們引入了兩種物體對(duì)象進(jìn)行測(cè) 試 ,如圖 9 ( a)和圖 11 ( a)所示 。一般說(shuō)來(lái) ,一個(gè)好的特征點(diǎn)檢 測(cè)算法應(yīng)該在物體的大小或者是旋轉(zhuǎn)角度發(fā)生變化時(shí)保持一 種穩(wěn)定性 。因此 ,這里我們對(duì)每個(gè)物體在這些因素變化時(shí)也進(jìn) 行了測(cè)試和比較 。這些變化的曲線連同原邊界曲線如圖 9 ( a)圖 12 ( a) 所示 ,并且

38、在圖 9 ( be) 圖 12 ( b e) 中分別對(duì)co s方法 、分割 2合并方法 、co s2maxd 方法以及新方法所檢測(cè) 到的特征點(diǎn)作了標(biāo)記 ,并且在表 1和表 2中對(duì)得到的測(cè)試結(jié)果進(jìn)行了總結(jié) 。如圖 9所示 ,我們對(duì)第一個(gè)物體的邊界曲線進(jìn)行了特征點(diǎn)表 2 對(duì)于圖 11 和圖 12 的邊界曲線新算法與其他算法的比較檢測(cè) ?？梢钥吹?,使用 co s角檢測(cè)方法只檢測(cè)到了四 個(gè)特征點(diǎn) (圖 9 ( b) ) ,很明顯 ,四個(gè)點(diǎn)檢測(cè)出的正好是物體的 四個(gè)角 點(diǎn) 。但是 ,用這些點(diǎn)并不能很好地逼近該邊界曲線 ,因?yàn)樵谶?界曲線上還有兩段弧線 。而其他的三種方法均檢測(cè)到了六個(gè)特征點(diǎn) (圖 9

39、( ce) ) ,這樣就能夠較好地描述這條曲線 。下面我們?cè)趤?lái)觀察一下圖 10 ( a ) , 它與圖 9 ( a ) 是同一個(gè)物體的邊 界 ,只是旋轉(zhuǎn)了一定角度 。可以看到 ,使用 co s方法和新方法與旋轉(zhuǎn)前得到的結(jié)果相同 (圖 10 ( b, e)和圖 9 ( b, e) ) ,而在分割 合并算法和 co s2maxd 方法中 , 產(chǎn)生了過(guò)多的冗 余特征 點(diǎn) (圖 10 ( c, d) ) 。所以可以看出只有新方法不僅檢測(cè)到了合 適的特征點(diǎn) ,而且得到了較好的一致性結(jié)果 ,這說(shuō)明對(duì)物體的方向 、大小不敏感 。在表 1 中我們給出了比較結(jié)果 , co s角檢測(cè)方法有最大的均值誤差 ,而其他

40、三種方法在這一方面比較相 近 。但在算法的運(yùn)行時(shí)間上 ,新算法用時(shí)最少 ,這是因?yàn)樵谒惴ㄖ幸肓宿D(zhuǎn)折點(diǎn)的概念 ,減少了很多的計(jì)算量 。表 1 對(duì)于圖 9 和圖 10 的邊界曲線新算法與其他算法的比較6結(jié)束語(yǔ)一般來(lái)說(shuō) ,特征點(diǎn)檢測(cè)算法均有下面三個(gè)步驟 :( 1)找出轉(zhuǎn)折點(diǎn) ;( 2)通過(guò)計(jì)算曲率 求 出 一 些 明 顯 的 特 征 點(diǎn) (曲 率 大 于 tg的點(diǎn) ) ;( 3)通過(guò)一個(gè)逼近過(guò)程確定其余的特征點(diǎn) ,使得特征點(diǎn)間 的連線較好地逼近原始曲線 。其中第 ( 3 )步要計(jì)算 pi 到 pi - k pi + k連線的距離 , 這需要大 量的計(jì)算 。而本文介紹的綜合算法將上述的第 ( 2 )

41、 步和第 ( 3 )步合為一個(gè)步驟 。由于在上述過(guò)程的第 ( 2 ) 步計(jì)算曲率 di / l i時(shí)已經(jīng)求出了 di , 所以該算法就利用 di 的累加值來(lái)代替上述 第 ( 3)步的 復(fù) 雜 計(jì) 算 , 這 同 樣 可 以 達(dá) 到 很 好 地 逼 近 曲 線 的 目的 。實(shí)際上 ,通過(guò)設(shè)置逼近閾值 ,所有算法都可以進(jìn)行任何程度的逼近 ,關(guān)鍵是在逼近的過(guò)程中所需計(jì)算量的多少 。實(shí)驗(yàn)及 比較結(jié)果表明 ,本文的新算法在選擇適當(dāng)?shù)奶卣鼽c(diǎn)及運(yùn)算速度方面都比現(xiàn)有算法有較大的改進(jìn)和提高 。參考文獻(xiàn) : 1 f a ttneave. som e info rm ationa l a sp ec ts of v

42、 isua l pe rcep tion j . p sycho l. r ev, 1954 , 61 ( 3 ) : 183 2193.a ro senfe ld, e john ston. a ngle d e tec tion on d igita l cu rves j . ieee tran s. on comp u te rs, 1973 , 22: 875 2878.c h teh, r t ch in. o n the d e tection of dom inan t po in ts on d igitalcu rve s j . ieee tran s. patte rn

43、 a na l on m ach ine in te lligence,1989 , 11 ( 8 ) : 859 2872.u r am e r. a n ite ra tive p rocedu re fo r the po lygona l app roxim a tion ofp lane cu rve s j . comp u te r grap h ic s im age p roce ss, 1972 , 16 ( 1 ) :244 2256.t pavlid is, s l ho row itz. segm en ta tion of p lane cu rve s j . ieee tran s. on comp u te rs, 1974 , 23: 860 2870.n a n sa ri, e j d e lp. o n d e tec ting dom inan t po in ts j . pa tte rnr ecogn ition, 1991 , 24 ( 5 ) : 441 2451.w y w u, m j w ang. d e tecting the dom inan t po in ts by the cu rva2 tu