~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

Linux Cross Reference
Tina4/src/vision/match/dynamic.c

Version: ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /**@(#)
  2 **/
  3 /* dynamic.c
  4  * 
  5  * general routines for perfoming dynamic programming
  6  * 
  7  * the sum of weights of the matches is maximised.
  8  * 
  9  * the solution allows primitives to be skipped
 10  * 
 11  * on route to maximal solutions (missed matches score 0) */
 12 
 13 #include <tina/sys.h>
 14 #include <tina/sysfuncs.h>
 15 #include <tina/math.h>
 16 #include <tina/vision.h>
 17 
 18 #define INCLUDED(c,r) (c>=first && c<=last && r>=low[c] && r<=up[c])
 19 
 20 /* construct a list of match data (referenced in the DP array) starts
 21  * from the solution and walks back through the optimal path on the
 22  * basis of the type fields of the DP nodes */
 23 static List *back_track(int i, int j, Dpnode ** dp_array, int *low, int *up, int first, int last)
 24 {
 25     List   *list = NULL;
 26 
 27     while (INCLUDED(i, j))
 28     {
 29         Dpnode *dp = &dp_array[i][j];
 30 
 31         switch (dp->m_type)
 32         {
 33         case DP_MATCHED:
 34             if (dp->data != NULL)
 35                 list = ref_addtostart(list, (void *) dp->data, MATCH);
 36             i--;
 37             j--;
 38             break;
 39         case DP_PVTROW:
 40             i--;
 41             break;
 42         case DP_PVTCOL:
 43             j--;
 44             break;
 45         }
 46     }
 47     return (list);
 48 }
 49 
 50 /* find solution to DP that has been found by dp_accum
 51  * 
 52  * examine the last active row of the DP array for the highest value
 53  * solution and track it throgh the solution path collecting valid
 54  * matches along the way */
 55 List   *dp_solution(Dpnode ** dp_array, int *low, int *up, int first, int last)
 56 {
 57     int     i, j;
 58     float   max_sup;
 59     int     maxj;
 60 
 61     i = last;
 62     maxj = low[i];
 63     max_sup = dp_array[i][low[i]].m_tot;
 64     for (j = maxj + 1; j <= up[i]; ++j)
 65     {
 66         float   sup = dp_array[i][j].m_tot;
 67 
 68         if (sup > max_sup)
 69         {
 70             max_sup = sup;
 71             maxj = j;
 72         }
 73     }
 74 
 75     /* now we can back track from the solution */
 76     return (back_track(i, maxj, dp_array, low, up, first, last));
 77 }
 78 
 79 /* accumulate the DP array
 80  * 
 81  * 3 preceeding values are compared to update each node the type field is
 82  * set depening upon which is maximal */
 83 void    dp_accum(Dpnode ** dp_array, int *low, int *up, int first, int last)
 84 {
 85     int     i, j;
 86 
 87     for (i = first; i <= last; ++i)
 88     {
 89         for (j = low[i]; j <= up[i]; ++j)
 90         {
 91             Dpnode *dp_new = &dp_array[i][j];
 92             float   m_tot, r_prev = (float) 0.0, c_prev = (float) 0.0;
 93 
 94             /* compute best cost to this node */
 95 
 96             m_tot = dp_new->cost;
 97             if (INCLUDED(i - 1, j - 1))
 98                 m_tot += dp_array[i - 1][j - 1].m_tot;
 99             if (INCLUDED(i - 1, j))
100                 r_prev = dp_array[i - 1][j].m_tot;
101             if (INCLUDED(i, j - 1))
102                 c_prev = dp_array[i][j - 1].m_tot;
103 
104             if (m_tot > r_prev && m_tot > c_prev)
105             {
106                 dp_new->m_tot = m_tot;
107                 dp_new->m_type = DP_MATCHED;
108             } else if (c_prev > r_prev) /* prevented along the column */
109             {
110                 dp_new->m_tot = c_prev;
111                 dp_new->m_type = DP_PVTCOL;
112             } else
113             {
114                 /* prevented row best */
115                 dp_new->m_tot = r_prev;
116                 dp_new->m_type = DP_PVTROW;
117             }
118         }
119     }
120 }
121 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~ [ freetext search ] ~ [ file search ] ~

This page was automatically generated by the LXR engine.
Visit the LXR main site for more information.