Using Daala Intra Frames for Still Picture Coding
Nathan E. Egge, Jean-Marc Valin, Timothy B. Terriberry, Thomas Daede, Christopher Montgomery
MozillaMountain View, CA, USA

Abstract—Recent advances in video codec technology havebeen successfully applied to the field of still picture coding. Daalais a new royalty-free video codec under active development that
contains several novel coding technologies. We consider using
Daala intra frames for still picture coding and show that it iscompetitive with other video-derived image formats. A finishedversion of Daala could be used to create an excellent, royalty-free
image format.

techniques. Unsignaled horizontal and vertical prediction (seeSection II-D), and low complexity prediction of chroma coefficients from their spatially coincident luma coefficients (seeSection II-E) are two examples.

I. I NTRODUCTION
The Daala video codec is a joint research effort between
Xiph.Org and Mozilla to develop a next-generation video
codec that is both (1) competitive performance with the stateof-the-art and (2) distributable on a royalty free basis. In working to produce a royalty free video codec, Daala introduces
new coding techniques to replace those used in the traditional
block-based video codec pipeline. These techniques, while notcompletely finished, already demonstrate that it is possible todeliver a video codec that meets these goals.
All video codecs have, in some form, the ability to codea still frame without prior information. As the bitstreams
of other video codecs have stabilized, new standards in still
picture coding have been proposed most notably with WebP
based on VP8 [1] and BPG based on H.265 [2].
This paper outlines the techniques used in Daala to code justthese still-image ’intra’ frames. It includes a brief experimental
study comparing still image performance against other lossy
still picture codecs, e.g., JPEG, WebP, and BPG, using two
quality metrics: PSNR and Fast MS-SSIM[3]. In the future
work section we describe what features are missing from Daalathat would be required by an effort to standardize Daala intra
frames as a stand alone still picture format.

Fig. 1. State of blocks within the decode pipeline of a codec using lapped
transforms. Immediate neighbors of the target block (bold lines) cannot be
used for spatial prediction as they still require post-filtering (dotted lines).

Transform

Prediction

Quantization

Encoding

Super
Block

Haar +
ScalarLaplacianPVQ

k-Tokenizer

DC

LT

DCT

Luma

HV

AC
Chroma CfL

Fig. 2.

High-level block diagram of Daala encode pipeline.

II. C ODING T ECHNIQUES
Coding of intra frames in Daala is similar to other blockbased image codecs. An input image is broken into super
blocks of 32x32 pixels which are processed left-to-right, topto-bottom. Based on content, each super block can be split into
quadrants down to blocks as small as 4x4 pixels. Each block
goes through familiar stages: transform, prediction, quantization, and coefficient coding. However, many traditional
picture coding approaches are inapplicable to Daala, and newtechniques need to be invented.
For example, Daala’s use of an invertible lapped transform(see Section II-A) means that spatial information from neighboring blocks is not available for use in block prediction,
as shown in Figure 1. On the other hand, use of gain-shapequantization (see Section II-B) allows for new intra-prediction

A. Time-Domain Lapped Transforms
Lapped transforms were proposed for video coding as early
as 1989 [4]. Like the loop filters more commonly found inrecent video coding standards, Time-Domain Lapped Transforms (TDLTs) use a post-processing filter that runs between
block edges to reduce or eliminate blocking artifacts. Unlike aloop filter, the TDLT filter is invertible, allowing the encoder
to run the inverse filter on the input video [5].
The Time-Domain Lapped Transform can be viewed as aset of pre- and post- filters to an existing block-based DCTtransform.

Subset 1 γc
KLT
DCT
CDF(9/7)
LappedKLT
LappedDCT

4x4
12.47dB
12.42dB
13.14dB
13.35dB
13.33dB

8x8
13.62dB
13.55dB
13.82dB
14.13dB
14.12dB

16x16
14.12dB
14.05dB
14.01dB
14.40dB
14.40dB

Fig. 4.
Coding gain figures for several 2-D transforms collected over
Xiph.Org’s standard image coding test subset 1.

Fig. 5. Bands used for PVQ. 32x32 and larger blocks follow a similar pattern.

CB, the reconstructed gain ĝ and shape û can be found by
Fig. 3. Illustration of time-domain lapped transforms consisting of the DCT
with pre-filters P and post-filters P−1 straddling block boundaries.

ĝ = γg · Q(1)û = CB[γu ](2)and reconstructed coefficients x̂ are thus
The pre-filter P operates in the time domain, processing
block boundaries and removing inter-block correlation. The
blocks are then transformed by the DCT into the frequency
domain, where the resulting coefficients are quantized andencoded. When decoding, the inverse operator P−1 is applied
as a post-filter to the output of the inverse DCT. This has two
benefits:
1) Quantization errors are spread over adjacent blocks via
the post-filter P−1 , reducing blocking artifacts without
the need for a separate deblocking filter.
2) The increased support region of the transform allows it
to take advantage of inter-block correlation to achieve ahigher coding gain than a non-overlapped DCT. This
allows it to more effectively code both smooth andtextured regions (see Figure 4.)
Daala implements the TDLT as a reversible lifting filter
with perfect reconstruction, allowing lossy or fully lossless
operation at up to 12-bits of input depth [6].
B. Gain-Shape Quantization
The Daala video codec uses gain-shape quantization, a formof vector quantization in which the vector of coefficients
x is separated into two intuitive components: a magnitude(gain) and its direction (shape). The gain g = kxk represents
how much energy is contained in the block, and the shapeu = x/ kxk indicates where that energy is distributed among
the coefficients. The gain is then quantized using scalar quantization, while the shape is quantized by finding the nearest
VQ-codeword in an algebraically defined codebook. The codec
does not explicitly store the VQ-codebook and the encoderneed search only a small set of VQ-codewords around the
input vector.
Given the gain quantization index γg , the shape vector
quantization index γu and an implicitly defined VQ-codebookx̂ = ĝ · û(3)

Each block is subdivided into bands, as shown in Figure
5. Each band is separately coded with a gain and shape. By
explicitly signaling the amount of energy in a block, androughly where that energy is located, gain-shape quantization
is texture preserving.
The algebraic codebook used in Daala is based on the
pyramid vector quantizer described by Fisher [7]; we refer
to our extended technique as Perceptual Vector Quantization(PVQ). A complete description of PVQ usage in Daala and its
other advantages over scalar quantization is outside the scopeof this paper and is described in detail by Valin [8].
C. Prediction with PVQ
In block based codecs, intra prediction can often construct
a very good predictor for the block that will be decoded next.
In the encoder, this predicted block is typically subtracted
from the input image and the residual is transformed to thefrequency domain, quantized and entropy coded. When thetransform is linear, as is the case with codecs based on lapped
transforms, this is equivalent to transforming the predictor andcomputing the difference in the frequency domain. However,
if one were to simply quantize the frequency domain residual
using PVQ, the texture preservation property described in theprevious section would be lost; the energy is no longer thatof the block being coded, but rather the difference from its
predictor. In Daala, this is avoided by explicitly not computing
a residual, but instead extracting another intuitive parameterin gain-shape quantization.
We can reduce the entropy of the symbols we code andretain the energy preserving properties of PVQ by using a
Householder reflection. Considering the predictor as anothern-dimensional vector, a reflection plane is computed that

of our prediction vector r and s = sgn(rm ). Thus the largest
component lies on the m-axis after reflection. When thepredictor is good, we expect that the largest component ofz will also be in the em direction and θ will be small. If we
code θ̂ using scalar quantization, we can remove the largest
dimension of z and reduce the coding of x to a gain-shapequantization of the remaining n − 1 coefficients where thegain has been reduced to sin θ · g. Given a predictor r, thereconstructed coefficients x̂ are computed asx̂ = ĝ − s · cos θ̂ · em + sin θ̂ · û(7)(a)

When the predictor is poor, θ will be large and the reflection isunlikely to make things easier to code. Thus when θ is greaterthan 90◦ we code a flag and use PVQ with no predictor.
Conversely when r is exact, θ̂ is zero and no additional
information needs to be coded. In addition, because we expect
r to have roughly the same amount of energy as x, we canget additional compression performance by using krk as apredictor for g:ĝ = γg · Q + krk(8)

D. Horizontal & Vertical Intra Prediction(b)Fig. 6.
(a) A Householder reflection plane is computed that aligns theprediction vector so that its largest component is along an axis. (b) The input
vector is reflected across the plane and the angle θ is computed and codedusing scalar quantization. The axis on which the predictor lies is eliminated,
the remaining n − 1 dimensions are coded using PVQ.

aligns the predictor with one of the axes in our n-dimensional
vector space making all but one of the components in thepredictor equal zero. The encoder can then reflect the input
vector x across this reflection plane in a way that is perfectly
reproducible in the decoder, see Figure 6.
Let r be the n-dimensional vector of predictor coefficients.
Then the normal to the reflection plane can be computed asrv=+ s · em(4)krk
where s · em is the signed unit vector in the direction of theaxis we would like to reflect r onto. The input vector x canthen be reflected across this plane by computing
vT x
v
(5)
vT v
We can measure how well the predictor r matches our input
vector x by computing the cosine of the angle θ between them
as
xT r
zT r
zm
cos θ === −s(6)
kxk krkkzk krkkzk
z=x−2

We are free to choose any axis in our n-dimensional space
and we select em to be the dimension of the largest component

Traditional directional intra prediction, as seen in video
codecs like H.264, is not usable for lapped transform based
codecs. The final spatial reconstruction of the neighboring
blocks, necessary for prediction, is not available until after
prediction and decode, as shown in Figure 1. However, thecomplete frequency-domain coefficients are available.
A simple horizontal and vertical predictor is implemented
by copying the first row of coefficients of the horizontal bands
from the block above, and the first column of horizontal
coefficients from the block to the left (see Figure 5 for the bandlayout). No signaling is done at this step - rather, PVQ cansignal on a per-band basis whether to use a band’s prediction
or not. This is more flexible as well, as there are multiple
horizontal and vertical bands on larger blocks.
The first band is nondirectional and a special case - whether
to copy from the top or left is decided based on which has agreater variance in the row or column to be copied.
E. Chroma from Luma Prediction
In spatial-domain chroma-from-luma [9], the key observation is that the local correlation between luminance andchrominance can be exploited using a linear prediction model.
For the target block, the chroma values can be estimated fromthe reconstructed luma values asC(u, v) = α · L(u, v) + β(9)where the model parameters α and β are computed as a linear
least-squares regression using N pairs of spatially coincident
luma and chroma pixels.
When α and β are sent explicitly in the bitstream, the pairs
are taken from the original, unmodified image. However, thedecoder can also compute the same linear regression using its
previously decoded neighbors and thus α and β can be derived
implicitly from the bitstream.

In codecs that use lapped transforms, the reconstructed pixel
data is not available. However the transform coefficients inthe lapped frequency domain are the product of two linear
transforms: the linear pre-filter followed by the linear forward
DCT. Thus the same assumption of a linear correlation between luma and chroma coefficients holds. In addition, we cantake advantage of the fact that we are in the frequency domain
to use only a small subset of coefficients when computing ourmodel.
The chroma values can then be estimated using frequencydomain chroma-from-luma (FD-CfL) [10]:CDC = αDC · LDC + βDC
CAC (u, v) = αAC · LAC (u, v)

(10)
(11)

where the αDC and βDC are computed using a linear regression with the DC coefficients of the three neighboring blocks:
up, left and up-left. When estimating CAC (u, v) we can omit
the constant offset βAC as we expect the AC coefficientsto be zero mean. Additionally, we do not include all of the
AC coefficients from the same three neighboring blocks when
computing αAC .
Consider what happens when the frequency-domain
chroma-from-luma (FD-CfL) algorithm it is used with gainshape quantization. As an example, consider a 4x4 chroma
block where the 15 AC coefficients are coded using gain-shapequantization with the FD-CfL predictor from Equation 11. The
15-dimensional predictor r is simply a linearly scaled vectorof the coincident reconstructed luma coefficients:
CAC (u, v) = αAC · LAC (u, v) =⇒ r = αAC · x̂L(12)Thus the shape of the chroma predictor r is exactly that of thereconstructed luma coefficients x̂L with one exception:
αAC · x̂Lx̂Lr=
= sgn(αAC )(13)krkkαAC · x̂L k
kx̂L kBecause the chroma coefficients are sometimes inversely correlated with the coincident luma coefficients, the linear term
αAC can be negative. In these instances the shape of x̂L points
in exactly the wrong direction and must be flipped.
Moreover, consider what happens to the gain of xC when
it is predicted from r. The PVQ prediction technique assumes
that krk = αAC · kx̂L k is a good predictor of gC = kxC k.
Because αAC for a block is learned from its previously
decoded neighbors, often it is based on highly quantized oreven zeroed coefficients. When this happens, αAC · kx̂L k
is no longer a good predictor of gC and the cost to codekxC k−αAC ·kx̂L k using scalar quantization is actually greaterthan the cost of just coding gC alone.
Thus we present a modified version of PVQ prediction in
Section II-C that is used just for chroma-from-luma intra prediction called PVQ-CfL. For each set of chroma coefficientscoded by PVQ, the prediction vector r is exactly the coincident
luma coefficients. We determine if we need to flip the predictor
by computing the sign of the cosine of the angle between x̂Land xC :f = sgn(x̂TL xC )(14)

A negative sign means the angle between the two is greaterthan 90◦ and flipping x̂L is guaranteed to make the angle lessthan 90◦ .
We then code f using a single bit3 , and the gain ĝC using
scalar quantization with no predictor. The shape quantization
algorithm for xC is unchanged except that r = f · x̂L . Thisalgorithm has the advantage over FD-CfL of being both lower
complexity (neither the encoder nor decoder need to compute alinear regression per block) and providing better compression(the chroma gain gC is never incorrectly predicted).
F. Paint Deringing Filter
The paint deringing filter is a post-processing step to attenuate ringing artifacts. The idea is to turn the reconstructed
image into a painting, that is an image where pixels in eachblock follow a single direction. In regions where the original
image is also directional, such as edges, the painted image
looks better than the coded image, especially at low bitrate.
By using the painted image only in regions where it improves
quality, we can reduce the amount of ringing without causing
additional artifacts.
The painting algorithm works in three steps:
1) Direction search: Determine which direction best
matches the pattern in each 8x8 block of the quantizedimage. The direction does not need to be signaled since
the decoder also computes it on the quantized image.
2) Boundary pixels: Determine the pixel values at blockboundaries that optimally match the image using the directions found in step 1. Again, no signaling is required.
3) Painting: For each block, use all four boundaries aswell as the direction to paint the pixels inside the block.
The boundary pixels computed in step 2 are used. Blockdiscontinuities are avoided by blending within blocks
based on the distance to each boundary.
Chosing which pixels should be replaced with the painted
pixels and which ones are best unmodified is done using again derived from a Wiener filter. Intuitively, we see that inregions of the image that have clear directional patterns, thepainted image should be much closer to the decoded image
than in regions with unpredictable texture. Also, knowing thequality at which the image was coded, we can estimate theamount of quantization noise that was introduced, which isalso the magnitude of the difference we can expect between
decoded image and its painted version. The choice is madeusing the following equation for the optimal weight to apply
to the painted image:
Q2
w = min 1, α
12σ 2
where Q is the quantization step size, σ 2 is the meansquared distance between decoded image and the painted
3 It is not strictly necessary to code a bit for f . Instead the parameter αACcould be found using least-squares regression and the sign extracted. However,using a single bit to code f is (1) better overall than relying on least-squares
regression which can be wrong and (2) reduces the complexity significantly.

22
20
18

Quality (dB)

16
14
12
10
8

(a)
Fig. 7.

(b)daala-v0.0.960-g13612d0 (FastSSIM)
libbpg-0.9.5 (FastSSIM)
libwebp-0.4.3 (FastSSIM)
libjpeg-turbo-1.2.1 (FastSSIM)

6

Daala luma plane (a) before and (b) after applying paint deringing.

4
0

0.2

0.4

0.6

0.8

1

Rate (bits/pixel)

image, and α is a tunable parameter between 0 and 1. For
each boundary pixel, we compute a weight along the directionof each adjacent block. This gives us more control thancomputing the weight at the block level. There are still cases
where we might be wrong and where our deringing would hurt
image quality by blurring texture. Because of this, there is anadditional per-superblock gain α transmitted to the decoder. It
is the only information transmitted for the deringing filter.
III. E XPERIMENTAL E VALUATION
To compare the Daala intra frame coding to other still image
formats a small experimental study was conducted using the 8
mandatory images provided as part of the Image Compression
Evaluation feature session at PCS 2015 [11]. The original 2
mega-pixel 8-bit RGB images were converted to 8-bit YUV
and downsampled to 4:2:0. The resulting images were fed
through Daala and 3 other lossy image codecs at a wide varietyof quality factors. A graph of the rate-distortion curves forluma PSNR and luma Fast MS-SSIM can be found in Figures
8 and 9 respectively.
40

Rate-distortion comparison using luma Fast MS-SSIM.

support for color encoding schemes and metadata. The Daalaroadmap [13] includes adding support for 4:2:2 subsampling,
monochrome (luminance only) input, alpha plane support andfor lossless RGB using YCgCo.
Other highly requested features would require more fundamental changes to Daala. The lapped transforms only allow
up to 12-bit input per channel and a separate design would beneeded for higher bit-depth images. There is no support for
depth channels, no support for high dynamic range content,
no way to specify a region of interest for rate allocation, andno spatial scalability.
Daala is intended for use in real-time and streaming video
applications and some design choices, e.g., memory footprint,
encoder/decoder performance, etc. are not optimal for single
frame encoding. However, many of these requirements canbe relaxed for still image coding, which could yield better
efficiency at the cost of speed.
R EFERENCES

38
36
34
Quality (dB)

Fig. 9.

32
30
28
26
daala-v0.0.960-g13612d0 (PSNR)
libbpg-0.9.5 (PSNR)
libwebp-0.4.3 (PSNR)
libjpeg-turbo-1.2.1 (PSNR)

24
22
20
0

0.2

0.4

0.6

0.8

1

Rate (bits/pixel)

Fig. 8.

Rate-Distortion comparison using luma PSNR.

IV. F UTURE W ORK
The Daala video codec is under active development [12] andthere are clearly features missing that are needed to produce acompetitive still picture format. Most obviously is the lack of[1] “WebP website,” https://developers.google.com/speed/webp/.
[2] “BPG website,” http://bellard.org/bpg/.
[3] M.-J. Chen and A. C. Bovik, “Fast structural similarity index algorithm,”in Proc. ICASSP, march 2010, pp. 994–997.
[4] H. S. Malvar and D. H. Staelin, “The LOT: Transform coding without
blocking effects.” IEEE Trans. Acoustics, Speech, and Signal Processing,vol. 37, no. 4, pp. 553–559, 1989.
[5] T. D. Tran, J. Liang, and C. Tu, “Lapped transform via time-domain preand post-filtering,” IEEE Transactions on Signal Processing, vol. 51,
no. 6, pp. 1557–1571, 2003.
[6] “Timedomainlappedtransforms
for
video
coding,”https://tools.ietf.org/html/draft-egge-videocodec-tdlt.
[7] T. R. Fischer, “A pyramid vector quantizer,” IEEE Trans. on Information
Theory, vol. 32, pp. 568–583, 1986.
[8] J.-M. Valin and T. B. Terriberry, “Perceptual vector quantization forvideo coding,” vol. 9410, 2015.
[9] J. Kim, S. Park, Y. Choi, Y. Jeon, and B. Jeon, “New intra chroma
prediction using inter-channel correlation,” no. JCTVC-B021. Geneva,
Switzerland, 2nd meeting: Joint Collaborative Team on Video Coding(JCT-VC) of ITU-T VCEG and ISO/IEC MPEG, July 2010.
[10] N. E. Egge and J.-M. Valin, “Predicting chroma from luma withfrequency domain intra prediction,” vol. 9410, 2015, pp. 941 008–
941 008–10.
[11] “Picture Coding Symposium (2015) website,” http://www.pcs2015.org/.
[12] “Daala git repository,” https://git.xiph.org/daala.git.
[13] “Daala roadmap,” https://wiki.xiph.org/DaalaRoadmap.