基于全局距离最优的抗污染极短纠错码设计

刘坚强，屈也频，吕余海

（中国人民解放军海军研究院，上海 200436）

0 引言

在无人机自动起降、工业机器人、交通自动控制等工程化应用中，都需要使用特定编码进行目标快速识别，如有学者使用合作二维码估计无人机上摄像机的相对位姿［1］。这类编码使用时面临着污渍、遮挡、光照阴影、雨水、破损等恶劣污染环境，且对可靠性、识别解码速度相较于传统的支付、购物、聊天、注册等应用更为严格。如何设计抗污染能力强、识别速度快的目标识别码，是工程化应用中首先应该解决的问题。

目标识别码有多种样式，如一维条码、二维点阵码、立体码等，其中二维点阵码具有简洁、信息量多、容易制作等特点，成为目标识别码的主流。二维点阵码是用某种特定的几何图形按一定规律在平面（二维方向上）分布的黑白/彩色相间记录数据符号信息的图形［2］。常见的编码有快速响应矩阵（Quick Response，QR）码、数据矩阵（Data Matrix，DM）码、PDF417、Code 16K 等。

在工程化应用中提高二维码抗污染能力的做法包括增大二维码码点、补光、设置稳定平台、人工维护等方式，屈也频等［3］对污染环境下的合作目标设计提出了信息冗余等设计原则，但最根本的解决方法是采用更加高效的编码、解码算法以及图像处理。

在编码方面，通常采用差错控制编码技术，在编码受到污染出现错误数据时，仍然能通过纠错技术正确识别编码，该技术是适应数字通信抗噪声干扰的需要而发展起来的。1948 年，著名的信息论创始人Shannon 指出，可以通过差错控制码在信息传输速率不大于信道容量的前提下实现可靠通信。随后，Hamming 和Golay 提出了第一个实用的差错控制编码方案，将数据分成数据块，对每一块进行独立编码和解码，称为分组码［4］。为了提高编码效率，分组码的数据结构和算法不断优化，其中最为重要的子集是二元的BCH（Bose-Chaudhuri-Hocquenghem）码，它有严密的代数理论，是目前研究最透彻的一类码，具有纠错率高、结构简单等特点［4］。将BCH 码扩展到非二元时，产生了里德-所罗门（Reed-Solomon，RS）码。在通信中，为了解决分组码存在延时大和需要精确帧同步等问题，又出现了卷积码，将通信数据流中不同数据块之间建立关系，后续的还有低密度奇偶校验（Low Density Parity Check，LDPC）码、Tanner 图、极化码（Polar code）、Turbo 码等［5］。

差错控制编码在二维码技术中也得到广泛使用，由于编码点阵固定，分组码正好满足该特点，尤其是BCH 和RS 码（多元BCH 码）得到了广泛应用［6-7］，如手机支付、通信、防疫和控制领域中最常见的QR 二维码，国家标准GB/T 18284—2000《快速响应矩阵码（QR）》对此进行了详细规定［8］，核心信息数据编码就是BCH 码和RS 码。其他的卷积码等并不是特别适合在二维码中应用，如廖景辉［9］研究了将通信中常用的Turbo 码和Polar 码等应用到二维码中，但也提出这些算法在码长较长时才具有较好的纠错能力，而且算法会随着码长增加而越加复杂。

解码是编码的反向工程，解码前通常需要进行图像处理，包括图像增强、滤波、二值化、透视变换、去阴影等过程，进而获得编码点信息，然后对编码点进行解码和纠错，获得二维码表达的信息，有关图像处理的国内外相关研究文献较多，如针对复杂光照等情况下对QR 算法进行优化［10］。

上述基于BCH 和RS 编码的二维码具有较好的效果，但是在使用中仍然存在一些问题：

1）算法较为复杂，复杂度随码长的增加快幅增长，解码时间长，难以满足一些在运动中快速识别的应用要求，限制了算法在工程上的推广应用。如为了提高BCH 解码速度，采用基于现场可编程门阵列（Field Programmable Gate Array，FPGA）的并行算法［11-12］，代价较大。

2）所有数据位之间都有严格的逻辑关系，解码算法与编码算法一般是对应的，具有单一性，难以引入其他算法，一旦误码数据超过本身算法所允许的纠错能力时，就很难识别准确，识别率会大幅减低。如任亚博等［13］对BCH 码进行优化，但是污染比例较低时才有效；吴昭军等［14］提出了一种基于平均余弦符合度的识别算法，用于低信噪比时的BCH 码识别，但是以时间为代价。

3）在复杂环境的工程化应用中，在污染、破损等比较恶劣时，抗污染能力难以提高。曹济英［15］虽然对QR、DM 两种码提出了若干优化算法，但也提出在破损等情况下，识别率会变低。

4）实际工程化应用中，为了提高抗污染能力，编码点不能太少，但二维码面积区域有限，编码点数量不能太多，由此限制了长码的使用。张多利等［16］研究了缩短BCH（36，24，5）码的应用，有一定效果。

因此，构造抗污染能力强、码点少、算法简单、识别速度快、便于推广应用的二维码是一个工程应用的现实需求。

1 码污染模型

首先研究实际环境中二维码污染模型。通过观察不难发现，污渍、遮挡、光照阴影、雨水、破损等各种恶劣环境都会污染二维码。对于均匀的椒盐污染，可采用适当增大编码点面积而很容易解决，因此需要重点关注随机块状污染，也就是成块的数据被改变。数据被污染的严重程度可用污染比例表示，即被污染点数量和总编码点数量之比，被污染点是指在受到污染时，被识别为固定的1 或0（污染码）的编码点，与编码点未被污染时所代表的数据（0 或1）无关。

随机块状污染的数学模型，是在m×n编码点阵区域内随机产生一个多边形凹凸区域，区域覆盖的码点数量从1 到m×n个码点，区域内所有码点数据变为污染码（0 或者1），多边形凹凸区域的顶点坐标集合G见式（1）：

生成多边形凹凸区域时，以编码点阵中的任意一点(x0，y0)为中心点，从该点出发，围绕该点产生i条线段，数量一般为3～10，线段的角度为θi，每条线段的长度li都不同，在一个固定长度r0上再叠加随机长度di，di小于编码点阵Am×n的行数m和列数n之和，由此产生线段的另一端坐标为(xi，yi)，所有线段端点按序组成集合{(xi，yi)}，记为G，连接所有端点，产生多边形凹凸区域，示例见图1。

图1 污染区域示例Fig.1 Example of polluted area

污染模型除了形状外，还有污染点所代表的数据。污染点数据是指应用系统经过各种图像处理后得到的编码点所代表的数据（0 或1），由于不同环境时的污染物不同，如黑色轮胎印、白色油漆、泥土、深色树叶等，产生“0”和“1”污染的概率也不相同，需要根据具体场景进行确定。

2 极短纠错码编码、编排和解码设计

2.1 极短纠错码设计

当前，BCH 等编码在二维码设计中普遍使用，但应用于户外容易污染、对识别速度要求高的场合时，存在算法复杂、编码长、适应性差等缺点，为此本文提出了一种抗污染的极短纠错码。

设目标数据为D，二进制长度为l，二进制数为AD=[al…ai…a1]，ai可表示信息“0”和“1”。在数据传输时，ai如果也只用1 个位表示，当受到污染时，信息会变成1或0，无法得到正确信息，即无法纠错，因此需要用多个位（称为码）表示信息。

按照编码理论，当需要对长度为n的码中t个位进行纠错时，码的最小汉明距离dmin≥2t+1［4］，假设t取最小值1，那么dmin最小为3，对应的码长n最小也为3，此时，按照最小汉明距离定义，这组码中只能有两个长度为n=3 的码字[a2，a1，a0]和[b2，b1，b0]，而且码字中的码元互为反码，可取0 或1。

在此，将两个码字分别用来表示信息“0”和“1”，对应目标数据AD中的单个位，由于这是数据中的最小组成单元，因此将这两个码字组成的码定义为极短纠错码，简称“极短码”。采用编码领域通常做法，记为J(3，1，1)，参数分别表示码长度n=3，信息长度k=1，可纠错长度t=1。满足要求的码字组合有8 种，如表1 所示。

表1 极短纠错码码字组合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]。这两组极短码表述极为简洁，具有以下特点：

1）目标数据中每一位都按照此编码后，数据表现为三重冗余；具有优良的单组码纠错能力和编码效能，与BCH 编码比较见表2 和图2。

2）需要的编码点数量少，可以在非常有限的区域内使用。当可用区域较大时，也可以很方便地进行扩展，便于推广应用。

3）解码时可以采用多种算法，解决了长码解码算法的单一性问题，提高适应不同区域纠错能力和识别速度。

为了评估极短码的性能，将其和BCH 编码进行比较。

BCH 编码表达式为BCH(n，k，t)，其中，n为编码总长度，k为信息码元长度，t为可纠错长度，编码后的码字为，a为信息码元，b为监督码元。

在各类码中，编码利用率和纠错能力是一对矛盾，提高纠错能力，必然降低编码利用率，需要进行权衡。为便于比较，将编码利用率×纠错能力（k×2）定义为编码效能。极短码和典型BCH 编码的编码利用率、纠错能力和编码效能见图2 和表2。

从图2 和表2 中可以看出以下特点：

表2 极短码和典型BCH码参数Tab.2 Parameters of very short code and typical BCH codes

1）在图2 中，序号1 对应的是极短纠错码，序号2～21 对应的是BCH 码。编码利用率曲线中，极短纠错码为0.33，相对BCH 的0.158～0.9，为偏低水平；纠错能力曲线中，极短纠错码为0.33，远高于BCH 的0.016～0.24；综合后的编码效能曲线中，极短纠错码为0.11，远高于其他所有BCH 码。

图2 极短码和BCH码的编码效能比较Fig.2 Comparison of coding efficiency between very short code and BCH code

2）在编码效能曲线中，每一种长度为3（极短码）、7、15、31、63 的码中都有一个最理想的均衡点，即编码效能波峰，但是n越长，波峰越小，极短码具有最好的编码效能。

3）对目标数据用极短码进行编码时，对每一位进行编码后再进行组合，当编码点总长度和纠错能力要求相同时，极短码可表示的目标数据长度比BCH 的长。

2.2 极短纠错编码点编排设计

编排就是将经过极短码编码的码元放置在编码点阵中。假设需要编码的目标数据为D，二进制长度为l，二进制数为AD，每一位ai都按照极短码编码，得到包含A0、A1、A2三组数据的编码矩阵An3。根据实际可用范围，构建m×n的二维码点阵Bm×n，编码点总数量不少于3l，见式（2）：

将An3中的数据编排到Bm×n中，包括两种方式。

1）顺序编排。将a11a21…al1、a12a22…al2、a13a23…al3按照横向顺序逐行依次排放到二维码点阵中b11b12…b1nb21b21…b2n…bm1bm2…bmn，或者按照纵向顺序逐列依次排放在b11b21…bm1b12b22…bm2…b1nb2n…bmn中，当编码点有空余时，填成0 或者1。

2）基于约束点阵域全局距离最优的极短码编排。该编排方法就是使得极短码中3 个位之间的平均距离尽量大，综合后的全局距离最优，其实质就是将突发错误变成随机错误，将集中的错误分散到各个码组，使得每一组编码中被污染的数据的数量小于纠错能力。

该方法分为3 步：首先，将a11a21…al1按顺序放置在编码点阵Bm×n起始点阵区域b11b12…或者b11b21…；然后，按照距离最优算法将a13a23…al3放置在编码点阵尾部点阵区域…bmn-1bmn或者…bm-1nbmn；最后，按照最优距离算法，将a12a22…al2放置在编码点阵中间点阵区域。其中开始区域、尾部区域和中间区域为预先指定的约束点阵域。

构建最优距离ηoptim，其基本原理是同一个数据位中的3个编码点之间的距离越远，同时受到污染的概率就越低，从平均距离（davg）和散布标准差（dstd）两个因素对所有编码点进行综合考虑，得到整体最优距离，见式（3）。即将A0、A1、A2按照排列形成l！个编码方案，在每一种编码方案中，计算编码点阵Bm×n中单个[ai1，ai2，ai3]子编码点两两之间的距离dij，再统计所有l个子编码距离的平均值davg和标准差dstd。平均距离越大且其散布的标准差越小，对应的编码方案为最优方案。

式中：xij、yij、xi1、yi1为第i个子编码中第j（或1）个编码点在Bm×n中的行数和列数。

2.3 极短纠错码解码算法

极短码在解码时可以采用多种算法，不同于长码的算法单一性，包括：

1）2/3 准则对每一位解码，再组合算法。每一个数据位的3 个编码点相同，即a2=a1=a0、b2=b1=b0，因此，无论何种污染，3 点中至少有2 个点的数据一致，将该数据作为目标数据位，将所有数据位按照顺序组合后作为目标数据。

2）3 组数据加校验独立解码。由于每一个数据位的3 个编码点相同，表现为3 冗余，组合后的3 组数据A0、A1、A2也相同。对每一组数据进行独立解码时，采用奇偶校验位进行查错，相校于BCH 码，极短码具有多余编码点，可以在每一组数据中设置1 位奇偶校验码。奇偶校验正确的数据，再按照2/3准则确定目标数据，如果3组数据均不相同，则无法解码。

3）3 组数据拆分为多个子组加校验独立解码。当多余编码点数量较多时，可以将数据进一步拆分为多个子组，每一个子组对应一位奇偶校验码，按照2/3 准则确定子目标数据，然后将多个子目标数据进行组合得到目标数据。

4）根据目标环境预估污染点数据进行解码。在实际应用环境中，产生“0”和“1”污染的概率不相同，当按照2/3 准则和奇偶校验进行解码得不到准确目标数据时，可以根据具体环境中污染概率大小，将2/3 准则中不是全部相同的点的目标数据位更改为大概率数据，重新进行校验解码，提高识别率。

5）根据历史记录推断。对于用户和编码相对固定的场景，当出现污染严重无法得到目标数据时，可以借助历史记录的特征进行推断。

解码是编码的反向操作，基本原则是解码后输出的目标数据应该是准确的：如果无法得到准确的目标数据，就应该报错。因此，综合应用上述算法可提高准确率。

3 极短纠错编码抗污染能力评估

3.1 抗污染能力评估

根据引言中描述，在主流二维码中，BCH 是信息数据的核心编码，因此，为了评估极短纠错码的性能，以BCH 编码算法作为参考对象。选择BCH（63，18，10）作为评估基准，编码点数是极短码编码点数3 的整数倍，而且数量适中，63个编码点可以排列在点阵中。由于BCH 码只有一组，各数据位对于污染是同等的，编排顺序不影响解码结果，以纵向顺序排列为例，点阵如图3 所示。解码采用Matlab 自带的Berlekamp-Welch 算法［17］的bchenc 函数。

图3 BCH（63，18，10）编码点图Fig.3 BCH（63，18，10）coding point diagram

为了和参考码对应，同样选择7×9 的二维码点阵，k设为21，在BCH（63，18，10）的18 位数据基础上，增加3 位奇偶校验码，对应将18 位数据拆分为3 个子组。

按照顺序和最优距离两种方式对数据点进行编排，点阵分别如图4（a）（b）所示。解码时综合利用3.3 节中2/3 准则和多个子组加校验独立解码两种算法。

图4 极短码编码点图Fig.4 Very short code coding point diagram

鉴于本文关注的是数据的编码性能，与图像处理等无关，为了获得大样本量，采用计算机模拟仿真方式进行评估。在Intel8700 计算机中采用Matlab 模拟产生3 万组随机目标数据，按照BCH 码、顺序编排极短码、最优距离编排极短码对目标数据进行编码，产生编码点阵，再按照第1 章中所述随机块状模型构建多边形凹凸区域，区域覆盖点数从1 个点到所有63 个点，将区域作为污染覆盖到编码点阵上，将污染的编码点设置为固定的0 或者1，对所有编码点进行解码，比较解码的数据和目标数据，统计编码识别准确率和污染比例的关系，结果如图5 所示。

图5 随机块状污染情况下的码识别准确率Fig.5 Code recognition accuracy in case of random block pollution

从图5 中可以看出，在出现20%严重污染时，顺序编排极短码、最优距离编排极短码、BCH（63，18，10）编码的识别率分别为52%、88%、93%。最优距离编排极短码的编码识别率接近BCH（63，18，10）编码。

显然，提高极短码编码点之间的距离，并采用多种编码算法，可使块状污染环境下整体识别准确率接近BCH（63，18，10）码。

在实际使用中，考虑到美观，避免大块0 或1，可以在按照J(3，1，1)=[0，0，0]完成目标数据编码后，将每个数据组的某一位取反，更改为另一种极短码，如更改为J(3，1，1)=[0，1，0]，［0，1，0］表示0，［1，0，1］表示1，或者表1 中所列的其他极短码，在解码阶段，图像处理时，将提取后的对应编码点取反，转换为J(3，1，1)=[0，0，0]，再进行解码。还可以增加方向识别信息，将目标数据中某些位设为固定值，将3 个编码点分别放置在编码点阵3 个角上。

在某室外单目视觉测量系统中，按照极短码制作的合作目标经过300 多天使用，经历了各种天气和轮胎反复碾压，一直能够可靠快速识别，充分证明了极端纠错码的技术性能。

3.2 识别速度评估

3.1 节所述模拟仿真过程中，对不同污染比例情况获取的编码点阵数据的解码时间进行统计，如图6 所示。结果表明，采用极短码的解码时间平均仅有0.017 ms，而BCH（63，18，10）码平均需用时2.2 ms，极短码的识别速度是BCH（63，18，10）的130 倍。

图6 解码时间Fig.6 Decoding time

因此，极短码具有很高的识别速度，特别适合于无人机、工业机器人等运动平台目标编码识别应用场合。

4 结语

针对二维编码在工程化应用环境中抗各种污染、快速识别的需求，通过构建模拟工程应用中的污染数学模型，提出了极短纠错编码的概念、定义和数学模型，研究了在有限约束域内全局最优距离的编码点编排方法，以及极短纠错码的解码算法。以经典的BCH 编码作为参考，对极短码的抗污染能力和识别速度进行了仿真评估。结果表明：极短纠错码在相同污染环境中的识别准确率接近BCH 编码，但具有更快的解码速度，以及编码明确、纠错算法简洁、易于标准化推广应用的特点，特别适合于无人机自动起降、工业机器人、交通自动控制等设备和目标之间有运动，存在污渍、遮挡、光照阴影、雨水、破损等污染环境，且对目标编码识别实时性、准确性要求很高的工业控制场合。后续还将根据具体应用，对编码点的形状、尺寸，以及布局美观性、图像快速识别等方面进行研究，进一步提高在恶劣环境下的识别准确率和工程应用价值。