Abstract
Low bit rate image coding is an important problem regarding applications such as storage on low memory devices or streaming data on the internet. The state of the art in image compression is to use 2-D wavelets. The advantages of wavelet bases lie in their multiscale nature and in their ability to sparsely represent functions that are piecewise smooth. Their main problem on the other hand, is that in 2-D wavelets are not able to deal with the natural geometry of images, i.e they cannot sparsely represent objects that are smooth away from regular submanifolds. In this paper we propose an approach based on building a sparse representation of the edge part of images in a redundant geometrically inspired library of functions, followed by suitable coding techniques. Best N-terms non-linear approximations in general dictionaries is, in most cases, a NP-hard problem and sub-optimal approaches have to be followed. In this work we use a greedy strategy, also known as Matching Pursuit to compute the expansion. The residual, that we suppose to be the smooth and texture part, is then coded using wavelets. A rate distortion optimization procedure chooses the number of functions from the redundant dictionary and the wavelet basis.
Introduction
The state of the art in image compression is based on transform coding using orthonormal basis such as DCT and Wavelets. These schemes have achieved high compression ratios thanks to the huge research work that has been performed in efficiently coding the transform coefficients and parameters. Nevertheless these traditional approaches suffer some severe limitations. Wavelets for example fail to capture regularities of contours, since they are not able to sparsely represent one-dimensional singularities of 2-D signals [1] . Recently a lot of research effort was aimed at representing a natural image exploiting its inherent geometrical structure. Concerning image compression, interesting approaches that follow this idea can be found for example in [2] , [3] and [4] .
Introduction
In this work we aim at obtaining an efficient encoding by approximating the edges of an image by a sum of two-dimensional, non-separable functions. The residual, that we suppose constituted by the smooth part of the image and textures, is then coded via wavelets. The edge-oriented dictionary is built by anisotropically scaling, orienting and bending a generating function, resulting in an overcomplete basis set. Highly non-linear approximation in redundant dictionaries is, in general, a NP-hard problem. However this does not impair the possibility of finding good sparse representations in particular classes of dictionaries. There are different approaches that find a sub-optimal solution to this problem like Basis Pursuit [5] (BP), Orthogonal Matching Pursuit [6] (OMP) and Matching Pursuit [7] (MP). In this paper we use a technique based on the greedy Matching Pursuit algorithm that in general is not sparsenesspreserving [8] . However experimental results showed its ability to give highly sparse decompositions of 1-D signals [9] , images [10, 11] and videos [12, 13] . Moreover very recent theoretical results prove that, under certain conditions, MP iteratively selects the atoms that give the sparsest representation. This recovery condition is based on the quasi-incoherence of the dictionary and the sparseness of the signal [14] [15] [16] . Combining the MP approximation properties with an accurate design of the dictionary makes it possible to achieve high compression ratios, catching the most visually relevant structures of natural images. Since at very low bit rate these structures mainly consist of object contours, we designed a dictionary that can represent edges working on the output of a Laplacian pyramid. The low-frequency part and textures are coded using a simple wavelet coder. The balance between the functions approximating the contours and wavelet coefficients is performed in a rate distortion sense. Numerical and visual comparisons with the state of the art show the quality of the results; in particular ringing artifacts typical of wavelets are avoided. This paper is organized as follows: Section 2 explains the adopted coding scheme composed by a high pass filtering that gives a detail version of an image, a greedy decomposition for the high frequencies and a wavelet based coding of the residual. Section 3 recalls the basic principles of the Matching Pursuit algorithm, while the dictionary design and the atom selection method are illustrated in Section 4 and 5 respectively. Section 6 presents a rate distortion study of our representation method and Section 7 shows results and comparisons. Finally, conclusions can be found in Section 8.
Representation Method
Natural images present different primitives with peculiar characteristics. We can easily distinguish smooth parts (low frequency components, I smooth ), edges (I edge ) and textures (I texture ). Formally, we propose here the following model for an image I:
Representation Method
I I smooth + I edge + I texture .
Representation Method
(1) According to this model, we describe here a compression scheme that codes each of the primitives of Eq. 1 with a different technique. Such a scheme is presented in Fig. 1 .
Representation Method
The dictionary, described in Section 4, has been designed to match the object contours. These discontinuities have most of their energy at high frequencies. Therefore, before coding the edges, the image is decomposed with wavelets and reconstructed keeping all the sub-bands but the low-pass. This step is equivalent to a high-pass filtering and it is labeled as "W HP" in Fig 1. The high frequency content of the signal is thus decomposed over the edge-oriented dictionary using the Matching Pursuit algorithm. After that the MP projection coefficients have been quantized, a residual image is computed by subtracting the quantized MP reconstruction from the original input image. This residual contain the low frequencies of the signal, the textures and the artifacts introduced by MP (the latter also include quantization errors). As can be seen in Fig. 1 the residual is decomposed with wavelets. The wavelet functions, used for both decomposing the residual and computing the HP input for MP, are the Cohen-Daubechies-Feauveau 9,7 [17] . At this point we have low pass wavelet coefficients (projection on the scaling function) representing I smooth , atoms from the edge-oriented dictionary representing I edge and the high frequency wavelet coefficients representing I texture and correcting the MP artifacts, if any. Note that the quantization of the MP indexes and projections is fixed. The coefficients of the coarse version representing the smooth part of the image are quantized in a differential way (DPCM), while the wavelet coefficients are subject to a dead-zone quantization with the dead-zone step twice the quantization step. The quantization steps for the coarse signal and wavelet coefficients are independent.
Representation Method
All these parameters are subject to a Rate-Distortion (RD) optimization that establishes the number of atoms to code, the quantization step for the DPCM of the coarse version and the step for the wavelet dead-zone quantization. All the parameters and the quantized coefficients are entropy coded using an adaptive arithmetic coding algorithm. 
Matching Pursuit Algorithm
In this section we recall the basics of the iterative process used for the selection of waveforms that represent the signal structures. A more detailed explanation of the Matching Pursuit algorithm can be found in [7] . Let D = {g γ } γ∈Γ be a dictionary of unit norm vectors g γ called atoms, where Γ is the set of possible indexes. The function f is first decomposed as follows:
Matching Pursuit Algorithm
where Rf is the residual component after having approximated f in the direction of g γ 0 . Since Rf and g γ 0 are orthogonal, it follows that
Matching Pursuit Algorithm
To minimize Rf we must choose g γ 0 such that the absolute value of the projection | g γ 0 , f | is maximal. Applying iteratively such a procedure, after N iterations we obtain:
Matching Pursuit Algorithm
where R 0 f = f and R n f is the residual after the n th step; it can be proved [18] that R n f converges to zero when n tends to infinity. The convergence is exponential in the case of finete dimensional signal spaces. Following (3) we can write:
Matching Pursuit Algorithm
Equation (5) expresses the energy conservation of the MP. The convergence of MP depends on the structure of the dictionary, the search strategy and the signal f that has to be approximated. In [18] it is shown that there exist two real numbers α, β ∈]0, 1] such that for all n ≥ 0 the following relation is valid:
Matching Pursuit Algorithm
where α is an optimality factor related to the strategy adopted to select the best atom in the dictionary, while β depends on the dictionary, representing its ability to capture the features of the input function f [19] . Equation (6) gives a simple upper bound of the decay of the approximation error.
The Dictionary
The dictionary used to represent the detail version of the image is composed of a set of functions, named atoms, built by applying the following four types of transformation to the generating function φ( x) :
The Dictionary
a) Translation T b , to move the atom all over the image:
The Dictionary
b) Rotation R θ , to locally orient the atom along contours:
The Dictionary
where r θ is a rotation matrix
The Dictionary
c) Since, in general, images not only contain straight edges, we are adapting the atoms to the shape of natural contours with a bending transformation B r . Roughly speaking, this operation arches the x 2 -axis with radius r, formally B r φ( x) = φ (β r ( x)). Figure 2 shows how the β r (·) operation acts, and Figure  4 shows the result of bending a generating function. The transformation
is not linear and it is defined as
arctan(
is not linear and it is defined as
Applying the bending to a continuous function φ( x) we obtain B r φ( x), which is in general discontinuous on the semi-axis [r, +∞). When φ( x) is continuous and satisfies the conditions
is not linear and it is defined as
it follows that B r φ( x) is continuous for all x ∈ IR 2 . The definition of the bending transformation is driven by the desire to keep the wavelet like behavior of the generating function (see Subsection 4.1) perfectly orthogonal to the smooth direction of edges.
is not linear and it is defined as
In practice the bending transformation does not introduce discontinuities in the atoms, since the generating functions are close to zero for x 1 = r. d) Anisotropic scaling S a 1 ,a 2 , to adapt to contour smoothness
is not linear and it is defined as
Atoms are generated varying the parameters b, θ, r, a of the four previous transforms in the following order:
is not linear and it is defined as
Finally the waveforms obtained are normalized:
is not linear and it is defined as
The dictionary used by the MP-algorithm can be written as in equation (15), where all the parameters are discretized:
is not linear and it is defined as
The radius r is discretized using a dyadic grid, while for the position b a uniform grid is kept. The two scaling factors are discretized in a uniform way; the range of the scaling factor along x 2 is bigger than the one along x 1 and depends on the radius parameter (it can not exceed π 2
is not linear and it is defined as
times the radius). The rotation step θ is inversely proportional to the scale a 2 .
Generating functions
The choice of the generating function φ(x 1 , x 2 ) is driven by the idea of efficiently approximating the high frequencies of contours, like singularities in 2-D. Therefore, the atom must be a smooth low resolution function in the direction of the contour and approximate the edge transition in the orthogonal (singular) direction.
Generating functions
In order to be able to well represent either roof and ramp edges [20] we adopted two different generating functions, doubling in this way the size of the dictionary.
Generating functions
The first function, called φ 1 ( x) is a combination of a generalized Gaussian and its first derivative. In the x 1 -direction (which is the singular-direction) it is the first derivative of a Gaussian, while in the x 2 -direction (which is the contour-direction) it is a generalized Gaussian, see Fig. 3 :
Generating functions
The second generating function φ 2 ( x), shown in Fig. 3 , is a combination of a Gaussian and its second derivative. It is a slight variation of the function introduced in [21] ; this choice is motivated by the optimal joint spatial and frequency localization of the gaussian kernel:
Generating functions
We chose the shape parameter of the generalized gaussian equal to four in the x 2 -direction in order to have a faster decay in the space domain. It turns out that atoms can better approximate segments of edges and visual artifacts are reduced. Figure 4 shows three atoms generated using the two different generating functions in both space and frequency domain. The bending transformation is also shown. It can be seen that the function φ 2 is more compact in the frequency domain, whereas φ 1 reaches lower frequencies.
Generating functions
It is worth mentioning that the atoms we generate are similar to the basis functions obtained by Olshausen and Field while studying the spatial receptive fields of simple cells in mammalian striate cortex [22] . These functions, as well as our atoms, are characterized by being localized in space, oriented and bandpass. An additional property of the overcomplete dictionary we propose is given by the possibility of bending the generating function. This characteristic does not appear in the functions obtained by Olshausen and Field. This can be explained by considering that the image patches they were analyzing are too small to observe such a phenomenon.
Size of the Dictionary
Taking into account all the atom parameters and the two generating functions, the dictionary can be written as: Here φ ∈ {φ 1 , φ 2 } is the index that specifies which function has been chosen to create the atom, while the other values are the same as in equation (15). Finally we obtain a highly redundant dictionary, with a redundancy factor d 17000.
Size of the Dictionary
The size of the dictionary increases dramatically allowing big scaling factor along x 2 , indeed the number of rotations is proportional to the scale parameter a 2 . A dictionary including elongate atoms is able to better represents long edge structures. In fact we can say that designing high redundant dictionaries, we are trying to increase the β parameter of equation (6).
Size of the Dictionary
Even if big dictionaries can be built with a small coherence [23] , our dictionary has high coherence since we adopt a geometric oriented design. Thus, we can not assure that MP recovers the best sparse approximation of the signal [14] . Nevertheless we notice a fast energy decay of the residual at first iterations, which means that the dictionary copes well with natural data. MP is able to select good atoms, at least during first iterations.
Searching Algorithm
Matching Pursuit is used to decompose the detail version of the image in its most important features. This greedy algorithm selects at each iteration an atom from the dictionary such that the projection coefficient | g γn , R n f | is maximum. To find such g γn we use a full search algorithm that computes the inner products between the residual and all the functions of the dictionary. Since the dictionary is composed of all the translations of the transformed generating functions (TGF), see Eq. (13), it is clear that all the inner products between the TGF translated all over the residual and the residual itself, correspond to the convolution of the TGF with the residual. To speed up the search, we compute the convolutions like products in the frequency domain. The Fourier transform of all the TGF is computed only once and stored.
Searching Algorithm
The complexity of a MP decomposition of a signal of n samples results to be of the order of
Searching Algorithm
where N is the number of chosen atoms, the constant C depends on the strategy adopted for atom selection and d depends on the size of the dictionary. In fact, d = |D|/n is the redundancy of the dictionary and it corresponds to the size of D without considering translations. In particular we use a modified Matching Pursuit algorithm for which C 1. At each iteration, n k − n k−1 atoms are selected and used to decompose the residual. Like in Eq. (4) we can write:
Searching Algorithm
with n 0 = 0 and n K = N . At the k th iteration all the atoms of the dictionary are sorted according to the absolute values of the projection coefficients. Afterwords, starting from the one with highest projection, all the atoms that are quasi-orthogonal are selected. We adopted this algorithm in order to obtain an important reduction in computational load. In fact selecting on average n k atoms at once it turns out that MP only needs N/n k iterations, reducing in this way the number of inner products which constitute the most computationally demanding part of the algorithm. For example, decomposing images of size 256 × 256 pixels we observed a speed-up of around 20. The drawback of this method is that there is no more a guaranty that at each iteration the best atom will be selected as in the case of the full search MP. However the resulting loss in image quality is negligible [10] .
Searching Algorithm
This method is similar to the fast MP implementation described by Mallat [18] . When you control the structure of the dictionary, you can update the projection of the atoms on the residual at the next step taking into account the correlation between atoms, according the following updating formula:
Searching Algorithm
In particular the projection of the atoms orthogonal to the selected ones will not change.
Searching Algorithm
In order to further speed up the atom selection, another algorithm, based on a tree-based pursuit decomposition, may be taken into account [24] . But since the quality loss is not negligible, especially at the range of bit rate that we are interesting in, we decided not to use this searching method.
Rate Distortion
As described in Section 2 , the number of atoms to code and the quantization step for the wavelet coefficients are chosen based on a Rate-Distortion optimization. In order to study the RD of our representation method, we take into account the image model (1) proposed in Section 2.
Rate Distortion
We indicate withĨ edge (m) the m-terms approximation of the edge part of the image obtained by the MP decomposition of I edge over the contour oriented dictionary. Thereby the input of the wavelet decomposition (I st ), supposed to contain the smooth and texture part, is obtained by subtractingĨ edge from the original image:
Rate Distortion
SinceĨ edge (m) is the superposition of m atoms with quantized projections, the final error is given by
Rate Distortion
whereĨ st (m, ∆) is the approximation of I st (m) given by the quantization of the wavelet coefficients. Let R M P the rate due to the atoms and R W the one due to the wavelet coefficients, the total rate is R = R M P + R W . It depends on the number of atoms used to approximate I edge and on the quantization steps of the wavelet coefficients. Before investigating the Rate-Distortion of our representation method, we study the rate related to the MP expansion, and we recall the RD theory concerning wavelet coding.
MP rate
Our signal approximation over D is represented by the atom indexes, positions and projections. The indexes or parameters that characterize the atoms shape are entropy coded using an adaptive arithmetic coding algorithm. Since the x 2 -scale parameter depends on the radius, the arithmetic coder uses the conditional probability p(x 2 -scale|radius) to code the x 2 -scale, and p(rotation|x 2 -scale) for the rotation parameter. In order to code the positions and projection coefficients, two different approaches can be taken into account. The first one consists of ordering the atoms in decreasing absolute projection values, then the projections can be quantized either in a differential way (DPCM) [10] or using an exponential quantizer [25] . The quantization is followed by arithmetic coding. The x 1 and x 2 coordinates of the atoms positions are then simply stored without any particular coding scheme.
MP rate
The second approach performs a different sorting of the atoms in such a way to take advantage in coding their positions [12] . The atoms are ordered by raster scanning, then the x 1 and x 2 coordinates are coded in a differential way followed by arithmetic coding. The drawback is that the SNR scalability is lost [11] . In this case a simple uniform quantization and arithmetic coding of the projections is performed.
MP rate
As shown on the left-hand side of Figure 5 , the position oriented coding method outperforms the projection coding, thus we chose to use the former to code atoms positions and projections. Finally the right-hand side of Figure 5 gives the total bit rate per atom R a (m) as a function of the number of atoms used to approximate the edge component I edge . The exponential decay of R a (m) is due to the fact that increasing m, the grid representing the atoms positions becomes more dense and the entropy of the displacements between adjacent atoms decreaseS. At the limit we can say that the bits required to code an atom get close to the coding rate of the projection and shape parameters.
Wavelet rate distortion
The wavelet functions, used to decompose the residual (22) , are the CohenDaubechies-Feauveau 9,7 with normalization ( √ 2, √ 2). This biorthogonal wavelet basis is nearly orthogonal and thus we suppose that the distortion given by the quantization in the wavelet domain coincides with the distortion in the original domain. In order to have an hint on the real rate-distortion behavior, let us make the hypothesis of high resolution quantization, although it is not always satisfied in the compression domain. Using a uniform quantizer, we can approximate the distortion or MSE as a function of the quantization step ∆:
Wavelet rate distortion
The rate, that corresponds to the entropy of the output indexes, depends on the quantization step and on the differential entropy
Wavelet rate distortion
where h k is the differential entropy, N k is the number of wavelet coefficients at resolution k and N is the size of the signal.
MP+Wavelet rate distortion
Now we can formulate the Rate-Distortion of our coder based on MP and wavelet decomposition. The final distortion depends on the quantization step of the wavelet coefficients, and for fine quantization we have that
MP+Wavelet rate distortion
. The total rate R = R M P (m)+R W (m, ∆) depends on the number of atoms approximating I edge and obviously on the quantization step ∆,
MP+Wavelet rate distortion
It is important to notice that the differential entropy h k (m) associated to wavelet resolution level k, depends on the number of atoms that represent I edge (m). Indeed the statistic of I st (m) = I −Ĩ edge (m) changes with m, especially at the resolution levels that contain the energy of the edge structures. The left-hand side of Figure 6 shows how the differential entropy depends on m. We thus write the Lagrangian cost
MP+Wavelet rate distortion
where R bpp is the bit budget per pixel.
MP+Wavelet rate distortion
Differentiating with respect to ∆ and m (we neglect the integer constrain on m), we obtain 
MP+Wavelet rate distortion
and setting the derivative to 0 we obtain
MP+Wavelet rate distortion
and
MP+Wavelet rate distortion
Solving equation (32) we find the optimal number of atoms that minimizes the rate for a given distortion. It is important to notice that the solution of (32) does not depend on the final distortion D. This is due to the assumption of fine quantization of the wavelet coefficients. Once we get the optimal number of atoms m opt , setting to zero the derivative of equation (28) with respect to λ, we obtain the quantization step as a function of the bit budget,
MP+Wavelet rate distortion
Remark that this is true only at hight bit rate, and that the functions R a (m) and h k (m) have to be estimated. Figure 6 shows on the left-hand side the behavior of the differential entropy at different resolution levels, and on the right-hand side shows the total rate as a function of m for a fixed step ∆ (changing ∆ corresponds to a vertical translation of the wavelet rate). The minimum rate is reached coding m opt atoms: for studied example this minimum occurs between 100 and 150 atoms.
MP+Wavelet rate distortion
In practice, at low bit rates the fine quantization hypothesis is not satisfied and the simple model for the wavelet RD does not fit its real behavior. Moreover, we are using a dead zone uniform quantizer, which improves the rate distortion at low bit rate quantization [26] , and different steps of quantization for the coarse and wavelet coefficients can be chosen. Implementing a numerical rate distortion optimization, it turns out that the optimal number of atoms changes depending on the bit rate. All the graphics in this section show the mean of the results obtained using the three standard images Lena, cameraman and peppers of size 256 × 256.
Results
This section provides some results obtained with our algorithm; in the following it will be simply called MPW. A comparison is made with the standard JPEG2000 [27, 28] . Another point of comparison is a pure wavelet encoder that uses exactly the same coding options and RD optimization we adopted in the MPW coding scheme. In the following, we refer to the latter method as "Wavelets". Table 1 shows the PSNR vs. bit-rate results for the images peppers and cameraman. Both images have size 256 × 256 pixels. For this size, the computational time for MPW coding is around one hour, using a 2GHz processor. At very low bit rate, our algorithm obtains good results because it is capable of catching the main features of a natural image with few functions. It is fair to observe that at less than 0.1 bpp the gap between JPEG2000 and MPW is also partly due to the bigger size of the JPEG2000 header: in fact one can notice that even our very simple "Wavelet" encoder outperforms the standard. The size of the JPG2000 header is 148 Byte, meanwhile MPW has a simple header of size 22 Byte. Regarding JPEG2000, if we take into account only the bit stream due to the quantized wavelets coefficients, we observe an increase of about 0.6 dB, 0.4 dB and 0.2 dB barbaramartin@example.org bpp, 0.2 bpp and 0.3 bpp. This difference disappears for bigger images (e.g. 512×512 pixels). In [10] we obtained similar (but slightly worse in terms of PSNR) results with a less elaborated approach also based on Matching Pursuit. However, thanks to the use of the wavelets for coding the residual (see Sec. 2), the gain we obtain here is not only limited at very low bit rates. Moreover, observing Figure 7 , one can see that the proposed scheme outperforms JPEG2000 not only in terms of PSNR but also of visual quality. We compare results up to 0.5 bpp, where there is no relevant visual difference between the images compressed with our method and JPEG2000.
Results
Other numerical results can be found in [29, 30] . In particular we compress bigger images and we show an example of how the PSNR decreases using a less redundant dictionary. 
Conclusions
In this paper we introduced a technique for coding natural images at low bit rates. The edges are approximated using elementary waveforms from a redundant dictionary, while the non-edge part of the image is represented by wavelets. The geometry inspired dictionary is build by applying anisotropic scaling, rotation and bending transformations to two generating functions which are smooth on the edge direction and wavelet like in the other. In order to overcome the combinatorial complexity in finding the sparsest approximation over a redundant dictionary, we use a pursuit algorithm based on MP. A rate distortion analysis, together with numerical entropy estimations, controls the number of edge-oriented atoms and the quantization of wavelets.
Conclusions
This coding scheme easily allows SNR scalability. Starting from a base layer given by the atoms representing contours, SNR enhancements can be obtained applying usual scalability properties of wavelet encoders [27] .
Conclusions
Our coder outperforms the state of the art in terms of both PSNR and visual quality. In particular edges, which at very low bit rate constitute the more visually relevant features of an image, are no more affected by ringing artifacts typical of wavelets.

{'paper_id': '2153218', 'title': 'Image compression using an edge adapted redundant dictionary and wavelets', 's2_url': 'https://api.semanticscholar.org/CorpusID:2153218', 'source': 'S2ORC'}