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

目前，基于機(jī)器視覺(jué)的障礙物檢測(cè)方法大體上分為三類[1]。第一類方法是從單幅圖像中提取已知的障礙物[2]。這種方法的缺點(diǎn)是需要已知障礙物的2D圖像模式，或者需要一個(gè)學(xué)習(xí)階段。第二類方法是利用運(yùn)動(dòng)信息提取障礙物，其中最流行的方法是基于光流的障礙物檢測(cè)[3]。該類方法的缺點(diǎn)是運(yùn)算量大，而且基于所求出的光流場(chǎng)分割障礙物仍然很困難。第三類方法是利用立體視覺(jué)方式提取障礙物，該類方法運(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]。本文采用一種基于視覺(jué)模型的邊緣檢測(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，稱為正直線段；一種是GradValue<0，稱為負(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ù)直線段，右邊的直線段為正直線段，則把將梯度方向互換一下位置即可。[!--empirenews.page--]

然后，根據(jù)每組"候選直線段對(duì)"間內(nèi)部像素點(diǎn)的灰度直方圖計(jì)算這兩條線段的相關(guān)性。因?yàn)閷儆谕粋€(gè)物體的像素點(diǎn)的灰度直方圖有一個(gè)明顯的凸峰，所以把凸峰占整個(gè)直方圖面積的百分比作為計(jì)算"候選直線段對(duì)"相關(guān)性的第一個(gè)度量值定為inner_rela。

屬于物體中的像素點(diǎn)的灰度值與它所處背景的像素點(diǎn)的灰度值相差比較大。所以把計(jì)算"候選直線段對(duì)"相關(guān)性的第二個(gè)度量值定為

。T1為兩直線段間像素的灰度平均值，T2為兩直線段構(gòu)成區(qū)域的背景灰度平均值。因?yàn)?/p>

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

。

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

inner_rela的計(jì)算方法介紹如下：

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

Step2：直方圖存在一個(gè)明顯的凸峰，計(jì)算出凸峰的位置Peak，并取凸峰鄰域?yàn)閇Peak-T，Peak+T]，本文取T=32。對(duì)灰度值處在凸峰鄰域[Peak-T，Peak+T]的像素點(diǎn)的個(gè)數(shù)進(jìn)行累加，累加值Count存儲(chǔ)到變量中。

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

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

4實(shí)驗(yàn)分析

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

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

本文提出的利用直線段匹配檢測(cè)障礙物的方法，不需要事先學(xué)習(xí)障礙物的2D圖像模式，避免了使用計(jì)算量大的光流法和立體視覺(jué)方法。試驗(yàn)結(jié)果表明該方法能有效地實(shí)時(shí)檢測(cè)障礙物。

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