This paper presents a short survey of the key research work that has been undertaken in the application of parallel algorithms for Fractal image compression. The interest in fractal image compression techniques stems from their ability to achieve high compression ratios whilst maintaining a very high quality in the reconstructed image. The main drawback of this compression method is the very high computational cost that is associated with the encoding phase. Consequently, there has been significant interest in exploiting parallel computing architectures in order to speed up this phase, whilst still maintaining the advantageous features of the approach. This paper presents a brief introduction to fractal image compression, including the iterated function system theory upon which it is based, and then a review on the different techniques that have been, and can be, applied in order to parallelize the compression algorithm.
References
1.
HuffmanD. A., “A Method for the Construction of Minimum-Redundancy Codes”, Proceedings of the Institute of Radio Engineers, 40 (9): 1098–1101, 1952.
2.
ZivJ.LempelA., “Universal Algorithm for Sequential Data Compression”, IEEE Transactions on Information Theory, 23 (3): 337–343, 1977.
3.
Video codec for audio visual services of Px64 Kbits/s. CCITT Recommendation H. 261, Aug. 1990.
4.
Digital Compression and Coding of Continuous-Tone Still Images Part 1, Requirements and Guidelines. ISO/IEC JTCI Committee Draft 10918–1.
5.
Digital Compression and Coding of Continuous-Tone Still Images Part 2, Compliance Testing. ISO/IEC JTCI Committee Draft 10918–2.
6.
LiouM. L., “Overview of the Px64 Kbits/s Video Coding Standard”, Communications of the ACM, Vol. 34, No. 4, 1991.
7.
WallaceGregory K., “The JPEG Still Picture Compression Standard”, Communications of the ACM, Vol. 34, No. 4, 1991.
8.
MallatS. G., “Multifrequency Channel Decomposition of Images and Wavelet Models”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 37, No. 12, 1989.
9.
JacquinA. E., “Fractal Image Coding: A Review”, Proceedings of the IEEE, Vol. 81, No. 10, 1993.
10.
FisherY., “Fractal Image Compression: Theory and Application”.New York: Springer-Verlag New York, Inc., 1995.
11.
WohlbergB. and JagerG. D., “A Review of the Fractal Image Coding Literature”, IEEE Transaction on Image Processing, Vol. 8, 1999.
12.
DongarraJ.WalkerD.LuskE.“Special Issue – MPI – A Message-Passing Interface Standard”, International Journal of Supercomputer Applications and High Performance Computing, 8 (3–4): 165-&, 1994.
ErjunZhaoDanLiu, “Fractal Image Compression Methods: A Review”, The Third International Conference on Information, Technology and Applications, ICITA2005 (Sydney), pp. 756–759, 2005.
15.
DistasiR.NappiM., and RiccioD., “A Range/Domain Approximation Error-Based Approach for Fractal Image Compression”, IEEE Trans. Image Process., vol. 15, No. 1, pp. 89–97, 2006.
16.
IanoY.SilvestreD. S., and CruzA. L. M., “A Fast and efficient Hybrid Fractal-Wavelet Image Coder”, IEEE Trans. Image Process., vol. 15, No. 1, pp. 98–105, 2006.
17.
KomlehH. E.ChandranV., and SridharanS., “Face Recognition Using Fractal”, Proc. Int. Conf. Image Processing, Vol. pp. 58–61, 2001.
18.
BeaumontJ. M., “Image Data Compression Using Fractal Techniques”, BT Techn. Journal, vol. 9, pp. 93–109, 1991.
19.
MelnikovG. and KatsaggelosA. K., “A Jointly Optimal Fractal/DCT Compression Scheme”, IEEE Trans. on Multimedia, vol. 4, No. 4, pp. 413–422, 2002.
20.
DavisG. M., “A Wavelet-Based Analysis of Fractal Image Compression”, IEEE Transaction on Image Processing, USA, Vol.No. 2, 1998.
21.
DistasiR.NappiM., and TucciM., “FIRT: Fractal Indexing with Robust Extensions for Image Databases”, IEEE Trans. Image Process., vol. 12, No. 3, pp. 373–384, 2003.
22.
HartensteinH.RuhlM., and SaupeD., “Region-based fractal image compression”, Image Processing, IEEE Transactions on, vol. 9, pp. 1171–1184, 2000.
23.
BelloulataK. and KonradJ., “Fractal image compression with region-based functionality”, Image Processing, IEEE Transactions on, vol. 11, pp. 351–362, 2002.
24.
WohlbergB. and JagerG. D., “A Review of the Fractal Image Coding Literature”, IEEE Transaction on Image Processing, Vol.No. 12, 1999.
25.
PolvereM. and NappiM., “Speed-up in Fractal Image Coding-Comparison of Methods”, IEEE Trans. Image Process., Vol. 9, pp. 1002–1009, 2000.
26.
TongC. S. and PiM., “Fast Fractal Image Encoding Based on Adaptative Search”, IEEE Trans. Image Process., Vol. 10, pp. 1269–1277, 2001.
27.
LiJ.ChenG., and ChiZ., “A Fuzzy Image Metric with Application to Fractal Coding”, IEEE Trans. Image Process., Vol. 11, pp. 636–643, 2002.
28.
TongC. S. and WongM., “Adaptative Approximate Nearest Neighbor Search for Fractal Image Compression”, IEEE Trans. Image Process., Vol. 11, pp. 605–615, 2002.
29.
RinaldoR. and CalvagnoG., “Image Coding by Block Prediction of Multiresolution Subimages”, IEEE Trans. Image Process., Vol. 4, pp. 909–920, 1995.
30.
DuhD. J.JengJ. H., and ChenS. Y., “DCT-based Simple Classification Scheme for Fractal Image Compression”, Image and Vision Computing, Vol. 23, pp. 1115–1121, 2005.
31.
IanoY.SilvestreD. S., and CruzA. L. M., “A Fast and Efficient Hybrid Fractal-Wavelet Image Coder”, IEEE Trans. Image Process., Vol. 15, pp. 98–105, 2006.
32.
HerI., “Geometric Transformations on the hexagonal Grid”, IEEE Transaction on Image Processing, vol. 4, 1995.
33.
PalazzariP.ColiM., and LulliG.. “Massively parallel processing approach to fractal image compression with near-optimal coefficient quantization”. Journal of Systems Architecture45. 765–779, 1999.
34.
UhlA., and HammerleJ.. “Fractal Image Compression on MIMD architectures I: Basic Algorithms”. The First International Conference on Visual Information Systems.1996.
35.
BodoZ. P.. “Maximal processor utilization in parallel quadtree-based fractal image compression on MIMD Architectures”. Informatica.Volume XLIX (2). 2004.
36.
MinX.HansonT., and MerigotA.. “A massively parallel implementation of fractal image compression”. IEEE International Conference on Image Processing.1994.
37.
ErraU., “Toward real time fractal image compression using graphics hardware”, Advances in Visual Computing, proceedings lecture notes in computer science3804:723–728, 2005.
38.
AckenK. P.KimH. N.IrwinM. J. and OwensR. M., “An architecture design for parallel fractal compression”, Application Specific Sysytems, Architectures and Processors, 1996.
39.
JacksonD. J., and BlomT.. “A parallel fractal image compression algorithm for hypercube multiprocessors”. 27th Southern Symposium on System Theory.274–278. 1995.
40.
HammerleJ., and UhlA.. “Approaching Real-time Processing for Fractal Compression”.
41.
JacksonD. J., and TinneyG. S.. “Performance analysis of distributed implementation of a fractal image compression algorithm”. Concurrency-Practice and Experience8 (5): 357–386. 1996.
42.
LeeS.OmachiS., and AsoH.. “A parallel architecture for quadtree-based fractal image coding”. Proceedings of 2000 International Conference on Parallel Processing.15–22. 2000.
43.
JacksonD. J., and MahmoudW.. “Parallel Pipelined Fractal Image Compression using Quadtree Recomposition”. The Computer Journal.Vol. 39 (1): 1–13. 1996.
44.
JacksonD. J., and HumphresC. W.. “A simple yet effective load balancing extension to the PVM software system”. Parallel Computing22. 1647–1660. 1997.
45.
HufnaglC., and UhlA.. “Algorithms for Fractal Image Compression on Massively Parallel SIMD Arrays”. Real-Time Imaging6. 267–281. 2000.
46.
PommerA.. “Fractal Video compression on shared memory systems”. Parallel Computation Lecture Notes in Computer Science1557: 317–326. 1999.
47.
HammerleJ., and UhlA.. “Improving the Efficiency of Parallel Fractal Compression using Localized Domain-pools”.
48.
HammerleJ., and UhlA.. “Fractal Image Compression on MIMD architectures II: Classification Based Speed-up Methods”. The Fourth International Conference of the ACPC.1999.
49.
WuX. W.JacksonD. J., and ChenH. C.. “A fast fractal image encoding method based on intelligent search of standard deviation”. Computers and Electrical Engineering31: 402–421. 2005.
50.
ZhouC. G.MengK., and QiuZ. L.. “A fast fractal image compression algorithm based on average-variance function”. IEICE TRANS. INF. & SYST.Vol. E89-D (3). 2006.
51.
DistasiR.NappiM., and RiccioD.. “A range/domain approximation error-based approach for fractal image compression”. IEEE Transactions on Image Processing., Vol. 15(1). 2006.
52.
WangM. Q.HuangZ. H.LaiC. H.. “Matching search in fractal video compression and its parallel implementation in distributed computing environments”Applied Mathematical Modelling30 (2006) 677–687. 2006.
53.
HammerleJ., and UhlA.. “Classification based speed-up methods for fractal image compression on multicomputers”. Parallel Computation Lecture Notes in Computer Science1557:276–285. 1999.
54.
ChangH. T., and KuoC. J., “Intrinsic parallel random iteration algorithm for fractal image decoding based on iterated function system code”, Optical Engineering44(3), 2005.
55.
DederaL., and ChmurnyJ.“A parallel approach to image decoding in the Fractal image block coding scheme”.
56.
PeiS. C.TsengC. C., and LinC. Y.. “A parallel decoding algorithm for IFS codes without transient behavior”. IEEE Transactions on Image Processing.Vol. 5 (3). 411–415. 1996.
CybenkoG., “Dynamic Load Balancing for Distributed Memory Multiprocessors”, J. of Parallel and Distributed Computing, 7, 279–301, 1989.
59.
TouheedN.SelwoodP.JimackP. K., & BerzinsM. A., “Comparison of Some Dynamic Load-Balancing Algorithms for a Parallel Adaptive Flow Solver”, Parallel Computing, vol. 26, pp. 1535–1554, 2000.
