基于四叉树算法的智能实时图像识别模型设计与分析

郦丽华LI Li-hua

（浙江育英职业技术学院，杭州 310018）

0 引言

Pearlma WA等人提出了将编码思想和快速小波变换为基础的SPIHT算法，作为现代国际图像变换编码的领先方法，此算法基于分割排序和零树集合，使待量化编码小波系数划分成为3个集合列表，利用排序、初始化、量化、细化步长对子过程进行更新，实现编码嵌入。SPIHT编码结构简单，并且不需要任何的训练，还能够支持多码率。然而，通过理论分析与实验结果分析，此算法也存在部分问题，例如：在小波变换时，要求结合图像数据开展卷积运算，计算比较复杂，需要的内存空间比较大；分割排序与零数集合复杂，信噪比较高；存在较大的计算量，提高编码速度；算法编码阶段关联模型比较简单，通过有限关联信息对节点状态进行预测，影响压缩能力[1]。因此，本文提出了基于四叉树算法的图像实时识别模型[2]，通过此算法定义SPIHT编码算法和小波变换，解决多级树集合分裂（Set Partitioning in Hierarchical Trees，SPIHT）编码算法的编码速度慢等问题。实验结果表示，此算法图像复原质量、编码速度等技术指标比SPIHT等编码算法要优，应用前景广阔。

1 四叉树的算法分析

1.1 四叉树分解算法

四叉树分解能够划分原始图像为多个小块，在同个小块中划分一致性像素，此小块大部分都是方块，只有少部分为三角形或者长方形。通过图像归一化实现图像四叉树分解，利用简单缩放使图像转变为方形，像素点数为2的整数次幂，对四叉树进行分解。

分解四叉树的具体过程如下：将原始图像划分成为原始子块，如果子块能够满足使一致性标准要求，则存储整体子块像素值，否则把方形原始图像划分成为大小相同的4个子方块。现代一致性的检验标准多，包括纹理特征与QRH。本文使用标准差为一致性校验标准，此算法复杂度比较低，并且算法比较简单，能够将子块中图像边缘算法等优势展现出来，分割效果如图1所示。

图1 图像的分割效果

1.2 四叉树结构编码

在存储四叉树时，要保存四叉树结构信息和叶子节点颜色信息。指针中各节点要对指针场进行存储，在存储三元组时，要将每个节点层次L和此层的位置（X，Y）指出。但是此方法要求大量的存储空间。

为了解决原四叉树结构编码中模版只能够代表有限的结构类型，并且树深度最多只能够达到三层等问题，本文对算法进行了改进，得到超过两次的四叉树分解，思想表示为：首先，对目前块进行四叉树分解，直到将全部进行分解；其次，根据上述编码规则实现分解。数的编码结构如图2所示，Layer1中的模块（D0，D1，d1，d2，d3，d4）和图中110011对应。并且d1，d2，d3，d4不是叶子节点，而用于表示是否又子树。如果为1，那么子树的数量就是4棵，节点为另外4棵树的根。如果图片需要分解，最终编码为110011000100000。

图2 数的编码示意图

在实现树结构编码信息之后，通过简单层次遍历使其转变成为物理存储方式。在实际编码过程中，对最后一层0结构信息不进行存储，以便压缩存储空间。经过实验验证，对于一个需要两次及两次以上分解的图像，平均每个结点的颜色信息仅需要0.03bit就可以存储其位置信息。如果图像要分解两次以下，此方法退化成为原本算法，也就是每个节点颜色信息存储信息位置[3]。

2 基于四叉树的图像特征提取

2.1 区域分割

在分割图像区域过程中，利用四叉树分裂合并的方法实现图像区域的分割，图3为四叉树分解。假如R表示整幅数字图像，那么将R分解成为4个大小一样的子区域Ri（i=1，2，3，4）。针对此区域，图像并没有某种相同属性，说明此区域划分成为4个相同区域Rij（i=1，2，3，4；j=1，2，3，4），依次实现各子区域的分裂，直到无法再分裂。在分裂过程中，针对相邻子区域，假如具备某种相同属性，就要合并区域，避免某属性子区域划分成为不同区域，直到无法合并和分裂，实现图像分割。

图3 四叉树分解

2.2 图像特征提取

算法思想指的是对尺度空间极值点进行检测，确定尺度与位置，实现特征点描述子的生成。将算法思想为基础实现SIF特征向量的生成，对两幅图像中关键点相似性的生成，此种判定指的是通过两幅图像特征向量欧式距离进行度量。在判定两个关键点的时候，根据目前欧氏距离和最小距离相除，假如比设定值要小，那么匹配两个关键点。逐渐降低设定阈值，满足匹配关键点也会降低，但是会更加稳定。

通过四叉树分裂合并与局部特征算法特点提出了基于特征融合与四叉树的图像识别措施，利用四叉树对图像区域进行分割，之后提取分割图像的颜色直方图信息，根据局部特征SIFT算法提取特征精度，实现特征信息的融合，对图像特征具有更好的辨识[4]。

3 基于四叉树的图像编码算法

3.1 编码算法流程

基于四叉树分割量化的编码算法步骤为：

其一，对原始图像的L级整型进行小波变换，得出3L个高频子带和1个最低频子带；

其二，将最低子带LL的编码得到实现，对高频子带实现四叉树分割量化编码；

其三，根据关联模型进行算术编码。

根据SIFT算法实现高频子带四叉树分割量化编码，但是要对说明部分重新定义，也就是C（i，j）-像素点（i，j），Ts指的是带s的小波系数四叉树。Ts[l]（i，j）指的是四叉树的节点值：

m（i，j）指的是最重要位，s（i，j）指的是四叉树节点重要性程度。重要性测试函数定义为：

3.2 四叉树的结构和增长顺序

图4为四叉树增长与剪枝结构，最上层为原始父节点，第二层为子节点，第三层为孙节点，以此类推。父节点的选择对最终增长结果并没有太大的影响，但是会影响到区域增长过程。一般在目标图像中选择父节点，对于容易确定的目标图像可以使图像分割速度加快。而对于不确定多目标的图像，没有分割的原始像素点，一般都能够作为对应目标的父节点。分割正副图像，分割结果使背景作为特殊目标，对目标灰度与大小进行判断，区分背景[5]。

图4 四叉树增长与剪枝结构

在四叉树增长的过程中，要剪除部分没有满足进一步增长需求的子节点。要剔除自身为父辈切点的部分子节点。剔除部分为同辈中先增长的节点。通过图5可以看出来，在增长时的子节点和父辈、同辈的子节点关系。一般剪枝条件如下：

其一，子节点无法满足继续增长条件；

其二，子节点中具有父辈节点；

其三，子节点中包括已经增长的同辈子节点。

在全部子节点被剪枝的时候，终止增长过程，从而分割目标。

3.3 局部密度估计

密度估计指的是以样本集推断总体概率分布的方法，是数据分析方法之一。密度估计有非参数估计和参数估计两种方式，参数估计能够使用少量简单参数对总体分布进行描述，但是要求得到样本所属类别和类条件总体概率密度形式。非参数估计能够描述未知总体概率密度函数的方式，但是计算比较复杂，存储空间耗费比较大。在基于四叉树分块密度估计模型中，四叉树分块算法便于使用单一类别的均匀分布与高斯分布进行描述，能够对像素灰度值相似性进行保证。如果需要避免全局特征和其他分块算法在局部特征估计中的样本类别比较多，降低参数估计描述精准度，就必须使用非参数估计情况[6]。

本文使用单高斯分布描述每块像素灰度值，单高斯分布对数似然函数：

公式中的X指的是分块像素集，D指的是图像通道数，N指的是像素个数。μ参指的灰度均值，∑指的是通道之间的协方差阵。

4 试验仿真

图5为仿真样本，表1为试验仿真样本特征值，实现特征值局部离散化并且利用此属性约简算法进行约简。设计网络结构，使用多输入单输出三层结构，输出层以特征向量输出设置16个节点，规则层节点设置为10，和需要分类数字一样，输出层设置为1，激励函数为purelin和logsig，学习函数为learngdm，误差率为0.001，学习速率为0.05。

图5 仿真样本

表1 试验仿真样本特征值

训练结果分析：提取特征值通过四叉树算法约简前后的维数不同，所以约简前后网络训练曲线不同，对于没有通过处理和通过处理的样本训练[7]。通过仿真结果表示，在误差精度相同的条件下，利用四叉树算法的网络能够满足收敛需求，迭代次数为885次，没有优化的网络迭代书数为2976次，减少训练次数，节约大量时间。

4.1 抗噪能力测试

通过训练样本与测试集样本选择40副图片，划分成为4组，每组添加密度0.01、0.02、0.03、0.04的随机椒盐噪声与方差0.01、0.02、0.03、0.04的高斯噪声，测试添加之后的样本，表2为抗噪声能力测试表。

通过表2可以看出来，如果噪声密度不大，对于污染的图片具有良好识别效果，表示图像识别模型抗噪声能力较强。

表2 抗噪声能力测试表

4.2 识别速率测试

表3为识别速率测试结果，通过表3可以看出，本文算法的运算速率比其他两种要优，是因为此算法能够对冗余特征简约，降低网络训练时间，系统实时性良好。

表3 识别速率测试结果

4.3 自适应性测试

通过训练样本与测试集样本选择40副图片划分成为四组，每组旋转1°、2°、3°、4°，测试旋转之后的图片，表4为旋转自适应测试表。之后，对每组样本分别放大1倍、1.5倍和缩小到原来的1/2、1/3，测试放大和缩小的图片，表5为缩放自适应测试表。通过表4和表5可以看出来，系统对于旋转和缩放之后的图片识别效果良好，表示系统具备良好自适应性，所提取特征有效[8]。

表4 旋转自适应测试表

表5 缩放自适应测试表

5 结语

本文通过四叉树分裂合并提出了基于四叉树算法的图像识别与特征提取方法，能够通过四叉树实现图像区域分割，对图像区域中的信息提取并且识别。通过对算法模型进行验证，表示本文的方法能够满足实际需求。