劉堅(jiān)強(qiáng)，屈也頻，呂余海

（中國(guó)人民解放軍海軍研究院，上海 200436）

0 引言

在無(wú)人機(jī)自動(dòng)起降、工業(yè)機(jī)器人、交通自動(dòng)控制等工程化應(yīng)用中，都需要使用特定編碼進(jìn)行目標(biāo)快速識(shí)別，如有學(xué)者使用合作二維碼估計(jì)無(wú)人機(jī)上攝像機(jī)的相對(duì)位姿［1］。這類編碼使用時(shí)面臨著污漬、遮擋、光照陰影、雨水、破損等惡劣污染環(huán)境，且對(duì)可靠性、識(shí)別解碼速度相較于傳統(tǒng)的支付、購(gòu)物、聊天、注冊(cè)等應(yīng)用更為嚴(yán)格。如何設(shè)計(jì)抗污染能力強(qiáng)、識(shí)別速度快的目標(biāo)識(shí)別碼，是工程化應(yīng)用中首先應(yīng)該解決的問題。

目標(biāo)識(shí)別碼有多種樣式，如一維條碼、二維點(diǎn)陣碼、立體碼等，其中二維點(diǎn)陣碼具有簡(jiǎn)潔、信息量多、容易制作等特點(diǎn)，成為目標(biāo)識(shí)別碼的主流。二維點(diǎn)陣碼是用某種特定的幾何圖形按一定規(guī)律在平面（二維方向上）分布的黑白/彩色相間記錄數(shù)據(jù)符號(hào)信息的圖形［2］。常見的編碼有快速響應(yīng)矩陣（Quick Response，QR）碼、數(shù)據(jù)矩陣（Data Matrix，DM）碼、PDF417、Code 16K 等。

在工程化應(yīng)用中提高二維碼抗污染能力的做法包括增大二維碼碼點(diǎn)、補(bǔ)光、設(shè)置穩(wěn)定平臺(tái)、人工維護(hù)等方式，屈也頻等［3］對(duì)污染環(huán)境下的合作目標(biāo)設(shè)計(jì)提出了信息冗余等設(shè)計(jì)原則，但最根本的解決方法是采用更加高效的編碼、解碼算法以及圖像處理。

在編碼方面，通常采用差錯(cuò)控制編碼技術(shù)，在編碼受到污染出現(xiàn)錯(cuò)誤數(shù)據(jù)時(shí)，仍然能通過糾錯(cuò)技術(shù)正確識(shí)別編碼，該技術(shù)是適應(yīng)數(shù)字通信抗噪聲干擾的需要而發(fā)展起來(lái)的。1948 年，著名的信息論創(chuàng)始人Shannon 指出，可以通過差錯(cuò)控制碼在信息傳輸速率不大于信道容量的前提下實(shí)現(xiàn)可靠通信。隨后，Hamming 和Golay 提出了第一個(gè)實(shí)用的差錯(cuò)控制編碼方案，將數(shù)據(jù)分成數(shù)據(jù)塊，對(duì)每一塊進(jìn)行獨(dú)立編碼和解碼，稱為分組碼［4］。為了提高編碼效率，分組碼的數(shù)據(jù)結(jié)構(gòu)和算法不斷優(yōu)化，其中最為重要的子集是二元的BCH（Bose-Chaudhuri-Hocquenghem）碼，它有嚴(yán)密的代數(shù)理論，是目前研究最透徹的一類碼，具有糾錯(cuò)率高、結(jié)構(gòu)簡(jiǎn)單等特點(diǎn)［4］。將BCH 碼擴(kuò)展到非二元時(shí)，產(chǎn)生了里德-所羅門（Reed-Solomon，RS）碼。在通信中，為了解決分組碼存在延時(shí)大和需要精確幀同步等問題，又出現(xiàn)了卷積碼，將通信數(shù)據(jù)流中不同數(shù)據(jù)塊之間建立關(guān)系，后續(xù)的還有低密度奇偶校驗(yàn)（Low Density Parity Check，LDPC）碼、Tanner 圖、極化碼（Polar code）、Turbo 碼等［5］。

差錯(cuò)控制編碼在二維碼技術(shù)中也得到廣泛使用，由于編碼點(diǎn)陣固定，分組碼正好滿足該特點(diǎn)，尤其是BCH 和RS 碼（多元BCH 碼）得到了廣泛應(yīng)用［6-7］，如手機(jī)支付、通信、防疫和控制領(lǐng)域中最常見的QR 二維碼，國(guó)家標(biāo)準(zhǔn)GB/T 18284—2000《快速響應(yīng)矩陣碼（QR）》對(duì)此進(jìn)行了詳細(xì)規(guī)定［8］，核心信息數(shù)據(jù)編碼就是BCH 碼和RS 碼。其他的卷積碼等并不是特別適合在二維碼中應(yīng)用，如廖景輝［9］研究了將通信中常用的Turbo 碼和Polar 碼等應(yīng)用到二維碼中，但也提出這些算法在碼長(zhǎng)較長(zhǎng)時(shí)才具有較好的糾錯(cuò)能力，而且算法會(huì)隨著碼長(zhǎng)增加而越加復(fù)雜。

解碼是編碼的反向工程，解碼前通常需要進(jìn)行圖像處理，包括圖像增強(qiáng)、濾波、二值化、透視變換、去陰影等過程，進(jìn)而獲得編碼點(diǎn)信息，然后對(duì)編碼點(diǎn)進(jìn)行解碼和糾錯(cuò)，獲得二維碼表達(dá)的信息，有關(guān)圖像處理的國(guó)內(nèi)外相關(guān)研究文獻(xiàn)較多，如針對(duì)復(fù)雜光照等情況下對(duì)QR 算法進(jìn)行優(yōu)化［10］。

上述基于BCH 和RS 編碼的二維碼具有較好的效果，但是在使用中仍然存在一些問題：

1）算法較為復(fù)雜，復(fù)雜度隨碼長(zhǎng)的增加快幅增長(zhǎng)，解碼時(shí)間長(zhǎng)，難以滿足一些在運(yùn)動(dòng)中快速識(shí)別的應(yīng)用要求，限制了算法在工程上的推廣應(yīng)用。如為了提高BCH 解碼速度，采用基于現(xiàn)場(chǎng)可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）的并行算法［11-12］，代價(jià)較大。

2）所有數(shù)據(jù)位之間都有嚴(yán)格的邏輯關(guān)系，解碼算法與編碼算法一般是對(duì)應(yīng)的，具有單一性，難以引入其他算法，一旦誤碼數(shù)據(jù)超過本身算法所允許的糾錯(cuò)能力時(shí)，就很難識(shí)別準(zhǔn)確，識(shí)別率會(huì)大幅減低。如任亞博等［13］對(duì)BCH 碼進(jìn)行優(yōu)化，但是污染比例較低時(shí)才有效；吳昭軍等［14］提出了一種基于平均余弦符合度的識(shí)別算法，用于低信噪比時(shí)的BCH 碼識(shí)別，但是以時(shí)間為代價(jià)。

3）在復(fù)雜環(huán)境的工程化應(yīng)用中，在污染、破損等比較惡劣時(shí)，抗污染能力難以提高。曹濟(jì)英［15］雖然對(duì)QR、DM 兩種碼提出了若干優(yōu)化算法，但也提出在破損等情況下，識(shí)別率會(huì)變低。

4）實(shí)際工程化應(yīng)用中，為了提高抗污染能力，編碼點(diǎn)不能太少，但二維碼面積區(qū)域有限，編碼點(diǎn)數(shù)量不能太多，由此限制了長(zhǎng)碼的使用。張多利等［16］研究了縮短BCH（36，24，5）碼的應(yīng)用，有一定效果。

因此，構(gòu)造抗污染能力強(qiáng)、碼點(diǎn)少、算法簡(jiǎn)單、識(shí)別速度快、便于推廣應(yīng)用的二維碼是一個(gè)工程應(yīng)用的現(xiàn)實(shí)需求。

1 碼污染模型

首先研究實(shí)際環(huán)境中二維碼污染模型。通過觀察不難發(fā)現(xiàn)，污漬、遮擋、光照陰影、雨水、破損等各種惡劣環(huán)境都會(huì)污染二維碼。對(duì)于均勻的椒鹽污染，可采用適當(dāng)增大編碼點(diǎn)面積而很容易解決，因此需要重點(diǎn)關(guān)注隨機(jī)塊狀污染，也就是成塊的數(shù)據(jù)被改變。數(shù)據(jù)被污染的嚴(yán)重程度可用污染比例表示，即被污染點(diǎn)數(shù)量和總編碼點(diǎn)數(shù)量之比，被污染點(diǎn)是指在受到污染時(shí)，被識(shí)別為固定的1 或0（污染碼）的編碼點(diǎn)，與編碼點(diǎn)未被污染時(shí)所代表的數(shù)據(jù)（0 或1）無(wú)關(guān)。

隨機(jī)塊狀污染的數(shù)學(xué)模型，是在m×n編碼點(diǎn)陣區(qū)域內(nèi)隨機(jī)產(chǎn)生一個(gè)多邊形凹凸區(qū)域，區(qū)域覆蓋的碼點(diǎn)數(shù)量從1 到m×n個(gè)碼點(diǎn)，區(qū)域內(nèi)所有碼點(diǎn)數(shù)據(jù)變?yōu)槲廴敬a（0 或者1），多邊形凹凸區(qū)域的頂點(diǎn)坐標(biāo)集合G見式（1）：

生成多邊形凹凸區(qū)域時(shí)，以編碼點(diǎn)陣中的任意一點(diǎn)(x0，y0)為中心點(diǎn)，從該點(diǎn)出發(fā)，圍繞該點(diǎn)產(chǎn)生i條線段，數(shù)量一般為3～10，線段的角度為θi，每條線段的長(zhǎng)度li都不同，在一個(gè)固定長(zhǎng)度r0上再疊加隨機(jī)長(zhǎng)度di，di小于編碼點(diǎn)陣Am×n的行數(shù)m和列數(shù)n之和，由此產(chǎn)生線段的另一端坐標(biāo)為(xi，yi)，所有線段端點(diǎn)按序組成集合{(xi，yi)}，記為G，連接所有端點(diǎn)，產(chǎn)生多邊形凹凸區(qū)域，示例見圖1。

圖1 污染區(qū)域示例Fig.1 Example of polluted area

污染模型除了形狀外，還有污染點(diǎn)所代表的數(shù)據(jù)。污染點(diǎn)數(shù)據(jù)是指應(yīng)用系統(tǒng)經(jīng)過各種圖像處理后得到的編碼點(diǎn)所代表的數(shù)據(jù)（0 或1），由于不同環(huán)境時(shí)的污染物不同，如黑色輪胎印、白色油漆、泥土、深色樹葉等，產(chǎn)生“0”和“1”污染的概率也不相同，需要根據(jù)具體場(chǎng)景進(jìn)行確定。

2 極短糾錯(cuò)碼編碼、編排和解碼設(shè)計(jì)

2.1 極短糾錯(cuò)碼設(shè)計(jì)

當(dāng)前，BCH 等編碼在二維碼設(shè)計(jì)中普遍使用，但應(yīng)用于戶外容易污染、對(duì)識(shí)別速度要求高的場(chǎng)合時(shí)，存在算法復(fù)雜、編碼長(zhǎng)、適應(yīng)性差等缺點(diǎn)，為此本文提出了一種抗污染的極短糾錯(cuò)碼。

設(shè)目標(biāo)數(shù)據(jù)為D，二進(jìn)制長(zhǎng)度為l，二進(jìn)制數(shù)為AD=[al…ai…a1]，ai可表示信息“0”和“1”。在數(shù)據(jù)傳輸時(shí)，ai如果也只用1 個(gè)位表示，當(dāng)受到污染時(shí)，信息會(huì)變成1或0，無(wú)法得到正確信息，即無(wú)法糾錯(cuò)，因此需要用多個(gè)位（稱為碼）表示信息。

按照編碼理論，當(dāng)需要對(duì)長(zhǎng)度為n的碼中t個(gè)位進(jìn)行糾錯(cuò)時(shí)，碼的最小漢明距離dmin≥2t+1［4］，假設(shè)t取最小值1，那么dmin最小為3，對(duì)應(yīng)的碼長(zhǎng)n最小也為3，此時(shí)，按照最小漢明距離定義，這組碼中只能有兩個(gè)長(zhǎng)度為n=3 的碼字[a2，a1，a0]和[b2，b1，b0]，而且碼字中的碼元互為反碼，可取0 或1。

在此，將兩個(gè)碼字分別用來(lái)表示信息“0”和“1”，對(duì)應(yīng)目標(biāo)數(shù)據(jù)AD中的單個(gè)位，由于這是數(shù)據(jù)中的最小組成單元，因此將這兩個(gè)碼字組成的碼定義為極短糾錯(cuò)碼，簡(jiǎn)稱“極短碼”。采用編碼領(lǐng)域通常做法，記為J(3，1，1)，參數(shù)分別表示碼長(zhǎng)度n=3，信息長(zhǎng)度k=1，可糾錯(cuò)長(zhǎng)度t=1。滿足要求的碼字組合有8 種，如表1 所示。

表1 極短糾錯(cuò)碼碼字組合Tab.1 Code word combination of very short error correction code

其中[0，0，0] ?[1，1，1]、[1，1，1] ?[0，0，0]最為特殊，也就是a2=a1=a0、b2=b1=b0，組合[0，0，0] ?[1，1，1]可記為J(3，1，1)=[0，0，0]，用[0，0，0]表示0，[1，1，1]表示1；[1，1，1] ?[0，0，0]可記為J(3，1，1)=[1，1，1]。這兩組極短碼表述極為簡(jiǎn)潔，具有以下特點(diǎn)：

1）目標(biāo)數(shù)據(jù)中每一位都按照此編碼后，數(shù)據(jù)表現(xiàn)為三重冗余；具有優(yōu)良的單組碼糾錯(cuò)能力和編碼效能，與BCH 編碼比較見表2 和圖2。

2）需要的編碼點(diǎn)數(shù)量少，可以在非常有限的區(qū)域內(nèi)使用。當(dāng)可用區(qū)域較大時(shí)，也可以很方便地進(jìn)行擴(kuò)展，便于推廣應(yīng)用。

3）解碼時(shí)可以采用多種算法，解決了長(zhǎng)碼解碼算法的單一性問題，提高適應(yīng)不同區(qū)域糾錯(cuò)能力和識(shí)別速度。

為了評(píng)估極短碼的性能，將其和BCH 編碼進(jìn)行比較。

BCH 編碼表達(dá)式為BCH(n，k，t)，其中，n為編碼總長(zhǎng)度，k為信息碼元長(zhǎng)度，t為可糾錯(cuò)長(zhǎng)度，編碼后的碼字為，a為信息碼元，b為監(jiān)督碼元。

在各類碼中，編碼利用率和糾錯(cuò)能力是一對(duì)矛盾，提高糾錯(cuò)能力，必然降低編碼利用率，需要進(jìn)行權(quán)衡。為便于比較，將編碼利用率×糾錯(cuò)能力（k×2）定義為編碼效能。極短碼和典型BCH 編碼的編碼利用率、糾錯(cuò)能力和編碼效能見圖2 和表2。

從圖2 和表2 中可以看出以下特點(diǎn)：

表2 極短碼和典型BCH碼參數(shù)Tab.2 Parameters of very short code and typical BCH codes

1）在圖2 中，序號(hào)1 對(duì)應(yīng)的是極短糾錯(cuò)碼，序號(hào)2～21 對(duì)應(yīng)的是BCH 碼。編碼利用率曲線中，極短糾錯(cuò)碼為0.33，相對(duì)BCH 的0.158～0.9，為偏低水平；糾錯(cuò)能力曲線中，極短糾錯(cuò)碼為0.33，遠(yuǎn)高于BCH 的0.016～0.24；綜合后的編碼效能曲線中，極短糾錯(cuò)碼為0.11，遠(yuǎn)高于其他所有BCH 碼。

圖2 極短碼和BCH碼的編碼效能比較Fig.2 Comparison of coding efficiency between very short code and BCH code

2）在編碼效能曲線中，每一種長(zhǎng)度為3（極短碼）、7、15、31、63 的碼中都有一個(gè)最理想的均衡點(diǎn)，即編碼效能波峰，但是n越長(zhǎng)，波峰越小，極短碼具有最好的編碼效能。

3）對(duì)目標(biāo)數(shù)據(jù)用極短碼進(jìn)行編碼時(shí)，對(duì)每一位進(jìn)行編碼后再進(jìn)行組合，當(dāng)編碼點(diǎn)總長(zhǎng)度和糾錯(cuò)能力要求相同時(shí)，極短碼可表示的目標(biāo)數(shù)據(jù)長(zhǎng)度比BCH 的長(zhǎng)。

2.2 極短糾錯(cuò)編碼點(diǎn)編排設(shè)計(jì)

編排就是將經(jīng)過極短碼編碼的碼元放置在編碼點(diǎn)陣中。假設(shè)需要編碼的目標(biāo)數(shù)據(jù)為D，二進(jìn)制長(zhǎng)度為l，二進(jìn)制數(shù)為AD，每一位ai都按照極短碼編碼，得到包含A0、A1、A2三組數(shù)據(jù)的編碼矩陣An3。根據(jù)實(shí)際可用范圍，構(gòu)建m×n的二維碼點(diǎn)陣Bm×n，編碼點(diǎn)總數(shù)量不少于3l，見式（2）：

將An3中的數(shù)據(jù)編排到Bm×n中，包括兩種方式。

1）順序編排。將a11a21…al1、a12a22…al2、a13a23…al3按照橫向順序逐行依次排放到二維碼點(diǎn)陣中b11b12…b1nb21b21…b2n…bm1bm2…bmn，或者按照縱向順序逐列依次排放在b11b21…bm1b12b22…bm2…b1nb2n…bmn中，當(dāng)編碼點(diǎn)有空余時(shí)，填成0 或者1。

2）基于約束點(diǎn)陣域全局距離最優(yōu)的極短碼編排。該編排方法就是使得極短碼中3 個(gè)位之間的平均距離盡量大，綜合后的全局距離最優(yōu)，其實(shí)質(zhì)就是將突發(fā)錯(cuò)誤變成隨機(jī)錯(cuò)誤，將集中的錯(cuò)誤分散到各個(gè)碼組，使得每一組編碼中被污染的數(shù)據(jù)的數(shù)量小于糾錯(cuò)能力。

該方法分為3 步：首先，將a11a21…al1按順序放置在編碼點(diǎn)陣Bm×n起始點(diǎn)陣區(qū)域b11b12…或者b11b21…；然后，按照距離最優(yōu)算法將a13a23…al3放置在編碼點(diǎn)陣尾部點(diǎn)陣區(qū)域…bmn-1bmn或者…bm-1nbmn；最后，按照最優(yōu)距離算法，將a12a22…al2放置在編碼點(diǎn)陣中間點(diǎn)陣區(qū)域。其中開始區(qū)域、尾部區(qū)域和中間區(qū)域?yàn)轭A(yù)先指定的約束點(diǎn)陣域。

構(gòu)建最優(yōu)距離ηoptim，其基本原理是同一個(gè)數(shù)據(jù)位中的3個(gè)編碼點(diǎn)之間的距離越遠(yuǎn)，同時(shí)受到污染的概率就越低，從平均距離（davg）和散布標(biāo)準(zhǔn)差（dstd）兩個(gè)因素對(duì)所有編碼點(diǎn)進(jìn)行綜合考慮，得到整體最優(yōu)距離，見式（3）。即將A0、A1、A2按照排列形成l！個(gè)編碼方案，在每一種編碼方案中，計(jì)算編碼點(diǎn)陣Bm×n中單個(gè)[ai1，ai2，ai3]子編碼點(diǎn)兩兩之間的距離dij，再統(tǒng)計(jì)所有l(wèi)個(gè)子編碼距離的平均值davg和標(biāo)準(zhǔn)差dstd。平均距離越大且其散布的標(biāo)準(zhǔn)差越小，對(duì)應(yīng)的編碼方案為最優(yōu)方案。

式中：xij、yij、xi1、yi1為第i個(gè)子編碼中第j（或1）個(gè)編碼點(diǎn)在Bm×n中的行數(shù)和列數(shù)。

2.3 極短糾錯(cuò)碼解碼算法

極短碼在解碼時(shí)可以采用多種算法，不同于長(zhǎng)碼的算法單一性，包括：

1）2/3 準(zhǔn)則對(duì)每一位解碼，再組合算法。每一個(gè)數(shù)據(jù)位的3 個(gè)編碼點(diǎn)相同，即a2=a1=a0、b2=b1=b0，因此，無(wú)論何種污染，3 點(diǎn)中至少有2 個(gè)點(diǎn)的數(shù)據(jù)一致，將該數(shù)據(jù)作為目標(biāo)數(shù)據(jù)位，將所有數(shù)據(jù)位按照順序組合后作為目標(biāo)數(shù)據(jù)。

2）3 組數(shù)據(jù)加校驗(yàn)獨(dú)立解碼。由于每一個(gè)數(shù)據(jù)位的3 個(gè)編碼點(diǎn)相同，表現(xiàn)為3 冗余，組合后的3 組數(shù)據(jù)A0、A1、A2也相同。對(duì)每一組數(shù)據(jù)進(jìn)行獨(dú)立解碼時(shí)，采用奇偶校驗(yàn)位進(jìn)行查錯(cuò)，相校于BCH 碼，極短碼具有多余編碼點(diǎn)，可以在每一組數(shù)據(jù)中設(shè)置1 位奇偶校驗(yàn)碼。奇偶校驗(yàn)正確的數(shù)據(jù)，再按照2/3準(zhǔn)則確定目標(biāo)數(shù)據(jù)，如果3組數(shù)據(jù)均不相同，則無(wú)法解碼。

3）3 組數(shù)據(jù)拆分為多個(gè)子組加校驗(yàn)獨(dú)立解碼。當(dāng)多余編碼點(diǎn)數(shù)量較多時(shí)，可以將數(shù)據(jù)進(jìn)一步拆分為多個(gè)子組，每一個(gè)子組對(duì)應(yīng)一位奇偶校驗(yàn)碼，按照2/3 準(zhǔn)則確定子目標(biāo)數(shù)據(jù)，然后將多個(gè)子目標(biāo)數(shù)據(jù)進(jìn)行組合得到目標(biāo)數(shù)據(jù)。

4）根據(jù)目標(biāo)環(huán)境預(yù)估污染點(diǎn)數(shù)據(jù)進(jìn)行解碼。在實(shí)際應(yīng)用環(huán)境中，產(chǎn)生“0”和“1”污染的概率不相同，當(dāng)按照2/3 準(zhǔn)則和奇偶校驗(yàn)進(jìn)行解碼得不到準(zhǔn)確目標(biāo)數(shù)據(jù)時(shí)，可以根據(jù)具體環(huán)境中污染概率大小，將2/3 準(zhǔn)則中不是全部相同的點(diǎn)的目標(biāo)數(shù)據(jù)位更改為大概率數(shù)據(jù)，重新進(jìn)行校驗(yàn)解碼，提高識(shí)別率。

5）根據(jù)歷史記錄推斷。對(duì)于用戶和編碼相對(duì)固定的場(chǎng)景，當(dāng)出現(xiàn)污染嚴(yán)重?zé)o法得到目標(biāo)數(shù)據(jù)時(shí)，可以借助歷史記錄的特征進(jìn)行推斷。

解碼是編碼的反向操作，基本原則是解碼后輸出的目標(biāo)數(shù)據(jù)應(yīng)該是準(zhǔn)確的：如果無(wú)法得到準(zhǔn)確的目標(biāo)數(shù)據(jù)，就應(yīng)該報(bào)錯(cuò)。因此，綜合應(yīng)用上述算法可提高準(zhǔn)確率。

3 極短糾錯(cuò)編碼抗污染能力評(píng)估

3.1 抗污染能力評(píng)估

根據(jù)引言中描述，在主流二維碼中，BCH 是信息數(shù)據(jù)的核心編碼，因此，為了評(píng)估極短糾錯(cuò)碼的性能，以BCH 編碼算法作為參考對(duì)象。選擇BCH（63，18，10）作為評(píng)估基準(zhǔn)，編碼點(diǎn)數(shù)是極短碼編碼點(diǎn)數(shù)3 的整數(shù)倍，而且數(shù)量適中，63個(gè)編碼點(diǎn)可以排列在點(diǎn)陣中。由于BCH 碼只有一組，各數(shù)據(jù)位對(duì)于污染是同等的，編排順序不影響解碼結(jié)果，以縱向順序排列為例，點(diǎn)陣如圖3 所示。解碼采用Matlab 自帶的Berlekamp-Welch 算法［17］的bchenc 函數(shù)。

圖3 BCH（63，18，10）編碼點(diǎn)圖Fig.3 BCH（63，18，10）coding point diagram

為了和參考碼對(duì)應(yīng)，同樣選擇7×9 的二維碼點(diǎn)陣，k設(shè)為21，在BCH（63，18，10）的18 位數(shù)據(jù)基礎(chǔ)上，增加3 位奇偶校驗(yàn)碼，對(duì)應(yīng)將18 位數(shù)據(jù)拆分為3 個(gè)子組。

按照順序和最優(yōu)距離兩種方式對(duì)數(shù)據(jù)點(diǎn)進(jìn)行編排，點(diǎn)陣分別如圖4（a）（b）所示。解碼時(shí)綜合利用3.3 節(jié)中2/3 準(zhǔn)則和多個(gè)子組加校驗(yàn)獨(dú)立解碼兩種算法。

圖4 極短碼編碼點(diǎn)圖Fig.4 Very short code coding point diagram

鑒于本文關(guān)注的是數(shù)據(jù)的編碼性能，與圖像處理等無(wú)關(guān)，為了獲得大樣本量，采用計(jì)算機(jī)模擬仿真方式進(jìn)行評(píng)估。在Intel8700 計(jì)算機(jī)中采用Matlab 模擬產(chǎn)生3 萬(wàn)組隨機(jī)目標(biāo)數(shù)據(jù)，按照BCH 碼、順序編排極短碼、最優(yōu)距離編排極短碼對(duì)目標(biāo)數(shù)據(jù)進(jìn)行編碼，產(chǎn)生編碼點(diǎn)陣，再按照第1 章中所述隨機(jī)塊狀模型構(gòu)建多邊形凹凸區(qū)域，區(qū)域覆蓋點(diǎn)數(shù)從1 個(gè)點(diǎn)到所有63 個(gè)點(diǎn)，將區(qū)域作為污染覆蓋到編碼點(diǎn)陣上，將污染的編碼點(diǎn)設(shè)置為固定的0 或者1，對(duì)所有編碼點(diǎn)進(jìn)行解碼，比較解碼的數(shù)據(jù)和目標(biāo)數(shù)據(jù)，統(tǒng)計(jì)編碼識(shí)別準(zhǔn)確率和污染比例的關(guān)系，結(jié)果如圖5 所示。

圖5 隨機(jī)塊狀污染情況下的碼識(shí)別準(zhǔn)確率Fig.5 Code recognition accuracy in case of random block pollution

從圖5 中可以看出，在出現(xiàn)20%嚴(yán)重污染時(shí)，順序編排極短碼、最優(yōu)距離編排極短碼、BCH（63，18，10）編碼的識(shí)別率分別為52%、88%、93%。最優(yōu)距離編排極短碼的編碼識(shí)別率接近BCH（63，18，10）編碼。

顯然，提高極短碼編碼點(diǎn)之間的距離，并采用多種編碼算法，可使塊狀污染環(huán)境下整體識(shí)別準(zhǔn)確率接近BCH（63，18，10）碼。

在實(shí)際使用中，考慮到美觀，避免大塊0 或1，可以在按照J(rèn)(3，1，1)=[0，0，0]完成目標(biāo)數(shù)據(jù)編碼后，將每個(gè)數(shù)據(jù)組的某一位取反，更改為另一種極短碼，如更改為J(3，1，1)=[0，1，0]，［0，1，0］表示0，［1，0，1］表示1，或者表1 中所列的其他極短碼，在解碼階段，圖像處理時(shí)，將提取后的對(duì)應(yīng)編碼點(diǎn)取反，轉(zhuǎn)換為J(3，1，1)=[0，0，0]，再進(jìn)行解碼。還可以增加方向識(shí)別信息，將目標(biāo)數(shù)據(jù)中某些位設(shè)為固定值，將3 個(gè)編碼點(diǎn)分別放置在編碼點(diǎn)陣3 個(gè)角上。

在某室外單目視覺測(cè)量系統(tǒng)中，按照極短碼制作的合作目標(biāo)經(jīng)過300 多天使用，經(jīng)歷了各種天氣和輪胎反復(fù)碾壓，一直能夠可靠快速識(shí)別，充分證明了極端糾錯(cuò)碼的技術(shù)性能。

3.2 識(shí)別速度評(píng)估

3.1 節(jié)所述模擬仿真過程中，對(duì)不同污染比例情況獲取的編碼點(diǎn)陣數(shù)據(jù)的解碼時(shí)間進(jìn)行統(tǒng)計(jì)，如圖6 所示。結(jié)果表明，采用極短碼的解碼時(shí)間平均僅有0.017 ms，而BCH（63，18，10）碼平均需用時(shí)2.2 ms，極短碼的識(shí)別速度是BCH（63，18，10）的130 倍。

圖6 解碼時(shí)間Fig.6 Decoding time

因此，極短碼具有很高的識(shí)別速度，特別適合于無(wú)人機(jī)、工業(yè)機(jī)器人等運(yùn)動(dòng)平臺(tái)目標(biāo)編碼識(shí)別應(yīng)用場(chǎng)合。

4 結(jié)語(yǔ)

針對(duì)二維編碼在工程化應(yīng)用環(huán)境中抗各種污染、快速識(shí)別的需求，通過構(gòu)建模擬工程應(yīng)用中的污染數(shù)學(xué)模型，提出了極短糾錯(cuò)編碼的概念、定義和數(shù)學(xué)模型，研究了在有限約束域內(nèi)全局最優(yōu)距離的編碼點(diǎn)編排方法，以及極短糾錯(cuò)碼的解碼算法。以經(jīng)典的BCH 編碼作為參考，對(duì)極短碼的抗污染能力和識(shí)別速度進(jìn)行了仿真評(píng)估。結(jié)果表明：極短糾錯(cuò)碼在相同污染環(huán)境中的識(shí)別準(zhǔn)確率接近BCH 編碼，但具有更快的解碼速度，以及編碼明確、糾錯(cuò)算法簡(jiǎn)潔、易于標(biāo)準(zhǔn)化推廣應(yīng)用的特點(diǎn)，特別適合于無(wú)人機(jī)自動(dòng)起降、工業(yè)機(jī)器人、交通自動(dòng)控制等設(shè)備和目標(biāo)之間有運(yùn)動(dòng)，存在污漬、遮擋、光照陰影、雨水、破損等污染環(huán)境，且對(duì)目標(biāo)編碼識(shí)別實(shí)時(shí)性、準(zhǔn)確性要求很高的工業(yè)控制場(chǎng)合。后續(xù)還將根據(jù)具體應(yīng)用，對(duì)編碼點(diǎn)的形狀、尺寸，以及布局美觀性、圖像快速識(shí)別等方面進(jìn)行研究，進(jìn)一步提高在惡劣環(huán)境下的識(shí)別準(zhǔn)確率和工程應(yīng)用價(jià)值。