基于矩阵分解和图像的协同过滤（基于改进协方差矩阵的半色调图像分类研究）

基于矩阵分解和图像的协同过滤（基于改进协方差矩阵的半色调图像分类研究）COV定义如下：协方差矩阵[13-14]（Covariance matrix，COV）是概率论、统计学的一个概念，通过不同维度计算协方差构成的矩阵，衡量两个随机变量的变化。协方差矩阵表示一个多维随机变量各个维度之间的相关性。协方差矩阵于2006年被Tuzel O，Porikli F[15]作为描述子最先应用在医学图像处理的目标检测中，能够很好地描述图像，因为将其用于图像特征提取时，将区域图像不同的特征值通过统计矢量的方式统一于协方差矩阵中。COV作为描述子具有很好的鲁棒性，对外部形态和光照的改变能很好地维持其主要特征的不变性，所以可将COV应用于半色调图像的特征提取中[16]。以上方法都基于欧式空间，本文提出的方法需在黎曼空间上进行特征匹配，再利用黎曼距离和局部概率密度来实现对半色调图像的分类。黎曼流形是具有黎曼度量的微分流形，即有一个对称正定协变的二阶张量场在这个流形上，相比于欧式空间，

摘 要： 针对半色调图像分类中只存在0和1的特点，提出了一种基于改进的协方差矩阵在半色调图像中的分类方法。根据协方差矩阵在实现半色调图像分类中个数少且并未体现其局部和全局信息的特性，对协方差矩阵的底层特征进行改进。利用样本的局部特性和核密度估计方法，实现黎曼流形上的贝叶斯分类策略。实验中研究协方差矩阵的底层特征与传统协方差矩阵的特征提取方法并对其进行分类性能比较。实验结果表明，在半色调图像分类中，与传统的协方差矩阵相比较，改进的协方差矩阵提取出的特征在分类中平均错误分类率更低。

0 引言

数字半色调（也称为空间抖动）始于19世纪50年代，是将一幅连续色调的图像先进行二值化处理，再用这些黑白二色的点来表示各个等级灰度的技术[1]。数字半色调技术已广泛应用于传真、打印、印刷、显示设备及数字图像的压缩存储等领域。较常用的数字半色调方法有：有序抖动法[2]、误差分散法[3]、点分散法[4]、绿噪声半调法[5]等。通过分析现有的半色调技术可知，不同半色调技术应用于多级图像时将产生具有各自不同特性的半色调图像[6]，有周期性、点分布、点分散性、点相关性等。当通用型逆半色调技术用于某种半色调图像的重建时，将缺少相关半色调模式信息，所以较难获得半色调图像的最优重建。

目前数字半色调图像分类方法的研究比较少。Chang[7]首先对半色调图像分类进行研究，指出在半色调图像恢复成连续灰度图像之前运用一维自相关函数，提取出四类半色调图像，最后用BP神经网络进行分类。虽然该方法分类结果有时能达到100%，但获取的类别比较少。文志强[1，8]提出一种在3个方向上利用像素自相关特征进行同或运算来描述纹理特征的有监督流形上的半色调分类方法，利用图像分块的思想获取纹理特征，目的在于提高建模效率和纹理特征的有效性。

以上方法都基于欧式空间，本文提出的方法需在黎曼空间上进行特征匹配，再利用黎曼距离和局部概率密度来实现对半色调图像的分类。黎曼流形是具有黎曼度量的微分流形，即有一个对称正定协变的二阶张量场在这个流形上，相比于欧式空间，具有更丰富的黎曼度量方法，是研究概率分布和模式匹配的有效工具。

1 传统协方差矩阵建模方法

通过多种半色调技术可将多级灰度图像转化为半色调图像样本，并对其进行分类。12种常用半色调技术，如表1所示。图1给出相应的12幅灰度图像产生的半色调图像（以lena（大小：256×256）为例）。由图1可知，不同半色调技术产生的半色调图像具有不同的纹理特征。一些半色调图像纹理比较明显，如图1中的（a）、（g）、（h）、（i）子图；另一些纹理差别不明显，分类较困难，如图1中（b）、（c）、（e）和（l）子图难以区分，子图（d）、（f）、（j）和（k）区别也较小。由分析可知，造成半色调图像分类错误率高的最主要原因是纹理差别不明显。因此，本文在半色调图像上对协方差矩阵改进之后再进行构建与分类。

协方差矩阵[13-14]（Covariance matrix，COV）是概率论、统计学的一个概念，通过不同维度计算协方差构成的矩阵，衡量两个随机变量的变化。协方差矩阵表示一个多维随机变量各个维度之间的相关性。协方差矩阵于2006年被Tuzel O，Porikli F[15]作为描述子最先应用在医学图像处理的目标检测中，能够很好地描述图像，因为将其用于图像特征提取时，将区域图像不同的特征值通过统计矢量的方式统一于协方差矩阵中。COV作为描述子具有很好的鲁棒性，对外部形态和光照的改变能很好地维持其主要特征的不变性，所以可将COV应用于半色调图像的特征提取中[16]。

COV定义如下：

设I为一维强度或三维强度的彩色图像，f为原图I内具有M×N个像素的区域图像，h为该区域f内提取的d维特征向量，如式（1）所示：

将区域f每个像素的特征向量通过共生关系统一到协方差矩阵C中，如式（2）所示：

其中，h（x，y）为区域矩阵每个元素的特征向量，u为M×N个dx1维特征向量h（x，y）的均值，h（x，y）表示区域图像每个像素的底层特征，如式（3）所示：

h（x，y）=[|fxx|，|fyy|，|fx|，|fy|，f（x，y）]T（3）

式（2）中C（f）为协方差矩阵，融合了原始图像底层的五个特征，等价于公式（4）：

C（f）=HHT（4）

由公式（1）~（4）可知，COV能够较好地表示图像的特征，且具有如下优点：

（1）很好的辨识度。能够将区域图像多种特征融合于COV中。

（2）更低的维数。COV是一个对称的半正定矩阵，所以d维的特征向量构成的协方差矩阵具有（d2 d）/2个不同值。

（3）很好的鲁棒性。将一幅图像旋转后，若选取的特征适当，则形成的COV不发生相应的改变。

2 改进的协方差矩阵建模方法

COV虽然有很多优点，但也存在不足。由公式（2）可知，当h（x，y）=u时，协方差矩阵的行列式有可能为0，所以准确地讲，协方差矩阵应属半正定矩阵，针对该问题可采用附加一个足够小的对角矩阵p来进行预处理。

可以看到，图1中12幅半色调图像的纹理不明显，分类较困难。针对这一难点，可将半色调图像求梯度，即通过梯度信息来描述图像中物体的边缘、轮廓、形状等纹理特征。对图像加入水平边缘算子[-1，0，1]和垂直边缘算子[-1，0，1]T，并将该特征加入协方差矩阵的底层特征中。所以提出改进的协方差矩阵（Improved covariance matrix，ICM）。

本文获取区域半色调图像f的底层特征如公式（5）所示，通过公式（2）将其构成COV。

h（x，y）=[x，y，|fx|，|fxx|，|fy|，|fyy|，f（x，y），

其中，x，y分别为区域半色调图像的坐标值，f（x，y）设定以位置（x，y）为中心的n×n（实验中n取9）邻域各个像素值之和，|fx|、|fxx|为像素值在x方向的一阶、二阶导，|fy|、|fyy|为像素值在y方向的一阶、二阶导。arctan|fy|/（|fx| p）为f（x，y）在位置（x，y）处的梯度。由于协方差矩阵的行列式有可能为0，所以添加一个无穷小量。S1（x，y）=（|Ix|*|Ix| |Iy|*|Iy| |fx|*|fx| |fy|*|fy|），其中Ix为水平边缘梯度，Iy为垂直边缘梯度。S2（x，y）=arctan|Iy|/（|Ix| p）。图2为对应图1中ICM特征图像示例图。由图2可知，各矩阵的特征图都有一定的差别，这说明提取的特征矩阵可用于描述半色调图像。即加入梯度算子后，图像的轮廓明显变得更清晰。将梯度算子加入COV的底层特征后，特征更明显，更容易区分图像的纹理信息。ICM算法实现步骤如下：

算法：ICM算子的构造

输入：一幅大小为M×N的区域半色调图像f

输出：能够表征原始半色调图像的改进协方差矩阵

Step1 根据公式（5）获取区域半色调图像的十个底层特征，分别是x，y，|fx|，|fxx|，|fy|，|fyy|，f（x，y），arctan|fy|/（|fx| p），S1（x，y），S2（x，y）；

Step2根据公式（2）计算区域半色调图像f的协方差 矩阵C（f）。

3 实验结果及比较

3.1 实验环境

本实验在Windows 7操作系统环境下进行，采用VC6.0结合OpenCV 1.0及MATLAB 7.11进行编程。常用半色调图像由VC6.0结合OpenCV 1.0产生，ICM特征的提取使用MATLAB 7.11生成。

3.2 实验结果

对原始图像产生12类常用半色调图像库，对每类随机取出410幅样本（大小为256×256）。对每幅图像提取ICM特征，之后从每类410个协方差矩阵的特征中随机抽取205个作为训练样本，剩余205个作为测试样本。为验证提出方法的有效性，取相同K值不同类型的特征矩阵在黎曼流形上采用K最近邻分类器对纹理特征进行分类。现取K=23，应用传统的协方差矩阵与本文提出方法对随机取出的410×12幅图像进行分类，比较其分类精度如表2和表3所示。

由表2可知，采用传统协方差矩阵对12类常用的半色调图像的平均分类正确率为83.487 5%，由表3可知，提出方法对12类常用半色调图像的平均分类正确率为92.598 3%。比较表明，本文所提出的方法有所改善。

3.3 参数影响

对于多类别（类别数大于2）投票时可能会出现两种或多种类别票数相同问题，这种情况下分类器取K个近邻值中最小值对应的类别为最终类别。分类结果性能采用平均分类错误率（公式（7））和分类错误方差率（公式（8））来评价，其中公式（6）为错误分类率。平均分类错误率越小说明分类效果越好，分类错误方差率越小说明分类器越稳定。

其中，nj为测试样本总数，mj为正确分类样本数，N为总的类别数（N=12），j为类别数，j=1，2，…，12。

本实验测试不同K值对相同类型的影响。由12类常用半色调图像变更不同的K值，分别取11，15，19，23，27，31，35七个值来比较传统协方差矩阵和提出方法提取特征矩阵对其进行eave和v比较，折线图比较如图3和图4所示。由图3可知，常用12类半色调图像的分类中，COV在K=19时分类效果最好，ICM在K=23时分类效果最好。但不管K为何值，提出方法效果均优于COV。由图4的v折线图可知，COV在K=23时分类器最稳定，ICM在K=27时v最小，此时的分类器性能最稳定。不管K为何值，本文提出方法的分类器更稳定。由此证明，提出方法的有效性。

4 总结

针对12类常用半色调图像的分类问题，对半色调图像的特征建模和分类方法进行了深入研究，提出对传统的协方差矩阵进行改进，并用黎曼流形上的K最近邻方法对提取出的特征矩阵进行分类。通过比较分类精度来验证提出方法的有效性。实验证明，将传统的协方差矩阵与提出方法进行eave和v比较，可知提出方法在K=23时，eave最低，即分类效果最好；在K=27时，v最小，即分类器性能最稳定，所以在选择K值时应视需求而定。

参考文献

[1] 文志强，胡永祥，朱文球.基于统计量模板的半色调图像特征提取与分类[J].计算机科学，2013，40（12）：94-112.

[2] LIU Y F， GUO J M. New class tiling design for dot-diffused halftoning[J]. IEEE Trans. on Image Process， 2013，2（3）： 1199-1208.

[3] STEVENSON R. Inverse halftoning via MAP estimation[J].IEEE Trans. on Image Processing， 1997， 6（4）： 574-583.

[4] MESE M， VAIDYANATHAN P P. Recent advances in digital halftoning and inverse halftoning methods[J]. IEEE Trans. on Ciruits and Systems： Fundamental Theory and Applications， 2002，49（6）： 790-805.

[5] LIU Y F， GUO J M， LEE J D. Inverse halftoning based on the Bayesian theorem[J]. IEEE Trans. on Image Process， 2011， 20（4）： 1077-1084.

[6] 文志强，胡永祥，朱文球.黎曼流形上半调图像的协方差建模与贝叶斯分类方法[J].模式识别与人工智能，2013，26（11）：993-1003.

[7] CHANG P C， YU C S. Neural net classification and LMS reconstruction to halftone images[C]. Proc. of the SPIE Visual Communications and Image Processing， San Jose， USA， 1998： 592-602.

[8] Wen Zhiqiang， Hu Yongxiang， Zhu Wenqiu. A novel classification method of halftone image via statistics matrices[J]. IEEE Trans. on Image Process， 2014， 23（11）： 4724-4736.

[9] GUO J M， LIU Y F， CHANG J Y， et al. Efficient halftoning based on multiple look-up tables[J]. IEEE Trans. on Image Process， 2013， 22（11）：4522-4531.

[10] MESE M， VAIDYANATHAN P P． Recent advances in digital halftoning and inverse halftoning methods[J]. Circuits and Systems I： Fundamental Theory and Applications， IEEE Transactions on， 2002，49（6）：790-805.

[11] ULICHNEY R. Digital halftoning and the physical reconstruction function[C]. Ph. D Dissertation. Cambridge， USA： Massachusetts Institute of Technology， 1986.

[12] KNUTH D E. Digital halftones by dot diffusion[J]. ACM Trans. on Graphics， 1987， 6（4）：245-273.

[13] MESE M， VAIDYANATHAN P P. Optimized halftoning using dot diffusion and methods for inverse halftoning[J]. IEEE Trans. on Images Process， 2000，9（4）：691-709.

[14] WU Y， CHENG J， WANG J， et al. Real-time probabilistic covariance tracking with efficient model update[J]. IEEE Trans. on Image Process， 2012，21（5）：2824-2837 .

[15] PORIKLI F， TUZEL O， MEER P. Covariance tracking using model update based on lie algebra[C]. Computer Vision and Pattern Recognition， 2006 IEEE Computer Society Conference on. IEEE， 2006：728-735.

[16] Wen Zhiqiang， Hu Yongxiang， Zhu Wenqiu. Bayesian classification of halftone image based on region covariance[J]. Intelligent System Design and Engineering Applications， 2013（3）：398-401.