分形视频图像压缩并行算法设计
摘要
随着我国国民经济的快速发展,越来越多的科研和工程应用部门对大规模科学与工程数值计算提出了挑战性需求,而并行计算是满足这些需求的必要途径。大规模的科学计算需要通过高性能计算机实现,高性能计算机是一个所有最先进的硬件、软件、网络和算法的综合概念,“高性能”的标准是随着技术的发展而发展的。高性能计算机的应用和研制水平是一个国家综合实力的标志之一。
分形图像压缩方法是利用图像内部块与块之间的自相似性来编制软件的图像压缩算法,它具有很高的压缩比。分形视频压缩是分形图像压缩的扩展,巨大的计算量限制了它的应用和研究,只有在计算机硬件发展到一定程度时分形压缩算法的实现才比较容易。在分形视频压缩的匹配过程中,各个帧组之间或帧内各部分之间的匹配过程是相互无关的,存在数据并行性,因此可以通过并行计算来缩短压缩时间。
本文针对分形视频压缩中值域立方体搜索过程中的数据无关性,研究和设计了分形视频压缩的并行算法; 通过对几种可扩展的并行计算机的体系结构和并行程序设计模型的分析和比较,本文在分布共享并行机上实现了基于MPI的分形视频压缩算法,将图像的定义域块和值域块的搜索匹配过程分配给多台处理器同时执行。MPI是目前一种比较著名的应用于并行环境的消息传递标准,MPI提供了一种与语言和平台无关、可以被广泛使用的编写消息传递程序的标准。
实验结果表明,采用基于MPI的并行算法对分形视频图像进行压缩,可以在不改变压缩比的情况下,缩短压缩时间,取得很高的加速比。同时我们进行了可扩展性测试,经过实验数据验证,该并行算法具有较好的扩展性。
并行计算具有巨大的数值计算和数据处理能力,采用并行计算系统可以实现图像的实时压缩,在网格环境下可以做为图像处理的服务器程序,因此具有很强的实用性和广泛的应用前景。
With the rapid development of the national economy, many science and engineering research departments and institutes wish to deal with ever larger problems in scientific computing. Parallel computing is a possible way to fulfill such desires. Many large-scale scientific computations require high-performance computers to implement the computing tasks. High-performance computer is a broad computer science subject dealing with advanced hardware, software, network, and algorithms. Progress in the standard of high-performance is along with the development of technology. The application and research level of high-performance computer indicates the general scientific advancement of a country.
This thesis examines parallel algorithms for fractal image compression which is based on the self-similarity search between range and domain blocks, so it can achieve a high compression ratio. Fractal compression of video sequences is the extension of fractal still image compression which has a high computational complexity that restricts its commercial applications. The implementation of the compression algorithm depends on the high configuration of computer hardware. In the process of performing fractal video compression, searching and matching image blocks between each group of frames are independent from each other. As a result compression time can be greatly reduced by using parallel computing.
Due to the independent feature of the process of searching cube range blocks in a fractal video compression system this thesis examines the design of a suitable parallel algorithm for fractal video compression and the performance of such algorithm. An overview of of several different systematic structures of scalable parallel computers and parallel programming model suggested that MPI seems to be a good candidate for implementing fractal video compression algorithms based on distributed-memory parallel computers. The searching and matching process of domain blocks and range blocks of the image is assigned to several processors to execute. MPI is commonly used message passing library for parallel environment. MPI provides a criterion which is independent of language and platform and can be widely used for making message passing programs.
Experimental results show that the parallel algorithm is able to reduce the
compression time and achieve a high speedup without changing the compression rate. A scalability test has also performed, and results show that this parallel algorithm is scalable. Parallel computing is particularly suitable in treating data parallel processing, has the potential of achieving real-time compression of images, and can be used as the server program for image processing. The parallel algorithms developed in this thesis is industrial practical and will certainly become a promising tool in image compression and processing.
分形图像压缩方法是利用图像内部块与块之间的自相似性来编制软件的图像压缩算法,它具有很高的压缩比。分形视频压缩是分形图像压缩的扩展,巨大的计算量限制了它的应用和研究,只有在计算机硬件发展到一定程度时分形压缩算法的实现才比较容易。在分形视频压缩的匹配过程中,各个帧组之间或帧内各部分之间的匹配过程是相互无关的,存在数据并行性,因此可以通过并行计算来缩短压缩时间。
本文针对分形视频压缩中值域立方体搜索过程中的数据无关性,研究和设计了分形视频压缩的并行算法; 通过对几种可扩展的并行计算机的体系结构和并行程序设计模型的分析和比较,本文在分布共享并行机上实现了基于MPI的分形视频压缩算法,将图像的定义域块和值域块的搜索匹配过程分配给多台处理器同时执行。MPI是目前一种比较著名的应用于并行环境的消息传递标准,MPI提供了一种与语言和平台无关、可以被广泛使用的编写消息传递程序的标准。
实验结果表明,采用基于MPI的并行算法对分形视频图像进行压缩,可以在不改变压缩比的情况下,缩短压缩时间,取得很高的加速比。同时我们进行了可扩展性测试,经过实验数据验证,该并行算法具有较好的扩展性。
并行计算具有巨大的数值计算和数据处理能力,采用并行计算系统可以实现图像的实时压缩,在网格环境下可以做为图像处理的服务器程序,因此具有很强的实用性和广泛的应用前景。
With the rapid development of the national economy, many science and engineering research departments and institutes wish to deal with ever larger problems in scientific computing. Parallel computing is a possible way to fulfill such desires. Many large-scale scientific computations require high-performance computers to implement the computing tasks. High-performance computer is a broad computer science subject dealing with advanced hardware, software, network, and algorithms. Progress in the standard of high-performance is along with the development of technology. The application and research level of high-performance computer indicates the general scientific advancement of a country.
This thesis examines parallel algorithms for fractal image compression which is based on the self-similarity search between range and domain blocks, so it can achieve a high compression ratio. Fractal compression of video sequences is the extension of fractal still image compression which has a high computational complexity that restricts its commercial applications. The implementation of the compression algorithm depends on the high configuration of computer hardware. In the process of performing fractal video compression, searching and matching image blocks between each group of frames are independent from each other. As a result compression time can be greatly reduced by using parallel computing.
Due to the independent feature of the process of searching cube range blocks in a fractal video compression system this thesis examines the design of a suitable parallel algorithm for fractal video compression and the performance of such algorithm. An overview of of several different systematic structures of scalable parallel computers and parallel programming model suggested that MPI seems to be a good candidate for implementing fractal video compression algorithms based on distributed-memory parallel computers. The searching and matching process of domain blocks and range blocks of the image is assigned to several processors to execute. MPI is commonly used message passing library for parallel environment. MPI provides a criterion which is independent of language and platform and can be widely used for making message passing programs.
Experimental results show that the parallel algorithm is able to reduce the
compression time and achieve a high speedup without changing the compression rate. A scalability test has also performed, and results show that this parallel algorithm is scalable. Parallel computing is particularly suitable in treating data parallel processing, has the potential of achieving real-time compression of images, and can be used as the server program for image processing. The parallel algorithms developed in this thesis is industrial practical and will certainly become a promising tool in image compression and processing.
引文
[1] Kai Hwang.高等计算机系统结构:并行性,可扩展性,可编程性. 北京:清华大学出版社,1995.
[2] 王美清,郑守淇,郑文波.JDCS:实现高性能计算的分布式计算系统.计算机工程与应用,2002,38(21):79~82.
[3] 黄哲煌,王美清.分布计算技术及其在分形视频压缩中的应用:[硕士学位论文].福州:福州大学,2004.
[4] 都志辉.高性能计算之并行编程技术——MPI 并行程序设计.清华大学出版社 , 2001.
[5] 胡志刚,唐小龙,钟掘.基于 PVM 的并行分布计算中的任务调度策略.计算机工程, 2001,27(3) :25~26.
[6] A.E.Jacquin.A Fractal Theory of Iterated Markov Operators with Applications to Digital Image Coding.PhD Thesis,Georgia Institute of Technology,August 1989.
[7] J.M.Beamount.Image data compression using fractal techniques. British Telecommunications Technical Journal,Vol.9,pp.93-109,Oct 1991.
[8] Y.Fisher , D.Rogovin and T. P. Shen. . Fractal (self-VQ) Encoding of VideoSequences.In :Proceedings of the SPIE,Visual Communications and Image Processing,Chicago, USA, Sept. 25~28, 1994.
[9] 王美清,郑守淇.分布并行的分形视频压缩技术.计算机工程与应用,Vol.38, No.11: 50-52, 2002.
[10] Gilly, Daniel Unix in a nutshell : System V edition / Daniel Gilly and the staff of O'Reil . -2nd ed. . -Sebastopol, CA : O'Reilly & Associates, 1994 .
[11] Hahn, Brian D. Problem solving with Fortran 77 . -London : Edward Arnold, 1987 .
[12] D. Saupe, R. Hamzaoui, H. Hartenstein.Fractal image compression — an introductory overview. In D. Saupe, J. Hart (eds.), Fractal Models for Image Synthesis, Compression and Analysis, ACM SIGGRAPH'96 Course Notes 27, New Orleans, Louisiana, Aug. 1996.
[13] 肖侬,黄金锋,卢宇彤.网络并行计算的动态负载平衡策略.计算机工程与科学,1998,20(3) :13~17.
[14] T.M.R. Ellis,Ivor R. Philips,Thomas M.Lahey, Fortran 90 programming -Addison-Wesley Publishing Company,1994.
[15] 陈国良.并行计算—结构.算法.编程.北京:高等教育出版社,1999.175~178.
[16] 于玲,李金宝,张淑娟.用 DCOM 实现并行与分布式计算.黑龙江大学自然科学学报, 2002,19(2) :58~61.
[17] Smith, I. M. (Ian Moffat), 1940-Programming in Fortran 90 : a first course for engineers and scientists . -Chichester : Wiley, 1995 .
[18] 秦军,孟丹,古志民.Java RMI 及多线程技术在机群管理系统中的应用.计算机工程与应用,2004,40(13) :108~110.
[19] 李晓梅. 并行算法. 湖南科技出版社,1992
[20] 沈志宇. 并行程序设计. 国防科大出版社,1997
[21] Foster I. Designing and building parallel programs: concepts and tools for parallel software engineering, Addison-Wesley, 1995
[22] Andrews G R. Foundations of multithreaded parallel, and distributed programming,Pearson Education, 2002
[23] Akl S G.. The design and analysis of parallel algorithms. Prentice-Hall, Inc, 1989
[24] Buyya R. High performance cluster computing. Prentice-Hall, Inc, 1999
[25] 陈登伟,鲁智勇.网络动态负载均衡算法分析.现代电子技术,2003,26(21):81~84.
[26] 朱福喜 ,何炎祥.并行分布计算中的调度算法理论与设计.湖北: 武汉大学出版,2003
[27] Balfour, A. (Alexander) Programming in Standard Fortran 77 / A. Balfour, D.H. Marwick . -London : Heinemann Educational, 1979 .
[28] M. Barnsley, L. Hurd.Fractal Image Compression.A K Peters, Wellesley, 1993.
[29] E. Jacquin.Image coding based on a fractal theory of iterated contractive image transformations.IEEE Trans. Image Processing, 1 : 18 – 30, 1992.
[2] 王美清,郑守淇,郑文波.JDCS:实现高性能计算的分布式计算系统.计算机工程与应用,2002,38(21):79~82.
[3] 黄哲煌,王美清.分布计算技术及其在分形视频压缩中的应用:[硕士学位论文].福州:福州大学,2004.
[4] 都志辉.高性能计算之并行编程技术——MPI 并行程序设计.清华大学出版社 , 2001.
[5] 胡志刚,唐小龙,钟掘.基于 PVM 的并行分布计算中的任务调度策略.计算机工程, 2001,27(3) :25~26.
[6] A.E.Jacquin.A Fractal Theory of Iterated Markov Operators with Applications to Digital Image Coding.PhD Thesis,Georgia Institute of Technology,August 1989.
[7] J.M.Beamount.Image data compression using fractal techniques. British Telecommunications Technical Journal,Vol.9,pp.93-109,Oct 1991.
[8] Y.Fisher , D.Rogovin and T. P. Shen. . Fractal (self-VQ) Encoding of VideoSequences.In :Proceedings of the SPIE,Visual Communications and Image Processing,Chicago, USA, Sept. 25~28, 1994.
[9] 王美清,郑守淇.分布并行的分形视频压缩技术.计算机工程与应用,Vol.38, No.11: 50-52, 2002.
[10] Gilly, Daniel Unix in a nutshell : System V edition / Daniel Gilly and the staff of O'Reil . -2nd ed. . -Sebastopol, CA : O'Reilly & Associates, 1994 .
[11] Hahn, Brian D. Problem solving with Fortran 77 . -London : Edward Arnold, 1987 .
[12] D. Saupe, R. Hamzaoui, H. Hartenstein.Fractal image compression — an introductory overview. In D. Saupe, J. Hart (eds.), Fractal Models for Image Synthesis, Compression and Analysis, ACM SIGGRAPH'96 Course Notes 27, New Orleans, Louisiana, Aug. 1996.
[13] 肖侬,黄金锋,卢宇彤.网络并行计算的动态负载平衡策略.计算机工程与科学,1998,20(3) :13~17.
[14] T.M.R. Ellis,Ivor R. Philips,Thomas M.Lahey, Fortran 90 programming -Addison-Wesley Publishing Company,1994.
[15] 陈国良.并行计算—结构.算法.编程.北京:高等教育出版社,1999.175~178.
[16] 于玲,李金宝,张淑娟.用 DCOM 实现并行与分布式计算.黑龙江大学自然科学学报, 2002,19(2) :58~61.
[17] Smith, I. M. (Ian Moffat), 1940-Programming in Fortran 90 : a first course for engineers and scientists . -Chichester : Wiley, 1995 .
[18] 秦军,孟丹,古志民.Java RMI 及多线程技术在机群管理系统中的应用.计算机工程与应用,2004,40(13) :108~110.
[19] 李晓梅. 并行算法. 湖南科技出版社,1992
[20] 沈志宇. 并行程序设计. 国防科大出版社,1997
[21] Foster I. Designing and building parallel programs: concepts and tools for parallel software engineering, Addison-Wesley, 1995
[22] Andrews G R. Foundations of multithreaded parallel, and distributed programming,Pearson Education, 2002
[23] Akl S G.. The design and analysis of parallel algorithms. Prentice-Hall, Inc, 1989
[24] Buyya R. High performance cluster computing. Prentice-Hall, Inc, 1999
[25] 陈登伟,鲁智勇.网络动态负载均衡算法分析.现代电子技术,2003,26(21):81~84.
[26] 朱福喜 ,何炎祥.并行分布计算中的调度算法理论与设计.湖北: 武汉大学出版,2003
[27] Balfour, A. (Alexander) Programming in Standard Fortran 77 / A. Balfour, D.H. Marwick . -London : Heinemann Educational, 1979 .
[28] M. Barnsley, L. Hurd.Fractal Image Compression.A K Peters, Wellesley, 1993.
[29] E. Jacquin.Image coding based on a fractal theory of iterated contractive image transformations.IEEE Trans. Image Processing, 1 : 18 – 30, 1992.