On hidden Markov models and cyclic strings for shape recognition

• Starting point invariance in contour classification is not achieved with current HMM proposals.
• Cyclic strings are adequate for achieving starting point invariance.
• We modify the Baum–Welch and Viterbi algorithms for dealing with cyclic strings.
• A new model, cyclic linear HMMs, speeds up training and classification of cyclic strings.
• Our experiments show that our proposals outperform other methods in the literature.

Shape descriptions and the corresponding matching techniques must be robust to noise and invariant to transformations for their use in recognition tasks. Most transformations are relatively easy to handle when contours are represented by strings. However, starting point invariance is difficult to achieve. One interesting possibility is the use of cyclic strings, which are strings that have no starting and final points. We propose new methodologies to use Hidden Markov Models to classify contours represented by cyclic strings. Experimental results show that our proposals outperform other methods in the literature.