基于直線(xiàn)段匹配的移動(dòng)機器人的障礙物檢測

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

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

1邊緣點(diǎn)的提取

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

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

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

2直線(xiàn)段的提取

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

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

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

定義1線(xiàn)段子元：連通的同類(lèi)型邊緣點(diǎn)的集合。

定義2線(xiàn)段元：同類(lèi)型的并且相互間有連接點(diǎn)的線(xiàn)段子元組合成的集合。

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

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

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

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

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

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

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

3直線(xiàn)段的兩兩匹配與輪廓重構

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

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

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

(2)兩條直線(xiàn)段的長(cháng)度相差不大。

(3)兩條直線(xiàn)段的梯度方向對稱(chēng)。假設左邊的直線(xiàn)段為正直線(xiàn)段，右邊的直線(xiàn)段為負直線(xiàn)段，則左右兩直線(xiàn)段的梯度方向如圖3所示。如果左邊的直線(xiàn)段為負直線(xiàn)段，右邊的直線(xiàn)段為正直線(xiàn)段，則把將梯度方向互換一下位置即可。