Fractal Image Compression Algorithm Based on Double-Layer Non-Negative Matrix Factorization

doi:10.3778/j.issn.1002-8331.2009-0350

Abstract

Abstract: As a structure-based image compression technology, fractal image compression is used in many image processing. However, the encoding stage of fractal image compression is very time-consuming, and the quality of the reconstructed image is not good. To solve these problems, a fractal image compression coding algorithm based on double-layer non-negative matrix factorization（DLNMF） is proposed. In the traditional theory of non-negative matrix factorization（NMF）, the projection non-negative matrix factorization（PNMF） is combined with the [L3/2] norm constraint to extract representative image features in a short time. Firstly, the features of the original image are extracted by double-layer non-negative matrix decomposition; then the image features are clustered by [K]-means, and the classified image blocks are obtained according to the corresponding index; orthogonal sparse decomposition is performed in the corresponding class blocks to obtain the fractal code; and finally, the reconstructed image is obtained according to the fractal code. Experimental results show that compared with images reconstructed by fast sparse fractal image compression theory, the fractal compression algorithm of double-layer non-negative matrix factorization improves the quality of the reconstructed image and shortens the encoding time.

Key words: non-negative matrix factorization, projected non-negative matrix factorization, orthogonal matching pursuit, [K]-means clustering, sparse fractal image compression

摘要： 分形图像压缩作为一种基于结构的图像压缩技术，在许多图像处理中得到了应用。但是分形图像压缩的编码阶段非常耗时，且重建图像的质量效果不佳。针对这些问题，提出了一种基于双层非负矩阵分解的分形图像压缩编码算法。在传统的非负矩阵分解理论上，将投影非负矩阵分解与[L3/2]范数约束相结合，可以在较短的时间内提取具有代表性的图像特征。算法采用双层非负矩阵分解提取原始图像的特征，对图像的特征进行[K]均值聚类，根据对应索引得到分类的图像块，在相应类别块里进行正交稀疏分解得到分形码，最后重建图像。实验结果表明，与快速稀疏分形图像压缩理论重建的图像相比，双层非负矩阵分解的分形压缩算法提高了重建图像的质量，同时缩短了编码时间。

关键词: 非负矩阵分解, 投影非负矩阵分解, 正交匹配追踪, [K]均值聚类, 稀疏分形图像压缩

FANG Meidong, WANG Hui, ZHANG Aihua. Fractal Image Compression Algorithm Based on Double-Layer Non-Negative Matrix Factorization[J]. Computer Engineering and Applications, 2022, 58(8): 204-213.

方美东, 王辉, 张爱华. 双层非负矩阵分解的分形图像压缩算法[J]. 计算机工程与应用, 2022, 58(8): 204-213.

References

[1] BARNSLEY M F，SLOAN A D.A better way to compress images[J].BYTE，1988，13（1）：215-233.
[2] BARNSLEY M F，HURD L P.Fractal image compression[M].Wellesley：A K Petter Ltd，1993：49-74.
[3] PRATT W，KANE J，ANDREWS H C.Hadamard transform image coding[J].Proceedings of the IEEE，1969，57（1）：58-68.
[4] JACQUIN A E.Image coding based on a fractal theory of iterated contractive image transformations[J].IEEE Transactions on Image Processing，1992，1（1）：18-30.
[5] BARNSLEY M F，DEMKO S.Iterated function systems and global construction of fractals[J].Proceedings of the Royal Society of London，1985，399（1817）：243-275.
[6] 唐国维，韩鹏宇，王艾，等.一种基于分块的分形图像压缩方法[J].大庆石油学院学报，2012，36（3）：100-118.
TANG G W，HAN P Y，WANG A，et al.A fractal image compression method based on block[J].Journal of Daqing Petroleum Institute，2012，36（3）：100-118.
[7] 张晶晶，张爱华，纪海峰.基于小波与分形相结合的图像压缩编码[J].计算机科学，2019，46（8）：310-314.
ZHANG J J，ZHANG A H，JI H F.Image compression coding based on the combination of wavelet and fractal[J].Computer Science，2019，46（8）：310-314.
[8] 付晨.基于分形理论的局部码本改进与图像检索加权算法研究[D].保定：河北大学，2018.
FU C.Research on local codebook improvement and image retrieval weighting algorithm based on fractal theory[D].Baoding：Hebei University，2018.
[9] BHARATHI M，JANANI T.Fractal image compression using quantum search algorithm[J].Journal of Computational and Theoretical Nanoscience，2017，14（9）：4580-4585.
[10] HUANG X Q，ZHANG Q，LIN W B.A new method for image retrieval based on analyzing fractal coding characters[J].Journal of Visual Communication & Image Represention，2013，24（1）：42-47.
[11] PAATERO P，TAPPER U.Positive matrix factorization：a non-negative factal model with optimal utilization of error estimates of data values[J].Environmetrics，1994，5（2）：111-126.
[12] LEE D D，SEUNG H S.Learning the parts of objects by non-negative matrix factorization[J].Nature，1999，401（6755）：788-791.
[13] 王倩.基于数据流形结构的非负矩阵分解人脸识别算法研究[D].深圳：深圳大学，2018.
WANG Q.Research on non-negative matrix factorization face recognition algorithm based on data manifold structure[D].Shenzhen：Shenzhen University，2018.
[14] 孙静静，赵飞.非负矩阵分解在空间目标图像识别中的应用[J].激光与光电学进展，2019，56（10）：130-137.
SUN J J，ZHAO F.Application of non-negative matrix factorization in space target image recognition[J].Progress in Laser and Optoelectronics，2019，56（10）：130-137.
[15] 覃阳，肖化.自适应非负矩阵分解的人脸识别方法研究[J].软件导刊，2019，18（12）：73-77.
QIN Y，XIAO H.Research on face recognition method based on adaptive non-negative matrix factorization[J].Software Guide，2019，18（12）：73-77.
[16] AUSYIN W，ANDERSON D.Full supervised non-negative matrix factorization for feature extraction[C]//Proc of IEEE International Geoscience and Remote Sensing Symposium.Piscataway，NJ：IEEE Press，2018：5772-5775.
[17] HOYER P O.Non-negative sparse coding[C]//2002 IEEE Workshop on Neural Networks for Signal Processing，2002：557-565.
[18] HOYER P O.Non-negative matrix factorization with sparseness constrains[J].Journal of Machine Learning Research，2004，5（9）：1457-1469.
[19] DU S Q，SHI Y Q，WANG W L.Sparse non-negative matrix factorization with fractional norm constraints[C]//Proceedings of the 33th Chinese Control Conference，Nanjing，2014：28-30.
[20] DU S Q，SHI Y Q，WANG W L.L3/2 sparsity constrained graph non-negative matrix factorization for image representation[C]//The 26th Chinese Control and Decision Conference，Changsha，2014：2962-2965.
[21] YANG Z R，YUAN Z J，LAAKSONEN J.Projective non-negative matrix factorization with applications to facial image processing[J].International Journal of Pattern Recognition & Artificial Intelligence，2007，21（8）：1353-1362.
[22] SINDHWENI V，HU J Y，MOJSILOVIC A.Regularized co-clustering with dual supervision[C]//Advances in Neural Information Processing Systems，2008：1505-1512.
[23] ZHANG Z，XU Y，YANG J，et al.A survey of sparse representation：algorithms and applications[J].IEEE Access，2015，3：490-530.
[24] PATI Y C，REZAIIFAR R，KRISHNAPRASAD P S.Orthogonal matching pursuit：recursive function approximation with approximation to wavelet decomposition[C]//Pro IEEE Asilomar Conf Signals Systems Computer，1993：40-44.
[25] MALLAT S G，ZHANG Z.Matching pursuits with time-frequency dictionaries[J].IEEE Transactions on Signal Processing，1993，41（12）：3397-3415.
[26] KRISHNAN D，FERGUS R.Fast image deconvolution using Hyper-Laplacian priors[C]//Advances in Neural Information Processing Systems，2010：1033-1041.
[27] LEE D D，SEUNG H S.Algorithms for non-negative matrix factorization[C]//Advance in Neural Information Processing Systems，2001.
[28] DEMPSTER A P，LAIRD N M，RUBIN D B.Maximum likelihood from incomplete data via the EM algorithm[J].Journal of the American Society，1977，39（1）：1-38.
[29] CAO J，ZHANG A H，LEI S.Orthogonal sparse fractal coding algorithm bansed on image texture feature[J].IET Image Processing，2019，13（11）：1872-1879.
[30] 郭友雄.Hadoop平台下并行聚类算法的研究[D].福建：福建师范大学，2018.
GUO Y X.Research on parallel clustering algorithm under Hadoop platform[D].Fujian：Fujian Normal University，2018.
[31] ZHAO W Z，MA H F，LI N.A new nonnegative matrix factorization algorithm with sparseness constrains[C]//Proceedings of the 2011 International Conference on Machine Learning and Cybernetics，Guilin，2011：10-13.
[32] JENG J H，TRUONG T K，SHEU J R.Fast fractal image compression using the Hadamard transform[J].IEE Proceeding-Vision Image and Signal Process，2000，147（6）：571-573.
[33] WANG J J，CHEN P，XI B，et al.Fast sparse fractal image compression[J].Plos One，2017，12（9）：e0184408.