[SciPy-user] Algorithm of Viterbi

Stefan van der Walt stefan@sun.ac...
Tue Dec 4 15:29:25 CST 2007


Hi Dorian

On Mon, Dec 03, 2007 at 08:26:52PM +0100, Dorian wrote:
> I downloaded the files but I don't understand how to compile and for which
> example this algorithm works.

Sorry, I don't know how to compile things under Windows.  Maybe some
other people on the list have experience with ctypes on that platform.

> Could you please give me a clear explanation step by step how it works ?
> I'm using python on Windows .

There are two functions, "find" and "remove".  I wrote these to see
how well the seam carving algorithm in

  http://www.shaiavidan.org/papers/imretFinal.pdf

works.  The first finds the shortest path through the image, and the
last removes that path.  It is a trivial matter to modify the
algorithm to look for minimal path cost, instead of minimal
difference cost.

Now that I think about it, there is an approximation to Viterbi that
is even easier to implement -- simply take the maximum position in
each column.  It doesn't give the best path (it is not even guaranteed
to be connected), but often it is a good approximation, and it is easy
to implement.  See for example

  http://www.cs.colostate.edu/~hamiltom/hmm/hmm.txt

I can also suggest the following article, which gives a very good
overview of HMMs and Viterbi:

  http://dx.doi.org/10.1109/5.18626

Cheers
Stéfan


More information about the SciPy-user mailing list