基于分形技术的图像检索研究
摘要
分形码的提取和相似性比较是分形图像检索中的关键技术。为了达到实时准确的检索效果,本文将通过不同的分形算法对图像编码、解码及检索进行研究。针对不同类别的图库,使用灰度直方图相似性比较算法进行检索,并得出测试结果,作为后续工作中查全-查准率的比较标准;对图像进行基本分形编码测试,其结果作为后续工作中图像信噪比的比较标准。与此同时,提出了两种新的局部码本检索算法,即基于四叉树分割的快速分形检索算法和基于HV分割的快速分形检索算法。
本文改进了四叉树的分割算法,对子块匹配策略加以限制,仅从其邻域中选取4个方向的D块进行比较判别,避免了四叉树分割算法匹配过程中搜索量过大的缺点。图像编码速度得到提升。对编码后分形码的比较算法进行了研究与分析,综合考虑了不同R块之间的大小、位置、匹配方向等因素,提出了一种新的距离比较公式。
基于HV分割的快速分形检索算法,提高了分割块对图像的自适应性。对于当前R块,本文算法仅需要一次匹配运算,进一步提升了编码效率。由于不同图像的分割块数目和大小比例并不一致,在对不同R块相似性比较判断上,本文提出了基于面积交叉的权重公式,并得到一种新的基于HV分割分形检索算法距离比较公式。
根据以上算法,本文针对大小为256×256尺寸的灰度图进行编码解码相关测试。在相同测试条件下,重点对不同检索算法的编码时间、解码质量、分割效果等方面进行分析。基于四叉树和基于HV分割快速分形检索算法在编码速度上相对于基本分形编码算法提高了40倍以上,解码质量依然能够得到保证。在结构复杂的纹理图测试中,基于HV分割分形检索算法的解码质量要高于基本分形编码算法的解码质量。为了检验本文算法针对于不同类别图像的检索效果,分别对人物、风景、纹理及生活杂类图库进行测试。测试结果表明,基于四叉树和基于HV分割的快速分形检索算法能体现出图像中结构的相似程度,测试结果优于灰度直方图检索算法的相似性比较结果。
The extraction of fractal code and comparison between similarities are the key technologies. To achieve real time and accuracy retrieval, this paper discussed different fractal algorithms in image retrieval. The test result of histogram retrieval method is given as the standard of accurate-complete retrieval rating in future works; the test result of basic fractal encoding is given as the standard of PSNR in future works. Two partial code retrieval methods, contiguous-match and HV segmentation, are put forward.
The segmentation matching strategy in quadtree fractal algorithm are restricted in this paper, the D blocks are selected in four directions only from the neighbors, to avoid mass searching. The image encoding speed is improved. The comparison algorithm of encoded IFS is analyzed, the size, location and matching direction between different R blocks are considered, and a new distance formula is put forward.
The HV fragmentation based fractal retrial algorithm improves the image adaptability of fragmentations. Only one encode matching is required for each R block, so the encoding efficiency is further improved. For different images, the size and ratio of blocks are different, a weight formula based on cross area is put forward to compare the similarities of different R blocks, a new retrial formula based on HV fragmentation algorithm is obtained.
According to the algorithm given above, this paper test the encoding and decoding of 256×256 size grey images. Under certain testing conditions, the encoding time, decoding quality and fragmentation effect are especially analyzed. Both Quadtree and HV segmentation fractal retrieval algorithm can improve the encoding speed over 40 times, and the decoding quality is guaranteed. In the test of complicated texture images, the HV based fractal retrieval algorithm has higher decoding quality over the original algorithm. To test the retrieval effect against different image types, the paper test the character, scenery, texture and daily-life images. The results show that the quadtree and HV based fractal retrieval algorithm can embody the similarity of image structure, and which is prior than the histogram retrieval algorithm.
本文改进了四叉树的分割算法,对子块匹配策略加以限制,仅从其邻域中选取4个方向的D块进行比较判别,避免了四叉树分割算法匹配过程中搜索量过大的缺点。图像编码速度得到提升。对编码后分形码的比较算法进行了研究与分析,综合考虑了不同R块之间的大小、位置、匹配方向等因素,提出了一种新的距离比较公式。
基于HV分割的快速分形检索算法,提高了分割块对图像的自适应性。对于当前R块,本文算法仅需要一次匹配运算,进一步提升了编码效率。由于不同图像的分割块数目和大小比例并不一致,在对不同R块相似性比较判断上,本文提出了基于面积交叉的权重公式,并得到一种新的基于HV分割分形检索算法距离比较公式。
根据以上算法,本文针对大小为256×256尺寸的灰度图进行编码解码相关测试。在相同测试条件下,重点对不同检索算法的编码时间、解码质量、分割效果等方面进行分析。基于四叉树和基于HV分割快速分形检索算法在编码速度上相对于基本分形编码算法提高了40倍以上,解码质量依然能够得到保证。在结构复杂的纹理图测试中,基于HV分割分形检索算法的解码质量要高于基本分形编码算法的解码质量。为了检验本文算法针对于不同类别图像的检索效果,分别对人物、风景、纹理及生活杂类图库进行测试。测试结果表明,基于四叉树和基于HV分割的快速分形检索算法能体现出图像中结构的相似程度,测试结果优于灰度直方图检索算法的相似性比较结果。
The extraction of fractal code and comparison between similarities are the key technologies. To achieve real time and accuracy retrieval, this paper discussed different fractal algorithms in image retrieval. The test result of histogram retrieval method is given as the standard of accurate-complete retrieval rating in future works; the test result of basic fractal encoding is given as the standard of PSNR in future works. Two partial code retrieval methods, contiguous-match and HV segmentation, are put forward.
The segmentation matching strategy in quadtree fractal algorithm are restricted in this paper, the D blocks are selected in four directions only from the neighbors, to avoid mass searching. The image encoding speed is improved. The comparison algorithm of encoded IFS is analyzed, the size, location and matching direction between different R blocks are considered, and a new distance formula is put forward.
The HV fragmentation based fractal retrial algorithm improves the image adaptability of fragmentations. Only one encode matching is required for each R block, so the encoding efficiency is further improved. For different images, the size and ratio of blocks are different, a weight formula based on cross area is put forward to compare the similarities of different R blocks, a new retrial formula based on HV fragmentation algorithm is obtained.
According to the algorithm given above, this paper test the encoding and decoding of 256×256 size grey images. Under certain testing conditions, the encoding time, decoding quality and fragmentation effect are especially analyzed. Both Quadtree and HV segmentation fractal retrieval algorithm can improve the encoding speed over 40 times, and the decoding quality is guaranteed. In the test of complicated texture images, the HV based fractal retrieval algorithm has higher decoding quality over the original algorithm. To test the retrieval effect against different image types, the paper test the character, scenery, texture and daily-life images. The results show that the quadtree and HV based fractal retrieval algorithm can embody the similarity of image structure, and which is prior than the histogram retrieval algorithm.
引文
[1]中国互联网发展状况统计报告.中国互联网络信息中心, 2011, 1.
[2] Y.Fisher. Fractal image compression theory and application. Springer-Verlag, New York.1993.
[3] M.Barnsley, L.Hurd. Fractal Image Compression. AK Peters, Wellesley, 1993.
[4] Y.Fisher, S.Menlove. Fractal encoding with HV partions in Fractal Image Compression-Theory and Application, Y.Fisher, Ed.New York: Springer,1994.
[5] E.Reusens. Partitioning complexity issue for iterated function systems based image coding, in Proc. VIIth Eur. Signal Processing Conf. EUSIPCO, vol. 1, Edinburgh, U.K., 1994: 171-174.
[6] O.Peitgen, H.Jurgens, D.Saupe. Chaos and Fractals New Frontiers of Science, Spinger, New York, 1992.
[7] M.Novak. Attractor coding of images. In Proceedings of the International Picture Coding Symposium PCS’93, Lausanne, March 1993: 15-16.
[8] D.J.Jackson, W.Mahmoud, W.A.Stepleton, and R.T.Gaughan. Faster fractal image compression using recomposition, Image Vision Computing, 1997(15): 759-767.
[9] S.Kumar, R.C. Jain. Low complexity fractal-based image compression technique. IEEE Trans on Consumer Electronics, 1997(43): 987-993.
[10] F.Davoine. J.M.Chassery. Adaptive Delaunay triangulation for attractor image coding, in Proc. 12th Int. Conf. Pattern Recognition, Jerusalem, Israel, 1994.
[11] F.Davoine, G. Robert, J.M. Chassery. How to improve pixel-based fractal image coding with adaptive partitions, in Fractals in Engineering, J.L. Vehel, E.Lutton, and C.Tricot, Eds. London, U.K.: Springer-verlag, 1997: 292-306.
[12]刘维胜,高占国,李力.分形图像编码的快速算法.计算机工程与应用, 2009, 45(9): 182-185.
[13]洪安祥,陈刚,吴炯峰,李均利.基于分型编码的图像相似匹配研究.电子学报, 2002, 30(5): 624-627.
[14]王兴元,陈志丰.快速的分形码图像检索方法.计算机科学与探索, 2009, 3(4): 423-432.
[15]何传江,黄席樾.基于图像块叉迹的快速分形图像编码算法.计算机学报, 2005, 28(10): 1753-1758.
[16]王志勇,池哲儒,余英林.分形编码在图像检索中的应用.电子学报, 2000, 28(6): 19-23.
[17]马燕,李顺宝. IFS分形码的快速图像检索算法.光电工程, 2006, 2(33): 81-84.
[18]何传江,刘维胜,申小娜.基于行列式的快速分形图像编码算法.中国图像图形学报, 2008, 3(13): 435-439.
[19]徐艳,王加俊.使用拼贴误差直方图的分形图像检索.电子与信息学报, 2006, 4(28): 603-605.
[20]刘明,叶正麟,陈作平.基于自适应分类的快速分形编码方法.中国图像图形学报, 2006,11(1):128-133.
[21]何传江,杨静.基于形态特征的快速分形图像编码.中国图像图形学报, 2005, 4(10): 410-414.
[22]裔传俊,徐涛.基于中间块比较的快速分形图像编码.中国图像图形学报, 2008, 1(13): 53-57.
[23]李高平,雷开彬.缩减码书的快速分形图像编码算法.中国图像图形学报, 2007, 3(12): 427-431.
[24]周明全,耿国华,韦娜.基于内容图像检索技术.北京:清华大学出版社, 2007.
[25] F.Jocob, Y. Fisher, R. Boss. Image compression: A study of the iterated transform method, Signal Process, 1992(29): 251-263.
[26] B. Hurtgen, C. Stiller. Fast hierarchical codebook search for fractal coding of still images, in Proc. EOS/SPIE Visual Communications PACS Medical Applications’93, Berlin, Germany, 1993.
[27]裔传俊.基于新型四叉树分割的快速分形图像编码.计算机与数字工程, 2009, 7(37): 151-153.
[28]吴一全,郭建军.基于Krawtchouk距的自适应门限四叉树分形编码.信号处理, 2009, 7(25): 1033-1037.
[29]陈卫红,张焕春,孙以雷.一种混合的四叉树分形图像编码.现代电子技术, 2006, 2: 39-42.
[30] Y. Fisher, S. Menlove. Fractal encoding with HV partitions, in Fractal Image Compression– Theory and Application, Y. Fisher, Ed. New York: Springer, 1994.
[31] Yu Liu, Ming Zhang, Fang Yuan. Fast Fractal Image Retrieval Algorithm Based On Contiguous- Matches. Machine Learning and Cybernetics, 2010(4): 2047-2052.
[2] Y.Fisher. Fractal image compression theory and application. Springer-Verlag, New York.1993.
[3] M.Barnsley, L.Hurd. Fractal Image Compression. AK Peters, Wellesley, 1993.
[4] Y.Fisher, S.Menlove. Fractal encoding with HV partions in Fractal Image Compression-Theory and Application, Y.Fisher, Ed.New York: Springer,1994.
[5] E.Reusens. Partitioning complexity issue for iterated function systems based image coding, in Proc. VIIth Eur. Signal Processing Conf. EUSIPCO, vol. 1, Edinburgh, U.K., 1994: 171-174.
[6] O.Peitgen, H.Jurgens, D.Saupe. Chaos and Fractals New Frontiers of Science, Spinger, New York, 1992.
[7] M.Novak. Attractor coding of images. In Proceedings of the International Picture Coding Symposium PCS’93, Lausanne, March 1993: 15-16.
[8] D.J.Jackson, W.Mahmoud, W.A.Stepleton, and R.T.Gaughan. Faster fractal image compression using recomposition, Image Vision Computing, 1997(15): 759-767.
[9] S.Kumar, R.C. Jain. Low complexity fractal-based image compression technique. IEEE Trans on Consumer Electronics, 1997(43): 987-993.
[10] F.Davoine. J.M.Chassery. Adaptive Delaunay triangulation for attractor image coding, in Proc. 12th Int. Conf. Pattern Recognition, Jerusalem, Israel, 1994.
[11] F.Davoine, G. Robert, J.M. Chassery. How to improve pixel-based fractal image coding with adaptive partitions, in Fractals in Engineering, J.L. Vehel, E.Lutton, and C.Tricot, Eds. London, U.K.: Springer-verlag, 1997: 292-306.
[12]刘维胜,高占国,李力.分形图像编码的快速算法.计算机工程与应用, 2009, 45(9): 182-185.
[13]洪安祥,陈刚,吴炯峰,李均利.基于分型编码的图像相似匹配研究.电子学报, 2002, 30(5): 624-627.
[14]王兴元,陈志丰.快速的分形码图像检索方法.计算机科学与探索, 2009, 3(4): 423-432.
[15]何传江,黄席樾.基于图像块叉迹的快速分形图像编码算法.计算机学报, 2005, 28(10): 1753-1758.
[16]王志勇,池哲儒,余英林.分形编码在图像检索中的应用.电子学报, 2000, 28(6): 19-23.
[17]马燕,李顺宝. IFS分形码的快速图像检索算法.光电工程, 2006, 2(33): 81-84.
[18]何传江,刘维胜,申小娜.基于行列式的快速分形图像编码算法.中国图像图形学报, 2008, 3(13): 435-439.
[19]徐艳,王加俊.使用拼贴误差直方图的分形图像检索.电子与信息学报, 2006, 4(28): 603-605.
[20]刘明,叶正麟,陈作平.基于自适应分类的快速分形编码方法.中国图像图形学报, 2006,11(1):128-133.
[21]何传江,杨静.基于形态特征的快速分形图像编码.中国图像图形学报, 2005, 4(10): 410-414.
[22]裔传俊,徐涛.基于中间块比较的快速分形图像编码.中国图像图形学报, 2008, 1(13): 53-57.
[23]李高平,雷开彬.缩减码书的快速分形图像编码算法.中国图像图形学报, 2007, 3(12): 427-431.
[24]周明全,耿国华,韦娜.基于内容图像检索技术.北京:清华大学出版社, 2007.
[25] F.Jocob, Y. Fisher, R. Boss. Image compression: A study of the iterated transform method, Signal Process, 1992(29): 251-263.
[26] B. Hurtgen, C. Stiller. Fast hierarchical codebook search for fractal coding of still images, in Proc. EOS/SPIE Visual Communications PACS Medical Applications’93, Berlin, Germany, 1993.
[27]裔传俊.基于新型四叉树分割的快速分形图像编码.计算机与数字工程, 2009, 7(37): 151-153.
[28]吴一全,郭建军.基于Krawtchouk距的自适应门限四叉树分形编码.信号处理, 2009, 7(25): 1033-1037.
[29]陈卫红,张焕春,孙以雷.一种混合的四叉树分形图像编码.现代电子技术, 2006, 2: 39-42.
[30] Y. Fisher, S. Menlove. Fractal encoding with HV partitions, in Fractal Image Compression– Theory and Application, Y. Fisher, Ed. New York: Springer, 1994.
[31] Yu Liu, Ming Zhang, Fang Yuan. Fast Fractal Image Retrieval Algorithm Based On Contiguous- Matches. Machine Learning and Cybernetics, 2010(4): 2047-2052.