ltkdynamictimewarping.h

An open source handwriting recongnition package!!!

/*****************************************************************************************
* Copyright (c) 2006 Hewlett-Packard Development Company, L.P.
* Permission is hereby granted, free of charge, to any person obtaining a copy of 
* this software and associated documentation files (the "Software"), to deal in 
* the Software without restriction, including without limitation the rights to use, 
* copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the 
* Software, and to permit persons to whom the Software is furnished to do so, 
* subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
* INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A 
* PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
* CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE 
* OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 
*****************************************************************************************/

/************************************************************************
 * SVN MACROS
 *
 * $LastChangedDate: 2008-01-11 14:11:25 +0530 (Fri, 11 Jan 2008) $
 * $Revision: 359 $
 * $Author: sundarn $
 *
 ************************************************************************/
#ifndef __DYNAMICTIMEWARPING_H
#define __DYNAMICTIMEWARPING_H

#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#ifndef _WIN32
#include <values.h>
#endif
#include <limits>
#include <algorithm>
#include <cmath>
#include <deque>


using namespace std;

template <typename TimeSeriesElementType, typename DistanceType>
//TimeSeriesElementType - pointer of type feature (LTKShapeFeature * etc.)
//DistanceType - type of distance (float, int etc.)



/**
 * @class DTWShapeRecognizer
 */
class DynamicTimeWarping
{
    private:

        vector<vector <DistanceType> > m_cumulativeDistance;		// Cumulative distance matrix

        vector<vector<int> > m_phi;						// phi matrix required for path computation

        //function pointer type of the function that defines local distance function
        typedef int (*FN_PTR_DISTANCE)(const TimeSeriesElementType&, const TimeSeriesElementType&, DistanceType&) ; 								


        DistanceType m_maxVal;	
        // Max val (like FLT_MAX etc),  
        // this max value that can be returned
        // local distance			


        /**
         * This function back tracks and calculates the DTW warping path from the DTW distance matrix
         * @param1 lastPointYIndex is the x index of the point from which back tracking has to start
         * @param1 lastPointXIndex is the y index of the point from which back tracking has to start
         */
        void populatePath(int lastPointYIndex, int lastPointXIndex, deque<vector<int> >& warpingPath)
        {

            int yIndex = lastPointYIndex;
            int xIndex = lastPointXIndex;
            vector<int > indices(2);
            int tb;					// req for warping path
            int k,p;				// loop variables

            //Path Computation

            indices[0] = yIndex;
            indices[1] = xIndex;
            warpingPath.push_front(indices);

            while((yIndex > 0) && (xIndex > 0))
            {
                tb = m_phi[yIndex][xIndex];
                if (tb == 2)
                {
                    yIndex--; 
                    xIndex--;
                    indices[0] = yIndex;
                    indices[1] = xIndex;
                }
                else if(tb == 0)
                {
                    yIndex--;
                    indices[0] = yIndex;
                    indices[1] = xIndex;
                }
                else if (tb == 1)
                {
                    xIndex--;
                    indices[0] = yIndex;
                    indices[1] = xIndex;
                }

                warpingPath.push_front(indices);

            }

            if((yIndex > 0) && (xIndex == 0))
            {
                --yIndex;
                for(k = yIndex; k >= 0; --k)
                { 
                    indices[0]  = (k);
                    indices[1] = (0);
                    warpingPath.push_front(indices);
                }
            }
            else if(( yIndex == 0) && (xIndex > 0))
            {
                --xIndex;
                for(p = xIndex; p >= 0; --p)
                { 
                    indices[0]  = (0);
                    indices[1] = (p);
                    warpingPath.push_front(indices);
                }
            }

        }

    public:



        /** @name Constructors and Destructor */
        //@{

        /**
         * This Constructor takes the size of the input train character, 
         * size of input test character, Max Value (ie FLT_MAX, INT_MAX etc)
         * Local distance function, reduce by half function, and banding value
         */

        DynamicTimeWarping()
        {


        }


        /**
         * Destructor
         */

        ~DynamicTimeWarping(){};

        /**
         * @name Methods
         */

        //@{


        /**
         * This function computes the DTW distance between the two vectors.
         * @param train This is an input parameter and corresponds to the first vector
         * @param test This is an input parameter and corresponds to the second vector
         * @param local This is the function pointer to the local distance function 
         * @param distanceDTW This is the output parameter which gives the DTW distance between the two vectors.
         * @param warpingPath This is the output parameter which gives DTW warping path
         * @param banding This is the banding value for the DTW Matrix
         * @param bestSoFar This is an imput parameter as stoping criteria based on Best So Far
         * @param maxVal This is used to pass the maximum possible value for the DTW distance
         */
/*
        int computeDTW(const vector <TimeSeriesElementType>& train, 
                const vector <TimeSeriesElementType>& test,
                FN_PTR_DISTANCE localDistPtr, 
                DistanceType& distanceDTW, 
                deque<vector<int> >& warpingPath, 
                int banding=0, DistanceType bestSoFar=numeric_limits<DistanceType>::infinity(),
                DistanceType maxVal=numeric_limits<DistanceType>::infinity())
                */
        int computeDTW(const vector <TimeSeriesElementType>& train, 
                const vector <TimeSeriesElementType>& test,
                FN_PTR_DISTANCE localDistPtr, 
                DistanceType& distanceDTW, 
                deque<vector<int> >& warpingPath, 
                float banding=0, DistanceType bestSoFar=numeric_limits<DistanceType>::infinity(),
                DistanceType maxVal=numeric_limits<DistanceType>::infinity())

        {
            m_maxVal = maxVal;
            if(localDistPtr == NULL)
            {
                /*LOG(LTKLogger::LTK_LOGLEVEL_ERR)
                  <<"Error : "<< ENULL_POINTER <<":"<< getErrorMessage(ENULL_POINTER)
                  <<" DynamicTimeWarping::computeDTW()" <<endl;*/

                LTKReturnError(ENULL_POINTER);
            }
            int trainSize = train.size(); //Temporary variables to store the size of the train and test vectors.
            if(trainSize == 0)
            {
                /*LOG(LTKLogger::LTK_LOGLEVEL_ERR)
                  <<"Error : "<< EEMPTY_VECTOR <<":"<< getErrorMessage(EEMPTY_VECTOR)
                  <<" DynamicTimeWarping::computeDTW()" <<endl;*/
                LTKReturnError(EEMPTY_VECTOR);
            }
            int testSize = test.size();	//Temporary variables to store the size of the train and test vectors.
            if(testSize == 0)
            {
                /*LOG(LTKLogger::LTK_LOGLEVEL_ERR)
                  <<"Error : "<< EEMPTY_VECTOR <<":"<< getErrorMessage(EEMPTY_VECTOR)
                  <<" DynamicTimeWarping::computeDTW()" <<endl;*/
                LTKReturnError(EEMPTY_VECTOR);
            }

            banding = floor(testSize*(1-banding));
            int banded = 0;
            
            if(banding < 0 || banding >= trainSize || banding >= testSize)
            {
                /*LOG(LTKLogger::LTK_LOGLEVEL_ERR)
                  <<"Error : "<< ENEGATIVE_NUM <<":"<< getErrorMessage(ENEGATIVE_NUM)
                  <<" DynamicTimeWarping::computeDTW()" <<endl;*/

                LTKReturnError(ECONFIG_FILE_RANGE);
            }
            else
            {
                banded = banding;	     // is the variable used for fixing the band in the computation of the distance matrix.
                // this is the number of elements from the matrix
                // boundary for which computation will be skipped
            }

            int trunkI = banded; //Temporary variables used to keep track of the band in the distance matrix.

            int	trunkJ = 0;	//Temporary variables used to keep track of the band in the distance matrix.

            int i,j,l; //index variables

            if(m_cumulativeDistance.size() == 0)
            {
                vector <DistanceType> dVec(testSize,m_maxVal);
                vector <int> phiVec(testSize,0);

                for(i = 0; i < trainSize; ++i)
                {
                    m_cumulativeDistance.push_back(dVec);
                    m_phi.push_back(phiVec);	
                }
            }
            else if(trainSize > m_cumulativeDistance.size() || testSize > m_cumulativeDistance[0].size())
            {
                m_cumulativeDistance.clear();
                m_phi.clear();
                vector <DistanceType> dVec(testSize,m_maxVal);
                vector <int> phiVec(testSize,0);

                for(i = 0; i < trainSize; ++i)
                {
                    m_cumulativeDistance.push_back(dVec);
                    m_phi.push_back(phiVec);	
                }

            }
            else
            {