daala/doc/intra_paint.lyx

#LyX 2.1 created this file. For more info see http://www.lyx.org/
\lyxformat 474
\begin_document
\begin_header
\textclass article
\begin_preamble
\usepackage{color}
\usepackage{url}
\usepackage[pdfpagemode=None,pdfstartview=FitH,pdfview=FitH,colorlinks=true,pdftitle=Perceptual Vector Quantization for Video Coding,pdfauthor=Jean-Marc Valin]{hyperref}
\end_preamble
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman default
\font_sans default
\font_typewriter default
\font_math auto
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 2cm
\topmargin 2cm
\rightmargin 2cm
\bottommargin 2cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
Intra Paint Deringing Filter
\end_layout

\begin_layout Author
Jean-Marc Valin
\end_layout

\begin_layout Section
Introduction
\end_layout

\begin_layout Standard
Intra paint is a pixel domain technique designed to reconstruct images based
 only on a direction and the pixels that lie on block boundaries.
 Intra paint can be used either for directly encoding images, or as a post-proce
ssing deringing filter to reduce coding artefacts.
\end_layout

\begin_layout Section
Intra Paint Algorithm
\end_layout

\begin_layout Standard
The intra paint algorithm works in four steps:
\end_layout

\begin_layout Subsection*
Step 1: Dividing Into Blocks
\end_layout

\begin_layout Standard
The first step is to divide the image into blocks of fixed or variable size
 (Fig.
\begin_inset space ~
\end_inset


\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Input-image-divided"

\end_inset

).
 Variable-size blocks make it possible to use large blocks on long, continuous
 edges and small blocks where edges intersect or change direction.
 Fixed block size is easier to implement, especially in the deringing applicatio
n where we do not wish to signal the sizes on a block-by-block basis.
 For deringing purposes a block size around 8x8 is generally suitable.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
centering{
\end_layout

\end_inset


\begin_inset Graphics
	filename fruits_block2_luma.jpg
	width 85col%

\end_inset


\begin_inset ERT
status open

\begin_layout Plain Layout

}
\end_layout

\end_inset


\begin_inset Caption Standard

\begin_layout Plain Layout
Input image divided into fixed 32x32 blocks.
\begin_inset CommandInset label
LatexCommand label
name "fig:Input-image-divided"

\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection*
Step 2: Direction Search
\end_layout

\begin_layout Standard
Once the image is divided into blocks, we determine which direction best
 matches the pattern in each block (Fig.
\begin_inset space ~
\end_inset


\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Dominant-direction"

\end_inset

).
 The direction is only signaled when operating as an image encoder.
 One way to determine the direction is to minimize the pixel variance.
 For each direction, we assign a line number to each pixel, as shown in
 Fig.
\begin_inset space ~
\end_inset


\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Lines-for-direction"

\end_inset

.
 
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout

\end_layout

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
centering{
\end_layout

\end_inset


\begin_inset Graphics
	filename dlines.eps
	scale 80

\end_inset


\begin_inset ERT
status open

\begin_layout Plain Layout

}
\end_layout

\end_inset


\begin_inset Caption Standard

\begin_layout Plain Layout
Line numbers for pixels following one direction in an 8x8 block.
\begin_inset CommandInset label
LatexCommand label
name "fig:Lines-for-direction"

\end_inset


\end_layout

\end_inset


\end_layout

\end_inset

For each direction 
\begin_inset Formula $d$
\end_inset

, the variance is defined as:
\begin_inset Formula 
\begin{equation}
\sigma_{d}^{2}=\frac{1}{N}\sum_{k\in\mathrm{block},d}\left[\sum_{p\in P_{d,k}}\left(x_{p}-\mu_{d,k}\right)^{2}\right]\ ,\label{eq:direction-variance0}
\end{equation}

\end_inset

where 
\begin_inset Formula $x_{p}$
\end_inset

 is the value of pixel 
\begin_inset Formula $p$
\end_inset

, 
\begin_inset Formula $P_{d,k}$
\end_inset

 is the set of pixels in line 
\begin_inset Formula $k$
\end_inset

 following direction 
\begin_inset Formula $d$
\end_inset

, 
\begin_inset Formula $N$
\end_inset

 is the total number of pixels in the block, and 
\begin_inset Formula $\mu_{k}$
\end_inset

 is the pixel average for line 
\begin_inset Formula $k$
\end_inset

:
\begin_inset Formula 
\begin{equation}
\mu_{d,k}=\frac{1}{N_{d,k}}\sum_{p\in P_{d,k}}x_{p}\ ,\label{eq:pixel-average}
\end{equation}

\end_inset

where 
\begin_inset Formula $N_{d,k}$
\end_inset

 is the cardinality of 
\begin_inset Formula $P_{d,k}$
\end_inset

.
 Substituting 
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:pixel-average"

\end_inset

 into 
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:direction-variance0"

\end_inset

 and simplifying, we get 
\begin_inset Formula 
\begin{equation}
\sigma_{d}^{2}=\frac{1}{N}\left[\sum_{p\in\mathrm{block}}x_{p}^{2}-\sum_{k\in\mathrm{block},d}\frac{1}{N_{d,k}}\left(\sum_{p\in P_{d,k}}x_{p}\right)^{2}\right]\,,\label{eq:direction-variance1}
\end{equation}

\end_inset

Considering that the first term of Eq.
 
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:direction-variance1"

\end_inset

 is constant with respect to 
\begin_inset Formula $d$
\end_inset

, we simply find the optimal direction 
\begin_inset Formula $d_{opt}$
\end_inset

 as:
\begin_inset Formula 
\begin{equation}
d_{opt}=\max_{d}\sum_{k\in\mathrm{block},d}\frac{1}{N_{d,k}}\left(\sum_{p\in P_{d,k}}x_{p}\right)^{2}\,.\label{eq:direction-variance2}
\end{equation}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
centering{
\end_layout

\end_inset


\begin_inset Graphics
	filename fruits_direction_small.png
	width 85col%

\end_inset


\begin_inset ERT
status open

\begin_layout Plain Layout

}
\end_layout

\end_inset


\begin_inset Caption Standard

\begin_layout Plain Layout
Dominant direction for each block of the image (a dot means no dominant
 direction).
\begin_inset CommandInset label
LatexCommand label
name "fig:Dominant-direction"

\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection*
Step 3: Boundary Pixels
\end_layout

\begin_layout Standard
Determine the pixel values at block boundaries (Fig.
\begin_inset space ~
\end_inset


\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Optimal-pixel-values"

\end_inset

) that optimally match the image using the directions found in step
\begin_inset space ~
\end_inset

2.
 While directly using the pixels that lie on the block boundaries would
 work to some extent, we can generate a better image when also considering
 the pixels within the blocks.
 
\end_layout

\begin_layout Standard
When operating as an encoder, we need to code these pixels, but we can use
 intra prediction from other block boundaries to help save bits.
 This can be done by copying already coded pixels in the same line as the
 pixels being predicted -- in a similar way to existing video codecs, except
 that only boundary pixels are predicted.
 
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
centering{
\end_layout

\end_inset


\begin_inset Graphics
	filename fruits_edges2_luma_small.png
	width 85col%

\end_inset


\begin_inset ERT
status open

\begin_layout Plain Layout

}
\end_layout

\end_inset


\begin_inset Caption Standard

\begin_layout Plain Layout
Optimal pixel values at block boundaries.
\begin_inset CommandInset label
LatexCommand label
name "fig:Optimal-pixel-values"

\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Subsection*
Step 4: Painting
\end_layout

\begin_layout Standard
For each block, use all four boundaries as well as the direction to paint
 the pixels inside the block (Fig.
\begin_inset space ~
\end_inset


\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Reconstructed-painted-image"

\end_inset

).
 The boundary pixels encoded in step
\begin_inset space ~
\end_inset

3 are not taken directly from the original image, but rather optimized to
 give the best prediction of the original image at this stage.
 Block discontinuities are avoided by blending within blocks based on the
 distance to each boundary.
 Each pixel is reconstructed from up to 4
\begin_inset space ~
\end_inset

boundary pixels as
\begin_inset Formula 
\begin{equation}
y_{p}=\sum_{i=1}^{4}w_{p,i,d}\cdot x_{p,i,d}\ ,\label{eq:pixel-painting}
\end{equation}

\end_inset

where 
\begin_inset Formula $x_{p,i,d}$
\end_inset

 are the 4
\begin_inset space ~
\end_inset

boundary pixel values used to predict pixel 
\begin_inset Formula $p$
\end_inset

 for direction 
\begin_inset Formula $d$
\end_inset

 and 
\begin_inset Formula $w_{p,i,d}$
\end_inset

 are the corresponding weights and sum to one.
 The weights are computed in such a way as to interpolate between adjacent
 boundary pixels, while also blending the prediction coming from each end
 of the prediction line.
 An example is provided in Fig.
\begin_inset space ~
\end_inset


\begin_inset CommandInset ref
LatexCommand ref
reference "fig:Interpolation-of-pixel"

\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
centering{
\backslash
scalebox{1.0}{
\backslash
input{interp.pspdftex}}}
\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout
\begin_inset Caption Standard

\begin_layout Plain Layout
Interpolation of pixel (2,4) from pixels (-1,2), (-1,3), (7,6), and (7,7).
 The current block shown in gray.
\begin_inset CommandInset label
LatexCommand label
name "fig:Interpolation-of-pixel"

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Plain Layout

\end_layout

\end_inset


\end_layout

\begin_layout Standard
It turns out that the weights used in 
\begin_inset CommandInset ref
LatexCommand ref
reference "eq:pixel-painting"

\end_inset

 are exactly the same as those we want to use in Step
\begin_inset space ~
\end_inset

3.
 In other words, for each pixel in the block in Step
\begin_inset space ~
\end_inset

3, we use the weights to do the accumulation on the corresponding boundary
 pixels.
 This in turn minimizes the distance between the original and the painted
 image 
\begin_inset Formula 
\begin{equation}
D=\sum_{p}\left(x_{p}-y_{p}\right)^{2}\label{eq:distance}
\end{equation}

\end_inset

over the entire image.
\end_layout

\begin_layout Standard
\begin_inset Float figure
wide false
sideways false
status open

\begin_layout Plain Layout
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
centering{
\end_layout

\end_inset


\begin_inset Graphics
	filename fruits_recons2_luma.jpg
	width 85col%

\end_inset


\begin_inset ERT
status open

\begin_layout Plain Layout

}
\end_layout

\end_inset


\begin_inset Caption Standard

\begin_layout Plain Layout
Reconstructed 
\begin_inset Quotes eld
\end_inset

painted
\begin_inset Quotes erd
\end_inset

 image.
 
\begin_inset CommandInset label
LatexCommand label
name "fig:Reconstructed-painted-image"

\end_inset


\end_layout

\end_inset


\end_layout

\end_inset


\end_layout

\begin_layout Section
Deringing Filter
\end_layout

\begin_layout Standard
Intra paint can be used as a post-processing step to attenuate the coding
 artefacts.
 The idea is that there are regions of the image (e.g.
 close to edges) where the painted version looks better than the coded image,
 especially at low bitrate.
 Of course, it would be bad to replace the entire image with the painted
 version.
 We would only want to do use it in places where it improves quality.
 We also want to avoid spending too many bits on the painting process or
 on signaling which are the pixels that benefit.
\end_layout

\begin_layout Standard
For deringing purposes, instead of running the paint algorithm on the original
 image and sending information about the directions and edges, we can simply
 run the algorithm on the decoded image.
 The second part is trickier.
 How can we know which pixels should be replaced with the painted pixels
 and which ones are best unmodified? Intuitively, we see that in regions
 of the image that have clear directional patterns, the painted image should
 be much closer to the decoded image than in regions with unpredictable
 texture.
 Not only that, but knowing the quality at which the image was coded, we
 have an idea of the amount of quantization noise that was introduced, which
 is also the magnitude of the difference we can expect between decoded image
 and its painted version.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $\mathbf{x}_{k}$
\end_inset

 be the decoded pixels on a line 
\begin_inset Formula $k$
\end_inset

 and 
\begin_inset Formula $\mathbf{y}_{k}$
\end_inset

 be the painted version of the same line, the deringing output is given
 by
\begin_inset Formula 
\begin{equation}
\mathbf{z}_{k}=\left(1-g_{k}\right)\mathbf{x}_{k}+g_{k}\mathbf{y}_{k}\ ,\label{eq:deringing-output}
\end{equation}

\end_inset

where 
\begin_inset Formula $g_{k}$
\end_inset

 is the filter gain.
 The gain that minimizes the expected mean squared error is given by
\begin_inset Formula 
\begin{equation}
g_{k}=\min\left[1,\ \frac{\alpha Q^{2}}{12\sigma_{k}^{2}}\right]\label{eq:deringing-weight}
\end{equation}

\end_inset

where 
\begin_inset Formula $Q$
\end_inset

 is the image quality (quantization step size), 
\begin_inset Formula $\sigma_{k}^{2}=\left\Vert \mathbf{x}_{k}-\mathbf{y}_{k}\right\Vert ^{2}$
\end_inset

 is the mean squared distance between decoded image and the painted image,
 and 
\begin_inset Formula $\alpha$
\end_inset

 is a tunable parameter between 0 and 1.
 Computing a weight along each line of a diven direction provides more control
 than computing the weight at the block level.
 
\end_layout

\begin_layout Standard
Instead of computing 
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:deringing-output"

\end_inset

 and 
\begin_inset CommandInset ref
LatexCommand eqref
reference "eq:deringing-weight"

\end_inset

 separately on each line of each block, we can compute 
\begin_inset Formula $\sigma_{k}^{2}$
\end_inset

 on block boundary pixels in the same way as we computed the pixel averages
 in Step 3.
 This allows us to compute the partial gain 
\begin_inset Formula 
\begin{equation}
g_{k}^{*}=\frac{Q^{2}}{12\sigma_{k}^{2}}\label{eq:partial-gain}
\end{equation}

\end_inset

on each boundary pixel.
 From there, we can treat the 
\begin_inset Formula $g_{k}^{*}$
\end_inset

 values in the same way as pixels and apply the paint algorithm in Step
 4 to fill the 
\begin_inset Formula $g_{k}^{*}$
\end_inset

 values that are inside the blocks.
 This provides us with a continuously-varying gain across the image.
 The final gain then becomes 
\begin_inset Formula 
\begin{equation}
g_{k}=\min\left[1,\ \alpha g_{k}^{*}\right]\label{eq:final_gain}
\end{equation}

\end_inset

where the 
\begin_inset Formula $\alpha$
\end_inset

 parameter is the only information coded for the deringing filter.
 Typically, the encoder selects 
\begin_inset Formula $\alpha$
\end_inset

 by comparing the filter output to the original image and picking the 
\begin_inset Formula $\alpha$
\end_inset

 value that minimizes a certain cost metric (e.g.
 PSNR).
 To reduce the signaling overhead, 
\begin_inset Formula $\alpha$
\end_inset

 is typically signaled over a larger block size than the painting itself.
 For example, good results were obtained when signaling 
\begin_inset Formula $\alpha$
\end_inset

 only on 32x32 superblocks.
 
\end_layout

\begin_layout Subsection
Simplifications
\end_layout

\begin_layout Standard
\begin_inset CommandInset label
LatexCommand label
name "sub:Simplifications"

\end_inset


\end_layout

\begin_layout Standard
In some applications, applying the algorithm as described above may require
 too much CPU time.
 In that case, some simplifications are possible.
 It is possible to reduce complexity by skipping Step 3 of the paint algorithm
 and painting each block independently.
 Although this may increase boundary effects around blocks, it may still
 be acceptable for deringing purposes.
 Alternatively, the painting may be performed on overlapping blocks, which
 would reduce blocking artefacts at the cost of higher complexity.
 
\end_layout

\begin_layout Standard
It is also possible to reduce the complexity of the filter gain computation
 by only computing 
\begin_inset Formula $g$
\end_inset

 on a block-by-block basis.
\end_layout

\begin_layout Section
Implementation
\end_layout

\begin_layout Standard
A deringing filter based on the intra paint algorithm has been implemented
 for the Daala
\begin_inset space ~
\end_inset


\begin_inset CommandInset citation
LatexCommand cite
key "Daala"

\end_inset

 codec.
 It is available from the Daala Git repository
\begin_inset space ~
\end_inset


\begin_inset CommandInset citation
LatexCommand cite
key "Daala-Git"

\end_inset

, in the 
\family typewriter
exp_paint_deringing4
\family default
 branch.
 To maximize the resulting quality, the implementation does not include
 the simplifications described in Section
\begin_inset space ~
\end_inset


\begin_inset CommandInset ref
LatexCommand ref
reference "sub:Simplifications"

\end_inset

.
\end_layout

\begin_layout Section
Conclusion
\end_layout

\begin_layout Standard
We have demonstrated an effective algorithm to remove ringing artefacts
 from coded images and videos.
 While this algorithm does not significantly improve objective quality metrics
 we have been using on Daala (PSNR, PSNR-HVS, SSIM, FAST-SSIM
\begin_inset space ~
\end_inset


\begin_inset CommandInset citation
LatexCommand cite
key "Testing-draft"

\end_inset

), the improvement in subjective quality is significant, mostly on edges.
 See this technilogy demo
\begin_inset space ~
\end_inset


\begin_inset CommandInset citation
LatexCommand cite
key "Paint-demo"

\end_inset

 for more information.
 
\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Daala"

\end_inset

Daala website, Xiph.Org Foundation.
 
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
url{http://xiph.org/daala/}
\end_layout

\end_inset


\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Daala-Git"

\end_inset

Daala Git repository.
 
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
url{http://git.xiph.org/?p=daala.git;a=summary}
\end_layout

\end_inset


\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Testing-draft"

\end_inset

T.
 Daede, J.
 Moffitt, 
\emph on
Video Codec Testing and Quality Measurement
\emph default
, IETF Internet draft, 2015.
 
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
url{https://tools.ietf.org/html/draft-daede-netvc-testing}
\end_layout

\end_inset


\end_layout

\begin_layout Bibliography
\begin_inset CommandInset bibitem
LatexCommand bibitem
key "Paint-demo"

\end_inset


J.-M.
 Valin, 
\emph on
Daala: Painting Images for Fun (and Profit?)
\emph default
.
 
\lang english

\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
url{http://people.xiph.org/~jm/daala/paint_demo/}
\end_layout

\end_inset


\end_layout

\end_body
\end_document