Marco Bevilacqua
email: marco.bevilacqua@imtlucca.it

Member, IEEE Aline Roumy

Fellow, IEEE Christine Guillemot

Alberi Morel

Marie-Line Alberi Morel
email: marieline.alberi-morel@alcatel-lucent.com

M-L Alberi Morel

Single-Image Super-Resolution via Linear Mapping

Keywords: super resolution, example-based, regression, neighbor embedding I

published or not. The documents may come

environmental conditions. Moreover, with the spread of digital technologies, there is a tremendous amount of user-produced images collected in the years, that are valuable but may be affected by a poor quality. Therefore, techniques to augment the resolution of an image, i.e. the total number of pixels, and contextually improve its visual quality, are particularly appealing. SR methods are traditionally categorized according to the number of input images: when several low-resolution (LR) input images are available we speak about multi-frame SR algorithm; vice versa, when the LR input image is unique, we have the single-image SR problem. In both cases, as an output, a unique high-resolution (HR) super-resolved image is produced.

Multi-frame SR methods, of which a good overview is given in [START_REF] Park | Super-Resolution Image Reconstruction: A Technical Overview[END_REF], are the first ones that have been studied, since the SR problem first appeared in the scientific community [START_REF] Huang | Multiframe image restoration and registration[END_REF]. Here, the multiple LR input images are considered as different views of the same scene, taken with sub-pixel misalignment, i.e. each image is seen as a degraded version of an underlying HR image to be estimated, where the degradation processes can include blurring, geometrical transformations, and down-sampling. Single-image SR, instead, aims at constructing the HR output image from as little as a single LR input image. The problem stated is an inherently ill-posed problem, as there can be several HR images generating the same LR image. Single-image SR is deeply connected with traditional "analytical" interpolation, since they share the same goal. Traditional interpolation methods, e.g. bicubic interpolation, by computing the missing pixels in the HR grid as averages of known pixels, implicitly impose a "smoothness" prior. However, natural images often present strong discontinuities, such as edges and corners, and thus the smoothness prior results in producing ringing and blurring artifacts in the output image. Single-image SR algorithms can be broadly classified into two main approaches: interpolation-based methods [3]- [START_REF]Image Upsampling via Imposed Edge Statistics[END_REF], which, possibly in a nonparametric fashion, follow the interpolation approach by posing more sophisticated statistical priors; and machine learning (ML) based methods.

In particular, the latter, by taking advantage of the powerfulness of ML techniques, have shown to give very challenging results, and many algorithms appeared in the literature in the recent years. ML-based algorithms can consist in pixel-based procedures, where each value in the HR output image is singularly inferred via statistical learning [START_REF] He | Single image super-resolution using Gaussian process regression[END_REF], [START_REF] Zhang | Single Image Super-Resolution With Non-Local Means and Steering Kernel Regression[END_REF], or patch-based procedures, where the HR estimation is performed thanks to a dictionary of correspondences of LR and HR patches (i.e. squared blocks of image pixels). ML-based SR that makes use of patches is also referred to as example-based SR [START_REF] Freeman | Example-Based Super-Resolution[END_REF]. In the upscaling procedure the LR input image itself is divided into patches, and for each LR input patch a single HR output patch is reconstructed, by observing the "examples" contained in the dictionary.

Example-based methods mainly vary in two aspects: the patch reconstruction method used and the typology of dictionary. As for the method to perform the single patch reconstructions, we have again two main categories: coding-based reconstruction methods and direct mapping (DM). Neighbor embedding (NE) belongs to coding-based methods. In NE-based SR [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF]- [START_REF] Chan | Neighbor embedding based super-resolution algorithm through edge detection and feature selection[END_REF], for each LR input patch we select K similar LR examples in the dictionary by nearest neighbor search (NNS), and a linear combination of these neighbors is computed to possibly approximate the input patch. The corresponding HR neighbors are then similarly combined, i.e. by using the same weights October 15, 2014 DRAFT computed with the LR patches, to generate the HR output patch. This approach relies on what in [START_REF] Li | Locality preserving constraints for super-resolution with neighbor embedding[END_REF] is called "manifold assumption": the linear combination weights are meant to capture the local geometry of a manifold on which the LR patches are supposed to lay; by applying the same weights to reconstruct the HR patches, we implicitly assume that they too lay on a manifold with similar local structures. In order to enforce the assumption of manifold similarity between the two distinct spaces represented by the LR and HR patches, Gao et al. propose in [START_REF] Gao | Joint learning for single-image super-resolution via a coupled constraint[END_REF] to compute the weights in a subspace common to the LR and HR patches. The method therefore assumes the existence of a common low-dimensional space that preserve some meaningful characteristics of the patches.

Example-based SR via sparse representations [START_REF] Yang | Image Super-Resolution Via Sparse Representation[END_REF], [START_REF] Wang | Resolution enhancement based on learning the sparse association of image patches[END_REF] also falls within the family of coding-based methods, and can be considered very close to NE-based SR: however, here, the weights are not computed on neighbors found by NNS, but typical sparse coding algorithms are employed. The method presented in [START_REF] Gao | Image Super-Resolution With Sparse Neighbor Embedding[END_REF] bridges the two approaches (NE and sparse representations), by proposing a "sparse neighbor embedding" algorithm. In [START_REF] Zhang | Multi-scale dictionary for single image super-resolution[END_REF], instead, another sparse-representation-based SR algorithm is presented, which, in addition to a sparse example-based term, uses several regularization terms to globally optimize the image generation process.

All the methods so far require manifold similarity between the LR and HR spaces. A different patch reconstruction approach that does not rely on this assumption is given instead by direct mapping (DM). Example-based SR via DM [START_REF] Yang | Fast Image Super-Resolution Based on In-Place Example Regression[END_REF]- [START_REF] Kim | Single-Image Super-Resolution Using Sparse Regression and Natural Image Prior[END_REF] aims at finding, in fact, for each patch reconstruction, a function that directly map a given LR patch into its HR version. The mapping function is commonly found with traditional regression methods.

As for the second discriminating aspect of example-based SR, the typology of the dictionary, we have mainly two choices: an external dictionary, built from a set of external training images, and an "internal" one, built without using any other image than the LR input image itself. This latter case exploits the so called "self-similarity" property, typical of natural images, according to which image structures tend to repeat within and across different image scales: therefore, patch correspondences can be found in the input image itself and possibly scaled versions of it. To learn these patch correspondences, that specifically take the name of self-examples, we can have one-step schemes [START_REF] Yang | Fast Image Super-Resolution Based on In-Place Example Regression[END_REF], [START_REF] Freedman | Image and Video Upscaling from Local Self-Examples[END_REF], [START_REF] Zhang | Single image super-resolution with multiscale similarity learning[END_REF] or schemes based on a pyramid of recursively scaled images starting from the LR input image [START_REF] Glasner | Super-Resolution from a Single Image[END_REF]- [START_REF] Yang | Learning context-aware sparse representation for single image super-resolution[END_REF]. Clearly, the advantage of having an external dictionary instead of an internal one lies in the fact that it is built in advance, while the internal one is generated online and updated at each run of the algorithm.

However, external dictionaries have a considerable drawback: they are fixed and thus non-adapted to the input image.

The study conducted in [START_REF] Zontak | Internal Statistics of a Single Natural Image[END_REF] also confirms the benefit of using internal statistics in patch-based image processing algorithms.

A. Main contributions

In this paper we present a novel example-based SR algorithm that makes use of an internal dictionary. The contributions are twofold. First, we build a "double pyramid", where the traditional image pyramid of [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] is juxtaposed with a pyramid of interpolated images. Second, HR patches are reconstructed through DM, whereas in [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] the HR patches are reconstructed via NE. Therefore, in the proposed algorithm, a linear mapping is learned on the double pyramid from the LR interpolated patches to the HR patches, and then applied to each interpolated LR October 15, 2014 DRAFT input patch. As said before, unlike NE, DM does not rely on any theoretical assumption (i.e. a manifold similarity between the LR and HR spaces), and is therefore preferable.

The rationale for the interpolation operation is to make the computation of the single mapping functions via regression more robust (LR and HR patches, in fact, turn out to have the same sizes). Moreover, a Tikhonov regularization is added to the problem to provide numerical stability in the computation, since the linear mapping requires a matrix inversion. A double-pyramid-like scheme has also been introduced in [START_REF] Zhang | Single image super-resolution with multiscale similarity learning[END_REF]. However, our proposed algorithm differs from [START_REF] Zhang | Single image super-resolution with multiscale similarity learning[END_REF] in two ways. First, the reconstruction in [START_REF] Zhang | Single image super-resolution with multiscale similarity learning[END_REF] is based on a neighbor embedding technique analyzed in [START_REF] Bevilacqua | Low-Complexity Single-Image Super-Resolution based on Nonnegative Neighbor Embedding[END_REF] (NE with a sum-to-one constraint). This NE technique was shown to have a performance highly dependent on the number of neighbors chosen. More precisely, when this number is equal to the size of the LR input vectors, the performance of the algorithms dramatically drops. As a second discriminating aspect, while [START_REF] Zhang | Single image super-resolution with multiscale similarity learning[END_REF] initializes the pyramid by down-scaling the LR input image only once, we instead initialize the pyramid with many sub-levels by recursively down-scaling the LR input image. We show that many sub levels are needed in order to better reconstruct a HR image. More precisely, we have that at the first iteration of the algorithm around 35% of the selected patches come from the pyramid levels below the first one (see Fig. 3 for details). The patches initially selected play a crucial role: in fact, since the whole algorithm is by nature recursive, it is very sensitive to its initialization.

All the listed contributions are possible at the cost of a slight increase in the complexity of the algorithm (i.e.

+10.7% for a scale factor of 3 and +8.1% for a scale factor of 4; see Section IV-B for details), while having a beneficial effect on the quality performance, both in terms of objective metrics (PSNR and SSIM) and visual results.

B. Organization of the paper

The rest of the paper is organized as follows. Section II reviews the fundamentals of example-based SR using an internal dictionary, by giving also a general introduction of NE and DM methods. Then, in Section III, our algorithm is described in detail, by explaining how the internal dictionary is trained and the whole upscaling procedure. Before drawing the conclusions, Section IV presents some extensive experiments done: the different implementation choices are here validated and the algorithm is compared with other state-of-the-art methods, by showing visual and quantitative results.

II. EXAMPLE-BASED SR WITH SELF-EXAMPLES

A. Principles and notations

Single-image SR is the problem of estimating an underlying HR image, given only one observed LR image. The generation process of the LR image from the original HR image, that we consider, can be written as

I L = (I H * B) ↓ s , (1)
where I L and I H are respectively the LR and HR image, B is a blur kernel the original image is convoluted with, which is typically modeled as a Gaussian blur [START_REF] Baker | Limits on Super-Resolution and How to Break Them[END_REF], and the expression ↓ s denotes a downsampling operation by a scale factor of s. The LR image in then a blurred and down-sampled version of the original HR image.

Example-based single-image SR aims at reversing the image generation model [START_REF] Park | Super-Resolution Image Reconstruction: A Technical Overview[END_REF], by means of a dictionary of image examples that map locally the relation between an HR image and its LR counterpart, the latter obtained with the model [START_REF] Park | Super-Resolution Image Reconstruction: A Technical Overview[END_REF]. For general upscaling purposes, the examples used are typically in the form of patches, i.e. squared blocks of pixels (e.g. 3 × 3 or 5 × 5 blocks). The dictionary is then a collection of patches, which, two by two, form pairs. A pair specifically consists of a LR patch and its HR version with enriched high frequency details.

Example-based SR algorithms comprise two phases:

1) A training phase, where the above-mentioned dictionary of patches is built;

2) The proper super-resolution phase, that uses the dictionary created to upscale the input image.

As for the training phase, in the next section we discuss how to build an "internal" dictionary of patches, i.e.

starting from as little as the LR input image. As for the SR phase, instead, in example-based algorithms the patch is also the reconstruction unit used in the upscaling procedure. In fact, the LR input image is partitioned into patches;

for each single LR input patch, then, by using the LR-HR patch correspondences in the dictionary, a HR output patch is constructed. The HR output image is finally built by re-assembling all the reconstructed HR patches. In

Section II-C we revise the two main patch reconstruction approaches: neighbor embedding and direct mapping.

Hereinafter in this paper we will use the following notation to indicate the different kinds of patches.

X l = {x l i } Nx i=1
will denote the set of LR patches into which the LR input image is partitioned; similarly, X h = {x h i } Nx i=1 will denote the set of reconstructed HR patches, that will form the HR output image. Each patch is expressed in vector form, i.e. its pixels are concatenated to form a unique vector. As for the dictionary, Y l = {y l i } Ny i=1 and Y h = {y h i } Ny i=1 will be respectively the sets of LR and HR example patches. In each patch reconstruction, then, the goal is to predict an HR output patch x h i , given the related LR input patch x l i , and the two coupled sets of patches, Y l and Y h , that form the dictionary. Fig. 1 shows in a simple manner the operating diagram of an example-based SR algorithm, where the input image is partitioned into LR patches, a dictionary of patch correspondences is exploited, and new HR patches are generated and subsequently re-assembled to create the super-resolved output image.

B. Searching for self-examples

In example-based SR, when performing the training phase, we speak about an internal learning when, instead of making use of external training images, we derive the patches directly from the input image and processed versions of it. Local image structures, that can be captured in the form of patches, tend to recur across different scales of an image, especially for small scale factors. We can then use the input image itself, conveniently upsampled or down-sampled into one or several differently re-scaled versions, and use pairs of these images to learn correspondences of LR and HR patches, that will constitute our internal dictionary. We call the patches learned in this way self-examples. In this respect, there are two main kinds of learning schemes described in the literature: one-step schemes like in [START_REF] Yang | Fast Image Super-Resolution Based on In-Place Example Regression[END_REF], [START_REF] Freedman | Image and Video Upscaling from Local Self-Examples[END_REF], [START_REF] Zhang | Single image super-resolution with multiscale similarity learning[END_REF], and schemes involving the construction of a pyramid of recursively scaled images [START_REF] Glasner | Super-Resolution from a Single Image[END_REF]- [START_REF] Yang | Learning context-aware sparse representation for single image super-resolution[END_REF].

LR input image HR output image

One-step schemes are meant to reduce as much as possible the size of the internal dictionary, i.e. the number of self-examples to be examined at each patch reconstruction, and thus the computational time of the SR algorithm.

In fact, from the input image only one pair of training images is constructed and thus taken into account for the construction of the dictionary. This approach is motivated by the fact that the most relevant patches correspondences can be found when the rescale factor employed is rather small. Only one rescaling is then sufficient to obtain a The method described in [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] paved the way to several SR algorithms (e.g. [START_REF] Yang | Exploiting Self-Similarities for Single Frame Super-Resolution[END_REF], [START_REF] Yang | Learning context-aware sparse representation for single image super-resolution[END_REF]), based on self-examples derived in an image pyramid. Differently from one-step learning methods, here several training images are constructed by recursively down-scaling the LR input image, thus forming a sort of overturned pyramid. Given a LR input patch, all the levels of this pyramid can be used to find similar self-examples, usually by performing a nearest neighbor search (NNS) (see Fig. 2).

To test the effective usefulness of constructing a full pyramid of images, we built a pyramid with 6 sub-levels as in [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] (the original LR image is recursively down-scaled 6 times). For each LR input patch, then, the K = 9

most similar self-examples (the K nearest neighbors) have been searched throughout the whole pyramid, and the histogram of all the selected neighbors has been drawn, where the histogram classes are the 6 sub-levels of the pyramid. Fig. 3 presents the histograms of the selected neighbors for two different images.

As we can observe from Fig. 3, it is clear that the first sub-level, i.e. the image obtained with only one rescaling operation, is the most relevant source of self-examples. Nevertheless, in both cases nearly 35 percent of the neighbors still come from the other sub-levels, which is not a negligible percentage. Pyramidal scheme like in [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] are then preferable than one-step scheme like [START_REF] Yang | Fast Image Super-Resolution Based on In-Place Example Regression[END_REF], [START_REF] Freedman | Image and Video Upscaling from Local Self-Examples[END_REF], [START_REF] Zhang | Single image super-resolution with multiscale similarity learning[END_REF].

C. Patch reconstruction methods based on local learning

Once the dictionary of self-examples is built, i.e. we have the two dictionary sets Y l and Y h containing, respectively, LR and HR example patches, the proper SR upscaling procedure is ready to start. In this

M i = M(x l i , Y l i , Y h i ).
3) Prediction: The model M i is applied to actually predict the HR output patch. NE and DM differ in steps 2 and 3 of the local learning procedure above. In NE, the reconstruction model M i consists of a vector of weights w i ∈ R K (where K is the number of neighbors chosen), that identifies a linear combination of the LR neighbors Y l i . The weights are computed w.r.t. the LR input patch and its neighbors (w i = M(x l i , Y l i )). In [START_REF] Glasner | Super-Resolution from a Single Image[END_REF], e.g., the single weight w i (j), related to the neighbor y l j found in the pyramid, is an exponential function of the distance between the latter and the LR input patch, according to the non-local means October 15, 2014 DRAFT (NLM) model [START_REF] Buades | A Non-Local Algorithm for Image Denoising[END_REF].

w i (j) = 1 C e - x l i -y l j 2 2 t , (2)
where t is a parameter to control the decaying speed and C is a normalizing constant to make the weights sum up to one.

In other NE methods, instead, the weights are meant to describe a linear combination that approximates the LR input patch (i.e. x l i ≈ Y l i w i ). In [START_REF] Chang | Super-Resolution Through Neighbor Embedding[END_REF]- [START_REF] Chan | Neighbor embedding based super-resolution algorithm through edge detection and feature selection[END_REF], e.g., the weights are computed as the result of a least squares problem with a sum-to-one constraint:

w i = arg min w x l i -Y l i w 2 s.t. w T 1 = 1 . (3)
The formula (3) recalls the method used in Locally Linear Embedding (LLE) [START_REF] Roweis | Nonlinear Dimensionality Reduction by Locally Linear Embedding[END_REF] to describe a high-dimensional point lying on a manifold through its neighbors. In [START_REF] Bevilacqua | Low-Complexity Single-Image Super-Resolution based on Nonnegative Neighbor Embedding[END_REF], instead, the sum-to-one constraint is replaced by a nonnegative condition, thus leading to nonnegative weights.

w i = arg min w x l i -Y l i w 2 s.t. w ≥ 0 . (4)
In [START_REF] Gao | Joint learning for single-image super-resolution via a coupled constraint[END_REF], finally, the weight computation is performed in an appropriate subspace: the LR input patch and its HR neighbors are expressed as lower-dimensional vectors, thanks to convenient projection matrices. The weights are then found by minimizing the error in the new subspace with no explicit constraint:

w i = arg min w P l i x l i -P h i Y h i w 2 . ( 5
)
Once the vector of weights w i is computed, the prediction step (Step 3) of the NE learning procedure consists in generating the HR output patch x h i as a linear combination of the HR neighbors Y l i , by using the same weights:

x h i ≈ Y h i w i . (6)
Fig. 4a depicts the scheme of the patch reconstruction procedure in the NE case. The model, i.e. the weights, is totally learned in the LR space, and then applied to the HR local training set to generate the HR output patch.

In direct mapping (DM) methods [START_REF] Yang | Fast Image Super-Resolution Based on In-Place Example Regression[END_REF]- [START_REF] Kim | Single-Image Super-Resolution Using Sparse Regression and Natural Image Prior[END_REF], instead, the model is a regression function f i that directly maps the LR input patch into the HR output patch. The function is learned by taking into account the two local training

sets (f i = M(Y l i , Y h i ))
, by minimizing the empirical fitting error between all the pairs of examples. An appropriate regularization term is placed to make the problem well-posed. We then have:

f i = arg min f ∈H K j=1 y h j -f (y l j ) 2 2 + λ f 2 H , (7)
where H is a desired Hilbert function space and λ ≥ 0 a regularization parameter. Examples similar to x l i and their corresponding HR versions are then used to learn a unique mapping function, which is afterwards simply applied to x l i to predict the HR output patch (Step 3):

x h i = f i (x l i ) (8)
Fig. 4b depicts the scheme of the patch reconstruction procedure also in the DM case.

An advantage of DM w.r.t. NE is that it can enable fast procedures, while presenting only slightly degraded performance, as done in [START_REF] Timofte | Anchored neighborhood regression for fast example-based super-resolution[END_REF]. By allowing a mismatch in the neighborhood computation (neighborhood of the closest atom in the dictionary rather than neighborhood of the input patch), the mappings can be pre-computed and stored. Hence the fast implementation.

III. PROPOSED ALGORITHM

In this section we present our novel SR algorithm, based on an internal dictionary of self-examples. Starting from the image pyramid described in Section II-B, we propose a modified scheme with a "double pyramid", presented in Section III-A. The self-examples found in this scheme are used to gradually upscale the LR input image up to the final super-resolved image, according to the cross-level scale factor chosen for the pyramid. The upscaling procedure employed falls within the local learning based reconstruction methods described in Section II-C. In particular, it is a direct mapping method, where each LR patch is mapped into its HR version by means of a specifically learned linear function. The whole upscaling procedure and a summary of the whole algorithm are given in Section III-B.

A. Building the double pyramid

The goal of our SR algorithm is to retrieve the underlying HR image I H from a degraded LR version of its I L , which is supposed to be originated according to the image generation model [START_REF] Park | Super-Resolution Image Reconstruction: A Technical Overview[END_REF]. We choose the blur kernel B to be a Gaussian kernel with a given variance σ 2 B . The value s is instead an integer scale factor (e.g. 3 or 4), which is the factor by which we want the LR input image I L to be magnified; i.e. if I L is of size N × M , the final super-resolved image ÎH will have a size of sN × sM .

For complexity reason, the SR algorithm later described is applied only on the luminance component Y of the input image I L (a colorspace transformation from the RGB to the Y IQ model is then possibly performed at the October 15, 2014 DRAFT beginning), whereas the color components I and Q are simply upsized by Bicubic interpolation to the final desired size sN × sM . In fact, since humans are more sensitive to changes in the brightness of the image rather than changes in color, it is a common belief that the SR procedure is worthy to be performed only on Y , so reducing the complexity of the algorithm by one third. Hereafter, then, all the image matrices and patch vectors must be intended as collections of pixel luminance values.

As a starting point for our internal dictionary learning procedure, we take the single pyramid depicted in Fig. 2.

Here, the top-level is represented by the LR input image itself (I 0 = I L ). From it, a finite number of "sub-levels" is created, according the the following relation:

I -n = (I L * B n ) ↓ p n , (9)
where p, the pyramid cross-level scale factor, is typically a "small" number (e.g. p = 1.25). The sub-level image I -n is then a particular rescaled version of the original image I L (the total rescale factor amount to p n ). As for the variance of the Gaussian kernel B n to which it is subjected, it can be computed according to the following formula, which is explained in [START_REF] Yang | Exploiting Self-Similarities for Single Frame Super-Resolution[END_REF]:

σ 2 Bn = n • σ 2 B • log(p)/ log(s) . (10)
Once the single pyramid is created, we propose now to interpolate each sub-level I -n by the factor p. The so

B. Gradual upscalings

Once the LR and HR dictionary sets, Y l and Y h , are formed, by populating them with the correspondences of self-examples found in the double pyramid described in Section III-A, the proper SR reconstruction algorithm starts.

The algorithm consists in a multi-pass procedure, where the input image is gradually magnified by an upscale factor equal to the cross-level scale factor p. Given s as the total scale factor to be achieved, the number of necessary passes it then:

N P = log p s . ( 11
)
If s is not a power of p, the image super-resolved after N P passes will be over-sized w.r.t. to the targeted dimension (sM × sN ); which means that an extra resizing operation is needed. I 0 will be super-resolved into I 1 , I 1 into I 2 , October 15, 2014 DRAFT and so until obtaining I N P , which will be possibly resized to obtain the SR estimated image ÎH with the desired dimension. The multi-pass SR procedure is illustrated graphically in Fig. 6.

When generally upscaling the image I n , this is first interpolated into the image U(I N ) from which a set of overlapping patches X l = {x l i } Nx i=1 is formed, by scanning it with a sliding window of dimension

√ D × √ D. Each
input patch x l i is processed singularly and, after the learning based patch reconstruction procedure, a corresponding HR output patch x h i is produced. By iterating for all patches, we have at the end a set of HR reconstructed patches X h = {x h i } Nx i=1 , which will be finally re-assembled to form the upper-level image I n+1 . In the following paragraph we describe the patch reconstruction method adopted. DM has been employed in SR example-based algorithms using external dictionaries [START_REF] Tang | Single-image super-resolution via local learning[END_REF], [START_REF] Kim | Single-Image Super-Resolution Using Sparse Regression and Natural Image Prior[END_REF], by using in particular the Kernel Ridge Regression (KRR) solution. In this case, the function space H is what is called a reproducing kernel Hilbert space (RKHS), and the single regression function f i is seen as an expansion of kernel functions, where Gaussian kernels are typically chosen.

For the sake of simplicity, we believe instead that, since in the case of internal learning the dictionary patches are more pertinent training examples, a simple linear mapping "can do the job". With this goal, H is taken as a linear function space

H = f (x) = M x | M ∈ R D×D , x ∈ R D ( 12
)
and the regularized empirical error ( 7) can be re-expressed as follows:

M i = arg min M ∈R D×D K j=1 y h j -M y l j 2 2 + λ M 2 F = arg min M ∈R D×D Y h i -M Y l i 2 2 + λ M 2 F , (13)
where Y l i and Y h i are the usual, respectively LR and HR, local training sets related to the patch x l i . In other words, we are looking for a linear transformation (i.e. the matrix M i ) to be directly applied to the LR input patch. This linear transformation is learned by observing the relations between the LR and HR dictionary patches which are neighbors with x l i , according to the machine learning pattern and a regression model, where Y l i is the matrix of the predictor variables or regressors, and Y h i is the matrix of the response variables. As the response variables are vectors and not scalars, we properly speak about multi-variate regression (MLR) [START_REF] Hyötyniemi | Multivariate regression -Techniques and tools[END_REF]. The solution to ( 13) is known, and can be written in a closed-form formula:

M i = Y h i Y l i T Y l i Y l i T + λI -1 (14)
October 15, 2014 DRAFT where I is the identity matrix. The equation ( 14) corresponds exactly to what we called "model generation" (Step 2 of the local learning procedure described in Section II-C). The prediction of the HR unknown patch (Step 3) is the straight application of the linear mapping learned:

x h i = M i x l i . (15)
Fig. 5 gives a rough depiction of how the DM reconstruction method works in the double pyramid.

2) Patch aggregation and IBP: By learning for each input patch x l i ∈ X l a linear function M i with the equation ( 14), and by applying this function to generate the related output patch, we end up with a collection of HR patches

X h = {x h i } Nx i=1
that need to be assembled to generate the current upscaling. Before the patch aggregation, the set of reconstructed HR patches X h and the equivalent set of LR patches from which they have been originated, X l , are added to the dictionary as new correspondences of patches to be used in future upscalings: the patches of the two sets, in fact, are equal in number, and a LR-HR relation stands. The update of the dictionary is performed by

simple set union, i.e. Y l = Y l ∪ X l and Y h = Y h ∪ X h .
The patches of the input image, and consequently also in the equally-sized output image, are taken with a certain overlap; that means that, when they are re-placed in the original positions, at each pixel location we have a set of different candidate values. We can see the image at this stage as a 3-D image, where the multiple values per pixel are the results of different local observations of the input image (i.e. different patches taken), and therefore contain different partial information about the unknown HR image. We obtain a single output image by convexly combining these candidates at each pixel location: the convex combination is done by simply taking uniform weights, i.e. each candidate is weighted by 1/N p , where N p is the number of overlapping patches contributing to that particular position.

After the image of the new level is formed, by overlapping and averaging, before it is used as a starting image for the next upscaling, it is further refined in an iterative fashion by the iterative back-projection (IBP) procedure. IBP is an additional operation adopted by several SR algorithms (e.g. [START_REF] Yang | Image Super-Resolution Via Sparse Representation[END_REF], [START_REF] Glasner | Super-Resolution from a Single Image[END_REF]), for which the output super-resolved image, once reconstructed, is "back-projected" to the LR dimension in order to assure it to be consistent with the LR input image, i.e. to assure it to be a plausible estimation of the underlying HR image, and conveniently corrected if errors are observed.

At the iteration t of this refining procedure, the generic reconstructed n-th level I t n is first back-projected into an estimated LR image Ît L :

Ît L = I t n * B n ↓ p n (16)
where B n is a Gaussian blur with variance as expressed in [START_REF] Fan | Image Hallucination Using Neighbor Embedding over Visual Primitive Manifolds[END_REF]. The deviation between this LR image found by back-projection and the original LR image is then used to further correct the HR estimated image:

I t+1 n = I t n + I L -Ît L ↑ p n * b , (17)
where b is a back-projection filter that locally spreads the differential error.

October 15, 2014 DRAFT

In Listing 1, our proposed SR procedure is described in a simplified manner, by reporting the pseudocode for the two main routines of the algorithm: "InternalLearning", where the double pyramid is constructed and the dictionary sets of LR and HR patches are initially formed, and "SingleUpscale", that reports the procedure to upscale a generic level I n to the upper level. To be noted, in particular, on line 15 the for loop, which consists of 3 instructions and implements the 3 steps of the local learning based patch reconstruction procedure described in Section II-C: nearest neighbor search, model generation, and prediction.

IV. EXPERIMENTAL RESULTS

In this section we conduct some experiments on the proposed single-image SR algorithm. In particular, in Section IV-A we evaluate the different contributions, in terms of implementation choices, that led to its final formulation summarized in Listing 1. Section IV-B provides some considerations about the complexity, intended both as time and space complexity, of the proposed algorithm. In particular, we evaluate the amount of extra complexity possibly brought by the double pyramid. In Section IV-C, finally, we compare our algorithm with other state-of-the-art methods, by both showing visual comparisons on super-resolved images and reporting quantitative results, according to the PSNR and SSIM metrics. PSNR and SSIM values are obtained as measures of the distance between the HR original image, from which the LR input image, for test purposes, has been originated, and the super-resolved image. The image generation model adopted is the one expressed in Equation ( 1), with the variance of the Gaussian blur σ 2 B set to 1 in all experiments. The interpolation method used is Bicubic interpolation. As for the various parameters of the algorithms, they have been "tuned" by empirically looking for their optimal values. Notably, the cross-level scale factor p is taken as p = 1.25; as for the patch size, instead, 5 × 5 patches are sampled from the internal images with a 4-pixel overlap. For each input patch, then, K = 12 are selected in the dictionary via NNS.

A. Evaluation of the different contributions

In this section we want to assess the different contributions of our algorithm, which have been discussed in Section III. With respect to the well-known single-image SR algorithm in [START_REF] Glasner | Super-Resolution from a Single Image[END_REF], two main contributions have been presented:

1) The employment of a DM reconstruction method (i.e. MLR), instead of NE;

2) The introduction of a different training and upscaling scheme, i.e. the "double" pyramid.

To singularly evaluate the two "ingredients" above, we test three different procedures (summarized in Table I), which all fall in the category of example-based single-image SR algorithms employing an internal dictionary. We first start with an algorithm, where a single pyramid is constructed and NE with non-local means (NLM) weights ( 2) is used as patch reconstruction method ("Algorithm 1"). This algorithm is very close in the spirit to the method in [START_REF] Glasner | Super-Resolution from a Single Image[END_REF], and thus its implementation can be considered as a reference for the mentioned method, except for for n ← 1, N L do Create the pyramid levels 3:

σ 2 Bn ← n • σ 2 B • log(p)/ log(s)
4:

I -n ← (I L * B n ) ↓ p n 5: U(I -n ) ← (I -n ) ↑ p 6:
end for 7:

for n ← 1, N L do Populate the internal dict.

M i ← Y h i Y l i T Y l i Y l i T + λI -1
18:

x h i ← M i x l i 19:
end for 20:

Form I n+1 with the constr. patches Y l ← Y l ∪ X l Update the LR dictionary 23:

X h = {x h i } Nx
Y h ← Y h ∪ X h
Update the HR dictionary This gain can be appreciated when observing the output images. Fig. 7 shows in fact the visual results obtained with the three different procedures, for two super-resolved images.

As we can observe from the zoomed-in areas of the images, with the finally proposed algorithm, we are able to produce finer details (see the branch of the tree behind the bird, or the texture of the hat of the woman). In particular, by observing the woman's hat, we can appreciate a sort of progress in the outcome of the three algorithms:

Algorithm 1 gives a pretty blurred result; Algorithm 2, thanks to the use of DM in the place of NE, shows instead more regular structures; the edges and the shapes of these structures look even sharper with the Proposed algorithm, where the DM functions have been computed on the interpolated patches of the double pyramid.

B. Considerations on the algorithm complexity

In order to evaluate the time complexity of the algorithm, we ran two versions of it, featuring the usual single pyramid and our double pyramid, for two different scale factors (3 and 4). The single-pyramid implementation gives an idea of the complexity of several algorithms in the literature (e.g. [START_REF] Glasner | Super-Resolution from a Single Image[END_REF]- [START_REF] Yang | Learning context-aware sparse representation for single image super-resolution[END_REF]). The goal of this test is to evaluate the penalty brought by the use of our double pyramid, in terms of increased complexity. Table III summarizes the results of the tests made.

As we can see from Table III, the double pyramid leads to an extra complexity in the order of about 10%. The increase in the computational cost is mainly due to the fact that bigger LR vectors are processed (LR patches have the same size as HR patches). Nevertheless, we believe that the complexity increase is still within a tolerable extent. To evaluate the space complexity, i.e. memory storage requirement, we can instead compute an estimation of the size of the internal dictionary. Here, the only discriminating factor between the single and the double pyramid is the size of the LR patches. In fact, in the case of double pyramid, both patches have the same size, whereas the LR patches are p 2 smaller in the case of single pyramid (where p is the small scale factor used at each pass). Given this, it is easy to compute the ratio between the two dictionary sizes:

October 15, 2014 DRAFT R = 2 1 + 1 s 2 . ( 18
)
In our tests p was set to 1.25, which corresponds to a 22% increase of the storage requirement.

C. Comparison with state-of-the-art algorithms

In this section we perform a comparative assessment of our method with other single-image SR algorithms in the state-of-the art, by extending the comparison also to SR methods based on external dictionaries. For this purpose, we consider Bicubic interpolation as a reference for traditional analytical interpolation methods, and four other example-based SR algorithms. The characteristic of the latter, as well as those ones of our proposed method, are summarized in Table IV. For the first three methods in the table, the original code of the respective authors, possibly slightly modified to make the comparison fair, has been used. For the "pyramid" method of [START_REF] Glasner | Super-Resolution from a Single Image[END_REF], instead, the third-party code of the authors of [START_REF] Yang | Exploiting Self-Similarities for Single Frame Super-Resolution[END_REF] has been adopted. Table V reports the performance results of the algorithms considered (PSNR and SSIM values), with the usual set of seven test images, and 3 and 4 as scale factors.

Table V shows clearly that our method outperforms the other algorithms in terms of objective quality of the super-resolved images, for all the images and the two scale factors considered. The results are confirmed when observing the visual comparisons (Fig. 8, Fig. 9, and Fig. 10).

From the visual results presented, we can see that methods based on external dictionaries ("LLE-based NE", "NN NE", and "Sparse SR") often present blurring and ringing artifacts (see e.g. the Bike images in Fig. 9). Results

for the two algorithms based on an internal dictionary (the "pyramid" algorithm of [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] and ours), instead, are certainly more pleasant at sight, presenting sharp edges and smooth artifact-free results in the regions with no texture. However, the algorithm of [START_REF] Glasner | Super-Resolution from a Single Image[END_REF] in some cases shows results that look somehow "artificial", with oversmoothed areas or unnatural edges (see Lena's eye in Fig. 10e, whose shape is deformed). Our algorithm succeeds also in avoiding these undesired effects. reference patch in the interpolated version of the starting image U (I 0 ), x l i , 3 LR neighbors are found in the "side pyramid" of interpolated levels (y l 1 , y l 2 , y l 3 ). Thanks to these and the corresponding HR neighbors (y h 1 , y h 2 , y h 3 ), a linear function M is meant to be learned to directly map x l i into its corresponding HR output patch x h i .

Fig. 1 .

 1 Fig. 1. Operating diagram of the example-based SR procedure.

  good amount of self-examples. Let D denote an image downscaling operator, s.t. D(I) = (I) ↓ p , where p is a conveniently chosen small scale factor; and let U denote the dual upscaling operator, s.t. U(I) = (I) ↑ p . Let I L still indicate the LR input image. In [22], for example, J L = U(D(I L )), which represents a low-pass filtered version of the LR input image I L , is used as source for the LR patches, whereas the HR example patches are directly sampled from the input image (J H = I L ). Freedman and Fattal propose in [21] an equivalent approach, except that October 15, 2014 DRAFT a high-pass version of I L (J H = I L -J L ) is used to get HR training patch. In [18], instead, we have J L = (I L * B) and J H = U(I L ): the LR examples patches are taken again from a low-pass filtered version of I L , obtained by blurring the original image with a Gaussian blur kernel B, and the corresponding HR patches are taken from an upscaled version of I L , which does not alter its frequency spectrum content.

Fig. 3 .

 3 Fig. 3. Percentage of selected neighbors for each sub-level of the pyramid, for two different images.

  obtained interpolated level U(I -n ), where U is an upscaling operator s.t. U(I) = (I) ↑ p , is an image with the same size as the original non-interpolated level located just above in the pyramid I -n+1 (except for possible 1-pixel differences, due to the non-integer interpolation factors). We can then consider the pair constituted by U(I -n ) andI -n+1 a pair of, respectively, LR and HR training images, from which derive a set of self-examples. By using all the pairs {U(I -n ), I -n+1 } for n = 1, . . . N L, where N L is the chosen number of sub-levels, and sampling at corresponding locations pairs of, respectively, LR and HR patches of equal size √ D × √ D, we can then form our LR and HR internal dictionary sets: Y l = {y l i ∈ R D } Ny i=1 and Y h = {y h i ∈ R D } Ny i=1 . Fig. 5 reports the scheme described, with the "double pyramid" formed by the traditional image cascade and, next to it, a side pyramid of interpolated levels.

1 )

 1 Direct mapping of the self-examples via multi-linear regression: While most of the "pyramid-based" SR algorithms in the literature [23]-[25] make use of a neighbor embedding (NE) based procedure to express each input and output patch in terms of combinations of self-examples, we follow instead the direct mapping (DM) approach. As explained in Section II-C, DM aims at learning, thanks to the LR and HR local training sets, a mapping to directly derive the single HR output patch as a function of the related LR input patch.

Listing 1

 1 Single-image SR via linear mapping of interpolated self-examples 1: procedure INTERNALLEARNING(I L , N L, s, p, σ 2 B ) 2:

8 : 9 : 15 :

 8915 Sample patches from U(I -n ) and add to Y l Sample patches from I -n+1 and add to Y h 10: end for 11: end procedure 12: procedure SINGLEUPSCALE(I n , p, Y l , Y h ) 13:U(I n ) ← (I n ) ↑ pUpscale the current level 14:Extract LR patches fromU(I n ) → X l = {x l i } Nx i=1 for i ← 1, N x doSingle patch reconstructions 16: Find the local train. sets of x l i by NNS → Y l i , Y h i 17:

Fig. 4 .Fig. 5 .

 45 Fig.[START_REF] Tappen | Exploiting the Sparse Derivative Prior for Super-Resolution and Image Demosaicing[END_REF]. Operating schemes of the local learning based reconstruction procedure, for the two approaches described (NE and DM). From the image it is clear how NE exploits the intra-space relationships, by learning a model among the LR patches and applying it on the HR patches. DM, instead, exploits the "horizontal" relationships, by attempting to learn the mapping between the two spaces.October 15, 2014 DRAFT

Fig. 6 .Fig. 8 .Fig. 9 .Fig. 10 .

 68910 Fig. 6. Estimation of the HR image by gradual upscalings. The original image I L , by 4 upscalings by a factor of p, is super-resolved into I 4 , that exceeds in dimension the desired scale factor s. ÎH is obtained by a finally resizing operation.

  a nearest neighbor search (NNS). A desired number of neighbors of the LR input patch x l i is searched among the LR self-examples Y l , and consequently an equal number of HR neighbors is determined. Let Y l i indicate the matrix collecting, column by column, the selected LR neighbors, and let Y h i indicate the matrix of the corresponding HR neighbors. Thanks to the local sets Y l i and Y h i , the unknown HR patch x h i is then predicted. The whole local learning procedure can be summarized in 3 steps. Model generation: A model M i for the local reconstruction is computed. M i generally depends on both the LR input patch and the local training sets:

	1) Nearest Neighbor Search (NNS): The local training sets Y l i and Y h i are determined.
	2)

respect, example-based SR algorithms consist in patch-based procedures, where the HR output image is built by means of single patch reconstructions, as many as the number of LR patches the LR input image is partitioned into.

For example-based SR, two main approaches to reconstruction are possible: neighbor embedding (NE) and direct mapping (DM). In both cases, for each input patch x l i , LR and HR local training sets are formed, by performing

TABLE I SUMMARY

 I OF THE INTERNAL-DICTIONARY PROCEDURES CONSIDERED TO EVALUATE THE DIFFERENT CONTRIBUTIONS OF OURALGORITHM. in the code configuration and the choice of the parameters. With respect to Algorithm 1, "Algorithm 2" uses a DM patch reconstruction method instead of NE, i.e. the MLR method described in Section III-B that linearly maps each LR patch into the related HR patch. The finally proposed algorithm introduces then the double pyramid scheme, featuring the side pyramid of interpolated levels. TableIIpresents the PSNR and SSIM values for all the considered algorithms, when tested on seven input images and for two different scale factors(s = 3, 4).As we can observe from the table, from Algorithm 1 to the Proposed algorithm we have almost always a progressive consistent improvement in the SR performance, with our finally proposed procedure presenting an average gain of about 0.22 dB w.r.t. to the traditional scheme based on a single pyramid and NE (Algorithm 1).

		Rec. Method Double pyr.
	Algorithm 1 NE	No
	Algorithm 2 DM	No
	Proposed	DM	Yes
	possible slight differences

TABLE II PERFORMANCE

 II RESULTS (PSNR AND SSIM VALUES) OF THE THREE DIFFERENT ALGORITHMS USING AN INTERNAL DICTIONARY, WHEN SUPER-RESOLVING SEVERAL IMAGES FOR SCALE FACTORS OF 3 AND 4.

						Algorithm 1	Algorithm 2	Proposed
				Image	Scale	PSNR SSIM	PSNR SSIM	PSNR SSIM
				Bike	3	23.13	0.792 23.20	0.796	23.30	0.799
				Bird	3	33.71	0.884 34.06	0.890	34.13	0.890
				Butterfly	3	27.08	0.833 27.38	0.840	27.56	0.841
				Hat	3	29.95	0.651 30.11	0.655	30.11	0.655
				Head	3	32.43	0.633 32.47	0.667	32.43	0.668
				Lena	3	30.68	0.770 30.91	0.775	30.89	0.775
				Woman	3	30.33	0.862 30.41	0.866	30.52	0.867
				Avg gain w.r.t. A1	-	-	0.18	0.009	0.23	0.010
				Bike	4	21.58	0.685 21.53	0.688	21.63	0.689
				Bird	4	30.61	0.810 30.89	0.824	31.01	0.826
				Butterfly	4	24.68	0.763 24.71	0.772	25.05	0.775
				Hat	4	28.54	0.553 28.60	0.556	28.53	0.555
				Head	4	31.17	0.556 31.28	0.591	31.23	0.590
				Lena	4	29.02	0.681 29.22	0.687	29.28	0.689
				Woman	4	27.60	0.778 27.90	0.793	27.96	0.793
				Avg gain w.r.t. A1	-	-	0.13	0.012	0.21	0.013
							TABLE III
	AVERAGE RUNNING TIME OF THE ALGORITHM, FOR TWO SCALE FACTORS, WITH SINGLE OR DOUBLE PYRAMID. TIME IS EXPRESSED IN
							SECONDS.
	Scale LR size	N. Passes Single Pyr. Double Pyr.	∆T
	3	85 × 85 5	75	83		+10.7%
	4	64 × 64 7	111	120		+8.1%

TABLE IV SUMMARY

 IV OF OUR METHOD AND THE FOUR EXAMPLE-BASED SR ALGORITHMS CONSIDERED FOR THE COMPARISON.

	Method	Reference	Dictionary	Rec. Method
	LLE-based NE	Chang et al. [9]	External	NE with LLE weights (3)
	Nonnegative NE	Bevilacqua et al. [33]	External	NE with NN weights (4)
	Sparse SR	Yang et al. [14]	External	Sparse coding
	Pyramid	Glasner et al. [23]	Internal, single pyramid	NE with NLM weights (2)
	Proposed	This paper	Internal, double pyramid	DM via Multi-linear Regress.

October 15, 2014 DRAFT

This work was supported by the joint research lab INRIA-Alcatel Lucent Bell Labs. is with IMT Institute for Advanced Studies Lucca,

V. CONCLUSION

In this paper we presented a novel single-image single-image (SR) method, which belongs to the family of example-based SR algorithms, using a dictionary of patches in the upscaling procedure. The algorithm originally makes use of a "double pyramid" of images, built starting from the input image itself, to extract the dictionary patches (thus called "self-examples"), and employs a regression-based method to directly map the low-resolution (LR) input patches into their related high-resolution (HR) output patches. When compared to other state-of-the-art algorithms, our proposed algorithm shows the best performance, both in terms of objective metrics and subjective visual results. As for the former, it presents considerable gains in PSNR and SSIM values. When observing the superresolved images, also, it turns out to be the most capable in producing fine artifact-free HR details. The algorithm does not rely on extra information, since making use of an internal dictionary automatically "self-adapted" to the input image content, and also the few parameters have proven to be easy to tune. This makes it a particularly attractive method for SR upscaling purposes.


Sophie Derrot
email: sophie.derrot@bnf.fr

Jean-Philippe Moreux
email: jean-philippe.moreux@bnf.fr

Clément Oury
email: clement.oury@bnf.fr

Stéphane Reecht
email: stephane.reecht@bnf.fr

Preservation of ebooks: from digitized to born-digital

Keywords: design, documentation, experimentation, legal aspects, performance, security, standardization, verification digital library, legal deposit, born-digital archives, digitization of heritage content, accessibility, ebook, DRM, EPUB, ONIX, PDF

The scope of digital curation at the BnF covers documents digitized from BnF collections as well as born-digital material bought by the BnF or collected under its legal deposit mandate. It is therefore critical for the library to investigate if common approaches may be adopted for similar document types, whatever their origin may be. This paper proposes to focus on the case of electronic books (or ebooks), by comparing the way BnF teams intend to ensure the long term preservation of those directly digitized by the library and those that will enter through legal deposit.

Data and metadata formats are different, even though EPUB appears as the reference format for both kinds of ebooks. Acquisition procedures are necessarily specific. However, for the other steps of the treatment process, digitized and born digital books should follow similar and parallel workflows: indexing in BnF General Catalogue, access through the digital library Gallica and preservation in SPAR, BnF's digital repository. Common validation tools, characterization schemes and preservation metadata will be used in order to preserve both faces of French digital heritage.

INTRODUCTION

The scope of digital curation at the BnF -i.e. the set of processes intended to acquire, index, give access and preserve digital resources -covers two distinct kinds of digital material:

• on one hand, documents digitized from physical media (books, engravings, maps, etc.) held in BnF's collections;

• on the other hand, born-digital material bought by the BnF or collected under its legal deposit mandate.

Even though these resources are distinct in terms of acquisition method, legal status and heritage value, and even though they may depend on different organizational entities, we find in both cases similar types of documents: books, periodicals, images, audio and video.

It is therefore critical for the library to investigate if common approaches may be adopted for similar document types, whatever their origin may be. This paper proposes to focus on the case of ebooks, by comparing the way BnF teams intend to ensure the long term preservation of those directly digitized by the library and those that enter through legal deposit. It intends to see if they present similar characteristics and issues regarding long term preservation, if the same tools and the same workflows can be used, and where expertise can be shared. This paper does not take into account questions related to ebooks acquired for payment, as the topic is not yet mature enough. However, when the procedure for handling them is eventually designed, it will benefit from the double experience of digitization and digital legal deposit.

EBOOKS AT THE BIBLIOTHÈQUE NATIONALE DE FRANCE 2.1 Digitization: from image files to ebooks

The BnF has been involved in the field of digitization since 1992 through a digital library, Gallica, with nearly 2 million documents (books and periodicals, newspapers, engravings, manuscripts, objects, sound recordings, audiovisual material).

The BnF has recently decided to enhance the public dissemination of its digital contents through the production of electronic books, in addition to image and text modes. The aim of this new delivery format is to take benefit from some of the advantages of dedicated electronic book formats in comparison with the standard delivery formats usually offered by digital libraries (web, PDF):

• nomadic reading outside the digital library's website, on dedicated devices in a dedicated ebook format, EPUB;

• better dissemination of contents and better accessibility of digital contents for visually impaired people.

During the period 2011-2013, this effort has been embodied in two separate digitization programs: integration of an EPUB production process in a mass digitization program; and reprocessing of documents previously digitized, with the production of tables of contents and EPUBs. Digitization is either performed in-house or by a private contractor.

The implementation of this new format in the library has required much interaction between all the BnF teams involved in heritage digitization and some radical changes in the way the library considers its digitization activity: program, which needs to be fed with thousands of documents every year.

• Publishing: a "heritage EPUB" template suitable for accommodating a variety of types of documents has been defined, as well as an EPUB production charter. Again, the library must change its habits: it no longer produces facsimiles of heritage documents but a totally new editorial product.

• Quality Assurance: the BnF automatic input control system has evolved, in order to analyze this new format (metadata, technical requirements, etc.). A specific EPUB quality assurance team has been set up within the quality assurance section of the digitization service, to perform visual checking of EPUBs on reading devices and assessment of text quality.

• Archiving and long-term preservation: section 4.2 below describes the ingest process of the digitized books in the BnF long-term archiving system, SPAR.

In 2014, the Legal Deposit of ebooks is an opportunity to leverage the EPUB expertise acquired from the digitization programs.

Digital legal deposit: from web harvesting to direct deposit

In August 2006, an extension of the law on legal deposit mandated the BnF to collect, preserve and provide long-term access to all French online publications. Until recently, the BnF digital legal deposit team mainly focused on setting up a complete web archiving workflow 1 . Legal, heritage and technical reasons explained this choice. On one hand, websites were considered the most at-risk documents. Besides, tools and best practices were already available thanks to international cooperation. On the other hand, the ebook market was not very dynamic, both in terms of production and sales, and the production and distribution workflow were still maturing on publisher's side.

Finally, in the absence of a decree enforcing the law, the BnF was not able to ask for content distributed under payment and was limited to harvesting freely available resources.

When the decree on digital legal deposit was published, in December 2011 -it is now part of the "Heritage code" -the BnF started designing its ebooks deposit system. This entry track is still under development, but some critical decisions have already been taken. First, a deposit system was preferred to web harvesting for ebooks. The BnF could have chosen to crawl ebooks hosting platforms, as it currently does for news websites [START_REF] Oury | When press is not printed: the challenge of collecting digital newspapers at the Bibliothèque nationale de France[END_REF]. However, direct deposit, via an FTP platform, was more appropriate to allow unitary treatment and cataloguing of ebooks. Moreover, in several cases, ebooks distributed online are not directly hosted on the website of the online bookstore, which is only the place where financial transaction occurs; the document itself or the link to download it is then sent to the purchaser by another mean (e.g. by email). In that case, web harvesting would not have been efficient.

Second, it was decided to work with ebook "distributors". In the French ebook market, the publisher is in charge of creating the book (both the intellectual content and the digital document); the digital bookseller is in charge of promoting and selling the ebook to end-users; the role of the distributor is to make a bridge between these two stakeholders: it receives the ebook, checks its 1 See [START_REF] Illien | The state of e-legal deposit in France: looking back at five years of putting new legislation into practice and envisioning the future[END_REF] for questions related to digital legal deposit legislation; and [START_REF] Follic | Putting it all together: creating a unified web harvesting workflow at the Bibliothèque nationale de France[END_REF] about the web harvesting workflow set up by BnF.

format, verifies and enhances the quality of its metadata, and sends it to the bookseller.

Working with distributors appeared very quickly as the best solution as:

• there are few distributors compared to hundreds of publishers;

• the BnF benefits from a first set of quality controls performed by distributors, both for the ebooks and their metadata;

• distributors receive ebooks without DRMs; they are therefore able to send them to the library without DRMs.

Parallel workflows: using common tools for digitized and born-digital books

Finally, an internal workflow has been designed. Ebooks deposited by distributors along with their metadata will be received on a dedicated FTP platform. A first set of checks will be performed by the library, in order to ensure that all declared documents are available, to verify that data and metadata are consistent, and to validate the format of the ebooks and metadata.

If the package that has been delivered passes the check, the ebook receives a legal deposit number and the distributor is informed that the document has been deposited. If not, the library requests a new deposit from the distributor.

The entry system is necessarily different for digitized and born digital books. However, for the other steps of the treatment process, the library intends that both kinds of documents follow similar and parallel workflows:

• Descriptive metadata will be ingested (and potentially corrected by human cataloguers) in the BnF General Catalogue, which indexes most published resources hosted in the Library.

• Access to digitized books will be given via Gallica, the BnF digital library; access to deposited ebooks will be given via Gallica intra muros. This is a specific version of Gallica, which is only accessible within the Library premises, and which gives access to content protected by intellectual property rights (as recent documents entered through legal deposit are).

• Preservation will be ensured by the BnF digital repository, SPAR, which is described more thoroughly in section 4 of this paper.

This choice has been made in order to avoid reinventing the wheel and redeveloping already existing tools. However, the reader's perspective and needs were also taken into account: readers would probably have been lost if forced to use two series of tools and applications. In short, BnF readers should not need to know BnF internal systems, and should not wonder if they are looking for a digitized or a born digital document before accessing it.

DIGITIZED AND BORN-DIGITAL EBOOKS: TECHNICAL CHARACTERISTICS

Management of ebooks, from entry to access, has thus become a strong issue across the whole of the BnF. Questions related to preservation have been particularly taken into account, as both digitization and digital legal deposit channels are intended to deliver documents that will be accessible over the long term. From this point of view, do both types of documents present the same characteristics? This raises two series of questions especially important in a preservation perspective, the one related to ebook formats, the other related to their metadata.

Formats

Digitization track

In 2011, the BnF chose EPUB 2 as support of its digitized books program, because it was the de facto technical standard for digital reading. The alternative "fixed layout" was not used because it

was not yet specified at this time.

BnF ebooks have been designed to present as few problems as possible in terms of preservation:

• EPUB is based on standards and formats already mastered: XHTML, CSS, Dublin Core, etc.

• They are produced under a BnF charter: their content and structure are well known, and remain consistent over digitization programs.

• They do not include contents or formats that are potentially "risky" for preservation: multimedia files, programming code for interactivity, etc.

The next mass digitization program (2014-2017) will foster the accessibility to digital contents with the EPUB 3 format. This new version offers a wide range of accessibility mechanisms based on the semantic annotations of content. These mechanisms are all based on markups (HTML5 markup and EPUB 3 specific markup). Consequently, the risk for preservation is considered sufficiently low.

Legal deposit track

Historically the jungle of commercialized ebook formats is very dense, as every content or device producer has tended to create its own format (PDB, LRF, LIT, MOBI, etc.). Over the past couple of years though this density has tended to reduce, to the advantage of standardized formats (EPUB) or closed-source formats of the market leaders (such as Amazon's KF8). Even if it does not solve every issue, this simplification is quite a relief from a preservation point of view, especially in a legal deposit context which theoretically extends the perimeter of the objects concerned to all produced and commercialized formats.

Above all, it is necessary to determine the limits of the scope of legal deposit. We tried to concentrate our efforts on files which can be easily defined as "books" in comparison with printed books. Therefore, ebooks on formats such as TXT or DOC are initially excluded, as they are closer to production formats than to diffusion formats. These formats are never to be found on commercial markets and distributors do not work with them. At the other end of the ebook channel, physical reading devices and their software won't be concerned either by this deposit track.

Once these exclusions have been made

, what is left? During the initial discussions, publishers and distributors made clear that the most frequently produced and sold formats were EPUB 2 and PDF; MOBI and EPUB 3 were in minority. Distributors add DRMs to these files or send them to international online booksellers (Apple, Amazon and Google); these online booksellers take then care of the migration into their own format.

It was agreed that ebooks with DRMs will be excluded, to permit manipulations of the files during the deposit process. Frequent copies are necessary for deposit, access and preservation processes, yet they are often prevented by DRMs. Setting up a legal deposit system of this kind of protected material didn't seem feasible 2 . Our publisher partners agreed to that pragmatic position, which simplifies the whole process. Closed source formats won't be deposited for the same reasons: preservation systems will probably be unable to deal with them, especially in the long term.

In spite of the ambiguity of this position -in contradiction with the traditional objective of comprehensiveness of legal deposit -, it seemed more reasonable to proceed in this way in order to ensure long-term access and preservation -which are also part of the objectives of legal deposit.

Metadata

Digitized ebooks

The EPUB format embeds metadata (Dublin Core) to provide information about the digital publication. These metadata are exported from the BnF catalogue. Some of them have particular values in a library context:

• ID: ark3 of the digital document in the BnF digital library (Gallica).

• Source: HTML link to this digital document.

• Relation: catalogue entry of the heritage document.

EPUB 3 version offers a richer description of the bibliographical metadata and enables the inclusion of accessibility compliance metadata in an ONIX4 message.

But the EPUB file, as every digital object in the library, must also be characterized within the BnF IT systems:

• Version: EPUB 2 or EPUB 3?

• Format: standard EPUB or fixed layout EPUB?

• Quality: Bronze and Silver are heritage EPUBs produced by mass digitization programs, with two text quality levels; Gold are editorial EPUBs (enrichments, editorial works, etc.).

• Accessibility: does the EPUB embed accessible features?

• Production information: service provider, tools used, date of production, etc.

This information is relevant for various uses: diffusion, preservation, production, etc.

Deposited ebooks

The main idea when putting in place an ebook legal deposit was automation, including re-exploitation of metadata created by publishers and distributors for their own needs. The most used format for carrying this metadata in the book trade is ONIX for Books, a XML standard designed to support computer-tocomputer communication of bibliographic information. ONIX files are generally completed by distributors from information provided by publishers and then sent to online booksellers along with ebook files.

• Advantages of ONIX files attached to ebooks by the distributors are their richness and precision: this information has to be exact because of its commercial purpose.

• On the other hand, quite a few of the data are useless from a librarian point of view (for example: prices for every country where the ebook is commercialized) and some important bibliographic metadata is often lacking (ISBN of the printed version is not always provided).

To make existing ONIX files as useful as possible for us, an ONIX model including the BnF specifications was defined by librarians and proposed to publishers and distributors. In the meantime, an ONIX-to-Intermarc5 conversion was developed to allow an easy and automatic transformation of the trade information into bibliographic notices. This conversion also enables the use of this metadata for preservation needs: it will be reused within the METS file attached to the EPUB or PDF file into the Submission Information Packages (SIP).

COMMON APPROACHES FOR INGEST? 4.1 SPAR in a nutshell

SPAR, the Scalable Preservation and Archiving Repository, is the BnF preservation system [START_REF] Derrot | Preservation is Knowledge: A community-driven preservation approach[END_REF]. It has been developed since 2005, and seeks to conform to the OAIS model. Its initial scope was to automate all entities that could be automated, and to offer a wide range of functions, in order to preserve various types of asset. Up to now, development was mainly concentrated on the Ingest, Storage, Data management and Administration modules.

The sets of documents to be ingested are grouped into tracks and sub-tracks (channels), according to their nature (digitized books, audiovisual files, web archives, administrative records…), to their legal frameworks, and to the way the BnF plans to manage their life cycle and apply preservation strategies. At the present time, SPAR ingests objects in four tracks: Digitized documents and associated files (except audiovisual), Audiovisual objects, Web legal deposit (ARC or WARC files), Third party storage (various kinds of files, from partners outside the institution); several others are in progress, including the Negotiated legal deposit track that will be presented in 4.3.

Each track needs a specific preingest module, because no producer 6 is able yet to deliver well-formed SIPs according to SPAR's requirements. These modules build SIPs depending on specific settings and send them to a generic ingest module, which transforms them into Archival Information Packages (AIPs).

Four levels of formats are distinguished in SPAR, corresponding to four levels of risk: stored (the most unsafe), identified, known and managed [START_REF] Ledoux | SPAR: From Design to Operations[END_REF]. A "managed" format has published documentation, at least one reference tool and a characterization scheme. Besides, the BnF may define use restrictions depending on the producer.

Metadata for package and preservation information are contained in METS files, with PREMIS elements. Metadata for data management are expressed in RDF.

Ingest of digitized books

EPUB files aren't considered preservation copies of digitized books, but a medium for dissemination. Though, their cost and their value explain that the BnF intends to preserve them in the long term.

When they enter SPAR in the "Preservation digitization track", EPUB and adaptative7 files are controlled and characterized. It was necessary to find a characterization tool and a characterization scheme for EPUB files. This difficulty was solved by using and adapting Epubcheck 38 , in order to improve this software and make it a basic characterization tool. This solution is not yet completely satisfactory, and we are still looking for a characterization scheme in order to record the preservation metadata extracted by the tool. This is the reason why it can't be said yet that EPUB is a "managed" format in SPAR.

EPUB 2 and 3 files are accepted, in both standard and fixed layout for EPUB 3. This corresponds to the three kinds of ebook formats produced or to be produced soon in our digitization process. The quality level (Bronze, Silver or Gold, see 3.2.1) will not be checked, but the information declared by the digitization contractor will be preserved, as well as other production information.

Ebooks are at the moment considered as associated objects of books digitized in image mode (TIFF and now JPEG2000 files). They are described in the METS manifest with specific fileGrp use (epub or adaptative) and structMap type (ebook) 9 . So ebooks can't be ingested alone: they are delivered either with new digitized books or while reworking digitization (pictures are redelivered with new OCR and EPUB files). The possibility to deliver an isolated ebook and then create a new completed version of an existing AIP is yet to be investigated.

Ingest of deposited ebooks

As explained in 4.1, a dedicated preingest module will be developed for the "Negotiated legal deposit track". The legal deposit is considered "negotiated" as the form of the delivery is negotiated between the distributor and the library, so that for example not all formats will be accepted.

This module will get the package ready for ingest, joining together the ebook file (EPUB or PDF), the original ONIX file, possibly a picture file of the book cover, and finally the METS manifest.

The role of the SPAR system in the legal deposit workflow is critical. On one hand, the preingest module will provide fundamental information to the General Catalogue, such as the ARK number of the ebook file, i.e. its persistent identifier. On the other hand, SPAR will deliver the deposited ebooks to the access platform and application.

Within SPAR itself, two channels will be set up, according to the ebook format and its components:

• Ebooks whose format is considered "managed" after all quality checks and characterization will be ingested in the first channel.

• Files that are valid from a format specification point of view but which present some preservation threats will be ingested in the second channel. For example, EPUB files containing Flash or JavaScript elements are not considered managed as BnF does not have sufficient confidence in its capability to preserve them in the long term.

Thanks to the digitization track, Epubcheck has already been chosen to perform a new format check on EPUB files when they enter SPAR. But the choice has still to be made for PDF. It is currently investigated if Apache™ Tika 1.5 10 may be used in addition to Jhove: the first one to characterize the files; the second one to validate them against the results of Tika's characterization and against pre-defined profiles. This will also be an opportunity to improve other tracks containing PDF files (particularly administrative records), where Jhove is the only and imperfect tool for validation and characterization.

For the legal deposit track, XMP will probably be used as a characterization scheme for both formats PDF and EPUB. If this characterization format is considered relevant, it will in turn likely be used for the EPUB files produced by digitization. Thus, files and formats analyzes would be performed in a consistent manner. Every file of each format will be handled with the same tools and schemes, regardless of the channel or the track it belongs to. Only the application rules will differ.

Some critical choices are thus still to be done. The BnF intends to proceed on these questions during the current year, and to ingest the first deposited ebooks at the end of 2014 or the beginning of 2015.

From a digital strongbox to digital library stacks

In the current situation, that is for the digitization track as well as other tracks (e.g. web archiving), there is a fork in the document management workflows between access and preservation. SPAR is not a step between entry and access, but only one branch of the fork, separated from the access branch. This current solution is not really satisfactory, as SPAR still appears as a digital strongbox, not as BnF digital stacks.

The ebook legal deposit tracks will represent a chance to improve this situation. In this workflow, the SPAR system will play the role of the central application, as it will receive the documents from the entry step, send information to the catalogue and provide the books to the access application.

However, this architecture decision implies some challenges:

• First, SPAR will need to show a better ability to communicate with other library applications. • Second, it should develop its capability to provide the expected files according to defined rules (for example if only one format for a specific book is requested). • Third, the response time of SPAR must be guaranteed, because every slowdown or interruption will increase the delay between the entry of a document and its visualization.

In this way, the BnF will be able to ensure that it gives access only to documents that are already ingested in the repository. There won't be any difference anymore between what is preserved and what is offered to readers.

10 https://tika.apache.org/1.5/index.html.

CONCLUSION

Ebooks from legal deposit and digitization tracks differ in various aspects: they have different legal statuses; they were not acquired for the same goals and for the same audiences; and BnF's preservation mandate for them is different. In one case, the BnF (or its contractor) is the producer of the documents; in the second case the BnF is only the depository.

Moreover, even though both kinds of ebooks are available in the same formats (EPUB and PDF), their technical characteristics may differ (use of JavaScript, of embedded content, etc.).

It is nonetheless possible to adopt common approaches and to leverage developments performed for one track to improve another track. Systems originally built for digitized books (Gallica/Gallica intra muros for access, SPAR for preservation) will be used for ebooks received through legal deposit. Common tools (Epubcheck, Tika, Jhove) and common characterization schemes (XMP) are applicable in both cases.

Benefiting from expertise of various teams with different backgrounds has actually been a strength: crossing points of views brought a global vision considering all aspects of ebooks preservation.

About issues of preserving digital resources with DRMs, see[START_REF] Aparsen | Report on DRM Preservation[END_REF].

ARK (Archival Resource Key) is a persistent identifier system created and managed by the California Digital Library. See https://wiki.ucop.edu/display/Curation/ARK.

ONline Information eXchange. See http://www.editeur.org/8/ONIX.

Intermarc, in the family of MARC formats, is the BnF format for bibliographic metadata.

In the OAIS model, the producer is the external or internal entity that produces the resource and transfers it to the Archive with the mandate to preserve it.

DAISY format, used to create text or audio books for visually impaired people.

https://github.com/IDPF/epubcheck.

See BnF's METS profile for SPAR: http://www.loc.gov/standards/mets/profiles/00000039.xml.