Rate–distortion optimization

<h2 id="background">Background</h2>
<p>The classical method of making encoding decisions is for the video encoder to choose the result which yields the highest quality output image.  However, this has the disadvantage that the choice it makes might require more bits while giving comparatively little quality benefit.  One common example of this problem is in <a href="/facts/Motion_estimation/FF2TIndo">motion estimation</a>,
<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
and in particular regarding the use of <a href="/facts/Qpel/zAsusDGn">quarter pixel-precision motion estimation</a>.  Adding the extra precision to the motion of a <a href="/facts/Macroblock/L7XPoRNP">block</a> during motion estimation might increase quality, but in some cases that extra quality isn't worth the extra bits necessary to encode the motion vector to a higher precision.
</p>
<h2 id="how-it-works">How it works</h2>
<p>Rate-distortion optimization solves the aforementioned problem by acting as a video quality metric, measuring both the deviation from the source material and the bit cost for each possible decision outcome.  The bits are mathematically measured by multiplying the bit cost by the <a href="/facts/Lagrange_multipliers/U5mSI5YP">Lagrangian</a>, a value representing the relationship between bit cost and quality for a particular quality level.  The deviation from the source is usually measured as the <a href="/facts/Mean_squared_error/kz3TR7bv">mean squared error</a>, in order to maximize the <a href="/facts/PSNR/FPlWpNkI">PSNR</a> video quality metric.
</p><p>Calculating the bit cost is made more difficult by the <a href="/facts/Entropy_encoding/44I0n8F8">entropy encoders</a> in modern video codecs, requiring the rate-distortion optimization algorithm to pass each block of video to be tested to the entropy coder to measure its actual bit cost.  In <a href="/facts/MPEG/ygmT7JBB">MPEG</a> codecs, the full process consists of a <a href="/facts/Discrete_cosine_transform/gPpDhPwP">discrete cosine transform</a>, followed by <a href="/facts/Quantization_(image_processing)/hXzWCrmY">quantization</a> and entropy encoding.  Because of this, rate-distortion optimization is much slower than most other block-matching metrics, such as the simple <a href="/facts/Sum_of_absolute_differences/8mdzPfPF">sum of absolute differences</a> (SAD) and <a href="/facts/Sum_of_absolute_transformed_differences/yk08Qv1R">sum of absolute transformed differences</a> (SATD).  As such it is usually used only for the final steps of the <a href="/facts/Motion_compensation/6BM2Ylxn">motion estimation</a> process, such as deciding between different partition types in <a href="/facts/H.264%2fAVC/soCzKcmJ">H.264/AVC</a>.
</p>
<h2 id="list-of-encoders-that-support-rdo">List of encoders that support RDO</h2>
<ul><li><a href="/facts/Ateme/JUmxe1cP">Ateme</a> <a href="/facts/H.264/soCzKcmJ">H.264</a> encoder</li>
<li><a href="/facts/Grass_Valley_(company)/ehRye4Q0">Grass Valley</a> ViBE encoders (SD & HD MPEG-2/MPEG-4)</li>
<li>Harmonic Electra 8000 encoder (SD & HD MPEG-2/MPEG-4)</li>
<li><a href="/facts/Libavcodec/69SFWWvw">libavcodec</a></li>
<li><a href="/facts/MainConcept/vKWXoWgV">MainConcept</a> <a href="/facts/H.264/soCzKcmJ">H.264</a> encoder</li>
<li><a href="/facts/Microsoft/nGIDDXdx">Microsoft</a> <a href="/facts/VC-1/KotHFF8I">VC-1</a> encoder</li>
<li><a href="/facts/Tandberg_Television/PaABkmu9">Tandberg Television</a> SD MPEG-2 EN8100</li>
<li><a href="/facts/Tandberg_Television/PaABkmu9">Tandberg Television</a> HD MPEG-4 EN8190</li>
<li><a href="/facts/Tandberg_Television/PaABkmu9">Tandberg Television</a> SD & HD MPEG-4 iPlex</li>
<li><a href="/facts/Theora/RnlKRQBb">Theora</a> 1.1-alpha1 and later (the "Thusnelda" branch)</li>
<li><a href="/facts/X264/owWXH5CL">x264</a> H.264 encoder</li>
<li><a href="/facts/X265/grbdzKzS">x265</a> H.265 encoder</li>
<li><a href="/facts/Xvid/CbpsozCI">Xvid</a> <a href="/facts/MPEG-4_ASP/qrahXdyN">MPEG-4 ASP</a> encoder</li>
<li><a href="/facts/H.264%2fAVC/soCzKcmJ">H.264/AVC</a> reference software JM (Joint Model)</li>
<li>H.264 / AVC / MPEG-4 AVC / MPEG-4 part 10 (Intel Quick Sync Video acceleration) hardware encoder</li>
<li><a href="/facts/HEVC/6gp7DC1a">HEVC</a> reference software HM (HEVC Test Model)</li>
<li>Kvazaar (partial)<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Hoang, D.T.; Long, P.M.; Vitter, Jeffrey (August 1998). "Rate-Distortion Optimizations for Motion Estimation in Low-Bitrate Video Coding" (PDF). IEEE Transactions on Circuits and Systems for Video Technology. 8 (4): 488–500. doi:10.1109/76.709413.
A shorter version appears in  Hoang, D.T.; Long, P.M.; Vitter, J.S. (March 1996). "Rate-distortion optimizations for motion estimation in low-bit-rate video coding". Digital Video Compression: Algorithms and Technologies 1996. Vol. 2668. SPIE. pp. 18–27. doi:10.1117/12.235433. <a href="/wiki/Jeffrey_Vitter" target="_blank">/wiki/Jeffrey_Vitter</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"Ultra Video Group". <a href="http://ultravideo.cs.tut.fi/#encoder" target="_blank">http://ultravideo.cs.tut.fi/#encoder</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Rate–distortion optimization open-in-new

Rate–distortion optimization