Abstract--The main objective of this paper is to examine the performance of Neuro- Statistical Sparse Transformation Function for implementation in a still image vector coding based compression system. This paper discusses the important features of low bit-rate image coding which is based on recent developments in the theory of Multivariate Nonlinear Piecewise Polynomial Approximation in still images. It combines Binary Space Partition (BSP) scheme with Geometric Wavelet (GW) tree approximation so as to efficiently capture curve singularities and provide a sparse representation of the image. The quality of the reconstructed image is measured objectively using Peak Signal to Noise Ratio. Experimental results show that the proposed image compression system yields higher compression with minimal loss.
Keywords--Grayscale images, Neuro Statistical, Compression, Binary space partition technique.
I. INTRODUCTION
Structured approach to the design of the reversible transforms for image compression is advantageous than ad-hoc methods. By using a highly structured approach to transform design, more sophisticated transform can be produced. Thus, general frameworks for the construction of reversible transforms are of greater importance. The proposed algorithm preserves the significant edge singularities of the image even at very low bit-rates, without the ringing artifacts that is a known phenomenon of low bit-rate isotropic wavelet coding. The first segmentation-based coding method appeared in the early 80’s. This algorithm partition the image into geometric regions over which it is approximated using Low-Order Polynomials. Segmentation techniques partition the digital image into a set of different geometric regions which are approximated by simple functions called as low order polynomials. This technique subdivides an initial convex domain into two sub -domains by intersecting it with a hyper plane. In image processing applications, the convex domain is the plane on which a straight line acts as a hyper plane. The subdivision process is performed to minimize the given cost functional. The BSP (Radha et al., 1996) approach partitions the desired image recursively by straight lines in a hierarchical manner. The major drawback of this method is low distortion rate and high computational complexity (Shukla et al., 2005).
Effective methods for transform-domain image compression rely on the successful interplay of three related components: A transform with desirable properties, Accurate models for the transform coefficients, and Efficient compression algorithms that operate according to the models. From a practical standpoint, transform coefficients for images of interest should exhibit a certain structure, or behavior that can be well modeled. Ideally, such models should also lead to fast, efficient processing algorithms; hidden Markov trees (HMTs) are one example where the organization of a model leads naturally to an elegant suite of signal processing algorithms. The wavelet transform is a key ingredient in most state-of-the-art image compression algorithms, including the recent JPEG-2000 standard. Historically the use of wavelets in image processing arose primarily due to the success of wavelets in one-dimensional (1-d) signal processing (Varodayan et al., 2005).
The wavelet transform provides a multi scale analysis that is localized in both space and frequency. Due to this arrangement, 1-d wavelets provide efficient representations for the large and useful class of piecewise-smooth 1-d signals. Smooth components of these signals are well-localized in the frequency domain, while point singularities at discontinuities are localized spatially. As a result, the 1-D wavelet transform of a Piecewise-Smooth Signal is sparse and most of the signal energy is captured by a few large wavelet coefficients. Reconstructing the signal using these few wavelet coefficients can provide a very accurate “Nonlinear Approximation” of the original signal. JPEG-2000 (JPEG, 2000) and most other wavelet-based image coders employ separable two-dimensional (2-D) filter banks that are a simple extension of 1-d techniques. As with 1-d wavelets, the 2-D wavelet coefficients can be interpreted and modeled using a tree-structured space-frequency representation (Firouzmaneshi, 2011). The convenience of tree-structured modeling has been exploited in a variety of wavelet-based compression algorithms. Despite the popularity of wavelet- based approaches to compression, 2-d wavelets fail to provide sparse representations for geometric images. Natural images can be viewed as collections of geometric, smooth, and textured regions. Geometric features, such as edges, generally indicate transitions between smooth or textured regions and are characterized by abrupt changes in intensity that persist along straight or curved contours. Edges communicate important information, conveying the location and shape of pictured objects and many of their features. In addition, because pixel values vary rapidly in the direction orthogonal to an edge, much of an image’s high-frequency energy may come from edges. For these reasons, a successful algorithm for image compression must efficiently encode geometric features. As with 1-d wavelets, 2-d wavelets do provide efficient approximations for smooth regions and point singularities. In the case of an edge, however, where a singularity extends along a contour, the number of 2-d wavelet basis functions overlapping the singularity grows exponentially at finer scales and many wavelet coefficients are required to reconstruct even a simple, straight edge.
The abundance of significant coefficients describing geometry is not an immediate barrier to effective wavelet- domain image processing including compression, in particular. There is, in fact, a strong coherency among the coefficients which is imposed by the structure of the geometry. In the case of an isolated, sharp edge, for example, the 1-d information describing the trace of the edge contour completely determines the values of the 2-d wavelet coefficients. A simplified model not only affects rate-distortion (R-D) efficiency, but also leads to ringing artifacts when quantization disrupts the geometric coherency of the coefficients. Faced with the challenges presented by geometric features, two clear options are available: the first is to develop a new transform that includes properties such as Sparse Representations for Geometry; the second is to improve the Wavelet-Domain Models and algorithms accordingly. One difficulty is redundancy: these over complete transforms produce a collection of coefficients that is larger than the number of pixels in the original image. In addition, these transforms are designed specifically to account for geometry; modeling their behavior in non-geometric regions may prove to be difficult.
II. LITERATURE REVIEW
In the past decades, the discrete cosine transform (DCT) has been the most popular for compression because it provides optimal performance and can be implemented at a reasonable cost. Several compression algorithms like JPEG standard, the MPEG standard (Shannon, 1948) are based on DCT (Skodras et al., 2001). However, the EZW, the SPIHT, the SPECK, the EBCOT algorithms and the current JPEG 2000 standard are based on the Discrete Wavelet Transform (DWT). DWT has the ability to solve the blocking effect introduced by DCT; it also reduces the correlation between the neighboring pixels and gives Multi Scale Sparse Representation of the image.
In spite of providing excellent results in terms of
rate-distortion compression, the transform-based coding
Figure 1. Block Diagram of the Proposed Work.
methods do not take an advantage of the underlying geometry of the edge singularities in an image. From the mid 80s there have been many attempts to design second generation image coding techniques that exploit the geometry of the edge singularities of an image. Recently, many image compression algorithms such as the Bandelets, the Prune tree, the Prune-Join tree, and the GW image coding method based on the sparse geometric representation have been introduced. The present study is envisaged to improve the GW image coding (Negahdaripour and Khamene, 2000) method. The slope intercept form of the straight line is used in the binary space partition scheme (BSP). Firouzmaneshi et al. (2011) presented the spatially variation sensing method to enhance the interactive and mesh transmission for online 3D applications. Some of the researchers implemented the mesh compression while merging the regions in a method such as multi resolution LOD based methods; however in the current model the mesh and texture resolution vary continuously by transmission of the points of interest. Drummond et al. (2013) presented the effect of fovea in stereo image compression algorithms using the spatial variation sensing method. The stereo images are taken from the two different perspectives and the depth of each 3D point will be obtained from a relative displacement between its projections on the left and right hand side.
III. OUTLINE OF THE PROPOSED WORK
The proposed method consists of six steps namely; Preprocessing, Construction of BSP forest, Geometric Wavelets, Encoding, Rate distortion optimization and decoding as shown in Fig. 1.
IV. METHODS
The methods for compressing the images using segmentation based coding approach are discussed below.
A. Binary Space Partitioning Technique
The most challenging aspect of a segmentation based coding approach is to balance between a small number of geometrically simple regions and the smoothness of the image signal within these regions.BSP scheme achieves the above balance by using a simple, yet flexible description of the images. It has wide applications in the field of image processing and computer graphics. This technique subdivides an initial convex domain into two sub domains by intersecting it with a hyper plane. In image processing applications, the convex domain is the plane on which a straight line acts as a hyper plane. The subdivision process is performed to minimize the given cost functional. The BSP approach partitions the desired image recursively by straight lines in a hierarchical manner. In image processing applications, the convex domain is the plane on which a straight line acts as a hyper plane. The subdivision process is performed to minimize the given cost functional. The BSP approach partitions the desired image recursively by straight lines in a hierarchical manner. The BSP technique can be described as follows. Given an image f, the algorithm divides convex polygonal domain Ω into two subsets Ω0 and Ω1 using a bisecting line. The subdivision is performed to minimize a given cost functional. This partitioning process then operates recursively in a hierarchical manner on the sub domains until some exit condition is met. To be specific, algorithm can be described of which is a BSP algorithm that identifies a compact geometric description of a target bivariate function. The goal is to encode an optimal cutoff of the BSP tree, to be precise, a sparse piecewise polynomial approximation of the original image based on the union of disjoint polygonal domains in the BSP tree. Rate-distortion optimization strategies are used to meet a given bit rate. The polynomial interpolation is made using the least square method, computing the difference between the image and the polynomial at a defined region Ω. The algorithm continues partitioning each region recursively until there are no enough pixels to subdivide or the approximation error is sufficiently small. The algorithm constructs a binary tree with the partitioning information .The algorithm needs to encode the information of the geometry, namely, the line that cut each sub-domain and the approximation function in each sub-domain represented by the polynomial coefficients. Figure.2 show the steps involved in Binary Space Partitioning algorithm.
First, A line L divides the region Ω into two regions Ω0 and Ω1. The two regions Ω0 and Ω1 are further divided into Ω00, Ω01 and Ω11, Ω10, respectively. These four regions are further divided into eight and so on until area of the sub domain contains only a very few pixels. Then it is represented in a tree structure as shown in Fig. 3.
Figure 2. Binary Space Partitioning of the domain Ω (two levels).
Figure 3. BSP tree representation.
B. Geometric Wavelets
Geometric wavelets are multi-scale dictionary elements which are constructed directly from the data and have guarantees on the computational cost, the number of elements in the dictionary and the sparsity of the representation. Geometric Wavelets (GW) have been considered in context of image compression (Alani et al., 2007). It is a new multi-scale data representation technique which is useful for a variety of applications such as data compression, interpretation and anomaly detection. GW is defined as:
(1)
where Ω0 means one of the children of mother, Ω. It is possible to reconstruct the function using:
. (2)
Geometric Wavelet, ΨΩ is a local difference component that belongs to the detail space between two levels in the BSP tree, a “low resolution” level associated with Ω and a high resolution level associated with Ω0. Geometric wavelets also satisfy the vanishing moment property like isotropic wavelets. Unlike classical wavelets, geometric wavelets do not satisfy the biorthogonality property.
C. The Geometric Wavelet Encoding Algorithm
As in wavelet decomposition, the differences between the original coarse projections of the data and the points projected onto the planes at a finer scale, to find a compact representation for the data at the finer scale is encoded. In order to do this, an effective scheme is developed based on the construction of a minimal space spanning this set of differences. The axes of this difference space are termed as geometric wavelets (Dekel and Leviatan, 2005) and the projections of the finer-scale corrections to the data points onto the plane spanned by these axes are called the wavelet coefficients. The process is continued, forming a binary tree of mother and children at finer and finer scales until no further details are needed to approximate the data up to a pre-specified accuracy.
D. BSP Tree Construction
The BSP method is computationally very
intensive. Therefore generally, the image is tiled first and then the BSP
algorithm is applied independently on each tile. The tile size is generally
adopted as 128x128. But image tiling has many disadvantages. The tiling
procedure signify-
Figure 4. Tiling of Cameraman image.
cantly reduces the time complexity of the algorithm but also reduces its coding efficiency. Also at low bit-rates, there are blocking artifacts at the tiles’ boundaries. The BSP scheme is applied on the entire image by using the polar coordinate form of the straight line. In polar coordinates on the Euclidean plane, a line is expressed as:
(3)
where m is the slope of the line and b is the y-intercept. The equation can be rewritten as:
(4)
It is not possible to quantize the parameter m, as it is unbounded, has value infinity for the straight lines which are parallel to y axis. This problem is solved by using the new parameter ø in place of m in where ø is the angle between the line and the x axis in the anticlockwise direction.
Subsequently, reduces to:
(5)
Here, the probability of minimizing the cost function given is increased, compared to the normal form of the straight line is used.
To reduce the computational cost image tile size is generally taken as 128x128 as shown in Fig. 4.
E. Finding a Sparse GW Representation
The full BSP forest may contain a large number of GW nodes. The purpose of efficient encoding is found useful to impose the additional condition of a tree structure over each image tile. Once a parent is encoded in this hierarchical representation, then it is only needed to encode the quantized BSP line that creates the child. This significantly saves bits when the geometry of the sparse representation is encoded. Finally, a rate-distortion (R-D) optimization process is applied. Instead of encoding a n+k term tree approximation, a geometric wavelet tree can be generated and then pruning-iterations is applied where at each step the sub -tree with minimal R-D slope is pruned. The method is well known and has been applied before the setting of isotropic wavelets and in sparse geometric representations. Empirical results show that this rate-distortion mechanism increases the PSNR by 0.1 dB in some cases. Sparse geometric representation is extracted using greedy approximation methodology, where n wavelets are selected from the joint list of geometric wavelets over all tiles. For the efficient encoding of extracted BSP forest it is necessary that if a child is present in the sparse representation then the parent should also be there, i.e., each BSP tree should be connected. Instead of encoding an n-term tree approximation, an n+k geometric wavelet tree by considering more k nodes can be generated. The penalty for imposing the condition of the connected tree structure is not very huge, since there is high probability that if a child is significant all its ancestors are also significant. The encoding of the geometry of the extracted connected tree structure saves bits as only optimal cut is to be encoded.
F. Encoding the Sparse Representation
There are two types of information to be encoded, the geometry of the support of the wavelets participating in the sparse representation and the polynomial coefficients of the wavelet. Before encoding the extracted BSP forest, a small header is written to the compressed file. Header consists of the minimum and maximum values of the coefficients of the participating wavelet and the image gray levels. Out of header size of 26 bytes, 24 are used in the storage of the minimum and the maximum values of the coefficients while 2 bytes are utilized to store the external values of the image. Root geometric wavelets have maximum contribution in the approximation so each root wavelet is encoded. The encoding process is applied repeatedly for each of the geometric wavelet tree nodes in each tile. The leaf node is encoded by using the bit “1.” Codes “00” and “01” are used for the one child symbol and the two children symbol, respectively. If only 1 child of W is participating in the sparse representation, then this event is encoded by using an additional bit. In case node is not a leaf node, then the indexes of the parameter of the bisecting line are encoded using the variable length coding.
G. Encoding the Coefficients of the Wavelet Polynomial
This encoding step is similar to that of the GW method. The coefficients of the wavelet polynomial are quantized and encoded using the orthonormal basis. Before the actual forest is encoded, a small header is written to the compressed file. This header contains the minimum and maximum values of the coefficients of the wavelets participating in the sparse representation. These values are used by the decoder to decode the coefficients. In addition, the header contains the minimum and maximum values of the gray levels in the image. The coefficients external values are encoded with four bytes each and image external values with 1 byte each. Due to the fact that the contribution of the root wavelets to the approximation is generally high, all of them are encoded. This is similar to the JPEG algorithm, where the DC component of the DCT transform plays the same role and is always encoded. The encoding procedure is then applied recursively for each GW tree root in each image tile.
Once the information associated with W is encoded, the recursion is applied only to the children nodes that belong to the sparse representation. The decoder reconstructs the GW forest and generates the approximation to the image.
(a)
(b)
Figure. 5 (a) Original Image (b) Reconstructed Image.
H. Rate Distortion Optimization
After the encoding step a rate distortion optimization process using SOFM is performed in order to attain the desired bit rate. Pruning iterations are applied, where at each iteration the leaf node with minimal R-D slope is pruned until the desired rateis achieved. This method is very common and has been used in the case of isotropic wavelets and in sparse geometric representation.
I. Decoding
In this step compressed bit stream is read to find whether the participating node is the leaf node, has 1 child or 2 children. If one child is participating then by using bit stream, it is found that whether it is left or right. If at least one of the children belongs to the sparse representation, then the indexes of F and c is decoded and using these index parameters Fi and cijof optimal cut are calculated. Thereafter, using this optimal cut, domain is partitioned into two sub domains; and depending upon the situation vertex set of only one child or both children is found. An orthonormal basis was used during the encoding of the coefficients of geometric wavelet. Thus, before using the decoded geometric wavelets in n-term sum, its representation in the standard basis is found. This process is repeated until entire bit stream is read.
V. EXPERIMENTAL RESULTS
Figures 5 (a and b) presents the original and reconstructed image of Lena from the GW algorithm at different bit-rates. Note that the algorithm preserves the significant edge singularities of the image, even at very low bit-rates, without the ringing artifacts that is a known phenomenon of low bit-rate isotropic wavelet coding. However, at the lower bit-rates the boundaries of the 128 x 128 tiles are visible.
Table 1 compares between the rate-distortion (PSNR)
performance of the GW algorithm and published results
Table 1 Performance Comparison of PSNR values with CR = 512:1 for LENA image.
|
BPP |
Proposed |
EZW |
SPHIT |
EBCOT |
|
0.125 |
30.75 |
27.15 |
25.51 |
22.35 |
|
0.25 |
31.25 |
28.32 |
27.87 |
25.85 |
|
0.5 |
33.68 |
30.14 |
29.14 |
27.21 |
|
0.625 |
34.18 |
31.86 |
30.24 |
29.65 |
|
1.0 |
37.47 |
34.29 |
31.54 |
30.08 |
Table .2 Comparison of various Sparse Geometric Representation algorithms
|
Bpp |
Proposed |
Prune Tree |
Prune-Join |
Bandelets |
|
0.0125 |
30.75 |
27.19 |
28.26 |
27.55 |
|
0.25 |
33.68 |
30.95 |
28.67 |
29.18 |
|
0.5 |
35.29 |
32.19 |
31.09 |
29.85 |
|
0.625 |
37.21 |
34.18 |
32.75 |
30.48 |
|
1.0 |
38.19 |
34.54 |
33.28 |
31.85 |
of several state-of-the-art wavelet-based algorithms on Lena.
Table 2 compares between the rate-distortion (PSNR) performance of the GW algorithm and other recent algorithms that are based on sparse geometric representation, the Prune-Join algorithm (Rao et al., 1994) and the Bandelets. The algorithm is very similar in nature to the GW algorithm. Both use partitions of the image over which it is approximated using low order polynomials. However, there are two main differences: the tree structure is based on dyadic cubes and anisotropic bisecting lines are used only at the leaves of the tree. Also, the underlying approximation scheme is piecewise polynomials approximation and there is no notion of -term sums or wavelets. The Bandelets algorithm applies an anisotropic multi resolution transform of the image that is based on a preprocessing step that computes the geometric flow in the image. In the Bandelets algorithm there is anunderlying partition of the image into dyadic squares, over which the geometric flow is constrained to be “unique”.
Thus the presented method produces the PSNR values that are competitive with the state-of-art coders in literature. The advantage of this method is the improvement in the PSNR values at high and medium bit rates. In the proposed algorithm the existing pruning method is replaced by the competitive learning algorithm which reports a gain of 16.54 dB over the existing method which improves the distortion rate and minimizing the cost functional.
The performance of the proposed work is compared with JPEG 2000 image compression standard that is implemented in the wavelet domain. The resulting performance measures are shown in Table 3.
Table 3 reveals that the proposed framework results in lower distortion and lower bitrates in comparison with those results obtained with JPEG 2000. Subjective testing is also undertaken to compare the quality of the reconstructed image obtained with the proposed framework and the JPEG 2000 standard. The quality of the image obtained by the proposed framework is better than the JPEG 2000 standard is illustrated in Fig. 6. JPEG 2000 does not distribute the error effectively and the certain areas of the image are not encoded with enough detail.
Table 3 Performance Comparison of the Proposed Work with JPEG 2000 Standard (JPEG, 2000).
|
S.no |
Image |
Algorithm |
MSE |
PSNR (db) |
CR |
bpp |
|
1 |
Lena |
Proposed |
183.65 |
27.51 |
36. 52 |
0.43 |
|
JPEG 2000 |
204.26 |
26.85 |
30. 14 |
0.51 |
||
|
2 |
Cameraman |
Proposed |
148.29 |
26.51 |
35. 14 |
0.45 |
|
JPEG 2000 |
155.27 |
26.27 |
27. 89 |
0.58 |
||
|
3 |
Peppers |
Proposed |
138.95 |
24.12 |
42. 68 |
0.37 |
|
JPEG 2000 |
146.27 |
24.05 |
40. 05 |
0.42 |
||
|
4 |
Lifting Body |
Proposed |
132.24 |
23.24 |
39. 17 |
0.25 |
|
JPEG 2000 |
139.54 |
22.96 |
32. 16 |
0.26 |
||
|
5 |
Pears |
Proposed |
122.65 |
20.14 |
27. 15 |
0.22 |
|
JPEG 2000 |
123.54 |
20.05 |
27. 86 |
0.20 |
(a) (b)
(c)
Figure 6. (a) Original Image (b) Reconstructed image using Proposed Work (c) Reconstructed image using JPEG 2000.
Thus the proposed method produces the PSNR values that are competitive with the state-of-art coders in literature. The advantage of this method is the improvement in the PSNR values at high and medium bit rates.
VI. DISCUSSION AND CONCLUSION
Hybrid algorithm for image compression using the geometric wavelets and the tree-structured binary space partition scheme is explored in this research. The coding efficiency of the GW algorithm is improved by using the polar coordinate form of straight line for best bisection in the partitioning procedure. A novel pruning algorithm is tried to optimize the rate distortion curve and achieve the desired bit rate. A new “geometric” context modeling scheme combined with arithmetic coding is designed to boost the performance of the algorithm. The algorithm is extremely complex in computation and has very high execution time. Sparse Partitioning is found to reduce considerably the computational complexity and in turn the time complexity of the algorithm without affecting its coding efficiency. The presented method produced PSNR values that are competitive with the state-of-art coders in literature. The algorithm works well with geometrically rich content images at low bit-rates.
REFERENCES
Alani, D., Averbuch, A. and Dekel, S. (2007) Image coding with geometric wavelets. IEEE Trans. on Image Processing. 16, 69–77.
Dekel, S. and Leviatan, D. (2005) Adaptive multivariate approximation using binary space partitions and geometric wavelets. SIAM J. Numer. Anal. 43, 707–732.
Drummond, T., Cheng, I. and Basu, A. (2013) Efficient compression of rhythmic motion using spatial segmentation and temporal blending. IEEE International Conference on Multimedia and Expo Workshops (ICMEW). 1–4.
Firouzmaneshi, A., Cheng, I. and Basu, A. (2011) Perceptually guided fast compression of 3-d motion capture data. IEEE Transactions on Multimedia. 13, 829–834.
JPEG (2000) Kakadu JPEG2000 Software V4.5 [Online]. http://www.kakadusoftware.com/
Negahdaripour, S. and Khamene, A. (2000) Motion-based compression of underwater video imagery for operations of unmanned submersible vehicles. Computer Vision and Image Understanding. 79, 162-183.
Radha, H., Vetterli, M. and Leonardi, R. (1996) Image Compression Using Binary Space Partitioning Trees. IEEE Trans. on Image Proc. 5, 1610-1624.
Rao, V., Thomas, M., Mitra, S. and Parten, M.E. (1994) Compression of high resolution images with visually transparent techniques. SPIE, Proc. on Applications of Digital Image Processing. San Diego.
Shannon, C.E. (1948) A mathematical theory of communication. Bell System Technical Journal. 27, 379-423 and 623-656.
Shukla, R., Daragotti, P.L., Do, M.N. and Vetterli, M. (2005) Rate-distortion optimized tree structured compression algorithms for piecewise polynomial images. IEEE Trans. Image Process. 14, 343–359.
Skodras, A., Christopoulos, C. and Ebrahimi, T. (2001) The JPEG2000 still image compression standard. IEEE Signal Process. Mag. 18, 36–58.
Varodayan, D., Aaron, A. and Girod, B. (2005) Rate-adaptive distributed source coding using low-density parity-check codes. Proc. Asilomar Conf. Signals, Systems and Computers. Pacific Grove, CA.
Received: May 7, 2020
Sent to Subject Editor: January 12, 2021
Accepted: December 19, 2021
Recommended by Subject Editor Jose E Guivant