Visual Communications and Image Processing, SPIE’94, Chicago Fractal transform coding of c

Visual Communications and Image Processing,SPIE’94,Chicago

Fractal transform coding of color images

Bernd H¨u rtgen,Paul Mols,and Stephan F.Simon

Institut f¨u r Elektrische Nachrichtentechnik

RWTH,Rheinisch-Westf¨a lische Technische Hochschule Aachen

52056Aachen,Germany,Tel.:+49–241–807683,Fax:+49–241–8888–196

Email:huertgen@ient.rwth-aachen.de

ABSTRACT

The paper reports on investigations concerning the application of block oriented fractal coding schemes for encoding of color images.Correlations between the different color planes can be exploited for the aim of data compression.For this purpose the similarities between the fractal transform parameters of one block location but different color planes are regarded in a blockwise manner.Starting-point is the fractal code for one block in the dominant color plane which serves as prediction for the code of the corresponding block in the other planes.Emerging from this prediction the depending codes can be derived by a successive re?nement strategy.Since the fractal code for the dominant color plane and the re?nement information for determining the code for the other planes can be represented with fewer bits compared to the independently calculated ones, a coding gain can be achieved.

Keywords:fractal coding,attractor coding,still image coding,color image coding

1.INTRODUCTION

During the last years a novel coding and modeling scheme for natural signals has been developed which is widely known as fractal coding.The basic idea for encoding of signals by use of fractal techniques is originated in various publications of Barnsley et al,e.g.[1,2,3].A?rst implementation of an automatic encoding routine for gray-scale images at common compression ratios has been proposed by Jacquin[4,5,6].A review on fractal image coding may be found in[7]and an excellent mathematical foundation of fractal signal modeling is contained in[8].Recently some improvements and modi?cations have been published,e.g.[9,10,11,12,13],which made the fractal technique a challenging candidate for encoding of images especially if high compression is the issue.

In principle the encoding process consists in?nding for each part of the image another part,which after some sort of translation,scaling,rotation,and mirroring?ts best in the sense of some given distortion measure.Though the shape of the image parts is arbitrary,most authors use square blocks.The encoding operation results in a number of parameters which after quantization serve as fractal code for this particular block.The parameters of all blocks together then form the code for the entire signal.A coding gain can be achieved if all parameters can be represented with fewer bits than the signal itself.

Currently the investigations concerning fractal coding schemes nearly exclusively concentrate on gray-scale images though in order to present a complete encoding scheme also color information has to be included.Therefore color image coding based on fractal techniques demands for further research.There are only three sources on this topic known to the author,from which[14]and[15]are based on the yard stick method but which is discarded in this paper.The only block-oriented approach which also serves as basis for this paper is published in[16].

The physiology of the human eye motivates the trichromatic theory of color vision,which states that the color of light received by the human observer may be speci?ed by a mixture of only three primary colors.These are usually chosen to be either red,green,and blue which are the primary colors of light,or yellow,magenta,and cyan which are the primary colors of pigments.Hence color images consist of three image planes each representing a different spectral area.Due to the physical effect of image generation these planes are highly correlated.

The purpose of this paper is to illustrate how these correlations can be used for data compression purposes within a fractal coding environment.It is proposed to exploit the dependencies between the fractal codes of the different color planes within the transform domain rather than treating them in the original domain.The results show that jointly encoding blocks of different color planes but of the same spatial location results in a signi?cant decrease in bits necessary for representing the fractal code of the entire image.

1683

Visual Communications and Image Processing,SPIE’94,Chicago

For this purpose the main characteristics of all fractal parameters describing an image block are investigated.It is shown, that for the same block location in different color planes not only the pixel intensities but also the parameters of the fractal code are highly correlated.Hence only slight modi?cations of the fractal code for one color plane are necessary in order to describe the other planes with suf?cient accuracy.

After presenting the necessary mathematical foundation of fractal coding in section2,section3deals with encoding of images in general.After describing the application of fractal coding schemes to gray-scale images in topic3.1,some important characteristics of the different fractal coef?cients representing an image block are investigated.This leads to the problem of quantization which is addressed in3.2.Emphasis is put on topic3.3which describes how correlations between the different color planes can be exploited within the fractal domain.The paper concludes with some simulation results and a prospect on future investigations in section4.

2.MATHEMATICAL FOUNDATION

Consider a signal consisting of sample values as point in the n-dimensional vector space.With the de?nition of the Euclidean norm

(1)

de?ned by the square root of the inner product and by inducing a metric

(2)

the vector space becomes a normed metric space denoted by.Transformations within this space can be described by a linear operator for which a consistent operator-or matrix norm is the so called spectral-or Hilbert norm,de?ned by

(3)

which is the square root of the largest eigenvalue in magnitude of the matrix.Additionally for every linear operator the spectral radius is de?ned by

(4)

which is the magnitude of the largest eigenvalue of.Any norm and spectral radius of a linear operator are connected through the following equations:

(5) 2.1.Fractal encoding

All existing practical implementations of block-oriented fractal coding schemes emerge from an af?ne transformation which is capable of performing scaling,rotating,mirroring,and shifting operations in order to exploit the presupposed self-similarities of the signal.An af?ne transformation of the entire signal is de?ned by

(6)

consisting of a linear part and an additive part.The transformation is called contractive if there exists a constant factor,such that

(7)

1684

Visual Communications and Image Processing,SPIE’94,Chicago

With the de?nition of the metric(2),the af?ne transformation(6),and the contractivity(7)we obtain the suf?cient condition

(8)

for contractivity in the sense of any norm.

The encoding process for a given signal now consists in?nding a contractive transformation and a vector such that the approximation error

(9)

is as small as possible.Below it is shown that for reconstruction at the decoder only the knowledge of the transformation is necessary.Therefore data compression can be achieved,if the transformation can be represented with fewer bits than the signal itself.

2.2.Fractal decoding

Banach’s?xed point theorem gives us an idea how the decoding process works:

Let be a contractive transformation and a metric space with metric.Then the sequence of signals constructed by converges for any arbitrary initial signal to the unique?xed point of the transformation,i.e.

(10)

The reconstruction error between the original signal and its fractal reconstruction is then bounded by

(11)

The contractivity condition(8)is suf?cient but not necessary for the convergence of the iteration process.For af?ne transformations a suf?cient and necessary condition can be formulated by using the spectral radius of the transformation matrix.Emerging from any arbitrary initial signal the decoder iteratively applies the transformation(6).For the k-th iterate then follows

(12)

k times

If and only if the spectral radius satis?es,then and with the identity and the null matrix[17].Hence the sequence converges to the?xed point of the transformation

(13)

Due to the fact that not the original signal itself,but a?xed point of a contractive transformation which is close to the signal, is encoded,fractal coding sometimes is termed attractor coding.

3.FRACTAL IMAGE CODING

3.1.Encoding of gray-scale images

In contrast to common transformations,e.g.DCT,whose coding gain emerges from the correlations of adjacent samples,fractal coding schemes mainly exploit some sort of long range correlations also termed self-similarities within the signal.For practical reasons fractal coding schemes operate in a block-oriented manner which allows describing them as vector quantization with signal dependent codebook.

1685

Visual Communications and Image Processing,SPIE’94,Chicago

The image consisting of pixels is segmented into non-overlapping image blocks with elements.Then for each of these blocks one codebook entry from a set of entries is selected which after scaling with and adding an offset minimizes some given distortion measure

(14)

The codebook is generated from the image itself by use of a codebook construction matrix.If denotes the’fetch-operation’of the codebook entry from the codebook and the’put-operation’of the modi?ed codebook entry into the approximation,the mapping process for the entire image may be formulated by

(15)

This represents an af?ne transformation consisting of a linear part and a non-linear offset which together form the fractal code for the approximation of the original signal.

3.2.Quantization of the transform parameters

For a fractal based transmission and storage system the fractal code must be represented by a number of bits which should be as small as possible.For the sake of simpli?cation the fractal code is treated in a blockwise manner with each block code regarded independently from all others,so no inter-block DPCM is performed.The block code itself consists of four different parts,the scaling coef?cient,the index for the codebook entry,the type of isometric transformation which has to be applied to the codebook entry,and the gray-scale offset.The?rst three parameters for all blocks are contained in the transformation matrix and the gray scale offset in the vector.Since and are real valued,a quantization step is necessary as outlined below.

coef?cient for.and the quantization of the scaling coef?cient.

Fig.1shows the Gaussian like histogram of the scaling coef?cient derived from a large number of test images.Practical implementations restrict the scaling coef?cients to the range.For convergence of the reconstruction process can be guaranteed without any additional computational c79245c68bd63186bcebbc5eputer simulation showed that also for larger scaling coef?cients a convergent reconstruction is obtained in most cases,but then a complex eigenvalue analysis of the transformation matrix is necessary in order to decide whether the reconstruction converges or not.Details about the convergence properties of fractal coding schemes may be found in[18,19].The quantization of the scaling coef?cients is rather uncritical since only this codebook entry together with its appropriate quantized scaling coef?cient is selected which ?ts best in the sense of the used distortion measure.In practical implementations2,3or4bit have proven to be suf?cient for the quantization of the scaling coef?cients.As can be seen in Fig.2the number of bits spent for the scaling coef?cients also in?uences the optimal bound ranging from1.2to2.5.

1686

Visual Communications and Image Processing,SPIE’94,Chicago

The second real valued parameter within the fractal code is the vector containing the gray-scale offsets for each block within the image.Its histogram is depicted in Fig.3.Depending on the desired reconstruction quality three to eight bits have been found to be suf?cient for its representation.

error for.

The correlation coef?cient between scaling and offset parameter is in the range0.7...0.95depending on the image and the allowed scaling coef?cients.This indicates that some additional savings in terms of bits necessary for representing the fractal code can be obtained,if those correlations are exploited.Fig.5shows that a prediction for the offset,which is linear in the scaling coef?cient,might be suited for these purpose.Here are the parameters describing the regression line as plotted in Fig.5.

coef?cient and gray-scale offset.codebook for each block contains24,26,28,or210

entries,represented by4,6,8,or10bits respectively.

Due to the restriction of the scaling coef?cients and the range of allowed gray-scale values,also the offset parameters are constrained restricted.Its permissible range as function of the actual scaling coef?cient is outlined in Fig.5.Instead of quantizing and encoding the gray-scale offset independently from the scaling coef?cient the prediction serves as an estimate for and therefore only the prediction error needs to be transmitted.The advantage of this procedure can be seen easily from the histogram of the offset parameter(Fig.3)and the prediction error(Fig.4).Since the distribution of the prediction error has a signi?cantly smaller variance,it can be encoded with fewer bits compared with direct encoding of the offset parameter.

Additionally an index for the selected codebook entry must be included in the fractal code.The required number

1687

Visual Communications and Image Processing,SPIE’94,Chicago

of bits is determined by the size of the codebook which typically contains about24–210entries and signi?cantly in?uences the available reconstruction quality.Moreover the codebook entry might be isometrically transformed in one of eight ways. Since all types of isometric transformations are approximately selected with same probability a three bit long?xed length code is additionally needed.Summarizing,one block can be represented by11–25bits,depending on the desired image?delity. The available reconstruction quality in terms of the SNR for a typical test image and for various choices of the bit allocation is displayed in Fig.6.

3.3.Application to color images

All statements carried out in the previous topics dealt with encoding of gray-scale images or images consisting of only one image plane.In order to present a complete encoding scheme for images,also the treatment of“multispectral images”should be considered.The following paragraphs describe the extension of the ordinary fractal coding scheme to a scheme capable of encoding color images.We restrict our investigations to RGB and YUV images,but the algorithm may easily be extended to other color spaces.

In the area of computer vision color images mostly are associated with three different sets of data each describing a different spectral domain of the same scenery.The color image itself is the composition of these sets.This is due to the fact that the color of light received by the human observer may be speci?ed by a mixture of only three so-called primary colors.In the RGB space the primary colors are chosen to be red,green,and blue.In the YUV space the Y component contains the information about the intensity of the light whereas the U and V components contain the color information.For natural images the three image planes are highly correlated.In the RGB color space the correlation coef?cient between two of the planes is about0.78 for blue-red,0.89for red-green and0.94for green-blue,respectively.This indicates that signi?cant improvements in terms of compression and/or reconstruction quality can be expected if those correlations are exploited.

The presented algorithm is based on the proposal published in[16].It is shown that exploiting the correlations between the fractal codes of the different color planes for one block location results in a signi?cant decrease in bits necessary for representing the fractal code for the entire image.For this purpose the parameters of the transform domain rather than the samples of the original domain are treated.It is shown that for the same block location in different color planes not only the pixel intensities but also the parameters of the fractal code are highly correlated.Hence only slight modi?cations of the fractal code for one color plane are necessary in order to describe the other planes with suf?cient accuracy.

For the RGB color space the principal encoding procedure may be described exemplarily as follows:First the green or master component is encoded independently from the other ones which yields the master code.Green has been chosen for the master component because it possesses the largest correlation coef?cient to the other components.This is also con?rmed by a slightly better reconstruction quality as is reported in[16].Initially the master code is also assigned to the slave components red and blue,so that.This is of course an insuf?cient description for some blocks of the slave components,so that for those blocks a successive modi?cation of the encoding parameters is performed until a suf?cient reconstruction quality for all color planes is achieved.Then both slave codes are only variations of the master code. The transition functions with describing the modi?cations of the master code in order to get the slave code are much less complex and therefore may be stored with fewer bits than the slave codes themselves.Storing the master code and the two transition functions is much more ef?cient than storing all three codes independently from each other.The two slave components are treated equally since there is no advantage in regarding the third component as function of the second one.

step codebook entry type of isometry

scaling

coef?cient

gray-scale offset

1old old old old

2old old old new

3old old new new

4old new new new

5new new new new

Tab. 1.Order of recalculating the different encoding parameters for the slave components.

In detail the process works as follows:The green component is encoded just the same way as an ordinary gray-scale image.Then the fractal code of the green component is blockwise assigned to the slave components red and blue.If some error

1688

Visual Communications and Image Processing,SPIE’94,Chicago

criterion is met the master code is also suitable for describing the slave components with suf?cient accuracy and encoding of this particular block is?nished after step one as is indicated in Tab.1.If the reconstruction error is to large a recalculation of the gray-scale offset is performed(step2).If still no suf?cient approximation is obtained the remaining transform parameters which are the scaling coef?cient(step3),the type of isometric transformation(step4),or even the codebook entry itself(step5) are recalculated.

In the same way as described above for the RGB space the encoding procedure can also be performed on the basis of the YUV color space.Naturally the luminance component Y is chosen to be the master component whereas the chrominance signals U and V are the slave components.Tab.2depicts for the test image“lena”up to which step the slave code must be re?ned in order to get a suf?cient reconstruction quality for the RGB and YUV color space.One can see that for both color spaces a recalculation of the type of isometric transformation(step4)without also determining a new codebook entry is very rare.Therefore this step may be omitted so that if no suf?cient approximation is obtained after determining a new scaling coef?cient,a new codebook entry together with an appropriate isometric transformation is selected.Hence,two bits are suf?cient for determining the type of slave transformation.

component step1step2step3step4step5

Y----4096

U27238031902

V17926492311432

G----4096

R281308829431402

B1120240710014455

Tab. 2.Number of slave blocks for which a re?nement of the fractal code has to be performed.

4.IMPLEMENTATION,RESULTS AND CONCLUSIONS

The reconstruction quality is essentially determined by the number and size of blocks within the image.A variable block size has proven advantageous in comparison to a?xed size.As is reported in[10]a coding gain up to3dB can be expected if a variable block segmentation is applied.For the sake of a small segmentation overhead a quadtree partitioning has been chosen which allows to adjust the number and size of image blocks within a wide range.So the?rst step of the encoding process is to determine the number of blocks together with an appropriate block partitioning.If the number of available bits is prescribed, a resulting average number of bits per image block can be calculated.

Secondly the size of the codebook is?xed.According to Fig.6high reconstruction quality requires a large codebook but on the other hand for high compression a smaller one proves optimal.

No difference between the color components has been made for the scaling coef?cients since their quantization turned out to be uncritical as mentioned above.This is not the case for the gray-scale offset.Here the larger portion of available bits is assigned to the luminance or green component.The optimal bit allocation for the gray-scale offset is depicted in Tab.3

overall bits for

RGB space YUV space

gray-scale offset

16R-5/G-6/B-5Y-6/U-5/V-5

15R-5/G-5/B-5Y-6/U-5/V-4

14R-5/G-5/B-4Y-6/U-4/V-4

13R-4/G-5/B-4Y-5/U-4/V-4

12R-4/G-4/B-4Y-5/U-4/V-3

11R-4/G-4/B-3Y-5/U-3/V-3

10R-3/G-4/B-3Y-4/U-3/V-3

Tab. 3.Bit allocation for the gray-scale offset.

1689

Visual Communications and Image Processing,SPIE’94,Chicago

codebook entry type of isometry scaling coef?cient gray-scale offset type of slave transform

master component4-1032-44-6-one slave

component

0,4-100,30,2-40,3-62

compression4x4

blocks compression8x8

blocks

compression

16x16blocks

min number of bits per block1721:190:1361:1

max number of bits per block736:123:184:1

Tab.4.Overall bit allocation for master and slave component.Zero bits for some of the encoding parameters of the slave component indicate that the corresponding parameter of the master component is taken.

Tab.4summarizes the various bit allocation possibilities which assign at least17and at most73bits to one image block consisting of three different image planes.This results in a compression factor depending on the size of the underlying image block rising from6:1for4by4blocks up to361:1for16x16image blocks.For typical natural test images an average compression factor of20:1to60:1can be obtained with reasonable?delity.The signal to noise ratio representing the objective picture quality strongly depends on the type of image.It lies between21–24dB for the test image“baboon”and between 28and36dB for the image“lena”.In contrast to the results published in[16]encoding of the RGB components resulted in a slightly better reconstruction quality compared to the YUV components.An additional improvement may be obtained if the master component is permitted to change from block to block,so that for each block that component is regarded as master component which results in the best reconstruction quality.A comparison with the common JPEG algorithm resulted in advantages for the fractal compression scheme if high compression is desired and in slight advantages for JPEG if very good reconstruction is the issue.

5.REFERENCES

[1]M.F.Barnsley,V.Ervin,D.Hardin,and c79245c68bd63186bcebbc5encaster,“Solution of an inverse problem for fractals and other sets,”in

c79245c68bd63186bcebbc5eA,vol.83,pp.1975–1977,Apr.1986.

[2]M.F.Barnsley and J.H.Elton,“A new class of markov processes for image encoding,”Advances in applied probability,

vol.20,pp.14–22,1988.

[3]M.F.Barnsley,Fractals Everywhere.

London:Academic Press Inc.,1988.

[4] A.E.Jacquin,“A novel fractal based block-coding technique for digital images,”in Proceedings of the IEEE International

Conference on Acoustics Speech and Signal Processing ICASSP’90,vol.4,pp.2225–2228,1990.

[5] A.E.Jacquin,“Fractal image coding based on a theory of iterated contractive image transformations,”in Proceedings

SPIE Visual Communications and Image Processing’90,vol.1360,pp.227–239,1990.

[6] A.E.Jacquin,“Image coding based on a fractal theory of iterated contractive image transformations,”IEEE Transactions

on Image Processing,vol.1,pp.18–30,Jan.1992.

[7] A.E.Jacquin,“Fractal image coding:A review,”Proceedings of the IEEE,vol.81,pp.1451–1465,Oct.1993.

[8]L.Lundheim,Fractal signal modelling for source coding.

PhD thesis,Universitetet I Trondheim Norges Tekniske H?gskole,1992.

[9]J.M.Beaumont,“Advances in block based fractal coding of still pictures,”in Proceedings of the IEE colloquium“The

Application of Fractal Techniques in Image Processing’90”,Dec.1990.

[10] B.H¨u rtgen,F.M¨u ller,and C.Stiller,“Adaptive fractal coding of still pictures,”in Proceedings of the International

Picture Coding Symposium PCS’93,(Lausanne,Switzerland),p.1.8,1993.

1690

Visual Communications and Image Processing,SPIE’94,Chicago

[11] D.M.Monro,“A hybrid fractal transform,”in Proceedings of the IEEE International Conference on Acoustics Speech

and Signal Processing ICASSP’93,vol.5,pp.169–172,1993.

[12]G.E.?ien,L2-optimal attractor image coding with fast decoder convergence.

PhD thesis,Universitetet I Trondheim Norges Tekniske H?gskole,1993.

[13]S.Leps?y,Attractor image compression-Fast algorithms and comparisons to related techniques.

PhD thesis,Universitetet I Trondheim Norges Tekniske H?gskole,1993.

[14]H.Yan and G.Filippoff,“Color image compression based on fractal geometry,”in Proceedings of the2nd Singapore

International Conference on Image Processing’92,pp.3–5,1992.

[15] B.Goel and S.Kwatra,“A data compression algorithm for color images based on run-length coding and fractal geometry,”

in Proceedings of the IEEE International Conference on Acoustics Speech and Signal Processing ICASSP’88,pp.1253–1256,1988.

[16]R.D.Boss and E.W.Jacobs,“Studies of iterated transform image compression and its application to color and DTED,”

Tech.Rep.1468,Naval Ocean Systems Center,San Diego,CA,Dec.1991.

[17] E.Kreyszig,Introductory functional analysis with applications.

Robert E.Krieger Publishing Company,1989.

[18] B.H¨u rtgen and F.M¨u ller,“Modelling of fractal coding schemes,”in Proceedings of the VIIth European Signal Processing

Conference EUSIPCO’94,vol.1,(Edinburgh,Scotland),pp.600–603,1994.

[19] B.H¨u rtgen and S.F.Simon,“On the problem of convergence in fractal coding schemes,”in Proceedings of the IEEE

International Conference on Image Processing ICIP’94,vol.3,(Austin,Texas,USA),pp.103–106,Nov.1994.

1691

本文来源：https://www.bwwdw.com/article/fkne.html