## ffmpeg / doc / viterbi.txt @ ee028bbd

History | View | Annotate | Download (2.7 KB)

1 | dc7d978a | Michael Niedermayer | 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 |