## ffmpeg / doc / viterbi.txt @ 43836928

History | View | Annotate | Download (2.7 KB)

1 |
This is a quick description of the viterbi aka dynamic programing |
---|---|

2 |
algorthm. |

3 | |

4 |
Its reason for existence is that wikipedia has become very poor on |

5 |
describing algorithms in a way that makes it useable for understanding |

6 |
them or anything else actually. It tends now to describe the very same |

7 |
algorithm under 50 different names and pages with few understandable |

8 |
by even people who fully understand the algorithm and the theory behind. |

9 | |

10 |
Problem description: (that is what it can solve) |

11 |
assume we have a 2d table, or you could call it a graph or matrix if you |

12 |
prefer |

13 | |

14 |
O O O O O O O |

15 | |

16 |
O O O O O O O |

17 | |

18 |
O O O O O O O |

19 | |

20 |
O O O O O O O |

21 | |

22 | |

23 |
That table has edges connecting points from each column to the next column |

24 |
and each edge has a score like: (only some edge and scores shown to keep it |

25 |
readable) |

26 | |

27 | |

28 |
O--5--O-----O-----O-----O-----O |

29 |
2 / 7 / \ / \ / \ / |

30 |
\ / \ / \ / \ / \ / |

31 |
O7-/--O--/--O--/--O--/--O--/--O |

32 |
\/ \/ 1/ \/ \/ \/ \/ \/ \/ \/ |

33 |
/\ /\ 2\ /\ /\ /\ /\ /\ /\ /\ |

34 |
O3-/--O--/--O--/--O--/--O--/--O |

35 |
/ \ / \ / \ / \ / \ |

36 |
1 \ 9 \ / \ / \ / \ |

37 |
O--2--O--1--O--5--O--3--O--8--O |

38 | |

39 | |

40 | |

41 |
Our goal is to find a path from left to right through it which |

42 |
minimizes the sum of the score of all edges. |

43 |
(and of course left/right is just a convention here it could be top down too) |

44 |
Similarly the minimum could be the maximum by just fliping the sign, |

45 |
Example of a path with scores: |

46 | |

47 |
O O O O O O O |

48 | |

49 |
>---O. O O .O-2-O O O |

50 |
5. .7 . |

51 |
O O-1-O O O 8 O O |

52 |
. |

53 |
O O O O O O-1-O---> (sum here is 24) |

54 | |

55 | |

56 |
The viterbi algorthm now solves this simply column by column |

57 |
For the previous column each point has a best path and a associated |

58 |
score: |

59 | |

60 |
O-----5 O |

61 |
\ |

62 |
\ |

63 |
O \ 1 O |

64 |
\/ |

65 |
/\ |

66 |
O / 2 O |

67 |
/ |

68 |
/ |

69 |
O-----2 O |

70 | |

71 | |

72 |
To move one column forward we just need to find the best path and associated |

73 |
scores for the next column |

74 |
here are some edges we could choose from: |

75 | |

76 | |

77 |
O-----5--3--O |

78 |
\ \8 |

79 |
\ \ |

80 |
O \ 1--9--O |

81 |
\/ \3 |

82 |
/\ \ |

83 |
O / 2--1--O |

84 |
/ \2 |

85 |
/ \ |

86 |
O-----2--4--O |

87 | |

88 |
Finding the new best pathes and scores for each point of our new column is |

89 |
trivial given we know the previous column best pathes and scores: |

90 | |

91 |
O-----0-----8 |

92 |
\ |

93 |
\ |

94 |
O \ 0----10 |

95 |
\/ |

96 |
/\ |

97 |
O / 0-----3 |

98 |
/ \ |

99 |
/ \ |

100 |
O 0 4 |

101 | |

102 | |

103 |
the viterbi algorthm continues exactly like this column for column until the |

104 |
end and then just picks the path with the best score (above that would be the |

105 |
one with score 3) |

106 | |

107 | |

108 |
Author: Michael niedermayer |

109 |
Copyright LGPL |

110 |