边缘图像自适应编码方法

高异凡，谌德荣，宫久路

（北京理工大学，北京100081）

0 引言

边缘作为图像的重要特征，是无人系统用于目标识别、视觉测量等的重要信息。Edwin［1］使用Canny算子来提取仪表盘和指针边缘，实现了利用机器视觉识别仪表读数。Ling［2］借助包裹的轮廓边缘特征来识别快递包裹尺寸。

在无线网络和运载火箭遥测等无线信道容量有限的无人系统中，为了最大限度传输重要信息，通常将系统设计为2个子系统［3⁃4］：前端进行图像采集和预处理等计算复杂度较低的处理，同时有效减少数据量；后端进行识别和测量等计算复杂度较高的处理。研究表明［4］，在前端进行边缘特征提取，只将边缘图像发送到后端，是平衡计算资源和数据量的合理方式。

边缘图像可以通过数据压缩方法进一步减少数据量，以降低无人系统中数据传输和存储的压力。由于测量任务的精度要求，系统只能使用无损压缩的方式［5⁃6］。常用的边缘图像无损压缩算法包括边缘打包法和链码编码法［7］。边缘打包法将边缘数据按照每8个像素为一组，并打包成1字节进行编码压缩；链码编码法利用Freeman 8⁃方向链码对边缘数据进行编码压缩。对由以上2种方法获取的数据，还可以通过LZ4［7］等通用压缩算法进一步提高编码压缩比。

边缘打包法计算复杂度较低，适用范围广；链码编码法对边缘稀疏图像压缩效率高，但计算复杂度较高。针对上述问题，本文提出一种边缘图像自适应编码算法，通过使用Logistic回归模型，快速选择边缘打包法或链码编码法，以获得比单一方法更优的压缩结果。

1 边缘图像的直接编码

1.1 边缘图像获取

本文参考Canny边缘检测方法，设计了如图1所示的边缘获取流程。具体流程如下：

图1 边缘图像获取流程Fig.1 Flow chart for edge image acquisition

1）利用Gauss滤波对输入图像进行去噪处理。当图像背景比较单一或目标轮廓清晰时，Gauss滤波核的标准差应稍大些，以避免噪声干扰。

2）利用一阶微分算子计算图像在水平和垂直方向上的微分，并计算梯度。

3）沿着梯度方向进行非极大值抑制，去除弱响应点。

4）进行双阈值检测，获取单像素边缘。

5）删除孤立点和噪声，得到边缘图像。

1.2 边缘打包法

在边缘图像中，用1和0表示某点是否为边缘点。边缘打包法首先将二维边缘图像表示为一维数据流，下面以图2为例进行详细说明。

图2 边缘打包法示例Fig.2 Example of edge packing

从左上方像素点开始，按照从左至右、从上至下的顺序依次将每8个像素作为一组，并打包成1字节。由于图2每行有12个像素，并不是8的整数倍，这种情况有2种处理方式：1）行尾填充 “0”；2）将图像按行展开成一维向量。在使用第2种方法时，图2可表示为（16进制）：［0x40 0x20 0x02 0x10 0x40 0x88 0x05 0x00 0x20］。

由于打包后的一维数据流仍然存在冗余信息，综合考虑计算资源和数据量的限制，选用LZ4算法对打包后的边缘数据进行进一步压缩。边缘打包法流程如图3所示。

图3 边缘打包法流程图Fig.3 Flow chart for edge packing

LZ4属于字典编码，是LZ77的一种改进算法。LZ77维护一个滑动窗口，从已编码的数据流中查找是否存在待搜索缓存，并用匹配串的索引表示。而LZ4借助Hash表来存储滑动窗口中的数据索引，改善待搜索缓存的匹配速度，在保证较高压缩比的同时极大地缩短了压缩时间［8］。

1.3 链码编码法

链码是一种表示曲线的常用编码技术，其主要方法有方向链码和顶点链码。其中，方向链码分为 4⁃方向链码和 8⁃方向链码［7］。Freeman 8⁃方向链码从某个起始像素点开始，用ci∈｛0，1，…，7｝表示相邻的8个位置，于是每个链码可用3bit实现存储。以某点作为起点开始，若当前点存在一个相邻的像素是边缘点，则用代表此方向的ci编码，并将此点设置为当前点，继续下一轮编码，直至在8个相邻方向找不到未编码点为止。最后，由起始点坐标（x，y）、链码总长度n以及n个ci组成一条完整链码。

为了使用Freeman 8⁃方向链码表示图2，设从像素相邻的正上方开始，顺时针依次编码为0、1、2、…、7。若以（0，1）为起点，余下点编码为［3 3 3 3 3 1 1 1 1］，则图2的完整编码是（16进制）：［0x00 0x01 0x0A 0x6D 0xB6 0x49 0x24］。

与边缘打包法类似，用LZ4对链码数据进行二次编码后输出。此方法为链码编码法，流程如图4所示。

图4 链码编码法流程图Fig.4 Flow chart for chain-code coding

值得注意的是，链码编码法需要用到泛洪填充算法来搜索边缘图像中的所有链码，其运行时间远大于边缘打包法，这是链码编码法的不足之处。

2 边缘图像自适应编码

2.1 压缩性能分析

设图像长为w，高为h，边缘打包后的数据量为wh；设其中链的条数为k，链平均长度为l，假设长、高和最长链的长度都不超过216，则链码编码后的数据量为（3×16+3l）kbit。当不考虑 LZ4压缩时，边缘打包法的数据量是固定值，只与图像的尺寸相关。而链码编码法的数据量随着图像内容的不同而变化，每条链码至少需要48bit的存储起始点和链码长度，且编码每个边缘点所用数据量为打包压缩法的3倍。如图5所示，当图像边缘稀疏时，采用链码编码法的压缩比为6.85（本文中的压缩比都是以二值图像来计算压缩前数据量），而采用边缘打包法时为5.24。如图6所示，当图像中存在大量短边缘时，采用链码编码法的压缩比为0.80，而采用边缘打包法时为1.52，即采用链码编码法反而增加了数据量。

图5 边缘稀疏图像Fig.5 Image with sparse edges

图6 含大量短边缘的图像Fig.6 Image with plenty edges

在实际应用中，为尽可能减小输出码率，同时尽可能减少计算量，如何快速从两种编码方法中选择其一，是下面要解决的问题。该问题可以看作一个二分类问题，本文引入Logistic回归建立分类模型以实现编码方法的自适应快速选择。

2.2 Logistic回归

Logistic回归也叫对数几率回归，是一种基于Sigmoid函数的有监督分类模型，主要研究多个自变量与一个因变量之间的多元回归关系。它的优点是［9］：1）无需事先假设数据分布；2）不仅可得到分类，还能得到近似概率；3）对数几率函数是任意阶可导的凸函数，有很好的数学性质，许多数值优化算法可以直接用于求解最优值。

建模的第1步是提取模型的特征。考虑到边缘打包法的计算速度比链码编码法快很多，首先使用边缘打包法对边缘图像进行编码，记此时的压缩率（压缩比的倒数）为x1。另外，在边缘提取过程中，加入统计边缘点个数的功能，并求得边缘点个数占所有像素的比例，记为x2。

对于回归问题，常用的特征选择方法有卡方检验、信息增益和分类器错误率等。卡方检验是一种基于χ2分布的假设检验方法，其基本思想是根据样本数据推断总体的分布与期望分布是否有显著性差异，或者推断2个分类变量是否相关或者独立。本文使用卡方检验对x1、x2进行分析，随机选取1组数据集，使用scikit⁃learn中基于卡方检验的特征选择函数chi2，计算得到2个特征的χ2和 p⁃value，其分别是 56、142 和 6.0×10-14、6.5×10-33。说明特征的显著性和相关性较好，x1、x2选择合理。

以x1、x2作为自变量；编码方法选择的结果作为因变量，记为y，当y=1时选择边缘打包法，当y=0时选择链码编码法。将自变量的线性组合z=θTx=θ0+θ1x1+θ2x2带入到Sigmoid函数中建立概率预测函数

2.3 边缘图像自适应编码流程

边缘图像自适应编码流程如图7所示，具体流程如下：

1）对输入图像按照图1所示流程提取边缘。

2）统计边缘点数量，计算边缘点比例x2。

3）按照图3所示流程对边缘图像进行边缘点打包压缩，并计算压缩比x1。

4）使用提前训练好参数的概率预测函数，按照式（1）计算hθ（z）。如果hθ（z）＞50%，表示边缘打包法的输出数据量有更大概率小于链码编码法，直接输出；如果hθ（z）≤50%，用图4所示的链码编码法对边缘图像进行编码输出。

图7 边缘图像自适应编码流程框图Fig.7 Flow chart for adaptive coding method of edge image

3 测试与分析

为了测试边缘图像自适应编码性能，采用VOC2012图像数据库［10］作为测试源对算法压缩比和处理时间进行测试，同时将测试结果与边缘打包法和链码编码法进行对比。VOC2012是一个用于目标识别任务的图像测试集合，包含人物、动物、车辆等20个种类的测试数据，即共约1万张静态图片和一段5min（约9千帧）火箭发射监控视频。测试环境为Windows 10，64位操作系统，i5⁃8250U CPU，8G内存。具体测试流程如下：

1）随机选择VOC2012中70%的数据作为训练集，使用python语言的scikit⁃learn机器学习开发包，训练系统的Logistic回归模型，得到最佳参数θ。

2）使用余下的30%数据和视频对边缘打包法、链码编码法和使用参数θ下的自适应编码算法进行边缘图像编码压缩。

3）计算不同方法的压缩比，并统计每种方法的平均处理时间。

4）重复上述测试10次，并计算平均结果。

前2次测试结果和10次测试结果的平均值如表1所示。

表1 不同算法测试结果对比Table 1 Test results comparison of the three methods

从表1可以看出，在不同的θ值下，边缘图像自适应编码法压缩比相比边缘打包法提高了约5%，比链码编码法提高了约20%；计算时间比边缘打包法提高了约6%，比链码编码法降低了13%。

4 结论

本文针对无人系统中边缘图像高效压缩问题，提出了一种边缘图像自适应编码算法，该算法利用Logistic回归建立分类模型，快速自适应地从边缘打包法和链码编码法中选择压缩比最高的方法对边缘图像进行压缩。对VOC2012图像数据库的测试结果表明，自适应编码算法能提高边缘图像压缩比5%左右，有效降低了数据量。