gfiber / vendor / opensource / ffmpeg / 3d15d128df6c42df883fe3aedbbd2ef50085217f / . / doc / viterbi.txt

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 | |