基于梯度直方圖的交叉點(diǎn)檢測(cè)方法*

劉進(jìn)博，郭鵬宇，李 鑫

(1.中國(guó)空氣動(dòng)力研究與發(fā)展中心 超高速空氣動(dòng)力研究所，四川 綿陽(yáng) 621000；2.軍事科學(xué)院 國(guó)防科技創(chuàng)新研究院，北京 100071)

相機(jī)-投影儀組成的結(jié)構(gòu)光三維重建系統(tǒng)中，相機(jī)與投影儀的參數(shù)標(biāo)定最為重要，直接決定了系統(tǒng)形貌測(cè)量的精度[1]。目前典型的標(biāo)定方法是將投影儀視作逆相機(jī)，通過(guò)虛擬成像，利用張正友平面靶板標(biāo)定方法確定系統(tǒng)參數(shù)，該方法雖然精度較高，但標(biāo)定過(guò)程復(fù)雜、耗時(shí)較長(zhǎng)[2]。通過(guò)引入網(wǎng)格結(jié)構(gòu)光，可避免對(duì)投影儀進(jìn)行虛擬成像，從而簡(jiǎn)化標(biāo)定過(guò)程，提高相機(jī)-投影儀標(biāo)定效率。上述方法的難點(diǎn)在于平面網(wǎng)格結(jié)構(gòu)光的交叉點(diǎn)檢測(cè)，包括交叉點(diǎn)定位精度和交叉點(diǎn)檢測(cè)率兩方面。

交叉點(diǎn)檢測(cè)是圖像處理中的一項(xiàng)重要內(nèi)容，可以為圖像的特征提取、圖像目標(biāo)識(shí)別、圖像理解等提供重要的參數(shù)和依據(jù)[3-6]。目前，交叉點(diǎn)檢測(cè)仍然是計(jì)算機(jī)視覺(jué)領(lǐng)域尚未完全解決的難題之一，且相關(guān)文獻(xiàn)較少。已報(bào)道的交叉點(diǎn)檢測(cè)方法主要分為以下兩類：①對(duì)二值化圖像進(jìn)行膨脹、腐蝕等圖像形態(tài)學(xué)運(yùn)算，提取交叉線單像素骨架，逐一掃描圖像點(diǎn)，根據(jù)交叉點(diǎn)8鄰域灰度突變次數(shù)確定交叉點(diǎn)粗位置，然后根據(jù)擬合法或灰度重心法對(duì)交叉點(diǎn)進(jìn)行亞像素定位[7-8]；②分別按行和列對(duì)圖像進(jìn)行亮度峰值掃描，細(xì)化圖像交叉線并提取骨架，通過(guò)計(jì)算單像素線條交點(diǎn)確定交叉點(diǎn)粗位置，然后根據(jù)擬合法或灰度重心法對(duì)交叉點(diǎn)進(jìn)行亞像素定位[8-9]。第一類方法為傳統(tǒng)交叉點(diǎn)檢測(cè)方法，計(jì)算速度較快，但錯(cuò)檢率、漏檢率較高，而且受圖像形態(tài)學(xué)運(yùn)算精度的限制，傳統(tǒng)交叉點(diǎn)檢測(cè)方法的定位準(zhǔn)確性不夠。第二類方法要求交叉線夾角(交叉角)近似垂直，且交叉線方向與圖像坐標(biāo)軸近似平行，此種情況下，該方法的圖像交叉點(diǎn)檢測(cè)率和定位精度均較高。但由于未考慮灰度分布的方向性，若圖像發(fā)生旋轉(zhuǎn)或透視變換，將導(dǎo)致交叉角大小或交叉線方向發(fā)生較大變化，從而第二類方法不適用。

在深入研究了尺度不變特征變換(Scale-Invariant Feature Transform,SIFT)算法原理的基礎(chǔ)上[10-11]，本文提出了一種基于梯度直方圖的交叉點(diǎn)檢測(cè)方法：以灰度梯度幅值和方向?yàn)榛A(chǔ)，在角度空間構(gòu)造8維特征描述子，根據(jù)交叉點(diǎn)鄰域梯度分布特點(diǎn)對(duì)特征描述子進(jìn)行判定，篩選出候選交叉點(diǎn)，最后通過(guò)聚類和灰度加權(quán)對(duì)交叉點(diǎn)幾何中心進(jìn)行亞像素定位。

1 算法原理

基于梯度直方圖的交叉點(diǎn)檢測(cè)流程如圖1所示。對(duì)輸入圖像進(jìn)行高斯濾波并逐像素掃描，將特征描述子滿足交叉點(diǎn)判定準(zhǔn)則的像素加入候選交叉點(diǎn)集，最后通過(guò)聚類輸出圖像交叉點(diǎn)檢測(cè)結(jié)果。檢測(cè)過(guò)程主要涉及3個(gè)重要環(huán)節(jié)：特征描述子生成、交叉點(diǎn)判定和候選交叉點(diǎn)聚類，本節(jié)內(nèi)容主要針對(duì)上述3個(gè)環(huán)節(jié)進(jìn)行詳細(xì)闡述。

圖1 基于梯度直方圖的交叉點(diǎn)檢測(cè)方法流程圖Fig.1 Flowchart for the detection method based on gradient-histogram

1.1 特征描述子生成

由于相機(jī)采集圖像存在噪聲，為提高算法適應(yīng)能力，首先對(duì)原始圖像進(jìn)行高斯濾波，若原始圖像為彩色圖像，則需轉(zhuǎn)換為灰度圖像再進(jìn)行高斯濾波。記pi,j為灰度圖像的第i行、第j列像素點(diǎn)，g(i,j)為其對(duì)應(yīng)的灰度值，根據(jù)中心差分計(jì)算各像素點(diǎn)的灰度梯度幅值及方向[12-13]，公式為：

(1)

其中，gx、gy為對(duì)應(yīng)像素點(diǎn)沿圖像x、y方向的灰度梯度，m為對(duì)應(yīng)像素點(diǎn)的灰度梯度幅值，θ為對(duì)應(yīng)像素點(diǎn)的灰度梯度方向(范圍為0°～360°)。

將角度空間0°～360°劃分為8等份，如圖2所示。1～8表示劃分的角度空間標(biāo)號(hào)，分別代表的梯度方向?yàn)?°、45°、90°、135°、180°、225°、270°、315°和360°，其中337.5°～22.5°屬于第1角度空間，22.5°～67.5°屬于第2角度空間，以此類推。

圖2 角度空間8等份劃分Fig.2 Slice up angle space into 8 equal parts

統(tǒng)計(jì)各像素點(diǎn)16×16鄰域的梯度幅值及方向，并按角度空間累積梯度幅值。交叉點(diǎn)如圖3(a)所示。由于交叉點(diǎn)中心附近梯度幅值小且方向易受影響，如圖3(b)所示，因此利用權(quán)重模板，如圖3(c)所示，對(duì)鄰域像素梯度進(jìn)行加權(quán)，進(jìn)而在角度空間生成梯度直方圖，作為各像素點(diǎn)的特征描述子k(pi,j)，如圖3(d)所示。

(a)交叉點(diǎn) (b)交叉點(diǎn)鄰域梯度(a)Intersection points (b)Gradients of neighborhood pixel

1.2 交叉點(diǎn)判定

利用1.1節(jié)介紹的方法計(jì)算出各像素點(diǎn)的特征描述子之后，根據(jù)如下的準(zhǔn)則對(duì)像素點(diǎn)進(jìn)行逐一判定，篩選出候選交叉點(diǎn)。不失一般性，以圖像中任一像素pi,j為例，記k(pi,j) = (h1,h2,h3,h4,h5,h6,h7,h8)為該像素點(diǎn)的特征描述子。

1)總能量判定準(zhǔn)則。交叉點(diǎn)由兩條直線或近似直線相交而成，在直線邊緣處，灰度梯度最大。因此特征描述子的梯度幅值之和，即能量總和必須大于給定的能量閾值Tthresh。

(2)

2)能量占比判定準(zhǔn)則。對(duì)于任一交叉點(diǎn)，在其鄰域范圍內(nèi)必然存在4個(gè)梯度主方向?；诖耍瑢?duì)特征描述子k(pi,j)中的8個(gè)能量分量進(jìn)行由高到低排序，假設(shè)h1≥h2≥h3≥h4≥h5≥h6≥h7≥h8，Rthresh為給定的能量占比閾值，則：

(3)

3)反向判定準(zhǔn)則。交叉點(diǎn)由兩條直線或近似直線相交而成，直線兩側(cè)的灰度梯度方向相反，不失一般性，記hi、hj、hk、hl為特征描述子的4個(gè)梯度主方向，ni、nj、nk、nl為其對(duì)應(yīng)的角度空間標(biāo)號(hào)，Si,j表示ni與nj的角度差，Si,k表示ni與nk的角度差，Sk,l表示nk與nl的角度差，Sj,l表示nj與nl的角度差。則ni、nj、nk、nl必然滿足式(4)或式(5)。

(4)

(5)

4)能量平均判定準(zhǔn)則。交叉點(diǎn)由兩條直線或近似直線相交而成，直線兩側(cè)的灰度梯度幅值近似相等。不失一般性，記hi、hj、hk、hl為特征描述子的4個(gè)梯度主方向，Dthresh為平均能量閾值，hi、hj、hk、hl必然滿足：

為什么會(huì)沉默時(shí)充實(shí)，開口時(shí)空虛？因?yàn)橐坏╅_口，就像戰(zhàn)士沖出了戰(zhàn)壕，將自己完全暴露于敵人的火力之下。為此，如果沒(méi)有直接傷害到個(gè)人利益，許多人都會(huì)選擇沉默。過(guò)去如此，現(xiàn)在也是如此。至于戰(zhàn)陣中伙伴的變化，也是經(jīng)常發(fā)生的事情，高升的不再下顧，退隱的不再出頭，所以那些站在前邊的改革者和吶喊著，會(huì)經(jīng)常地感覺(jué)到苦悶和孤獨(dú)。

(6)

1.3 候選交叉點(diǎn)聚類

候選交叉點(diǎn)聚類前后如圖4所示。由于交叉點(diǎn)的兩條交叉線有一定寬度，通常大于1像素，導(dǎo)致交叉點(diǎn)及其相鄰像素的特征描述子有一定的相似度。因此在實(shí)際的交叉點(diǎn)附近一般存在2個(gè)甚至2個(gè)以上的候選交叉點(diǎn)，如圖4(a)所示。

(a) 透視變換-1 (b) 透視變換-2(a) Transformation-1 (b) Transformation-2

(a) SNR=21.97 dB (b) SNR=10.32 dB

(a) σ =1.0像素 (b) σ=2.0像素

(a) 旋轉(zhuǎn)角為10° (b) 旋轉(zhuǎn)角為30°(a) Rotation angle is 10° (b) Rotation angle is 30°

(a) 交叉角為90° (b) 交叉角為85°(a) Crossing angle is 90° (b) Crossing angle is 85°

(a) 候選交叉點(diǎn)分布(a) Distribution of candidate intersection points

采用基于歐氏距離的候選交叉點(diǎn)聚類方法，即相互距離小于設(shè)定的距離閾值dthresh的候選交叉點(diǎn)集聚為一類。

(7)

式中，dist(pi,j,pk,l)為像素點(diǎn)pi,j和像素點(diǎn)pk,l在圖像上的歐式距離。

(8)

其中，x，y為像素點(diǎn)p的圖像像素坐標(biāo)。

理論上，交叉點(diǎn)灰度值應(yīng)大于鄰域灰度值，即從候選交叉點(diǎn)中選取灰度值最大的點(diǎn)作為交叉點(diǎn)檢測(cè)結(jié)果輸出。但實(shí)際應(yīng)用中發(fā)現(xiàn)，圖像灰度值大小會(huì)受到被觀測(cè)物體表面粗糙度和反射率影響，導(dǎo)致交叉點(diǎn)灰度值不一定在鄰域范圍內(nèi)總是最大，即交叉點(diǎn)能量中心和幾何中心存在偏差。因此，采用灰度加權(quán)法計(jì)算聚類中心[8]。

(9)

選用灰度加權(quán)法計(jì)算聚類中心雖然使得本文算法更加魯棒，即對(duì)于鄰域灰度不完全滿足高斯特性的交叉點(diǎn)，本文算法依然可以定位到交叉點(diǎn)幾何中心附近，但對(duì)于灰度呈高斯分布且能量中心與幾何中心重合的交叉點(diǎn)，該灰度加權(quán)法會(huì)使得交叉點(diǎn)定位精度有所降低，如圖4(b)所示。

2 實(shí)驗(yàn)

實(shí)驗(yàn)?zāi)康脑谟跍y(cè)試算法在不同配置下的檢測(cè)性能。算法性能通過(guò)兩個(gè)參數(shù)表征：圖像交叉點(diǎn)提取精度和圖像交叉點(diǎn)檢測(cè)率。

圖像分辨率大小為768×1 024，根據(jù)不同配置要求仿真交叉點(diǎn)圖像，交叉點(diǎn)幾何中心真實(shí)坐標(biāo)及交叉點(diǎn)數(shù)量視為已知：①對(duì)比不同配置條件下交叉點(diǎn)提取坐標(biāo)和交叉點(diǎn)真實(shí)坐標(biāo)，計(jì)算圖像交叉點(diǎn)幾何中心定位誤差；②對(duì)比不同配置條件下交叉點(diǎn)檢測(cè)數(shù)量和圖像交叉點(diǎn)全部數(shù)量，計(jì)算圖像交叉點(diǎn)檢測(cè)率。

2.1 交叉角影響

仿真生成37×37的網(wǎng)格交叉點(diǎn)圖像，交叉角大小分別設(shè)置為90°、85°、80°、75°、65°和60°，交叉線寬為7像素，利用本文算法對(duì)圖像交叉點(diǎn)進(jìn)行檢測(cè)，高斯濾波器卷積模板為：

檢測(cè)結(jié)果如圖5所示。表1為不同交叉角配置下算法的檢測(cè)性能。結(jié)果表明：算法適用于交叉角為65°～90°范圍內(nèi)的交叉點(diǎn)檢測(cè)，幾何中心定位精度優(yōu)于0.6像素，檢測(cè)率接近100%；當(dāng)交叉角為60°時(shí)，算法對(duì)交叉點(diǎn)幾何中心的定位精度為5.5像素，檢測(cè)率僅為12%，算法失效。失效原因在于：隨著交叉角的減小，交叉線重疊區(qū)域變大，交叉點(diǎn)鄰域梯度分布不確定性增大，進(jìn)而使得特征描述子大概率不能通過(guò)交叉點(diǎn)判定準(zhǔn)則，最終影響算法定位精度及檢測(cè)率；算法的幾何中心定位精度和檢測(cè)率與交叉角大小不存在絕對(duì)的單調(diào)性關(guān)系，整體趨勢(shì)上，算法幾何中心定位精度和檢測(cè)率隨交叉角增大而提高，但在某些局部，算法定位精度和檢測(cè)率可能發(fā)生振蕩，如交叉角為75°和65°的情況。

表1 不同交叉角配置下算法檢測(cè)性能Tab.1 Detection functions of intersection points with different crossing angles

2.2 圖像旋轉(zhuǎn)角影響

仿真生成37×37的網(wǎng)格交叉點(diǎn)，交叉線寬為7像素，旋轉(zhuǎn)角大小分別設(shè)置為10°、30°、50°、60°、70°、80°，利用本文算法對(duì)圖像交叉點(diǎn)進(jìn)行檢測(cè)。高斯濾波器卷積模板與2.1節(jié)中相同，檢測(cè)結(jié)果如圖6所示，表2為不同旋轉(zhuǎn)角配置下算法的檢測(cè)性能。結(jié)果表明：算法可以很好地抵抗圖像旋轉(zhuǎn)，交叉點(diǎn)幾何中心定位精度優(yōu)于0.6像素，檢測(cè)率接近100%。算法旋轉(zhuǎn)不變的原因在于：圖像的整體旋轉(zhuǎn)只會(huì)影響交叉點(diǎn)鄰域梯度的絕對(duì)分布，梯度的相對(duì)分布并未發(fā)生變化，而本文提出的特征描述子及交叉點(diǎn)判定準(zhǔn)則只依賴于梯度的相對(duì)分布。

表2 不同旋轉(zhuǎn)角配置下算法檢測(cè)結(jié)果Tab.2 Detection results of intersection points with different image rotation angles

2.3 位置噪聲影響

受相機(jī)和投影儀元器件加工工藝水平限制，交叉點(diǎn)能量中心和幾何中心可能存在位置偏差，影響交叉點(diǎn)檢測(cè)性能。仿真生成37×37的網(wǎng)格交叉點(diǎn)，交叉角為90°，交叉線寬為7像素，向交叉點(diǎn)能量中心加入不同等級(jí)(0均值、標(biāo)準(zhǔn)差σ=0.0～3.0像素)的高斯位置噪聲，對(duì)交叉點(diǎn)幾何中心進(jìn)行檢測(cè)，結(jié)果如圖7所示。表3為不同位置噪聲等級(jí)下算法的檢測(cè)性能，結(jié)果表明：位置噪聲等級(jí)由0.0像素提高到3.0像素過(guò)程中，交叉點(diǎn)定位精度略有降低，但不明顯，檢測(cè)率均為100%。原因在于：算法采用灰度加權(quán)法計(jì)算交叉點(diǎn)幾何中心位置，對(duì)于能量中心和幾何中心存在偏差的交叉點(diǎn)，依然可保證較高的交叉點(diǎn)定位精度。

表3 不同位置噪聲等級(jí)下算法檢測(cè)性能Tab.3 Detection functions of intersection points with different position noise levels

2.4 灰度噪聲影響

電荷耦合器件(Charge Coupled Device,CCD)相機(jī)傳感器的噪聲源主要為暗電流噪聲和光子散粒噪聲，在數(shù)字圖像上則表現(xiàn)為椒鹽(顆粒)噪聲。仿真生成37×37的網(wǎng)格交叉點(diǎn)，交叉角為90°，交叉線寬為7像素，圖像灰度等級(jí)為0～255，向圖像中加入不同等級(jí)(σ=0.0～30.0像素)的椒鹽噪聲，計(jì)算不同信噪比條件下算法的檢測(cè)性能。信噪比定義如下：

(10)

式中：PS表示信號(hào)的有效功率；Pn表示噪聲的有效功率；信噪比越大，表明圖像質(zhì)量越高。仿真結(jié)果如圖8所示。表4為不同信噪比條件下算法檢測(cè)性能。結(jié)果表明：交叉點(diǎn)定位誤差隨信噪比的提高而減??；當(dāng)信噪比低于8.0 dB時(shí)，算法定位誤差大于5.0像素、檢測(cè)率低于50%，算法失效；當(dāng)信噪比為27.97 dB時(shí)，交叉點(diǎn)定位精度優(yōu)于0.5像素、檢測(cè)率為100%。目前科學(xué)級(jí)CCD相機(jī)的信噪比一般大于60 dB，可滿足算法的工程應(yīng)用需求。

表4 不同信噪比條件下算法檢測(cè)性能Tab.4 Detection functions of intersection points with different SNR

2.5 透視變換影響

仿真生成37×37的網(wǎng)格交叉點(diǎn)，交叉線寬為7像素，模擬相機(jī)對(duì)網(wǎng)格交叉點(diǎn)成像過(guò)程。若相機(jī)光軸垂直于網(wǎng)格平面，即為正視圖。在正視圖的基礎(chǔ)上，隨機(jī)改變光軸的空間指向，由于算法主要應(yīng)用于結(jié)構(gòu)光三維重建，因此設(shè)定光軸三自由度變動(dòng)范圍均小于30°，在此約束下，生成透視變換后的網(wǎng)格交叉點(diǎn)圖像。對(duì)圖像交叉點(diǎn)進(jìn)行檢測(cè)，高斯濾波器卷積模板與2.1節(jié)中相同。檢測(cè)結(jié)果如圖9所示。表5為不同透視變換配置下算法的檢測(cè)性能。結(jié)果表明：在上述實(shí)驗(yàn)條件下，算法可以很好地抵抗圖像透視變換，交叉點(diǎn)幾何中心定位精度優(yōu)于0.6像素，檢測(cè)率大于90%。

表5 不同透視變換配置下算法檢測(cè)性能Tab.5 Detection results of intersection points with different perspective transformations

3 結(jié)論

本文提出了一種基于梯度直方圖的圖像交叉點(diǎn)檢測(cè)方法，具有較高的交叉點(diǎn)定位精度和檢測(cè)率，可應(yīng)用于結(jié)構(gòu)光三維重建中的系統(tǒng)標(biāo)定和形貌測(cè)量。其特點(diǎn)可歸納如下：①對(duì)圖像交叉點(diǎn)中心的提取精度和檢測(cè)率基本不受圖像旋轉(zhuǎn)角大小的影響；②對(duì)于交叉角大小具有一定的容忍度，即可用于檢測(cè)交叉角在65°～90°之間的圖像交叉點(diǎn)；③抗噪性能良好，可滿足一般透視變換下的圖像交叉點(diǎn)檢測(cè)需求。

但是，本文方法對(duì)圖像交叉點(diǎn)的檢測(cè)不具有尺度不變性，圖像的放大或縮小會(huì)直接影響交叉點(diǎn)的檢測(cè)率和定位精度。考慮利用圖像金字塔[14]，在每一層圖像中獨(dú)立檢測(cè)、提取交叉點(diǎn)，然后基于歐式距離融合多尺度檢測(cè)結(jié)果。此外，多視圖之間的交叉點(diǎn)自動(dòng)匹配問(wèn)題也是下一步亟待解決的問(wèn)題。