Prof Frédéric Marco Dufaux

Prof Cagnazzo

Anissa

Dr Ricardo Carmona-Galán

Résumé

La modélisation des signaux peut être vue comme la pierre angulaire de la méthodologie contemporaine de traitement du signal et de l'image. La modélisation parcimonieuse permets la représentation des signaux en termes de combinaisons linéaires d'un ensemble sousjacent, appelé dictionnaire, de signaux élémentaires connus sous le nom d'atomes. La force motrice de ce modèle est la rareté des coefficients de représentation, c'est-à-dire la décroissance rapide des coefficients de représentation sur le dictionnaire. L'objectif principal de cette thèse est de fournir de nouvelles applications pour cette méthode de modélisation du signal en abordant plusieurs problèmes sous différents angles. On se concentre sur une autre application importante de la modélisation parcimonieuse des signaux, à savoir la résolution des problèmes inverses, notamment la compensation des erreurs, la reconstruction des images incomplètes et la reconstruction des images compresses à partir d'un nombre limité de mesures aléatoires. La modélisation du signal est généralement utilisée comme une connaissance préalable du signal pour résoudre ces problèmes NP-difficiles. Puis, Il commence par l'application directe de la représentation éparse, c'est-à-dire a la compression d'image.

Un nouveau codec image basé sur la représentation éparse adaptative sur un dictionnaire formé est proposé, dans lesquels différents niveaux de densité sont assignés aux correctifs d'image appartenant aux régions saillantes. Dans cette thèse, ces défis sont transférés dans des cadres distincts d'acquisition comprimée et plusieurs méthodes de reconstruction sont proposées.

i Abstract Signal models are a cornerstone of contemporary signal and image processing methodology.

In this , two particular signal modeling methods, called analysis and synthesis sparse representation, are studied which have been proven to be effective for many signals, such as natural images, and successfully used in a wide range of applications. Both models represent signals in terms of linear combinations of an underlying set, called dictionary, of elementary signals known as atoms. The driving force behind both models is sparsity of the representation coefficients, i.e. the rapid decay of the representation coefficients over the dictionary. On the other hands, the dictionary choice determines the success of the entire model. According to these two signal models, there have been two main disciplines of dictionary designing; harmonic analysis approach and machine learning methodology.

The former leads to designing the dictionaries with easy and fast implementation, while the latter provides a simple and expressive structure for designing adaptable and efficient dictionaries.

The main goal of this thesis is to provide new applications to these signal modeling methods by addressing several problems from various perspectives. It begins with the an important application of the sparse signal modeling, i.e. solving inverse problems, especially for error concealment (EC), wherein a corrupted image is reconstructed from the incomplete data, and Compressed Sensing recover, where an image is reconstructed from a limited number of random measurements. Signal modeling is usually used as a prior knowledge about the signal to solve these NP-hard problems. In this thesis, inspired by the analysis and synthesis sparse models, these challenges are transferred into two distinct sparse recovery frameworks and several recovery methods are proposed. Compared with the state-of-the-art EC and CS algorithms, experimental results show that the proposed methods show better reconstruction performance in terms of objective and subjective evaluations. This thesis is finalized by giving some conclusions and introducing some lines for future works.

In the end part of thesis, it focuses on direct application of the sparse representation, i.e. image compression. The line of research followed in this area is the synthesis-based sparse iii representation approach in the sense that the dictionary is not fixed and predefined, but learned from training data and adapted to data, yielding a more compact representation.

A new Image codec based on adaptive sparse representation over a trained dictionary is proposed, wherein different sparsity levels are assigned to the image patches belonging to the salient regions, being more conspicuous to the human visual system. Experimental results show that the proposed method outperforms the existing image coding standards, such as JPEG and JPEG2000, which use an analytic dictionary, as well as the state-ofthe-art codecs based on the trained dictionaries.

Chapter 1 Introduction

Signal models are fundamental tools for efficiently processing of the signals of interesting, including audio recordings, natural images, video clips, and medical scans, to name just a few. A signal model formulates a mathematical description of the family of signals of interesting in a way which faithfully captures their behavior. Designing accurate signal models, which efficiently capture useful characteristics of the signals, has been a crucial aim in the signal processing area for so many years and a variety of mathematical forms has been proposed by now [START_REF] Mairal | Sparse modeling for image and vision processing[END_REF]. One of the simplest and most common forms is that the signals are coming from some priori probability distribution assumed on the signal space [START_REF] Elad | Analysis versus synthesis in signal priors[END_REF][START_REF] Elad | Analysis versus synthesis in signal priors[END_REF]. While this representation is mostly useful when employing statistical signal processing methods, many practical signals cannot be directly associated to a probabilistic distribution.

Sparsity-based modeling has been used in many applications in which each signal is represented in terms of linear combinations of an underlying set, called dictionary, of elementary signals known as atoms, resulting in simple and compact models. The driving force behind this model is sparsity, i.e. the rapid decay of the representation coefficients over the dictionary. In this signal modeling, the dictionary plays an important role for the success of entire model in an efficient representation of the signal.

Finding appropriate dictionaries with good predictive power of various signal classes of interest and high compactness ability, especially natural images, has been an active field of research during past decades. The early attempts for designing dictionaries were based on building the model using harmonic analysis of the signal classes and extracting some mathematical functions, resulting in a fixed off-the-shelf dictionary called analytic or mathematical dictionary. The sparse representation using these fixed mathematical dictionaries is called analysis sparse modeling. The long series of works on designing the analytic dictionaries lead to appearing various transforms such as Fourier and its discrete version, discrete cosine [START_REF] Ahmed | Discrete cosine transform[END_REF], wavelets [START_REF] Mallat | A Wavelet tour of signal processing[END_REF], curvelets [START_REF] Candés | Fast discrete curvelet transforms[END_REF], contourlets [START_REF] Do | Contourlets: a new directional multiresolution image representation[END_REF], bandlets [START_REF] Pennec | Sparse geometric image representations with bandelets[END_REF][START_REF] Pennec | Bandelet image approximation and compression[END_REF], and Chapter 1. Introduction steerable wavelets [START_REF] Simoncelli | Shiftable multiscale transforms[END_REF].

A significantly different approach to the sparse modeling, originally introduced by Olshausen and Field [START_REF] Olshausen | Sparse coding with an overcomplete basis set: a strategy employed by v1?[END_REF], consists of learning a dictionary from some training data. The sparse representation using this trained dictionary is called, synthesis sparse modeling.

The trained dictionaries, also called synthetic dictionary, could efficiently capture the underlying structures in the natural image patches and are well adapted to a large class of natural signals.

A straightforward application of the sparse signal modeling in the field of image processing has been image compression due to providing a compact representation of the signal.

Another important success of the sparse signal modeling has been its ability for solving the inverse problems such as denoising, reconstruction from incomplete data, or more generally restoration problems. The restoration problems are indeed often difficult to solve without a priori knowledge of the data source. The sparse signal modeling provides a strong tool for a priori model of the data source. The sparse signal modeling based on the predefined mathematical (analytic) dictionaries has led to the design effective algorithms for many image processing applications, such as compression [START_REF] Mallat | A Wavelet tour of signal processing[END_REF][START_REF] Pennec | Bandelet image approximation and compression[END_REF][START_REF] Vergara | Edging out the competition: Lossy image coding with wavelets and contourlets[END_REF][START_REF] Wang | Iterative image coding with overcomplete curvelet transform[END_REF][14], denoising [15][START_REF] Blomgren | Color TV: total variation methods for restoration of vector-valued images[END_REF][START_REF] Starck | The curvelet transform for image denoising[END_REF][START_REF] Portilla | Image denoising using scale mixtures of gaussians in the wavelet domain[END_REF][START_REF] Matalon | Improved denoising of images using modelling of a redundant contourlet transform[END_REF][START_REF] Eslami | Translation-invariant contourlet transform and its application to image denoising[END_REF], superresolution [START_REF] Farsiu | Fast and robust multiframe super resolution[END_REF][START_REF] Li | Multiframe super-resolution reconstruction using sparse directional regularization[END_REF], inpainting [START_REF] Elad | On the role of sparse and redundant representations in image processing[END_REF][START_REF] He | Iterative support detection-based split bregman method for wavelet frame-based image inpainting[END_REF], and compressed sensing reconstruction [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF], and more. Furthermore, the idea of learning a synthetic dictionary, instead of using a predefined one, has been successfully applied in numerous applications in many fields, notably in image processing and computer vision, such as image compression [START_REF] Gurumoorthy | A method for compact image representation using sparse matrix and tensor projections onto exemplar orthonormal bases[END_REF][START_REF] Mazaheri | Learning a tree-structured dictionary for efficient image representation with adaptive sparse coding[END_REF][START_REF] Sun | Dictionary learning for image coding based on multisample sparse representation[END_REF], denoising [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF][START_REF] Mairal | Sparse representation for color image restoration[END_REF], super-resolution [START_REF] Yang | Image super-resolution via sparse representation[END_REF], inpainting [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF], and compressed sensing reconstruction [START_REF] Zhang | Image compressive sensing recovery via collaborative sparsity[END_REF], debluring [START_REF] Dong | Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization[END_REF], to name just a few.

Main Objectives of the Thesis

This thesis presents the theoretical and practical aspects of the dictionary-based sparse signal modeling. The theoretical aspects include addressing the analysis and the synthesis sparse signal modeling and their relationship. The practical aspects consider several stateof-the-art applications of the analysis and synthesis sparse signal modeling. We address several questions relating to some important applications of the sparse modeling: How to efficiently represent an image over a trained dictionary in order to improve the performance of the image compression? How can the sparse modeling be employed for solving the inverse problems? The first problem is error concealment (EC) application, where groups of adjacent pixels in the image are lost, and second problem is Compressed Sensing (CS) reconstruction, where an image is reconstructed from a few number of random measurements. We try to answer these questions using different tools from convex and non-convex optimization techniques and some image processing methods.

For the CS reconstruction problem, we consider different concepts to improve the recovery quality. First, inspired by the fact that the visually salient regions of the image are more conspicuous to the human visual system, an adaptive CS method is presented, which provides a higher recovered image quality with respect to the existing algorithms. The analysis sparse signal modeling is used to reconstruct the image form the random measurements. Then, we extend the concept of prediction and residual reconstruction to the image CS recovery. A prediction is produced to create a measurement-domain residual of the image to be recovered. Considering the local strong correlation, local sparsity, and nonlocal similarities among the image patches within an image, several methods for generation of the prediction are proposed. Specifically, a prediction of the image is estimated using synthesis sparse representation technique via a trained over-complete dictionary which models the image patches as a linear combination of very few number of atoms chosen from an overcomplete dictionary. We show that using the synthesis sparse signal modeling for generation of the prediction leads to a significant improvement of the quality of the reconstructed image. Finally, objective experimental results are given for each algorithm in terms of peak-signal to noise ratio (PSNR) and the significant gains of the presented CS recovery methods are compared to the state-of-the-art algorithms.

We then address the EC problem by casting the inverse problem as a sparse recovery problem. First, we show that the dictionary learning-based synthesis sparse modeling can be useful for predicting the missing visual information, leading to the state-of-the-art results for the image EC. Specifically, joint sparse representation (JSR) model, which has recently emerged as a powerful technique with wide variety of applications, is extended to the EC application, being effective to recover a high quality image from a corrupted input. This model is based on jointly learning a dictionary pair and two mapping matrices In the next work, being related to the EC problem, the analysis sparse signal modeling via a mathematical dictionary (wavelet basis) is employed to achieve the analysis sparse recovery and reconstruct the missing information. The proposed approach is motivated by the recent results in the sparse recovery theory, which suggest that, under mild conditions, the sparse signal can be recovered from its far fewer measurements. For this purpose, a robust encoder is carefully designed in order to mitigate the negative effects of the packet loss. At the receiver side, the sparse structure of the wavelet coefficients is explicitly exploited in order to model the error recovery problem as a sparse recovery framework.

We show that both the proposed analysis and synthesis based sparse recovery approaches achieve the state-of-the-art results for the image EC and compete with existing algorithms.

The last, but not least, contribution of this thesis is addressing an adaptive sparse representation with respect to a trained dictionary in order to efficiently compress the images. Based on this representation, different sparsity levels are assigned to the image patches belonging to the salient regions of the image that are more conspicuous to the human visual system. Experimental results show that the proposed method outperforms the existing image coding standards, such as JPEG and JPEG2000, which use an analytic dictionary, as well as the state-of-the-art codecs based on the trained dictionaries.

Thesis Outline

The remainder of thesis is organized as follows: The first part of Chapter 2 starts with the concept of sparsity in signal processing. The use of sparse representation modeling with respect to over-complete mathematical and trained dictionaries is presented. Next, several formulations for the sparse representation using over-complete dictionaries are presented, which have been extensively used during the past two decades. This part is concluded with a brief description of a well-known and yet effective dictionary learning algorithm, introduced by Elad and Aharon [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF]. The end of Chapter 2 is devoted to the inverse problem formulation that has received a large attention in recent years.

With all these formulations in hand, the four additional Chapters in this thesis document our recent works on using the sparse modeling for different applications. In Chapter 3, the concept of CS in the image processing is introduced and a brief description of a well-known and yet effective CS reconstruction algorithm, called block-based CS with 1.2. Thesis Outline smoothed-projected Landweber reconstruction (BCS-SPL), is presented. In the next part of this chapter, several methods for the prediction generation are discussed. First, considering the strong correlation among the neighboring areas within an image, we present an image CS recovery by providing an intra-image prediction. Further, the local sparsity and nonlocal similarities among the image patches are implicitly exploited to generate an optimal prediction, improving the performance of the image CS recovery. Finally, at the end part of chapter, objective experimental results are given for each algorithm and the significant gains of the presented CS recovery methods are compared to the BCS-SPL algorithm.

In Chapter 4, a receiver-based image error concealment algorithm, inspired by the synthesis sparse representation model, is proposed using the overcomplete trained dictionaries.

In this thesis, the JSR model is extended to the EC application, being effective to recover a high quality image from a corrupted input. In order to improve the accuracy and stability of the proposed JSR-based EC algorithm and avoid unexpected artifacts, the local and nonlocal priors are seamlessly integrated into the JSR model and an improved EC algorithm is given. The objective and subjective evaluations, compared with the state-of-the-art EC algorithms, are reported at the end of chapter.

In Chapter 5, another error recovery algorithm is proposed in which a high quality image is guaranteed, even at the high loss scenarios, at the expense of a simple modification at the transmitter. Different from the receiver-based EC algorithm, proposed in Chapter 4, wherein the synthesis signal modeling has been done at the receiver side, the proposed scheme benefits from implicitly mathematical modeling of the EC scheme as an analysis sparse recovery framework at the receiver. Furthermore, the recovery stability and upper bound for the expected distortion are considered in this chapter. At the end of chapter, an experimental framework is described wherein the proposed EC method is validated for several transmission scenarios.

We discuss the use of sparse signal modeling for discovering the underlying structure of natural image patches, being useful for image compression, image EC, and image CS reconstruction. A straightforward application of the sparse signal modeling is discussed in Chapter 6, where a generic image compression scheme is developed and implemented, based entirely on adaptive sparse representation. The rate-distortion analysis of the proposed method compared with the conventional image coding standards, such as JPEG and JPEG2000, which use an analytic dictionary, and the state-of-the-art codecs based on a trained dictionary is also reported.

Finally, Chapter 7 concludes the thesis and provides some seeds for future research.

Chapter 2

Sparsity-Based Signal Models

Abstract

In recent years, a large amount of multi-disciplinary research has been conducted on sparse models and their applications. In signal processing, sparse coding consists of representing data with linear combinations of a few dictionary elements. In this chapter, a review of sparse modeling and its applications to image processing is given. First, a historical view of sparse representation and two well-known techniques of sparse signal modeling are introduced. Then, a dictionary learning formulation, which is a key component of most applications presented later in this , is introduced. A brief description of a well-known and yet effective dictionary learning algorithm, called K-SVD, is also presented. Finally, the chapter is concluded with some theoretical aspects, such as the concept of inverse problem and sparse recovery that has attracted much attention in recent years.

Introduction

One of the well-known methods in designing of the signal models is linear approximation.

In this modeling technique, given a set of vectors

[d k ∈ R N ] K-1 k=0 , a signal x ∈ R N is represented as a linear combination of K basis, x K-1 k=0 c k d k , (2.1)
where set [c k ] K-1 k=0 consists of representation coefficients. The signal approximation (2.1) can be reformulated in a matrix form as

x Dc, (2.2)
where c = [c 1 , c 2 , • • • c k ] T ∈ R K is the coefficients vector. The matrix D = [d 1 d 2 • • • d K ] ∈
R N ×K is called dictionary and its columns constitute the dictionary atoms. If the dictionary D is a basis, i.e. K = N , and atoms are linearly independent, it is often With the right choice of dictionary, the coefficients vector c is expected to be sparse, in the sense that its sorted coefficients decay rapidly. Motivated by this idea, the design of efficient orthogonal and bi-orthogonal dictionaries was an active area of research during the last decades of 20th century. The well-known Fourier transform [START_REF] Ahmed | Discrete cosine transform[END_REF] is the result of these works which sparsifies uniformly the smooth signals. In the process, in order to achieve sparsity more efficiently, some fundamental concepts (localization, multi-resolution, and adaptivity) were formed, guiding more efficient dictionary design [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. The Short Time Fourier Transform (STFT) [START_REF] Allen | A unified approach to short-time fourier analysis and synthesis[END_REF], used in the JPEG compression standard [START_REF] Wallace | The jpeg still picture compression standard[END_REF], Gabor transform [START_REF] Qian | Discrete gabor transform[END_REF], wavelet transform [START_REF] Mallat | A Wavelet tour of signal processing[END_REF], used in JPEG2000 compression standard [START_REF] Skodras | The jpeg 2000 still image compression standard[END_REF], and packet wavelet [START_REF] Coifman | Wavelet analysis and signal processing[END_REF] are the designed transforms based on these concepts. It has been shown that the representation using the wavelet basis is optimal for piecewise smooth 1-d signals with a finite number of discontinuities (point singularities) [START_REF] Mallat | Singularity detection and processing with wavelets[END_REF]. However, it loses its optimality in representation of the image signals due to existence of curve singularities (elongated edges) in these types of signals [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. As an instance, the images encoded by the JPEG2000 standard suffer from the ringing (smoothing) artifacts near edges.

Although these dictionaries have been used in many applications due to their mathematical simplicity, their limited expressiveness of these orthogonal dictionaries leads to outweigh this simplicity. Consequently, the complete dictionaries are not well equipped for representing increasingly complex natural and high dimensional signals. This weakness is due to estimation of the small and fixed number of atoms (K = N ) in the dictionary, which is dictated by the orthogonality. In the case of bi-orthogonal dictionaries, invertiblity imposes a strict limit on the number of atoms in the dictionary (K = N ).

In an attempt to minimize this weakness of the orthonormal dictionaries, the design of more general over-complete dictionaries, which have more atoms than the dimension of signal, i.e. K > N , has been investigated over the past decades, and is still intensely ongoing.

These dictionaries have a more descriptive ability to represent a wide range of interesting signals, in comparison with the invertible complete dictionaries. Over-complete dictionaries such as steerable pyramids [START_REF] Simoncelli | Shiftable multiscale transforms[END_REF], complex wavelets [START_REF] Selesnick | The dual-tree complex wavelet transform[END_REF], curvelets [START_REF] Candés | Fast discrete curvelet transforms[END_REF], contourlets [START_REF] Do | Contourlets: a new directional multiresolution image representation[END_REF],

surfacelets [START_REF] Lu | Multidimensional directional filter banks and surfacelets[END_REF] and shearlets [START_REF] Easley | Sparse directional image representations using the discrete shearlet transform[END_REF], as well as a wide range of trained dictionaries [START_REF] Olshausen | Sparse coding with an overcomplete basis set: a strategy employed by v1?[END_REF][START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF][START_REF] Engan | Family of iterative LS-based dictionary learning algorithms, ILS-DLA, for sparse signal representation[END_REF] are especially advantageous for multi-dimensional signal data, where invertible complete dictionaries lose much of their effectiveness.

Sparse Modeling using Over-complete Dictionaries

Compared to the complete case, representation with overcomplete dictionaries must be more carefully defined. There are two distinct paths for representing a signal using the over-complete dictionaries: analysis path and synthesis path. The analysis sparse modeling relies on the classical basics of the signal modeling in which the representation of the signal is identified as a linear combination of atoms,

x Dc a , (2.3)
where the coefficients vector c a is obtained via the inner products of the signal and the dictionary c a = Ωx = D T x. This method has the advantage of providing a simple and efficient way to achieve sparse representation over the dictionary. In this case, every signal has an unique representation as a linear combination of the dictionary atoms.

Increasing sparsity, in order to obtain a well-defined representation, requires departure from this linear representation towards a more flexible and non-linear representation. Each signal is represented using a different set of atoms from a pool, called dictionary, in order to achieve the best sparsity. Thus, the approximation process becomes

x Dc s ,

where the coefficients vector c s is obtained via a non-linear approach, in contrast to the linear-based approach in the analysis path. This signal modeling approach, called synthesis sparse representation, needs further refinement to find the well-defined representation due to degrees of freedom identified by the null-space of D [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF], which leads to a non-unique choice of c s in (2.4), as opposed to the analysis sparse modeling which has a unique solution.

In order to find the most informative representation, the coefficients vector c s is obtained with respect to some cost function F(•), which minimizes the sparsity of the coefficients vector c s under a reconstruction constraint:

c s = arg min c∈R K F(c) subject to x -Dc 2 2 ≤ , (2.5)
where is the prior knowledge about the noise level. The penalty function F(•) is defined in a way that is tolerant to the large coefficients and aggressively penalizes the small Chapter 2. Sparsity-Based Signal Models coefficients [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. The normal choice for this function is p norm with 0 ≤ p ≤ 1. Of specific interest is the 0 case, i.e. F(c) = c 0 , which counts the number of non-zeros in the representation. For this case, the problem (2.5) becomes

c s = arg min c∈R K c 0 subject to x -Dc 2 2 ≤ . (2.6)
This problem, known to be NP-hard in general, can be efficiently approximated based on the idea of iterative greedy pursuit. The earliest and yet effective one includes the orthogonal matching pursuit (OMP) [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF]. Their successors include the stagewise OMP (StOMP) [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF] and the regularized OMP (ROMP) [START_REF] Needell | Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit[END_REF]. The sparsity adaptive matching pursuit (SAMP) [START_REF] Do | Sparsity adaptive matching pursuit algorithm for practical compressed sensing[END_REF] and compressive sampling matching pursuit (CoSaMP) [START_REF] Needell | Cosamp: Iterative signal recovery from incomplete and inaccurate samples[END_REF] are other methods for solving this optimization problem.

Another compelling choice for F(•) is the 1 norm, i.e. F(c) = c 1 , which provides a powerful combination of robustness and convexity. The resulting problem is given by [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] c s = arg min

c∈R K c 1 subject to x -Dc 2 2 ≤ . (2.7)
Another equivalent formulation with (2.7), from a convex optimization perspective, consists of a penalty instead of a constraint [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]:

c s = arg min c∈R K x -Dc 2 2 + λ c 1 , (2.8)
where λ is a parameter that controls the tradeoff between the fidelity term and sparsity term. This formulation forms a convex linear programming problem, for which a variety of solvers are available. An approach is based on finding a solution, c s , supported over a basis of R N within D. This approach is named Basis Pursuit (BP) [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]. Alternatively, more specialized algorithms include least absolute shrinkage and selection operator (LASSO) [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF],

gradient projection for sparse reconstruction(GPSR) [START_REF] Figueiredo | Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[END_REF], focal underdetermined system solver (FOCUSS) [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FOCUSS: a re-weighted minimum norm algorithm[END_REF], and iterative thresholding methods [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF][START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF][START_REF] Blumensath | Iterative hard thresholding for compressed sensing[END_REF][START_REF] Elad | Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization[END_REF].

These three formulations (2.6)-(2.8) have gained a large success beyond the statistics and signal processing communities and have been extensively employed in different signal processing algorithms. In the image processing applications, since the size of natural images is too large, it is chosen to partition the image into blocks and the sparse modeling is done on the set of image blocks

X = [x 1 x 2 • • • x L ], each of size √ N × √ N pixels,
where where √ N is an integer value and x i ∈ R N is lexicographically stacked representation of the i-th image patches.

Dictionary Choice

In the discussion so farit is assumed that the dictionaries of the analysis and synthesis models are known. Choosing the dictionary carefully is an important and involving task, in which substantial research has been invested. Based on analysis and synthesis models, the scientific community has developed two main routes for designing the dictionaries [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF].

The first one is analytic dictionaries derived from a set of mathematical assumptions made on the family of the signals. The dictionaries of this type are generated by finding the appropriate mathematical functions through harmonic analysis of the interesting signals for which an efficient representation is obtained. For instance, Fourier basis is designed for optimal representation of smooth signals, while the wavelet dictionary is more suitable for piecewise-smooth signals with point singularities.

Designing analytic over-complete dictionaries are formulated as DD T x = x for all x.

Then, the approach tries to establish an appropriate dictionary by analyzing the behavior of D T x and establishing a decay rate. The Curvelet [START_REF] Candés | Fast discrete curvelet transforms[END_REF], contourlet [START_REF] Do | Contourlets: a new directional multiresolution image representation[END_REF], and bandlet [START_REF] Pennec | Sparse geometric image representations with bandelets[END_REF] transforms are some of the analytic dictionaries which provide comprehensive frameworks in order to handle the multi-dimensional signals.

Finding the more compact sparse representation has been a major driving force for the continued development of more efficient dictionaries. The synthesis formulation of the sparse representation paved the way to the design of an efficient dictionary, called synthetic dictionaries, from signal realizations via machine-learning techniques. The basic assumption behind this approach is that the structure of the complex natural signals can be more accurately extracted directly from the data than by using a general mathematical model [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. In fact, this approach replaces prior assumptions on the signal behavior with a training process which constructs the dictionary based on the observed signal properties.

Compared to the analytic dictionaries, the synthetic dictionaries deliver an increased flexibility and the ability to adapt to specific signals and are superior in terms of representation efficiency at the cost of a non-structured and substantially more complex dictionary.

In this approach, a dictionary is trained for the sparse representation of small patches collected from a number of training signals. The desire to efficiently train a dictionary for the sparse representation led to developing some algorithms so far [START_REF] Olshausen | Sparse coding with an overcomplete basis set: a strategy employed by v1?[END_REF][START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF][START_REF] Engan | Family of iterative LS-based dictionary learning algorithms, ILS-DLA, for sparse signal representation[END_REF][START_REF] Vidal | Generalized principal component analysis (GPCA)[END_REF][START_REF] Sulam | Trainlets: Dictionary learning in high dimensions[END_REF].

The earlier works on the dictionary learning mostly focused on statistical methods. Given the training image patches

X = [x 1 x 2 • • • x L ],
where L is the number of training patches, this method finds a dictionary which either maximizes the likelihood of the training data P(X | D) [START_REF] Lewicki | Learning overcomplete representations[END_REF] or the posterior probability of the dictionary P(D | X) [START_REF] Kreutz-Delgado | Dictionary learning algorithms for sparse representation[END_REF]. These formulations lead to some optimization problems that are solved in an expectation-maximization fashion, alternating estimation of the sparse representation and the dictionary using gradient descent or similar methods.

In neuroscience area, Olshausen et al. [START_REF] Olshausen | Sparse coding with an overcomplete basis set: a strategy employed by v1?[END_REF] proposed a significantly different approach for designing the dictionary using the training data, benefiting from modeling the receptive fields of simple cells in the mammalian primary visual cortex. In another attempt, the K-SVD algorithm introduced by Aharon et al. [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF] is one of the well-known methods of dictionary learning. Given a set of examples

X = [x 1 x 2 • • • x L ],
the goal of the K-SVD algorithm is to search the best possible dictionary D ∈ R N ×K for the sparse representation of the training set X through the optimization problem of (2.9):

arg min C,D L i=1 c i 0 subject to X -DC 2 2 ≤ , (2.9)
where is a fixed small value and

C = [c 1 c 2 • • • c L ] is a matrix of size K × L, consisting
of the representation coefficients vectors [c i ] L i=1 of the training samples. The expression in (2.9) is performed iteratively. First, by considering an initial dictionary, the algorithm tries to find the best coefficients matrix C that can be found. Once D is known, the penalty, posed in (2.9), reduces to a set of L sparse representation operations, like the ones seen in (2.6). The OMP algorithm [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF] is used for the near-optimal calculation of the coefficients matrix C.

At the next stage, the columns of dictionary are sequentially updated and relevant coefficients in the matrix C are simultaneously changed. At a time, one column is updated and the process of updating one column is based on the singular value decomposition (SVD) on the residual data matrices, computed only on the training samples that use this atom.

The K-SVD algorithm includes a mechanism to control and rescale the 2 -norm of the dictionary elements. Indeed, without such a mechanism, the norm of D would arbitrarily go to infinity. For more details, refer to [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF].

In the image processing applications, since the size of natural images is too large for learning a full matrix D, it is chosen to learn the dictionary on a set of natural image

patches X = [x 1 x 2 • • • x L ], each of size √ N × √ N pixels
, where √ N is an integer value and x i ∈ R N is lexicographically stacked representations of the i-th image patches.

Analysis versus Synthesis

As mentioned before and also outlined in [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF], some of the most important elements of effective dictionary design include localization, multi resolution, and adaptivity. Modern dictionaries typically provide localization in both the analysis and synthesis routes.

However, multi-resolution property is usually better supported by the analytic structures, whereas adaptivity is mostly found in the synthetic methods.

The most important advantage of the analytic dictionaries is the easy and fast implementation. On the other hands, the main advantage of the trained dictionaries is their ability to provide a much higher degree of specificity to the particular signal properties, allowing them to produce better results in many practical applications such as image compression, feature extraction, content-based image retrieval and others. On the other hand, the compactness promoted by the synthesis approach might also come as a weakness. In such a framework, where only a small number of atoms are used to represent each signal, the significance of every atom differs enormously. Consequently, any wrong choice of one atom could potentially lead to additional erroneous atoms that are selected as compensation, deviating further from the desired reconstruction. This weakness is usually appeared in the 0 -norm based non-convex optimization problem of (2.6). The convex relaxation approaches from 0 to 1 are more stable for the sparse representation at the expense of computational complexity. In the analysis formulation, however, all atoms take an equal part in describing the signal, thus minimizing the dependence on each individual one, and stabilizing the recovery process.

Inverse Problem Solution Using Synthesis Models

Different applications of the analysis and synthesis sparse modeling approaches are considered in this research. The direct and explicit application of these modeling types is their ability to provide more sparse representation, allowing them to produce better results in image compression.

This section is devoted to another application of the sparse signal modeling. In fact, there are many signal processing applications for which sparse modeling is successfully gained. As an instance, Elad and Aharon in [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF] proposed an image denoising algorithm that achieved state-of-the-art results compared to other approaches at that time.

Inverse problem regularization is another important use of the signal models whose Chapter 2. Sparsity-Based Signal Models purpose is to reconstruct the original signal x ∈ R N from its degraded observed version y ∈ R M (M ≤ N ). This ill-posed problem can be generally formulated as:

y = Hx + n, (2.10)
where n ∈ R M is the system noise (usually additive Gaussian white noise). In the case of image signals, x and y are lexicographically stacked representation of the original image and the degraded image, respectively. H is a non-invertible matrix representing degradation operator.

A wide range of fundamental image processing routines, generally called image restoration (IR) algorithms, are described using this formulation; such as denoising, interpolation, super-resolution, inpainting, compressive sensing, and deblurring. The special choice of H = I, where I is an identity matrix, represents the denoising problem [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF]. If H is a diagonal matrix, whose diagonal entries are either 0 or 1, the problem (2.10) becomes an image impainting problem [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF][START_REF] Dong | Nonlocal image restoration with bilateral variance estimation: A low-rank approach[END_REF]. If H is a random measurement matrix of size M × N (M < N ), the formulation (2.10) describes compressed sensing (CS) [START_REF] Zhang | Image compressive sensing recovery via collaborative sparsity[END_REF].

When H is a filtering operator, the IR problem is the deblurring challenge [START_REF] Dong | Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization[END_REF] and in the case of H being a composite operator of blurring and downsampling, Eq. (2.10) shows an interpolation or super-resolution problem [START_REF] Yang | Image super-resolution via sparse representation[END_REF].

Without prior knowledge on x, recovering x from y is an impossible task. Furthermore, the degradation operator H introduces further complexity, as it is typically lossy, making its direct inversion highly ill-posed and unstable. To cope with the ill-posed nature of the inverse problems, the regularization-based techniques [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF][START_REF] Oliveira | Adaptive total variation image deblurring: A majorization-minimization approach[END_REF][START_REF] Rudin | Total variation based image restoration with free local constraints[END_REF] lead to the following minimization problem by regularizing the solution space:

arg min x∈R N y -Hx 2 2 + λS(x), (2.11)
where y -Hx 2 2 is the fidelity term and S(•) is the regularization term, denoting prior assumptions about the signal behavior, used to regularize the solution space and guide the solver towards an optimal solution. λ is a regularization parameter balancing the fidelity and regularity terms. Finding and modeling the appropriate prior knowledge of the signals, especially natural images, plays an important role for the performance of the regularizer and directly determines the success of the image restoration process. Some early works are based on smoothness assumptions, leading for instance to the Tikhonov regularization [START_REF] Franklin | On tikhonov's method for ill-posed problems[END_REF] and the total variation [START_REF] Oliveira | Adaptive total variation image deblurring: A majorization-minimization approach[END_REF][START_REF] Rudin | Total variation based image restoration with free local constraints[END_REF]. These regularization methods tend to over-smooth the images due to the piecewise constant assumption. Sparsity-based signal models form another powerful regularizes and have achieved great success for solution of the inverse problems [15-24, 29-34, 63]. Quite often, the requisite sparsity exists with respect to some dictionary D. In this case, the key to the sparse recovery is the production of a sparse set of significant coefficients c, whose entries' magnitude decays rapidly when sorted, and the ideal recovery procedure searches for c with the smallest p norm consistent with the observed y. Then, x is reconstructed by x = Dc.

Plugging the sparse signal modeling, i.e. x = Dc, in (2.11) leads to the following optimization problem:

ĉ = arg min c∈R K y -HDc 2 2 + λ c p , (2.12)
where D is either an analytic or synthetic dictionary. The p -norm measures the sparsity of the representation coefficients c and penalizes the denser representations. For instance, the 2 -norm aims to decrease the length of c, while penalizes the large coefficients and givs less attention to the smaller ones. On the other hand, the family of p -norms, where 0 ≤ p ≤ 1, provides more robust tool for measuring the sparsity. Excepting 1 -norm by which all magnitude of coefficients c are equally penalized, other measures penalize more the nonvanishing small coefficients, while tolerating a limited number of large ones. Further, such measures are much better in capturing the rate of decay of a vector, and are more useful for describing modern sparsifying transforms, which are known to produce heavy-tailed coefficient distributions in natural signal data. Of specific interest is the choice p = 1, as it represents the most robust convex option for (2.12).

Clearly, the optimization problem (2.12) is similar to the minimization problem of (2.5), except that the minimization problem (2.12) is more severly under-determined and it has a much larger number of unknowns in comparison with (2.5). In other words, it equals the sparse representation of degraded signal y over the overcomplete matrix HD; therefore, it can be typically solved using a suitable variant of the algorithms mentioned in Section 2.3.

Indeed, in this , the term of sparse recovery is used, instead of sparse representation, for the description of optimization problem (2.12) in order to make clear its difference with the sparse representation.

Using a synthetic dictionary, the problem (2.12) is called analysis sparse recovery which has been successfully applied in a wide range of inverse problems, leading to state-ofthe-art results for image denoising, inpainting, CS reconstruction, deblurring, and superresolution [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF][START_REF] Mairal | Sparse representation for color image restoration[END_REF][START_REF] Yang | Image super-resolution via sparse representation[END_REF][START_REF] Zhang | Group-based sparse representation for image restoration[END_REF][START_REF] Zhang | Image compressive sensing recovery via collaborative sparsity[END_REF][START_REF] Dong | Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization[END_REF][START_REF] Dong | Nonlocal image restoration with bilateral variance estimation: A low-rank approach[END_REF], to name just a few.

Chapter 2. Sparsity-Based Signal Models

CS-based Image Acquisition and Analysis Sparse Reconstruction

Unlike the traditional point-by-point sampling (Nyquist sampling theorem), the CS theory provides a new approach for signal acquisition wherein the signal can be exactly reconstructed using a small number of random linear measurements, under certain sparsity conditions [START_REF] Candes | An introduction to compressive sampling[END_REF][START_REF] Donoho | Compressed sensing[END_REF]. Since most signals are indeed compressible or sparse with respect to some transform domains Ψ, the CS has attracted a lot of attentions in many applications, including medical imaging, camera design and multimedia sensor networks, due to its potential of reduction of sampling rates, power consumption and computation complexity in the image acquisition.

Mathematically, the CS effectively acquires the real-valued signal x ∈ R N , via a linear projection of the signal onto some random measurement basis Φ of size M × N where M N , i.e.:

y = Φx + n, (2.13)
where y ∈ R M is the measurements vector and n ∈ R M is the system noise (usually Gaussian additive white noise). The rate of sampling, called subrate, achieved by (2.13), is defined as S = M/N . The sampling operator Φ, called also measurement matrix, is a non-invertible matrix and should be incoherent with Ψ [START_REF] Donoho | Compressed sensing[END_REF]. A sufficient condition for the unique and exact recovery of the signal is restricted isometry property (RIP) of the measurement matrix Φ [START_REF] Candes | An introduction to compressive sampling[END_REF][START_REF] Donoho | Compressed sensing[END_REF]. The matrix Φ ∈ R M ×N satisfies the RIP of order k if there is constant δ k (0 < δ k < 1) such that, for all vectors x ∈ R N with x 0 , i.e. k-sparse signals, it holds: with a large k, is desirable to have a measurement matrix with a δ k as small as possible.

(1 -δ k ) x 2 2 ≤ Φx 2 2 ≤ (1 + δ k ) x 2 2 . ( 2
The fundamental concept of the CS theory states that, although the number of unknowns is larger than the number of measurements, the signal can still be exactly recovered, if it is sparse enough [START_REF] Candes | An introduction to compressive sampling[END_REF][START_REF] Donoho | Compressed sensing[END_REF]. To address this problem, there have been great efforts to develop optimal CS reconstruction algorithms which differ based on their computational complexity and also the reconstruction quality [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF][START_REF] Chen | Atomic decomposition by basis pursuit[END_REF][START_REF] Fowler | Multiscale block compressed sensing with smoothed projected landweber reconstruction[END_REF][START_REF] Cartis | A new and improved quantitative recovery analysis for iterative hard thresholding algorithms in compressed sensing[END_REF].

How to efficiently reconstruct the image with good recovery quality and low computational complexity is always a focused topic in the CS applications field. Without prior knowledge about the original signal, recovering x from y is an impossible task. Furthermore, the measurement matrix Φ introduces further complexity because of its lossy nature that leads to the highly ill-posed and unstable direct inversion. To cope with the ill-posed nature of the CS recovery, regularization-based techniques [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF][START_REF] Oliveira | Adaptive total variation image deblurring: A majorization-minimization approach[END_REF][START_REF] Rudin | Total variation based image restoration with free local constraints[END_REF] lead to the following minimization problem:

x = arg min x∈R N y -Φx 2 2 + λS(x), (2.15)
where y -Φx 2 2 is the fidelity term and S(x) is the regularization term, used to regularize the solution space and guide the solver towards an optimal solution. λ is a regularization parameter balancing the fidelity and regularity terms. S(•) in (2.15) expresses prior assumptions about the signal behavior. Finding and modeling the appropriate prior knowledge of the signals, especially natural images, plays an important role for the performance of the regularizer and directly determines the success of the image restoration process.

The analysis sparse modeling provides some regularization methods that are based on this fact that the requisite sparsity exists using some sparse transform x → Ψ(x) and it is expected that the representation coefficients Ψ(x) is sparse in the sense that the sorted coefficients decay rapidly. Based on the sparse signal modeling, the regularization term S(•) in (2.15) can be defined in way to measure the sparsity of the representation coefficients Ψ(x) and penalizes denser representations. In practice, the p -norms achieve these goals and can be considered as the sparsity measure. For instance, the 2 -norm aims to decrease the length of Ψ(x), while penalizing the large coefficients and giving less attention to the smaller ones. On the other hand, the family of p -norm, where 0 ≤ p ≤ 1, provides a more robust tool for measuring the sparsity. Excepting 1 -norm wherein the magnitudes of all coefficients Ψ(x) are equally penalized, other norms penalize more the non-vanishing small coefficients, while tolerating a limited number of large ones.

Given the sparse transform Ψ(•) and incorporating this model into the minimization problem (2.15), the recovery is achieved by solving the following optimization problem:

x = arg min x∈R N y -Φx 2 2 + λ Ψ(x) p . (2.16)
Based on this modeling, the recovery algorithm searches for a sparse set of significant coefficients, c = Ψ(x) that are consistent with the observed measurements y and the magnitude of its entries decays rapidly when sorted. Then, x is reconstructed by x = Ψ -1 (c),

where Ψ -1 (•) is the inverse transform of Ψ(•). Of specific interest is the choice p = 1, as it represents the most robust convex option for the minimization problem (2.16), which is efficiently solved by the well-known BP algorithm [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]. Alternatively, more specialized algorithms include LASSO [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF], GPSR [START_REF] Figueiredo | Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[END_REF], FOCUSS [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FOCUSS: a re-weighted minimum norm algorithm[END_REF], and iterative thresholding methods [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF][START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF][START_REF] Blumensath | Iterative hard thresholding for compressed sensing[END_REF][START_REF] Elad | Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization[END_REF].

The design of an efficient orthogonal transform was an active area of research during the last decades. The well-known DCT [START_REF] Ahmed | Discrete cosine transform[END_REF], STFT [START_REF] Allen | A unified approach to short-time fourier analysis and synthesis[END_REF], Gabor transform [START_REF] Qian | Discrete gabor transform[END_REF], wavelet transform [START_REF] Mallat | A Wavelet tour of signal processing[END_REF], and wavelet packets [START_REF] Coifman | Wavelet analysis and signal processing[END_REF] are the proposed transforms based on this concept.

Although these dictionaries have been used in many applications due to their mathematical simplicity, their limited expressiveness of the orthogonal dictionaries leads to outweigh this simplicity. Consequently, the complete dictionaries are not well equipped for representing increasingly complex natural and high dimensional signals. For instance, the representation using the wavelet basis is optimal for piecewise smooth 1-d signals with a finite number of discontinuities (point singularities) [START_REF] Mallat | Singularity detection and processing with wavelets[END_REF]. However, it loses its optimality in the representation of image signals due to existence of curve singularities in these types of signals [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. This weakness is due to the small and fixed number of atoms (K = N ) in the dictionary, which is the consequence of the orthogonality. On the other hand, transform reversibility imposes a strict limit on the number of atoms in the dictionary (K = N ).

In an attempt to minimize this weakness of the orthonormal dictionaries, the design of more general over-complete dictionaries which have more atoms than the dimension of the signal, i.e. K > N , has been investigated. These dictionaries have a more descriptive ability to represent a wide range of interesting signals, when compared with the reversible complete dictionaries. Over-complete dictionaries such as steerable pyramids [START_REF] Simoncelli | Shiftable multiscale transforms[END_REF], complex wavelets [START_REF] Selesnick | The dual-tree complex wavelet transform[END_REF], curvelets [START_REF] Candés | Fast discrete curvelet transforms[END_REF], contourlets [START_REF] Do | Contourlets: a new directional multiresolution image representation[END_REF], surfacelets [START_REF] Lu | Multidimensional directional filter banks and surfacelets[END_REF] and shearlets [START_REF] Easley | Sparse directional image representations using the discrete shearlet transform[END_REF], as well as a wide range of trained dictionaries [START_REF] Olshausen | Sparse coding with an overcomplete basis set: a strategy employed by v1?[END_REF][START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF][START_REF] Engan | Family of iterative LS-based dictionary learning algorithms, ILS-DLA, for sparse signal representation[END_REF] are especially advantageous for multidimensional signals, where invertible dictionaries lose much of their effectiveness.

Block-based CS Reconstruction

When the signal x is an image or video, the CS reconstruction methods need a large memory and computational burden due to the multidimensional nature of image data. Furthermore, a large memory is needed when storing the measurement matrix Φ. Low complexity of the sensing and recovery schemes play an important role in designing an imaging sensor. Blockbased compressed sensing (BCS) comes to solve these issues by splitting the image into K non-overlapping blocks of size √ N b × √ N b and then, the acquisition is achieved block by block independently using the same measurement matrix Φ b for each block [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF][START_REF] Gan | Block compressed sensing of natural images[END_REF].

Assuming x i is a vector of size N b , representing the i-th block of the image in the vector format, the corresponding measurements x i are obtained via:

y i = Φ b x i , (2.17)
where Φ b is the measurement matrix of size

M b × N b (M b < N b ) [69]
. This procedure can be applied directly on the entire image by creating the block-diagonal matrix

Φ = diag(Φ b , • • • , Φ b ) [25].
At the receiver side, each block can be reconstructed separately using the algorithm mentioned in the previous section. However, these recovery algorithms usually create unpleasant blocking artifacts. To overcome this weakness, several BCS reconstruction algorithms have been designed [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF][START_REF] Gao | Relative sparsity estimation based compressive sensing for image compression applications[END_REF][START_REF] Trinh | Compressive sensing recovery with improved hybrid filter[END_REF]. Recently, the authors in [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF] proposed a BCS reconstruction algorithm, called BCS with smoothed projected Landweber reconstruction (BCS-SPL), that is based on successive projections and thresholding in the transform domain. Given an initial approximation of the image x[0] , at each iteration k, the BCS-SPL algorithm updates the i-th block x[k] i as:

x[k] i = x[k] i + Φ T y i -Φx [k] i . (2.18)
In the next step, all the reconstructed blocks at iteration k, i.e. [x

[k] i ] K i=1
, are put back into the full-image plane to update the reconstructed image x[k+1] using smoothing and thresholding operations. The BCS-SPL algorithm uses a smoothing operator via Wiener filtering, which reduces the blocking artifacts, and a thresholding process in the transform domain Ψ(•), which controls the local sparsity. The BCS-SPL algorithm offers the advantage of easily allowing the utilization of a wide range of sparse transforms, such as directional transforms; the most effective one is proven by experiments to be the dual-tree discrete wavelet transform (DDWT) [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF]. Throughout this chapter, the BCS-SPL algorithm is coupled with the DDWT as the sparsity basis. Such a procedure is iterated until

x[k+1] -x[k]
2 ≤ . The details of the BCS-SPL algorithm is summarized in Algorithm 1.

In Algorithm 1, the operator R(•) splits the image into K non-overlapping blocks and the operator R -1 (•) puts back the reconstructed blocks into the corresponding positions in

Chapter 2. Sparsity-Based Signal Models Algorithm 1 BCS-SPL 1: Input: Φ b , [y i ] K i=1 , N p , Ψ(•) 2: Output: x 3: Initialize: k ← 0 and x[0] = 0 4: Repeat 5: x[k] i K i=1 = R x[k] 6:
For i ← 1 to K do 7:

x

[k] i = x[k] i + Φ T y i -Φx [k] i 8:
End 9:

x

[k] = R -1 x[k] i K i=1 10:
x

[k] = Wiener x[k] 11: x[k] i K i=1 = R x[k]
12:

For i ← 1 to K do 13:

x

[k] i = x[k] i + Φ T y i -Φx [k] i 14:
End 15:

x

[k] = R -1 x[k] i K i=1 16:
x

[k] = Ψ(x [k] ) 17:
x

[k] = Threshold(x [k] ) 18:
x

[k+1] = Ψ -1 (x [k] ) 19: Until x[k+1] -x[k] 2 ≤ µ
the reconstructed image, padded with zeros elsewhere. The BCS-SPL algorithm provides a good trade-off between the computational complexity and the reconstruction quality.

Please refer to [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF] for more details.

Chapter 3 Image Compressed Sensing Recovery

The material of this part is essentially based on the following works area for so many years and a variety of mathematical forms has been proposed by now [START_REF] Mairal | Sparse modeling for image and vision processing[END_REF].

One of the simplest and most common forms is that signals have some priori probability distribution assumed on the signal space [START_REF] Elad | Analysis versus synthesis in signal priors[END_REF][START_REF] Elad | Analysis versus synthesis in signal priors[END_REF]. While this representation is mostly useful when employing statistical signal processing methods, many signals in practical use cannot be directly associated to a probabilistic distribution.

One efficient signal modeling methods is the sparse representation which has been proven to be effective for many signals, such as natural images, and successfully used in a wide range of applications. This model represents signals in terms of linear combinations of an underlying set, called dictionary, of elementary signals, known as atoms. The driving force behind this model is the sparsity of the representation coefficients, i.e. the rapid decay of the representation coefficients over the dictionary.

The sparse signal modeling has the ability to solve inverse problems such as compressed sensing (CS) recovery, denoising, and so on. The CS recovery are indeed often difficult to solve without a priori knowledge of the data source. The sparse signal modeling provides a strong tool for an a priori model of the data source. The main goal of this chapter is to provide new applications of the sparse signal modeling for the CS recovery from various perspectives.

Contributions

In this chapter, several image CS recovery methods are studied. First, by joining the block based sampling and the human visual system (HVS) characteristics, an adaptive block based CS scheme is presented in order to achieve a smart-human recovery performance.

Visual saliency is a cognitive mechanism of the HVS. A human always focuses on the salient regions while ignoring non-salient areas when exploring a natural scene. To the best of our knowledge, there is no application of the visual saliency in the image CS domain. Different from previous approaches in the adaptive CS, we adopt the adaptive CS framework by access to side information, such as a saliency map, which leads to an efficient CS image reconstruction. In this sense, we try to obtain a saliency model of the original image. Since the complex human visual system performs numerous functions when viewing, it is not possible to combine it into the direct sensing process. Beside the hardware problems, the process of integrating the salient region detection into the cameras is not straightforward due to its time and energy consuming process. However, by considering a feedback channel between the sensor and the receiver, the CS can gain from the visual saliency for improving the image reconstruction quality. In addition, the feedback information should be as few as possible, then a low bandwidth channel is required. The procedure begins with a fixedrate compressive sampling for all blocks and a primary recovery at the receiver. Then a classical graph based [START_REF] Harel | Graph-based visual saliency[END_REF] is used to compute the saliency map, so that the HVS interesting regions are extracted. Then, a binary map, where the ones represent the blocks belonging to the salient region, is organised. We achieve the adaptivity in sampling by establishing a feedback channel between the sensor and receiver, making subsequent measurements more directly into the salient regions of the image.

As a second contribution to improve the perofromance of CS reconstruction, we extend the concept of prediction and residual reconstruction to the image CS recovery. A prediction is produced to create a measurement-domain residual of the image to be recovered; such a residual is typically more compressible than the original one, making it more adapted to the CS reconstruction. Several methods for the prediction generation are discussed in this chapter. First, considering the strong correlation among the neighboring areas within an image, we present an CS recovery of images by providing an intra-image prediction. Further, the local sparsity and nonlocal similarities among the image patches are implicitly exploited to generate an optimal prediction, improving the performance of the image CS recovery. Specifically, a prediction of the image is estimated using synthesis sparse representation technique vis a trained over-complete dictionary which models the image patches as a linear combination of very few number of atoms chosen from an over-complete dictionary. A novel sparse representation modeling of natural images, called group-based sparse representation (GSR) [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF], is exploited. In this method, the concept of group which is composed of non-local patches with similar structures, is considered as the means unit of sparse representation.

Adaptive block-based CS recovery

The conventional BCS scheme acquires all blocks with the same number of measurements, ignoring the subjective importance of each block to the HVS. On the other hand, from the view of biological vision and scientific analysis, the visual significance of each block varies with its spatial position [START_REF] Borji | Salient object detection: A benchmark[END_REF]. Some regions can be more sensitive to the HVS, while others have a lower level of visual interest. Therefore, it is necessary to design an adaptive BCS scheme by joining the block-based sampling and the HVS characteristics in order to achieve a smart-human recovery performance.

In order to improve the limitations of the traditional fixed-rate BCS, several adaptive BCS from various perspectives have been proposed in the literature. In [START_REF] Malloy | Near-optimal adaptive compressed sensing[END_REF], the authors give a theoretical analysis of the adaptive compressed sampling and confirm that the adaptive measurements significantly outperform the non-adaptive systems in practice.

The existing adaptive acquisition techniques are based on extracting local features, such as standard deviation [START_REF] Noor | Adaptive compressive sensing algorithm for video acquisition using single pixel camera[END_REF][START_REF] Guicquero | Nonuniform sampling with adaptive expectancy based on local variance[END_REF], edge counting [START_REF] Guicquero | An adaptive compressive sensing with side information[END_REF] or estimation of the reconstruction error [START_REF] Malioutov | Sequential compressed sensing[END_REF] in the measurement domain. Inspired by relationship between compressibility and redundancy of the natural images, an adaptive scheme is proposed in [START_REF] Chen | Self-adaptive sampling rate assignment and image reconstruction via combination of structured sparsity and non-local total variation priors[END_REF] by estimation of the compressibility based on the local redundancy, measured by the statistics of the pre-sensed measurements. These adaptive samples can benefit from on-the-fly acquisition, but are often not accurate. Some few works perform the adaptive BCS by combining the sampling and reconstruction together. In [START_REF] Warnell | Adaptive-rate compressive sensing using side information[END_REF], this joint sampling is used to improve the reconstruction quality for pedestrian tracking in the video surveillance applications.

Saliency-based BCS recovery

Visual saliency is a cognitive mechanism of the HVS in order to accurately identify the significant visual information (salient or foreground regions) and filter out other redundant visual information (non-salient or background regions) when exploring the natural scenes.

Since the HVS performs numerous functions when viewing, it is not possible to combine this complex function into the direct sensing process. Beside of the hardware problems, the process of integrating the salient region detection into the cameras is not straightforward due to its time-and energy-consuming process. However, by considering a feedback channel between the sensor and the receiver, the BCS can gain from the visual saliency to improve the image reconstruction quality [START_REF] Akbari | Adaptive saliency-based compressive sensing image reconstruction[END_REF]. The graph-based visual saliency (GBVS) model [START_REF] Harel | Graph-based visual saliency[END_REF] is a well-known algorithm to extract the salient regions within the image. In the following, the GBVS and BCS-SPL algorithms are employed to build up an image CS recovery algorithm in an adaptive way to the human visual perception, called saliencybased BCS with smoothed-projected reconstruction (SBCS-SPL). Following this adaptive procedure, the high sampling rates are assigned to the salient regions while the low sampling rates are allocated to the non-salient regions, lead to a better recovery quality.

The block diagram of the SBCS-SPL scheme is shown in the Fig. 3.1. Firstly, the basic BCS acquisition is done at the sensor side, i.e. the image is partitioned into

√ N b × √ N b
non-overlapping blocks sampled at the same subrate S. At the receiver side, an initial reconstruction of the image is obtained using the BCS-SPL algorithm. In the next step, a saliency map for the whole image is computed using the initial reconstructed image via the GBVS model [START_REF] Harel | Graph-based visual saliency[END_REF]. The GVBS consists of the following three main steps:

Feature map extraction: A feature map represents the image based on a well-defined feature. These maps can be extracted and computed either from the first-order statistics of stimulus features such as intensity, color, orientation, and texture or by linear filtering on the image followed by some elementary nonlinearity. For example, a contrast map computed using intensity variance in the local patches of the image or a simply an intensity of the grayscale values can be considered as a feature map.

Activation map computation: In the second step, the feature map is transformed to an activation map in which the parts of the scene, according to a specific feature, that strongly differ from its surrounding are highlighted. The process is implemented by a graph-based random walk which can be applied on feature map to extract local activities for each feature type. At first, a graph is generated by connecting the nodes in a feature map. Then, by assignment a weight between nodes, the graph is interpreted as Markov chains. It accumulates mass at nodes that have high dissimilarity with their surrounding nodes and is considered as activation and saliency values.

Normalization and combination: In the last stage of the attention model, a saliency map is generated by normalization of the activation map in order to prevent some salient regions masked by noise or interfered by less-salient regions. A similar approach based on graph over activation map is also implemented in this step. Mass will flow preferentially to those nodes with high activation. Please refer to [START_REF] Harel | Graph-based visual saliency[END_REF] and its references herein for more details. Based on the obtained saliency map, a binary label is assigned to each block; label 1 for the blocks belonging to the salient regions and label 0 for the blocks within the other area of the image. To this purpose, the saliency map of the input image is normalized into the range of [0, 1]. The pixel values of the normalized saliency map can be interpreted as the probability of that pixel belonging to the salient regions. A block is considered to be salient (labelled with 1), if the averaged probability of its pixels, called the salience value of the block, is greater than a predetermined threshold T in the range [0, 1]; otherwise, it is considered as a non-salient block (labelled with 0). Obviously, the percentage of blocks falling into the salient regions will be increased by decreasing the threshold. The obtained saliency values depend on the performance of the GVBS model. However, one can design a new model to extract more precise saliency value for each block. Finding the exact value of T is not a non-trivial task. In the following, a simple procedure for finding an appropriate threshold T is proposed.

Following the above step, the new sampling subrates are computed based on this binary block labeling. The aim is thus to allocate different subrates to the salient and non-salient blocks, provided that the overall subrate equal (or slightly inferior) to the target subrate S. Mathematically, the subrates, assigned to the salient and non-salient blocks, i.e. S s and S ns respectively, are adjusted such that:

N s S s + N ns S ns = (N s + N ns )S, (3.1)
where N s and N ns denote the number of salient and non-salient blocks, respectively. Assume the salient and non-salient subrates are the fractions of a constant value U ; i.e.

S s = K s U and S ns = K ns U, (3.2)
subject to

0 < K ns < K s < 1 and K s + K ns = 1, (3.3)
where K s and K ns are two predetermined parameters being related to the proportion of the salient and non-salient blocks in the corresponding number of measurements. From (3.2) and (3.3), one can easily solve (3.1) for U by:

U = (N s + N ns )S K s N s + K ns N ns . (3.4)
It should be noted that taking a small value for the parameter K ns can lead to serious distortion in the non-salient regions, while a selection of large value for K ns cannot reflect the superiority of this scheme because of the inconspicuous contribution in the adaptive sampling.

At high target subrate S, finding the subrates S s and S ns using (3.2) may lead to

S s > 1.
In this case, we impose S s = 1 and then S ns can be easily computed from (3.1) via the following equation:

S ns = (N s + N ns )S -N s N ns . (3.5)
In contrast, the value of subrate S ns obtained with (3.2) is very small at a low target subrate S and can result into inaccurate reconstruction of the non-salient blocks. In order to guarantee that the assigned subrate to the non-salient blocks is not too small, a minimum Chapter 3. Image Compressed Sensing Recovery subrate S m is considered for the subrate S ns . We set up S m = K × S, where 0 < K < 1 is a predefined parameter to adjust the minimum subrate for the non-salient blocks. After obtaining S s and S ns using (3.2), if S ns ≤ S m , we set S ns = S m and the subrate of the salient blocks is re-calculated using (3.1) via:

S s = (N s + (1 -K)N ns )S N s . (3.6)
Finally, the block labels and the sampling subrates corresponding to the salient and non-salient blocks, i.e. N s and N ns , are sent to the sensor in order to perform a new adaptive acquisition. As an overall result, the measurements for i-th block is achieved by y i = Φ b x i , where a smaller subrate than S, i.e. S ns , is assigned to the non-salient regions, while the visually significant blocks are sampled at a higher subrate than S, i.e.

S s , so that the overall subrate of image is unchanged. After getting the new adaptive measurements for each block, the SBCS-SPL scheme follows the same procedure with the BCS-SPL algorithm to recover the original image.

It is worth saying that each block has a different saliency value. Therefore, the quality of the reconstructed image is improved by assigning different sampling rates based on their saliency value. On the other hand, this procedure increases the overhead information to send back to the sensor which needs a high-bandwidth feedback connection. However, the SBCS-SPL scheme just sends a binary sequence and two obtained values of sampling subrates, i.e. S s and S ns , to the sensor. Therefore, a low-bandwidth connection is enough for transmitting the side information to the sensor. The length of binary sequence depends on the number of blocks in the image. It should be noted that one can assign different labels, instead of only two binary levels, to each block in order to allocate more precise sampling rate. However, this increases the size of the side information.

The number of salient and non-salient blocks, N s and N ns , depends on the predetermined value of the threshold T . Finding an appropriate threshold T is a non-trivial task.

Choosing a large threshold value T leads to a small number of the salient blocks which does not have a big effect on the performance. On the other hand, with considering a small value of the threshold T , a large part of the image is considered as the salient region.

T = 1 2(R × C) R-1 x=0 C-1 y=0 H(x, y), (3.7)
where R and C are the width and height of the normalized saliency map H, respectively, and H(x, y) is the saliency value of the pixel at the position (x, y). As can be observed in the Fig. 3.3, the obtained threshold for the Lena image is T = 0.13 which is near to the real maximum of the curve. At this case, the percentage of salient regions is %53.9. Given the threshold T , relatively high sampling rates are assigned to the blocks in the salient regions and low sampling rates are assigned to the rest of blocks. For instance, for the Lena image at the target subrate S = 0.3, the obtained subrates for the salient and non-salient areas are S s = 0.46 and S ns = 0.11, respectively.

Residual-based Image CS Reconstruction Algorithms

In the previous section, an image BCS recovery algorithm has been presented by which the recovery quality is improved via establishing a feedback channel between the receiver and the sensor in an adaptive acquisition framework. This section focuses on introducing receiver-based CS recovery algorithms without any change in the signal acquisition part.

In video compression, motion estimation and compensation are used to support the temporal sparsity. In this technique, the first frame within a group of pictures (GOP) is firstly encoded. Exploiting the high resemblance among the frames within the same GOP, instead of fully encoding the next frame, the residual between the original frame and its prediction from the previous frame, is encoded. This resulted residual is obviously more sparse. The same encoding procedure is conducted for the multi-view image and video compression, exploiting disparity estimation and compensation methods. The fundamental property of the CS theory states that a very sparse signal can be perfectly reconstructed. Therefore, higher sparsity can be provided by estimating a prediction of that image and exploiting it for the CS reconstruction [START_REF] Trocan | Compressedsensing recovery of multiview image and video sequences using signal prediction[END_REF][START_REF] Trocan | Compressedsensing recovery of multiview image and video sequences using signal prediction[END_REF][START_REF] Trocan | Disparitycompensated compressed-sensing reconstruction for multiview images[END_REF] by implicitly increasing the signal compressibility [START_REF] Tramel | Video compressed sensing with multihypothesis[END_REF]. In this paradigm, during the reconstruction step, a prediction of the current block is obtained by exploiting the strong correlation among the blocks within an image. Then, the CS reconstruction algorithm is driven by the measurement-domain residual that is obtained by difference between the measurements of current block and its prediction [START_REF] Fowler | Multiscale block compressed sensing with smoothed projected landweber reconstruction[END_REF][START_REF] Mandache | Image compressed sensing recovery using intra-block prediction[END_REF][START_REF] Akbari | Residual based compressed sensing recovery using sparse representations over a trained dictionary[END_REF]. Suppose the measurements of block x i is obtained via

y i = Φ b x i .
Let xi is a prediction of the block x i , then the measurement-domain residual of the i-block is obtained by r i = y i -Φ b xi . Given the measurement-domain residuals for all blocks, i.e.

r, the final reconstructed frame x is computed as:

x = x + BCS-SPL(r, Φ b ), (3.8)
where x is the prediction image. As the residual (difference between x and x) is more compressible (sparser) than the block itself, a better approximation of the signal is obtained by the CS recovery [START_REF] Trocan | Compressedsensing recovery of multiview image and video sequences using signal prediction[END_REF][START_REF] Trocan | Disparitycompensated compressed-sensing reconstruction for multiview images[END_REF]. This is demonstrated empirically in Fig. 3.4 wherein it is seen that the coefficient magnitudes decay more quickly for a residual frame than for the original video image. A good prediction always makes the residual very sparse and also random.

However, in the CS reconstruction algorithms, the randomness is not an issue for recovery.

Until the measurement matrix satisfies the restricted isometry property (RIP) and the signal to be recovered is sparse enough, the recovery can be done.

Residual-based CS reconstruction using intra-image prediction

In this section, the basic framework of intra-image prediction is exploited to propose a novel strategy for the block-based image CS reconstruction, called block-based CS reconstruction In the initial phase, the BCS-IIP algorithm builds an initial reconstruction of the image,i.e.

x. This reconstruction can be achieved using any CS reconstruction algorithm. The BCS-SPL algorithm is employed in our implementation. Moving forward to the enhancing phase, the initial reconstructed image x is partitioned into L non-overlapping blocks of size N p × N p . N p is not necessarily the same as N b . For the prediction goal, the small block sizes improve the prediction quality, whilst in the case of CS, the bigger the block the better the reconstruction will be. For the former, the selection of a smaller block size increases the correlation among the neighboring blocks, leading to a more accurate prediction. For the latter, the larger blocks for the acquisition provides more sparse blocks, a necessary condition for the success of CS reconstruction algorithms.

Let set S = z 1 , z 2 , • • • z 8 consist of 8 surrounding blocks of the current block z in the initial reconstruction image x, as shown in Fig. 3.6. The similarity between the block z and its k-th surrounding block is measured by sum of absolute differences (SAD) as:

SAD k = Np m=1 Np n=1 |z k (m, n) -z(m, n)|. (3.9)
Using these similarity measure, the decoder can decide if the block z and its 8 surrounding blocks are part of the same smooth area within the image. This decision is achieved as:

SAD k < T, (3.10)
where the threshold T is related to the block size and the maximal intensity value within the image. T can be effectively determined by T = B 2 p .I, which is equivalent to the sum of values within a block of size N p × N p pixels, whose all pixel values equals to I.

Based on the SAD values and the threshold T , the neighboring blocks that satisfy the condition (3.10) are taken into account to generate a prediction for the current block z.

The way of using the blocks in the set S influences the quality of the obtained prediction for the current block z. A weighting scheme is used to control the influence of each sample The Hamming function [START_REF] Ganguly | An overlapped motion compensated approach for video deinterlacing[END_REF] is used for generating this weighting window. By splitting this weighting matrix into N p × N p blocks, the corresponding weighting coefficients for the 8 corresponding blocks are obtained, as shown in Fig. 3.8. The central block in the weighting window, denoted by w c , is replaced with a block whose all values equal to 1, meaning that the current block z contributes entirely to its prediction. Finally, the prediction of the current block z is obtained by the following equation:

z p = z + k∈Ss z k * w k w c + k∈Ss w k , (3.11)
where * shows element-wise matrix multiplication and the set S s denotes the set of neighboring blocks which respect to (3.10). w k is the corresponding submatrix for the block z k belonging to the set S. This prediction process is done for all the blocks within the initial image x to generate a prediction x for the image x.

With respect to the same BCS at the encoder side, the prediction image

x is partitioned into √ N b × √ N b blocks

Residual-based compressed sensing recovery using a trained dictionary

In the previous section, a residual-based CS reconstruction algorithm has been described wherein the final reconstructed image is obtained using a measurement-domain residual.

Generally, the CS recovery of the residual image, obtained by difference of the original image and its prediction, increases the CS reconstruction performance [START_REF] Mandache | Image compressed sensing recovery using intra-block prediction[END_REF][START_REF] Chen | Compressed-sensing recovery of images and video using multihypothesis predictions[END_REF]. In the BCS-IIP algorithm, the weighted average of the spatially surrounding blocks is computed to obtain a prediction for each block. However, the limitation of this method is that its performance relies heavily on the obtained prediction that is based on the assumption of similarity among the adjacent blocks within an image. To address this issue, the non-local self-similarities of image patches within an image can be exploited in order to produce a prediction that is as close as possible to each block in order to generate a highly compressible residual [START_REF] Akbari | Residual based compressed sensing recovery using sparse representations over a trained dictionary[END_REF].

The well-known SR models the image patches as a linear combination of a very few number of atoms chosen from an over-complete dictionary. GSR [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF] Given the measurement vectors [y i ] K i=1 , the object is to recover the image patches

[x i ] K i=1
in order to reconstruct the whole image x. In the first step, the aim is to find an optimal prediction of the image x by solving the following minimization problem:

x = arg min z x -z 2 + λΘ(z), (3.13)
where xz 2 is the 2 data-fidelity term, Θ(z) is the regularization term that regularizes the solution space of the fidelity term, and λ is the regularization parameter. As discussed in Section 2.5, one of the most significant regularization terms is sparsity, which means that the natural images are locally sparse. In other words, each local image patch can be accurately represented as a few elements chosen from a dictionary [START_REF] Elad | Image denoising via sparse and redundant representations over learned dictionaries[END_REF][START_REF] Yang | Image super-resolution via sparse representation[END_REF][START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. Further, there are many repetitive high level patterns and regular structures globally positioned in the images [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF]. This significant property between similar patches within an image, called non-local self-similarity, in combination with the local sparsity existing in the natural images, can be used as a more suitable and efficient regularization term to regularize the solution space of the minimization problem in (3.13) and develop a much more accurate prediction [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF][START_REF] Dong | Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization[END_REF][START_REF] Sun | Learning discriminative dictionary for group sparse representation[END_REF]. the obtained residual has a random nature, it is s deep sparse signal that can be recovered more accurate from the corresponding measurements.

Assume an image u is firstly partitioned into L overlapping patches of size N p × N p pixels, represented as column vectors [u p i ] L i=1 , where u p i ∈ R Np . Assume matrix H i ∈ R Np×C consists of C similar patches to the x i within a large enough window of size B × B pixels, as shown in Fig. 3.9. The Euclidean distance is considered as the similarity measure.

Lets define the operator R i (•) that extracts matrix H i from the image u, i.e.

H i = R i (u).
Given all the matrices [H i ] L i=1 , the image u is estimated by:

x = L i=1 R T i (H i ) • / L i=1 R T i (1 N b ×C ), (3.14)
where the operator R T i (•) puts back the patches in the matrix H i into the corresponding positions in the reconstructed image, padded with zeros elsewhere. The operator •/ denotes the pixel-wise division and 1 Ns×C is a unit matrix of the same size as matrix H i . It can be easily seen that the reconstructed image via Equation (3.14) is obtained by averaging all the overlapped patches. As will be seen later, this overlapping partitioning technique ensures that the obtained prediction does not suffer from the blocking artifacts and provides a high quality prediction.

The prediction in the BCS-GSR algorithm is obtained by assuming that each group of similar patches, i.e. H i , can be represented by linear combinations of a few of atoms chosen from an over-complete dictionary D.

Suppose D = [D 1 D 2 • • • D M ] whose atoms [D j ] M
j=1 are matrices of the same size as matrix H i . With this structure, the dictionary D is a matrix of size N s × CM . Given the dictionary D with M atoms, the object is to find the sparse representation of each group H i with respect to dictionary D. In other words, we want to find a sparse vector α i ∈ R M such that H i M j=1 α i,j d j , where α i,j is the j-th element of the sparse vector α i . Mathematically, the sparse coding of H i with respect to D is obtained by solving the following minimization problem:

arg min α i ∈R M H i - M j=1 α i,j d j 2 + λ α i 0 , (3.15)
where λ is a regularization parameter. In this framework, the 0 -norm of α i enforces the sparsity and the self-similarity of patches is considered in the definition of H i . Given the sparse representation vectors [α i ] L i=1 and by considering Equation (3.14), image u can be Figure 3.9: One image patch and its associated window for finding the similar patches. estimated as:

u D α = L i=1 R T i   M j=1 α i,j D j   • / L i=1 R T i (1 Np×C ). (3.16)
where α denotes the concatenation of all sparse representation vectors [α i ] L i=1 . The notation D α is just for simplicity of the following equations.

In the following, we combine this approach of prediction generation into the CS reconstruction algorithm. By considering Equations (3.13), (3.15), and (3.16), we propose the reconstructed image via x D α as a prediction for the image, where α is obtained by solving the following minimization problem:

arg min α x -D α 2 + λ α 0 .
(3.17)

However, Since the original image x is unknown, the CS recovery cannot be directly achieved. However, it can be successfully solved by applying an iterative procedure. First, an initial image, denoted by x[0] , is reconstructed using the BCS-SPL algorithm. At each iteration k, the reconstructed image is updated through two steps as follows:

Step1-Prediction Generation: The scheme tries to find a solution for the following minimization problem:

α[k] = arg min α x[k] -D α [k] 2 + λ α [k] 0 . (3.18)
Given the dictionary D, the minimization problem (3.18) is efficiently solved by the algorithm proposed in [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF]. Given α[k] , the generated prediction at iteration k is updated by

x[k] = D α[k] .
Step2-Residual Reconstruction: In this step, the residual-based CS reconstruction algorithm is employed to recover the image. To this purpose, the obtained prediction

x[k] is partitioned into K N b × N b non-overlapping blocks [x [k] i ] K i=1
, similar to the partitioning procedure that has been done at the transmitter side. Then, each block is projected onto the measurement domain via

ỹ[k] i = Φ b x[k] i . After computing the measurement-domain residuals r [k] = [r [k] i ] K i=1 , where r i = y [k] i - ỹ[k]
i , the spatial-domain residual image is obtained using the BCS-SPL algorithm. Finally, the image is obtained by combining the prediction image x and the reconstructed residual image as:

x[k+1] = x[k] + BCS-SPL(r [k] , Φ b ). (3.19)
The reconstruction quality is then improved by repeating step1 (prediction generation) and step2 (residual reconstruction). The details of the BCS-GSR algorithm is summarized in Algorithm 2. The decoder terminates the iterations when

x[k+1] -x[k] 2 ≤ 0.001.
However, the decoder can terminate the reconstruction algorithm early depending on its hardware abilities.

The discussion so far has assumed that the dictionary D is known. Choosing the dictionary D is an important task for finding an optimal solution to the minimization problem in (3.18). The scientific community has developed two main ways for designing the dictionaries [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]: 1-mathematical modeling and 2-training procedure [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. The former tries to find the dictionary from a set of mathematical assumptions made on the family of the signals. For instance, Fourier basis is designed for optimal representation of smooth signals, while the wavelet dictionary is more suitable for piecewise-smooth signals with point singularities. The latter provides an ability to design a dictionary adapted to a specific data signal via machine-learning techniques. The basic assumption behind this approach is that the structure of the complex natural signals can be more accurately extracted directly from the data than by using a general mathematical model [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. Compared to the mathematical dictionaries, the trained dictionaries deliver an increased flexibility and the ability to adapt to specific signals are superior in terms of representation efficiency, at the cost of a non-structured and substantially more complex dictionary. In the BCS-GSR algorithm, a dictionary is trained usinf a set of training image patches collected from a number of Algorithm 2 BCS-GSR

1: Input: Φ b , [y i ] K i=1 2: Output: x 3: Initialize: k ← 0 and x[0] = BCS-SPL([y i ] K i=1 , Φ b ) 4: Repeat 5:
Step1: Prediction Generation 6:

Solve: α[k] = arg min α x[k] -D α [k] 2 + λ α [k] 0 7:
Compute prediction:

x[k] = D α[k] 8:
Step2: Residual Reconstruction

9: Split x[k] into K non-overlapping blocks: [x [k] i ] K i=1 10: For i ← 1 to K do 11: r [k] i = y [k] i -Φ b x[k] i (i = 1, 2, • • • K) 12:
End 13:

Update:

x[k+1] = x[k] + BCS-SPL(r [k] , Φ b ) 14: Until x[k+1] -x[k] 2 ≤ µ
training signals. We adopt the dictionary learning algorithm method in [START_REF] Zhang | Group-based sparse representation for image restoration[END_REF] wherein a self-adaptive dictionary is learned.

Experimental Results

In this section, the performance of the SBCS-SPL, BCS-IIP, and BCS-GSR algorithms will be evaluated via a suite of simulations carried out on a set of 8-bit grayscale standard The computational complexity of the above-mentioned algorithms is evaluated in terms of reconstruction time (second) in Table 3.2 at various subrates. The experiments are conducted on a PC with an Intel(R) Xeon(R) processor at 3.20 GHz and 8-GB of RAM at 64-bits operating system of WINDOWS 7 with a non-optimized MATLAB implementation. As can be seen, the SBCS-SPL method is slower than the BCS-SPL one due to the extra process of the initial reconstruction and also extracting the salient blocks. In addition, as expected, the BCS-IIP and BCS-GSR algorithms cannot be faster than the BCS-SPL algorithm, mostly due to the prediction time. However, its advantage in image reconstruction with high accuracy is interesting.

In the SBCS-SPL, BCS-IIP, and BCS-GSR algorithms, the BCS-SPL algorithm is involved as the core of the reconstruction process. Therefore, the computational burden of the recovery process of these algorithms is substantially increased using the iterative nature of the BCS-SPL algorithm. It is worthwhile to mention that, thanks to the blockbased reconstruction, it is plausible to the extent that a parallel implementation of the BCS-SPL algorithm can be trivially accomplished in hardware, which is suitable for the real-time applications. In the other words, the BCS-SPL algorithm can be easily executed in a parallel manner to provide an acceptable computational cost using an array of multiple instructions multiple data (MIMD)-based parallel processors. In the BCS-GSR algorithm, in addition to this parallel implementation, the decoder can early terminate the iterations, depending on its computational power, to decrease the computational complexity and yet obtain a visually satisfactory image reconstruction. Finally, it should be noted that the SBCS-SPL method can be effectively and usefully employed for the pedestrian tracking in the video surveillance applications and also sampling of the low-to-normal dynamics video sequences without increasing the computational complexity. At these applications, only the first frame within a group of pictures (GOP) is used for the saliency computation and the rate allocation. Given the high resemblance among the frames within the same GOP, the adaptive sensing uses this saliency information to guide the sampling of the next frames in order to optimize the gain of new information.

Conclusion

Several new CS reconstruction algorithms have been considered at this chapter. First, a summary of the CS methodology and a brief description of the well-known BCS-SPL algorithm have been presented in the first part of this thesis. Inspired by the saliency In the existing image/video transmission systems, a frame is divided into non-overlapped blocks which are coded separately. In the packetization step, one or more blocks are fed loss rate (PLR), their performance is known to degrade as the PLR increases [START_REF] Akbari | Sparse recovery-based error concealment[END_REF][START_REF] Song | Robust multiple description image coding over wireless networks based on wavelet tree coding, error resilient entropy coding, and error concealment[END_REF].

Recently, a robust image transmission scheme has been proposed in [START_REF] Akbari | Sparse recovery-based error concealment[END_REF] and [START_REF] Akbari | Sparse recovery-based error concealment for multiview images[END_REF], by which a high quality image can be recovered, even at the high PLRs, at the expense of adding a simple random linear encoder at the transmitter side. However, the transmitter still needs to send extra information, degrading the efficiency of transmission through the low bandwidth connections.

In contrast to the transmitter-based methods, error concealment (EC), as a receiverbased method, is an alternative solution to mitigate the negative effects of the packet loss. The EC techniques recover the missing information without modifying the encoder or sending any additional information, leading to a better bandwidth efficiency [START_REF] Kim | Spatial error concealment for H.264 using sequential directional interpolation[END_REF]. These methods exploit the high spatial or temporal correlations existing among the lost areas and correctly received neighboring pixels to reconstruct a high quality image or video from its degraded version. Appropriate modeling of this intrinsic characteristic of the natural images plays an important role in the recovery performance of the EC algorithms which has been extensively studied over the past decades.

Sparse representation (SR) has been a powerful tool for image processing over the past decade. In this technique, a signal can be represented by linear combination of a few atoms chosen from a pool called dictionary [START_REF] Peyre | A review of adaptive image representations[END_REF]. Based on analysis sparse modeling (2.3) and synthesis sparse modeling (2.4), the used dictionary can be designed by some mathematical functions or learned from some training examples [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. In this chapter, the synthesis sparse representation model is extended to EC application, being effective to recover a high quality image from a corrupted input. is proposed in [START_REF] Asheri | Multi-directional spatial error concealment using adaptive edge thresholding[END_REF]. A more advanced algorithm for reconstruction of more complex visual features is proposed in [START_REF] Kim | Spatial error concealment for H.264 using sequential directional interpolation[END_REF]105,[START_REF] Rongfu | Content-adaptive spatial error concealment for video communication[END_REF]. In these methods, an edge descriptor method over the missing block is integrated into the error control system for obtaining a more visually pleasing texture reconstruction. Although these methods are effective for realtime applications, in many cases, the quality of the concealed images is unsatisfactory in practice.

The statistical-based methods usually assume that the missing pixels can be estimated by employing some fixed-function kernels or adaptive-structure kernels [START_REF] Shirani | An adaptive markov random field based error concealment method for video communication in an error prone environment[END_REF][START_REF] Koloda | Kernel-based MMSE multimedia signal reconstruction and its application to spatial error concealment[END_REF][START_REF] Zhai | Image error-concealment via block-based bilateral filtering[END_REF][START_REF] Zhai | Bayesian error concealment with DCT pyramid for images[END_REF]. A minimum square error estimator is used in [START_REF] Koloda | Kernel-based MMSE multimedia signal reconstruction and its application to spatial error concealment[END_REF] to conceal the lost blocks by modeling the problem of error recovery as a regression problem. The missing pixels are estimated from their known context using a minimum square error estimator which uses a probability density function obtained by kernel density estimation. In [START_REF] Zhai | Bayesian error concealment with DCT pyramid for images[END_REF], the missing blocks are recovered by the computation of conditional expectation of the missing pixels by the surrounding available ones in a Bayesian framework. Markov random fields model is considered in [START_REF] Shirani | An adaptive markov random field based error concealment method for video communication in an error prone environment[END_REF] for filling the missing pixels. In [START_REF] Zhai | Image error-concealment via block-based bilateral filtering[END_REF], using a pair of Gaussian kernels and capturing the block-level similarity, the lost blocks are recovered as a weighted average of the neighboring pixels.

In contrast to the aforementioned block-based approaches, a sequential orientation adaptive interpolation (OAI) method is proposed in [START_REF] Li | Novel sequential error-concealment techniques using orientation adaptive interpolation[END_REF], wherein the pixels in the missing blocks are successively recovered by exploiting a linear predictor on a small spatial window.

This algorithm overcomes the blocking and blurring effects of the simple interpolationbased methods and exhibits the edge-preserving property. Another sequential estimation of the missing pixels is proposed in [START_REF] Liu | Spatial error concealment with an adaptive linear predictor[END_REF] by using an adaptive linear predictor (ALP) in which a Bayesian information criterion is adopted to explicitly determine the order of the predictor (e.g. the available neighbouring pixels suitable for estimation). Different from the algorithm proposed in [START_REF] Liu | Spatial error concealment with an adaptive linear predictor[END_REF][START_REF] Li | Novel sequential error-concealment techniques using orientation adaptive interpolation[END_REF], the algorithm in [START_REF] Koloda | Sequential error concealment for video/images by sparse linear prediction[END_REF]114] focuses on seeking a distinct, robust, and sparse linear predictor (SLP) to select a linear combination of a few number of neighboring pixels for estimation of the lost pixels. These approaches, however, may address the error propagation by the incorrect estimation of the missing pixels, causing undesirable blurred details. In addition, at the high packet loss rates, where consecutive blocks are lost, this impairment becomes more severe.

The sparse recovery-based EC schemes tackle these shortcomings. In these methods, the restoration is done by transferring the recovery problem into the SR domain with respect to some trained or mathematical dictionaries. Then, the reconstructed image is obtained by back projection into the spatial domain. In other words, these methods improve the quality of corrupted images by uncovering the relationships among the corrupted and original image patches in the SR domain, where these relationships can be achieved more adaptively and accurately than the abovementioned techniques proposed for the spatial domain. Especially, this correlation is efficiently modeled by means of the synthesis sparse representation of the correctly received neighboring area using a learned dictionary.

The synthesis sparse recovery-based approaches are superior to both interpolationbased and statistical-based methods, since they are able to produce novel details that cannot be recovered by the aforementioned methods. Several sparse recovery-based EC methods have been proposed in [START_REF] Akbari | Image error concealment using sparse representations over a trained dictionary[END_REF] and [115]. The method in [START_REF] Akbari | Image error concealment using sparse representations over a trained dictionary[END_REF] assumes that the sparse representation of the lost area in the image is the same as that of the known neighboring areas with respect to an off-line trained dictionary. However, this assumption is not satisfied when the lost area is located in the high textural region or the size of missing area becomes larger. Therefore, there is no guarantee for an accurate recovery of the missing regions.

Motivated by the joint sparse representation model, the works in [START_REF]Joint-domain dictionary learning-based error concealment using common space mapping[END_REF], [START_REF]Image error concealment based on joint sparse representation and non-local similarity[END_REF], and [115] try to learn the relationships between the patches in the corrupted and original images using two external training datasets of the original and corrupted image patches. This relationship can be effectively found by transferring the original and corrupted patches into the sparse representation space over the trained dictionaries. In addition to these works, instead of using external training datasets, the authors in [115] train a mapping function between a lost block and its neighboring pixels by finding the similar patches in the input corrupted image in order to transfer knowledge of available regions to the missing regions for the EC purpose. However, in the extreme, when the similar patches cannot be found in the image, it is impossible to learn a good mapper.

Joint Sparse Representation (JSR)

In recent years, the sparse data representation has been extensively utilized in different applications by means of 0 -norm and 1 -norm minimization techniques [START_REF] Tropp | Computational methods for sparse solution of linear inverse problems[END_REF]. Based on this modeling, an image patch is represented using a small number of basis functions chosen out of an over-complete dictionary [START_REF] Peyre | A review of adaptive image representations[END_REF]. The choice of over-complete dictionary plays an important role in the sparse representation modeling. One of the most flexible ways to obtain such an over-complete dictionary is by learning from a set of example image patches, which has been an active field of research over the past decade [START_REF] Elad | On the role of sparse and redundant representations in image processing[END_REF][START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF][START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF][START_REF] Mairal | Learning multiscale sparse representations for image and video restoration[END_REF].

Recently, Yang et al. proposed a joint sparse representation modeling for image super resolution [START_REF] Yang | Image super-resolution via sparse representation[END_REF]. They assume that there exist two coupled over-complete dictionaries for two different modalities (low resolution (LR) and high resolution (HR) image patches), over which each paired samples of modalities have the same sparse representations. Based on this modeling, a coupled dictionary learning is proposed, in which the coupling is realized by enforcing the low and high resolution patches to share the same sparse feature space.

This joint sparse representation modeling has been extensively used in other applications, including classification [START_REF] Shekhar | Coupled projections for adaptation of dictionaries[END_REF], cross-model matching [START_REF] Biswas | Generalized coupled dictionary learning approach with applications to cross-modal matching[END_REF], and multispectral image change detection [START_REF] Gong | Coupled dictionary learning for change detection from multisource data[END_REF]. In [START_REF] Wang | Semi-coupled dictionary learning with applications to image super-resolution and photo-sketch synthesis[END_REF], it is assumed that the sparse representations of the two modalities are related to each other via a linear mapping function. This type of modeling relaxes the strong assumption of the coupled dictionary learning algorithm in [START_REF] Yang | Image super-resolution via sparse representation[END_REF], and brings more flexibility to characterize the image structures. However, using a single linear mapping may not be good enough for the sparse representations of two modalities accurately [START_REF] Liu | Cross-view action recognition via view knowledge transfer[END_REF].

In the field of cross-model matching, a new coupling model has been recently proposed which uses two linear mappings to project the sparse representations of the paired samples from the two different modalities into a common space to enable joint assessment of the two modalities [START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF].

Contributions

In this chapter, the image EC task is considered as an inverse problem of recovering the original image from the corrupted received image. This recovery procedure is generally a severely ill-posed problem due to the limited and insufficient information of the correctly received areas of the image. However, one can solve this NP-hard problem by the sparse signal modeling techniques and the strong correlations among the adjacent pixels in the image. The present chapter models the error concealment scheme as a synthesis sparse recovery framework (see Eq. (2.12)) using a trained dictionary. We use the learned dictionary in order to adaptively select the most relevant basis for representing each patch of the image, including the correctly received surrounding areas of the lost region. Then, these basis and corresponding coefficients are used to conceal the corrupted region.

In this work, we build upon the recent success of the JSR techniques and propose a novel EC method. Different from [START_REF] Wang | Semi-coupled dictionary learning with applications to image super-resolution and photo-sketch synthesis[END_REF][START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF][START_REF] Yang | Coupled dictionary training for image super-resolution[END_REF] wherein the authors use the learned mappings and dictionaries for image synthesis and recognition, we reformulated the JSR-based dictionarymapping algorithm in [START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF] for error concealment application. Throughout the chapter, we describe the settings for learning the dictionaries and mappings. As in the JSR, two dictionaries corresponding to the original clean and corrupted image patches are trained in a coupled manner. It is assumed that the dictionaries of the original and corrupted patches are coupled to each other by identifying a mapping function. Based on this assumption, the objective is to learn the mapping function jointly with the dictionary pair. As the sparse representation of the original clean patch and the corrupted patch may not be well correlated, several coupling approaches are proposed in this chapter to address this problem. In the recovery phase, the dictionary corresponding to the corrupted dataset is used to compute the sparse representation of the corrupted patch. This is then transformed into the common space using the respective mapping function in order to find a good estimation of the sparse representation of the original patch. Following this step, the dictionary corresponding to the original dataset is used to recover the original patch.

Apart from the JSR model to error recovery, some natural image priors can also be used as the regularization term to make the above joint encoding model more effective and robust for the EC application. In this chapter, non-local self-similarity (NS) and local regularity (LR) priors are integrated into the proposed JSR model to further regularize the solution space. The NS model benefits from many repetitive image structures in the whole image and best preserves the edge sharpness and complex texture [START_REF] Mairal | Non-local sparse models for image restoration[END_REF][START_REF] Jiang | Single image super-resolution via locally regularized anchored neighborhood regression and nonlocal means[END_REF] in the concealed image. On the other hand, the LR model characterizes the local image structures, wherein each pixel is estimated via linear combination of its surrounding pixels within the support of the LR model [START_REF] Dong | Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization[END_REF][START_REF] Zhang | Image interpolation by adaptive 2-d autoregressive modeling and soft-decision estimation[END_REF]. The way we mixed the local and non-local properties with the learned mappings and dictionaries is our main and second contribution in this chapter. In contrast to the existing approaches that use these priors in the spatial domain, the novelty here is in the use of modeling the local and non-local priors in a transformed space. The reason is that it provides a more robust and accurate estimation of the sparse representation of the corrupted patch and the main features of the corrupted area can be recovered more accurately in comparison with those from spatial domain. Combining the JSR, LR, and NS models into a framework leads to a minimization problem. Designing a fast and efficient solution for this minimization problem is another contribution of this chapter. The main contributions of this chapter are therefore summarized as:

• We reformulated the JSR-based dictionary-mapping algorithm in [START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF] for the EC application.

• By combining the JSR model, NS and LR priors into a unified framework, a robust EC technique, namely joint sparse representation based-EC with the non-local and local regularization (JSR+NL) is proposed.

• A fast and effective algorithm for solving the designed minimization problem is proposed.

• A number of experiments are conducted to demonstrate the effectiveness of the proposed JSR+NL method in comparison with recent EC algorithms. Further, we analyze different parameter settings for our proposed approach, including the image patch size and the dictionary size.

Joint Sparse Representation for EC

In this section, we firstly formulate the image EC problem to be considered in this chapter. Next, based on the concept of joint sparse representation, a joint dictionary-mapping learning algorithm is introduced. Finally, the JSR model for the image EC is proposed. x using just the correctly received information. This problem is formulated as follows:

x = arg min x y -Hx 2 2 , (4.1)
where H is an M ×M diagonal matrix, whose diagonal entries are either 0 or 1. Here, value 0 refers to loss and 1 to correctly received corresponding pixel in the image. In this section, in order to solve this ill-posed problem, a joint sparse representation model is considered to regularize the solution space. The local and non-local priors are considered as another regularization term in the next section.

The corrupted and original patches belong to different visual observation subspaces X and Y, respectively. There is an intrinsic relationship, represented by mapping function F, between these subspaces and if we could find this relationship, the error recovery can be achieved easily. One of the most flexible ways to discover the mapping function F is by learning. In this way, F is learned from the training data offline. This mapping function is then utilized in the image reconstruction step [START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF][START_REF] Wang | Learning coupled feature spaces for cross-modal matching[END_REF]. However, learning the mapping function F in the spatial domain is difficult due to the existence of a complex structure among the training data in the spatial domain. This complexity makes it hard to correlate the data of different modalities accurately. On the other hand, it is wellknown that the image patches are sparse when represented by dictionaries [START_REF] Peyre | A review of adaptive image representations[END_REF]. Inspired by this fact, the mapping function F can be found in the sparse representation domain more accurately. Therefore, a straightforward way to find the mapping function is to build two such dictionaries, one of which is responsible for the original patches in the observation subspace X , whereas the other one is responsible for the corrupted patches in the observation subspace Y. The JSR model [START_REF] Yang | Image super-resolution via sparse representation[END_REF][START_REF] Wang | Semi-coupled dictionary learning with applications to image super-resolution and photo-sketch synthesis[END_REF][START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF] provides a powerful tool to learn these dictionaries jointly with the mapping function F.

Joint Dictionay-Mapping Learning

In this section, we reformulate the JSR-based dictionary-mapping learning algorithm in [START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF], for EC. The main idea is to learn a dictionary pair for the corrupted and original patches in a coupled manner such that the sparse representations of the corresponding patches are maximally correlated in some transformed space.

To learn the dictionary pair, firstly, two training datasets X and Y are constructed as follows: A set of training images are corrupted by generating the isolated loss pattern (see It is assumed that the sparse representation matrices, Λ x and Λ y , are directly related to each other via a linear mapping matrix M ∈ R K×K . In [START_REF]Image error concealment based on joint sparse representation and non-local similarity[END_REF][START_REF] Wang | Semi-coupled dictionary learning with applications to image super-resolution and photo-sketch synthesis[END_REF], a mapping term, defined as:

E mapping = Λ x -MΛ y 2 2 , (4.3)
is incorporated into the dictionary learning algorithm to find the two dictionaries, D x and D y , jointly with the mapping matrix M. Although this coupled dictionary-mapping learning algorithm has been successfully applied to several tasks, such as image super resolution and image classification [START_REF] Wang | Semi-coupled dictionary learning with applications to image super-resolution and photo-sketch synthesis[END_REF], as discussed in Section 4.4, it might not guarantee accurate matching of the corrupted and original patches for the EC application, especially when some important structures of the patches are corrupted. In other words, a more complex mapping matrix M should be learned to achieve a more robust performance.

Recently, the authors in [START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF] proposed a common space mapping approach for the cross-modal matching task, wherein a more efficient relationship is found for two different datasets X and Y. Inspired by this, we assume that the projections of the sparse representation matrices, Λ x and Λ y , into a K-dimensional common space using two mapping matrices, M x ∈ R K×K and M y ∈ R K×K , are the same with high probability. In this case, a mapping term is defined as:

E mapping = M x Λ x -M y Λ y 2 2 , (4.4)
and incorporated into the dictionary learning algorithm (4.2), leading to the following minimization problem:

arg min

Dx,Dy,Λx,Λy,Mx,My

X -D x Λ x 2 2 + Y -D y Λ y 2 2 + γ M x Λ x -M y Λ y 2 2 + λ x Λ x 1 + λ y Λ y 1 + λ m M x 2 2 + M y 2 2 , (4.5)
where the first and second terms are fidelity terms associated with the data reconstruction error. These terms ensure that the data in two modalities are reconstructed accurately D y , Λ x , and Λ y . More details can be found in [START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF]. The step of updating the mapping matrices is a ridge regression problem that is solved by the algorithm described in [START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF]. In this algorithm, a positive constant is added to the main diagonals of the mapping matrices.

This small perturbation produces the diagonal mapping matrices and also guarantees that the obtained mapping matrices are invertible. This means that the solution always exists.

More details can be found in [START_REF] Huang | Coupled dictionary and feature space learning with applications to cross-domain image synthesis and recognition[END_REF].

At the case of using direct mapping term (4.3) and plugging into the dictionary learning algorithm, the following optimization problem will be resulted:

arg min

Dx,Dy,Λx,Λy,Mx,My

X -D x Λ x 2 2 + Y -D y Λ y 2 2 + γ Λ x -MΛ y 2 2 + λ x Λ x 1 + λ y Λ y 1 + λ m M x 2 2 + M y 2 2 , (4.6)
Fig. 4.3 shows the difference between two joint dictionary learning algorithms using direct mapping term (4.3) and common space mapping term (4.4).

The JSR based EC

Given the trained dictionaries D This optimization problem is iteratively solved by alternatingly updating α y and α x using the two following problems:

arg min αy y -D y α y 2 2 + γ M x α x -M y α y 2 2 + λ y α y 1 , arg min αx x -D x α x 2 2 + γ M x α x -M y α y 2 2 + λ y α y 1 . (4.8)
Finally, the concealed patch is obtained via x = D x α x . Instead of using this iterative algorithm here, a fast and yet effective way is proposed to obtain an approximated solution for the minimization problem (4.7). image is obtained using a simple interpolation algorithm [START_REF] Shirani | An adaptive markov random field based error concealment method for video communication in an error prone environment[END_REF]. As explained later, this initial interpolation simplifies much of the subsequent work without a computational cost.

Given a corrupted patch y, its mean intensity value is subtracted from, and then its sparse representation, α y , with respect to the dictionary D y is obtained via the following minimization problem:

arg min αy y -D y α y 2 2 + λ s α y p , (4.9)
where α y p is the sparsity-inducing regularization term and λ s denotes the regularization parameter that balances the tradeoff between the fidelity and sparsity terms. If p = 1, then λ s = λ y . It has been illustrated in [START_REF] Mairal | Non-local sparse models for image restoration[END_REF], given a trained dictionary learned with 1 -norm, the sparse representation of the image patches with respect to this dictionary is in general of higher accuracy when using the 0 -norm. Therefore, we consider p = 0 in our implementations2 . The 0 -normalization problem (4.9) is efficiently solved by the well-known orthogonal matching pursuit (OMP) algorithm [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF].

Once α y is obtained by solving the minimization problem (4.9), it is projected into the K-dimensional common domain by α c = M y α y . It is assumed that the projection of the sparse representation of the original patch, α x , into the common domain by M x α x , is also associated with the α c , i.e. M y α y = M x α x . We next derive

α x = M -1 x α c = M -1 x M y α y . (4.10)
For simplicity, we consider P = M -1 x M y , then α x = Pα y . Further, the concealed patch is obtained via x = D x α x . Following this, the mean intensity value of the patch is added back to the estimated patch. Finally, the unknown pixels, i.e. v, are replaced by the corresponding pixels in the concealed patch x (see Fig. 4.2).

Block Recovery Order

As it can be seen in Fig. 4.2, the corrupted patch y contains P missing pixels of the lost block (In this , we consider P = 4.) So, the lost block cannot be recovered at one time. Instead, as in [START_REF] Koloda | Sequential error concealment for video/images by sparse linear prediction[END_REF], we propose to recover the lost block sequentially. First, the lost block is partitioned into √ P × √ P blocks, as shown in Fig. 4.5. Then, the subblocks are recovered one by one based on a predetermined order. Consider the subblock that is located at the upper-left corner of the lost block in Fig. 4.5. In order to recover this subblock, the corresponding corrupted patch of size √ T × √ T , consisting of this subblock and its avaialable adjacent pirxels, as shown in Fig. 4.2, is formed. Next, the patch is recovered using the procedure described at the previous section. Finally, the corrupted subblock is replaced with the corresponding pixels in the recovered patch. These steps are repeated for the next subblocks.

In order to improve the quality of the reconstructed block, two further considerations are employed: recovery order and overlap width. The reconstruction order, i.e. the order that subblocks are recovered, plays an important role to the performance of the proposed JSR-based EC algorithm. Since the accuracy of the recovered subblock depends on the reliability of its available adjacent pixels, the subblocks that have more reliable information at their support area are firstly recovered. This leads to a more precise estimation of the sparse coefficients via (4.9) and thus better reconstruction quality. The recovery order of an isolated lost block of size 8×8 pixels is shown in Fig. 4.5 where the subblocks illustrated by a brighter gray-level are recovered first. Using this order for recovering the subblocks also ensures that more reliable information at the support area of the next subblocks is already provided.

Addition to the recovery order, we also consider an overlap depth between the adjacent subblocks in order to avoid the blocking artifacts resulting from partitioning. Since the size

JSR-based EC with Non-local and Local Regularization (JSR+NL)

Clearly, it is expected that the sparse representation vector α x , obtained by Equation (4.10) should be as close as to the true sparse representation vector α t x of the patch to be recovered. However, the JSR model, presented in the Section 4.2.3, may not lead to recover the true sparse representation α t

x due to the corrupted pixels in the input patch y. Further, there are many repetitive patterns and regular structures throughout the natural images. This NS model in combination with the LR prior existing in the natural images can be used as a regularization term to regularize the solution space of the minimization problem (4.9) and develop a much more accurate sparse representation model. The NS and LR models have been used in many applications, such as image compression [START_REF] Chen | Nonlocal context modeling and adaptive prediction for lossless image coding[END_REF][START_REF] Lucas | Image coding using generalized predictors based on sparsity and geometric transformations[END_REF] and inverse problems [START_REF] Dong | Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization[END_REF][START_REF] Zhang | Image interpolation by adaptive 2-d autoregressive modeling and soft-decision estimation[END_REF][START_REF] Dong | Nonlocally centralized sparse representation for image restoration[END_REF]. However, in these works, the NS and LR models are implemented in the spatial domain whereas here they are in the sparse representation domain. This regularization term is incorporated into Equation (4.9) to develop a more effective EC algorithm, called JSR-based EC with the NS and LR models (JSR+NL).

The EC performance depends on the difference α x -α t x . To faithfully reconstruct the original image, this difference should be close to zero. By incorporating this difference into the minimization problem (4.9), we propose the following optimization problem:

arg min αy y -D y α y 2 2 + λ s α y 0 + λ nl P α y -α t x 1 , (4.11)
where λ nl represents the regularization parameter. This model enforces the sparse representation vector α y to be estimated in a way that P α y is close to α t x . However, α t x is unknown and the 1 -norm in the objective function (4.11) cannot be directly measured.

Nonetheless, if we find a good estimation of α t x , then we can develop a much more accurate sparse representation model.

Generally, α t

x can be estimated in various ways. We propose to achieve a good estimation of α t

x using the rich non-local and local redundancies existing in the input image. Then, a good estimation of α t

x can be computed as the weighted average of the sparse representation associated with an estimation of the input patch from the non-local similar patches within the image and the sparse representation associated with an estimation of the input patch from the local neighboring pixels. This leads to the following optimization problem: In the following section, we discuss how the sparse representation vectors β ns and β lr are obtained.

For understanding how these estimations of α t x , obtained by β ns and β lr , can improve the quality, we should pay attention to the second regularization term in (4.11). This term regularizes the solution space of the first term in the minimization problem (4.11) more effectively than the first regularization term. Since, β ns and β ns capture the main features of the patches y ns and y lr , respectively, this regularization term adds an efficient constraint in order to improve the accuracy of Pα y .

Non-local Self-similarity for Regularization

The NS model is based on this fact that the higher level patterns, e.g. edges and texture, tend to repeat themselves within the image [START_REF] Mairal | Non-local sparse models for image restoration[END_REF][START_REF] Jiang | Single image super-resolution via locally regularized anchored neighborhood regression and nonlocal means[END_REF][START_REF] Dong | Nonlocally centralized sparse representation for image restoration[END_REF]. Based on this concept, an estimation of each input patch y can be obtained via:

y ns = L i=1 w i y i , (4.13)
where y i is the i-th similar patch to the input patch y and L denotes the number of similar patches within a large enough window of size H × H pixels. As can be seen in Fig. 4.6, y and the i-th similar patch:

w i = 1 κ exp(-y -y i 2 2 /h), (4.14)
where h is a pre-determined scalar and κ denotes the normalization factor. The patches with a smaller Euclidean distance have larger weights in the average. The exponential function provides further control on the influence of similar patches on the estimation of the patch y. The parameter h controls the slop of the exponential function and therefore the decay of the weights as a function of the Euclidean distances [START_REF] Buades | A non-local algorithm for image denoising[END_REF]. This weighting procedure emphasizes the patches which are closer to patch y.

Given the estimated patch y ns , the sparse representation β ns can be easily found by

arg min βns y ns -D x β ns 2 2 + λ ns β ns 0 , (4.15)
The well-known OMP algorithm [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF] is used to solve this minimization problem.

Local Structural Regularity for Regularization

The LR model is based on this assumption that a local area in the image is stationary, which states that there are meaningful local structures in the spatial domain of the natural image.

Based on this property, one target pixel z i can be predicted by weighted combination of its neighbors s i (called context of the LR model), i.e. z = s i * a i , where a i includes the weighting coefficients (see Fig. 4.7). Therefore, an estimation of each input patch y can be obtained by estimating all its pixels sequentially.

The major challenge in the LR model is development of an accurate and fast predictive model, i.e. how to find the optimal weights in order to fully exploit the information contained in the context. In [START_REF] Lucas | Image coding using generalized predictors based on sparsity and geometric transformations[END_REF][START_REF] Wu | Model-guided adaptive recovery of compressive sensing[END_REF], the weighting coefficients are estimated by a training procedure, where the training set is collected from the initially recovered image by searching the similar patch in the entire image. But, this procedure may not adapt the LR model to the image characteristics due to the poor quality of the initially recovered image and tends to produce the visual artifacts [START_REF] Dong | Image deblurring and super-resolution by adaptive sparse domain selection and adaptive regularization[END_REF]. In this chapter, we propose a learning procedure, where z k is a N k ×1 column vector that consists of the target pixels in z corresponding to the training vectors in submatrix S k . A well-known closed-form solution for this minimization [START_REF] Lucas | Image coding using generalized predictors based on sparsity and geometric transformations[END_REF]. Note that a k includes the weighting coefficients of the LR model of k -th cluster.

wherein
problem is a k = (S T k S k ) -1 (S T k z k )
Given an input patch y and all C learned LR models, first, the k -th LR model is assigned to each pixel y i of y based on the minimum distance between its context, i.e. s i ∈ R 1×Q as shown in Fig. 4.7, and the centroid of clusters {µ 1 , µ 2 , • • • µ C }, i.e. k = arg min k s i -µ k . Finally, the pixel y i is updated via y i = s i a k . All pixels in the input patch y is sequentially estimated to obtain a prediction y lr for the input patch y. Finally, the sparse representation vector β lr is obtained by following the minimization function that is solved by the OMP algorithm [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF]:

arg min β lr y lr -D x β lr 2 2 + λ s β lr 0 , (4.17

Recovery Algorithm

The optimization problem (4.11) can be solved through two following separate steps.

Step1) First, an initial sparse representation vector, denoted by α

[0]
y , is obtained by the following optimization problem:

α [0] y = arg min α y -D y α 2 2 + λ s α 0 . (4.18)
This minimization problem is solved by the OMP algorithm [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF]. Then the initial estimation of x, denoted by x [0] , is estimated as lr respectively, are obtained using Equations (4.15) and (4.17).

x [0] = D x P α [0]
Step2) The accuracy of the sparse representation α y is improved using an iterative process. At each iteration l + 1, for fixed β ns and β lr obtained from previous iteration, the updated sparse representation vector α ns -bβ

[l] lr 1 , (4.19)
Then, Equations (4.15) and (4.17) are used to update β ns and β lr . Given α

[l+1] y
, the concealed image patch is updated as

x [l+1] = D x P α [l+1] y
, which can be used to estimate the

β [l+1] ns
and β

[l+1] lr using the minimizations in (4.15) and (4.17), respectively. The improved

β [l+1] ns
and β

[l+1] lr are then used to enhance the accuracy of α y , and so on. The accuracy of the sparse representation α y is gradually improved, which in turn improves the accuracy of α x and thus the EC quality. Such a procedure is iterated until convergence. In the proposed algorithm, the recovery process can be stopped when x

[l+1] -x [l] 2 ≤ .
A specific extension of the shrinkage algorithm [START_REF] Dong | Nonlocally centralized sparse representation for image restoration[END_REF], originally proposed in [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF], is adapted to solve the minimization problem (4.19) iteratively. At the j + 1-th iteration, This is one of the most important characteristics of the sparse representation techniques which has been used in many applications, especially image denoising.

Experimental Study

In this section, we briefly introduce the training datasets used by the joint dictionarymapping learning algorithm, described in Section 4.2.2. Then, the influences of the related parameters on the EC performance are evaluated in order to select the appropriate values of these parameters. Finally, the performance of the proposed JSR and JSR+NL algorithms,

Training Sets Description

The CVG-Granada database [START_REF] Timofte | Seven ways to improve example-based single image super resolution[END_REF]. This guarantees that the meaningful patches with a certain amount of edge structures will be involved in the training algorithm. In this chapter, only the patches with the intensity variance greater than a threshold σ = 4 are kept.

Experimental Setup

Several parameters should be selected carefully: dictionary size D, size of image patch M , values of the regularization parameters, and the related parameters in the NS and LR models, such as number of similar patches and number of clusters. By conducting a wide range of experiments, all the parameters are carefully tuned according to their best performance. The parameters ξ, h, λ x , λ y , λ m , γ, λ nl , a and b are evaluated by varying one of the parameters, and keeping the others constant. By conducting a wide range of experiments, these parameters are selected as 0.02, 65, 0.01, 0.01, 0.1, 0.1, 0.1, 0.8, and 0.2 respectively. It should be noted that the parameter λ s in Equations (4.9), (4.15), and (4.17) are related to the number of non-zero entities (S) in the corresponding sparse representation vector. In our implementation, we set S as the nearest integer number to M/4. This sparsity value guarantees to capture the important component of the corresponding patch.

In the JSR model, the dictionary size and patch size would jointly influence the quality of the bases in the dictionary pair and also the precision of the corresponding mappings, thus having a great effect on the EC quality. In the following sections, the influence of these parameters on the EC performance is analyzed. In each experiment, the test images are corrupted with the isolated loss pattern and restored by the proposed JSR-based EC method. successive iteration falls below a predefined threshold ( = 0.005), the recovery algorithm is stopped. All above-mentioned parameters are fixed for all the experiments throughout this chpater.

EC Quality

The performance of the proposed JSR+NL algorithm is compared with those of other stateof-the-art EC techniques, including non-normative spatial EC for H.264 (AVC) [START_REF] Varsa | Non-normative error concealment algorithms[END_REF], EC using projections onto convex sets (POCS) [START_REF] Sun | Concealment of damaged block transform coded images using projections onto convex sets[END_REF], content adaptive technique (CAD) [START_REF] Rongfu | Content-adaptive spatial error concealment for video communication[END_REF],

edge recovery technique based on visual clearness (VC) [105], Markov Random Fields approach (MRF) [START_REF] Shirani | An adaptive markov random field based error concealment method for video communication in an error prone environment[END_REF], multivariate kernel density estimation (MKDE) [START_REF] Koloda | Kernel-based MMSE multimedia signal reconstruction and its application to spatial error concealment[END_REF], sparse linear MKDE, SLP, and LSR can preserve more image details. However, these algorithms blur the image edges. In contrast, the ALP algorithm is more effective in reconstruction of both the smooth area and the complex regions, including texture and edges. Similar to the ALP algorithm, the proposed JSR+NL method achieves much better results than the others. Evidently, it can preserve most of image details and sharper image edges and generates much less artifacts, leading to visually much more pleasant recovery. It can also be observed that the JSR-based EC scheme can well reconstruct the image. However, there are some artifacts around the edges.

The superior performance of the proposed JSR+NL algorithm comes from both the joint sparse representation modeling and the natural image priors of the non-local selfsimilarity and the local structural regularity. By analyzing the objective and subjective results, the following observations are made: 1) In general, the JSR-based EC approach performs better as compared to the interpolation based methods like SLP and statistical based methods like MKDE, although its performance is comparable with that of ALP.

2) By incorporating the local and non-local models into the recovery phase, the image quality can be further improved. Using the NS and LR models lead to the consistent good performance.

Computational Costs

The run time of the proposed JSR+NL algorithm is compared with the state-of-the-art EC methods in Table 4.4 for the random loss pattern (PLR=30%) on a typical computer (Intel(R) Xeon(R) CPU @ 3.20 GHz 8 GB RAM) based on a non-optimized MATLAB implementation. A similar random loss pattern is used for all the above-mentioned algorithms and the average run time over 10 trials is given for each algorithm. It can be seen that the proposed algorithm is much faster than the recently proposed ALP algorithm, which is the best among the competing algorithms. Although, the proposed JSR+NL algorithm has a considerably large error recovery time in comparison with the AVC, CAD and MRF methods, its advantage in precisely estimation of the corrupted information is obvious in terms of objective evaluations.

It should be noted that the dictionaries and mappings are trained offline and the computational cost of the proposed JSR+NL algorithm is usually dominated by the computation of the sparse representation of the input patches using the OMP algorithm. In the worst case, B 2 vectors should be obtained via (4.18) for each lost block of size B × B. The computational cost of the sparse representation is also proportional to the dictionary and patch sizes. As discussed before, we set D = 256 and M = 25 to balance the EC quality and the reconstruction time. Further, the NS and LR models add additional computational costs which come from the iterative shrinkage algorithm [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF] and also finding the similar patches for the NS model and searching the best LR model for each patch.

However, our approach can be modified in order to reduce the recovery time as following:

• When building the patch y, one can consider more corrupted pixels P in the patch to be recovered. This approach reduces the number of vectors to be recovered for each lost block. In this chapter, we consider P = 4. It is also possible to decrease the overlap depth between the adjacent subblocks (see Section 4.2.4).

• The algorithm could be optimized by using a fast NS algorithm [START_REF] Zhang | Learning multiple linear mappings for efficient single image super-resolution[END_REF]. Further, for faster computation of the LR models, one can obtain one LR model for all the pixels in the input patch, instead of finding different LR models for each pixel.

• The computational burden of the recovery process is substantially increased using the iterative shrinkage algorithm [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF]. For decreasing the complexity, the receiver can early terminate the iterations, depending on its computational power, and yet obtain a visually satisfactory image reconstruction.

• The proposed method can be easily executed in parallel manner and obtain an acceptable computational cost using an array of multiple instructions multiple data (MIMD)-based parallel processors.

Finally, it should be noted that the initial interpolation by [START_REF] Shirani | An adaptive markov random field based error concealment method for video communication in an error prone environment[END_REF] simplifies much of the subsequent work without any computational cost. If the initial reconstructed image has a lower quality, it leads to a final low quality recovered image, reconstructed by the JSR algorithm. However, the second part of our algorithm can compensate this quality loss with a larger number of iterations that leads to a slower reconstruction. So, this initial reconstructed image influences the computational cost of the algorithm. In fact, the higher the initial recovery quality, the faster the eventual recovery algorithm. We use the algorithm in [START_REF] Shirani | An adaptive markov random field based error concealment method for video communication in an error prone environment[END_REF] for the initial recovery that gives us an acceptable reconstruction time for the JSR-NL algorithm. How to choose the initial recovery algorithm to guarantee the low computational cost and how to make the algorithm less sensitive to the initial reconstruction, and more generally, to noise, will be part of our future research.

Performance Analysis of the Proposed Algorithm

The proposed method offers several benefits. Firstly, learning a separate dictionary for each domain preserves the main structure of the data in the both domains, which can be represented well by sparse linear combinations of the dictionary atoms. Further, learning a mapping function in the sparse representation domain makes it more accurate since the irrelevant information in the spatial domain is discarded. We have introduced several mapping approaches in Section 4.2.2 which relate the sparse representations of the original and corrupted patches in different ways. In this section, the effect of the employed common space mapping, defined in (4.4), on the EC performance is evaluated in comparison with the direct mapping, defined by the term (4.3). We also evaluate the EC performance of the proposed coupling method in [START_REF] Akbari | Image error concealment using sparse representations over a trained dictionary[END_REF], wherein the mapping matrix M in (4.3) is set as an identity matrix.

Table 4.5 reports the experimental results in terms of PSNR, where the image Lena is corrupted with the random loss pattern at different PLRs, ranging from 10% until 50%. The image is concealed using the JSR-based EC algorithm with above coupling terms. "JSR-I", "JSR-D", and "JSR-C" means mapping with the identity matrix, direct mapping, and common space mapping, respectively. It can be observed that coupling of the sparse coefficients using a common space performs better error recovery than other coupling methods. The reason is that transferring the sparse representations into a common space provides more freedom to uncover the relationships between the sparse coefficients of the original and corrupted patches. It means that using an accurate coupling term in the objective function (4.5) plays an important role in the enhancement of error recovery.

Inroduction

In Chapter 4, an receiver-based error concealment (EC) technique was proposed. However, the annoying visual artifacts can still be observed for the high loss scenarios. In this chapter, another error recovery algorithm is proposed in which a high quality image is guaranteed, even at the high packet loss rates, at the expense of a simple modification at the transmitter. The proposed approach is motivated by the recent results in the compressed sensing theory [START_REF] Donoho | Compressed sensing[END_REF][START_REF] Laska | Democracy in action: Quantization, saturation, and compressive sensing[END_REF], which suggest that, under some mild conditions, the sparse signal can be recovered from far fewer measurements of it.

This chapter of the thesis answers the following question: Is it possible to model the error recovery scheme as an analysis sparse recovery framework; thereby, recovery of the lost information is efficiently achieved by the correctly received data? In the sequel, the proposed EC scheme will show that one may employ a simple linear projection to the signal Chapter 5. Transmitter-based Error Concealment to be transmitted in order to mitigate the negative effects of the packet loss caused by the channel impairments. Especially, the proposed algorithm projects signal's components into a random basis, such that each generated projection contributes equally to the transmitted information. If some of these projection are discarded, the signal can still be recovered, as a sufficient amount of information about the signal is maintained in the correctly received projections. At the receiver, the proposed approach simply discards the lost coefficients and models the problem of error recovery as a sparse image reconstruction framework using the remaining, received linear coefficients.

Furthermore, the proposed algorithm provides a more robust image transmission by partitioning the wavelet coefficients into sparse trees followed by the linear random projector and a simple packetization scheme, at the transmitter side. The sparse image recovery is achieved by adaptation of a well-known iterative sparse reconstruction to the defined tree structure in the wavelet domain. Different from the receiver-based algorithm, proposed in the Chapter 4, wherein the synthesis signal modeling has been done at the receiver side, the proposed scheme benefits from the analysis signal modeling at the transmitter side and implicitly mathematical modeling of the EC scheme as an analysis sparse recovery framework at the receiver. For this reason, the proposed method is named Analysis Sparse Recovery-based error concealment (SREC).

Analysis Sparse Recovery-based EC

In the sequel, the adaptation of the analysis sparse recovery for the image EC is investigated.

Transmitter Side

As shown in Fig. 5.1, the key operations of the proposed SREC algorithm at the encoder side consist of dividing wavelet coefficients into non-overlapping spatial groups which are further projected onto a random basis independently. The projected groups are then packetized appropriately prior to transmission over a Gaussian channel.

I. Partitioning of Wavelet Coefficients

First, an L-level 2D-wavelet decomposition Ω is applied to an image of size R × C pixels to decompose it into 3L + 1 subbands, i.e. X = Ωx, where X denotes the wavelet coefficients. Based on the well-known spatial-frequency relationship among the wavelet coefficients [START_REF] Said | A new, fast, and efficient image codec based on set partitioning in hierarchical trees[END_REF],

different structures are defined in [START_REF] Said | A new, fast, and efficient image codec based on set partitioning in hierarchical trees[END_REF][START_REF] Yang | Robust transmission of SPIHT-coded images over packet networks[END_REF] in which the wavelet coefficients that bear the information associated with the same location and orientation across the wavelet subbands are grouped into a wavelet tree structure. The proposed algorithm exploits this spatialfrequency relationship of the wavelet coefficients and defines a different tree structure, called Spatial Tree (ST). Instead of creating the tree in a certain orientation, the ST is branched across three dimensions (horizontal, vertical, or diagonal) on the hierarchical pyramid that is more appropriate for the sparse recovery.

The ST is rooted by one coefficient at the lowest frequency subband and then branched to three corresponding coefficients in the same relative position in each of the other three lowest level subbands. These three coefficients are considered as the offspring of the root coefficient. Each of these three nodes and all the subsequent coefficients in the higher subbands have four offspring grouped in 2 × 2 adjacent coefficients in the same relative position in the next higher level subbands of the pyramid. The union of the root and its entire offspring gives the ST structure. An example of a single ST in the wavelet transform domain is shown in Fig. 5.2(b). It should be noted that this partitioning structure partitions the wavelet coefficients into non-overlapping groups.

If the arrangement of one ST's wavelet coefficients is changed, as shown in Fig. 5.2(c), they constitute a block, called Spatial Block (SB). Conceptually, each SB contains the frequency components corresponding to a block of the same size in the pixel domain. Using an L-level wavelet decomposition, the size of one SB is 2 L × 2 L . Note that the SB can be generated by one or m × n adjacent STs. In this case, the size of the SB would be m2 L ×n2 L . The number of decomposition levels (L) and the number of trees generating a SB (T SB ) are chosen to meet a desired block size, typically 8 × 8, 16 × 16, or 32 × 32.

II. Linear Encoding of Wavelet Coefficients

Suppose S 1 , S 2 , • • • S T denote the SBs, where T is the number of generated SBs. T is equal to N LL /mn, where N LL is the number of coefficients in the lowest frequency subband

(N LL = RC/4 L ). Assume Z i , i = 1, 2, • • • T is a vector of size N × 1 representing, in
a raster-scan fashion, the wavelet coefficients of the corresponding SB, i.e. S i , where

N = mn4 L ). Each Z i is then projected onto a basis Φ i of size N × N by P i = Φ i Z i
to obtain the projection vector P i of size N . Φ i is a random matrix whose entries are independently Gaussian distributed with unit variance. We assume Φ i is also chosen to be orthonormal (Φ T i Φ i = I, where I is identity matrix.) This is done by orthonormalizing the rows of the above Gaussian matrix.

Generating the linear coefficients using the random matrix Φ i provides two significant properties associated with the entries of each P i . First, each entry of P i carries roughly the same amount of information about the corresponding SB (S i ). This property is called democracy property [START_REF] Laska | Democracy in action: Quantization, saturation, and compressive sensing[END_REF]. Second, each entry of one P i picks up a little bit of information about the relating SB (S i ) [START_REF] Romberg | Imaging via compressive sampling[END_REF]. As will be discussed in the next section, these properties enable the decoder to still achieve accurate recovery of the wavelet coefficients of the SBs so long as enough, but not fully, entries of each P i are received.

III. Packetization

In the following, the packetization algorithm is discussed. The packetization scheme involves distribution of the entries of P i -s into packets in a way that reduces the impact of the packet loss to the image quality. To further enhance both robustness and image quality of the proposed method, the entries of the projections vectors, P i -s, are evenly spread among the packets, so that no two coefficients from a certain projection vector appear in the same packet. The allocation process can be seen in Fig. 5. [START_REF] Elad | Analysis versus synthesis in signal priors[END_REF], where all the underlying coefficients assigned to a particular packet are denoted by the same shade pattern. If each This type of packetization ensures that if one packet is lost, only one entry of the P i , belonging to that packet, is lost. Then, only a fraction of entries of each P i is lost due to the packet loss, especially in the case of burst errors, thus preserving more entries of each P i for the image recovery. Furthermore, it mitigates the simultaneous loss of the whole coefficients for a certain P i , the fact that would have an impact on the performance of the proposed error recovery algorithm.

Due to the democracy property of the linear projections in the P i -s [START_REF] Laska | Democracy in action: Quantization, saturation, and compressive sensing[END_REF], the generated packets are expected to share the information equivalently, and thus there is no need to transmit the packets with priority, opposed to other encoding and packetization methods [START_REF] Kim | Error-resilient image and video transmission over the internet using unequal error protection[END_REF] that generate unequally important packets (i.e. , unequal protection over the noisy channel is mandatory in these schemes). In the proposed approach, therefore, the image quality is proportional to the number of received packets and not to specific Chapter 5. Transmitter-based Error Concealment packets [START_REF] Kim | Classified zerotree wavelet image coding and adaptive packetization for low-bit-rate transport[END_REF]. This type of packetization in connection with the linear projection of the wavelet coefficients introduces more robustness and error-resilience into the transmission system and ensures that a high quality image can be recovered, even for the high packet loss rates.

Receiver Side

At the receiver, the decoder can easily recover each SB as:

Zi = Φ -1 i Ṗi , (5.1)
where Ṗi denotes the received projections vector which equals the P i in a lossless channel.

Reconstruction via (5.1) leads to a low quality image in the case of transmission over an error-prone channel. But how does the proposed SREC method help the decoder in a lossy channel? In fact, the random and linear nature of the projected coefficients of each

I. EC via Sparse Recovery

Assume E i is a length-N binary vector with 1 at the position of the correctly received entries of the corresponding P i . It should be noted that the loss pattern in each E i can be detected easily. Since each packet is sequentially numbered before the transmission at the encoder side, the locations of the lost coefficients of each P i are easily identified at the decoder during the depacketization step. Consider Γ i ⊂ {1, 2, • • • N } whose entries denote the set of indices corresponding to the correctly received entries of the P i . Then, the received Ṗi , at the decoder side, is:

Ṗi = E i • * P i = E i • * (Φ i Z i ) = Φi Z i , (5.2)
where • * denotes an element-wise matrix product. It should be noted that the matrix Φi equals with the matrix Φ i for the rows indexed by Γ i and it is zero for the remaining ones.

By Φ i , we mean a |Γ i | × N matrix (CM) by Γ i . Then, Eq. (5.2) can be reformulated as:

P i = Φ i Z i , (5.3)
where P i is a |Γ i | × 1 vector obtained by removing the zero elements from the Ṗi . Here, the object is to recover Z i from P i . In this undetermined linear system, the number of unknowns is much larger than the received coefficients. To cope with the ill-posed nature of this inverse problem, as discussed in Section 2.4, the regularization-based technique leads to the following minimization problem:

Zi = arg min Z i ∈R N P i -Φ i Z i 2 2 + λ Z i 1 , (5.4)
where λ is the regularization parameter. It should be noted that the analysis sparse modeling has been implicitly done by using the wavelet basis at the transmitter side, in contrast to the algorithm, proposed in Chapter 4, that synthesis sparse modeling is achieved at the receiver side.

II. Recovery Algorithm

In sequel, a specific instance of the projected Landweber algorithm [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF], as decribed in Section 2.6, is adopted for the sparse recovery of the wavelet coefficients to find a solution for the cost function (5.4). At the receiver side, when all P i -s and their corresponding Φ i -s are extracted, the reconstruction is finally achieved by the adaptation of the PL in a way to accommodate the situation in which the sparse reconstruction takes place within the defined tree structure in the wavelet domain. The recovery algorithm also involves a thresholding procedure to accelerate the convergence of the LP algorithm. It tries to approach the minimizer of (5.4) by an iterative process which goes as follows.

For sake of simplicity, it is focused on a single iteration. Each iteration includes two stages as follows: first, the algorithm employs the PL algorithm on each SB separately in the form of

Z[k+1] i = Z[k] i + Φ T i (P i -Φ i Z[k] i ). Z[k]
i of size N × 1 represents, in a rasterscan fashion, the reconstructed wavelet coefficients of the corresponding SB, i.e. S i at the k -th iteration. At each iteration, the back projection term of

Φ T i (P i -Φ i Z[k] i
) is a distance measure to the previous solution. When added to the resulting solution at the k -th iteration, it promotes proximity between subsequent estimates of the iterative process.

In the next step, after rearranging the SBs into the corresponding spatial trees in the full-wavelet decomposition plane, the bivariate shrinkage thresholding process, as discussed Chapter 5. Transmitter-based Error Concealment in [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF], is interleaved with the PL stage in order to promote the sparsity in the domain of full-image wavelet transform. The thresholding step enforces prior information (sparsity) on the Z i -s to be reconstructed in order to accelerate the convergence of the LP iteration by simply setting some weights to the reconstructed coefficients, benefiting from the property of spatial localization of the wavelet coefficients. Finally, the L-level inverse wavelet transform is applied to the reconstructed wavelet coefficients X to obtain the concealed image x. The complete details of the recovery algorithm are described in Algorithm 4.

T hreshold(•) in Line 11 denotes the thresholding process used to provide the requisite sparsity constraint. In the proposed algorithm, the decoder terminates the recovery pro-

cess when x[k+1] -x[k]
2 ≤ 0.001. However, decoder can early terminate the iterations depending on its hardware limitations. It should be noted that the PL loop is independently applied on each SB. After reconstruction of all SBs at k -iteration, the resulting SBs should be transformed back into the full-wavelet plane in order to employ thresholding.

As shown in Fig. 5.2(c), each recovered SB corresponds to one block of the same size in the original image. Then, the appearance of the blocking artifacts is predictable, especially for the high packet loss rates. As will be shown in the next section, the proposed recovery method does not introduce the blocking artifacts. In fact, the inverse wavelet transform performs a weighted average of the reconstructed coefficients within the filter span. Thus, the wavelet coefficients relating to the neighboring STs contribute to the values of pixels in the block boundaries in the spatial domain.

Discussion

I. Recovery Stability and Error Robustness

As mentioned in Section 5.2.2, the recovery algorithm 4 is a specific instance of the PL algorithm [START_REF] Mun | Block compressed sensing of images using directional transforms[END_REF]. The convergence of this algorithm has been well proven in [START_REF] Blumensath | Iterative thresholding for sparse approximations[END_REF] and [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF],

if the restricted isometry property (RIP) holds and signal has enough sparsity level. As discussed in the Section 5.2.2, Φ i , which is a submatrix of Φ i and made up of rows corresponding to the coefficients that were not lost, must hold the RIP property in order to be able to recover a sparse signal. In the proposed algorithm, Φ i is a random matrix whose entries are independent realizations of a Gaussian distribution; then, with high probability, all

|Γ i | × N submatrices (Φ i ) of Φ i satisfy the RIP, provided |Γ i | ≥ O(K i log(N/K i )),
where K i is the sparsity level of the corresponding SB (see Appendix).

Moreover, the wavelet coefficients of the natural signals (voice, image and video) are Extract SBs:

Z[k] i (i = 1, 2, • • • T ) 6:
Compute PL for each SB:

7:

For i ← 1 to T do 8:

Z[k+1] i = Z[k] i + Φ T i (P i -Φ i Z[k] i ) 9:
End 10:

Reshape the SBs into full-wavelet plane:

X[k+1] 11:
Control the sparsity: Threshold( X[k+1] )

12:

Apply inverse wavelet decomposition:

13:

x

[k+1] = Ω -1 X[k+1] 14: Until x[k+1] -x[k] 2 ≤ 0.001
known for being compressible [START_REF] Devore | Image compression through wavelet transform coding[END_REF]. Fig. 5.2(a) illustrates this property, that is, the subbands contain large values at the low frequencies and decreasing values as the frequency of subbands increases. As a consequence, the defined tree structure (SB) (and then the corresponding Z i ) provides approximately K i -sparse structures (i.e. K i N ) and gives a guarantee for recovering the image using only a fraction of the correctly received information.

For description that the PL loop, including in the algorithm 4, guarantees the improvement in each iteration, it can be written that

Z[k+1] i - Z[k] i 2 ≤ I -Φ T i Φ i ( Z[k] i - Z[k-1] i ) 2 ≤ ( Z[k] i - Z[k-1] i ) 2 .
(5.5)

By replacing Z[k+1] i - Z[k] i = Φ T i (P i -Φ i Z[k] i ) and Z[k] i - Z[k-1] i = Φ T i (P i -Φ i Z[k-1] i ),
it can be easily found that the algorithm converges as k → ∞. It should be noted that the inequality is a consequence of the condition Φ i 2 ≤ 1, which ensures that the term I -Φ T i Φ i is positive definite. Furthermore, it will be experimentally discussed in the Section 5.2.4 that the accuracy of the reconstructed image is further improved iteration by iteration.

Instead of using Gaussian matrix Φ i , a more general class of sub-Gaussian matrices, such as i.i.d ±1 Rademacher matrix, can also be used in the proposed algorithm, given that any arbitrary subset of their rows satisfy the RIP property [START_REF] Laska | Democracy in action: Quantization, saturation, and compressive sensing[END_REF].

II. Distortion Estimation

To evaluate the effectiveness of the proposed SREC algorithm, it is assumed that the packets are transmitted through a memoryless channel with a probability of the packet loss given by a parameter . The object is to calculate the expected value of the correctly received coefficients for each SB. The probability of correctly receiving k out of N coefficients in each SB is given by the probability mass function:

Pr(k) = N k (1 -) k N -k . (5.6)
According to this formula, there are N k different ways of receiving exactly k coefficients with probability of (1 -) k and N -k failures with probability of N -k . The expected value of the correctly received coefficients for each SB can now be calculated as:

M = N k=0 kPr(k).
(

Moreover, according to the Theorem 1.1 in [START_REF] Candes | Near-optimal signal recovery from random projections: Universal encoding strategies?[END_REF] (see Appendix), the reconstruction error for each SB obeys:

Z i -Zi 2 ≤ C( M log N ) -r r = 1 β i - 1 2 , (5.8)
where 0 < β i < 1 and C is a fixed constant depending on β i . β i is selected such that the r-th largest component of the Z i holds Z i (r) ≤ αr -1/β i , where α is a constant. Therefore, β i is relating to the sparsity level of the corresponding SB; larger values for the highly textured SBs and lower values for the smoothed SBs are assigned. It results from the Parseval's theorem that the overall distortion of the reconstructed image can be calculated as:

x -x 2 = T i=1 Z i -Zi 2 ≤ D exp = C ( M log N ) -r , (5.9)
where r = 1 β -1 2 and T , as defined in the Section 5.2.1, represents the number of SBs. β is the average value of β i (i = 1, 2, • • • T ) and can be considered as a factor depending on the sparsity level of the full-wavelet coefficients. For the wavelet coefficients, β usually lies in the range of 0.3 < β < 0.7 [START_REF] Devore | Image compression through wavelet transform coding[END_REF]. C is a fixed constant depending on the β. D exp is thus considered as a bound of the expected reconstruction error and will be used in next section for evaluating the performance of the proposed SREC.

III. Compatibility

The proposed method can be easily extended to either spatial or other transform domains like Discrete Cosine Transform (DCT). It is just needed to apply the linear combination to the spatial or transformed blocks like DCT ones. What is important in the error recovery performane of the proposed method is that the blocks should be sparse in order to have a good recovery. As will be discussed in the Section 5.2.4, if the blocks are more sparse, the performance of the EC will be higher. In this chapter, the tree-sparse structure of the wavelet coefficients is explicitly exploited. In addition, the localization property of the wavelet transform achieves a superior sparsity in comparison with other transforms and allows more flexible representation based on the local signal characteristics. It also limits the effects of irregularities which are the main source of large coefficients [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF].

For an instance of compatibility of the proposed scheme, it can be easily extended for error protection of the intra frames encoded by the video coding standards, like MPEG, H.264, and HEVC. After partitioning the frame, DCT transform and quantization steps, the random linear combinations of coefficients of each block are then adopted to provide a high error recovery capability for the intra frames. This linear process coupled with the proposed simple packetization method introduces more robustness and error-resilience into the transmission system. At the receiver side, the sparse property of the DCT blocks is explicitly exploited in order to model the error recovery problem as a sparse recovery framework.

Experimental Results

In this section, the performance of the proposed EC technique described in the Section 5.2 will be evaluated via a suite of simulations carried out on a set of 8-bit grayscale standard images of size 512 × 512 pixels, as shown in Fig. 5.4(a), including Lena, Peppers, Goldhill, Barbara, and Mandrill. In each set of simulations, 10 trials are performed due to the random nature of packet loss then, the average performance is computed. In order to better take into account the stability and robustness of this recovery method, the Peak Signal-to-Noise Ratio (PSNR) and the Structural SIMilarity (SSIM) index [START_REF] Zhou Wang | Image quality assessment: from error visibility to structural similarity[END_REF] are chosen as objective measurements in the experiments. The SSIM index tends to automatically capture the visually important perception similarities (luminance, contrast, and structure) within the image and marginalize the influence of changes in the intensity; therefore, it provides a more pertinent perceptual quality measure [START_REF] Zhou Wang | Image quality assessment: from error visibility to structural similarity[END_REF]. Note that the SSIM index lies in [0, 1], a perfect image reconstruction having an SSIM index of 1.

Reconstruction Quality

A 4-level wavelet decomposition using the Daubechies biorthogonal 9/7 filter bank [START_REF] Antonini | Image coding using wavelet transform[END_REF] is applied to the original image, and then the SBs are extracted from the hierarchical subbands. In this set of experiments, each SB consists of only one spatial tree. In this case, 1024 16 × 16 SBs are constructed. Finally, the SBs are projected via a Gaussian random matrix Φ i . The packetization process is done as described in the Section III.

and each packet includes 4 coefficients. At this case, 65536 packets are generated. As mentioned before, no advantages are gained by using priority for the packet transmission.

A packet erasure channel model is implemented to evaluate the error robustness. The packets are randomly dropped according to a certain PLR, ranging from %10 to %80.

As we discussed in the Section III. , the generated packets are expected to share the information equivalently, and thus there is no need to transmit the packets with priority.

It means the performance of the proposed algorithm does not change, if the scenario of packet loss is changed.

The accuracy of the reconstructed image is improved iteration after each iteration. In As can be observed, more iterations are needed for the higher loss rates to satisfy the convergence condition. Generally, the computational burden of the recovery process is substantially increased using such iterative process. For decreasing the complexity, one receiver can early terminate the iterations, depending on its computational power, and yet obtain a visually satisfactory image reconstruction.

The reconstruction PSNR performance of the SREC at various PLR values, ranging from %10 to %80, is displayed in As can be seen, the PSNR and SSIM values for the received images decrease as the packet loss rate increases. However, the SREC algorithm provides surprisingly good performance in the high packet loss rates (where more than %50 of information is lost) due to the sparse property of the wavelet coefficients and the democratic characteristics of the linear random projections. Fig. 5.4(d) shows the concealed image for the loss scenario with %70 PLR that confirms the superior performance of the SREC for the high PLR values, subjectively.

For images with a small sparsity level, like highly textured images, more wavelet coefficients are needed for each SB to approximate the image with small errors. This also implies that more coefficients should arrive at the receiver end for an accurate recovery.

The plots in Fig. 5.6 reflect this scenario. For the same PLR, both PSNR and SSIM values for the Mandrill image are less than ones obtained for other images. From the objective results reported in Fig. 5.6 and the subjective results illustrated by the Fig. 5.4, it should be noted that considerable robustness is achieved at the expense of adding a simple random linear encoder at the transmitter side. In the sequel, other factors relevant to the system's performance are considered, including the wavelet functions and size of the generated SBs which is based on the number of wavelet decomposition levels (L) and the number of included spatial trees in each SB (T SB ).

Packet length Effect

Fig. 5.7 shows the performance of proposed EC method for different packet sizes for the Lena image at different PLRs. As can be observed in the Fig. 5.7, at a given PLR, there is no difference in the EC performance by changing the packet size. It can be concluded that the proposed scheme can be used in the networks in which the packets with different size can pass onwards. It should be taken into consideration that a larger packet carries more user data which brings greater efficiency in the network throughput. However using large packets are problematic in the presence of the communications errors. In fact, when a packet is corrupted at a certain time due to the corruptions in a communication network, more information is lost at the same time, when compared with a network in which smaller packet size is used.

Wavelet Functions Effect

The choice of wavelet function is a factor that influences the performance of the proposed SREC scheme. Therefore, it is of interest to investigate the relative impact of using different wavelet filters. In Tables 5 In the second set of experiments, the number of included spatial trees in each SB (T SB ) is fixed to 1 and different number of wavelet decomposition levels (3, 4, and 5) is applied.

In this scenario, the size of SBs will be 8 × 8, 16 × 16, and 32 × 32 pixels, respectively.

The impact of errors in the reconstructed image decreases as the number of decomposition levels increases, as can be seen in Table 5.4. This is due to the fact that when the size of SB is larger (either by increasing the L and/or T SB ), more sparse-tree structures would appear in each SB, and thus a better quality image is obtained when the same number of packets is lost (see Fig. 5.2).

In both above cases, the SB size has a great effect on the quality of the concealed image for the high packet loss rates, as can be observed in the Table 5.3 and 5.4 for the PLR = %80. However, it is worthy to note that a significant issue arises when the size of the SB increases. From the perspective of the practical implementation, the dimension of Φ i grows up as the size of SBs increases, which implies that more memory is needed to store

Comparison

The performance of proposed SREC is compared with other state-of-the-art EC techniques, such as content adaptive technique (CAD) [START_REF] Rongfu | Content-adaptive spatial error concealment for video communication[END_REF], Markov Random Fields approach (MRF) [START_REF] Shirani | An adaptive markov random field based error concealment method for video communication in an error prone environment[END_REF], sparse linear prediction (SLP) [START_REF] Koloda | Sequential error concealment for video/images by sparse linear prediction[END_REF], edge recovery technique based on visual clearness (VC) [105], frequency selective extrapolation (FSE) [114], multivariate kernel density estimation (MKDE) [START_REF] Koloda | Kernel-based MMSE multimedia signal reconstruction and its application to spatial error concealment[END_REF], and adaptive linear prediction (ALP) [START_REF] Liu | Spatial error concealment with an adaptive linear predictor[END_REF] 2 . We also compare with our JSR+NL algorithm that was peoposed in the previous chapter. In each trial, a similar random loss pattern is used for all algorithms and finally the average PSNR Visually, the existing approaches may address the error propagation at the high PLRs due to the incorrect estimation of the missing pixels, causing blocking artifacts and undesirable blurred details. These annoying visually artifacts can be observed for the high packet loss rates in the Fig. 5.8. In fact, these algorithms have not been designed for handling the large consecutive packet loss which usually occurs in the high PLR values. As can be observed, the restored image using the proposed algorithm is visually more plausible and coherent and has the most constant performance in concealing the smooth, edge and texture blocks, even for the high PLR values.

II. Reconstruction Time

The reconstruction complexity of the SREC is related to many factors, especially the number of iterations, which is depending on the PLR rate, as shown in Fig. 5.5(b), and the size of SBs. In Table 5.6, the run time of the Lena image reconstructed using several EC techniques is examined at %25 and %50 PLR on a typical computer (3.2 GHz Intel Xeon Core and 8 GB Memory) with a non-optimized MATLAB implementation. A similar random pattern is used for all the algorithms and finally the average run time over 10 trials are given. As can be observed, more time is consumed for %50 PLR. In addition, the reconstruction time decreases when the SB size increases. Indeed, the higher sparse-tree structure of larger SBs makes the PL algorithm converge faster. evaluations. Moreover, it is worthy to note that the time complexity of the SREC can be reduced by using an array of multiple instructions multiple data (MIMD) parallel processors. In the parallel implementation, each SB can be reconstructed independently by separate processors. An additional output processor must be used to organize the SBs and control the full-wavelet sparsity.

Conclusion

In this chapter, a novel approach to recovery of the lost information, occurred during image transmission over the error-prone channels, has been presented through modeling of the error recovery issue onto the sparse recovery framework. The proposed robust image transmission scheme achieves error robustness by partitioning the wavelet coefficients into the spatial trees and coding each tree in the form of an embedded linear coder followed by a simple packetization scheme. The core idea behind the proposed technique is the random linear projection of the spatial trees that provides a way to adapt the sparse recovery framework for recovering a high degree of the packet losses. This framework goes beyond simply assuming that the wavelet decomposition has a tree-sparse structure. At the receiver, the corrupted image is concealed using an iterative sparse reconstruction in the wavelet domain.

Performance of the proposed scheme and significant gains over existing EC techniques have also been demonstrated by various simulations of the proposed scheme. The ability of the proposed algorithm for the error protection for the high packet loss rates, combined with the property of being highly parallel-friendly, makes the algorithm a strong candidate for the image transmission on the error-prone channels.

Chapter 6. Sparse Representation-based Image Compression of the analytic dictionaries in the efficient expressiveness, an extensive body of literature has recently focused on the various applications of the synthesis sparse signal modeling via a trained dictionary. In this way, the performance can be significantly improved for the image compression application, benefiting the sparse representation of the image over a dictionary specifically adapted to it.

Related Work

In order to improve the limitations of the traditional sparse representation approaches over a trained dictionary, several studies have been conducted in the area of image compression.

In [START_REF] Gurumoorthy | A method for compact image representation using sparse matrix and tensor projections onto exemplar orthonormal bases[END_REF], a set of dictionaries are trained and the compression performance is improved by the sparse representation of each image patch over an optimal dictionary from the set of trained dictionaries to fit it efficiently. In [START_REF] Mazaheri | Learning a tree-structured dictionary for efficient image representation with adaptive sparse coding[END_REF], the authors propose a dictionary that consists of some sub-dictionaries in a tree structure. The dictionary in each tree level is learned from residuals of the previous level, thus using an adaptive sparse representation scheme implying the selection of the atoms among tree branches according to the sparsity of each level. In [START_REF] Sun | Dictionary learning for image coding based on multisample sparse representation[END_REF], multisample sparse representation (MSR) concept is introduced and incorporated into the dictionary learning process. The MSR considers encoding of the image patches with different sparsity levels. Instead of sparse representation of the patches independently, it handles multiple neighboring image patches to explore different sparse levels. In addition to this new learning dictionary algorithm, the authors propose an MSR-based image coding approach to image compression.

Contributions

Given a trained dictionary, the sparse representation of the image patches can be achieved in different ways such as the basis pursuit algorithms, matching pursuit techniques and other schemes [START_REF] Peyre | A review of adaptive image representations[END_REF]. However, the conventional sparse representation approaches consider a fixed number of atoms, called sparsity level, for all the image patches that can lead to a weak performance in the context of image compression. In this section, we adopt an adaptive sparse representation approach. From the view of biological vision and scientific analysis, the visual significance of each block (visual saliency) varies with its spatial position [START_REF] Borji | Salient oobject detection: A benchmark[END_REF].

Some regions can be more sensitive to the Human Visual System (HVS) (salient regions), while others have a lower level of visual interest. Therefore, it is necessary to design an adaptive sparse representation scheme by joining the sparse representation and the HVS characteristics in order to achieve an efficient compression performance. i=1 are encoded separately. The DC values are subsequently quantized and entropy coded and the AC values are sparsely represented over an overcomplete dictionary D of size N × K using the ROMP method [START_REF] Skretting | Image compression using learned dictionaries by rls-dla and compared with K-SVD[END_REF]. The dictionary is trained using the K-SVD dictionary learning algorithm [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF], which is supposed to be a general dictionary shared between encoder and decoder. Benefiting from the visual saliency information, an adaptive sparse representation scheme is incorporated into the image coding framework to encode AC components in order to further reduce the reconstructed errors.

Image Compression using Adaptive Sparse Representations over Trained

Finally, the obtained sparse coefficients C = [c i ] L i=1 are entropy coded, where c i ∈ K denotes the coefficients vector of the i -block. In the sequel, we propose to describe the adaptive sparse representation and entropy coding, respectively. At the decoder, the image can be easily retrieved by a minor application of the above steps.

Adaptive Synthesis Sparse Representation

To encode image patches effectively, the process of sparse representation plays an important role in the rate-distortion performance. Given the good performance of the Graph Based Visual Saliency (GBVS) model in [START_REF] Harel | Graph-based visual saliency[END_REF] that aims to predict the scene locations focused by a human observer, we propose to use it in the following in order to build up an adaptive synthesis sparse representation scheme to compress the image efficiently. Please refer to 3.1.3 for the details of the GVBS model. This saliency map of the image is exploited to determine the visual significance of the blocks in order to allocate different sparsity levels to each block according to its visual significance to the HVS.

In order to obtain the proper sparsity level for each block, the saliency map of the input image is normalized to [0, 1]. The output is a map where the intensity of each pixel represents the probability belonging that pixel to a salient region. By partitioning the saliency map into B × B non-overlapping blocks, the saliency value of the blocks are obtained by averaging the saliency values of pixels belonging to each block. Let H i represents the saliency value of i-th block. It should be noted that each block has a different saliency value and assigning the appropriate sparsity level to each block according to its saliency value will improve the reconstruction quality.

Let the sparsity level for block i be:

S i = α i S.
(6.1)

Our goal is thus to allocate a different sparsity level S i to each block while the overall sparsity level should be equal (or slightly inferior) to the target sparsity level S. Given a target sparsity level S and a set of saliency values [H i ] L i=1 , one can easily find:

α i = L × H i L i=1 H i . (6.2)
As a result, a set of sparsity levels [S i ] L i=1 is obtained via (6.1). Based on these new obtained sparsity levels, the sparse representation of each patch x i over the dictionary D is achieved by:

argmin c i x i -Dc i 2 Subject To c i 0 ≤ S i . (6.
3)

The ORMP method in [START_REF] Skretting | Image compression using learned dictionaries by rls-dla and compared with K-SVD[END_REF] is used to solve this problem. By assigning different sparsity level S i to each block, a more effective sparse representation of the image is obtained. . In order to efficiently compress them, a quad-tree splitting algorithm is used. At first, each vector c i is partitioned into two equal sections. Then, a binary test is done on each section: if the subsection includes at least one nonzero coefficient, the encoder inserts 1 at the output bitstream; otherwise, it is coded by 0. Each subsection including one or more nonzero coefficients, is again partioned into two subsections. This process continues until the maximum depth of partitioning is reached. This process encodes the indices of nonzero coefficients more efficient than the fixed length coding that is proposed in [START_REF] Sun | Dictionary learning for image coding based on multisample sparse representation[END_REF].

Experimental Results

In this section, the performance of the proposed approach is evaluated via a suite of simulations carried out on a set of 8-bit grayscale standard images of 512 × 512 pixel resolution, tion over the K-SVD dictionary, in which a fixed sparsity level is used in order to compress the images, induces larger reconstructed errors in comparison with the proposed adaptive sparse representation over the same dictionary. Thus, we incorporate the adaptivity into the sparse coding step and use it to compress natural images, achieving much reduced reconstructed errors. It can be concluded that if the salient parts are extracted accurately, better performance of the sparse representation can be realized that leads to the better rate-distortion performance. This leads to a better visual quality at low bit rate regime, which is more suitable for the band-limited transmission systems.

Conclusion

In this chapter, an adaptive sparse representation over a trained over-complete dictionary is proposed to compress the images. More specifically, in the proposed approach, given the saliency map of the image to be encoded, an image patch can be well represented with the linear combination of atoms selected from an overcomplete dictionary based on the sparsity level constrained by the proposed adaptive sparse representation. The experimental results demonstrated that the proposed image compression framework greatly outperforms some others such as JPEG and JPEG2000, which use an analytic dictionary, and the state-ofthe-art codecs based on a trained dictionary.

Chapter 7 Conclusion and Future Directions

Sparse signal modeling is a powerful and widely successful approach for efficient representing the natural signal phenomena. The idea of describing signals through a dictionary of the elementary atoms, controlled by the sparsity constraint, has had a profound impact on the research community, with applications spanning a wide scope of fields and tasks.

It has been used for tackling several image processing problems and is a key component of many state-of-the-art methods in the signal processing area. The two main directions of the dictionary-based models are the analysis and synthesis sparse signal representation via designing analytic (mathematical) and synthetic (trained) dictionaries.

A brief summary of the signal modeling methodology and its applications has been given at the first chapter of thesis. Then, several new CS reconstruction algorithms have been developed at the next chapter of thesis. First, a summary of the CS methodology and a brief description of the well-known BCS-SPL algorithm have been presented at the first part of this chapter. Inspired by the saliency based model of the visual attention, an adaptive BCS scheme has been introduced in order to enhance the reconstruction performance of the BCS-SPL algorithm. More specifically, based on a binary saliency map, obtained with a graph-based algorithm, the presented adaptive scheme enhances the recovery quality by finding an optimal subrate trade-off between the salient and non-salient areas. At the end part of the chapter, we have moved to the residual based CS reconstruction and extended the concept of prediction to the CS recovery. The idea is based on creating an optimal prediction comparable to the original image using the strong local correlation among neighboring blocks or exploiting the non-local self-similarities existing within natural images. This prediction is used to produce a measurement-domain residual which is more compressible, thus enhancing the quality of the reconstructed image. The efficiency of the above-mentioned methods has been evaluated via a wide range of experiments on several test images in comparison with the BCS-SPL algorithm.

In our second contribution, we moved to more implicit application of sparse represen-Finally, we ended with the explicit and straightforward formulation of the sparse representation being more suitable for the compression tasks. We have just focused on the synthesis-based signal modeling because of being mature of the image compression using the analysis-based sparse signal modeling. An adaptive sparse representation over a trained over-complete dictionary was proposed to compress the images. More specifically, given the saliency map of the image to be encoded, an image patch could be well represented with the linear combination of atoms selected from an overcomplete and trained dictionary based on the sparsity level constrained by the proposed method. The experimental results demonstrated that the proposed image compression framework greatly outperforms image coding standards, such as JPEG and JPEG2000, which use an analytic dictionary, and also the state-of-the-art codecs based on trained dictionaries.

To summarize, this thesis exposes three contributions of this thesis so far:

• It introduces several concepts for the CS reconstruction in order to improve the quality of the reconstructed image.

• It introduces several formulation to exploit both the analysis and synthesis sparse coding for the image EC.

• It introduces a formulation to exploit the synthesis-based sparse coding for the image compression.

Future Works

Video EC Typical error control techniques do not very well suit for video transmission. On the other hand, video transmission over error prone channels has increased greatly, e.g., over IP and wireless networks. These two facts combined together provided the necessary motivation for the development of a new set of EC techniques capable of dealing with transmission errors in video systems.

Video coding standards such as HEVC (H.265) rely on predictive coding to achieve high compression efficiency. Predictive coding consists of predicting each frame using preceding frames. However, predictive coding incurs a cost when transmitting over unreliable networks: the frames are no longer independent and the loss of data in one frame may affect future frames. The study of the effectiveness of sparse signal modeling in mitigating the effect of errors on the decoded video can be considered as one of solutions to improve the EC on HEVC decoders. The way to work in this situation is to realize that a real video signal varies very smoothly both in time and space, which means that spatial and temporal information correctly received, in the neighborhood of the affected area of an image, can be used to dissimulate the effects of the transmission errors. A sparse signal model for video data can be obtained offline and is thereafter utilized online in order to restore lost blocks from spatial and temporal surrounding information.

The proposed EC algorithm in the Chapter 4 can be efficiently used to compensate a lost macroblock in intra-coded frames (I-frames), in which no useful temporal information is available. This algorithm can be also easily extended for replenishing missing pixels in a lost macroblock of inter-coded frames (P-frames) with the information in previous frames. For the error concealment of P-frames, temporal, as well as spatial, information is available. In fact, temporal correlation is much higher than spatial correlation in real world image sequences so that P-frames can be more effectively concealed than I-frames.

Multiview Image CS

Multi-view image and video streaming has the potential to enable a new generation of efficient and low-power pervasive surveillance systems that can capture scenes of interest from multiple perspectives, at higher resolution, and with lower energy consumption. However, state-of-the-art multiview image coding architectures require relatively complex predictive encoders, thus resulting in high processing complexity and power requirements. Recently, a new encoding and decoding architecture for multiview video systems based on the CS principles has been proposed in order to overcome many limitations of traditional encoding techniques, specifically massive storage requirements and high computational complexity Next on our future work is to include the image prediction techniques, proposed in the Chapter 3 into multiview image CS reconstruction to exploit the high degree of interview and temporal correlation common to multiview scenarios. The high degree of correlation between views can be efficiently exploited to enhance recovery performance over straightforward independent view recovery. Instead of recovering each individual frame independently, neighboring frames in both the view and temporal directions are used to calculate a prediction of a target frame, and the difference is used to drive a residual-based compressed-sensing reconstruction. Especially, group sparse representation modeling can be exploited for the CR recovery. Grouping similar patches together coupled with learn-ing the adaptive basis from the similar groups, gets sparser representation and thereby performs better in CS recovery.

Fast and improved EC

In the Chapter 4, we start from a large collection of image patches and use a sparsity constraint to jointly train two dictionaries so that they are able to represent corrupted patches and their corresponding original counterparts using sparse representation coefficients and two mapping matrices. Once the dictionaries are trained, the algorithm searches for a sparse representation of each input patch. Then, the sparse representation of the original patch is obtained by multiplication of the sparse representation of the input patch and mapping function. Other approach as a future work would be to cluster the training image patches into a relatively small number of groups and to learn a separate mapping from corrupted patch space to original patch space for each cluster. The mapping coefficients can be learned offline and stored for each cluster.

6. 1 3 . 1

 131 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Image Compression using Adaptive Sparse Representations . . . . . . . . . 6.2.1 Adaptive Synthesis Sparse Representation . . . . . . . . . . . . . . . 6.2.2 Quantization and Entropy Coding . . . . . . . . . . . . . . . . . . . 6.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Block diagram of the SBCS-SPL framework. . . . . . . . . . . . . . . . . . . 3.2 (a) Initial reconstructed images. (b) Corresponding saliency maps at the S = 0.3. The saliency maps were quantized for better display. . . . . . . . . 3.3 Effect of threshold value T on quality of the reconstructed image Lena in terms of PSNR at the overall subrate S = 0.3. . . . . . . . . . . . . . . . . . 3.4 Decay of the magnitudes of coefficients as compared to that of residual. . . 3.5 Block diagram of the BCS-IIP algorithm. . . . . . . . . . . . . . . . . . . . 3.6 8 surrounding blocks of the current block z. . . . . . . . . . . . . . . . . . . 3.7 Hamming weighting window. . . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 Corresponding weighting coefficients for 8 corresponding blocks. . . . . . . . 3.9 One image patch and its associated window for finding the similar patches. .3.10 Subjective results for the image Lena by different CS recovery techniques at the subrate S = 0.3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Typical block loss patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Structure of the corrupted patch y. Each square stands for one pixel. L denotes the lost block and S denotes the support area. . . . . . . . . . . . . 4.3 Block diagram of coupled dictionary learning algorithm using: (a) Direct mapping term, (b) Common space mapping term . . . . . . . . . . . . . . . 4.4 Block diagram of the proposed joint sparse representation based image EC algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Recovery order of an isolated lost 8 × 8-pixels block. The pixels illustrated by a brighter gray-level are recovered first. . . . . . . . . . . . . . . . . . . . 4.6 Search window of the NS model. The search window includes the area that is clean or already recovered. . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Target pixel and its causal neighbors (context) of the LR model. Each square stands for one pixel. . . . . . . . . . . . . . . . . . . . . . . . . . . . xi xii LIST OF FIGURES 4.8 8-bit grayscale test images of size 512 × 512. From left to right: Lena, Peppers, Goldhill, Mandrill, and Zelda. . . . . . . . . . . . . . . . . . . . . . 65 4.9 Subjective comparison between the proposed JSR+NL results and those of other EC techniques for random loss patterns with 30% PLR using Lena concealed image. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.1 Block diagram of the proposed SREC method . . . . . . . . . . . . . . . . . 77 5.2 Wavelet decomposition, spatial tree, and spatial block . . . . . . . . . . . . 79 5.3 Packetization scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.4 Subjective results for the test images. (a) Original image, (b) Received images with PLR = %30, (c) Concealed images with PLR = %30, (d) Concealed images with PLR = %70. From left to right: Lena, Peppers, Goldhill, Barbara, and Mandrill. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.5 Reconstruction quality (average PSNR) vs. iteration number at: (a) PLR = %30 for different test images and (b) for different PLR values for Lena image. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.6 Quality of received and concealed images vs. PLR (averaged values) in term of (a) PSNR (b) SSIM. Solid lines depict the quality of reconstructed images. Dotted line depicts the quality of the received images reconstructed by (5.1). Dashed line depicts the minimum expected quality (PSNR) obtained by (5.9). 89 5.7 Effect of packet length on the EC performance for the Lena image. . . . . . 90 5.8 Subjective comparison for Lena by different EC techniques with (a) %25 PLR, (b) %50 PLR, and (c) %75 PLR. . . . . . . . . . . . . . . . . . . . . . 95 6.1 Block diagram of the proposed image coding framework. . . . . . . . . . . . 101 6.2 The Original images and their saliency maps. . . . . . . . . . . . . . . . . . 103 6.3 Rate-distortion performance in terms of PSNR . . . . . . . . . . . . . . . . 105 List of Tables 3.1 Comparison of quality of reconstructed images by differenct CS recovery tecnique in terms of PSNR (dB) . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Averaged reconstruction time (second ) at various subrates for different CS reconstruction algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Effect of dictionary size on the EC quality using the JSR-based EC algorithm in terms of PSNR (M is set to 5) . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Effect of patch size on the EC quality using the JSR-based EC algorithm in terms of PSNR (best dictionary size is obtained for each patch size) . . . . . 4.3 PSNR and MSSIM Values of the concealed images using several EC techniques for different loss patterns (isolated loss, consecutive loss and random loss with 30% PLR) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Reconstruction time (in seconds) for the concealed image Lena using several EC techniques for different loss patterns (isolated loss, consecutive loss and random loss with 30% PLR) . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Effect of mapping approach on the EC performance (PSNR) for the image Lena at different PLRs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Average PSNR Values for Lena Image for Different Wavelet Functions . . . 5.2 Average SSIM values for Lena Image for Different Wavelet Functions . . . . 5.3 Effect of Number of Spatial Trees in each SB (T SB ) on Average PSNR Values for the Lena Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Effect of Number of Decomposition Levels (L) on Average PSNR Values for the Lena Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 Average PSNR and SSIM for Lena and Mandrill Images Reconstructed using Several EC Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Reconstruction Time (in Second) Obtained for Lena Image using Several EC Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  that are trained offline from external training images. In order to improve the accuracy and stability of the proposed JSR-based EC algorithm and avoid unexpected artifacts, the local and non-local priors are seamlessly integrated into the JSR model. The non-local prior is based on the self-similarity within natural images and helps to find an accurate sparse representation by taking a weighted average of similar areas throughout the image. The local prior is based on learning the local structural regularity of the natural images and helps to regularize the sparse representation, exploiting the strong correlation in the small local areas within the image.

Chapter 2 .

 2 Sparsity-Based Signal Models said to be complete. The representation coefficients vector c ∈ R K is obtained via c = Θ(x) = Ωx = D -1 x. Generally, in the orthogonal basis, D -1 = D T . It means each representation coefficient c i can be computed as inner product of the signal x and the i-th atoms of Ω.

• 6 • 6 3. 1 Introduction

 661 A. Akbari, M. Trocan, and B. Granado, "Image compressed sensed recovery using saliency-based adaptive sensing and residual reconstruction," in Compressed Sensing: Methods, Theory and Applications. New York: Nova Science Publishers, 2018 • A. Akbari, D. Mandache, M. Trocan, and B. Granado, "Adaptive saliencybased compressive sensing image reconstruction," in Proceedings of IEEE International Conference on Multimedia Expo Workshops (ICMEW), Seattle, WA, July 2016, pp. 1-D Mandache, A. Akbari, M. Trocan, and B. Granado, "Image compressed sensing recovery using intra-block prediction," in Proceedings of IEEE International Conference on Telecommunications Forum (TELFOR), Belgrade, Serbia, Nov. 2015, pp. 748-751 • A. Akbari, M. Trocan, and B. Granado, "Residual based compressed sensing recovery using sparse representations over a trained dictionary," in Proceedings of International ITG Conference on Systems, Communications and Coding (SCC), Hamburg, Germany, Feb. 2017, pp. 1-Signal models are fundamental tools for efficient signal processing, including audio recordings, natural images, video clips and medical scans, to name just a few. A signal model formulates a mathematical description of the family of interesting signals in a way which Chapter 3. Image Compressed Sensing Recovery faithfully captures their behavior. Designing accurate signal models, which efficiently capture the useful characteristics of the signals, has been a crucial aim in the signal processing

Figure 3 . 1 :

 31 Figure 3.1: Block diagram of the SBCS-SPL framework.

Figure 3 . 2 :

 32 Figure 3.2: (a) Initial reconstructed images. (b) Corresponding saliency maps at the S = 0.3. The saliency maps were quantized for better display.

Fig. 3 .

 3 Fig. 3.2 shows some initial reconstructed images and their corresponding saliency maps at the target subrate S = 0.3. Brighter regions in the saliency maps represent the salient area within the test images, while the darker sections show the less-saliency regions.

Figure 3 . 3 :

 33 Figure 3.3: Effect of threshold value T on quality of the reconstructed image Lena in terms of PSNR at the overall subrate S = 0.3.

Figure 3 . 4 :

 34 Figure 3.4: Decay of the magnitudes of coefficients as compared to that of residual.

Figure 3 . 5 :

 35 Figure 3.5: Block diagram of the BCS-IIP algorithm.

Figure 3 .

 3 Figure 3.6: 8 surrounding blocks of the current block z.

  and then the measurements are separately obtained for each block by ỹi = Φ b xi . Note that the same measurement matrix should be used for sensing the blocks in the original and predicted images. Given the measurements ỹi , a residual in the measurement domain is obtained for each block via r i = y i -ỹi . Given the measurement matrix Φ b and the measurement-domain residuals r = [r i ] L i=1 for all blocks within the image, the spatial-domain residual image is obtained using the BCS-SPL algorithm. Finally, the image is obtained by combining the prediction image x and the reconstructed residual

Figure 3 . 7 :

 37 Figure 3.7: Hamming weighting window.

Figure 3 . 8 :

 38 Figure 3.8: Corresponding weighting coefficients for 8 corresponding blocks.

  is a novel modeling technique of the natural images. In this technique, instead of modeling the single image patches, a group of non-local image patches with similar structures is considered as the basic unit of the sparse representation. Based on this concept, the GSR is used to obtain a prediction for each block. This prediction drives a residual-based CS reconstruction algorithm, called block-based CS reconstruction using group sparse representation (BCS-GSR). Assume the image x of size √ N × √ N pixels is partitioned into K non-overlapping blocks of size √ N b × √ N b pixels. Then, each block is sampled as y i = Φ b x i , where x i ∈ R N b is the vector representation of i-th block of the image, y i ∈ R M b is the measurement vector, and Φ b is the measurement matrix of size M b × N b . Assume all block are sampled at the same subrate; therefore, the overall subrate is S = M b /N b .

  images of size 512×512 pixels, including Lena, Peppers, Goldhill and Mandrill. The quality performance is assessed by the peak signal-to-noise ratio measure (PSNR) at different subrates S, ranging from 0.1 to 0.5. The performance of these algorithms is also compared with the BCS-SPL algorithm 1 . The same measurement matrix Φ b is employed for all competing algorithms. Due to the randomness of the measurement matrix Φ b , the PSNR values are obtained by running the the competing methods 10 times and the average results are reported as the final values.For all the competing algorithms, size of the non-overlapped blocks for the acquisition step at the sensor side is set to 32 × 32 pixels. In the SBCS-SPL algorithm, the sampling subrates of the salient and non-salient blocks, i.e. S s and S ns , respectively, are determined by the Equation (3.2) and the parameters K ns , K s , and K are set as 0.2, 0.8, and 0.2, respectively. In the BCS-IIP algorithm, size of the non-overlapped blocks for the prediction generation step is considered to 4 × 4 pixels and the parameter I for determination of the threshold T in (3.10) is set as 8. In the BCS-GSR algorithm, size of the overlapped image patches for the prediction generation step is considered to be 8 × 8 pixels and the overlapping depth between adjacent patches is set to 2 pixels. Further, size of the search window for finding the similar patches is set to be 40 × 40 pixels and number of the similar patches in each group H i is set to C = 60. Table3.1 gives the averaged PSNR values of the reconstructed images by different CS reconstruction techniques at various subrates, ranging from 0.1 to 0.5. As can be seen, performance of the SBCS-SPL, BCS-IIP, and BCS-GSR algorithms is better than the BCS-SPL algorithm. The results of the BCS-IIP algorithm are nearly similar to the BCS-SPL algorithm, with the PSNR improvement up to 0.25 dB. The PSNR improvement by the SBCS-SPL algorithm is between 0.1 dB to 1.3 dB. It can be concluded that if the salient parts are extracted accurately, better performance of the CS reconstruction can be realized.The results indicate that the BCS-GSR achieves the best performance at all subrates and can indeed help to significantly increase the reconstructed image quality in terms of PSNR, especially at the higher subrates. The BCS-GSR algorithm achieves up to 3.50 dB higher PSNR than the BCS-SPL algorithm.The enlarged parts of the reconstructed image Lena by different CS recovery algorithms are shown in Fig.3.10 at the target subrate S = 0.3. It can be generally inferred that the reconstruction error of the BCS-GSR method is lower, when it compared with the BCS-SPL algorithm. As can be seen, the fine details and sharper image edges in the salient regions of the image become much clearer compared with those by the other methods, especially in some complex regions which contain high frequencies (strong hairs).

Figure 3 . 10 :

 310 Figure 3.10: Subjective results for the image Lena by different CS recovery techniques at the subrate S = 0.3.

5 •

 5 based model of the visual attention, an adaptive BCS scheme has been introduced in order to enhance the reconstruction performance of the BCS-SPL algorithm. More specifically, based on a binary saliency map, obtained by a graph-based algorithm, the presented adaptive scheme enhances the recovery quality by finding an optimal subrate trade-off between the salient and non-salient areas. In the end part of the chapter, we have moved to the residual based CS reconstruction and extended the concept of prediction to the CS recovery. The idea is based on creating an optimal prediction comparable to the original image using the strong local correlation among neighboring blocks or exploiting the nonlocal self-similarities existing within natural images. This prediction is used to produce a measurement-domain residual which is more compressible, thus enhancing the quality of the reconstructed image. The efficiency of the above-mentioned methods has been evaluated via a wide range of experiments on several test images in comparison with the BCS-SPL algorithm.Chapter 4Receiver-based Error Concealment based onSynthesis Sparse RecoveryThe material of this part is essentially based on the following works: • A. Akbari, M. Trocan, and B. Granado, "Image error concealment using sparse representations over a trained dictionary," in Proceedings of IEEE Picture Coding Symposium (PCS), Nuremberg, Germany, Dec. 2016, pp. 1---, "Joint-domain dictionary learning-based error concealment using common space mapping," Proceedings of IEEE International Conference on Digital Signal Processing (DSP), pp. 1-5, Aug. 2017 • --, "Image error concealment based on joint sparse representation and non-local similarity," Proceedings of IEEE Global Conference on Signal and Information Processing (GlobalSIP), Nov. 2017 • A. Akbari, M. Trocan, S. Sanei, and B. Granado, "Joint sparse learning with nonlocal and local image priors for image error concealment," IEEE Transactions on Circuits and Systems for Video Technology, 2018 4.1 Introduction Image and video transmission over error-prone channels, such as communication networks, always suffers from packet loss, leading to serious distortions in the received image/video.

Figure 4 . 1 :

 41 Figure 4.1: Typical block loss patterns [97]: black blocks denote the corrupted blocks of size 8 pixels. (a) Isolated loss. (b) Consecutive loss. (c) Random loss.

4. 1 . 1

 11 Previous Works on Error Concealment Many EC approaches have been developed in the literature and newer techniques are still emerging. These methods can be classified into three categories: interpolation-based, statistical-based and sparse recovery-based methods. The simple interpolation-based methods typically exploit the strong correlation among the neighboring blocks in the image [101, 103-106]. Edge-directed interpolation-based EC

Figure 4 . 2 :

 42 Figure 4.2: Structure of the corrupted patch y. Each square stands for one pixel. L denotes the lost block and S denotes the support area.

4. 2 . 1

 21 Problem Formulation Let L denotes a B × B lost block in the corrupted image and S be the set of available pixels, called support area. Consider a corrupted patch of size √ M × √ M , represented as a column vector y = [u, v] T , where v ∈ R P is a group of P unknown pixels in L and u ∈ R M -P contains a set of adjacent and available pixels in S, as shown in Fig. 4.2. The image EC problem asks: given a corrupted image patch y, recover the original image patch

Fig. 4 . 1 ) 2 2 2 2

 4122 Fig. 4.1). The lost blocks are recovered by a simple interpolation algorithm to generate an initial estimation for each corrupted image. The image patches of size √ M × √ M , containing both known and corrupted pixels as shown in Fig. 4.2, are extracted and considered as the set of corrupted training patches. The corresponding image patches at the same locations in the original images are recorded as the set of original training patches. The mean intensity value of each patch is subtracted in order to improve the numerical stability of the dictionaries in representing the patch textures. Let X = [x i ] N i=1 and Y = [y i ] N i=1 denote the two generated training sets, where the vectors x i ∈ R M and y i ∈ R M are the vector representations of the i-th original patch and corresponding corrupted patch of size √ M × √ M , respectively. Suppose D x ∈ R M ×K and D y ∈ R M ×K denote the trained dictionaries for the sparse representation of the original and corrupted patches X and Y, respectively. These dictionaries are obtained by minimizing the following objective functions:

  with minimum error. The third term denotes the mapping fidelity term to represent energy associated with the mapping error between the sparse representations of the corrupted and original training patches. Moreover, The fourth and fifth terms ensure that the representations of the data in two modalities X and Y with respect to dictionaries D x and D y are sparse. The terms γ, λ x , and λ y balance the image representation and sparsity, respectively. The 2 -norms on M x and M y impose additional constraints, regularized by λ m , in order to provide numerical stability and avoid over-fitting.The objective function (4.5) is convex with respect to each of D x , D y , Λ x , Λ y , M x , and M y when the others are fixed. An effective way to tackle the energy-minimization of (4.5) is proposed as follows: first, the dictionary pair, D x and D y , and the mapping matrices, M x and M y , are initialized as PCA basis and identity matrix, respectively. Then, three following steps are iterated until convergence: (1) updating the sparse coefficients, Λ x and Λ y , by fixing D x , D y , M x , and M y ; (2) updating the dictionary pair, D x and D y , by fixing M x , M y , Λ x , and Λ y ; (3) updating the mapping matrices, M x and M y , by fixing D x ,

2 2 + x -D x α x 2 2 2 2

 222 x and D y , and the learned mappings M x and M y , the sparse representation of the corrupted patch y (as shown in the Fig. 4.2), can be easily converted to the sparse representation of the original patch using the following optimization problem: arg min αy,αx y -D y α y + γ M x α x -M y α y + λ y α y 1 + λ x α x 1 .(4.7)

Figure 4 . 3 :

 43 Figure 4.3: Block diagram of coupled dictionary learning algorithm using: (a) Direct mapping term, (b) Common space mapping term

Figure 4 . 4 :Fig. 4 .

 444 Figure 4.4: Block diagram of the proposed joint sparse representation based image EC algorithm.

Figure 4 . 5 :

 45 Figure 4.5: Recovery order of an isolated lost 8 × 8-pixels block. The pixels illustrated by a brighter gray-level are recovered first.

arg min αy y -D y α y 2 2

 2 + λ s α y 0 + λ nl P α y -(aβ ns + bβ lr ) 1 , (4.12) where β ns is the sparse representation vector of the estimated patch obtained via linear combination of the non-local similar patches within the image and β lr is the sparse representation vector of the estimated patch obtained from the local neighboring pixels. a and b are two constants balancing the contribution of the NS and LR models (a + b = 1).

Figure 4 . 6 :

 46 Figure 4.6: Search window of the NS model. The search window includes the area that is clean or already recovered.

  an external database of the high-quality training examples are used to obtain the weighting coefficients. Let S be an N ×Q matrix including N training vectors, extracted from a set of training images. Each row of S consists of a 1 × Q vector that includes the pixels in the context of a target pixels z, as shown in Fig. 4.7. Let z be an N × 1 vector including the corresponding target pixels. Intuitively, the training vectors in the matrix S are grouped into several clusters, and then an LR model is learned for each cluster. In this chapter, the wellknown K-means algorithm [136] is used for clustering. Let S = {S 1 , S 2 , • • • , S C }, where S k ∈ R N k ×Q represents submatrix of N k training vectors in the matrix S which belongs to the cluster k and C is the total number of clusters. The weighting coefficients of the LR model of the k-th cluster, denoted by Q × 1 column vector a k , is obtained by solving the following least squares minimization problem: a = arg min a z k -S k a 2 2 , (4.16)

  )

Figure 4 . 7 :

 47 Figure 4.7: Target pixel and its causal neighbors (context) of the LR model. Each square stands for one pixel.

y

  . Based on the x [0] , initial non-local estimation of β ns and local prediction of β lr , i.e. β

D y α y 2 2

 2 + λ nl Pα y -aβ[l]

Figure 4 . 8 : 8 -

 488 Figure 4.8: 8-bit grayscale test images of size 512 × 512. From left to right: Lena, Peppers, Goldhill, Mandrill, and Zelda.

presented in Sections 4 .

 4 2 and 4.3 respectively, are evaluated via a suite of simulations carried out on a set of 8-bit grayscale standard images of size 512 × 512 pixels, including Lena, Peppers, Goldhill, Mandrill, and Zelda, as shown in Fig. 4.8. The EC performance is assessed by the peak signal to noise ratio (PSNR) and the image perceptual quality index (MSSIM) [137]. Note that the MSSIM index lies in the range [0, 1]. To evaluate the proposed methods, different types of loss patterns, i.e. isolated loss, consecutive loss, and random loss as shown in Fig. 4.1, are considered with the lost blocks of size 8 × 8 pixels with different PLR, ranging from 10% up to 50%. In the case of random loss pattern, the PSNR and MSSIM values are obtained by running the proposed methods 10 times and the average results are reported as the final values.

4. 5 Conclusion 5 •

 55 In this chapter, a new image EC has been developed by integrating the LR and the NS properties of natural images into the JSR. The JSR model estimates the corrupted patch via a dictionary pair and two mapping matrices that are trained offline from two given training datasets. By using this model, the error concealment is achieved by transferring the error recovery problem into a common space via the two learned dictionaries and mappings. Such transformation provides more freedom and flexibility for error concealment. Integrating this model with the local and non-local priors, as a new regularization term in the sparse representation domain, better preserves the sharp edges and suppresses visual artifacts. The performance of the proposed method has been evaluated and compared with the state-of-the-art methods, both quantitatively and perceptually. Chapter 5 Transmitter-based Error Concealment based on Sparse Recovery The material of this part is essentially based on the following works • A. Akbari and M. Trocan, "Sparse recovery-based error concealment for multiview images," in Proceedings of IEEE International Workshop on Computational Intelligence for Multimedia Understanding (IWCIM), Prague, Czech Republic, Oct. 2015, pp. 1-A. Akbari, M. Trocan, and B. Granado, "Sparse recovery-based error concealment," IEEE Transactions on Multimedia, vol. 19, no. 6, pp. 1339-1350, June 2017

Figure 5 . 1 :

 51 Figure 5.1: Block diagram of the proposed SREC method.

Fig. 5 .

 5 Fig. 5.2(c) shows the relationship between each SB and the corresponding image content.

Figure 5 . 2 :

 52 Figure 5.2: (a) 4-level wavelet decomposition of the Lena image (512 × 512 pixels). (b) ST structure. (c) SB construction and its relationship with corresponding image content.

Figure 5 . 3 :

 53 Figure 5.3: Packetization scheme. Coefficients with the same shading pattern map to one packet.

P

  i , produced by the encoder, provides a certain degree of the error protection. The error recovery starts by simply discarding some rows of the matrix Φ i to generate a submatrix Φ i , called Channel Matrix (CM), for each received Ṗi . Then, it performs the signal reconstruction by mathematically modelling of the error recovery as a sparse recovery problem. The structure of the decoder is depicted in the Fig.5.1.

Algorithm 4 ASR 1 : 2 : 3 :

 4123 Input: Φ i and Ṗi (i = 1, 2, • • • T ) Output: Φ i and Φ i (i = 1, 2, • • • T ) Initialize: k ← 0 and X[0] ← 0

Figure 5 . 4 :

 54 Figure 5.4: Subjective results for the test images. (a) Original image, (b) Received images with PLR = %30, (c) Concealed images with PLR = %30, (d) Concealed images with PLR = %70. From left to right: Lena, Peppers, Goldhill, Barbara, and Mandrill.

Fig. 5 .

 5 Fig. 5.5(a), the reconstruction PSNR values (in dBs) versus iteration number are given for the test images at %30 PLR. As can be seen, in the 10th iteration, the PSNR values for different iterations appear to level off at 39 dBs, 37 dBs, 35 dBs, 33 dBs, and 26 dBs for the Lena, Peppers, Goldhill, Barbara, and Mandrill, respectively. The PSNR values of the Lena image versus iteration number for different PLRs are illustrated in Fig. 5.5(b).

Fig. 5 .Figure 5 . 5 :

 555 Figure 5.5: Reconstruction quality (average PSNR) vs. iteration number at: (a) PLR = %30 for different test images and (b) for different PLR values for Lena image.

Figure 5 . 6 :

 56 Figure 5.6: Quality of received and concealed images vs. PLR (averaged values) in term of (a) PSNR (b) SSIM. Solid lines depict the quality of reconstructed images. Dotted line depicts the quality of the received images reconstructed by (5.1). Dashed line depicts the minimum expected quality (PSNR) obtained by (5.9).

Figure 5 . 7 :

 57 Figure 5.7: Effect of packet length on the EC performance for the Lena image.

.1 and 5 . 2 ,

 52 the error performances of different wavelet functions is compared in term of PSNR and SSIM, respectively. In addition to the Daubechies 9/7 filters, the performance of the Daubechies 5/3[START_REF] Gall | Sub-band coding of digital images using symmetric short kernel filters and arithmetic coding techniques[END_REF] and the LeGall 5/3 filters[START_REF] Unser | Mathematical properties of the JPEG2000 wavelet filters[END_REF] are also tested. The parameter set L = 4 and T SB = 1 is taken as the settings of these experiments. The 9/7 filters provide the substantial gain (PSNR: 1.3 -1.6 dBs and SSIM: 0.002 -0.017) over the Daubechies 5/3 filters and (PSNR: 5.23 -7.33 dB and SSIM: 0.01 -0.134) over the LeGall 5/3 filters under different PLRs. The reason comes from the fact that the floating-point 9/7 filter bank is nearly orthogonal, and it generates excellent sparse trees. In contrast, the floating-point Daubechies 5/3 and fixed-point LeGall 5/3 filter have less compaction characteristics than 9/7 ones.

ASRFigure 5 . 8 :

 58 Figure 5.8: Subjective comparison for Lena by different EC techniques with (a) %25 PLR, (b) %50 PLR, and (c) %75 PLR.

Figure 6 . 1 :

 61 Figure 6.1: Block diagram of the proposed image coding framework.

Fig. 6 .

 6 Fig. 6.1 presents the block diagram of the proposed image coding framework. This framework mainly consists of four parts, including pre-processing, dictionary learning, adaptive sparse representation and entropy coding. At the pre-processing step, the input image is partitioned into L non-overlapping image patches X = [x i ] L i=1 , where x i ∈ N denotes a B × B vectorized image block, containing N pixel values. As other compression schemes, like JPEG, the DC components, namely the mean values of image patches M = [m i ] L i=1 and AC components Y = [y i ] L i=1 are encoded separately. The DC values are subsequently quantized and entropy coded and the AC values are sparsely represented over an overcom-

Figure 6 . 2 :

 62 Figure 6.2: The Original images and their saliency maps.

Figure 6 . 3 :

 63 Figure 6.3: Rate-distortion performance compared with JPEG, JPEG2000 and K-SVD based codec using fixed S in terms of PSNR for several test images (size 512 × 512 pixels, gray-level).

Further, the

  proposed EC model based on sparse representation with respect to a trained dictionary demands larger computation resources and is not suitable for network edge devices like mobile, tablet and IoT devices. Deep convolutional neural networks (Deep CNN) have demonstrated superior performance to the previous hand-crafted models either in speed and restoration quality. A highly efficient and faster image EC can be obtained with Deep CNN. Current trend is using deeper CNN layers to improve performance. Optimizing the number of layers and filters of each CNN also achieves faster and efficient computation.

Table 3 .

 3 1: Comparison of quality of reconstructed images by differenct CS recovery tecnique in terms of PSNR (dB)

			Target Subrate (S)
		0.1	0.2	0.3	0.4	0.5
	BCS-SPL	28.00	31.28	33.31	35.15	36.44
	SBCS-SPL	28.83	32.44	34.61	36.28	37.76
	Lena
	BCS-IIP	28.08	31.38	33.43	35.28	36.57
	BCS-GSR	28.68 32.65 35.17 37.17 38.91
	BCS-SPL	28.99	31.95	33.62	34.95	36.17
	SBCS-SPL	29.24	32.44	34.09	35.38	36.51
	Peppers
	BCS-IIP	29.15	32.18	33.86	35.19	36.41
	BCS-GSR	30.31 33.45 35.27 36.66 37.95
	BCS-SPL	26.79	28.59	29.88	31.08	32.28
	SBCS-SPL	27.00	29.03	30.37	31.63	32.91
	Goldhill
	BCS-IIP	26.84	28.71	30.05	31.28	32.50
	BCS-GSR	27.42 30.34 32.07 33.93 35.70
	BCS-SPL	20.51	21.45	22.31	23.22	24.26
	SBCS-SPL	20.66	21.70	22.64	23.66	24.84
	Mandrill
	BCS-IIP	20.53	21.48	22.33	23.23	24.27
	BCS-GSR	20.76 22.98 24.31 25.98 26.79

Table 3 .

 3 2: Averaged reconstruction time (second ) at various subrates for different CS reconstruction algorithms

			Target Subrate (S)
		0.1	0.2	0.3	0.4	0.5
	BCS-SPL	21.72	10.92	6.62	4.77	3.92
	SBCS-SPL	57.62	29.45	18.24	13.65	12.55
	Lena
	BCS-IIP	28.63	16.25	10.84	6.48	5.12
	BCS-GSR	166.62 155.90 151.91 149.35 148.91

  3 is used for collecting the training data. This dataset consists of 96 natural gray-level images of size 512 × 512 pixels. 20 images are randomly selected

	for training. A corrupted training image set is also generated by creating the isolated
	loss pattern for each image. The lost blocks are recovered by a simple interpolation al-
	gorithm [108]. Then, the training sets X and Y are generated following the procedure
	described in Section 4.2.2. A total number of 100000 patches of size	√	M ×	√	M , which
	are rich in edges and textures, are randomly cropped from each set of training images. In
	practice, in order to make dictionaries more descriptive, the smooth patches are removed
	from the training datasets

Table 4 .

 4 1: Effect of dictionary size on the EC quality using the JSR-based EC algorithm in terms of PSNR (M is set to 5)

		Dictionary Size D
		10	20	30	40	50
	Lena	34.59 34.90 34.92 34.76 34.68
	Peppers 34.52 34.98 34.97 34.86 34.80
	Goldhill 32.53 32.71 32.67 32.64 32.60
	Mandrill 26.95 27.02 27.02 27.00 27.00
	Zelda	37.23 37.49 37.51 37.39 37.36

Table 4 .

 4 2: Effect of patch size on the EC quality using the JSR-based EC algorithm in terms of PSNR (best dictionary size is obtained for each patch size)

			Patch Size M
		4	5	6	7	8
	Lena	34.57 34.92 34.97 35.05 35.07
	Peppers 37.72 34.98 35.05 35.17 35.19
	Goldhill 32.55 32.67 32.69 32.73 32.80
	Mandrill 26.96 27.01 27.02 27.05 27.08
	Mandrill 37.31 37.51 37.52 37.59 37.63

Table 4 .

 4 3: PSNR and MSSIM Values of the concealed images using several EC techniques for different loss patterns (isolated loss, consecutive loss and random loss with 30% PLR)

	EC Technique

Random

PSNR 32.95 30.47 31.76 20.65 34.40 33.42 32.95 33.64 35.51 34.59 35.13 MSSIM 0.962 0.932 0.955 0.628 0.975 0.970 0.967 0.966 0.982 0.977 0.980

Table 4 .

 4 4: Reconstruction time (in seconds) for the concealed image Lena using several EC techniques for different loss patterns (isolated loss, consecutive loss and random loss with 30% PLR)

	EC Technique

Table 4 .

 4 5: Effect of mapping approach on the EC performance (PSNR) for the image Lena

	at different PLRs
			PLR (%)
	Mapping 10	20	30	40	50
	JSR-C	38.41 34.96 32.31 30.13 27.28
	JSR-D	38.31 34.87 32.23 30.05 27.26
	JSR-I	37.35 33.88 31.16 29.24 27.24

  1 , obtained by selecting the rows of Φ i indexed

1 |•| denotes the number of entries of a set.

Table 5 .

 5 1: Average PSNR Values for Lena Image for Different Wavelet Functions Daubechies 9/7 44.49 41.23 39.17 37.60 36.23 34.93 33.56 31.85 Daubechies 5/3 42.88 39.63 37.65 36.13 34.82 33.57 32.25 30.46

					PLR%
		10	20	30	40	50	60	70	80
	LeGall 5/3	37.70 35.62 33.93 32.37 30.82 29.13 27.13 24.52

Table 5 .

 5 2: Average SSIM values for Lena Image for Different Wavelet FunctionsAs mentioned in Section II. , the size of generated SBs depends on the number of wavelet decomposition levels (L) and the number of included spatial trees in each SB (T SB ).The SB size also makes some differences in the error recovery performance under a fixed PLR.

					PLR%
		10	20	30	40	50	60	70	80
	Daubechies 9/7 0.997 0.994 0.990 0.985 0.980 0.972 0.962 0.946
	Daubechies 5/3 0.995 0.991 0.985 0.979 0.972 0.963 0.950 0.929
	LeGall 5/3	0.987 0.978 0.967 0.954 0.937 0.914 0.878 0.812
	5.2.8 SB Size Effect

In order to evaluate the effect of SB size on the reconstructed image, at first, the number of wavelet decomposition levels (L) is fixed to 3 and the SBs with size of 8 × 8, 16 × 16, and 32 × 32 pixels are generated by inserting 1, 4, and 16 adjacent spatial trees in one SB, respectively. Table

5

.3 illustrates that there is a difference of approximately 0.2-2.34 dBs between the reconstructed quality with 32 × 32 and 8 × 8 SBs in the case that the same type of loss has occurred.

Table 5 .

 5 3: Effect of Number of Spatial Trees in each SB (T SB ) on Average PSNR Values 16 44.61 41.36 39.30 37.76 36.37 35.04 33.59 31.63 16 32 × 32 44.71 41.44 39.40 37.85 36.48 35.18 33.80 31.97

	for the Lena Image
						PLR%
	T SB SB size 10	20	30	40	50	60	70	80
	1	8 × 8	44.47 41.21 39.19 37.58 36.17 34.79 33.07 29.63
	4	16 ×

Table 5 .

 5 4: Effect of Number of Decomposition Levels (L) on Average PSNR Values for the 44.46 41.21 39.23 37.60 36.17 34.79 33.03 29.39 4 16 × 16 44.46 41.22 39.17 37.60 36.23 34.92 33.51 31.74 5 32 × 32 44.65 41.34 39.30 37.71 36.34 35.02 33.69 32.03 it.

	Lena Image
					PLR%
	L SB size	10	20	30	40	50	60	70	80
	3 8 × 8

Table 5 .

 5 5: Average PSNR and SSIM for Lena and Mandrill Images Reconstructed using

	Several EC Techniques
		EC Technique
	PLR%	CAD MRF SLP VC FSE MKDE ALP JSR+NL SREC
		Lena
		PSNR 31.23 31.53 31.58 32.35 32.38 32.47 33.89	34.98	40.07
	25
		SSIM 0.947 0.956 0.960 0.964 0.964 0.966 0.971	0.979	0.992
		PSNR 23.19 26.86 27.56 17.12 28.75 28.46 29.81	29.86	36.15
	50
		SSIM 0.811 0.904 0.905 0.887 0.918 0.919 0.936	0.937	0.979
		PSNR 17.65 21.86 20.55 8.97 22.56 21.47 22.51	22.49	33.01
	75
		SSIM 0.600 0.741 0.712 0.128 0.763 0.726 0.792	0.793	0.954
		Mandrill
		PSNR 25.13 26.13 24.77 26.04 26.29 26.14 26.42	26.52	27.46
	25
		SSIM 0.875 0.886 0.877 0.890 0.892 0.891 0.874	0.877	0.952
		PSNR 18.20 22.19 21.02 16.33 22.78 22.58 23.49	23.51	23.85
	50
		SSIM 0.606 0.759 0.730 0.640 0.771 0.761 0.798	0.799	0.859
		PSNR 15.35 20.06 18.23 9.15 20.13 19.22 19.62	20.01	21.22
	75
		SSIM 0.446 0.551 0.475 0.162 0.553 0.501 0.549	0.555	0.656
	the performance of the aforementioned methods is degraded, as it can be observed in the

Table 5 .

 5 [START_REF] Mallat | A Wavelet tour of signal processing[END_REF] for PLR = %50 and %70.

Table 5 .

 5 6: Reconstruction Time (in Second) Obtained for Lena Image using Several EC It can be seen that the proposed algorithm is much faster than the recently proposed ALP and MKDE algorithms. Although the proposed algorithm has a considerably large error recovery time in comparison with the CAD and MRF, its advantage in precisely estimation of the corrupted information is obvious in terms of objective and subjective

	Techniques
		EC Technique
			SREC
	PLR% CAD MRF SLP VC FSE MKDE ALP
			8 × 8 16 × 16 32 × 32
	25	6.77 9.68 370 305 37.23 1387	147 33.65 18.90 11.23
	50	9.07 19.22 444 610 83.86 1853	275 59.54 29.55 18.45

The MATLAB code of the BCS-SPL algorithm is available in authors' website: http://my.ece.msstate.edu/faculty/fowler/BCSSPL/

The 1-norm is defined as follows: for x ∈ R N , x 1 = N i=1 |xi| where | • | stands for the absolute value operator.

The • 0 denotes the 0-norm counting the nonzero elements

http://decsai.ugr.es/cvg/dbimagenes/

The Implementation of some techniques are available online at http://dtstc.ugr.es/~jkoloda/ download.html

The Implementation of[114] is available at https://sites.google.com/site/jingliu198810/ publication and other techniques' codes are available online at http://dtstc.ugr.es/~jkoloda/ research.html.

http://decsai.ugr.es/cvg/dbimagenes

http://www.ijg.org

http://www.openjpeg.org

http://www.ux.uis.no/~karlsk/ICTools/ictools.html

Acknowledgments

encouragement, inspirational advice, and endless love. Finally, this would not have been possible without the support of the ISEP engineering school, which I would like to thank for having funded

Papers in Preparation

• --, "Image compressed sensing recovery using saliency-based adaptive sensing and residual reconstruction," IEEE Transactions on Multimedia

List of Algorithms

and β

[l+1] lr using (4.15) and (4.17);

is obtained by the following shrinkage operator:

where ν [l,j] = α lr , ξ is a constant, and S(•) is the soft-thresholding operator that accelerates the convergence of the recovery algorithm. At the first iteration, i.e. j = 0, α [l,0] y is set as α [l-1] y and when the last iteration is done α

y , where J is the number of iterations for solving (4.19). It should be noted that P -1 = M -1 y M x . The complete details of the recovery algorithm are described in Algorithm 3.

Discussion

As mentioned at first of this section, the existing LR and NS models are implemented in the spatial domain. In these approaches, one can use the estimated patches, y ns and y lr , and simply improve the quality of the reconstructed image in the spatial domain instead of solving the minimization problem (4.11). However, it should be noted that the obtained patches, y ns and y lr , consist of a certain level of noise. When these noisy patches are used for recovery of the original patch in the spatial domain, the recovered patch looks unpleas-To evaluate the influence of dictionary size D on the EC quality, we set M = 25 and D as 64, 128, 256, 512, and 1024. For each size, the dictionary pair and the mapping matrices are learned using the joint dictionary-mapping learning algorithm. Table 4.1

shows the effect of dictionary size on the EC performance using the proposed JSR-based EC algorithm in terms of PSNR. As D increases, the PSNR value increases, but a larger value of D does not yield higher performance. It is easy to understand that the PSNR value first rises and then declines, when the dictionary size becomes larger. Further, for the high textured images, like Mandrill, the value of improvement is negligible with respect to the dictionary size. We also evaluate the performance of the proposed JSR-based EC algorithm with different M from 16 to 64. Best dictionary pair and mappings are trained for each patch size. Table 4.2 shows the results according to different values of M . As can be seen, the PSNR values increase when M increases. Using a larger patch means that the area u (see Fig. 4.2) contains more reliable information. Note that the size of area v is always fixed (2 × 2 pixels). The EC quality increases because more reliable information is used for patch recovery.

Generally, larger D and M are more suitable in the proposed JSR model for the EC.

The reason lies behind the fact that larger D and M will strengthen the representation ability of the dictionary pair and the matching precision of the mapping matrices. On the other hand, choosing a large patch size and dictionary size leads to more computational complexity. Therefore, we select an appropriate patch size to obtain good EC performance with lower computational costs, i.e. M = 25 and D = 256.

Other parameters: The number of similar patches in the NS model is set to L = 10 and the size of search window is set to 20 × 20 pixels. In addition, in order to avoid the data over-fitting, a LR model of the order 10 (i.e. J = 10) is used. The optimal selection of the number of clusters in the LR model is a nontrivial task. If the number of clusters is small, the distinctiveness of the LR models is decreased. On the contrary, choosing a large number of clusters leads the LR models less representative and reliable.

To select an appropriate value for the clusters number in the LR model, we conduct several experiments by changing the clusters number. We have found that the performance of the proposed JSR+NS method is stable when cluster number is greater than 200. The last parameter that should be set is the iterations number. The EC performance of the proposed JSR+NS algorithm is monotonically improved by increasing the iteration number. In our implementation, when the difference of the PSNR value of the reconstructed image in prediction (SLP) [START_REF] Koloda | Sequential error concealment for video/images by sparse linear prediction[END_REF], learning sparse representation-based EC (LSR) [START_REF] Akbari | Image error concealment using sparse representations over a trained dictionary[END_REF], and adaptive linear prediction (ALP) based EC [START_REF] Liu | Spatial error concealment with an adaptive linear predictor[END_REF] 4 . In order to see the effect of LR and NS models on the EC performance, the PSNR and MSSIM values of the reconstructed image using the JSR-based EC algorithm is also reported.

Table 4.3 provides the EC results of all the methods for the test images corrupted by different loss scenarios (isolated loss, consecutive loss, and random loss with 30% PLR).

The best values are marked in bold. In terms of PSNR and MSSIM, the performance of the proposed JSR-based EC algorithm is better than most of the competing methods, especially in the consecutive and random loss patterns. The EC performance can be further improved by the proposed JSR+NL algorithm. As can be seen in Table 4.3, the EC results of competing methods are significantly lower than those provided by the proposed JSR+NL algorithm for the images Lena and Peppers, which demonstrate its effectiveness for the error recovery by exploiting jointly the non-local self-similarity and local structural regularity.

Although, the performance of the JSR+NL algorithm for the high texture images, such as Mandrill, is lower than the ALP method in terms of PSNR, the MSSIM values, which are more consistent with the human visual system, are nearly the same. However, as discussed later, the JSR+LN algorithm is much faster than the ALP algorithm.

The zoomed parts of the concealed image Lena, reconstructed by different EC methods, are shown in Fig. 4.9 for visual comparisons. The image is corrupted by the random loss pattern (30%P LR). As it can be seen, the CAD and VC fail to recover the lost blocks and the AVC and POCS cannot restore the lost blocks well. In comparison, the MRF, and SSIM values over 10 trials are reported.

In the above-mentioned algorithms, it is assumed that the image is divided into 8 × 8 non-overlapping blocks which are coded separately at the transmitter side. In the packetization step, one or more coded blocks are fed into one packet; therefore, while transmitted over an error-prone channel, undesired packet erasure leads on missing an area of the image. These EC techniques rely on the estimation of the lost information from the correctly received data of the neighboring blocks by exploiting the high spatial correlation among them. Therefore, the packetization is done in a way that decreases the simultaneous loss of neighboring blocks in order to increase the EC performance.

Similar to the above-mentioned algorithms, the proposed SREC algorithm estimates the lost information from the correctly received data at the expense of a small modification of the transmitter. Using the linear combination at the transmitter side makes to each coefficient picks up a little bit of information about an area of the image (spatial trees); then, if some of these coefficients are discarded, the image recovery can still be done, as sufficient amount of information about the image is maintained in the correctly received coefficients. In addition, as we discussed in the Section III. , the generated packets are expected to share the information equivalently, and thus there is no need to transmit the packets with priority, opposed to other encoding and packetization methods [START_REF] Kim | Error-resilient image and video transmission over the internet using unequal error protection[END_REF]. This type of packetization in connection with the linear projection of the wavelet coefficients introduces more robustness and error-resilience into the transmission system and ensures that a high quality image can be recovered, even for the high packet loss rates.

I. Subjective and Objective Reconstruction Quality

As it can be observed in Table 5.5, the objective performance of the proposed SREC is generally superior to that achieved using other state-of-the art techniques in terms of PSNR and SSIM. The comparison with the SLP and FSE is particularly interesting since they are also sparse recovery based EC. Although, the improvement value of the SREC algorithm for the high texture Mandrill image in term of PSNR is smaller in comparison with the Lena image, its SSIM value which is more consistent with the human visual system proves the considerable visually improvements of the SREC scheme.

The significant superiority of the proposed SREC scheme is its great ability in the image error recovery at high PLRs, as it can be seen in Table 5.5 and Fig. 5.8. In fact, at high error rates, the loss of neighboring blocks occurs with high probability; therefore,

Introduction

The objective of lossy image compression is minimization of the file size without significant degradation of the image quality in order to be able to transmit or store the image efficiently. There are several different ways in which the image files can be compressed [START_REF] Shi | Image and video compression for multimedia engineering: fundamentals, algorithms, and standards[END_REF].

All these techniques aim to reduce the redundancy of the image data from different points of view. The most commonly used method is to transform the image to a domain with compressible coefficients which capture a large part of the image information with only a few significant coefficients. Therefore, the image compression can be well achieved by storing or transmitting the significant transform coefficients. The analysis and synthesis sparse modelings are two powerful tools for transforming the image into a compressible domain. The JPEG [START_REF] Wallace | The jpeg still picture compression standard[END_REF] and the JPEG2000 standards [START_REF] Skodras | The jpeg 2000 still image compression standard[END_REF] are the results of using the analysis sparse representation of the image by designing some analytic dictionaries, e.g.

discrete cosine transform (DCT) basis and discrete wavelet transform (DWT) basis, respectively. The analysis sparse modeling of the image is typically over-simplistic and has a weak ability to represent the high-textured images efficiently [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. Due to the weakness Chapter 6. Sparse Representation-based Image Compression as shown in Fig. 6.2, including Table, Barbara, Boat, Couple, Lena and Hill. In order to better take into account the rate-distortion performance of the proposed image coding scheme, the Peak Signal-to-Noise Ratio (PSNR) is chosen as the objective measurement in the experiments.

The saliency maps of the test images, computed using the GBVS [START_REF] Harel | Graph-based visual saliency[END_REF], are shown in the second row of Fig. 6.2 (the saliency maps were quantized for better display). In the saliency maps, brighter regions represent the salient locations on which a human observer pays more attention to, while the darker areas represent the less salient regions. According to the saliency maps shown in the Fig. 6.2, relatively larger sparsity levels are assigned to the blocks with higher saliency values.

A block dimension of size 8 × 8 is considered for the partitioning step and also for dictionary learning, as proposed in [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF]. A 64 × 440 dictionary is learned using the K-SVD method on the training images from the CVG-Granada dataset 1 . 1500 patches are randomly selected from 8 training images to form a training data set with L = 12000 patches. The ORMP algorithm [START_REF] Skretting | Image compression using learned dictionaries by rls-dla and compared with K-SVD[END_REF] is used for the atom selection in the dictionary learning step, as well as later in the sparse representation process for compression. The Rate-distortion graphs for the test images are presented in Fig. 6.3 for several baseline algorithms for comparison, including JPEG 2 , JPEG2000 3 and a K-SVD based image compression algorithm 4 , in which a fixed sparsity level is considered for all patches [START_REF] Aharon | K-SVD: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF].

Clearly, the proposed method gains remarkably when compared with the existing image coding standards, JPEG and JPEG2000. It can be observed that there is a 0.98 dB on average improvement over the JPEG2000 and a 1.22 dB improvement over the K-SVD based codec using a fixed S, slightly more evident at the high bit rates. Generally, the proposed method typically performs better on the highly textured images due to the fact that the trained dictionary has a great ability to capture and efficiently represent the contours, when compared with the analytic dictionaries like the wavelet transform basis.

Furthermore, we can find that the application of conventional image sparse representa-Chapter 7. Conclusion and Future Directions tation modeling i.e. sparse recovery suitable for solving the inverse problems such as error concealment (EC) and compressed sensing (CS). A novel image EC approach has been presented, through casting the error recovery issue onto a synthesis sparse recovery framework using over-complete and trained dictionaries. The core idea of our EC algorithm is that, under mild conditions, the sparse representation of an image patch and a portion of this patch are related to each other by a linear mapping function. Under this assumption, the missing pixels have been recovered using the sparse representation coefficients of the lost region's neighboring pixels. Especificaly, the joint sparse representation (JSR) model has been proposed. The JSR model estimates the corrupted patch via a dictionary pair and two mapping matrices that are trained offline from two given training datasets. By using this model, the EC is achieved by transferring the error recovery problem into a common space via the two learned dictionaries and mappings. Such transformation provides more freedom and flexibility for error concealment. Further, a new image EC has been developed by incorporating this model using the local and non-local priors, as a new regularization term in the sparse representation domain, which produces sharper edges and suppresses visual artifacts. The performance of the proposed method has been evaluated and compared with the state-of-the-art methods, both quantitatively and perceptually.

In another work relating to the EC problem, a novel approach to recovery of the lost information, occurred during the image transmission over the error-prone channels, was presented through modeling of the error recovery issue onto the analysis-based sparse recovery framework. The proposed robust image transmission scheme achieves the error robustness by partitioning the wavelet coefficients into the spatial trees and coding each tree in the form of an embedded linear coder, followed by a simple packetization scheme.

The core idea behind the proposed technique is the random linear projection of the spatial trees that provides a way to implicitly adapt the analysis-based sparse recovery framework for recovering a high degree of the packet losses. This framework goes beyond simply assuming that the wavelet decomposition has a tree-sparse structure. At the receiver, the corrupted image is concealed using an iterative sparse reconstruction in the wavelet domain. Performance of the proposed scheme and its significant gains over the existing EC techniques have also been demonstrated by various simulations. The ability of the proposed algorithm for the error protection for the high packet loss rates, combined with the property of being highly parallel-friendly, makes the algorithm a strong candidate for the image transmission on the error-prone channels.

Publications

Book Chapter Conference Publications for all x ∈ R N with x 0 ≤ K. The proof of this theorem can be found in [START_REF] Laska | Democracy in action: Quantization, saturation, and compressive sensing[END_REF].

Furthermore, suppose entries of the signal x is rearranged in the decreasing order of

where C p is a fixed constant depending on p only (see Theorem 1.1 of [START_REF] Candes | Near-optimal signal recovery from random projections: Universal encoding strategies?[END_REF].)