2.1.1

Filter Ordering and Block Size Decision

The 2D dependency problem is perhaps the most severe. In our original design, we apply the post-filter in the same order as a traditional adaptive loop filter. We apply the post-filter to each row of pixels that crosses a vertical block edge first (see Figure 1c), followed by each column of pixels that crosses a horizontal block edge (see Figure 1d). This maximizes parallelism (all row filters can be applied in parallel, followed by all column filters) and minimizes the buffering required. The pre-filter is applied in the opposite order. The size of the pre-/post- filter for each edge is the maximum that does not penetrate more than halfway into any neighboring transform block. That is, we use the largest overlap we can apply that will not introduce any additional dependencies on the order the filters are applied, under the constraint that the overlap size is constant for a whole transform block edge. E.g., a 16 × 16 transform block next to an 8 × 8 transform block and two 4 × 4 transform blocks uses a 4-tap filter along the entire shared edge (see Figure 1c). We term this scheme the “full lapping” scheme.

Figure 1:

Example DC basis functions for randomly chosen transform block sizes (a) and an (unrelated) example block size partitioning along with the vertical and horizontal lapping applied to each edge with the full lapping scheme (b-d).

This scheme has two issues. The first is that the filtering order can produce some very strangely shaped basis functions. To demonstrate this, we generated a frame with randomly chosen block sizes and set the DC coefficient in some blocks to a large, positive value. The result can be seen in Figure 1a. Although disconcerting, we never observed visual artifacts in real images with similar patterns, so this problem is mostly theoretical (and one that affects adaptive loop filters, as well).

The second problem is the much more practical issue that we have no idea how to search for the optimal transform block size. In order to compute the rate and distortion required for a traditional rate-distortion (R- D) search, we needed to know what filters were applied along each edge, which requires knowing the size of neighboring transform blocks. It is not even enough to know the size of the lapping on each edge. If a neighbor on the other side of a vertical edge is split, then the pre-filter is applied along the horizontal edge between them before it is applied along the vertical edge in the current block, changing the filter output. That is, in the example of Figure 1b, the pre-filters in Figure 1d are applied before the pre-filters in Figure 1c. Therefore, it is necessary to know which neighboring block is 8 × 8 and which are 4 × 4 to properly determine the output of the pre-filter in the 16 × 16 block. The corresponding dependency graph does not have a tree structure which admits a simple dynamic programming solution.

Our initial solution to this was to use a heuristic to select block sizes up-front, based on a perceptual estimate of the visibility of ringing artifacts. While this seemed to do vaguely reasonable things for intra frames, we did not have a known-optimal algorithm to compare it to, so we could not be certain how far off it really was. We were able to determine it was doing a poor job for inter frames: simply biasing the decision away from 4 × 4 and 8 × 8 blocks for large quantizers reduces the bitrate by more than 5% on all of the metrics we tested*.

2.1.2

Fixed Lapping

In order to permit a true RDO search, we change two things.²³

First, we change the lapping order. Dai et al. propose filtering on 16 × 16 macroblock (MB) boundaries first, followed by interior block edges (using the same order as the full lapping scheme in the interior).²² During block size decision, they use the smallest possible pre-filter on MB boundaries, and then exhaustively search partitions of the interior using the maximum possible overlap on internal block boundaries (as we described above). After block size decision, in a second pass, they filter MB boundaries with the maximum possible overlap for actual encoding, as in our full lapping scheme. In their implementation, MBs can be split down to 4 × 4, producing a total of 17 possible quad-tree subdivisions, which is still tractable to search exhaustively. However, at the time we conducted these experiments, we already supported block sizes up to 32 × 32, which would require searching 83, 522 partitions, and would later extend this to 64 × 64 (more than 48 quintillion partitions).

Instead, we apply what they do on MB boundaries recursively. Starting at the largest block size, what we term a superblock (SB), we pre-filter the exterior SB edges first. If the block is split, then we pre-filter the interior edges, and then recurse into each quadrant. Again, when post-filtering, we reverse the order.

This reduces the amount of potential parallelism, but still allows filtering all SB interiors in parallel, followed by all vertical SB edges in parallel and then all horizontal SB edges. But this change alone already makes our problem simpler. Returning to the example of Figure 1b, we no longer need to know which adjacent blocks are 4 × 4, since the edge between them will always be pre-filtered after the edge they share with the 16 × 16 block. All that remains is the issue of the filter size.

To solve this problem, we make our second change: we make the filter size constant. At first we used 8-point filters until we had split blocks down to 4 × 4, and then used 4-point filters on the final interior edges. However, currently we use 4-point lapping everywhere, as it provides substantial reductions in ringing, at the cost of some blocking artifacts and some detail preservation. We term this the “fixed lapping scheme”, illustrated in Figure 2.

Figure 2:

Example demonstrating the pre-filtering order for the fixed lapping scheme. At each step, the horizontal edges are pre-filtered before the vertical ones, to minimize buffering when applying the post-filter.

With those two changes, it is now possible to compute R-D optimal transform block sizes. After pre-filtering the exterior edges, we try splitting the block and pre-filtering the interior edges. Then we compute the optimal partitioning of each of the four quadrants (recursively), then apply the post-filter to the interior edges. At this point, although we have not post-filtered the exterior edges, it is still possible to do an apples-to-apples comparison of the distortion between the split and no-split cases.

The result is large rate reductions on all metrics: 10.3% and 12.3% on PSNR and SSIM, respectively, and 4.5% and 5.2% on PSNR-HVS and Fast MS-SSIM, respectively, compared to the full lapping scheme^†. For intra frames, the results showed similarly large gains, indicating that even though our heuristic looked “vaguely reasonable” in this case, it was not actually doing a good job. We also experimented with an approach similar to Dai et al.’s, where block size decisions are made using the fixed lapping size, but the actual video is encoded with the full lapping sizes (though still applied in recursive order). When optimizing for PSNR (using flat quantization and no activity masking), this also achieves large gains: a 9.2% reduction in bitrate^‡. This was an encoder-only change, and we verified the bitstreams were decodable by the mainline decoder at the time. This shows that most of the improvements of the fixed-lapping approach simply came from making better decisions than our previous heuristics. However, we opted to keep the fixed lapping size. The gains with the full lapping size are not as large as when using fixed lapping, and it is not obvious how to tune such an encoder, since the actual data that gets encoded can be significantly different than what is used to make decisions.

It might also be possible to explicitly signal the size of the pre-filters to use. The search remains tractable in the interior of a superblock, but some kind of heuristic would be required for the lapping on edges between superblocks, as they retain the original 2D dependency problem. Given that most of the motivation for larger lapping is the reduction in blocking artifacts in large regions that are either smooth or uniformly textured (where the largest transform blocks are used), this is a problem that would need to be solved. This is an area we have not explored.

2.1.3

Lapping vs. Loop Filters

The same recursive filter application order can also be applied to a standard adaptive loop filter. This allows an encoder to consider the effect of the loop filter when making transform block size decisions. We modified Daala to use the adaptive loop filter from the Thor video codec²⁴ in place of lapping through a compile-time option. When enabled, this produces bitrate reductions between 0.4% and 2.6% on video, depending on the metric used^§. However, when used on still images it produces bitrate increases between 2.5% and 3.2% (with the exception PSNR-HVS, where bitrate falls by 0.3%)^¶. The visual impact is more difficult tojudge. We can also get metrics gains on video by disabling lapping completely, despite the obvious blocking and loss of detail preservation that causes. However, we have not attempted to do a formal subjective comparison between lapped transforms and adaptive loop filters, and the results would probably be too close to justify the time and effort. So, although we believe we have made good strides in understanding how to use lapping in a modern video codec, it is not obviously technically superior.

In the context of the Alliance for Open Media, using lapping would require so many structural changes to the codec that it would not be possible to do and still meet our time-to-market goals, so it is not currently being pursued. However, the recursive filter ordering may still provide some benefit in terms of improved encoder decisions and potentially eliminating artifacts along the lines of Figure 1a. This is something we hope to experiment with in the future.

2.2.1

Variable Block Sizes

Extending this to variable block sizes creates even more complications. All of the prediction matrices trained above assume that each block is the same size as its neighbors. In practice, they may be different sizes. Training separate prediction matrices for every potential combination of neighboring block sizes is clearly impractical.

To handle this, we borrow a tool from the Opus audio codec: Time-Frequency (TF) resolution switching.²⁹ The basic idea is to apply a Walsh-Hadamard Transform (WHT) to very cheaply merge multiple blocks of frequency-domain coefficients into a single, larger block with higher frequency resolution, or conversely to split a large block of frequency-domain coefficients into smaller blocks with higher time resolution. The conversion is grossly approximate, but can be “good enough” for some purposes.

Since all of our coefficient blocks are two-dimensional (unlike audio), we can implement a particularly cheap integer version that is a has orthonormal scaling (i.e., is L₂ -norm preserving) and exactly reversible, with just seven additions and one shift. In order to implement the 2 × 2 WHT

we compute

This is significantly cheaper than other approaches described in the literature, such as that of Fukuma et al. (8 additions, 2 shifts, and 1 negation)³⁰ or that used by JPEG XR (10 additions, 1 shift, and 2 negations),³¹ and is, to our knowledge, a novel result.

With this tool in hand, we can handle variable block sizes several ways. For example, for each transform block, we can apply TF merging or splitting until our neighbors are all the same size as the current block, and then use the predictors trained for that size. This is what we implemented first.

However, there is no requirement that our predictors be trained with neighbors that are the same size as the block being predicted. Instead, we can TF all of our neighbors down to 4 × 4, and then train predictors for each block size from the TF’d 4 × 4 data. During training, we transform all blocks at a fixed block size, and then TF the transform coefficients in a block’s neighbors from that size down to 4 × 4. We also tried using the block size heuristic from Section 2.1.1 to choose block sizes, limiting the training for each size to blocks that would be encoded at that size, but this seemed to have little impact. Using TF’d 4 × 4 neighbors has a number of advantages:

The difference between the two approaches on metrics is small. The TF’d 4 × 4 approach gives a tiny gain on PSNR and loses between 0.4% and 1.4% on our other metrics**, but considering its other advantages we thought those losses acceptable.

2.2.2

A Simpler Approach

Although we are able to build a practical codec with lapped transforms and variable block sizes based on the frequency-domain intra prediction scheme described in the previous sections, we cannot say that it truly works well. The promising results of images coded at a fixed 4 × 4 block size disappear when larger block sizes are allowed, and over-fitting and training time, already a problem with 16 × 16 transform blocks, pose a serious challenge for 32 × 32 and above. The prediction does show gains of a few percent on metrics, but not enough to justify the computational complexity of the approach: a sparse matrix multiply with four multiplies per predicted coefficient, multiplied by the number of modes that have to be searched in the encoder, with a large table of trained prediction parameters, and a row buffer of 4 × 4 TF’d coefficient values (four times the size of the equivalent buffer for a spatial predictor). It also has the disturbing tendency to occasionally produce large, erroneous, isolated high-frequency coefficients (likely due to over-fitting in the training), which nevertheless cannot be corrected at low rates, an artifact we term “basis break-out”.

It is not obvious how to improve performance. Better training and more training data could improve the quality of the predictors we obtain, but we tried many different variations of our training methods, and suspect the potential upside here is limited. The approximations in TF are certainly one potential culprit. Although TF itself is orthonormal, our lapped transforms are biorthogonal, and each basis function has a different magnitude, depending on which post-filters are applied. With the full lapping scheme, it is difficult to even compute the magnitudes of the basis functions, as the filter order makes them depend on the size of all of ones neighbors (see Figure 1a). That makes it impractical to correct for the magnitudes of basis functions obtained via TF compared to those obtained with a fixed block size, much less for inaccuracies in the shape of the basis functions. That limits the effectiveness of the predictors we can train. With the fixed lapping scheme, these issues may be worth revisiting, as might the approach of de Oliveira and Pesquet-Popescu.

Instead, we opt to use two much simpler tools. The first, called Haar DC,³² simply applies our 2 × 2 WHT to recursively merge just the DC coefficients from each block up to the superblock level. At the superblock level, DC is predicted using a simple, static linear predictor. This ensures that we retain fine quantization of DC over large regions, since the magnitude of the DC basis function doubles with each application of the WHT, but the

quantizer resolution does not. It also greatly reduces the number of bits spent on DC.

The second simply copies the first row and/or column of AC coefficients from its neighbors, much like MPEG4 Part 2, with the important distinction that we use the copied coefficients as predictors before quantizing the AC coefficients in the current block, not afterwards. This copying is only done when the neighbors use the same transform block size. We experimented with using TF to generate predictors when the transform sizes differed, but this did not produce any appreciable gains.

Since we already partition each block into multiple frequency bands, and signal whether or not to use the prediction in each one (using “noref” flags, see Section 2.4), this approach requires no additional signaling, and no additional searching. For the lowest band, which contains portions of both the first row and the first column of AC coefficients, we only copy the one that has higher energy. On typical images, this prediction only reduces rate by 1 to 2%, but on a synthetically generated image of a large checkerboard, it reduces rate by around 50%. That is, its main utility is to prevent embarrassingly bad performance on trivial images.

Together, these two tools are about as effective as the much more complex frequency-domain intra prediction schemes of the previous sections. In the context of the Alliance for Open Media, frequency-domain intra prediction is mostly unnecessary, since without lapped transforms, spatial intra prediction can be used instead. That means neither Haar DC nor the simple AC coefficient copying are being pursued for integration. However, the pattern predictor illustrated in Figure 4 may have some potential as an additional prediction mode. The difficulty will be justifying the additional line buffers it would require in a hardware implementation.

2.7.1

Non-Binary Coding

We support alphabet sizes up to 16 using 15-bit probabilities. Larger alphabets are easy to support in software, but imposing a limit makes hardware simpler, and also allows SIMD implementations of probability updates. Thus each symbol coded with our non-binary coder can take the place of up to four binary symbols. This effectively gives us a (small) degree of parallelism.

Although we do not yet have a hardware implementation to use for comparisons, we created a small benchmark for testing software entropy coder implementations in isolation^¶. Like VP9, AV1 codes symbols using binary trees, with a binary probability at each node of the tree. This benchmark randomly generates 100, 000, 000 symbols according to the default probability distribution of the tree used for 16 × 16 intra modes. It then converts the tree into a flat 15-bit cumulative distribution for use with our entropy coder and a flat 10-bit cumulative distribution for use with rANS,³⁷ which is also under consideration for inclusion in AV1, and encodes and decodes each symbol with all three methods. The alphabet size is 10 and the average number of binary symbols required to encode a value from this distribution is 2.71, with 51.5% of symbols requiring only a single binary symbol to code. The resulting throughput of the encoder and decoder in each method is given in Table 3.

Table 3:

Encoder and decoder throughput for several entropy coding methods. All numbers are in megabits per second (higher is better).

This shows a significant speed-up for Daala over VP9, and rANS shows an even larger speed-up, particularly for encoding. However, rANS also brings several practical complications, such as the requirement of a 33 kbit lookup table in its current implementation and the requirement that symbols be decoded in the opposite order from which they are encoded. The latter requires buffering all of the symbols for a tile in the encoder, which is expensive for hardware. We do not claim that these software implementations of each method are fully optimized, nor that this single distribution is representative of the entire codec, however we expect this general trend to hold. The exact speed-ups depend a good deal on the average number of binary symbols represented by a single non-binary symbol, where we feel there is significant room for improvement in the design of AV1.

2.7.2

Adaptive Coding

Currently, like VP9, AV1 uses static probabilities for an entire frame. These probabilities are initialized to default values, then automatically updated using the statistics of the previous frame, and optionally overridden by values explicitly coded in the frame header. In its current implementation, the AV1 encoder performs R-D optimization of the entire frame, recording all of its decisions. Then it uses the statistics of these decisions to compute optimal probabilities for that frame, and makes a R-D optimal decision about whether or not to encode an explicit override for each one.

This has several drawbacks for interactive applications. Because such applications have to be robust in the face of packet loss, they cannot use the feed-forward updates of the probabilities using the statistics from prior frames. That means all probability updates must be explicitly coded from the defaults for every frame. This adds bitrate overhead on the order of 5.5%. It also means that the encoder must buffer the symbols to code for an entire frame, and cannot send out a single packet until the whole frame has finished encoding. As with rANS, this buffering is expensive. However, unlike rANS, it is possible to modify the implementation to encode with estimated probabilities rather than optimal probabilities. We have not modified the encoder to do so, but expect it would incur a similarly large overhead.

Instead, we are investigating using adaptive probabilities. Currently, Daala adapts most probabilities using simple frequency counts, periodically rescaling them as the total exceeds 15 bits. Since the total frequency count is generally not a power of two, we adapt the method of Stuiver and Moffat⁴ to coding these values without any multiplications or divisions (except that we over-estimate probabilities for symbols at the beginning of the alphabet, instead of the end). This method is only approximate, but has an overhead of around 1% to 2% compared to the theoretical entropy, which is similar to that of CABAC.

When the total frequency count is a power of two, we use 15 × 16 → 31 multiplies to code symbols with negligible (< 0.01%) overhead. If we can adapt the probability distributions while leaving their total constant, we can avoid the overhead of the non-power-of-two approach. Let f_i be a cumulative distribution of an alphabet of size M with total T, such that 0 < f₀ < f₁ < ... < f_i < ... < f_M-1 = T. Then, if we encode or decode symbol j, we propose updating the distribution f_i with an update rate of 2^r using the following rule:

This rule adjusts values of f_i downward when i < j and upward when j ≤ i, but ensures that the difference between f_i and f_i+1 is always at least 1, and maintains the total, T. So long as the difference is larger than 1, it can continue to adjust the corresponding probability, regardless of the rate, 2^r. While this update rule looks much more expensive than using simple frequency counts, with tables built around the constants M, T, 2^r, i, and j, it can be reduced to two vector additions and a vector shift, which is comparable to a frequency count update and a rescaling operation.

We implemented this adaptation scheme, with some additional rules to speed up the adaptation of the first few symbols coded in each context. Just converting some of the symbols coded in Daala to use this scheme reduced bitrates by 0.3% to 0.4%^‖. Whether or not the complexity of the more expensive update rule is worth the reduction in entropy coder overhead is still an open question.

We think that some of these ideas merit inclusion in AV1, though which exact direction the Alliance ultimately goes depends on exact engineering trade-offs and implementation costs, especially in hardware. We will continue to experiment with these ideas and get more feedback from our partners in the Alliance.

2.8.1

Rate Control Model

Daala controls rate by manipulating the quantization parameter, and thus quantizers, used in encoding. A simple model predicts bit usage for a given frame for any quantizer.

R represents the rate of a frame in bits, Q is the actual linear quantizer (a function of the quantization parameter), and α is a fixed modeling exponent chosen for an entire sequence based on frame type and target rate (in bits-per-pixel). We measure the parameter scale for each frame type during encoding.

2.8.2

Estimating scale

After encoding a frame, we know R and Q, and α is fixed. As a result we can solve the above relationship for scale.

We smooth this measured scale value using a digital approximation of a second order Bessel filter. The filter damps noise and oscillations while preserving reaction speed (see Figure 6), using a time constant that allows full-scale reaction in half the buffer interval. We adjust the reaction time to allow faster adaptation at the beginning of a sequence.

Daala models a separate scale parameter for each frame type and so maintains a Bessel filter for each of keyframes, long-term reference (golden) frames, regular P frames, and B frames.

Figure 6:

(a) Smoothing scale modeling and quantizer choice using an exponential moving average produces unstable/oscillatory behavior detrimental to objective and visual quality. (b) A 2^nd order Bessel filter damps the oscillations while preserving reaction speed. In addition, the Bessel filter’s time constant may be adjusted independent of buffer size to produce any desired reaction speed.

2.8.3

Choosing Q

For every frame, Daala constructs a bit usage plan for the entire remaining buffer interval by predicting the frame type of each subsequent frame and summing the bits used for each of these frames according to our prediction model. The goal of the bit usage plan is to hit a fixed buffer fullness level at the last keyframe in the buffer interval.

Here, N_i is the number of frames of each type, scale_i are the Bessel-smoothed scales corresponding to each frame type, and quantizers Q_i are functions of the quantization parameter. The encoder simply searches quantization parameters until R_total hits the desired bit usage target.

After encoding each frame, we discard the plan and construct a new plan starting from the next frame.

2.8.4

Two-Pass Rate Control

Most modern video encoders offer two-pass rate control which makes a first pass over a video file to collect metrics, and performs encoding in a second pass using knowledge of the complete video content. Daala’s two-pass rate control is a simple modification of the (one-pass, causal) rate control described thus far.

Rather than smoothing scale values for each frame in a Bessel filter, we simply measure and save the scale values during the first pass, and sum these empirical measured values during second pass encoding to use in place of the product N_i · scale_i in equation 9. We also add a fixed offset to correct for consistent over/under estimates. Everything else is just as in one-pass.

2.8.5

Chunked Two-Pass

Video hosting services and sites such as YouTube typically encode files by splitting them into many small chunks of one to five seconds each, and then encoding each chunk independently in parallel to reduce encoding time.

Daala’s rate control model allows the collection of complete file metrics from each chunk in a first pass, allowing the second pass encoding of each chunk to take into account the entire sequence. This produces a chunked two-pass rate control with quality performance similar or identical to a monolithic two-pass encoding.

We plan to investigate integration of this rate control method as an alternative to AV1’s existing rate control. We do not yet know which approach will prove more effective, but conceptually Daala’s is simple and easily adaptable to a broad array of use cases.