2012 International Workshop on Nonlinear Circuits,Communications and Signal Processing
NCSP'12, Honolulu, Hawaii, USA. March 4-6, 2012

On Investigation of the Intensity Scaling Factor in Fractal Image Coding
Yoshinori Kitano1 , Tetsushi Ueta1 , Yoshifumi Nishio1 , Guoan Yang2 , and Yang Yang2
1Tokushima University
Email: kitano-yoshinori@is.tokushima-u.ac.jp

Abstract
Fractal image coding uses geometrical self-similarity properties in the given image and it shows a high compression ratio.
There are many research results on gray-scale or color natural images with this coding system, in this paper we specify
that there is a trouble with black/white images because of thescaling factor value of the affine mapping for pixel values. Toovercome this problem, we examine the scaling factors versus
S/N ratio for various black and white images, and investigate
the scaling factor values distribution resulting the maximum
S/N ratio. With these values, the decoded image looks very
natural.
1. Introduction

2

Xi’an Jiaotong University

ing has been studied using geometric information of the compressed data.
Pen drawings, cartoons, sketches are often composed by aset of sharp black lines, dots, screen tones. When the original fractal coding scheme is applied to a binary valued image (only black and white pixels are stored), we noticed thedecompressed (decoded) images tend to be remarkably degraded since the scaling parameter of the intensity directionin the affine mapping is fixed. In fact, this parameter wasappeared in the Barnsley’s original algorithm[1], and it has
been fixed for a long time. In this paper, we explain this phenomenon, and propose its work around.

2. Fractal CodingAccording to diffusion of Internet and multimedia, imagecompressing techniques become very important for improve
speed and saving storage media. Today, some techniques ofimage compression such as JPEG, GIF and PNG method thatare using techniques such as statistical redundancy of the image frequency are researched and they are the mainstreamof image compression method. In contrast, there is a fractal
compression that has a compression technique using geometric redundancy in the image. It has features such as high compression and high-speed decoding of compressed pixel datafrom the current mainstream method. Therefore, this one has
an attracted attention as a next generation image compression
method.
Fractal coding that using fractal compression has been proposed by Barnsley et in 1988[2]. This coding is using theregion self similarity that the global structure used the similarity in local structure. Then, Jacquin et proposed partial selfsimilarity of fractal coding that search in blocks[2] and thelatter approach has become mainstream now. This approachis divided into blocks without overlapping images and is thatencoding using similarity blocks of different sizes. When we
decode the image, decoded image is generated by repeating
any blocks for affine mapping between the blocks stored incompressed data. while fractal coding takes much time forcoding computations, there are features of fractal coding thatis better than compression ratio of the other methods and allows fast decoding. Today, research of the image process-A practical scheme of the image compression is described
below. At first, we divide an original image into some small
blocks not to be overlapped one another. Here we call themdomain blocks. Next, we make a 2N × 2N size of domain
block from the original image. Here we call this a range
block. When we fix a domain block, a fractal code is a setof parameters for affine transformation with the best match
range block in the image:


x
ai
 y  7→  ci
z0bi
di0

 
0x
si0   y  +  ti pizqi

(1)

where, x, y are the positions of the domain block. z is thepixel value of (x, y). ai , bi , ci , di , pi , qi , si , ti are parameters. Fractal image codes are these sets of position and parameters. Note that these codes are usually encoded again byan entropy encoding algorithm to remove the redundancy ofthe parameters.
The decompressing scheme is described as follows. At
first, we create an image of the same size as the original image
and divide it by the domain block. we obtain the original image by replacing all domain blocks with corresponding range
blocks with iterating the affine mapping, see Fig.1. Parameters of the affine mapping are restored from the compresseddata.

- 273 -

well since distribution of pixel values are not appropriately
spread. This means that the decoding error does not specifically change impression of the whole image. However, forbinary valued images, drastic degrading results are obtained.
In Fig. 2(b), a white background is filled by a gray pixel. In
Fig 2(d), it seems to be a completely false image. The reasonof these defeats is the fixed value of pi in Eq. (1). Historically,
0.9 is chosen as pi , because the first version of Barnsley’s algorithm, this value is specified without any explanation. For
gray scaled images, a certain range of pi , say, 0.5 < pi < 0.9
is allowed to retain enough quality of the target image. For
the binary valued images, however, this 0.9 is not a suitable
number for coding. In the pixel value direction, a contract
mapping pi z + qi (gray scale reduction) does not prevent undesirable mixture of gray pixels enough.
Figure 1: Definition of the domain block and the range block. 4. Proposed Method
If we take the other value for pi , what is happened ? Figure?? shows decompressed images for Fig. 2. For Charley
3. Conventional Method
Brown, pi = 0.9 leaves the best quality. Now we propose a
When one tries the fractal coding for a binary valued im- modified fractal compression for binary valued images, i. e.,age with the original Barnsley’s code, an undesired results are we adaptively choose pi for the given image.
To evaluate the quality of decompressed image, we define
happened, see Fig. 2.
the peak signal-to-noise ratio P SN R as follows:{}
255 × 255
PSNR = 10 log(2)MSEm ∑n∑MSE =(a) Sample 1 original(b) Sample 1 decompressed(a) Sample 2 original(b) Sample 2 decompressedf (i, j) − f 0 (i, j)

i=0 j=0(3)
m×n
where, we assume the image is m × n size. f and f 0 are
the original and the decompressed image pixel value, respectively and they range 0 to 255. If the decompressed image is loss-less, the PSNR becomes infinity. Generally, ifPSNR is around 40 dB, people could not recognize the difference between original and decompressed image. We use
m = n = 256, and 4 for the domain block.
The strategy to obtain pi generating the best quality decoded image, we simply check brute-force computation, i.e.,
simply scan all values of pi < 1. A pi marking the largest
value of PSNR in this scan is the best value.
5. Experimental Result

We use Apple Mac Mini, 2.4 GHz Intel Core 2 Duo, 2MB
memory for computer simulations. The average coding time
Figure 2: Examples: undesired degraded decoding. (a) and for all figures is 200 seconds. Tables ??–?? show compu(c): the original images. (b) and (d): decoded images with tation comparison with the conventional method (Barnsley’sBarnsley’s original algorithm.
fixed parameter) and our best quality pi . We do not change
any algorithm, the computation time and compression ratio
For natural gray-scale images, the fractal coding works are not changed.

- 274 -

We summarize the features of these results below:

2220• It seems that there is an extreme value for Sample 1 and4. Beyond the extreme value, the PSNR suddenly declines like a threshold effect. Anyway in these samples,
Barnsley’s pi can only leave poor decoded images. We
should choose smaller value for pi , e.g., 0.65 < pi <0.7.

1816141210860.4• The fixed value of pi used in Barnsley’s algorithm does
not gain the best PSNR for any binary valued images.

• Oscillatory PSNRs are found in Sample 2 and 3. Theseimages contain thin and complex structures inside. Probably in the domain and range block matching stage, thesize of the domain block affects PSNR too much sincea slight difference of shapes between domain and range
block makes completely different referenced locations.

0.50.6

0.7

0.8

0.9

1

Figure 4: pi -PSNR graph for Sample 2.

25

20

15105

• It is difficult to find out generic tendency of these examples. Some normalized images (e.g., parameterizedcircles, squares, rectangles and other objects) should be
examined.

00.4

0.5

0.6

0.7

0.8

0.9

1Figure 5: pi -PSNR graph for Sample 3.

2330

22
25

21
20

20

1915

18
1710165

15
14
0.4

0.5

0.6

0.7

0.8

0.9

010.4

Figure 3: pi -PSNR graph for Sample 1.

0.5

0.6

0.70.80.9

Figure 6: pi -PSNR graph for Sample 4.

- 275 -1

tional costs and time to obtain the best value of pi , we would
like to derive an adaptive design method, i.e., an evaluation
function and its optimizing method should be developed.
References[1] M. Barnsley and L. Hurd, Fractal Image Compression,
AK Peters Ltd., 1993.

(a)[2] A. Jacquin, “A Novel Fractal Block-Coding Technique
For Digital Images,” IEEE ICASSP, pp.22–25, 1990.

(b)

Figure 7: The best images for Sample 1 and 2 with modified
value of pi . (a): pi = 0.82, (b): pi = 0.49.

[3] A. Takeuchi, T. Ueta, and K. Terada, “Improvements of Image Segmentation by using Fractal Coding,”
NOLTA’99, pp.347–350, Hawaii, 1999.
[4] T. Masaki, T. Ueta, and K. Terada, “Fingerprint Identification using Fractal Coding,” Proc. NOLTA’99, Vol. 1,
pp. 143–146, Hawaii, Dec. 1999.
[5] T. Nakanishi, T. Ueta, “Loss-less Fractal Compression Method for Line Drawings and Illustrations,” Proc.
NCSP’10, pp. 309–312, Hawaii, Mar. 2010.

(a) Barnsley’s(b) pi = 0.69.

Figure 8: Sample 3(a) Barnsley’s(b) pi = 0.71.

Figure 9: Sample 4
6. Conclusion
We investigated the role of pi used in the fractal coding.
We clarified that the fixed value of pi introduced in Barnsley’s
first issue do not have a reasonable evidence for its determination. Since the brute force method consume much computa-- 276 -