基于直線段匹配的移動機(jī)器人的障礙物檢測

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

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

1邊緣點的提取

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

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

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

2直線段的提取

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

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

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

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

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

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

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

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

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

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

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

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

3直線段的兩兩匹配與輪廓重構(gòu)

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

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

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

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

(3)兩條直線段的梯度方向?qū)ΨQ。假設(shè)左邊的直線段為正直線段，右邊的直線段為負(fù)直線段，則左右兩直線段的梯度方向如圖3所示。如果左邊的直線段為負(fù)直線段，右邊的直線段為正直線段，則把將梯度方向互換一下位置即可。