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

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

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

  1 /**@(#)
  2 **/
  3 /* dp_mlist.c
  4  * 
  5  * general routines for perfoming dynamic programming over a list of
  6  * matches
  7  * 
  8  * match indices are held in the DP_INDEX property of the match
  9  * 
 10  * the indices (ints) indicate the monoticity of the underlying problem */
 11 
 12 #include <string.h>
 13 #include <tina/sys.h>
 14 #include <tina/sysfuncs.h>
 15 #include <tina/math.h>
 16 #include <tina/vision.h>
 17 #include <tina/visionfuncs.h>
 18 
 19 /* static variables to maitain DP array
 20  * 
 21  * prevents repeted allocation and freeing of these data structures
 22  * 
 23  * a large array is allocated prior to dynamic programming over match
 24  * lists. */
 25 
 26 static int dp_size;
 27 static Dpnode **dp_array;       /* the DP array */
 28 static int *low, *up;           /* lower and upper indices into DP
 29                                  * array */
 30 
 31 void    dp_mlist_build(int s)
 32 {
 33     if (s <= dp_size)
 34         return;
 35     narray_free((char **) dp_array, 0, dp_size, 0, dp_size, sizeof(Dpnode));
 36     rfree((void *) low);
 37     rfree((void *) up);
 38     dp_size = s;
 39     dp_array = ts_narray_alloc(0, 0, dp_size, dp_size, Dpnode);
 40     low = (int *) ralloc((unsigned) (sizeof(int *) * dp_size));
 41     up = (int *) ralloc((unsigned) (sizeof(int *) * dp_size));
 42 }
 43 
 44 /* adjust low and up values between first and last to represent a
 45  * minimally valid and fully connected DP array. */
 46 void    form_valid_dp_array(int *low, int *up, int firsti, int lasti, int minj)
 47 {
 48     int     i, m;
 49 
 50     /* make DP array a strict envelope */
 51 
 52     for (i = firsti; i <= lasti; ++i)
 53         if (low[i] > minj)
 54             --low[i];
 55 
 56     for (i = firsti; i < lasti; ++i)
 57     {
 58         if (up[i + 1] > up[i])
 59             up[i] = up[i + 1] - 1;
 60     }
 61 
 62     m = up[firsti];
 63     for (i = firsti + 1; i <= lasti; ++i)
 64     {
 65         if (up[i] > m)
 66             m = up[i];
 67         else
 68             up[i] = m;
 69     }
 70 
 71     m = low[lasti];
 72     for (i = lasti - 1; i >= firsti; --i)
 73     {
 74         if (low[i] != -1 && low[i] < m)
 75             m = low[i];
 76         else
 77             low[i] = m;
 78     }
 79 
 80     /* ensure fully connected envelope */
 81     for (i = firsti; i < lasti; ++i)
 82     {
 83         if (up[i] < low[i])
 84             up[i] = low[i];
 85         if (up[i] < low[i + 1])
 86             up[i] = low[i + 1];
 87     }
 88 }
 89 
 90 void    mlist_set_dp_indices(List * mlist, int (*index_func) ( /* ??? */ ), void *data)
 91 {
 92     List   *lptr;
 93 
 94     for (lptr = mlist; lptr != NULL; lptr = lptr->next)
 95     {
 96         int     to1, to2;
 97         Match  *m = (Match *) lptr->to;
 98         Pair   *p;
 99 
100         to1 = index_func(m->to1, m->type, data);
101         to2 = index_func(m->to2, m->type, data);
102         p = pair_make((void *) to1, (int) NULL, (void *) to2, (int) NULL);
103         m->props = proplist_addifnp(m->props, (void *) p, DP_INDEX, rfree, true);
104     }
105 }
106 
107 List   *dp_mlist(List * list, double (*cost_func) ( /* ??? */ ))
108 /* list of list of matches in assending order */
109 
110 {
111     List   *ptr;
112     Match  *match;
113     Pair   *indices;
114     int     firsti, lasti, maxj, minj;
115     int     i, j, n;
116 
117     if (list == NULL)
118         return (NULL);
119 
120     for (n = 0, ptr = list; ptr != NULL; ptr = ptr->next)
121     {
122         match = (Match *) ptr->to;
123         indices = (Pair *) prop_get(match->props, DP_INDEX);
124         if (indices == NULL)
125             return (NULL);
126         i = (int) indices->to1;
127         if (i > n)
128             n = i;
129     }
130     n++;
131 
132     if (n > dp_size)
133     {
134         error("dp_mlist: dynamic programming table limit exeeded", warning);
135         return (NULL);
136     }
137     for (i = 0; i < n; ++i)
138         low[i] = up[i] = -1;
139 
140     maxj = 0;
141     minj = dp_size - 1;
142     for (ptr = list; ptr != NULL; ptr = ptr->next)
143     {
144         match = (Match *) ptr->to;
145         indices = (Pair *) prop_get(match->props, DP_INDEX);
146         i = (int) indices->to1;
147         j = (int) indices->to2;
148 
149         if (low[i] == -1 || j < low[i])
150             low[i] = j;
151         if (up[i] == -1 || j > up[i])
152             up[i] = j;
153         if (j > maxj)
154             maxj = j;
155         if (j < minj)
156             minj = j;
157     }
158 
159     if (maxj > dp_size)
160     {
161         error("dp_mlist: dynamic programming table limit exeeded", warning);
162         return (NULL);
163     }
164     /* find range of used values */
165     for (i = 0; i < n; ++i)
166         if (low[i] != -1)
167             break;
168     firsti = i;
169     lasti = n - 1;
170 
171     if (firsti > lasti)
172         return (NULL);
173 
174     form_valid_dp_array(low, up, firsti, lasti, minj);
175 
176     /* initialise DP array elements */
177 
178     for (i = firsti; i <= lasti; ++i)
179         (void) memset((char *) &dp_array[i][low[i]], 0, (up[i] - low[i] + 1) * sizeof(Dpnode));
180 
181     /* fill in values from match list */
182 
183     for (ptr = list; ptr != NULL; ptr = ptr->next)
184     {
185         match = (Match *) ptr->to;
186         indices = (Pair *) prop_get(match->props, DP_INDEX);
187         i = (int) indices->to1;
188         j = (int) indices->to2;
189 
190         dp_array[i][j].data = (void *) match;
191         if (cost_func == NULL)
192             dp_array[i][j].cost = match->weight;
193         else
194             dp_array[i][j].cost = (float)cost_func(match);
195     }
196 
197     dp_accum(dp_array, low, up, firsti, lasti);
198     list = dp_solution(dp_array, low, up, firsti, lasti);
199 
200     return (list);
201 }
202 

~ [ 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.