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

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

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

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

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

式中，Gx是Soble算子的水平模板；Gy是Soble算子的垂直模板；α(x，y)是梯度向量的方向角；I為背亮度灰度值，也就是象素點(diǎn)的灰度值，I小于a的區(qū)域?yàn)榈桶祬^(qū)，I大于b的區(qū)域?yàn)楦吡羺^(qū)，I在a和b之間為中間區(qū)；△I為所定閾值，灰度級(jí)為256級(jí)；α、β和C為待定參數(shù)。

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

2直線段的提取

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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