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

Linux Cross Reference
Tina5/tina-libs/tina/vision/visMatch_mdp.c

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

  1 /**********
  2  *
  3  * This file is part of the TINA Open Source Image Analysis Environment
  4  * henceforth known as TINA
  5  *
  6  * TINA is free software; you can redistribute it and/or modify
  7  * it under the terms of the GNU Lesser General Public License as
  8  * published by the Free Software Foundation.
  9  *
 10  * TINA is distributed in the hope that it will be useful,
 11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
 12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 13  * GNU Lesser General Public License for more details.
 14  *
 15  * You should have received a copy of the GNU Lesser General Public License
 16  * along with TINA; if not, write to the Free Software Foundation, Inc.,
 17  * 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 18  *
 19  **********
 20  *
 21  * Program :    TINA
 22  * File    :  $Source: /home/tina/cvs/tina-libs/tina/vision/visMatch_mdp.c,v $
 23  * Date    :  $Date: 2008/12/09 00:15:22 $
 24  * Version :  $Revision: 1.4 $
 25  * CVS Id  :  $Id: visMatch_mdp.c,v 1.4 2008/12/09 00:15:22 paul Exp $
 26  *
 27  * Author  : Legacy TINA
 28  *
 29  * Notes :
 30  * 
 31  * general routines for perfoming dynamic programming over a list of
 32  * matches
 33  * 
 34  * match indices are held in the DP_INDEX property of the match
 35  * 
 36  * the indices (ints) indicate the monoticity of the underlying problem 
 37  *
 38  *********
 39 */
 40 
 41 #include "visMatch_mdp.h"
 42 
 43 #if HAVE_CONFIG_H
 44   #include <config.h>
 45 #endif
 46 
 47 #include <string.h>
 48 #include <math.h>
 49 #include <tina/sys/sysDef.h>
 50 #include <tina/sys/sysPro.h>
 51 #include <tina/vision/vis_MatchDef.h>
 52 #include <tina/vision/vis_MatchPro.h>
 53 
 54 /* static variables to maitain DP array
 55  * 
 56  * prevents repeted allocation and freeing of these data structures
 57  * 
 58  * a large array is allocated prior to dynamic programming over match
 59  * lists. */
 60 
 61 static int dp_size;
 62 static Dpnode **dp_array;       /* the DP array */
 63 static int *low, *up;           /* lower and upper indices into DP
 64                                  * array */
 65 
 66 void    dp_mlist_build(int s)
 67 {
 68     if (s <= dp_size)
 69         return;
 70     narray_free((char **) dp_array, 0, dp_size, 0, dp_size, sizeof(Dpnode));
 71     rfree((void *) low);
 72     rfree((void *) up);
 73     dp_size = s;
 74     dp_array = ts_narray_alloc(0, 0, dp_size, dp_size, Dpnode);
 75     low = (int *) ralloc((unsigned) (sizeof(int *) * dp_size));
 76     up = (int *) ralloc((unsigned) (sizeof(int *) * dp_size));
 77 }
 78 
 79 /* adjust low and up values between first and last to represent a
 80  * minimally valid and fully connected DP array. */
 81 void    form_valid_dp_array(int *low, int *up, int firsti, int lasti, int minj)
 82 {
 83     int     i, m;
 84 
 85     /* make DP array a strict envelope */
 86 
 87     for (i = firsti; i <= lasti; ++i)
 88         if (low[i] > minj)
 89             --low[i];
 90 
 91     for (i = firsti; i < lasti; ++i)
 92     {
 93         if (up[i + 1] > up[i])
 94             up[i] = up[i + 1] - 1;
 95     }
 96 
 97     m = up[firsti];
 98     for (i = firsti + 1; i <= lasti; ++i)
 99     {
100         if (up[i] > m)
101             m = up[i];
102         else
103             up[i] = m;
104     }
105 
106     m = low[lasti];
107     for (i = lasti - 1; i >= firsti; --i)
108     {
109         if (low[i] != -1 && low[i] < m)
110             m = low[i];
111         else
112             low[i] = m;
113     }
114 
115     /* ensure fully connected envelope */
116     for (i = firsti; i < lasti; ++i)
117     {
118         if (up[i] < low[i])
119             up[i] = low[i];
120         if (up[i] < low[i + 1])
121             up[i] = low[i + 1];
122     }
123 }
124 
125 void    mlist_set_dp_indices(List * mlist, int (*index_func) ( /* ??? */ ), void *data)
126 {
127     List   *lptr;
128 
129     for (lptr = mlist; lptr != NULL; lptr = lptr->next)
130     {
131         int     to1, to2;
132         Match  *m = (Match *) lptr->to;
133         Pair   *p;
134 
135         to1 = index_func(m->to1, m->type, data);
136         to2 = index_func(m->to2, m->type, data);
137         p = pair_make((void *) to1, 0, (void *) to2, 0);
138         m->props = proplist_addifnp(m->props, (void *) p, DP_INDEX, rfree, true);
139     }
140 }
141 
142 List   *dp_mlist(List * list, double (*cost_func) ( /* ??? */ ))
143 /* list of list of matches in assending order */
144 
145 {
146     List   *ptr;
147     Match  *match;
148     Pair   *indices;
149     int     firsti, lasti, maxj, minj;
150     int     i, j, n;
151 
152     if (list == NULL)
153         return (NULL);
154 
155     for (n = 0, ptr = list; ptr != NULL; ptr = ptr->next)
156     {
157         match = (Match *) ptr->to;
158         indices = (Pair *) prop_get(match->props, DP_INDEX);
159         if (indices == NULL)
160             return (NULL);
161         i = (int) indices->to1;
162         if (i > n)
163             n = i;
164     }
165     n++;
166 
167     if (n > dp_size)
168     {
169         error("dp_mlist: dynamic programming table limit exeeded", warning);
170         return (NULL);
171     }
172     for (i = 0; i < n; ++i)
173         low[i] = up[i] = -1;
174 
175     maxj = 0;
176     minj = dp_size - 1;
177     for (ptr = list; ptr != NULL; ptr = ptr->next)
178     {
179         match = (Match *) ptr->to;
180         indices = (Pair *) prop_get(match->props, DP_INDEX);
181         i = (int) indices->to1;
182         j = (int) indices->to2;
183 
184         if (low[i] == -1 || j < low[i])
185             low[i] = j;
186         if (up[i] == -1 || j > up[i])
187             up[i] = j;
188         if (j > maxj)
189             maxj = j;
190         if (j < minj)
191             minj = j;
192     }
193 
194     if (maxj > dp_size)
195     {
196         error("dp_mlist: dynamic programming table limit exeeded", warning);
197         return (NULL);
198     }
199     /* find range of used values */
200     for (i = 0; i < n; ++i)
201         if (low[i] != -1)
202             break;
203     firsti = i;
204     lasti = n - 1;
205 
206     if (firsti > lasti)
207         return (NULL);
208 
209     form_valid_dp_array(low, up, firsti, lasti, minj);
210 
211     /* initialise DP array elements */
212 
213     for (i = firsti; i <= lasti; ++i)
214         (void) memset((char *) &dp_array[i][low[i]], 0, (up[i] - low[i] + 1) * sizeof(Dpnode));
215 
216     /* fill in values from match list */
217 
218     for (ptr = list; ptr != NULL; ptr = ptr->next)
219     {
220         match = (Match *) ptr->to;
221         indices = (Pair *) prop_get(match->props, DP_INDEX);
222         i = (int) indices->to1;
223         j = (int) indices->to2;
224 
225         dp_array[i][j].data = (void *) match;
226         if (cost_func == NULL)
227             dp_array[i][j].cost = match->weight;
228         else
229             dp_array[i][j].cost = (float)cost_func(match);
230     }
231 
232     dp_accum(dp_array, low, up, firsti, lasti);
233     list = dp_solution(dp_array, low, up, firsti, lasti);
234 
235     return (list);
236 }
237 

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