[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01

Network Working Group                                          JM. Valin
Internet-Draft                                                   Mozilla
Intended status: Standards Track                            July 6, 2015
Expires: January 7, 2016


        Screencasting Considerations and L1-Tree Wavelet Coding
                       draft-valin-netvc-l1tw-01

Abstract

   This document proposes a screencasting encoding mode based on the
   Haar wavelet transform and L1-tree wavelet (L1TW) coding.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on January 7, 2016.

Copyright Notice

   Copyright (c) 2015 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

   This document may not be modified, and derivative works of it may not
   be created, and it may not be published except as an Internet-Draft.



Valin                    Expires January 7, 2016                [Page 1]


Internet-Draft           Screencasting and L1TW                July 2015


Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  The Haar Wavelet  . . . . . . . . . . . . . . . . . . . . . .   3
   3.  L1-Tree Coding  . . . . . . . . . . . . . . . . . . . . . . .   3
   4.  Results . . . . . . . . . . . . . . . . . . . . . . . . . . .   4
   5.  Objective Evaluation  . . . . . . . . . . . . . . . . . . . .   4
   6.  Development Repository  . . . . . . . . . . . . . . . . . . .   5
   7.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   5
   8.  Security Considerations . . . . . . . . . . . . . . . . . . .   5
   9.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   5
   10. Informative References  . . . . . . . . . . . . . . . . . . .   5
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .   5

1.  Introduction

   Screensharing is an important application for an Internet video
   codec.  Screensharing content differs from photographic images in
   many ways, including:

   o  Text: screenshots often contain anti-aliased text on a perfectly
      flat background.  This makes ringing artefacts highly perceptible.
      Also, typical photographic codecs based on the discrete cosine
      transform (DCT) cannot take advantage of the fact that the
      background often has a constant colour.

   o  Lines and edges.  Screenshots often contain perfectly straight
      horizontal and/or vertical lines.  They appear in window frames,
      toolbars, widgets, spreadsheets, etc.  DCT-based codecs can
      represent those lines and edges, but not as compactly as codecs
      like PNG.

   o  Reduced number of colours: Screenshots are much less "noisy" than
      photographic images.  It is common for a certain region of an
      image to only contain a handful of different colours, another
      property we would like to exploit in a video codec.

   o  A very common motion pattern in screensharing content is the
      displacement of windows.  This typically involves rectangular
      boundaries.

   The technique described in this document only deals with still images
   for now and focuses on the problem of efficiently coding anti-aliased
   text.  While it is implemented for the Daala [Daala-website] codec,
   it should be applicable to most other video codecs.






Valin                    Expires January 7, 2016                [Page 2]


Internet-Draft           Screencasting and L1TW                July 2015


2.  The Haar Wavelet

   The Haar wavelet <https://en.wikipedia.org/wiki/Haar_wavelet> is the
   simplest of all orthogonal wavelets, and also the only one with
   linear phase.  We use the Haar transform both because it is spatially
   compact and because it makes it easy to switch between a wavelet
   transform and the DCT.

   In 1-D, a single level of the Haar transform is expressed as:

                                  ___
                      [ y0 ]     / 1  [  1 1 ] [ x0 ]
                      [    ] =  / --- [      ] [    ]
                      [ y1 ]   v   2  [ -1 1 ] [ x1 ]

   The 2-D Haar transform is implemented from a 2x2 lifting Haar kernel:

                          inputs: x0, x1, x2, x3
                          x0 <= x0 + x2
                          x3 <= x3 - x1
                          tmp <= (x0 - x3) >> 1
                          x1 <= tmp - x1
                          x2 <= tmp - x2
                          x0 <= x0 - x1
                          x3 <= x3 + x2
                          outputs: x0, x1, x2, x3

   This kernel has perfect reconstruction, making it also useful for
   lossless compression.

   The kernel above is applied on 5 levels for 32x32 superblocks.  The
   resulting wavelet coefficients are quantized non-uniformly using the
   following quantization scales relative to the DC quantizer (from low
   frequency to high frequency):

              horizontal/vertical: [1.0, 1.0, 1.0, 1.5, 2.0]
              diagonal:            [1.0, 1.0, 1.5, 2.0, 3.0]

3.  L1-Tree Coding

   Like other wavelet coding methods such as EZW and SPIHT, we code the
   wavelet coefficients using trees.  The main difference however is
   that rather than being based on the maximum coefficient value in a
   tree, this technique is based on the sum of the absolute values of
   all coefficients in the tree.  Let x(i,j) denote the quantized
   wavelet coefficient at position (i,j), the children of x(i,j) are
   x(2*i,2*j), x(2*i,2*j+1), x(2*i+1,2*j), and x(2*i+1,2*j+1).  The
   absolute sum of the tree rooted in (i,j) is defined recursively as:



Valin                    Expires January 7, 2016                [Page 3]


Internet-Draft           Screencasting and L1TW                July 2015


               S(i,j) = |x(i,j)| + S(2*i,2*j) + S(2*i,2*j+1)
                      + S(2*i+1,2*j) + S(2*i+1,2*j+1),

   with S(i,j)=0 for i or j >= N.  C(i,j) is defined as S(i,j)
   - |x(i,j)|.

   Coefficient coding starts at the root of each of the three "direction
   trees": (1,0), (0,1), and (1,1).  At each level we code the value
   of |x(i,j)| using a cumulative density function adapted based on the
   value of S(i,j).  Coding |x(i,j)| implies that the value of C(i,j) is
   known to the decoder, so it does not need to be coded.  Three symbols
   are then required to encode each of the new roots: S(2*i,2*j),
   S(2*i,2*j+1), S(2*i+1,2*j), and S(2*i+1,2*j+1).

   At the top level, we have S(0,0) = S(1,0) + S(0,1) + S(1,1), so that
   completely flat blocks can be coded with a single S(0,0)=0 symbol.
   The DC is coded separately.

4.  Results

   The coded images obtained with the Haar transform and L1TW have far
   better subjective visual quality than those obtained with the lapped
   DCT or with JPEG, and of comparable quality to those obtained with
   x264 <http://www.videolan.org/developers/x264.html> and x265
   <http://x265.org/>.  An example image at around 0.35 bit/pixel is
   provided at <http://jmvalin.ca/video/haar_example/>.  The x264 image
   encoded with options "--preset placebo --crf=27" and the x265 image
   is encoded with "--preset slow --crf=29".

   While the technique presented here works relatively well on the
   example above, there are still cases where it performs significantly
   worse than x265.  These include gradients, such as those in toolbars
   and window titlebars, and long horizontal and vertical lines such as
   those found in spreadsheets.  These cases should improve once we
   implement the ability to dynamically switch between the lapped DCT
   and the Haar transform.  Other ways of improving performance on long
   lines and edges would be to extend to use a different 2D wavelet
   decomposition, or use an overcomplete basis.

5.  Objective Evaluation

   As a first step for evaluating screensharing quality, we have added a
   small collection of screenshot images to the "Are We Compressed Yet?"
   (AWCY) <https://arewecompressedyet.com/> website, under the
   "screenshots" set name.  AWCY currently runs four quality metrics:
   PSNR, PSNR-HVS, SSIM, and FAST-SSIM [I-D.daede-netvc-testing].  It is
   not yet clear that and of these metrics is suitable for evaluating
   the quality of screensharing material.



Valin                    Expires January 7, 2016                [Page 4]


Internet-Draft           Screencasting and L1TW                July 2015


6.  Development Repository

   The algorithms in this proposal are being developed as part of
   Xiph.Org's Daala project.  The code is available in the Daala git
   repository at <https://git.xiph.org/daala.git>.  See [Daala-website]
   for more information.

7.  IANA Considerations

   This document makes no request of IANA.

8.  Security Considerations

   This draft has no security considerations.

9.  Acknowledgements

   Thanks to Timothy B.  Terriberry for useful feedback and for
   designing the 2-D Haar lifting kernel.

10.  Informative References

   [Daala-website]
              "Daala website", Xiph.Org Foundation , <https://xiph.org/
              daala/>.

   [I-D.daede-netvc-testing]
              Daede, T. and J. Jack, "Video Codec Testing and Quality
              Measurement", draft-daede-netvc-testing-00 (work in
              progress), March 2015.

Author's Address

   Jean-Marc Valin
   Mozilla
   331 E. Evelyn Avenue
   Mountain View, CA  94041
   USA

   Email: jmvalin@jmvalin.ca











Valin                    Expires January 7, 2016                [Page 5]


Html markup produced by rfcmarkup 1.122, available from https://tools.ietf.org/tools/rfcmarkup/