Abstract-Compression methods based on inpainting have been an active field of research in the past decade. Videos are especially challenging for this kind of methods, since real-time decompression requires highly efficient algorithms. Dedicated inpainting-based video codecs have so far focused on efficient frame-by-frame reconstruction without exploiting redundancies in time. As a remedy, we propose a modular framework that combines a classical prediction and correction approach with suitable structures for fully inpainting-based methods. The core idea of these techniques is to store values only at a small number of positions, and reconstruct missing regions via inpainting. Our generic framework supports any algorithm that generates such sparse representations. As a concrete demonstrator, we provide a prototypical implementation of our framework by supplementing all modules with methods based on partial differential equations (PDEs): Dense variational optic flow fields yield accurate motioncompensated predictions, while homogeneous diffusion inpainting and pseudodifferential equations are applied as intra prediction and residual compression techniques. With these components, we are able to outperform other inpainting-based video codecs in terms of quality and speed. For the first time in inpaintingbased video compression, we can decompress FullHD (1080p) videos in real-time with a fully CPU-based implementation.
I N today's world, videos are a vital part of our communication, be it personal or professional. According to Cisco's Global 2021 Forecast [1] , video traffic will reach 227.6 Exabytes (227.6 million Terabytes) per month in 2021, making up 82% of all IP traffic. It is therefore an important task to constantly continue research on improving codecs for video compression.
Currently, the most well-known and widely used codecs belong to the MPEG family [2] . They are based on hybrid video coding which combines a prediction and a correction step where prediction depends on the frame type. Intra frames rely solely on information from within themselves. Propagating values from preceding or subsequent frames along motion vectors approximates inter frames. The correction step is identical for both types: The residual contains the difference to the original frame and can be efficiently compressed, if the initial prediction was of high quality.
Both intra prediction and residual storage use image compression techniques, where traditional video codecs apply transform-based methods. For images, however, codecs of this type have been successfully challenged by inpainting-based techniques. Their core idea is to keep values only at a few carefully selected points (the so-called inpainting mask) and reconstruct the missing image parts via inpainting. The state of the art for color images is a PDE-based method by Peter S. Andris, P. Peter, R. Mohideen Kaja Mohideen, and J. Weickert are with the Mathematical Image Analysis Group, Saarland University, Saarbrücken, Germany, e-mail: {andris,peter,rakaja,weickert}@mia.unisaarland.de. S. Hoffmann is with Robert Bosch GmbH, Stuttgart, Germany. et al. [3] that extends work by Galić et al. [4] and Schmaltz et al. [5] and performs on par with JPEG2000 [6] for images with a small to medium amount of texture. As Jost et al. [7] have shown, these methods can even outperform HEVC/intra on piecewise smooth images. However, inpainting-based video compression is still in its fledgling stages. Most dedicated video codecs are designed as a proof of concept for the reconstruction speed of a particular algorithm and work on a strict frame-by-frame basis [8] , [9] . Others only focus on specific parts of the video coding pipeline without presenting a full codec [10] - [14] .
Inpainting can be a powerful tool in compression. However, corresponding video codecs will only reach their full potential if they consequently exploit temporal redundancies. To tackle this problem, we propose the first modular framework that combines the highly successful idea of prediction and correction with inpainting-based methods. It supports the integration of optic flow and inpainting techniques in several stages of the coding pipeline. Furthermore, we present a hybrid inpaintingbased video codec (HIVC-20) that employs the methods of Brox et al. [15] for optic flow field computation, homogeneous diffusion inpainting [16] for intra prediction, and finite state entropy (FSE) coding [17] . For representing the residuals, we introduce the first block-based variant of pseudodifferential inpainting [18] .
Three of the authors have presented a preliminary framework for PDE-based compression and a proof-of-concept codec (HIVC-16) including inpainting for intra prediction and PDE-based motion estimation in a conference paper [19] . Here, we generalise the framework further to also include other inpainting techniques. In order to show the potential of the framework, our main goal is to design a codec with significantly improved performance both in quality and speed compared to HIVC-16 and other inpainting-based codecs. To this end, we consequently implement inpainting-based methods for all prediction and compression submodules. Through efficient algorithms, we are able to push real-time reconstruction of color videos from a resolution of 854×364 in HIVC-16 to the more than five times higher FullHD 1080p resolution without resorting to parallelization on the GPU.
A core concept in our framework as well as in most established transform-based codecs is hybrid video coding which is based on the principle of prediction via intra/inter frames and correction via residuals. Bull [20] gives a very approachable introduction into important ideas leading up to the current standards H.264/AVC [21] and H.265/HEVC [22] .
Inpainting in image processing was pioneered by Masnou and Morel [23] for the task of disocclusion and has since entered various fields of research. In the context of video compression, inpainting-based techniques have been applied for several parts of the coding pipeline or even for complete codecs. Köstler et al. [8] were the first to achieve real-time performance with a codec based on homogeneous diffusion inpainting on a Playstation 3. The state of the art in PDEbased image compression, the R-EED codec by Schmaltz et al. [5] , has been adapted by Peter et al. [9] for video compression. However, these codecs work on a strict frame-byframe basis. First attempts to incorporate motion information were made by Schmaltz and Weickert [24] who combine pose tracking with static background compression by anisotropic diffusion inpainting. Breuß et al. [14] still perform framebased inpainting, but they acquire masks by shifting one optimised mask along motion vectors. They do not present a full video compression pipeline. Another stand-alone codec is presented by Wu et al. [25] who employ deep learning to interpolate inter frames between two intra frames. Liu et al. [11] , Doshkov et al. [12] , and Zhang and Lin [13] incorporate inpainting ideas directly into the intra prediction of a hybrid video coder. Their methods combine homogeneous diffusion inpainting with edge information, template matching, and adaptive boundary values, respectively. For the same task, Tan et al. [10] perform inpainting via template matching. Jost et al. [7] focus on the compression of dense optic flow fields and design a well-performing method employing edgeaware homogeneous diffusion inpainting. In the field of video completion, which tries to fill in missing regions e.g. for object removal, most papers are only connected to our work via the notion of inpainting. However, El Helou et al. [26] drive their method to the extreme by using a very sparse set of known data (1-2%) and applying the well-known Shepard interpolation [27] , [28] to reconstruct regions in between.
In their survey paper [29] , Sullivan and Wiegand note that the most significant improvements in video coding can be attributed to better motion prediction. It is therefore not surprising that research efforts have been invested into dense optic flow fields. The widely known optic flow method by Horn and Schunck [30] serves as a basis for motion computation in several papers. Moulin et al. [31] and Lin et al. [32] use an adapted version and subsequent compression with a linear model and transform coding, respectively. More recently, Li et al. [33] employ their Horn and Schunck flow fields for bidirectional prediction. More complex techniques such as Bayesian methods in Han and Podilchuk [34] and velocity field modeling in Chen and Mied [35] yield optic flow fields with higher prediction quality. Both methods take also the compressibility of the acquired motion into account. Going even further in this direction, Ottaviano and Kohli [36] represent optic flow in a wavelet basis and obtain the corresponding coefficients by minimising the residual after inter prediction.
We introduce our modular framework in Section II and present a corresponding video codec in the third section. Using this codec, we show experiments in Section IV and conclude our paper in Section V.
In the following, we present a framework that is a suitable foundation for inpainting-based video compression. The general structure is inspired by established codecs relying on prediction and correction. However, we specifically design the submodules to incorporate inpainting-based methods.
Our framework consists of three main modules. The first module incorporates the computation and subsequent compression of dense backwards optic flow fields (BOFFs) between frames. With the acquired motion we can firstly detect scene changes and secondly use it to predict inter frames in the second module. We represent one scene by a group of pictures (GOP), which includes one intra frame at the beginning and subsequent inter frames. In the second module, we predict frames according to their type (intra or inter) and compute a corresponding correction (residual) w.r.t. the originals. Finally, the last module stores and compresses all data needed for decoding. Figure 1 shows the structure of our proposed framework.
We assume that neighboring frames are connected with a BOFF, which represents motion from a frame u k+1 to its preceding frame u k . We employ PDE-based methods for the Optic Flow Computation submodule since they are robust, dense, and can be of high quality. Furthermore, they generate (piecewise) smooth flow fields, which can be compressed strongly without losing important information. The resulting flow fields predict inter frames via motion compensation. Thus, we have to store them in a concise manner in the submodule Optic Flow Compression. To avoid error accumulation, we use the reconstructed BOFFs after compression for inter prediction. Furthermore, we can utilise the flow fields for the submodule Scene Detection, since inconsistent movement indicates a scene cut.
For the submodule Intra Predictions we apply inpaintingbased image compression, since intra frames rely solely on information from within themselves. After predicting the first (intra) frame in a GOP, we perform Inter Prediction on the subsequent frames via motion compensation based on the previously computed compressed BOFFs. Each prediction is accompanied by a corresponding residual which stores the difference to the original frame. In the ideal case, predictions accurately approximate the originals leading to residuals that carry only few information and therefore allow an efficient submodule Residual Compression. Using lossless techniques in this submodule leads to lossless codecs. Combining prediction and compressed residual yields the reconstructed frame that a corresponding decoder can produce. We feed this reconstruction immediately back into the prediction process in order to avoid error accumulation on the decoder side.
For reconstruction, we have to save intra, motion, and residual data in the Storage module. All three types include positional data according to inpainting mask positions and corresponding value data. Intra, motion, and residual values live on different ranges and require dedicated quantization and storage methods. Finally, we remove remaining redundancies within the submodule Entropy Encoding.
Building on our work in the previous section, we now introduce suitable methods for all submodules of our framework to obtain a fully inpainting-based video codec. Since we aim at improving HIVC-16 [19] in both quality and decoding speed, we have to carefully choose methods which are fast and produce accurate approximations.
In a first step, we introduce the decoder design since it dictates requirements for the implementations of the submodules in the encoder. We divide computational load into several CPU threads. Since all predictions in a GOP build upon the initial intra prediction, we aim for high quality at the cost of increased runtime there. Therefore, we assign decoding as well as predicting intra frames an own thread. Decoding in general is always one GOP ahead of reconstruction, thus, the decoding of the remaining data also needs its own thread. We distribute all other tasks such that computational load is about the same. Figure 2 shows the resulting structure.
Given these prerequisites, we can introduce key ingredients for our framework's submodules in Sections III-A -III-F and summarise our final modeling choices in Section III-G.
Energy-based methods for computing optic flow are well understood and can produce (piecewise) smooth and thus well compressible motion fields. Classical algorithms integrate a data term and a smoothness term over the whole frame domain and penalise deviations from the assumptions given within these terms. In regions where information in the data term is not sufficient to generate a unique solution, the smoothness term fills in the optic flow field according to the underlying smoothness assumption. We can interpret this filling-in effect as an inpainting process. In our optic flow computation submodule, we choose the high precision method by Brox et al. [15] . Their data term incorporates the assumptions that brightness as well as gradient values should stay constant along motion trajectories. Moreover, it can handle large displacements. Together with a sub-quadratically penalised smoothness term this method produces accurate piecewise smooth motion fields while still being computationally manageable. Applying their algorithm back to front for all frames in a GOP, we obtain BOFFs for inter prediction that are highly compressible due to their piecewise smoothness but can still yield accurate predictions at motion boundaries. We also tested the much simpler method by Horn and Schunck [30] , but got consistently worse results both in terms of reconstruction error and final compression ratio of the video. Thus, it is worthwhile to invest into more advanced methods to acquire accurate flow fields.
Let f be a 1D representation of a 2D discrete image of size n x × n y , i.e. we sort the image pixels row-wise into the vector f of length N = n x n y . We store values only at a few selected locations represented by the binary inpainting mask m and discard all other values. It is then possible to compute an approximation u of the original image by solving the general discrete inpainting problem
The matrix M contains the entries of the inpainting mask m on its diagonal, and is zero everywhere else. I is the identity matrix and A represents a discrete inpainting operator with reflecting boundary conditions. The first term ensures that u adopts the original values from f at mask positions, the second term realizes inpainting steered by the operator A in regions inbetween. The choice of A influences the reconstruction quality immensely and simultaneously affects the complexity of the algorithms solving the inpainting problem. Choosing A = −L (with discrete Laplacian L) results in homogeneous diffusion inpainting [16] , which presents a good balance between quality and simplicity.
We use a coarse-to-fine algorithm similar to the cascadic conjugate gradient method by Deuflhard [37] to solve the arising system of equations. The basic idea is to build an image pyramid by subsampling, solving the system on a coarse level, and use this solution as input for the next finer level. This yields a much faster convergence (both on the individual levels and in total) compared to classically solving the system once on the finest level.
Pseudodifferential inpainting has been established by Augustin et al. [18] as a connecting concept between inpainting with rotationally invariant PDEs and radial basis function (RBF) interpolation. Their paper extends results of Hoffmann et al. [39] and Plonka et al. [40] on harmonic and biharmonic inpainting with Green's functions. We use their work to build a highly efficient algorithm for inpainting based on the discrete cosine transform, which yields major improvements for the final codec compared to HIVC-16. For images, mask, and operator, we stick to the notation used in Section III-B.
Introducing the theoretical background of Green's functions is beyond the scope of this paper. We refer the interested reader to [39] . Instead, we provide an intuitive interpretation: For a discrete symmetric inpainting operator A, the corresponding discrete Green's function g k characterises the influence of an impulse at pixel position k. Instead of solving a system of equations for the general inpainting problem, we can then directly obtain a solution via a weighted sum of the operator's Green's functions at mask positions:
(m i · c i · (g i ) k ) + a for k = 1, ..., N. (2) Recall that m = (m i ) i=1,...,N is the inpainting mask and u = (u i ) i=1,...,N the corresponding inpainting solution in vector notation. The coefficient vector c and the constant a can be acquired by solving a linear system of equations of size (K + 1) × (K + 1), where K is the number of mask points. An explanation on how to construct this system can be found in [39] . In contrast to the sparse but large matrix used for solving the general inpainting problem directly, the system matrix is fairly small and densely populated.
It is well-known that the discrete Green's functions build up the pseudo-inverse of the corresponding operator (see [40] for details). Therefore, they are symmetric, i.e. (g i ) k = (g k ) i for all i, k, since we assumed A to be symmetric. We define G as the matrix containing the Green's functions g k as its columns. Then we can reformulate Equation (2) as
where vector a has the constant a in every entry. Since our inpainting operator A is a finite difference matrix and the Green's functions are its pseudo-inverse, G is also a difference matrix. Hence, we can apply results by Strang and MacNamara [41] , proving that G is Toeplitz-plus-Hankel. According to Sanchez et al. [42] and Rojo [43] , matrices of this type are diagonalised by the even discrete cosine transform (DCT) of type II. Denoting the corresponding transform matrix by C, we can rewrite Equation (3) as
where the vector λ contains the eigenvalues of the Green's functions. Thus, if we have the coefficients c, we can acquire the final inpainting solution by multiplying the coefficients with the eigenvalues in the transform domain, computing the backtransform, and adding the constant to all pixels. All these considerations hold for arbitrary image sizes. If we now subdivide the image domain into 8 × 8 blocks and perform inpainting on each block independently, we can employ a dedicated fast DCT algorithm. We opt for the method by Arai et al. [44] which is employed by JPEG. Note that if we store the coefficients and the constant on the encoder side, the decoder only has to perform two fast DCTs, n x n y multiplications, and n x n y additions to acquire the final inpainting result. This brings our method close to the main concept of JPEG. However, in contrast to JPEG, our coefficients do not correspond to frequencies, but give a connection to local structures. Moreover, the inpainting operator is now completely defined by the eigenvalues of the Green's functions and can be easily replaced without changing the algorithm or influencing the speed on the decoder side.
Finding a suitable inpainting mask m is a vital task for all inpainting-based compression techniques. Regions in a frame that are hard to reconstruct for the underlying inpainting operator should be equipped with more mask points. Thus, we have to be able to adapt m to local structures and store the positions of the mask points explicitly. We choose a rectangular subdivision of the spatial domain which has been proposed by Schmaltz et al. [5] . The main idea is to split a rectangular image region at its longer side, if its reconstruction error exceeds a certain threshold. We define the rectangles to be overlapping by one pixel and set mask points at all corners and in the middle of each rectangle. In this way, we concentrate mask points in areas with a large approximation error and can store all locations with a simple binary tree. Note that we perform the final inpainting on the complete domain instead of separately on the individual rectangles.
So far, we can compress information in the spatial domain by selecting certain locations to be in the inpainting mask. quantization reduces the amount of data in the co-domain by mapping values into q different bins. For intra predictions, we can use a standard uniform quantization, but values from motion fields, residuals, and coefficients lie in completely different ranges. In a first step, we find symmetric lower and upper bounds for the appearing values and map them to [−127, 127] . For both motion and residual values, it is of high importance to reconstruct zero correctly to avoid flickering. Therefore, we apply uniform dead-zone quantization, which maps values in the interval [−127, 127] uniformly to [ −q/2 , q/2 ]. For a detailed introduction to dead-zone quantisers, we refer the interested reader to Chapter 3 in [6] . 
After dead-zone quantization, we can expect to produce data that have a high probability of being zero or close to zero. Therefore, we adopt an idea from JPEG and define categories which describe larger ranges for exceeding distance of its values from zero. We represent the categories with Huffman codes and store additional bits for the exact value.
In a final step, we apply entropy coding to all acquired data to remove remaining redundancies. The well-known concept of arithmetic coding (AC) by Rissanen [45] and variants thereof are still successfully used in various codecs. However, its problem of requiring costly arithmetic operations has only partly been solved. Asymmetric numeral systems (ANS) by Duda et al. [46] present an interesting alternative.
The core idea of successful entropy coders is to store symbols that appear with a larger probability with a smaller number of bits. Both AC and ANS start with an initial state and each encoded symbol shifts the encoder to a new state. The final state then encodes the complete input. In AC, these states are intervals with a size that adapts to the probability of the encoded symbol. Thus, every state can be described by the lower and upper bound of the current interval. In contrast, ANS uses an adapted description of natural numbers to define states. For simplicity reasons, we stick to a binary system to explain the concept of asymmetry of a numeral system. In this case, the symmetric system is the "normal" even and odd number distribution. The idea behind ANS is to assign a new definition of even and odd asymmetrically according to the symbol probabilities to the set of natural numbers (e.g. {1, 2, 4, 5, 7, 8, ...} are odd and {3, 6, 9, ...} are even). Encoding a bit 0 or 1 then means jumping to the next even or odd number to get to the next state, respectively. In this way, every state in ANS can be described by a single numeral instead of two interval bounds, which results in considerably reduced computational complexity.
Collet makes use of the tabled version tANS in his open source Finite State Entropy (FSE) coder [17] . Our implementation is a lightweight version of FSE specifically designed to fit our video codec structure. It performs on par with AC, but is consistenly faster on the encoder as well as on the decoder side.
Our final model combines methods explained in the previous sections to obtain a fully inpainting-based video codec. Its predecessor HIVC-16 includes homogeneous diffusion inpainting for intra prediction, the method of Brox et al. [15] for inter prediction, quantization for residual compression, and arithmetic coding for entropy coding. It is able to outperform other inpainting-based codecs, however, it has a limited range of possible compression ratios due to the simple residual compression technique and real-time decoding has only been shown for a resolution of 854 × 364. We aim at extending the compression range, improving quality, and increase decoding speed by consequently filling all submodules of the compression pipeline with suitable methods. The human visual system combines structural with color information and is less sensitive to errors in the color domain. Thus, most established codecs transform the input to a color space with a luma and two chroma channels and compress the chroma channels more strongly. Following this sentiment, we convert the frame sequence to YUV space with the reversible color transform (RCT) employed in JPEG2000 and carry out all computations in this domain. In order to realise a stronger compression in the chroma channels, we take half the amount of mask points there compared to the luma channel for all our inpainting methods.
Since we only have to reconstruct one intra frame per GOP, we choose the global homogeneous diffusion inpainting method (Section III-B) for prediction. This results in a lower prediction error at the cost of an increased runtime. We acquire the corresponding inpainting mask with the rectangular subdivision described in Section III-D and quantise color values with a simple uniform quantization.
For flow fields and residuals, we have more severe restrictions regarding runtime, since we have to recover one of each for every reconstructed frame. Experiments showed that typical BOFFs consist of very large regions with barely changing values. Thus, we use the rectangular subdivision scheme from Section III-D and assign the regions their average value. Residuals tend to contain more structure, since both intra and inter prediction work best on smooth regions. Therefore, we opt for block-based pseudodifferential inpainting with the harmonic operator as described in Section III-C. For every 8 × 8 block we again acquire mask positions with rectangular subdivision. The resulting coefficients of the Green's functions in general lie in a larger range than the standard color values and also attain negative values. Therefore, we apply mapping and dead-zone quantization as described in Section III-E. This way, we can ensure that zero-coefficients are reconstructed as zero again.
We store all produced data and use category coding as described in Section III-F for motion and residual data. Finally, we apply FSE coding and concatenate the output to the final compressed video file. 
We perform experiments on a sequence of 32 frames of the Sintel video by Rosendaal [47] with an Intel Xeon CPU W3565@3.20GHz.
In order to provide an insight into how our codec's different modules operate, we show intermediate results of the individual coding steps for an intra frame in Figure 3 , an inter frame in Figure 4 , and residual compression in Figure 5 .
For decoder run-time comparison, we use the 1080p version of Sintel. Figure 6 shows results over resolutions ranging from 480×205 to 1920×818 for our proposed codec HIVC-20, the predecessor HIVC-16, and R-EED [9] . For the R-EED video codec we have to perform all tests on greyscale videos, but still use color videos for HIVC-20 and HIVC-16, giving R-EED a significant advantage. Our new codec outperforms the other methods by roughly one order of magnitude and is the only codec capable of real-time decoding beyond a resolution of 720 × 307.
In Figure 7 , we compare the reconstruction quality of our approach with the best possible inpainting-based video compression method that provides an encoder as well as a decoder. Since the R-EED video codec only works on greyvalue videos, we supplement it by the state-of-the-art color image compression codec R-EED-LP [3] . This is straightforward since the original codec is completely frame-based, however, the resulting codec is significantly slower. Although it is not yet our goal to beat the established codecs of the MPEG family, we provide results for H.262/MPEG-2 [48] as a point of reference. Sintel at a resolution of 960 × 409 serves as test video. We do not include the HIVC-16 codec, since it is only able to compress at small compression ratios up to 35:1. Furthermore, it can only compete with R-EED-LP on highly textured videos. Here, we pick a smooth sequence that is very well suited for R-EED-LP compression, but HIVC-20 is still able to outperform it consistently over several compression ratios.
We presented a modular framework for inpainting-based video compression based on the prediction and correction principle with high flexibility to incorporate various inpainting methods. Furthermore, we implemented a fully inpaintingbased codec, which constitutes an important step towards competitiveness of inpainting-based video compression. We were able to significantly advance a previous version of the codec and outperform the state-of-the-art inpainting-based video codec in both quality and speed. Since our approach remains conceptually simpler than the most advanced transformbased codecs that have been engineered over many years by many researchers, it is natural that its performance cannot be on par yet. We expect that this will change if one gradually includes more and more sophisticated concepts. The modularity of our framework allows an easy incorporation of alternative techniques in its submodules. Furthermore, it is straightforward to add submodules with established concepts such as variable block sizes, bi-directional inter prediction, and deblocking filters. Our pseudodifferential inpainting implementation inherently incorporates a variety of linear operators. It requires further research to state which of these operators work well for compression with possibly adapted quantization techniques for the corresponding coefficients.