Review Paper on kick-out conditions in Domain Images

Review Paper on kick-out conditions in Domain Images

Review Paper on kick-out conditions in Domain Images

Shilpi Sharma, Vijayshri Chaurasia, Member, IEEE and M.K Gupta, Member, IEEE

Abstract Fractal Image Compression is a lossy technique which is based on Fractals. This method takes into account self- symmetry in the image. Fractal algorithms convert self symmetrical parts into mathematical data called fractal codes which can recreate the encoded image. Fractal Image Compression consumes lot of time in its encoding phase. A large variety of techniques to improve its time performance have already been proposed. This paper gives an a survey of kick-out based speed up techniques in which impossible or negligibly used domain blocks are removed from the domain pool prior to suitable domain search. This reduction into the domain pool size results a faster encoding process.

Index Terms Fractal Image Coding, Full search, Kick-out rule.

M.

M.

1. INTRODUCTION

   BARNSLEY gave the concept of Fractal Image Compression in 1988[2,30] and after that it has became an important content for research. Fractal

   method some redundant domains are rejected reducing the number of domains-range comparison improving computation time. Various Kick-out conditions have been proposed. In this paper most significant kick out conditions have been reviewed. In Section II Full Search method has been discussed. In section III significant kick out schemes have been studied and finally in section IV conclusion is made.

2. FULL SEARCH METHOD

   In the encoding phase of fractal image compression, the scheme [5,10] is as follows, The original image is divided into Range blocks and Domain blocks. Range blocks are non- overlapped and the collage of them could cover the whole image. Domain blocks can be overlapped. An initial domain Size is double of the range size. Then, the best matched domain block will be found out in codebook () on the basis of the following equation for the given range block:

   , = min min . + . (1)

   Image coding is based on the concepts and mathematical

   ()

   ,, <1

   results of Iterated Function Systems (IFS). Real-world images are usually not self-similar and it is impossible to find an operator that maps a whole image onto another image. However, real-world images present piecewise self-similarity [4-6] i.e instead of whole image some parts of the image resemble other parts. Starting from this observation, one can define an operator as the sum of piecewise mappings on image.

   In 1989 Jacquin[4] proposed the first fully automated algorithm for Fractal Image Compression which was based on affine transforms and partitioned iterated function system (PIFS) [3]. He decomposed the image into non-overlapping blocks called as range blocks and partitioned iterated functions are applied on these range blocks rather than the entire image.

   For searching self-symmetry in to the images the image to be encoded is also partitioned into overlapping manner resulting domain images. Fractal Image compression suffers from long encoding time since the suitable domain search phase includes a large number of range domain comparisons [1]. The number of possible range and domains are very large which takes long encoding time. In kick-out condition based

   Shilpi Sharma is a research scholar of AISECT University, Bhopal, Madhya Pradesh, India (phone: +9198935-08835; e-mail: shilpi2000sharma@gmail.com).

   Vijayshri Chaurasia, is with the Department of Electronics and Communication Engineering, MANIT, Bhopal, India (e-mail: vchaurasia@manit.ac.in).

   M. K. Gupta is with the Electronics and Communication Engineering Department, of MANIT, Bhopal, India (e-mail: gupta4@yahoo.com).

   is the best matched domain block. is a literal block whose brightness mean is 1, is the set of real numbers, . is the vector norm. The range index can be predicted from the decoder if the range blocks are coded sequentially. The parameter should be such that the inequality < 1 in order to theoretically guarantee decoding iteration sequence is convergence. is the best matched block serial number. , represent contrast and brightness adjustments separately. Then, the sample block is transformed into eight transformations in the Dihedral group on the pixel positions.

   Assuming the origin of the image block is located in the center, the eight affine transformations were noted for tk=(0,1,…,7) ,which were rearranged for pixels and improved the matched quality. So the fractal coding of is the quadruples {tk ,mk ,si , oi } and last, the necessary parameters are stored in order to decode. As follows:

   0 lim 0 = (2)

   is a Iterated Compression Transform. 0 is the initial image, is a fixed point of , is the default times of iterations.

3. KICK OUT METHODS

   • Kick- out and zero contrast condition

     Cheung-ming lai, Kin-man lam and Wan-chi siu proposed a algorithm based on kick-out and zero contrast condition in

     2003[7]. It avoids the large number of range – domain comparisons while finding the most suitable match. This algorithm can achieve the same reconstructed image quality as the full search method and it reduces the required computation time. It does not need any pre-processing step or additional memory for its implementation and can be combined with DCT inner product to reduce the computation time further. In this method first search is done using only contrast. The error function (, ) can be written as follows:

     , = 2 (3)

     where

     = 2 1 , 2 (4)

     calculations and removes the mismatched domain blocks at earlier stage in the process of finding the best matched domain block. In this method reconstructed image quality is equivalent as the full search method. Initially, normalized one-norm of each domain block is calculated and arranged in an increasing order. For normalized one-norm of range block binary search tree is used to find the domain block such that difference between one-norm of the normalized range block and one norm of normalized domain block is minimal. For 1 8, the eight errors for the eight isometry transformations are computed. The current minimum error is set and the domain is set to the current best matched domain block of .

     and

     = 2 1 , 2 (5)

   • Kick- out condition based on relative error

     In 2012 Aihua Zhang and Pei Yang proposed an Improved Algorithm based on Relative Error [9]. The proposed

     The coefficient is limited to the range (1, 1) to ensure convergence in the decoding. If > then the maximum error occurs when = 0 and minimum error occurs when

     = 1.To find the best matched domain block the search is performed only if the minimum error for the domain block under consideration is less than the current minimum error. Thus, the kick-out condition is as follows:

     algorithm uses an inequality linking the root-mean-square (RMS) and the relative error to set up a kick-out condition. It is based on the relative error to avoid the extreme searching, and discarding the remaining domain blocks, reducing its runtime significantly. In this method lemma is used to describe the relationship between the RMS and relative error to avoid the full searching. For a fixed intensity (s), when the relative error of R and D approaches.

     =

     (6)

     , =

     (7)

     The matching errors of the first omain block with each of the eight isometric operations are calculated. Out of these the one with the minimum error is considered to be the initial best

     ,

     (8)

     matched domain block. The current minimum distance is then set to this minimum distortion. To determine whether the next candidate domain block is closer to than the current best match its minimum distance is also computed and compared. If it is larger than or equal to minimum distortion then the domain block is rejected. Otherwise, it is replaced by the current best matched domain block. This process is repeated for all the domain blocks in the domain pool to find the best matched one for an input range block. Due to this kick-out condition, the required computation for searching the best matched domain block will be greatly reduced. After this zero contrast prediction is used to determine whether the contrast factor is zero or not, and the corresponding error function is computed without performing the range-domain block matching. So the required runtime can be further reduced.

   • Normalized one-norm & kick-out condition based method

   Hsiu et als [8] proposed another kick-out condition based fractal image encoding method using normalized one- norm in

   In the coding process, firstly, according to the standard deviation of the block threshold parameters is selected. Secondly, if the standard deviation of the R block is too small, then its fractal codes are given directly, avoiding large amount of computation in range-domain comparison. If the standard deviation is higher than the threshold then relative error of range block is computed. Nearest value of this range relative error is searched from code-book of domain relative errors. Then the domain block corresponding to nearest relative error is the best matched domain for the particular range block. For a fixed , is selected in the codebook whose relative error is close to as an initial matched block. We set a minimum distortion measure:

   = , (9)

   For any domain block in codebook, if

   , = (10)

   2009. This method is 22% faster than full search method. In

   , ,

   (11)

   this method a special measure called the one-norm of

   normalized block, present a novel inequality which can

   discard redundant computations involved in the error-term calculation which is one of the most important part in the encoding process. That is, for each range block, this kick out condition can discard impossible domain blocks as early as possible in the process for locating the best matched domain block. So the inequality derived discards redundant

   From the above equation is not the best matched block of

   , so it is kicked out in the global searching. The best matched block of will only be found out in the codebook where < . This method results an insignificant degradation in the subjective quality of the decoded image but the speed of encoding improves by more than 32 times of the

   full search method. The peak signal- noise-ratio (PSNR) of the proposed algorithm is smaller than the baseline fractal algorithm, but the image quality has not decreased significantly in the subjective conditions.

4. COMPARISON

   An eight bpp 512 × 512 Lenna image is used to compare the performance of kick-out based methods as compared to full search method in terms of execution time and decoded image quality. The decoded image quality is measured by PSNR (peak signal-to-noise ratio). In table I, percentage Time Reduction column shows improvement ratio with respect to full search method.

   1. A.E. Jacquin, Image coding based on a fractal theory of iterated contractive image transformations, IEEE Trans. Image Process. 1 (1992) 1830.

   2. A. E. Jacquin, Fractal image coding: A review, Proc. IEEE, vol. 81, pp. 14511465, Oct,1993.

   3. C.M. Lai, K.M. Lam, W.C. Siu, A fast fractal image coding based on kick-out and zero contrast conditions, IEEE Trans. Image Process. 11 (2003) 13981403.

   4. Hsiu-Niang Chen, Kuo-Liang Chung, Jian-Er Hung, Novel fractal image encoding algorithm using normalized one-norm and kick-out condition,Image and vision computing,2009.

   5. Aihua Zhang, Pei Yang, An Improved Algorithm for Fractal Image Encoding Based on Relative Error, 5th International Congress on Image and Signal Processing (CISP 2012), 2012.

   6. Li Gao ping,Fractal Image Compression method, Springer, South- west,Jiaotong University,2010.

   TABLE I

   Method	Performance
   	Time (sec)	PSNR (dB)	Time Reduction (%)
   Full Search	259.8	37.56	0 %
   Single kick-out condition & zero contrast prediction	194.6	37.56	25 %
   Normalized one norm & kick- out condition	189.2	37.56	27 %
   Improved method based on relative error	8.12	32.92	96.9%

   Method	Performance
   	Time (sec)	PSNR (dB)	Time Reduction (%)
   Full Search	259.8	37.56	0 %
   Single kick-out condition & zero contrast prediction	194.6	37.56	25 %
   Normalized one norm & kick- out condition	189.2	37.56	27 %
   Improved method based on relative error	8.12	32.92	96.9%

   EXECUTION TIME PERFORMANCE COMPARISON FOR 4 × 4 RANGE BLOCKS

5. CONCLUSION

Speed up techniques in which kick-out condition in domain images is used reduces the computation time remarkably. Single kick-out condition &zero contrast prediction based method and Normalized one norm & kick-out condition based method reduces the time requirement by 25% and 27% respectively. Both of these methods provide retrieved image quality comparable to conventional method. Relative error based method massively reduces the encoding time by 96.9%. This improvement in time performance is achieved on the cost of 12.35% degradation in decoded image quality.

The combination of other fast fractal methods along with kick- out conditions can decrease the computation time. In future we can apply kick-out condition on range images along with domain images so that encoding time reduces further and fractal image compression scheme can be useful for more applications.

REFERENCES

1. Fisher, Y, Fractal, Image Compression: Theory and Application, Springer Verlag, N.Y.,1995.

2. Barnsley M, Sloan A. A better way to compress images, BYTE, 1988, 1:215- 223.

3. Barnsley. M., Fractals Everywhere, Academic press. San Diego, 1989.

4. A. E. Jacquin, A fractal theory of iterated Markov operators with applications to digital image coding, Ph.D. dissertation, Georgia Institute of Technology, Atlanta, GA, Aug. 1989.