一種應(yīng)用于室內(nèi)移動(dòng)機(jī)器人的快速二維碼定位技術(shù)

曹琳 高皜 劉恩曉 胡鼎 李正軍

【摘 要】針對(duì)室內(nèi)結(jié)構(gòu)化環(huán)境中移動(dòng)機(jī)器人的定位問題，文章提出了一種具有自適應(yīng)能力的閾值分割算法和幾何特征提取評(píng)價(jià)算子，能夠快速識(shí)別探測(cè)塊的位置，大幅度提高了定位和識(shí)別速率。文章利用MTALAB對(duì)算法進(jìn)行了仿真分析，并在2.50 GHz主頻的CPU計(jì)算機(jī)上對(duì)算法的速率和準(zhǔn)確性進(jìn)行了驗(yàn)證。結(jié)果證明，該技術(shù)相比傳統(tǒng)二維碼識(shí)別算法，在識(shí)別和定位速度上取得了很大的進(jìn)步。

【關(guān)鍵詞】二維碼；幾何特征；參數(shù)學(xué)習(xí)

【中圖分類號(hào)】TP242 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】1674-0688（2016）11-0043-03

室內(nèi)移動(dòng)機(jī)器人的定位和導(dǎo)航的研究一直是機(jī)器人領(lǐng)域的一大熱點(diǎn)，伴隨家庭服務(wù)機(jī)器人、倉儲(chǔ)式機(jī)器人的推廣應(yīng)用，快速高效的室內(nèi)移動(dòng)機(jī)器人定位技術(shù)具有重要的研究意義。

目前，應(yīng)用比較廣的定位方法中利用碼盤、加速度傳感器等實(shí)現(xiàn)的被動(dòng)式傳感器定位方法的優(yōu)點(diǎn)是成本低、可靠性高，但是不可避免地存在累積誤差。主動(dòng)式傳感器定位方法中，路標(biāo)定位是常用方法，該方法運(yùn)用靈活、精度高，但是路標(biāo)識(shí)別的效率是研究的難點(diǎn)。

1 二維碼定位和識(shí)別技術(shù)概述

本文選取了貼于家居環(huán)境地板上的二維碼[1]作為路標(biāo)，每個(gè)路標(biāo)處的二維碼的碼值即為該點(diǎn)的坐標(biāo)值。該方法能夠及時(shí)校正累計(jì)誤差，確保定位精度。針對(duì)普遍存在于路標(biāo)識(shí)別算法中效率低下的問題，我們提出了一種基于訓(xùn)練模型的幾何特征提取的二維碼快速識(shí)別方法。

2 二維碼初定位方法改進(jìn)

二維碼作為路標(biāo)使用時(shí)，通過圖像處理對(duì)二維碼進(jìn)行定位和識(shí)別流程[2]的一般步驟是首先對(duì)二維碼進(jìn)行初定位，然后采用普遍應(yīng)用的二維碼識(shí)別技術(shù)[3]進(jìn)行識(shí)別。本文通過改進(jìn)初定位算法的速率來提升二維碼識(shí)別和定位技術(shù)的時(shí)效性。

本文將二維碼矩陣標(biāo)簽設(shè)計(jì)成矩陣陣列，向8個(gè)方向分別擴(kuò)展了一個(gè)碼的信息，增加了每個(gè)方向的容錯(cuò)能力。目前，普遍應(yīng)用的傳統(tǒng)的下采樣灰度差分投影法[4]不能滿足多碼識(shí)別的應(yīng)用要求。本文以二維碼的探測(cè)塊作為初定位的識(shí)別目標(biāo)，提出了一種改進(jìn)的幾何特征評(píng)價(jià)算子，提高了初定位的識(shí)別速率。

2.1 圖像分割

2.1.1 閾值分割算法對(duì)比

圖像分割是進(jìn)行幾何特征提取的前提。本文通過對(duì)幾種閾值分割方法進(jìn)行實(shí)驗(yàn)分析，提出了適合本文應(yīng)用的實(shí)時(shí)性高并且降低非二維碼區(qū)域噪聲的閾值分割算法。

大津法[5]的基本原理是選取最佳閾值T將像素分為2個(gè)部分，使這2個(gè)部分類間方差取最大值。大津法中灰度變化較大區(qū)域的圖像灰度值對(duì)最佳閾值的決定權(quán)也較大，但是對(duì)于圖像中灰度分布的區(qū)域特征及灰度分布不均這些因素沒有設(shè)置評(píng)價(jià)函數(shù)進(jìn)行克服。因此，大津法使用過程中對(duì)于灰度分布不均的現(xiàn)象會(huì)發(fā)生閾值分割失敗。

簡(jiǎn)單統(tǒng)計(jì)法[6]的原理是將每一點(diǎn)對(duì)分割閾值的貢獻(xiàn)權(quán)重用每一點(diǎn)鄰域梯度值占梯度累加總和的比重來代替，進(jìn)而計(jì)算出最終閾值。

綜合表1的時(shí)間效率對(duì)分割效果對(duì)比，可以看出大津法運(yùn)行速度快、效果穩(wěn)定，但是自適應(yīng)能力有待改善。簡(jiǎn)單統(tǒng)計(jì)法速度較慢，但是對(duì)單一碼閾值選取效果好，可以在對(duì)速度要求不高的訓(xùn)練學(xué)習(xí)模型中作為閾值選取算法。

2.1.2 改進(jìn)的基于閾值訓(xùn)練模型的自適應(yīng)變閾值分割法

本文在傳統(tǒng)算法的基礎(chǔ)上給出了一種以大津法為主體，結(jié)合訓(xùn)練模型的自適應(yīng)變閾值分割算法，而且由于訓(xùn)練信息的引入縮小了大津法閾值選取的初始區(qū)間，進(jìn)一步提升了閾值選擇的速率。本文論述改進(jìn)的閾值分割算法中的訓(xùn)練模型。首先對(duì)圖像分區(qū)，然后采用簡(jiǎn)單統(tǒng)計(jì)法對(duì)訓(xùn)練樣本中的每個(gè)單個(gè)二維碼進(jìn)行閾值選取，獲得單個(gè)二維碼的碼上最優(yōu)閾值。按照分區(qū)統(tǒng)計(jì)每個(gè)區(qū)域最優(yōu)閾值的最大值Tmax和最小值Tmin。

區(qū)間[Tmin-a×T255，Tmax+a×T255]中a的取值根據(jù)訓(xùn)練樣本與系統(tǒng)真正運(yùn)行時(shí)的實(shí)驗(yàn)圖像的新舊差距決定。如果新舊差距大，則a值選取大；反之，a值選取小。根據(jù)本文的實(shí)驗(yàn)環(huán)境，新舊差距較小，設(shè)置a取0.2效果較好。

區(qū)間[Tmin-b×T255，Tmax+b×T255]中b值取值要求小于a值。對(duì)經(jīng)過前一步篩選出來的閾值進(jìn)行進(jìn)一步的篩選。本區(qū)間用于為最優(yōu)閾值的選取提供參考區(qū)間，去除掉根據(jù)訓(xùn)練信息判定的不可能作為閾值區(qū)間的候選閾值。本實(shí)驗(yàn)環(huán)境中b取0.1，得到了較好的實(shí)驗(yàn)效果。

改進(jìn)的結(jié)合訓(xùn)練模型的閾值選取算法的總體流程如圖1所示。首先在每個(gè)區(qū)域訓(xùn)練得到的初始區(qū)間[Tmin-a×T255，Tmax+a×T255]的指導(dǎo)下進(jìn)行分區(qū)大津法閾值統(tǒng)計(jì)，獲得該區(qū)域的最優(yōu)閾值。然后將該最優(yōu)閾值與訓(xùn)練獲得的預(yù)選區(qū)間[Tmin-b×T255，Tmax+b×T255]進(jìn)行比較，看最優(yōu)閾值是否在該區(qū)間之內(nèi)。如果在該區(qū)間之內(nèi)，則認(rèn)為該區(qū)域內(nèi)二維碼出現(xiàn)概率較高，并標(biāo)記這樣的區(qū)域?yàn)榭赡苡写a區(qū)域。在可能有碼區(qū)域中遵從T3、T2、T1的優(yōu)先順序，選取該區(qū)域的最優(yōu)閾值作為全局最優(yōu)閾值，如果沒有可能有碼區(qū)域，直接選用T3區(qū)域的Tmin作為閾值對(duì)全圖像進(jìn)行分割。

2.2 基于訓(xùn)練信息的幾何特征提取初定位算法

二維碼的探測(cè)塊中心是一個(gè)黑色正方形連通域，具有規(guī)則易于提取的幾何特征。本文在對(duì)圖像進(jìn)行連通域分析的基礎(chǔ)上，選用幾何復(fù)雜度算子對(duì)連通域進(jìn)行評(píng)判，進(jìn)而定位二維碼的探測(cè)塊圖形。

2.2.1 幾何特征提取

首先對(duì)圖像分割得到的二值圖像進(jìn)行游程編碼[7]，然后對(duì)團(tuán)塊進(jìn)行連通域分析，簡(jiǎn)稱BLOB分析。本文采取的BLOB算法是將目標(biāo)像素聚合成連通的團(tuán)塊，并返回團(tuán)塊的面積、重心位置等信息。當(dāng)團(tuán)塊面積S滿足區(qū)間 [Smin，Sman]時(shí)被標(biāo)記為候選連通域和分別表示探測(cè)塊的面積的上下限，是通過訓(xùn)練模型得到的探測(cè)塊圖形的先驗(yàn)信息。

對(duì)于前面獲得的候選連通域可以用8鄰域鏈碼提取輪廓的邊長(zhǎng)。8鄰域鏈碼法就是用8個(gè)代碼分別代表一個(gè)像素鄰域內(nèi)的8個(gè)像素，并用這8個(gè)代碼組成的鏈碼表示平面內(nèi)連續(xù)的線條圖像的編碼方法[8]。以前述的BLOB連通域分析篩獲得的重心點(diǎn)為搜索起點(diǎn)對(duì)連通域進(jìn)行鏈碼，得到鏈碼信息。并近似認(rèn)為邊界上水平和垂直方向移動(dòng)一個(gè)像素記為步長(zhǎng)1，斜對(duì)角方向的一個(gè)像素移動(dòng)設(shè)置為1.5。這樣由鏈碼就可以獲得連通域邊界的周長(zhǎng)。

本文利用復(fù)雜度算子作為特征評(píng)價(jià)函數(shù)對(duì)不同形狀的連通域進(jìn)行區(qū)分。本論文選用的復(fù)雜度算子如公式（1），其含義是連通域周長(zhǎng)的平方除以連通域的面積。

C=■（1）

本文中的目標(biāo)探測(cè)塊為一個(gè)正方形，根據(jù)正方形周長(zhǎng)和面積的關(guān)系，C取值為16。因?yàn)殚撝捣指羁赡軙?huì)使得目標(biāo)不是嚴(yán)格的正方形，復(fù)雜度算子的計(jì)算值可能會(huì)有誤差，所以選用通過訓(xùn)練模型得到的復(fù)雜度算子的取值區(qū)間作為評(píng)價(jià)函數(shù)的評(píng)價(jià)區(qū)間。

2.2.2 幾何特征訓(xùn)練模型

幾何特征訓(xùn)練模型通過對(duì)待識(shí)別二維碼標(biāo)簽的識(shí)別，獲得其探測(cè)塊中心正方形的面積和復(fù)雜度評(píng)價(jià)算子的取值，然后相應(yīng)地?cái)U(kuò)展為一個(gè)評(píng)價(jià)區(qū)間，對(duì)候選連通域進(jìn)行篩選。幾何特征模型需要的學(xué)習(xí)參數(shù)都可以通過預(yù)先對(duì)二維碼路標(biāo)的訓(xùn)練學(xué)習(xí)獲得。

3 實(shí)驗(yàn)結(jié)果與分析

本節(jié)采用下采樣灰度差分投影法和改進(jìn)后的算法進(jìn)行實(shí)驗(yàn)，對(duì)比算法的時(shí)間效率和穩(wěn)定性。隨機(jī)選取250張實(shí)驗(yàn)圖像進(jìn)行算法時(shí)間統(tǒng)計(jì)，給出改進(jìn)算法中各部分耗時(shí)的統(tǒng)計(jì)信息，見表2。

表3是傳統(tǒng)算法與改進(jìn)之后算法探測(cè)塊初定位部分時(shí)間效率對(duì)比。可以看出改進(jìn)之后的算法在運(yùn)行速度較之傳統(tǒng)算法實(shí)現(xiàn)了2～3倍的提升，同時(shí)錯(cuò)檢率低于1%，能夠穩(wěn)定地為移動(dòng)機(jī)器人提供地面坐標(biāo)信息。

4 小結(jié)

本文根據(jù)二維碼探測(cè)塊的幾何特征設(shè)計(jì)了基于訓(xùn)練信息的幾何特征評(píng)價(jià)算子，能夠快速地識(shí)別探測(cè)塊的位置。目標(biāo)分割過程中，在對(duì)大量閾值分割算法實(shí)驗(yàn)分析的基礎(chǔ)上，提出了一種基于訓(xùn)練模型的自適應(yīng)變閾值目標(biāo)分割方法，克服了傳統(tǒng)閾值算法的弊端，兼顧了系統(tǒng)穩(wěn)定性、快速性和準(zhǔn)確性的均衡?；谟?xùn)練模型的幾何特征識(shí)別定位算法的運(yùn)行速度較之傳統(tǒng)算法實(shí)現(xiàn)了2～3倍的提升，為二維碼的快速定位和識(shí)別問題提出了一種嶄新的解決方法。

參 考 文 獻(xiàn)

[1]Kato H，Tan K T.Pervasive 2D barcodes for camera phone applications[J].Pervasive Computing IEEE，2007，6（4）：76-85.

[2]屈衛(wèi)鋒.低質(zhì)量QR二維碼快速識(shí)別與軟件設(shè)計(jì)研究[D].咸陽：西北農(nóng)林科技大學(xué)，2016.

[3]胡秋玉.QRcode識(shí)別算法的研究與改進(jìn)[D].成都：西南石油大學(xué)，2014.

[4]劉家昕，劉家朋，趙宇明.基于邊緣增強(qiáng)的二維碼區(qū)域快速檢測(cè)定位算法[J].Computer Engineering，2012，38（12）.

[5]王璇，張帆，程京.基于改進(jìn)最大類間方差法的灰度圖像分割[J].微計(jì)算機(jī)信息，2010，26（35）：206-207.

[6]王成順.表面缺陷檢測(cè)GPU并行圖像處理技術(shù)[D].合肥：合肥工業(yè)大學(xué)，2012.

[7]於正強(qiáng).實(shí)時(shí)的圖像連通域分析算法設(shè)計(jì)與實(shí)現(xiàn)[D].杭州：浙江大學(xué)，2014.

[8]王競(jìng)雪，宋偉東，趙麗科，等.改進(jìn)的Freeman鏈碼在邊緣跟蹤及直線提取中的應(yīng)用研究[J].信號(hào)處理，2014，30（4）：422-430.

[責(zé)任編輯：鐘聲賢]