ltkdynamictimewarping.h

An open source handwriting recongnition package!!!

                for(i=0; i<m_cumulativeDistance.size(); i++)
                {
                    for(j=0; j<m_cumulativeDistance[0].size();j++)
                    {
                        m_cumulativeDistance[i][j] = m_maxVal;
                        m_phi[i][j] = 0;
                    }
                }
            }

            DistanceType rowMin;	//Temporary variable which contains the minimum value of the distance of a row.

            DistanceType tempDist[2];	//Temporary variable to store the  distance

            DistanceType tempMinDist;	//Temporary variable to store the minimum distance

            DistanceType tempVal;

            int tempIndex;

            typename vector <vector<DistanceType> > ::iterator cumDistIter1;	//iterator for cumDist i
            typename vector<DistanceType> ::iterator cumDistIter2;	//iterator for cumDist j
            typename vector<DistanceType> ::iterator cumDistIter3;	//iterator for cumDist j 

            // TODO: error handling
            (localDistPtr)(train[0],test[0],m_cumulativeDistance[0][0]);

            m_phi[0][0]=2;	

            /**
              Computing the first row of the distance matrix.
             */

            cumDistIter2 = m_cumulativeDistance[0].begin();
            for(i = 1; i < testSize; ++i)
            {
                DistanceType tempVal;

                //TODO: error handling

                (localDistPtr)(train[0],test[i],tempVal);

                *(cumDistIter2 + i) = *(cumDistIter2 + i-1) + tempVal;
                m_phi[0][i]=1;
            }
            if(trunkI > 0)
            {
                --trunkI;
            }
            /**
              Computing the first column of the distance matrix.
             */

            for(j = 1; j < trainSize; ++j)
            {


                //TODO: error handling

                (localDistPtr)(train[j],test[0],tempVal);

                m_cumulativeDistance[j][0] = m_cumulativeDistance[j-1][0]+tempVal;
                m_phi[j][0]=0;
            }


            /**
              Computing the values of the rest of the cells in the distance matrix.
             */
            cumDistIter1 = m_cumulativeDistance.begin();
            for(i = 1; i < trainSize; ++i)
            {
                rowMin = m_maxVal;
                cumDistIter2 = (*(cumDistIter1+i-1)).begin();
                cumDistIter3 = (*(cumDistIter1+i)).begin();

                for(j = 1+trunkJ; j < testSize-trunkI; ++j)
                {
                    tempDist[0] = *(cumDistIter2+j-1);
                    tempIndex = 2;

                    tempMinDist = tempDist[0];
                    tempDist[0] = *(cumDistIter2+j);
                    tempDist[1] = *(cumDistIter3+j-1); 

                    for(l = 0; l < 2; ++l)
                    {
                        if(tempMinDist>=tempDist[l])
                        {
                            tempMinDist=tempDist[l];
                            tempIndex = l;
                        }
                    }

                    m_phi[i][j] = tempIndex;
                    localDistPtr(train[i],test[j],tempVal);
                    tempMinDist= tempMinDist+tempVal;
                    m_cumulativeDistance[i][j]=tempMinDist;

                    if(rowMin > tempMinDist)
                        rowMin = tempMinDist;

                }
                if(trunkI > 0)
                    --trunkI;
                if(i > (trainSize-banded-1))
                    ++trunkJ;

                if(rowMin > bestSoFar)
                {
                    distanceDTW = m_maxVal;
                    return SUCCESS;
                }
            }

            distanceDTW = tempMinDist;

            populatePath(trainSize-1,testSize-1,warpingPath);

            return SUCCESS;

        }	  


        /**
         * 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 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,  
                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,  
                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,k; //index variables
            vector<DistanceType> currentRow(testSize,m_maxVal);
            vector<DistanceType> previousRow(testSize,m_maxVal);

            DistanceType rowMin;		//Temporary variable which contains the minimum value of the distance of a row.

            DistanceType tempDist[3];	//Temporary variable to store the  distance

            DistanceType tempMinDist;	//Temporary variable to store the minimum distance

            DistanceType tempVal;

            // TODO: error handling
            (localDistPtr)(train[0],test[0],previousRow[0]);

            /**
              Computing the first row of the distance matrix.
             */

            for(i = 1; i < testSize; ++i)
            {

                //TODO: error handling
                (localDistPtr)(train[0],test[i],tempVal);
                previousRow[i] = previousRow[i-1] + tempVal;
            }
            if(trunkI > 0)
            {
                --trunkI;
            }


            for(i = 1; i < trainSize; ++i)
            {
                rowMin = m_maxVal;


                localDistPtr(train[i],test[0],tempVal);
                currentRow[0]=tempVal+previousRow[0];

                for(j = 1+trunkJ; j < testSize-trunkI; ++j)
                {

                    tempDist[0] = currentRow[j-1];
                    tempDist[1] = previousRow[j];
                    tempDist[2] = previousRow[j-1];

                    tempMinDist = tempDist[0];

                    for(k = 0; k < 3; k++)
                    {
                        if(tempMinDist>=tempDist[k])
                        {
                            tempMinDist=tempDist[k];
                        }
                    }

                    localDistPtr(train[i],test[j],tempVal);
                    tempMinDist= tempMinDist+tempVal;
                    currentRow[j]=tempMinDist;
                    if(rowMin > tempMinDist)
                        rowMin = tempMinDist;

                }
                copy(currentRow.begin(), currentRow.end(), previousRow.begin());
                if(trunkI > 0)
                    --trunkI;
                if(i > (trainSize-banded-1))
                    ++trunkJ;

                if(rowMin > bestSoFar)
                {
                    distanceDTW = m_maxVal;
                    return SUCCESS;
                }
            }

            distanceDTW = tempMinDist;

            return SUCCESS;

        }	  

};

#endif