I. INTRODUCTION
Many
corporations now demand that closed circuit television (CCTV) recordings be continually
recorded and saved for at least two weeks. Because they offer better
flexibility, higher performance, and are easier to deploy. For CCTV
applications, wireless-based high resolution cameras
are becoming more common. Three major drawbacks of this flexibility are the
high storage requirements, bandwidth limits, and power import
restrictions [49]. As a result, image reduction is a critical
component of any CCTV system. Fractal image compression (FIC) is an alternate
approach in this area due to its great compression efficiency, higher
performance, and simplicity. During transmission or storage, using
self-similarity between image blocks, an image of 2-D in size is turned into a
statistically uncorrelated dataset or fractals [1].
During the
encoding phase, an image will partition into non-overlapping blocks called
range blocks and overlapping blocks called domain blocks [2]. The
search method looks for the best-matched domain block for each range block. To
do so, all domain blocks must be evaluated, and the best-matched domain block
with the fewest matching errors is identified.
FIC based on an
iteration function system (IFS), Barnsley and Hurd [2] suggested
this method first, and then Jacquin [3] expanded
it further to create a partitioning iteration function system (PIFS). FIC has a
high CR when compared to other lossy techniques, especially when applied to
images captured by satellite imagery or aerial photography [3]. FIC
has a variety of applications in other categories of image processing, like character
recognition [4] and watermarking [5]. A high PSNR
and a simplistic decoding technique are two further appealing features of
FIC [6], [7].
FIC typically
necessitates a huge number of searches. As a result, Instead
of hours, the encoding time is measured in minutes. Reducing the size of the
domain block is one of the most straightforward ways to speed up coding. For
each range to what it mapped, a spatial limitation on the domain block is
used [8]. Several academics have developed strategies based on
various split decision functions to minimize the size of a domain block in the
previous decade [10,11]. Many scholars have employed the
variance feature as a decision function for domain block reduction [9,
12]. The entropy function has recently can used to minimize the domain
block as a split decision function [14, 13].
The proposed
FIC methods can be classified into three types depending on the search
technique: (1) full of search [15], (2) partial of search [16],
[17], and (3) no search [18]. The full-search
methodology is the most time-consuming of these search strategies. That is
because the whole image must be searched to get the best-matched domain block
for each range block. In general, the smaller the search space, the faster the
encoding. On the other indicator, Partial search is the second most
time-consuming method for reducing the search space and speeding up the
encoding process. To increase performance and reduce the processing time, many
authors have introduced approaches for improving the FIC [19]–[27].
Zheng
et al. [19] and Wu et al. [23] employed genetic
strategy, whereas Wang et al. [24] used hybrid encoding method
using STD and DCT. Further research [25] investigated the Hadamard
transformation for reducing runtime. In [22] and [26], the method
of prediction is combined with another fractal methodology for reducing
encoding time. Other studies, like as [20],[21], employed the
categorization method to speed up the encoding process by partitioning blocks
into classes and searching exclusively for blocks in the same class even with
search-less algorithms [28]. This tendency is slightly deviated by the
findings of Haque et al. [29], Erra
[30], and Ismail et al. [31], these scientists
used parallel processing instead of serial computation to accelerate the
procedure. As a result, the encoding speed has significantly increased. Saad,
et al. [32] created a new FIC strategy based on partial
similarity search, which achieves a considerable speed increase.
This
paper proposes a new fast-full search FIC algorithm for encoding high resolution
images with size (512x512) pixel for utilizing the fast-full search approach to
detect all pixels in a range block, as well as for future hardware design with
acceptable results to serve the detecting system.
The rest
of this paper is structured as follows: Section II looks
at related work on video compression and fractal picture coding. The FIC
method's encoding and decoding strategy is showed in Section III. Following
that, Section IV describes the
methodology used in this study. The proposed algorithm is then described in
Section V, followed by the experimental
results and study findings in Section VI. Section VII comes to a conclusion. Finally, Section VIII summarizes
our future plans and defines the research's direction.
2.
RELATED WORKS
Multiple
published papers in the literature focused on reducing the fractal technique's
encoding time using various methods [16], [24], [28], [33]-[38]. Even
though there are some algorithms for speeding up fractal calculations,
practically all of these designs presently employ
FIC's fundamental parallelism to enhance. Few designs avoid high-complexity
operations, lower operation precision, or combine the two to reduce the
computational complexity in coding processes.
For instance, L.
E. George, et al. [39] introduced a fractal
approach according to the vector quantization approach using the block indexing
technique. The color image blocks utilized to create the codebook using an
affine transform. S. Zhu, et al.[40] They explored a
method where fractal video sequences are coded in the context of region-based
functionality to speed up the encoding process. In another work, A.
G. Baviskar, et al. [41] presented
a strategy for fractal image compression, an effective domain search strategy
based on feature extraction is presented, which improved compressed image
quality while reducing encoding and decoding time. Likewise, but with more
clearly defined classes, the authors S. V Veenadevi,
et al [42] introduced a proposal method to achieve fractal
image compression, using a threshold value and Quadtree decomposition, the
original image will divided into non-overlapping
parts. For image encoding and decoding, a threshold value and Huffman coding
used, these methods used to compress satellite images.
S. B. Dhok, et al. [43] published a new
method with full search based on motion estimation technique utilizing FFT that
uses a circular cross-correlation approach attemptting
to optimize the runtime. The correlation-based similarity metric determines the
mean subtracted adjusted coefficient for correlation between the range and the
domain block. In comparing it with the standard full-search block matching
strategy with similar decoded video quality with the same amount of compression
ratio. The recommended algorithm can achieve a faster processing speed.
In the same
track, C. Rawat, et al.[44] presented a simple method for improving
compression quality by using the DCT theorem and fractal image compression
techniques. The original image can divided into a
total of (8x8) non-overlapping blocks. The DCT utilized for all blocks of the
image, and then the DCT coefficients are quantized. The zero values eliminated
using a zig-zag approach on the block values, which improves compression
quality and extracts nonzero data. In U. Nandi, et
al.[45] created a
new rapid classification strategy with quadtree partitioning technique and DCT
for image compression. The compression ratio and peak signal to noise ratio
(PSNR) of the fractal image compression approach is maintained by this
classification procedure, but the compression time is greatly reduced.
S. B. Dhok et al.[46] proposed a new coding approach based on Quadtree
decompositions to reduce searching time by Using domain block motion corrected
estimation error as little more than a threshold to limit incoming block
divisions. In the frequency domain, cross-correlation is performed using FFT,
which uses three-level quadtree partitions and quick NCC computation as a
matching criterion, as well as a single computing approach for all domain blocks
rather than individual block-by-block calculations. The addition of rotation
and reflection DFT capabilities to the IFFT considerably reduces the encoding
time of null extended range blocks.
On the other hand, V. Chaurasia, et
al. [47] performed a mechanism method in which domain pool
size was optimized by changing the overlapping of domain blocks. The number of
the domain blocks formed in domain partitioning is represented in terms of
image size and range size. It is directly proportional to image size while
indirectly proportional to range size. Later, K. Jaferzadeh, et al. [48] proposed
an approach to make FIC a faster technique by using local features to reduce
search space; a new local binary feature is introduced. The extracted feature
is used to calculate distinction among range and domain blocks by using Hamming
distance method instead of the least-square method.
Recently, Saad, et al.[49] the proposed approach
using deep data pipelining to implement FIC, in
this approach, two same processes can be applied immediately using two units as
a processor. Later time for encoding is reduced by adding the innately
more the extent of the relationship amid pixels into vicinity places and
best matching domain block search is done in the nearby blocks only. The
proposed method based on pipelining strategy encoded a large-size image very
fast with reasonable PSNR and CR. While, A.
Banerjee, et al. [50] introduced
another FIC algorithm using quadtree partitioning in which the original image
is divided into even part and odd part respectively. One part is divided using
the quadtree decomposition of a range of thresholds. Then complete encoding of
fractal codes is done using Huffman coding. This proposed suggested scheme
reduces time complexity, as well as, gives increased
CR and acceptable PSNR. Also, A.-M. H.
Y. Saad, et al .[51] they
investigated a new method where the fractal technique's search time was reduced
as compared to a full-fledged dynamic search approach. The dynamic search
starts with a domain block nearest to a range block so
it has to be coded and expands until it finds a suitably matching domain block
or until the completed search.
The effect of using a spatial dynamic search approach instead of a
matching threshold strategy on the search reduction of standard full-search of
FIC algorithm studied in Saad, et al.[52],When using the matching
threshold strategy, the dynamic search approach begins with the closest domain
and continues until after an acceptable matching block is found or the full
image is covered. Closed sub-image blocks are selected over distant image
blocks, according to the proposed approach. The discussion use of fast
wavelet transforms to classify data done in [53]. Wang, et
al. [54], on the other hand, devised a fractal
image compression algorithm according to quadtree division, neighbor searching,
and strategy of asymptotic. Wang, et al. [55] developed
a standard deviation feature for dividing the range blocks into two groups,
with the first group range blocks encoded by using the particle swarm
optimization technique to find a suitably matched domain block, and the other
group range blocks encoded directly by storing their average values without
searching.
In general, the main challenges of fractal
compression systems are compression ratio (CR), peak signal to noise
ratio (PSNR), and Encoding time. From the previous articles, we see that
most of the proposed algorithms were introduced to improve one of these
parameters on the other .and most of these algorithms are used to implement hardware
management, not just software applications. Nonetheless, for categorization
purposes, the majority of these systems necessitate a large number of logic
elements and memory block units[49]. As
a result, when used to encode high-quality images, the circuitry becomes even
more complex. As a result, it has been considered to design a simple but
effective fractal image compression algorithm that does not necessitate
significant additional processes. The solution we presented maintains image
quality while balancing the connection between computational complexity,
compression ratio, and processing time.
3.
FRACTAL IMAGE COMPRESSION
3.1 BACKGROUND
Barnsley and Hurd [2] were
the first to propose the Fractal image compression technology. He created the
Iterated Function Systems (IFS) theory and proposed the Collage Theorem, which
demonstrates how IFS may be used to approximate images. Using Partitioned
Iterated Function Systems (PIFS), Jacquin [3] has
developed a fully automatic fractal compression technique that eliminates the requirement
for human intervention during the compression process. Various fractal image
compression versions and enhancements have been developed as of now. Therefore in this paper, we'll look at PIFS; it divides the
original image into smaller and larger parts. We assume that the input image
with width M and with
height N may both be represented as powers of 2 when provided
the image in the rectangular form of an array with size MxN. The input image can be divided in any
way you like, but rectangular blocks are an obvious choice. We used square
blocks to simplify the partitioning.
In the coding
phase, the input image will be partitioned into non-overlapping range blocks (rxr) referred to as R blocks
and overlapping domain blocks (dxd) that are
larger than rang block and referred to as D blocks. The
size of a domain block has always been four times greater than a range
block. As for the matching phase, the
domain blocks will resample to match the range block size. This is accomplished
by replacing the average gray level of each non-overlapping 2x2 pixel in the
domain block.
The below
equation is the affine transformation W search process for
finding the best matching domain block for each range block[1]:
Where S and B regulate
the contrast and brightness, respectively, z is the
pixel's value at the position (x,y). The
symmetry transformation is also defined by the letters( a,
b, c, d, e, f). Only the S and B parameters
are considered in the algorithm to keep it simple. In the meantime, (a) and (d)
are both set to 1 to retain the pixels' placements, while the rest of the
parameters well set to zero.
A Mean Square Error (MSE) is a
metric for comparing range and domain blocks. Mathematically [1]:
Where N
represents the number of range's block pixels and (Ri, Di) is
the values of intensity for the range and domain blocks at the ith position. To obtain optimal matching between
the range and domain blocks, the parameters in Eq. 2 must
be approximated accurately. The technique of calculating ideal S and B values
is comparable to differentiating the Eq. 2 and then
equivalent the outputs to zero, according to standard optimization
theory.
Hence:
The ideal value for B in this situation could
be calculated in the following way:
In the same way, the ideal value for S is:
By substituting
Eq.4 into Eq.5, we get:
Finally, The MSE is calculated by putting Eqs.
4 and 6 into Eq. 2 as follows:
After examining all domain blocks for a particular range block,
the S and B values
corresponding to the domain block with the lowest MSE are
saved. Quantize S and B values
into specific bit sizes, which are typically 5 to 2 bits for S and
7 bits for B. When the MSE goes
below a certain threshold, the matching procedures are stopped and that's
reducing the search space.
3.2 DECODING
PROCEDURE
The decoding procedure is an iterative process
that begins with estimation and adjusts it until convergence is achieved. Each
range block is reconstructed using the following equation in each iteration[32]:
Where R' represents the reconstructed
range blocks while D (i, j) is the
best matching domain block in the ith position,
while B and S are corresponding
domain block's scale and offset values, respectively. In the next iterative
cycle, the range of the image evaluated at Eq. 8 is utilized
as the domain of a specified image, and this procedure continues until
convergence is obtained. To correctly decompress an image, decoding usually
takes no more than 10 iterations. The reconstruction's fidelity is defined in
terms of PSNR, which is measured as:
Where f is the original image, f ' is
the reconstructed image, and M ×N is the size of the image
[32].
4.
METHODOLOGY
A comprehensive
search strategy for a collection of transformations in the domain and range
blocks that translate an image into itself is offered as an efficient fractal
image compression scheme. The proposed methodology is shown in figure (1),
where the FIC procedure began by partitioning the input image (M X
N) into square non-overlapping range blocks (r x r) referred
to as R and overlapping domain blocks (d x d)
referred to as D and that’s partitioning depending on
the proximity of a block of pixels in an image to the surrounding area.
The overlapping
block partitioning for the construction of the domain pool is done with a
step-size stp which can be
from 1 to d, where the greater stp value, the fewer domain blocks are
constructed. The following formula can be used to calculate the number of domain
blocks Nd for an (MxN) image [52]:
As domain blocks are often four times bigger than the size of range
blocks where (d = 2r), each domain block should be geometrically
expanded to the range block's size during the recognition process. The average
of every 2x2 pixel is used to do compression. The affine transform is used to
improve the level of match between the range blocks and the domain blocks and it can change the constricted domain block's
intensity values by multiplying each of them with a certain value of contrast
scaling S and then adding the value of brightness
offset B to the output.
Until the values of S and B have been
computed are they quantized into a specific bit size, which is commonly 5 to 2
bits for S and 7 bits for B. For decoding
requirements, the fractal codes associated with the identified matched D
must be conserved, and D blocks must be searched and matched one
by one for a certain R in order to find D
with MSE less than a pre-defined number. S, B,
and the coordinates for finding matching D (denoted as (Xd, Yd) for the x- and y-axes)
will be recorded in the fractal codes file. The compressed image file will
contain all R. As a result, the following calculation can be used
to calculate the size of the compression file (CF size) [52]:
Where NR is equal to [NR = (MxN) / (rxr)] and
represents the total number of the range blocks in the encoding image. The
remaining coefficients represent the bit sizes of the fractal codes. The
compression ratio CR can be computed using (11), where
the original file size of the image (OF), compressed file
size (CF), and [CR=OF/CF].
Figure (1): Proposed methodology block
diagram
Figure (2) illustrates the fast full-search entire
procedure. As shown in the graphic, the search method prioritized the closet
domain blocks over the farthest ones. Whereas Figure (2) represents the search
condition to range block R in a center of the image,
this is evident that perhaps the nearest domain block to R is D0,
which will be the block that concludes R inside of it.
When D0 does not satisfy R,
searching space is pushed to the specified for every direction to include the
secondly nearest domain block.
A 3x3 domain block search window will appear as a
result. Increase the search window size to 5 then 7 then continue until an
adequate matching domain is discovered or the full image is searched. When
searching is enlarged, it will begin with domain blocks that locate at the
right side of the same horizontal line as D0 and work
their way clockwise and repeated, as shown in the graphical construction in the
figure below.
Figure (2):
Fast full-search mechanism demonstration.
The flowchart of a fast full-search algorithm for
fractal image compression that is utilized to assess our proposed search
approaches is shown in Figure (3). The process began with the image initially
interred and then the width M and height N of
the image that well measured.
The size of the range block (r),
division step-size of the domain blocks (stp),
scaling reduction bit-size (S bitsize)
and the value of main square error (MSE-thr)
must all be set so that we can use our whole search algorithm technique under
various typical coding conditions. To indicate the search processer and
encoding phase, these factors are used to calculate the number of blocks for
each iteration in range blocks and domain blocks NR and Nd.
After that, for each of the range blocks Ri, Where i ={0,
1,....., NR-1} and each domain block Dj where j={0,1,....., Nd-1} should
be compared one by one, starting with D0. Then the inter-image I is
partitioned into sub-image of (r x r) range block (R) and (d
x d) domain block (D) with step-size stp.
The following coefficients MSE, B,
and S are computed at the matching step of the
combination of both (Ri, Dj) using equations (2),
(4), and (6), respectively. Dj is
the selected best matching domain block for Ri if the
MSE value is less than the defined MSE-thr. In this situation, the fractal codes for Ri will
be the matching values of S, and B, as well as the
coordinate of the best matching domain Dj (X,
Y)Dj. Elsewhere, the
search under unsatisfied conditions will be continue till the matching
domain Dj with the
condition MSE < MSE-thr is
found or searching phase is completed or when all domain block Dj are
detected
( i.e.; j = Nd -1) . Later, if a search has stopped
without locating the desired matching domain, the fractal codes of the best
effective Dj are well saved
instead. For doing that, the fractal codes of each Dj discovered
at MSE < minMSE (this is
the lowest MSE ever) are well kept in varied temporaries (Si, Bi, (Xd, Yd)). As a result, when the search is
complete, these temporal values will preserve the fractal codes for the
best-matched Dj, which
can then be easily stored in a compressed file (CF). The method
is repeated in the encoded image for each Ri.
