changeset 191:f415747b151b re-minimise

Normalised path costs should use a different type from un-normalised ones (because they are in a different range)

--- a/src/Finder.cpp	Thu Feb 26 15:51:50 2015 +0000
+++ b/src/Finder.cpp	Thu Feb 26 15:52:16 2015 +0000
@@ -55,13 +55,13 @@
 }
 
 bool
-Finder::getBestRowCost(int row, int &bestCol, pathcost_t &min)
+Finder::getBestRowCost(int row, int &bestCol, normpathcost_t &min)
 {
     if (!m_m->isRowAvailable(row)) return false;
     pair<int, int> colRange = m_m->getColRange(row);
     if (colRange.first >= colRange.second) return false;
     for (int index = colRange.first; index < colRange.second; index++) {
-        pathcost_t tmp = m_m->getNormalisedPathCost(row, index);
+        normpathcost_t tmp = m_m->getNormalisedPathCost(row, index);
         if (index == colRange.first || tmp < min) {
             min = tmp;
             bestCol = index;
@@ -71,14 +71,17 @@
 }    
 
 bool
-Finder::getBestColCost(int col, int &bestRow, pathcost_t &min)
+Finder::getBestColCost(int col, int &bestRow, normpathcost_t &min)
 {
     if (!m_m->isColAvailable(col)) return false;
     pair<int, int> rowRange = m_m->getRowRange(col);
     if (rowRange.first >= rowRange.second) return false;
+    bestRow = rowRange.first;
     for (int index = rowRange.first; index < rowRange.second; index++) {
-        pathcost_t tmp = m_m->getNormalisedPathCost(index, col);
-        if (index == rowRange.first || tmp < min) {
+        normpathcost_t tmp = m_m->getNormalisedPathCost(index, col);
+        if (index == rowRange.first) {
+            min = tmp;
+        } else if (tmp < min) {
             min = tmp;
             bestRow = index;
         }
@@ -89,9 +92,9 @@
 void
 Finder::getBestEdgeCost(int row, int col,
                         int &bestRow, int &bestCol,
-                        pathcost_t &min)
+                        normpathcost_t &min)
 {
-    min = m_m->getPathCost(row, col);
+    min = m_m->getNormalisedPathCost(row, col);
     
     bestRow = row;
     bestCol = col;
@@ -101,7 +104,7 @@
         rowRange.second = row+1;	// don't cheat by looking at future :)
     }
     for (int index = rowRange.first; index < rowRange.second; index++) {
-        pathcost_t tmp = m_m->getNormalisedPathCost(index, col);
+        normpathcost_t tmp = m_m->getNormalisedPathCost(index, col);
         if (tmp < min) {
             min = tmp;
             bestRow = index;
@@ -113,7 +116,7 @@
         colRange.second = col+1;	// don't cheat by looking at future :)
     }
     for (int index = colRange.first; index < colRange.second; index++) {
-        pathcost_t tmp = m_m->getNormalisedPathCost(row, index);
+        normpathcost_t tmp = m_m->getNormalisedPathCost(row, index);
         if (tmp < min) {
             min = tmp;
             bestCol = index;
@@ -146,7 +149,7 @@
 
     int bestRow = row;
     int bestCol = col;
-    pathcost_t bestCost = -1;
+    normpathcost_t bestCost = -1;
 
 //    cerr << "Finder " << this << "::getExpandDirection: ";
     
@@ -362,7 +365,8 @@
              << ", advance in matrix is "
              << Matcher::advanceToString(err.advanceWas)
              << "\nPrev cost " << err.prevCost
-             << " plus distance " << err.distance << " [perhaps diagonalised] gives "
+             << " plus distance " << distance_print_t(err.distance)
+             << " [perhaps diagonalised] gives "
              << err.costShouldBe << ", matrix contains " << err.costWas
              << endl;
         cerr << "Note: diagonal weight = " << m_m->getDiagonalWeight() << endl;
@@ -380,7 +384,8 @@
         for (int j = -4; j <= 0; ++j) {
             cerr << setw(w) << j;
             for (int i = -4; i <= 0; ++i) {
-                cerr << setw(ww) << m_m->getDistance(err.r + j, err.c + i);
+                cerr << setw(ww)
+                     << distance_print_t(m_m->getDistance(err.r + j, err.c + i));
             }
             cerr << endl;
         }

--- a/src/Finder.h	Thu Feb 26 15:51:50 2015 +0000
+++ b/src/Finder.h	Thu Feb 26 15:52:16 2015 +0000
@@ -43,31 +43,32 @@
     void setDurations(int d1, int d2);
 
     /**
-     * Find the location and cost of the column with the cheapest path
-     * cost within the given row. If the row is out of range, return
-     * false and leave the bestCol and bestCost variables unchanged.
+     * Find the location and normalised path cost of the column with
+     * the cheapest path cost within the given row. If the row is out
+     * of range, return false and leave the bestCol and bestCost
+     * variables unchanged.
      */
-    bool getBestRowCost(int row, int &bestCol, pathcost_t &bestCost);
+    bool getBestRowCost(int row, int &bestCol, normpathcost_t &bestCost);
 
     /**
-     * Find the location and cost of the row with the cheapest path
-     * cost within the given column. If the column is out of range,
-     * return false and leave the bestRow and bestCost variables
-     * unchanged.
+     * Find the location and normalised path cost of the row with the
+     * cheapest path cost within the given column. If the column is
+     * out of range, return false and leave the bestRow and bestCost
+     * variables unchanged.
      */
-    bool getBestColCost(int col, int &bestRow, pathcost_t &bestCost);
+    bool getBestColCost(int col, int &bestRow, normpathcost_t &bestCost);
     
     /**
-     * Find the location and cost of the cheapest path cost within the
-     * final row and column of the search area, given that the area
-     * extends as far as the point at (row, col). This is used by
-     * getExpandDirection and can also be used, for example, to
-     * determine the current best estimate alignment for a frame we
-     * have just reached.
+     * Find the location and normalised path cost of the cheapest path
+     * cost within the final row and column of the search area, given
+     * that the area extends as far as the point at (row, col). This
+     * is used by getExpandDirection and can also be used, for
+     * example, to determine the current best estimate alignment for a
+     * frame we have just reached.
      */
     void getBestEdgeCost(int row, int col,
                          int &bestRow, int &bestCol,
-                         pathcost_t &bestCost);
+                         normpathcost_t &bestCost);
 
     /**
      * Calculate which direction to expand the search area in, given

--- a/src/MatchFeatureFeeder.cpp	Thu Feb 26 15:51:50 2015 +0000
+++ b/src/MatchFeatureFeeder.cpp	Thu Feb 26 15:52:16 2015 +0000
@@ -58,7 +58,7 @@
         return 0;
     }
     int bestRow = 0;
-    pathcost_t bestCost = 0;
+    normpathcost_t bestCost = 0;
     if (!m_finder.getBestColCost(m_pm2->getFrameCount()-1, bestRow, bestCost)) {
         return -1;
     } else {

--- a/src/MatchTypes.h	Thu Feb 26 15:51:50 2015 +0000
+++ b/src/MatchTypes.h	Thu Feb 26 15:52:16 2015 +0000
@@ -28,14 +28,17 @@
 /// The distance between two feature vectors
 typedef uint8_t distance_t;
 
-const int MaxDistance = 0xfe;
-const int InvalidDistance = 0xff;
+/// What to cast a distance_t to when printing it (to avoid printing as char)
+typedef int distance_print_t;
+
+const distance_t MaxDistance = 0xfe;
+const distance_t InvalidDistance = 0xff;
 
 /// The integrated distance (path cost) from the origin to a given point
 typedef uint32_t pathcost_t;
 
-const int MaxPathCost = 0xfffffffe;
-const int InvalidPathCost = 0xffffffff;
+const pathcost_t MaxPathCost = 0xfffffffe;
+const pathcost_t InvalidPathCost = 0xffffffff;
 
 /// A direction advance instruction or state
 enum advance_t : uint8_t {
@@ -57,6 +60,9 @@
 /// The distance between two feature vectors
 typedef float distance_t;
 
+/// What to cast a distance_t to when printing it
+typedef distance_t distance_print_t;
+
 const float MaxDistance = FLT_MAX;
 const float InvalidDistance = -1.f;
 
@@ -101,5 +107,8 @@
 /// A matrix of advance directions
 typedef std::vector<advancevec_t> advancemat_t;
 
+/// A normalised path cost, i.e. a pathcost_t divided by some scale factor
+typedef double normpathcost_t;
+
 
 #endif

--- a/src/Matcher.cpp	Thu Feb 26 15:51:50 2015 +0000
+++ b/src/Matcher.cpp	Thu Feb 26 15:52:16 2015 +0000
@@ -153,7 +153,8 @@
         if (dist == InvalidDistance) {
             cerr << "ERROR: Matcher::getDistance(" << i << ", " << j << "): "
                  << "Location is in range, but distance ("
-                 << dist << ") is invalid or has not been set" << endl;
+                 << distance_print_t(dist)
+                 << ") is invalid or has not been set" << endl;
             throw "Distance not available";
         }
         return dist;
@@ -168,7 +169,8 @@
     if (m_firstPM) {
         if (!isInRange(i, j)) {
             cerr << "ERROR: Matcher::setDistance(" << i << ", " << j << ", "
-                 << distance << "): Location is out of range" << endl;
+                 << distance_print_t(distance)
+                 << "): Location is out of range" << endl;
             throw "Indices out of range";
         }
         m_distance[i][j - m_first[i]] = distance;
@@ -177,11 +179,11 @@
     }
 }
 
-pathcost_t
+normpathcost_t
 Matcher::getNormalisedPathCost(int i, int j)
 {
     // normalised for path length. 1+ prevents division by zero here
-    return getPathCost(i, j) / (1 + i + j);
+    return normpathcost_t(getPathCost(i, j)) / normpathcost_t(1 + i + j);
 }
 
 pathcost_t

--- a/src/Matcher.h	Thu Feb 26 15:51:50 2015 +0000
+++ b/src/Matcher.h	Thu Feb 26 15:52:16 2015 +0000
@@ -238,7 +238,7 @@
      *  @return the cost of the minimum cost path to this location,
      *     normalised by the Manhattan distance from 0,0 to i,j
      */
-    pathcost_t getNormalisedPathCost(int i, int j);
+    normpathcost_t getNormalisedPathCost(int i, int j);
 
     /** Retrieves an advance direction from the matrix.
      *