改進的SUSAN角點檢測算法

1、改進的SUSAN!點檢測算法Improved SUSAN Corner Detection AlgorithmZHANG Yingquan,WANG Qionghua,LI Dahai,ZHANG Wentao (School of Electronics and InformationEngineering,Key Laboratory of Fundamental Synthetic Vision Graphics and Imagefor National Defense,Sichuan University,Chengdu,610065,China):SUSAN corner dete

2、ction algorithm is widely used in feature extraction for its good performance in noise resistance and fast calculation.The traditional SUSAN algorithm has a fixed brightness difference threshold and can t e liminate the fake corner well.The traditional algorithm is time-consuming when large-size mas

3、k is used.Aiming at those problems,the relationship between mask size and detection results is discussed,and an algorithm using alternate mask is proposed.A method that can select the threshold automatically is adopted.The energy distribution and pixel projection methods are used to eliminate the fa

4、ke corners.The experimental results show that this improved algorithm reduces the detection time and improves the detection accuracy.distribution;pixel projection0 引 言在計算機視覺和圖像處理中角點還沒有明確的數(shù)學(xué)定義 , 存 在多種數(shù)學(xué)描述方法。 一般的角點定義為圖像中灰度的劇烈變化 點或是曲線曲率的極大值點 1,2 。角點包含了大量圖像信息 , 但卻減小了計算量 3,4, 因而被廣泛運用于圖像識別、目標(biāo)匹 配、圖像融合以及三維重

5、建之中 5,6 。 SUSAN (Smallest Univalue Segment Assimilating Nucleus) 算法7,8 是由 Smith 等人提出的一種底層圖像處理方法。此算法簡單 , 定位精度高 , 運算速度快 , 其不需要梯度運算的特點 , 使該算法有很好的抗噪 聲性能9,10。但SUSAN!法也存在一些不足，例如,當(dāng)模板增大 時, 其運算量顯著增加 , 同時它不能很好地去除偽角點。 基于以上 兩點,這里提出一種變換模板的方法 ,解決在大模板下耗時的缺 點; 然后使用能量分布和像素投影的方法去除偽角點。1 SUSAN算法及改進算法1.1傳統(tǒng)SUSAf算法的基本原理圖1

6、是傳統(tǒng)SUSAN!法的原理圖，a,b,c,d 是圓形模板所在 的四個位置 , 模板中心點稱為“核” , 在模板內(nèi)把所有與核值相 同或相似的像素所構(gòu)成的區(qū)域叫作核值相似區(qū)(USAN)。當(dāng)模板位于平坦區(qū)域a時,USAN面積最大；當(dāng)模板位于角點b時,USAN面積 最小；當(dāng)模板位于邊緣c時,USAN面積為模板總面積50%;當(dāng)模板位于d時,USAN面積大于總面積的50%,由此可根據(jù)USAN面積大 小來判斷角點位置。c(r,r0)=1, |li- I0| tp(1)檢測時, 模板在圖上移動 , 在每個位置 , 用式(1) 比較模板內(nèi) 各像素與核值的灰度。式(1)中:r0是模板核的位置;r是模板內(nèi) 其他點的

7、位置 ;l0 是模板核的灰度值 ;li 是模板內(nèi)其他像素的灰 度值;tp是灰度閾值;c(r,r0) 是灰度比較的結(jié)果。t0=1NE Ni=0abs(li -10) (2)圖1傳統(tǒng)SUSAf算法原理圖式(1) 中的灰度閾值 tp 決定了所能檢測到的最低對比度以 及去除噪聲的能力 , 這里采用一種迭代的方法實現(xiàn)自動選取閾 值。如式 (2) 所示, 首先計算模板內(nèi)各點與核的差值 , 再取這些差 值的平均值t0作為迭代的初始值，其中N是模板內(nèi)的像素個數(shù)。ti + 1= 12Etid = 0dn(d)刀tid = 0n(d) + 刀 cmax d = ti+1d n(d) 刀 cmaxd = ti+1

8、n(d) (3)按式進行迭代。式中,ti是迭代初值;ti+1是迭代 值;d是模板內(nèi)各點與核的灰度差;cmax是這些差值中的最大 值;n(d)是模板內(nèi)與核值的灰度差為d的點個數(shù)。Farea(r0)= E Nr=1c(r,r0)(4)USAN勺面積由式 給出,Farea(r0) 是USAN的面積大小。通過判斷 Farea(r0) 的值, 便可判斷此點是否是角點SUSAN檢測算法中模板大小是固定的。實驗表明，模板尺寸 與檢測結(jié)果密切相關(guān)。圖 2 是不同尺寸方形模板檢測結(jié)果對比 , 圖 2 中加入了部分隨機噪聲。 從圖 2 可看出 , 模板越小 , 檢測靈敏 度越高;耗時越短,誤檢率越高;相反,大尺寸

9、模板的檢測準(zhǔn)確度 高,誤檢率低,但耗時更長。 因此有必要尋找檢測準(zhǔn)確度高且耗時 短的檢測方法。1.2改進的SUSANI點檢測算法變換模板檢測方法結(jié)合了小模板檢測靈敏度高 , 耗時短和大 模板檢測準(zhǔn)確度高 , 誤檢率低的優(yōu)勢 , 從而可以滿足上面的要求。 變換模板方法的檢測過程如下:首先用3X3的模板進行初檢測， 并記錄下此時檢測到的角點位置，然后再用9X9的模板對剛才 記錄下的初測角點位置進行精檢測。這些初測角點只有在 9X9 模板下滿足角點條件的才會被判定為特征點 , 這樣就可以減少 9X9模板檢測的像素個數(shù)，減少了計算量，從而縮減了檢測時 間。然而 , 實際中由于噪聲的存在 , 經(jīng)常會檢測

10、出偽角點 , 這需要 去除。圖 2 不同尺寸模板檢測結(jié)果首先分析一下偽角點產(chǎn)生的原因。 圖 3是偽角點產(chǎn)生及能量 分布法的原理圖 , 圖中顏色相同的方塊表示其像素灰度相似。從 圖中可知,USAN的面積，即淺色方格的個數(shù)是20,其中不包括核。 在文中判定是否是角點的條件:USA N的值介于模板總像素個數(shù) （不包括核）的 1/41/2 之間,因此圖 3中的核滿足角點條件。產(chǎn)生誤檢的原因是USAN勺像素分布不集中。圖3 偽角點產(chǎn)生及能量分布法原理圖 從圖 3 抽象出如下方法 , 模板內(nèi)與核值灰度相似的像素組成 模板內(nèi)的一高能量區(qū)，即USAN高能量區(qū)；相反,模板內(nèi)與核值灰 度差大于灰度閾值 tp 的像

11、素 , 則組成模板內(nèi)的另一個相對的低 能量區(qū)。模板內(nèi)每個與核值灰度相似的像素都對USAN高能量區(qū)產(chǎn)生各自的貢獻。因為角點的USAN分布應(yīng)相對集中，即它只應(yīng)集中分布于模 板四個角中的一個角 , 而不可能較均勻地散布在模板內(nèi) , 如圖 3 所示。以核所在的行、列為界,將模板分成四個能量區(qū) ,核的左上方 為能量I區(qū)，右上方為口區(qū)，同理左、右下方分別是區(qū)，其 中每個區(qū)都包含核所在的行列。 因此可以分別計算出圖 3 中四個 能量區(qū)的能量大小，也即USAN面積。如果模板的能量集中分布于 某一區(qū)域 , 即模板的四個能量區(qū)中只有一個高能量區(qū) , 并且這一 高能量區(qū)的大小滿足文中提到的角點條件 , 那么這就是一

12、個角 點。圖 4 是變換模板方法下用能量分布法去除偽角點的檢測圖。 從圖 4看出, 能量分布法能較好地去除偽角點 , 但圖 4中由兩條直 線相交而成的那些角點卻沒有被檢測到 , 如圖 4 中用圓圈標(biāo)識出 的, 這是因為它們在模板內(nèi)的分布本來就不集中。結(jié)合這類角點 的特性,可采用像素投影法來檢測。圖5為像素投影法的原理圖 , 如圖 5中虛線箭頭所示 , 模板中 與核值灰度相似的像素在垂直方向向下做投影 , 同時各列相應(yīng)像 素投影區(qū)計數(shù)加 1, 最后通過判斷各列像素投影區(qū)的值就可判斷 出該模板中心是否是角點。 在此過程中 ,核不參與投影 , 核所在列 的像素投影區(qū)位置最終也不予考慮。綜合實際中存在

13、的噪聲 , 并 考慮到常見的線型有“十”型和“ X”型兩種，若各列投影區(qū)均 有值 , 且不大于 2, 就認為該模板中心為角點。圖4 能量分布法去除偽角點檢測圖圖5 像素投影法原理圖1.3 實驗結(jié)果及分析圖 6 是變換模板方法結(jié)合能量分布法與像素投影法提取一幅圖像的特征點。圖像分辨率是 640X480,圖中加有部分隨機噪 聲, 角點數(shù)為 56 個, 包含了各類型角點。圖6改進的SUSAf算法檢測結(jié)果對比圖 6和圖2可看出,由于能量分布法的使用 ,許多偽角點 都被去除掉。對比圖 6 和圖 4 可看出 , 由直線相交而成的角點在 圖 4 中沒有被檢測到 , 而在圖 6 中 , 因為像素投影法的使用 , 它們 被檢測到了。表 1 是檢測結(jié)果對照表。從表 1 得出的模板越小 , 檢測出的偽角點越多 , 但耗時越短 , 大模板則有相反檢測效果。 在 結(jié)合了大小尺寸模板后 ,就可得到較好的結(jié)果。從圖 6和表 1可 看出 , 改進算法的準(zhǔn)確度最高 , 它提取出所有