<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Hi Aaron,<br>
<br>
Indeed the statistical modeling + entropy coding part of
compressor is a crucial part of the success. <br>
CABAC went in good direction, but still brings the burden of being
designed on previous CAVLC binarization and lack of inexpensive
accurate multi-symbol entropy coders back then.<br>
Now we can finally do this part in practically optimal way,
especially that rANS has has significantly reduced the cost (and
it's patent-free).<br>
Its decoding requires single multiplication (uint32, but uint16
would be sufficient) per large symbol (max 16 size alphabet here)
and can directly work on CDF-only:<br>
<br>
s =symbol(x & mask); // SIMD to find s such that
CDF[s] <= (x & mask) < CDF[s+1]<br>
x = (CDF[s+1] - CDF[s]) * (x >> n) + (x & mask) -
CDF[s];<br>
if (x < 2^16) x = x << 16 + read16bits();<br>
<br>
Then symbol-wise adaptation is also SIMD-able (max 16 size
alphabet) - for prepared mixCDF[s,i]:<br>
<pre><i>for (int i = 1; i < m; i++) CDF[i] -= (CDF[i] - mixCDF[s,i]) >> rate;</i></pre>
<br>
VP10 has initially planned to use ANS only for DCT, but now it's
everywhere:<br>
<a class="moz-txt-link-freetext" href="https://chromium.googlesource.com/webm/libvpx/+/fb9186d68d498919b290d7f444560f44a1d8d1df">https://chromium.googlesource.com/webm/libvpx/+/fb9186d68d498919b290d7f444560f44a1d8d1df</a><br>
<a class="moz-txt-link-freetext" href="https://chromium.googlesource.com/webm/libvpx/+/c961bcc594a642f31777df725e0c3698de8e4117">https://chromium.googlesource.com/webm/libvpx/+/c961bcc594a642f31777df725e0c3698de8e4117</a><br>
<br>
Kind Regards,<br>
Jarek<br>
<br>
<br>
On 16/04/24 18:27, Aaron Boxer wrote:<br>
</div>
<blockquote
cite="mid:CAK8GPyD=et-qk+a6+hSJ+KnWxHoX4-2HEsnh8QQbRBBO4AWmHQ@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>
<div>
<div>
<div>
<div>
<div>
<div>
<div>Hi Jarek,<br>
<br>
</div>
Excellent! I hope these efficiency improvements
that you are proposing will get adopted, or at
least investigated.<br>
</div>
<br>
I don't know much about arithmetic coding, but
according to Wikipedia, CABAC is considered one of
the primary reasons<br>
</div>
for H.264 and H.265 coding efficiency being superior
to predecessors. So, using rANS and the other
techniques you mention<br>
</div>
should give Daala a distinct advantage. <br>
<br>
</div>
The only reasons I can think of for them *not* being
adopted would be:<br>
<br>
</div>
1) increased codec complexity (the issue that JPEG 2000
foundered on)<br>
</div>
2) patents (another issue with JPEG 2000)<br>
</div>
3) Not Invented Here Syndrome (TM)<br>
<div>
<div>
<div>
<div><br>
</div>
<div>Kind Regards,<br>
</div>
<div>Aaron<br>
</div>
<div>
<div>
<div>
<div><br>
<br>
<div>
<div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Sun, Apr 24,
2016 at 10:43 AM, Jarek Duda <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:dudajar@gmail.com"
target="_blank">dudajar@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote"
style="margin:0 0 0 .8ex;border-left:1px
#ccc solid;padding-left:1ex">
<div bgcolor="#FFFFFF" text="#000000">
<div>Hi Aaron,<br>
<br>
I had some discussion and analysis
regarding their coding part, and
there is a few percents to easily
squeeze there (5-10%).<br>
In contrast to nasty CABAC scheme -
start with binarization then try to
model these bits, Daala has very
nice general scheme: <br>
send to coding part sequence of (ID,
symbol),<br>
where symbol is from up to size 16
alphabet,<br>
each ID is statistically modeled as
independent random variable - hence
ID itself contains both data type
and context (like neighborhood). <br>
<br>
However, they have a few
inefficiencies:<br>
1) start each frame with flat
uniform probability distribution
(this is the worst!),<br>
2) use approximated multi-symbol
range coder:
<a moz-do-not-send="true"
href="https://people.xiph.org/%7Etterribe/tmp/StuiverMoffat98-%20Piecewise%20Integer%20Mapping%20for%20Arithmetic%20Coding.pdf"
target="_blank">https://people.xiph.org/~tterribe/tmp/StuiverMoffat98-%20Piecewise%20Integer%20Mapping%20for%20Arithmetic%20Coding.pdf</a><br>
the cost of this approximation is
1-3% ratio loss for binary alphabet:
<a moz-do-not-send="true"
href="https://dl.dropboxusercontent.com/u/12405967/Moffat.nb"
target="_blank">https://dl.dropboxusercontent.com/u/12405967/Moffat.nb</a><br>
3) use costly every symbol
adaptation (mainly to handle the
flat initial distribution problem),
but with <br>
freq[s] = count[s] / total<br>
poor type of adaptation: a symbol
far in the past has the same
influence on the probability as the
most recent symbols,<br>
4) use fixed adaptation rate.<br>
<br>
These can be improved by:<br>
1) Start with a probability
distribution characteristic for a
given ID, for example a fixed
parametric, eventually modified
somewhere in the file (better
behaves in the beginning and allows
for more subtle adaptation),<br>
2) use an accurate entropy coder,
like rANS in VP10,<br>
3) use adaptation with exponential
forgetting to make recent symbol
more important, like <br>
for (int i = 1; i < m; i++)
CDF[i] -= (CDF[i] - mixCDF[i])
>> rate; <br>
where mixCDF is for the new part,
can be tabled for symbol-wise
adaptation such that frequencies of
not used symbol will drop to the
minimal nonzero frequency,<br>
4) Allow for varying adaptation rate
- for example some ID use more
static probability distribution, for
some it is beneficial to allow
encoder to choose one of a few
possible adaptation rates.<br>
<br>
Kind regards,<br>
Jarek Duda
<div>
<div class="h5"><br>
<br>
<br>
<br>
On 16/04/24 05:36, Aaron Boxer
wrote:<br>
</div>
</div>
</div>
<blockquote type="cite">
<div>
<div class="h5">
<div dir="ltr">
<div>
<div>
<div>Dear Daala-istas,<br>
<br>
</div>
I took a look at the PSNR
and PSNR-HVS charts for
daala vs H.264 and H.265.<br>
</div>
May I ask at what PSNR value
you would consider Daala to
be competitive with H.265 ?
From the graph, it looks
like you are asymptotically
matching H.264 quality, but
there is still significant
difference with HEVC, and
progress is flattening out.
<br>
<br>
</div>
<div>I don't mean to be that
guy, but when do you think
you will be able to meet
your project goal of meeting
or beating HEVC quality? I
am asking because I think
this is a great project, and
want to see it beating out
the $$-driven competition.<br>
<br>
<br>
</div>
<div>Kind Regards,<br>
</div>
<div>Aaron Boxer<br>
<br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<br>
<div><br>
</div>
</div>
<br>
<fieldset></fieldset>
<br>
</div>
</div>
<span class="">
<pre>_______________________________________________
daala mailing list
<a moz-do-not-send="true" href="mailto:daala@xiph.org" target="_blank">daala@xiph.org</a>
<a moz-do-not-send="true" href="http://lists.xiph.org/mailman/listinfo/daala" target="_blank">http://lists.xiph.org/mailman/listinfo/daala</a>
</pre>
</span></blockquote>
<span class="HOEnZb"><font
color="#888888"> <br>
<br>
<pre cols="72">--
dr Jarosław Duda
Institute of Computer Science and Computer Mathematics,
Jagiellonian University, Cracow, Poland
<a moz-do-not-send="true" href="http://th.if.uj.edu.pl/%7Edudaj/" target="_blank">http://th.if.uj.edu.pl/~dudaj/</a></pre>
</font></span></div>
<br>
_______________________________________________<br>
daala mailing list<br>
<a moz-do-not-send="true"
href="mailto:daala@xiph.org">daala@xiph.org</a><br>
<a moz-do-not-send="true"
href="http://lists.xiph.org/mailman/listinfo/daala"
rel="noreferrer" target="_blank">http://lists.xiph.org/mailman/listinfo/daala</a><br>
<br>
</blockquote>
</div>
<br>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<br>
<br>
<pre class="moz-signature" cols="72">--
dr Jarosław Duda
Institute of Computer Science and Computer Mathematics,
Jagiellonian University, Cracow, Poland
<a class="moz-txt-link-freetext" href="http://th.if.uj.edu.pl/~dudaj/">http://th.if.uj.edu.pl/~dudaj/</a></pre>
</body>
</html>