1 Introduction

With the rapid improvement of computer science and network, multimedia becomes an important research area today. Multimedia contains more information than words, but the negativeness of its application is the large size. Nowadays, the increment of multimedia size needs huge space to store and large bandwidth to transfer. So decrease of the multimedia is a highlight in research. Furthermore, decrease of image, which is the basis in this area, also shows its importance.

Today, based on the improvement of multimedia, many classic image encoding methods and international standard of multimedia have been presented. For example, discrete cosine transform (DCT) [24], Huffman code [9], wavelet image coding [25], etc. are all multimedia classic encoding methods. Meanwhile, BIG, JPEG, H.263, MPEG, etc. are all international standards.

But in nature, the geometrical form is usually not regular and smooth. In fact, artificial objects usually have the regular and smooth form, which can be processed by traditional geometry. However, nature objects are usually rough and anomalistic. In this way, since 1980s, a novel subject is created to research in the non-classical geometry. It is called fractal geometry [6, 21].

The basic thinking of fractal is to reach the scale of self-similarity of the whole and the part because most nature objects have the properties of self-similarity, just like in galaxies, lasers and waves [8, 10, 23].

Then, with Banach Fixed Point Theorem as a theoretical support, researchers can use the contractive affine transformation (CAT) into the image encoding study [7, 26]. This is a novel thinking in the image encoding study. It is called fractal image encoding. In this method, it first finds the self-similarity in whole-part of images. Then it stores the quantization parameters of CAT as an encoding file. So the encoding file is much smaller than the original image. In this case, it can reach higher compressing ratio.

In fact, fractal image encoding method has many benefits. One benefit is that this method with same parameters reaches fixed compressing ration for all images with same size. Then, by the proof of existence and uniqueness of the iteration, the final mapping image will always reach the original image with any initial mapping image. In other words, the original image is the ultimate limit of the iteration.

But as the fractal encoding method is a finite distortion method, it loses some points’ value indeed. Then, we believe that the lost values are not same for every image and there are some hidden relations between these values and the images.

So, in this paper, we present the distributions of images with different kinds by used the proposed primary additional errors. First, we exact additional primary errors, which are added to compensate the decoding image. In this case, the fast fractal coding method is proposed. Then, we analyze these errors and find a novel method to classify the images based on the distribution of primary additional errors.

The remainder of the paper is organized as follows. Related works are presented in Section 2. Then, we present the novel fractal encoding method with primary additional errors in Section 3. Furthermore, we study the distribution of images by the primary additional errors in Section 4. Finally, Section 5 summarizes the whole paper.

2 Related works

First, Barnsley and Jacquin used iterated function system (IFS) and Recurrent Iterated Function System (RIFS) in image encoding area [1]. They reached a highest compressing ratio more than 10000:1 for some special images. Then, Jacquin developed a software system of self-adaptive fractal encoding method [11]. The generation of the system is soon studied and improved by many researchers. At the same time, Monro and Dudbridge also found the fractal block in images and presented their fractal encoding method [22]. Furthermore, Bedford et al. presented a fractal encoding method in monochrome images, and Kim and Park presented theirs in still image by fractal approximation [2, 13]. Kim et al. focused on the mapping and non-contractive interframe mapping in the video, and presented a fractal encoding method in video sequence [12]. Chang and Kuo designed a domain pool and presented an iteration-free fractal image encoding method based on the pool [5].

Since 2000s, based on the rapid increments of multimedia, especially the images, fractal image encoding also progressed quickly. The mainly study domains are two, which are (i) increase the encoding rate and (ii) decrease the encoding time. There are many methods are presented based on many thinking. Li et al. present a fractal encoding method by used fuzzy image metric [15]. Lai et al. presented a fast fractal image encoding method by used kick-out and zero contrast conditions [14]. Belloulata encoded subbands by used non-iterative block clustering [3]. Wang et al. found a modified gray level transform and fitting plane and presented a no-search fractal image encoding method [28, 29]. He also used wavelet transform into fractal encoding method [30, 32]. Lu et al. used fitting plane into Huber fractal encoding method [20]. Bhayani and Thanushkodi found some properties of medical image and used fractal encoding method into medical image compression [4]. Our team also reached some results in this area. We researched fractal properties in k-M set and use it into facial capture [16, 18].

As the fractal encoding method lost some points’ value indeed, the lost values must have some hidden relations with the original images. So if we can reach the relation, we can classify or separate the images by used the relation. In this way, this paper encoded some images to find the distribution of these images.

3 Fractal encoding method by used primary additional errors

First, we present the steps of a fractal image encoding method in Fig. 1.

Fig. 1
figure 1

Process of fractal image encoding method

Full size image

Then, we propose the improved fractal image encoding and decoding method in Alg. 1a and Alg. 1b, In which I means original image, n means the size of I is n × n, c means the size of sub-image is c × c in encoding set (c|n), d = n/c, f means the size of sub-image is f × f in affine set (f < c), F means the encoding file.

      Algorithm 1a. Fractal Encoding Method with Primary Additional Error

Input. I(n × n); c; f.

Output. F.

   Step 1.

To find a partition Ir of I (r = 1, 2, …, d 2 ), which means that ∀ i, j|i ≠ j → Ii ∩ Ij = ∅ and U1 ≤ i ≤ d Ii = I is a tautology. Meanwhile, in this partition, ∀ i, j| scale of Ii = scale of Ij = cc is a tautology.

   Step 2.

To divide I to part-repeatable Dk. The size of all Dk is f.

   Step 3.

   For every Ir do

To find the best affine transformation of Ir in Dk, and store it as a vector in the affine transformation table.

Step 4.

To extract primary additional errors and store them in the matrix of primary additional errors (PAE). Then, output the fusion of both affine transforming table and PAE as encoding file F.

Alg. 1a finished

In following, decoding method is presented in Alg.1b, in which s means the scaling of luminance, o means offset of luminance, (x, y) mean the starting position of affine transformation, direction means the eight types of equilong transformations, T means the iterating time, D means the decoding images. Others are same to Alg. 1a.

      Algorithm 1b. Fractal Decoding Method with Primary Additional Error

   Input. F.

   Output. D.

   Step 1.

   To extract PAE and affine transforming table from F.

   Step 2.

   While the affine transforming table is not finished.

   To extract a vector from affine transforming table, which in a best affine transformation of Ir in Dk. To locate the position by used (x, y). To iterate a blank sub-image with size f×f by used corresponding s and o. Then, to process equilong transformation by used direction.

   Step 3.

   To collage all rectangular areas to an image D’. Then, let Ri = corresponding part of D’, iterating step 1–3 until iterating time = T.

   Step 4.

   To output D’ as D.

   Alg. 1b finished.

Here, we present six figures with same size 256 × 256 in Fig. 2 as the original images in our experiment, where Fig. 2a is classic “Lena”, Fig. 2b is classic “bird”, Fig. 2c is classic “baboon”, Fig. 2d is classic “Barbara”, Fig. 2e is classic “fractal”, Fig. 2f is classic “fruit”.

Fig. 2
figure 2

Original images

Full size image

Then, we use Alg. 1a to encode these original figures and Alg. 1b to decode these encoding files to decoding images. The decoding results are presented in Fig. 3, where the left sub-figure in every row is decoding image with one iterating time, the middle is decoding image with three iterating times, and the right is decoding image with five iterating times.

Fig. 3
figure 3figure 3

Decoding images of Fig. 2 with 1 (left), 3 (middle) and 5 (right) iterating times

Full size image

Figure 4 presents the encoding files of these original images, in which the symbols are corresponding to Fig. 2. In Fig. 4, we find the encoding files are divided into two parts. The left part in every sub-figures of Fig. 4 is the encoding s, o and start position of iteration. The right part is the encoding PAE, directions and position of PAE.

Fig. 4
figure 4

Encoding files of the original images

Full size image

Since we have extracted the PAE, we believe the quality of the decoding image is high enough. In fact, the PSNRs are computed to measure the quality of the decoding image from Eq. 1 and presented in Table 1 [27]. So we find the effectiveness of our method.

Table 1 Experimental results of fractal encoding method
Full size table
$$ \mathrm{PSNR}=10\cdot \log {}_{10}\frac{{\mathrm{n}}^2\cdot {255}^2}{{\displaystyle {\sum}_{\mathrm{i}=1}^{{\mathrm{n}}^2}}{\left({\mathrm{I}}_{\mathrm{i}}-{\mathrm{D}}_{\mathrm{i}}\right)}^2} $$
(1)

4 Distribution of the primary additional error

Since the fractal image encoding is a finite distortion encoding method, there are error values in many image points. The errors between D and I appear because Eq. 3 is applied to instead of Eq. 2 in real application, in which B means the grey level, E means the identity matrix, || || means the vector norm (usually 2-norm in fractal encoding), Ri means an affine sub- image, Dj means a pattern sub-image, mi means serial number of the best Dj, si means scaling of Ri, oi means offset of Ri in an affine mapping.

$$ \frac{1}{{\mathrm{B}}^2}\underset{\mathrm{j}}{ \min}\left\{\underset{\mathrm{s},\mathrm{o}\in \mathrm{R},\ \left|\mathrm{s}\right|<1}{ \min }{\left\Vert {\mathrm{R}}_{\mathrm{i}} - \left(\ \mathrm{s}\cdotp {\mathrm{D}}_{\mathrm{j}} + \mathrm{o}\cdotp \mathrm{E}\right)\right\Vert}^2\right\} $$
(2)
$$ \underset{\mathrm{j}}{ \min}\left\{ \min {}_{\mathrm{s},\mathrm{o}\in \mathrm{R}}\left\Vert {\mathrm{R}}_{\mathrm{i}} - \left(\mathrm{s}\kern0.24em \cdotp \kern0.24em {\mathrm{D}}_{\mathrm{j}} + \mathrm{o}\kern0.24em \cdotp \kern0.24em 1\right)\ \right\Vert\ \right\} = \min {}_{\mathrm{s},\mathrm{o}\in \mathrm{R}}\left\Vert {\mathrm{R}}_{\mathrm{i}} - \left(\ {\mathrm{s}}_{\mathrm{i}} \cdot p \kern0.24em {\mathrm{D}}_{{\mathrm{m}}_{\mathrm{i}}} + {\mathrm{o}}_{\mathrm{i}} \cdot p \kern0.24em \mathrm{E}\right)\ \right\Vert $$
(3)

These errors bring negativeness of visual effect in the decoding image. But we believe that not all of these errors bring the same scale of negativeness. In other words, there are several errors bring the mainly negativeness. So we extract PAE to find the properties of these errors.

In this way, we can extract additional error Δn×n from Eq. 4, in which the symbols are same to Eqs. 2 and 3 where Rj * denotes the decoding sub-images from Dj.

$$ {\varDelta}_{\mathrm{n}\times \mathrm{n}}={\mathrm{I}}_{\mathrm{n}\times \mathrm{n}}-{\cup}_{1\le \mathrm{j}\le \mathrm{d}}{\mathrm{R}}_{\mathrm{j}}^{\ast } $$
(4)

For all of the six original images, all Δs are computed and presented in Fig. 5 where c = 8, f = 4 (we also know n = 256 from Fig. 2). The symbols of sub-figures are corresponding to Fig. 2. In Fig. 5, we know that the value zero in Δ of these images is usually not so much in general. But many values are small (no more than 50). So, in order to ensure the quality of visual effect for all images, we are more interesting in those points with high error values in Δ.

Fig. 5
figure 5

Additional error values of the six original images

Full size image

It is admittedly that blocking effect is an important element in visual effect for all images. So, those error values Δp and Δq of points p and q have to be stored when there is a common edge e of two image block Dp and Dq, Δp∈Dp, Δq∈Dq, and Δp, Δq∈neighborhood of e. In this case, we have an evaluation standard to extract the valuable errors from Δ by the rule of Property 1 and present in Eq. 5 where uk = 1 + (1-kln2)/e denotes the penalty weight of chromatic aberration between the error point and each other points within distance k where uk is smaller when k is larger, (i, j) denotes the position of every error point, (i’, j’)∈Dp when (i, j)∈Dq and (i’, j’)∈Dq when (i, j)∈Dp denotes that |i − i′| = t1 and |j − j ′ | = t2 where t1 + t2 = k and t1, t2 N. So Eq. 4 is the formation of PAE.

Property 1

The weights wp and wq of two random error points p and q conform to the following rule.

  1. 1)

    wp > wq if Δp > Δq with other elements equally.

  2. 2)

    wp ≥ wq if p is nearer to e than q with other elements equally.

  3. 3)

    wp > wq if p has larger chromatic aberration around than q with other elements equally.

$$ {\mathrm{w}}_{\mathrm{i},\mathrm{j}}={\varDelta}_{\mathrm{i},\mathrm{j}}+{\displaystyle {\sum}_{k=1}^m{\mathrm{u}}_{\mathrm{k}}\cdot \frac{1}{\mathrm{k}-1}}{\displaystyle {\displaystyle {\sum}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i},\mathrm{j}}-{\mathrm{w}}_{\mathrm{i}\prime, \mathrm{j}\prime}\right|\right)}} $$
(5)

Theorem 1

Eq. 5 conform to properties 1)-3) of Property 1.

Proof.

Assuming the two points p(i, j) and q(i*, j*), we have the following proof.

  1. 1)

    Case when Δp > Δq with other elements equally.

    We have wp-wq = Δp-Δq > 0 because wp-Δp = wq-Δq (other elements equally). Case 1) is proved.

  2. 2)

    Case when p is nearer to e than q with other elements equally.

    It is equivalent to that point p has at least one pixel nearer than point q and q is at least one pixel away from e. So, there is no point (i*’, j*’) makes k = 1 around the point q. In this case, we have following Eq. 6 because Δp = Δq.

    $$ {\mathrm{w}}_{\mathrm{p}}-{\mathrm{w}}_{\mathrm{q}}={\displaystyle {\sum}_{\mathrm{k}=1}^{\mathrm{m}}{\mathrm{u}}_{\mathrm{k}}\cdot \frac{1}{\mathrm{k}-1}}{\displaystyle {\sum}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i},\mathrm{j}}-{\mathrm{w}}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\right|\right)}-{\displaystyle {\sum}_{\mathrm{k}=2}^{\mathrm{m}}{\mathrm{u}}_{\mathrm{k}}\cdot \frac{1}{\mathrm{k}-1}}{\displaystyle {\sum}_{{\mathrm{i}}^{*\prime },{\mathrm{j}}^{*\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i}*,\mathrm{j}*}-{\mathrm{w}}_{{\mathrm{i}}^{*\prime },\mathrm{j}{*}^{\prime }}\right|\right)} $$
    (6)

    Because of the other equal element of points p and q, we have following Eq. 7.

    $$ {\displaystyle {\sum}_{\mathrm{k}=1}^{\mathrm{m}\hbox{-} 1}{\mathrm{u}}_{\mathrm{k}}\cdot \frac{1}{\mathrm{k}-1}}{\displaystyle {\sum}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i},\mathrm{j}}-{\mathrm{w}}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\right|\right)}={\displaystyle {\sum}_{\mathrm{k}=2}^{\mathrm{m}}{\mathrm{u}}_{\mathrm{k}\hbox{-} 1}\cdot \frac{1}{\mathrm{k}-1}}{\displaystyle {\sum}_{{\mathrm{i}}^{*\prime },{\mathrm{j}}^{*\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i}*,\mathrm{j}*}-{\mathrm{w}}_{{\mathrm{i}}^{*\prime },\mathrm{j}{*}^{\prime }}\right|\right)} $$
    (7)

    So we have Eq. 8 to prove case 2) because uk-1 > uk and um > 0. Case 2) is proved.

    $$ {\mathrm{w}}_{\mathrm{p}}-{\mathrm{w}}_{\mathrm{q}}={\displaystyle {\sum}_{\mathrm{k}=2}^{\mathrm{m}}\left({\mathrm{u}}_{\mathrm{k}\hbox{-} 1}-{\mathrm{u}}_{\mathrm{k}}\right)\cdot \frac{1}{\mathrm{k}-1}}{\displaystyle {\sum}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i},\mathrm{j}}-{\mathrm{w}}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\right|\right)+{\mathrm{u}}_{\mathrm{m}}\cdot \frac{1}{\mathrm{m}\;\hbox{-}\;1}}{\displaystyle {\sum}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i},\mathrm{j}}-{\mathrm{w}}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\right|\right)}\kern0.49em > 0 $$
    (8)
  3. 3)

    Case when p has larger chromatic aberration around than q with other elements equally.

    It means that \( {\displaystyle {\sum}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i},\mathrm{j}}-{\mathrm{w}}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\right|\right)}>{\displaystyle {\sum}_{{\mathrm{i}}^{*\prime },{\mathrm{j}}^{*\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i}*,\mathrm{j}*}-{\mathrm{w}}_{{\mathrm{i}}^{*\prime },\mathrm{j}{*}^{\prime }}\right|\right)} \). So we have Eq. 9 to prove case 3). Case 3) is proved.

    $$ {\mathrm{w}}_{\mathrm{p}}-{\mathrm{w}}_{\mathrm{q}}={\displaystyle {\sum}_{\mathrm{k}=1}^{\mathrm{m}}{\mathrm{u}}_{\mathrm{k}}\cdot \frac{1}{\mathrm{k}-1}}\;\left({\displaystyle {\sum}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i},\mathrm{j}}-{\mathrm{w}}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\right|\right)}-{\displaystyle {\sum}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\left(\left|{\mathrm{w}}_{\mathrm{i},\mathrm{j}}-{\mathrm{w}}_{{\mathrm{i}}^{\prime },{\mathrm{j}}^{\prime }}\right|\right)}\ \right) > 0 $$
    (9)

    Then, theorem 1 is proved when cases 1)-3) are summarized.

In our experiment, we let m = 5 because the blocking effect is small enough when m > 5, and uk = 1 + (1 − kln 2) /e because the blocking effect corresponds to the distance of the points (blocking effect is larger when the distance is smaller). Then, PAE are extracted by sequenced all wij. We extract PAE with d/2 points because they can be stored in the encoding file that they do not bring additional space cost. Furthermore, after we extract the PAE of these images, we can analyze their distributions.

With original images, we have both the additional error values and PAE of our method. They are presented in Fig. 6, where the sub-figures a1-e1 are additional errors of original images with the corresponding symbols and the sub-figures a2-f2 are additional errors without PAE of the corresponding original images.

Fig. 6
figure 6

Comparisons between total additional errors and PAE

Full size image

First, we find some of the numerical characteristics in the additional errors. For example, the mean of value is 60 ~ 80 and maximum value is 150 ~ 200 in sub-figures a1-f1 of Fig. 6. Then, in sub-figures a2-f2, we find the additional errors change to 80 ~ 100 per point in PAE. It means that the formation we created to extract the PAE is effective. In other words, the PAE increase the encoding effect.

Then, in Fig. 6, the size of the matrix of addtional errors and PAE in sub-figures are same because the number of points is 256 × 256 = 65536. We present it in Fig. 6 by row major order. So in Fig. 6, we find that part of the PAE are around the edge of natural and artificial objects. The other part of PAE are around the inharmonious background. In other words, points of nature objects in the image mainly have small additional errors (see the small values in Figs. 6a1-6f1, they are all windows, hat, building, windwill, face, and other nature or harmonious objects et al.), and the points of inharmonious always have large additional errors (see the difference between Figs. 6a1-6f1 to Figs. 6a2-6f2, they are all factitious and inharmonious objects, the edge of person and window, tree and building, moving objects and background, et al.). So we know that we can divide the images to two parts, which are the natural (harmonious) background and inharmonious (artificial addition objects). Finally, the visual images of the PAE of all six images are shown in Fig. 7. We can find that the PAE are mostly distributed at edges of each images.

Fig. 7
figure 7

Comparisons between visual PAE and extracted edges

Full size image

In Figs. a1-f1, we have the visual PAE and in Figs. a2-f2, we have the extracted edges. In this way, we find the most PAE come from the edges of each images.

5 Conclusion

In this paper, we present a distribution of primary additional errors. Experimental results shows that the primary additional errors distribute over the different objects in image and mostly around the across edge.

In this way, we know that the distribution of primary additional errors can be an effective classification of natural and artificial images. So in future, our work will pay attention to microcosmic encoding rule. We project to construct a rule of indemnity by used fuzzy set because of the classification of primary additional errors. Another area we want to study is to use parallel environment to increase coding time [17, 19, 31].