一種應用于室內移動機器人的快速二維碼定位技術

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

【摘 要】針對室內結構化環境中移動機器人的定位問題，文章提出了一種具有自適應能力的閾值分割算法和幾何特征提取評價算子，能夠快速識別探測塊的位置，大幅度提高了定位和識別速率。文章利用MTALAB對算法進行了仿真分析，并在2.50 GHz主頻的CPU計算機上對算法的速率和準確性進行了驗證。結果證明，該技術相比傳統二維碼識別算法，在識別和定位速度上取得了很大的進步。

【關鍵詞】二維碼；幾何特征；參數學習

【中圖分類號】TP242 【文獻標識碼】A 【文章編號】1674-0688（2016）11-0043-03

室內移動機器人的定位和導航的研究一直是機器人領域的一大熱點，伴隨家庭服務機器人、倉儲式機器人的推廣應用，快速高效的室內移動機器人定位技術具有重要的研究意義。

目前，應用比較廣的定位方法中利用碼盤、加速度傳感器等實現的被動式傳感器定位方法的優點是成本低、可靠性高，但是不可避免地存在累積誤差。主動式傳感器定位方法中，路標定位是常用方法，該方法運用靈活、精度高，但是路標識別的效率是研究的難點。

1 二維碼定位和識別技術概述

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

2 二維碼初定位方法改進

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

本文將二維碼矩陣標簽設計成矩陣陣列，向8個方向分別擴展了一個碼的信息，增加了每個方向的容錯能力。目前，普遍應用的傳統的下采樣灰度差分投影法[4]不能滿足多碼識別的應用要求。本文以二維碼的探測塊作為初定位的識別目標，提出了一種改進的幾何特征評價算子，提高了初定位的識別速率。

2.1 圖像分割

2.1.1 閾值分割算法對比

圖像分割是進行幾何特征提取的前提。本文通過對幾種閾值分割方法進行實驗分析，提出了適合本文應用的實時性高并且降低非二維碼區域噪聲的閾值分割算法。

大津法[5]的基本原理是選取最佳閾值T將像素分為2個部分，使這2個部分類間方差取最大值。大津法中灰度變化較大區域的圖像灰度值對最佳閾值的決定權也較大，但是對于圖像中灰度分布的區域特征及灰度分布不均這些因素沒有設置評價函數進行克服。因此，大津法使用過程中對于灰度分布不均的現象會發生閾值分割失敗。

簡單統計法[6]的原理是將每一點對分割閾值的貢獻權重用每一點鄰域梯度值占梯度累加總和的比重來代替，進而計算出最終閾值。

綜合表1的時間效率對分割效果對比，可以看出大津法運行速度快、效果穩定，但是自適應能力有待改善。簡單統計法速度較慢，但是對單一碼閾值選取效果好，可以在對速度要求不高的訓練學習模型中作為閾值選取算法。

2.1.2 改進的基于閾值訓練模型的自適應變閾值分割法

本文在傳統算法的基礎上給出了一種以大津法為主體，結合訓練模型的自適應變閾值分割算法，而且由于訓練信息的引入縮小了大津法閾值選取的初始區間，進一步提升了閾值選擇的速率。本文論述改進的閾值分割算法中的訓練模型。首先對圖像分區，然后采用簡單統計法對訓練樣本中的每個單個二維碼進行閾值選取，獲得單個二維碼的碼上最優閾值。按照分區統計每個區域最優閾值的最大值Tmax和最小值Tmin。

區間[Tmin-a×T255，Tmax+a×T255]中a的取值根據訓練樣本與系統真正運行時的實驗圖像的新舊差距決定。如果新舊差距大，則a值選取大；反之，a值選取小。根據本文的實驗環境，新舊差距較小，設置a取0.2效果較好。

區間[Tmin-b×T255，Tmax+b×T255]中b值取值要求小于a值。對經過前一步篩選出來的閾值進行進一步的篩選。本區間用于為最優閾值的選取提供參考區間，去除掉根據訓練信息判定的不可能作為閾值區間的候選閾值。本實驗環境中b取0.1，得到了較好的實驗效果。

改進的結合訓練模型的閾值選取算法的總體流程如圖1所示。首先在每個區域訓練得到的初始區間[Tmin-a×T255，Tmax+a×T255]的指導下進行分區大津法閾值統計，獲得該區域的最優閾值。然后將該最優閾值與訓練獲得的預選區間[Tmin-b×T255，Tmax+b×T255]進行比較，看最優閾值是否在該區間之內。如果在該區間之內，則認為該區域內二維碼出現概率較高，并標記這樣的區域為可能有碼區域。在可能有碼區域中遵從T3、T2、T1的優先順序，選取該區域的最優閾值作為全局最優閾值，如果沒有可能有碼區域，直接選用T3區域的Tmin作為閾值對全圖像進行分割。

2.2 基于訓練信息的幾何特征提取初定位算法

二維碼的探測塊中心是一個黑色正方形連通域，具有規則易于提取的幾何特征。本文在對圖像進行連通域分析的基礎上，選用幾何復雜度算子對連通域進行評判，進而定位二維碼的探測塊圖形。

2.2.1 幾何特征提取

首先對圖像分割得到的二值圖像進行游程編碼[7]，然后對團塊進行連通域分析，簡稱BLOB分析。本文采取的BLOB算法是將目標像素聚合成連通的團塊，并返回團塊的面積、重心位置等信息。當團塊面積S滿足區間 [Smin，Sman]時被標記為候選連通域和分別表示探測塊的面積的上下限，是通過訓練模型得到的探測塊圖形的先驗信息。

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

本文利用復雜度算子作為特征評價函數對不同形狀的連通域進行區分。本論文選用的復雜度算子如公式（1），其含義是連通域周長的平方除以連通域的面積。

C=■（1）

本文中的目標探測塊為一個正方形，根據正方形周長和面積的關系，C取值為16。因為閾值分割可能會使得目標不是嚴格的正方形，復雜度算子的計算值可能會有誤差，所以選用通過訓練模型得到的復雜度算子的取值區間作為評價函數的評價區間。

2.2.2 幾何特征訓練模型

幾何特征訓練模型通過對待識別二維碼標簽的識別，獲得其探測塊中心正方形的面積和復雜度評價算子的取值，然后相應地擴展為一個評價區間，對候選連通域進行篩選。幾何特征模型需要的學習參數都可以通過預先對二維碼路標的訓練學習獲得。

3 實驗結果與分析

本節采用下采樣灰度差分投影法和改進后的算法進行實驗，對比算法的時間效率和穩定性。隨機選取250張實驗圖像進行算法時間統計，給出改進算法中各部分耗時的統計信息，見表2。

表3是傳統算法與改進之后算法探測塊初定位部分時間效率對比。可以看出改進之后的算法在運行速度較之傳統算法實現了2～3倍的提升，同時錯檢率低于1%，能夠穩定地為移動機器人提供地面坐標信息。

4 小結

本文根據二維碼探測塊的幾何特征設計了基于訓練信息的幾何特征評價算子，能夠快速地識別探測塊的位置。目標分割過程中，在對大量閾值分割算法實驗分析的基礎上，提出了一種基于訓練模型的自適應變閾值目標分割方法，克服了傳統閾值算法的弊端，兼顧了系統穩定性、快速性和準確性的均衡。基于訓練模型的幾何特征識別定位算法的運行速度較之傳統算法實現了2～3倍的提升，為二維碼的快速定位和識別問題提出了一種嶄新的解決方法。

參 考 文 獻

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

[2]屈衛鋒.低質量QR二維碼快速識別與軟件設計研究[D].咸陽：西北農林科技大學，2016.

[3]胡秋玉.QRcode識別算法的研究與改進[D].成都：西南石油大學，2014.

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

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

[6]王成順.表面缺陷檢測GPU并行圖像處理技術[D].合肥：合肥工業大學，2012.

[7]於正強.實時的圖像連通域分析算法設計與實現[D].杭州：浙江大學，2014.

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

[責任編輯：鐘聲賢]