目前，基于機器視覺的障礙物檢測方法大體上分為三類[1]。第一類方法是從單幅圖像中提取已知的障礙物[2]。這種方法的缺點是需要已知障礙物的2D圖像模式，或者需要一個學習階段。第二類方法是利用運動信息提取障礙物，其中最流行的方法是基于光流的障礙物檢測[3]。該類方法的缺點是運算量大，而且基于所求出的光流場分割障礙物仍然很困難。第三類方法是利用立體視覺方式提取障礙物，該類方法運算量大，通常需要專用的硬件[4]。本文提出的方法屬于第一類方法，但是省去了學習過程。此方法利用人們?nèi)缦碌南闰炛R：因為大多數(shù)人造物體呈現(xiàn)為棱柱狀、棱臺形狀或者圓柱、圓臺形狀，這些形狀左右邊緣表現(xiàn)為兩條直線段(如電線桿、燈柱、箱子、椅子、桌子等)，而且這兩條直線段中的像素點的梯度方向應該是對稱的，所以檢測出這些近似直線段的邊緣就可以重構物體輪廓，從而定位目標。

本文提出的算法主要由三步組成：首先計算原圖像中邊緣點的梯度值和梯度方向，并且按照"同一條直線段中像素點的梯度方向、梯度值相近似"的原則從邊緣點圖像中提取出直線段；然后利用提取出來的直線段的各種屬性(長度、梯度方向、位置)、兩條直線段之間像素點的灰度直方圖以及背景灰度直方圖對直線段進行匹配，搜索出分別對應于各個物體左右邊緣的兩兩相對的直線段；最后按照匹配函數(shù)計算出匹配值重構"障礙物"輪廓，并確定其位置。

1邊緣點的提取

本文使用Soble算子(如圖1)計算邊緣點梯度值，并利用公式(1)～(3)計算出梯度向量的方向角，從而構造梯度圖像[5]。本文采用一種基于視覺模型的邊緣檢測閾值選擇策略[6]進行梯度圖像的自適應閾值的設定，即利用公式(4)進行閾值設定。

式中，Gx是Soble算子的水平模板；Gy是Soble算子的垂直模板；α(x，y)是梯度向量的方向角；I為背亮度灰度值，也就是象素點的灰度值，I小于a的區(qū)域為低暗區(qū)，I大于b的區(qū)域為高亮區(qū)，I在a和b之間為中間區(qū)；△I為所定閾值，灰度級為256級；α、β和C為待定參數(shù)。

對梯度圖進行"空穴撿出"，刪除由相互連通的邊緣點組成的小塊區(qū)域。因為小塊區(qū)域大多由噪聲產(chǎn)生，就算是真正的邊緣點，它們對算法也不起作用，所以可刪除它們以降低算法復雜度。

2直線段的提取

通過綜合相位編組法與邊界跟蹤法的優(yōu)點，本文提出一種新的直線段的提取方法。這種方法能檢測到階躍形和屋頂形的直線邊緣，同時也適用于單像素和多像素寬度的直線邊緣的檢測。

首先，對邊緣點的梯度向量的方向角進行方向離散化，即將其分為0度、45度、135度、180度、270度和315度六個方向類型(如圖2)。邊緣點的梯度向量的方向角與哪個方向類型的差最小，就把邊緣點歸為哪個類型。同屬于一個方向類型的邊緣點互為"同類型邊緣點"，同屬于一個類型的直線段互為"同類型直線段"。

然后，在垂直于梯度方向角度的方向上的鄰域內(nèi)依次對連通的同類型邊緣點搜索并連接，組合成的集合稱為線段子元。由于物體的邊緣可能出現(xiàn)斷裂，以及邊緣大多不是單像素寬度，所以還要對線段子元進行組合，構造線段元[7]。

定義1線段子元：連通的同類型邊緣點的集合。

定義2線段元：同類型的并且相互間有連接點的線段子元組合成的集合。

由以上的定義可知，線段子元是線段元的子集，一個線段元可由一個也可由多個線段子元構成。本算法的輸入是梯度圖，輸出是對應圖像中物體左右邊緣的各條線段。整個算法流程如下所述。其中，line-Sub-Cell、line-Cell和line-Segment分別表示存儲線段子元、線段元和線段的結構。

Step1：依次掃描梯度圖像，取第一個未檢測到的邊緣點為邊界跟蹤起點Pi(i=0)。將Pi作為第一個像素保存到線段子元line-Sub-Cell中。

Step2：i=i+1，利用邊界跟蹤算法沿著跟梯度方向垂直的方向跟蹤下一個邊界點，根據(jù)定義1確定Pi是否屬于當前線段子元line-Sub-Cell。若屬于則將Pi保存到Line-Sub-Cell中，重復Step2；否則當前線段子元Line-Sub-Cell即為一個完整的線段子元，將其保存，并轉Step1。

Step3：對存儲了線段子元的數(shù)組依次掃描。取第一個未檢測到的線段子元為初始線段子元Qj(j=0)。將Qj作為第一個線段子元保存到線段元Line-Cell中。

Step4：j=j+1，根據(jù)定義2判斷Qj是否屬于當前線段元Line-Cell。若屬于將Qj加人Line-Cell中，然后重復Step4；否則當前線段元Line-Cell即為一個完整的線段元，并轉Step3。

Step5：按照以下的準則(準則1)合并線段元Line-Cell，構成直線段line-Segment。

準則1：判斷線段元Line-Cell是否屬于線段line-Segment的準則，判斷兩線段元的端點是否相鄰(或接近)，并且兩線段元斜率的偏轉角是否接近。若滿足上述條件即可將兩線段元連接起來，則形成一條較長的線段。

3直線段的兩兩匹配與輪廓重構

因為一個物體的左右兩邊邊緣點的梯度方向應該具有相互對稱的屬性，所以按照直線段上邊緣點的Gy的值GradValue(見公式(2))將直線段分為兩種極性：一種是GradValue>0，稱為正直線段；一種是GradValue<0，稱為負直線段。

首先，從包含所有正直線段的集合D1和包含所有負直線段的集合D2中依次各選取一條直線段。如果選取的兩條直線段滿足以下三個條件，則稱它們是一組"候選直線段對"[8]。

(1)圖像中這兩條直線段中心點的位置在Y坐標軸上的差小于一個閾值P1，在X坐標軸上的差大于一個閾值P2。P1、P2的值可根據(jù)圖像大小設定。

(2)兩條直線段的長度相差不大。

(3)兩條直線段的梯度方向對稱。假設左邊的直線段為正直線段，右邊的直線段為負直線段，則左右兩直線段的梯度方向如圖3所示。如果左邊的直線段為負直線段，右邊的直線段為正直線段，則把將梯度方向互換一下位置即可。[!--empirenews.page--]

然后，根據(jù)每組"候選直線段對"間內(nèi)部像素點的灰度直方圖計算這兩條線段的相關性。因為屬于同一個物體的像素點的灰度直方圖有一個明顯的凸峰，所以把凸峰占整個直方圖面積的百分比作為計算"候選直線段對"相關性的第一個度量值定為inner_rela。

屬于物體中的像素點的灰度值與它所處背景的像素點的灰度值相差比較大。所以把計算"候選直線段對"相關性的第二個度量值定為

。T1為兩直線段間像素的灰度平均值，T2為兩直線段構成區(qū)域的背景灰度平均值。因為

，所以把exter_rela除以255(作歸一處理)，使得

。

總的相關性度量值=inner_rela×exter_rela。如果總的相關性度量值超過一定的閾值，則這一組"候選直線段對"屬于同一個物體的左右邊緣。

inner_rela的計算方法介紹如下：

Stepl：計算這兩條直線段之間的區(qū)域中的像素點的灰度分布直方圖。

Step2：直方圖存在一個明顯的凸峰，計算出凸峰的位置Peak，并取凸峰鄰域為[Peak-T，Peak+T]，本文取T=32。對灰度值處在凸峰鄰域[Peak-T，Peak+T]的像素點的個數(shù)進行累加，累加值Count存儲到變量中。

Step3：inner_rela=Count／(整個直方圖象素點的總數(shù))。

最后，把配對成功的"候選直線段對"的相應端點進行連接，構造出的四邊形作為物體的抽象輪廓。因為這些四邊形之間會產(chǎn)生連接、包含、重疊等現(xiàn)象，所以取經(jīng)過輪廓疊加產(chǎn)生的圖像做為最終目標圖像，從而在圖像中實現(xiàn)對物體的定位。

4實驗分析

本算法在室內(nèi)進行了大量實驗后發(fā)現(xiàn)，對圖像中存在的棱柱狀、棱臺形狀物體以及圓柱狀、圓臺形狀物體能夠實現(xiàn)90％的檢測率；而對邊緣為曲線的物體以及其他不規(guī)則物體的檢測就根本不適用了。當評判匹配相關性的閾值設得偏大時"漏檢"的概率變大，"偽檢"的概率變小，反之亦然。

本文算法對于一副圖像的測試結果如圖4(a)～(e)所示，移動機器人平臺上的彩色CCD攝像頭拍攝的圖像包含了一個紙箱、一個疊加在紙箱上的黑色鋼管以及一個低矮的黃色木頭盒子。對彩色圖像運用顏色轉換程序，轉換成灰度圖(圖4(a))；在線段圖(圖4(d))中灰度值為128的線段是負線段，灰度值為0的線段是正線段；輸出的最終結果(圖(4)e)中直線配對每成功一次，相應的區(qū)域像素點的灰度值減去100。

本文提出的利用直線段匹配檢測障礙物的方法，不需要事先學習障礙物的2D圖像模式，避免了使用計算量大的光流法和立體視覺方法。試驗結果表明該方法能有效地實時檢測障礙物。

下一步還需要研究如何將圖像檢測出的障礙物信息與移動機器人的激光雷達數(shù)據(jù)相融合，以及加入距離信息來提高障礙物檢測的準確率和可靠性。