Statistics
| Branch: | Revision:

ffmpeg / doc / viterbi.txt @ 54c5848d

1 2 3 dc7d978a Michael Niedermayer ```This is a quick description of the viterbi aka dynamic programing ``` ```algorthm. ``` ```Its reason for existence is that wikipedia has become very poor on ``` ```describing algorithms in a way that makes it useable for understanding ``` ```them or anything else actually. It tends now to describe the very same ``` ```algorithm under 50 different names and pages with few understandable ``` ```by even people who fully understand the algorithm and the theory behind. ``` ```Problem description: (that is what it can solve) ``` ```assume we have a 2d table, or you could call it a graph or matrix if you ``` ```prefer ``` ``` O O O O O O O ``` ``` O O O O O O O ``` ``` O O O O O O O ``` ``` O O O O O O O ``` ```That table has edges connecting points from each column to the next column ``` ```and each edge has a score like: (only some edge and scores shown to keep it ``` ```readable) ``` ``` O--5--O-----O-----O-----O-----O ``` ``` 2 / 7 / \ / \ / \ / ``` ``` \ / \ / \ / \ / \ / ``` ``` O7-/--O--/--O--/--O--/--O--/--O ``` ``` \/ \/ 1/ \/ \/ \/ \/ \/ \/ \/ ``` ``` /\ /\ 2\ /\ /\ /\ /\ /\ /\ /\ ``` ``` O3-/--O--/--O--/--O--/--O--/--O ``` ``` / \ / \ / \ / \ / \ ``` ``` 1 \ 9 \ / \ / \ / \ ``` ``` O--2--O--1--O--5--O--3--O--8--O ``` ```Our goal is to find a path from left to right through it which ``` ```minimizes the sum of the score of all edges. ``` ```(and of course left/right is just a convention here it could be top down too) ``` ```Similarly the minimum could be the maximum by just fliping the sign, ``` ```Example of a path with scores: ``` ``` O O O O O O O ``` ```>---O. O O .O-2-O O O ``` ``` 5. .7 . ``` ``` O O-1-O O O 8 O O ``` ``` . ``` ``` O O O O O O-1-O---> (sum here is 24) ``` ```The viterbi algorthm now solves this simply column by column ``` ```For the previous column each point has a best path and a associated ``` ```score: ``` ``` O-----5 O ``` ``` \ ``` ``` \ ``` ``` O \ 1 O ``` ``` \/ ``` ``` /\ ``` ``` O / 2 O ``` ``` / ``` ``` / ``` ``` O-----2 O ``` ```To move one column forward we just need to find the best path and associated ``` ```scores for the next column ``` ```here are some edges we could choose from: ``` ``` O-----5--3--O ``` ``` \ \8 ``` ``` \ \ ``` ``` O \ 1--9--O ``` ``` \/ \3 ``` ``` /\ \ ``` ``` O / 2--1--O ``` ``` / \2 ``` ``` / \ ``` ``` O-----2--4--O ``` ```Finding the new best pathes and scores for each point of our new column is ``` ```trivial given we know the previous column best pathes and scores: ``` ``` O-----0-----8 ``` ``` \ ``` ``` \ ``` ``` O \ 0----10 ``` ``` \/ ``` ``` /\ ``` ``` O / 0-----3 ``` ``` / \ ``` ``` / \ ``` ``` O 0 4 ``` ```the viterbi algorthm continues exactly like this column for column until the ``` ```end and then just picks the path with the best score (above that would be the ``` ```one with score 3) ``` ```Author: Michael niedermayer ``` ```Copyright LGPL ```