9.3 Encoding and decoding algorithms for fractal image compression

Fractal image compression uses self-similarity within images to achieve high compression ratios. The encoding process partitions the image into range and domain blocks, searching for transformations that closely approximate each range block with a domain block.

Decoding starts with an arbitrary image and iteratively applies stored transformations. This process exploits the contractive nature of the transformations, ensuring convergence to a unique fixed point - the reconstructed image. Decoding is significantly faster than encoding, creating computational asymmetry.

Fractal Image Compression Encoding

Partitioning and Self-Similarity Exploitation

Top images from around the web for Partitioning and Self-Similarity Exploitation

• 

  Affine transformation - formulasearchengine View original

  Is this image relevant?

• 

  Frontiers | Fractal Analysis of Lung Structure in Chronic Obstructive Pulmonary Disease View original

  Is this image relevant?

• 

  Frontiers | Accurate Reconstruction of Image Stimuli From Human Functional Magnetic Resonance ... View original

  Is this image relevant?

• 

  Affine transformation - formulasearchengine View original

  Is this image relevant?

• 

  Frontiers | Fractal Analysis of Lung Structure in Chronic Obstructive Pulmonary Disease View original

  Is this image relevant?

1 of 3

Top images from around the web for Partitioning and Self-Similarity Exploitation

• 

  Affine transformation - formulasearchengine View original

  Is this image relevant?

• 

  Frontiers | Fractal Analysis of Lung Structure in Chronic Obstructive Pulmonary Disease View original

  Is this image relevant?

• 

  Frontiers | Accurate Reconstruction of Image Stimuli From Human Functional Magnetic Resonance ... View original

  Is this image relevant?

• 

  Affine transformation - formulasearchengine View original

  Is this image relevant?

• 

  Frontiers | Fractal Analysis of Lung Structure in Chronic Obstructive Pulmonary Disease View original

  Is this image relevant?

1 of 3

• Fractal image compression exploits self-similarity within images to achieve high compression ratios
• Encoding process partitions the image into:
  • Non-overlapping range blocks
  • Overlapping domain blocks (typically larger than range blocks)
• Algorithm searches for domain block and affine transformation that closely approximates each range block
• Affine transformations used include:
  • Scaling
  • Rotation
  • Adjustments to brightness and contrast
• Encoding aims to minimize difference between transformed domain block and range block
  • Often uses metrics like mean squared error (MSE)

Compression Output and Computational Considerations

• Encoding output consists of transformation coefficients for each range block
  • Forms compressed representation of the image
• Process computationally intensive due to exhaustive search for matching domain blocks
• Optimization techniques crucial for practical implementation
  • Quad-tree partitioning reduces complexity by adaptively dividing image based on local characteristics
  • Classification schemes for domain blocks reduce search space
    • Improves encoding efficiency at cost of some compression quality
• Parallel processing techniques distribute computational load across multiple processors
  • Reduces overall encoding time

Image Reconstruction from Compressed Data

Iterative Decoding Process

• Decoding starts with arbitrary initial image of same size as original (blank or random noise image)
• Process iteratively applies stored affine transformations to current image
  • Updates each range block with corresponding transformed domain block
• Iterations repeated until:
  • Fixed number reached (typically 8 to 16)
  • Convergence criterion met
• Each iteration refines image, progressively revealing more detail
• Decoding exploits contractive nature of transformations
  • Ensures process converges to unique fixed point (reconstructed image)

Decoding Efficiency and Asymmetry

• Decoding significantly faster than encoding
  • Creates asymmetry in computational requirements
• Number of iterations for acceptable image quality depends on:
  • Image complexity
  • Desired fidelity
• Algebraic Fractal Decoder technique accelerates convergence
  • Reduces number of iterations required for image reconstruction

Computational Complexity of Fractal Compression

Encoding Complexity Analysis

• Time complexity of basic encoding algorithm: $O(n^4)$ for $n \times n$ image
  • Due to exhaustive search for matching domain blocks
• Space complexity for encoding: $O(n^2)$
  • Primarily for storing original image and transformation coefficients
• High computational cost of encoding led to various optimization techniques
  • Aimed at reducing search space or accelerating matching process

Decoding Complexity and Optimization Strategies

• Decoding algorithm time complexity: $O(kn^2)$
  • $k$ represents number of iterations
  • Much faster than encoding
• Optimization techniques for reducing encoding complexity:
  • Quad-tree partitioning
  • Classification schemes for domain blocks
  • Parallel processing
• Wavelet-based fractal compression combines fractal techniques with wavelet transforms
  • Offers improved compression ratios and faster encoding times

Encoding vs Decoding Optimization Techniques

Encoding Optimization Methods

• Classification-based methods categorize domain blocks
  • Based on features like edge orientation or texture
  • Reduces search space during encoding
• Genetic algorithms and evolutionary computation techniques optimize search for matching domain blocks
  • Potentially improves compression quality and speed
• Adaptive partitioning schemes adjust block sizes based on image complexity
  • Examples include quad-tree and HV partitioning
  • Balances compression ratio and image quality
• Fast fractal encoding methods trade compression quality for reduced encoding time
  • Nearest neighbor search
  • Feature vector matching

Hybrid and Decoding Optimization Approaches

• Hybrid approaches combine fractal compression with other techniques
  • Example: DCT-based methods
  • Offers balance between compression ratio, quality, and computational complexity
• Wavelet-based fractal compression improves compression ratios and encoding speed
• For decoding, Algebraic Fractal Decoder accelerates convergence
  • Reduces number of iterations required for image reconstruction
• Parallel processing techniques applicable to both encoding and decoding
  • Distributes computational load across multiple processors