StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here's an implementation of the <a href="http://www.telecom.tuc.gr/~ntsourak/demo_viterbi.htm" rel="nofollow noreferrer">Viterbi algorithm</a> that I "discovered" recently. The purpose here is to decide the optimal distribution of frame types in video encoding. Viterbi itself is a bit hard to understand sometimes, so I think the best method is via actual example.</p> <p>In this example, Max Consecutive B-frames is 2. All paths must end with a P-frame.</p> <p>Path length of 1 gives us <code>P</code> as our best path, since all paths must end on a P-frame, there's no other choice.</p> <p>Path length of 2 gives us <code>BP</code> and <code>_P</code>. <code>"_"</code> is the best path of length 1. This gives us <code>BP</code> and <code>PP</code>. Now, we calculate the actual costs. Let's say, for the sake of this example, that BP is best.</p> <p>Path length of 3 gives us <code>BBP</code> and <code>_B</code>P and <code>__P</code>. <code>"__"</code> is the best path of length 2. This gives us <code>BBP</code> and <code>PBP</code> and <code>BPP</code>. Now, we calculate the actual costs. Let's say, for the sake of this example, that BBP is best.</p> <p>Path length of 4 gives us <code>_BBP</code> and <code>__BP</code> and <code>___P</code>. <code>"___"</code> is the best path of length 3. This gives us PBBP and BPBP and BBPP. Now, we calculate the actual costs. Let's say, for the sake of this example, that BPBP is best.</p> <p>Path length of 4 gives us <code>__BBP</code> and <code>___BP</code> and <code>____P</code>. <code>"____"</code> is the best path of length 4. This gives us <code>BPBBP</code> and <code>BBPBP</code> and <code>BPBPP</code>.</p> <p>Now--wait a minute--all of the paths agree that the first frame is a <code>B</code>! So the first frame is a <code>B</code>.</p> <p>Process is repeated until they agree on which frame is the first P-frame, and then encoding starts.</p> <p>This algorithm can be adapted to a huge variety of problems in many fields; its also the same algorithm I referred to in <a href="https://stackoverflow.com/questions/145676/how-to-approach-something-complex#145691">this post</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload