[FFmpeg-cvslog] r17772 - trunk/doc/viterbi.txt

[michael]

Author: michael
Date: Tue Mar  3 16:35:20 2009
New Revision: 17772

Log:
Quick desription of the viterbi algorithm so i dont have to repeat it
over and over again on the ML.

Added:
   trunk/doc/viterbi.txt

Added: trunk/doc/viterbi.txt
==============================================================================
--- /dev/null	00:00:00 1970	(empty, because file is newly added)
+++ trunk/doc/viterbi.txt	Tue Mar  3 16:35:20 2009	(r17772)
@@ -0,0 +1,110 @@
+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
+