1. INTRODUCTION
With the giant development of computer technologies, the need for images has increased. At the same time, that development in technology with the state-of-the-art means of image acquisition devices (cameras, mobiles, etc.) has added more megabytes to represent image pixels. Of course, those extra megabytes will need extra storage space to be saved and extra time to be shared. Hereby, many methods have emerged that aim to reduce image data, and one of these methods is the fractal image compression (FIC). (Menassel et al., 2020; AL-Bundi & Abd, 2020; Fathi & Abduljabbar, 2020; Ahmed et al., 2020)
Fractal image compression has shown great potential in terms of achieving high compression rate and good rate-distortion performance. It can obtain extraordinarily high-rate compression performance superior to that of the DCT-based algorithms. However, due to its complicated algorithm and the time-consuming process, the algorithm has been less attractive and applied less to real-time encoders. However, with the advancement of technology and the development of faster processing units, real-time encoding using fractal encoding is becoming more feasible. The main fast algorithms capable of achieving these impressive compression rates are classification-based fast fractal image compression algorithms. In the fractal coding process, a small domain pool can bring about better encoding features and a smaller file size of the encoded domain. This reduction in domain pool size through classification can lead to more efficient encoding and improved compression ratios. The domain pool reduction through classification proposed in this project, provides a better complexity-quality trade-off in fast fractal image compression. Many papers have concluded different types of domain pool reduction, which efficiently speed up the encoding process through different measures and actions. (Dwivedi & Mishra, 2022; Ahadullah et al., 2020; Singh & Bharany, 2020; Faragallah et al., 2022)
Literature Review
Fractal image compression is a computationally intensive process that has prompted significant research into methods for reducing encoding time while maintaining image quality. Various strategies have been proposed to address this challenge, focusing primarily on domain pool reduction and classification techniques.
Nithila and Kousalyadevi (2014) introduced a method to speed up fractal image compression by employing classification concept. Their approach involves classifying domain blocks into 72 classes based on pixel intensity orderings and variance, allowing for a more efficient search by comparing only those domains and ranges within the same class. This significantly reduces the search space and thus improves compression speed without sacrificing much accuracy.
Similarly, Revathy and Jayamohan (2012) proposed a dynamic domain classification method that adapts the domain pool for each range block based on its local fractal dimension. By calculating the fractal dimension of range and domain blocks, their method selectively searches for matches within domains that have similar fractal dimensions. This dynamic approach significantly reduces encoding time without compromising image quality.
Building on these foundational works, the current research introduces an approach to accelerate fractal encoding through domain classification based on standard deviation. Standard deviation is selected as a metric for classifying domain blocks because it effectively captures the variability and texture of pixel values within a block. Additionally, this approach helps preserve important image features by ensuring that blocks with similar textural characteristics are matched, thereby maintaining image quality. This static classification approach ensures that only domain blocks with similar standard deviations are considered for matching, thereby decreasing encoding time. Unlike the dynamic adaptation of Revathy and Jayamohan or the extensive class division of Nithila and Kousalyadevi, the current method offers a streamlined process that balances simplicity and efficiency.
Theoretical Background
Fractal image compression is a method that uses the self-similarity properties of images to achieve efficient compression. It is based on the concept of iterated function systems (IFS), which represent images as fixed points of contractive transformations. This technique was initially developed by Michael Barnsley and later refined by Arnaud Jacquin, who introduced a practical algorithm for its implementation (Jacquin, 1992; Barnsley, 1993).
The process involves dividing an image into smaller blocks and finding self-similarities within these blocks. These similarities are encoded using affine transformations, which include scaling, rotation, and translation. The method exploits the redundancy and self-similarity in natural images, allowing for high compression ratios (Fisher, 1995; Wohlberg & de Jager, 1999).
One of the main challenges of fractal image compression is the computational complexity of the encoding process, which requires extensive searching for matching blocks. To address this, various strategies have been developed, such as quadtree partitioning and fast search algorithms. Recent advancements have also explored combining fractal compression with other techniques like wavelet transforms and neural networks to improve performance (Saupe & Hamzaoui, 1994; Wohlberg & de Jager, 1999).
Methodology
The method was performed on four 256x256 images, Cameraman, Pepper, Tiger, and Flower (figure 1), with 8 bits per pixel, and the software simulation was done using Visual C++ on Windows 10, Intel Core i7-2670QM CPU 2.20 GHz platform.
The current study's method focuses on decreasing the time required for encoding through domain pool reduction. Reduction is done as follows:
The maximum standard deviation of range blocks for an image is found, which represents the measure of the distribution of the block's pixel values. Then, that value is divided by the required number of classes in order to create matching groups.
Before searching for the best match in the encoding step, the standard deviation for each range block was compared with that of the domain block to determine whether they both lay within the same group. If this was the case, a search for the best match was executed; otherwise, this domain block would be excluded from the matching process, and the next domain block would be evaluated in the same previous process. This reduction in domain pool size should result in a decrease in encoding time. The algorithm is as follows:
Algorithm:
1. Load Image
· Load a 256x256 grayscale image.
2. Quadtree Partitioning
· Partition the image using the quadtree method. This involves recursively dividing the image into four quadrants until a certain homogeneity criterion is met.
3. Domain Pool Creation
· Create a domain pool by downsampling the original 256x256 image to a 128x128 image using the averaging method.
4. Calculate Maximum Standard Deviation
· Compute the standard deviation for each range block.
(1)
· Identify the maximum standard deviation among all range blocks.
5. Classify Range Blocks
· Determine the number of classes (ClassNo) desired.
· Calculate the group threshold using the formula:
(2)
· Classify each range block into a group based on its standard deviation and the calculated threshold G.
6. Find Best Match for Each Range Block
· For each range block:
a. Determine its group based on its standard deviation.
b. Search for the best matching domain block within the same group:
- Iterate over domain blocks in the same group.
- Compare each domain block with the range block.
- Keep track of the best match based on root mean square (rms) similarity metric.
(3)
c. Select the domain block that best matches the range block.
The rationale for the choice of parameters in the classification and quadtree partitioning processes is detailed below.
The quadtree partitioning method was chosen because it is a well-established technique for dividing an image into smaller blocks based on homogeneity criteria. It ensures that the image is partitioned into blocks of varying sizes, with smaller blocks used for areas of high detail and larger blocks for homogeneous regions.
The quadtree partitioning process in this study was guided by four key control parameters: Maximum Block Size, Minimum Block Size, Ratio, and Inclusion Factor.
The Maximum and Minimum Block Sizes, which represent the largest and smallest allowable sizes, respectively, for a block in the quadtree partitioning process, were chosen to ensure that the partitioning process adapts to the content of the image, capturing fine details in complex regions while reducing the number of range blocks in homogeneous regions.
The Ratio parameter controls how sensitive the partitioning process is to local variations. Lower values allow for more splits, capturing finer details in regions with significant variations, whereas higher values reduce the number of splits, which can lead to faster processing in more homogeneous areas. The Inclusion Factor determines the threshold for splitting a block based on its homogeneity. Lower values allow for more splitting, ensuring that even slightly heterogeneous blocks are divided, which can enhance detail capture in complex areas, whereas higher values result in fewer splits, which can improve processing speed in more uniform regions.
These parameters were predetermined to ensure a balance between computational efficiency and image quality.
The classification of domain blocks was based on their standard deviation, which was chosen as the primary metric because it effectively captures the variability and texture of pixel values within a block. Standard deviation is computationally simple to calculate and provides a reliable measure of the distribution of pixel intensities. This makes it a suitable choice for grouping blocks with similar characteristics, ensuring that range blocks are only compared with domain blocks that are likely to produce a good match.
The number of classes (ClassNo) was set to 32 in this study. The choice of 32 classes was determined experimentally, as it provided a significant reduction in encoding time while maintaining high PSNR values across all test images. A higher number of classes would result in smaller groups of domain blocks, further reducing the search space and encoding time. However, excessively increasing the number of classes could lead to insufficient domain blocks within each class, potentially degrading the quality of the reconstructed image. Conversely, a lower number of classes would increase the search space, reducing the time-saving benefits of classification.
The group threshold (G) for classification was calculated using the formula ( G = MaxStd / ClassNo ), where MaxStd is the maximum standard deviation among all range blocks, and ClassNo is the number of classes. This formula ensures that the range of standard deviation values is evenly divided among the classes, creating groups of domain blocks with similar variability.
2. RESULTS AND ANALYSIS
The different tests are performed on four 256x256 images, Camerman, Pepper, Tiger, and Flower, with 8 bpp, and the software simulation is done using VC++ on Windows 10, Intel Core i7-2670QM CPU 2.20 GHz platform. The quadtree partition (Y. Fisher, 1995) is adopted. The image quality is measured by the peak signal-to-noise ratio (PSNR).
The PSNR is defined as follows:
(4)
where MSE (mean-square error)
(5)
where xi and yi are the pixels in the original and in the reconstructed image at the same position, respectively.
Figure 1: Test images: Cameraman(a), Pepper(b), Tiger(c), Butterfly(d)
Out of the classification methodology applied for the current article, it has been shown, as compared with Fisher’s method (Y. Fisher, 1995), that a very good reduction in encoding time has been achieved while keeping good quality as shown in table (1), table (2), and figure (2).
